plane sweepin

[gregorynoob]

heya... ok, so i was browsing the net to find out if there's a good text on this algorithm, but i don't seem to be able to find one. people are obviously using it, but, hey, there's no info on it.
the part i get is the theory on how it works... moving the line through the plane and stuff of that kind, but i've never, ever seen a simple, decent c++ implementation of it. i see people talking about starting events, stopping events, doing stuff like that, but i don't have any idea how i would implement that. could someone please help me?

[Narue]

>i've never, ever seen a simple, decent c++ implementation of it
Write one. That's what I do when I can't find a satisfactory implementation to pinch. Just find a good description of the algorithm and construct the code yourself; be careful not to get stuck on descriptions of an implementation, because you'll probably end up confusing yourself if you don't see the code (case in point, your confusion over the events).

[gregorynoob]

i would, but i'm really not talented in implementing something from scratch, my first mergesort took 10 secs to sort 100 integers, and even then, they weren't sorted. with msort it was easy cause i was able to look at other people's code, but this way, i'll never know is it good, or have i raised the complexity to...like a 10th power..?

[Narue]

>i'm really not talented in implementing something from scratch
There's no such thing as talent in programming, only experience. And you can only gain experience by doing it. My first merge sort was crappy too, but now I can crank out high quality implementations without batting an eyelash.

[gregorynoob]

okay, so i've tried...hard, seriously. and i'm stuck. i've implemented the events, and an imaginary set to hold them in, but i'm stuck at the actual sweeping part. the problem i'm trying to solve is box union, you're given a set of rectangles ( two diagonal points ) and gotta print the area of their union. this is the code of my sweep:

for( int i = 0; i < X.size(); ++i ) {
         int y_len = 0; // init for the y length for the inner sweep
         
         for( int j = 0; j < Y.size(); ++j ) { // inner sweep to get the  y length
              if( !A.cont( Y[j] ) ) continue;
              
              if( !B.empty() ) y_len += Y[j].value - Y[j-1].value;
              if( B.cont( Y[j] ) ) B.remove( Y[j] );
              else B.insert( Y[j] );
         }
         
         if( !A.empty() ) sol += y_len * ( X[i].value - X[i-1].value ); // outer sweep, adding up the area
         if( A.cont( X[i] ) ) A.remove( X[i] );
         else A.insert( X[i] );
    }

and.. i think i should mention: cont() is my memb. function for the set type, insert and remove also. A and B are set of events (segments in this example), X and Y are sorted sequences of events... can someone help me fix this part?
if you need the rest of the code, i can post it too! thanks!

[Lerner]

I can see getting the area of union of two rectangles defined by a series of three points. Is that good enough? I can also do it for a series of four points, if there isn't a common vertex.

[gregorynoob]

hmm, union of n rectangles, each defined by only two points, the segments are parallel with the lines of the system (x and y).

[Lerner]

I assume if you can do it for two arbitrary rectangles then you can do it for any given pair of rectangles in a group of n rectangles.

In general, if a rectangle is defined by two non adjacent points like p1(x1, y1) and p2(x2, y2), then, assuming x1 < x2 by definition, the length parallel to the x axis (call it width) is x2 - x1 and the length parallel to the y axix (call it height) is y2 - y1, assuming y1 < y2 by definition. The area is width times height.

The union of two rectangles means area of overlap of the two rectangles. That means if rectangle 1 is defined by (p1, p2) and rectangle 2 is defined by (p3, p4) where x1 < x2 and x3 < x4 by definition, then in order for there to be overlap if you sort x1, x2, x3 and x4 in ascending order. If the lowest two are x1 and x2 or x3 and x4 then there isn't overlap. If there is overlap then width of the overlap is difference between the second and third values in the sorted sequence. A similar procedure can be done with the y components to get the height of the overlap. This then should allow you to calculate the area of the overlap of any two rectangles oriented in with sides parallel to the x and y axis and each with x1 < x2 and y1 < y2.

Exactly how you plan to use this algorithm in a plane sweep algorithm I don't know.

[gregorynoob]

you're assuming too much, nobody guarantees any of those cases you mentioned. x1 < x2? why? it can be the opposite! also.. it isn't true that union is the area of the overlap.. it's the total area the rectangles cover together!

[Lerner]

Was my geometry class so long ago that I've forgotten the difference between union and intersection? I guess so! (sorry)

But don't despair. All that work hasn't gone for naught, at least in the scenario of two rectangles. I suspect the definition of the area of the union of two rectangles would be the total area of the two rectangles if they don't overlap and the total area of the two rectangles minus the area of overlap if they do overlap. Therefore, in the two rectangle scenario, knowing how to calculate the intersection of the two rectangles could be very helpful!

