I\'m looking for a sweep line algorithm for finding all intersections in a set o

Question

I'm looking for a sweep line algorithm for finding all intersections in a set of line segments that doesn't necessarily respects the general position constraint of Bentley-Ottman's algorithm (taken from Wikipedia):

No two line segment endpoints or crossings have the same x-coordinate
No line segment endpoint lies upon another line segment
No three line segments intersect at a single point.

Is there any sweep line solution to this problem? If not, is there any other algorithm that solves this problem in O((n+k)log(n))?

Explanation / Answer

Usually these algorithms can be adapted to the general case, but the details are messy and hard to get right. Another option is perturbation:

Move each line segment by some small amount in all directions.
Extend the segments slightly on both ends.

If you choose your parameters carefully (i.e., small enough), you are likely to have all the same intersections, but you will be in general position with probability 1. How small is small depends on your input, and this is a limitation of this approach, but in practice you can probably heuristically choose a small enough perturbation.

Implementing this using "virtual infinitesimals", you can come up with a version of Bentley

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.