Please support our C++ advertiser: Programming Forums
 |
•
•
Join Date: Jun 2008
Posts: 86
Reputation: 
Rep Power: 1
Solved Threads: 5
Junior Poster in Training
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?
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?
•
•
Join Date: Sep 2004
Posts: 6,687
Reputation: 
Rep Power: 32
Solved Threads: 529
>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).
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).
I'm here to prove you wrong.
•
•
Join Date: Jun 2008
Posts: 86
Reputation:
Rep Power: 1
Solved Threads: 5
Junior Poster in Training
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..?
•
•
Join Date: Sep 2004
Posts: 6,687
Reputation:
Rep Power: 32
Solved Threads: 529
>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.
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.
Last edited by Narue : Oct 20th, 2008 at 4:39 pm.
I'm here to prove you wrong.
•
•
Join Date: Jun 2008
Posts: 86
Reputation:
Rep Power: 1
Solved Threads: 5
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:
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!
c++ Syntax (Toggle Plain Text)
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!
Last edited by gregorynoob : Oct 22nd, 2008 at 11:47 am.
•
•
Join Date: Jul 2005
Posts: 1,395
Reputation:
Rep Power: 10
Solved Threads: 196
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.
Last edited by Lerner : Oct 22nd, 2008 at 3:00 pm.
Klatu Barada Nikto
•
•
Join Date: Jun 2008
Posts: 86
Reputation:
Rep Power: 1
Solved Threads: 5
Junior Poster in Training
hmm, union of n rectangles, each defined by only two points, the segments are parallel with the lines of the system (x and y).
•
•
Join Date: Jul 2005
Posts: 1,395
Reputation:
Rep Power: 10
Solved Threads: 196
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.
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.
Klatu Barada Nikto
•
•
Join Date: Jun 2008
Posts: 86
Reputation:
Rep Power: 1
Solved Threads: 5
Junior Poster in Training
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!
•
•
Join Date: Jul 2005
Posts: 1,395
Reputation:
Rep Power: 10
Solved Threads: 196
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.
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.
Klatu Barada Nikto
|
Other Threads in the C++ Forum
- Previous Thread: if and statement
- Next Thread: "missing storage-class or type specifiers" when using static data members
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
Linear Mode