Determining the union of three (or more) rectangles does increase the complexity dramatically; and I confess I don't know how to do it using the computer. Manually I might find the perimeter of what I would call the irregular polygon formed by the external edges of all the overlapping rectangles and then chop up the irregular polygon into individual rectangles and add up the the total area of all the resultant rectangles. Alternatively, I might find the area of a bounding rectangle followed by the area of all the rectangular spaces between the bounding rectangle and the perimeter of the irregular polygon and then subtract the area of the spaces from the aread of the bounding rectangle. I seem to remember something about an algorithm for determining the external boundaries of irregular polygons somewhere. I'll see what I can find since it seems like an intriguing problem.

My reason for requiring x1 < x2 was to give some order to things so they aren't completely random. After all, the rectangle ((4, 3), (1, 2)) is the same as ((1, 2), (4,3)). So I elected to consider ordering the pair of points by the x component.

Sorry about the misdirection. No harm intended. Good luck.

[Lerner]

Here's a couple sites that might give you a little direction. You've probably been there, done that, but then again, maybe not.

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep

http://www.challenge-you.com/challenge?id=1797

Again, good luck. Looking at these sites the challenge is more than I'm up for at this point.

[Lerner]

The following was inspired by the TopCoder link in my
previous post and was conjured up while laying in bed
overnight suffering from insomnia. It was typed during
quiet times at work. If it doesn't make sense, now you
know why.

A rectangle can be defined by two nonconsecutive points
on the XY axis which can be ordered such that x1 < x2.
A rectangle always has four sides. In this
implementation each side will have the numerical value
and a char value:
left = x1, l
right = x2, r
top = y2 if y1 < y2 or y1 if not, t
bottom = y1 if y1 < y2 or y2 if not, b
A rectangle always has a width and height defined by:
width = right minus left
height = top minus bottom

The union of n rectangles with edges parrallel to the XY
axis can be viewed as one or more orthagonol polygons.
See the TopCoder link for a representative example.
To find the area of the union of n rectangles you can
decompose the orthagonol polygons into vertically
oriented rectangles and the sum of the area of each of
the component rectangles will be the sum of the
polygon.

Each component rectangle would be constructed within
columns. Each column will have the width calculated from
two adjacent values of x. Each column may have more than
one rectangle, meaning there will be gaps or space
between individual component rectangles if there is more
than one component rectangle per column. If you prefer,
each column can be viewed as chunks of the n rectangles
used to develop the orthagonol polygons. The chunks may
overlap, abut or be non-contiguous to each other.

My algorithm to find the area of the union of n
rectangles uses several ordered lists, which I would sort
on insertion. Some of the variables I would use include:
list<rectangle> nRectangles
list<rectangle> availableRectangles
list<rectangle> rectanglesUsedInColumn
list<int> Xs
list<side> Ys
rectangle currentRectangle
int peviousLine //the line is x = previous value of currentLine
int currentLine //the line is x = current value of x

The procedure will be to:
1) insert n rectangles into nRectangles and copy nRectangles
into availableRectangles
2) insert all unique values of x into Xs
3) assign x with the lowest value to currentLine
4) insert all elements of availableRectangles with left =
currentLine to rectanglesUsedInColumn and delete them
from availableRectangles
5) assign currentLine to previousLine and advance
currentLine to the next value of x in Xs
6) calculate width of column by subtracting currentLine
from previousLine and assign it currentRectangle.width
7) insert the top and bottom of each rectangle in
availableRectangles into Ys
8) the side with the largest value in Ys will be the top of
currentRectangle
9) cycle through Ys from largest to smallest keeping track
of the number of t and b. If numT = numB then the
currentSide is the bottom of currentRectangle so calculate
the height of currentRectangle by subtracting bottom from
top, calculate the area of currentRectangle and add it to
totalArea. If there are more sides in Ys then next side
is top of currentRectangle, reset numbT and numbB, and
keep going until you've evaluated all sides in Ys.
10) when all sides in Ys in a given column have been
evaluated then reset appropriate counters, delete all
rectangles from rectanglesUsedInColumn that have left side
= currentLine
11) assign currentLine to previousLine and advance
currentLine to next value of x in Xs.
12) reset all appropriate variables, if any, to default
values
13) repeat steps 4) through 12) until both availableRectangles
AND rectanglesUsedInColumn are empty (which should be the
same time currentLine equals Xs.end())
14) when all the repeating is done output totalArea which
is the total area of the union of n rectangles

Note that if numT = numB before the end of Ys then there
is a horizontal gap between two polygons and if
rectanglesUsedInColumn becomes empty before
availableRectangles then there is a vertical gap between
two polygons.

The line (plane) sweep is the advancement of currentLine
to each successive element in Xs.