CODEWITHSUNDEEP
c++algorithmcomputational-geometry
andrestoga
andrestoga

Reputation: 67

Plane sweep algorithm: How to order the segments after intersection point

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,

Upvotes: 3

Views: 2161

Answers (3)

gue
gue

Reputation: 2028

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.

Upvotes: 2

Leon
Leon

Reputation: 32494

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.

Upvotes: -2

Malcolm McLean
Malcolm McLean

Reputation: 6404

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).

Upvotes: -2

Related Questions