Plane sweep algorithm: How to order the segments after intersection point
<p>I'm trying to implement in C++ code the plane sweep algorithm for segment intersections based on this book: <a href="http://www.cs.uu.nl/geobook/" rel="nofollow">http://www.cs.uu.nl/geobook/</a>. They suggest to implement the status structure of the plane sweep using a balanced binary search tree.</p>

<p>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".</p>

<p>The pseudo-code that is in the book says the following:</p>

<blockquote>
  <ol start="6">
  <li>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.</li>
  <li>(∗ Deleting and re-inserting the segments of C(p) reverses their order. ∗)</li>
  </ol>
</blockquote>

<p>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.</p>

<p>Any idea?</p>

<p>Update: The book is here: <a href="https://books.google.com/books?id=C8zaAWuOIOcC" rel="nofollow">https://books.google.com/books?id=C8zaAWuOIOcC</a> 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</p>

<p>Best,</p>