Finding intersectionpoints that form rectangles

Question

I have a bunch of lines described by their direction as well as a point that describes its origin. I have to combine these lines to make them form rectangles that can lie within eachother, but their edges cannot overlap. I also know that the origin of the lines lie within an edge of a rectangle, but it does not necessarily lie in the middle of that edge. Basically the input I have could be something like this:

And what I'm trying to achieve looks something like this:

Where every line is now described by the points where it intersected the other lines to form the correct rectangles.

I'm looking for an algorithm that finds the relevant intersection points and links them to the lines that describe the rectangles.

user_2093077 · Answer

First of all, this problem as it was stated, may have multiple solutions. For example I don't see any constraint that invalidates the following:

So, you need to define an objective, for example:

maximize total covered are
maximize number of rectangles
maximize number of used lines
...

Here I'm trying to maximize number of rectangle using a greedy approach. Keep in mind that a greedy algorithm never guarantees to find the optimum solution, but finds a sub-optimal one in a reasonable time.

Now, there are two steps in my algorithm:

Find all possible rectangles
Select a set of rectangles that satisfy constrains

Step 1: Find all possible rectangles

Two vertical lines (l & r) plus two horizontal lines (b & t) can form a valid rectangle if:

l.x < r.x and b.y < t.y
l.y and r.y are between b.y and t.y
b.x and t.x are between l.x and r.x

In the following pseudocode, Xs and Ys are sorted lists of vertical and horizontal line respectively:

function findRectangles
    for i1 from 1 to (nx-1)
        for i2 from (i1+1) to nx
            for j1 from 1 to (ny-1)
                if (Ys[j1].x>=Xs[i1].x and
                        Ys[j1].x<=Xs[i2].x and
                        Ys[j1].y<=Xs[i1].y and
                        Ys[j1].y<=Xs[i2].y)
                    for j2 from (j1+1) to ny
                        if (Ys[j2].x>=Xs[i1].x and
                                Ys[j2].x<=Xs[i2].x and
                                Ys[j2].y>=Xs[i1].y and
                                Ys[j2].y>=Xs[i2].y)
                            add [i1 j1 i2 j2] to results
                        end if
                    end for
                end if
            end for
        end for
    end for
end

Step 2: Select valid rectangles

Valid rectangles, as stated in the problem, can not overlap partially and also can not share an edge. In previous step, too many rectangles are found. But, as I said before, there may be more than one combination of these rectangles that satisfy constraints. To maximize the number of rectangle I suggest the following algorithm that tends to accept smaller rectangles:

function selectRects( Xs, Ys, rects )
    results[];
    sort rectangles by their area;
    for i from 1 to rects.count
        if (non of edges of rects[i] are eliminated)&
                (rects[i] does not partially overlap any of items in results)
            add rects[i] to results;
            Xs[rects[i].left].eliminated = true;
            Xs[rects[i].right].eliminated = true;
            Ys[rects[i].bottom].eliminated = true;
            Ys[rects[i].top].eliminated = true;
        end if 
    end for
end

Finding intersectionpoints that form rectangles

1 Answers