3

I'm trying to implement in C++ code the plane sweep algorithm for segment intersections based on this book: http://www.cs.uu.nl/geobook/. They suggest to implement the status structure of the plane sweep using a balanced binary search tree.

I'm using the std::set structure to implement the status structure but I'm having problems to reorder the segments that contain the point "p" and their upper endpoint is the point "p". They have the same coordinate point which means that I cannot insert them in std::set because it doesn't allow repetitive values... I tried to insert them with their lower endpoint but then, they are going to lose the order in which they intersect by a sweep line just below "p".

The pseudo-code that is in the book says the following:

  1. Insert the segments in U(p) ∪C(p) into Tao. The order of the segments in Tao should correspond to the order in which they are intersected by a sweep line just below p. If there is a horizontal segment, it comes last among all segments containing p.
  2. (∗ Deleting and re-inserting the segments of C(p) reverses their order. ∗)

I don't know how they are going to reverse their order.. As I insert segments in the status structure, I'm sorting them by their x upper endpoint coordinate. I don't know how to swap their order after an intersection.

Any idea?

Update: The book is here: https://books.google.com/books?id=C8zaAWuOIOcC but there a some pages that don't appear. It is on chapter 2, pages 24, 25 and 26. Hope it helps to give some context

Best,

andrestoga
  • 49
  • 7

3 Answers3

2

When using std::set the appearance of two or more items on a common y-value should not be a problem, assuming you use a fitting comparator for the std::set. I would suggest, besides the y-value, comparing and sorting by slope. (Example of a comparator for a std::set)

I would suggest not to use std::set for it but something like std::vector. Using std::vector enables you to swap (std::swap) the references to certain line segments and also insert/remove in O(log n) time if a line segment starts/ends, where n is the number of line segments. The idea is that you maintain the correct order of the status yourself throughout the line sweep by swapping the line segments that correspond to an intersection, only the event queue is a priority queue. (Removed due to the comment of @Sneftel, thanks for the insight.)

Regarding your general approach on the sweep line algorithm: The status (sweep line status) does represent the order of the line segments on a specific (current) time in your line sweep. For the sweep line status, in my understanding, one should use a balanced binary tree (as mentioned by @Sneftel). Then, you can maintain the correct order of the status yourself throughout the line sweep by swapping the line segments that correspond to an intersection, only the event queue must be some sort of priority queue.

Community
  • 1
  • 1
gue
  • 1,868
  • 1
  • 16
  • 21
  • 2
    The problem with `std::vector` is that inserting/deleting elements in the middle is `O(n)` rather than `O(log(n))`. That's why the algorithm specifies a balanced binary tree: it needs efficient search *and* efficient middle insertion/deletion. Still, for reasonable input sizes and types, linear-time inserts/delets are unlikely to be a major performance problem in a sweepline implementation. – Sneftel Oct 14 '16 at 15:41
  • To implement plane sweep, you create a list of "seg start" and "seg stop" events, in x. You then sort them. Then you create a dynamic ordered list, with the major sort on y, and insert segments into it. So even if there are large numbers of overlaps in y, the algorithm is still reasonably efficient. The question is what happens if two segments share a y. – Malcolm McLean Oct 15 '16 at 07:04
  • @Sneftel, true, the std::vector does not work in this scenario where additional line segments start at any time. – gue Oct 17 '16 at 06:19
  • It works if you first sort the segments that start at any time by their angles and then insert them in order. – andrestoga Oct 19 '16 at 06:09
-2

Write the comparison function so the major sort is on y, the minor on x. Then you can insert segments with duplicate y values, as long as the x is different. (If you've got two identical segments you need to handle specially for intersection testing anyway).

Malcolm McLean
  • 6,258
  • 1
  • 17
  • 18
  • Yeah, the problem is when you have multiple segments with the same upper point(same x and y coordinate), how do you sort them in the status structure? – andrestoga Oct 15 '16 at 21:09
-2

The sorting predicate for the std::set used as the plane sweep status data structure must work as follows:

  1. It must (dynamically) compute the coordinate of the intersection of a given segment with the sweep-line for the current position of the sweep-line.

  2. In case of a tie (when two segments appear to intersect the sweep line at the same coordinate) it must also compare the angles of the two segments - this will allow to find out the order of the segments in the status for future positions of the sweep line.

Note that the requirement 1. above means that the predicate object must hold a reference to the sweep-line position variable, so that it can compare segments correctly as the sweep-line advances. The sweep-line position cannot be stored in the predicate itself because then you will be unable to update it from your algorithm (std::set doesn't provide access to its predicate by reference).

EDIT

Note that the responsibility of maintaining correct order of segments in the set (i.e. swapping them as required) is still with the algorithm - an std::set with such a predicate will not automatically reorder its elements.

Leon
  • 31,443
  • 4
  • 72
  • 97
  • 1
    This isn't a good approach. std::set requires a comparator which does not change its output over time, and violating this *will* lead to bugs. Just because `std::set` is implemented *using* a balanced binary tree doesn't mean it can be used as a primitive balanced binary tree; the way in which the sweepline algorithm uses it requires manual swaps rather than an ordering function, and `std::set` isn't set up for that. – Sneftel Oct 14 '16 at 15:39
  • @Sneftel I never meant that `std:set` will automatically maintain the correct order of segments in the status. You still have to swap the segments while handling intersection events. – Leon Oct 14 '16 at 15:45
  • 1
    It's not just about maintaining the correct order. `std::set` does not expect its comparison function to change. If it does, your program may well crash. – Sneftel Oct 14 '16 at 15:47
  • @Sneftel Why would a program crash if the change in the comparison function doesn't affect the current order of elements in the set? – Leon Oct 14 '16 at 15:49
  • Because it does affect the order (otheriwse there'd be no reason to have a comparison). There's no way to "swap elements" in a `std::set`. – Sneftel Oct 14 '16 at 15:54
  • @Sneftel That part is the responsibility of the algorithm - the concerned algorithm breaks the segments by their point of intersection as soon as the intersection is detected, removes the old sub-segments when the point of intersection is reached, and inserts the new sub-segments (with the correct order). – Leon Oct 14 '16 at 15:57
  • @Sneftel Though you are right - when I implemented a variation of this algorithm years ago, I had to use `const_cast` to swap adjacent elements. Though this is kind of dirty, it worked in practice. – Leon Oct 14 '16 at 16:02
  • It happened to work in your particular case. It's still a violation of the standard. Though I suppose if you removed all the intersecting segments, backdoor-changed the compare, then reinserted the intersecting segments, it would be compliant (though complicated to implement, and slower than the normal algorithm). – Sneftel Oct 14 '16 at 16:04
  • Not only you need to swap segments but you also need to insert new segments that share the same y coordinate. As you said you ordered them by their angles but then you have to insert them in the status structure, but then, how are you gonna sort them in std::set? by their angles? It is not possible... – andrestoga Oct 19 '16 at 05:52
  • @andrestoga Ordering by angles comes after ordering by the x coordinate of intersection with the sweep line (i.e. major sort by the x-coordinate of intersection with the sweep-line, minor sort by the slope of the segment). – Leon Oct 19 '16 at 06:27
  • @Leon Oh, I got it! so, then you just need to delete them and reinsert them with their minor sort, right? so, you don't have to use `const_cast` to swap them. – andrestoga Oct 20 '16 at 06:10
  • @andrestoga Yes. Note, however, that this must be done correctly so that you don't face problems at intersection points where more than 2 segments intersect. At such an event point you must remove from the status all the involved segments and only after that reinsert them into the status. – Leon Oct 20 '16 at 06:56