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?

gregorynoob 2 Junior Poster in Training

Narue 5,707 Bad Cop Team Colleague

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 2 Junior Poster in Training

Narue 5,707 Bad Cop Team Colleague

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 2 Junior Poster in Training

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 582 Nearly a Posting Maven

gregorynoob 2 Junior Poster in Training

Lerner 582 Nearly a Posting Maven

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 2 Junior Poster in Training

Lerner 582 Nearly a Posting Maven

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 582 Nearly a Posting Maven

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 582 Nearly a Posting Maven

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.