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))?
Asked By : Caio Oliveira
Answered By : Yuval Filmus
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–Ottman that doesn't require general position. The idea is to do the perturbation by some infinitesimal amount, and record the results formally (e.g. $1$ goes to $1+\epsilon$, where $\epsilon$ is an infinitesimal). When running the algorithm, you will need to compare values which involve these infinitesimals, which you can do formally (for example, $1+\epsilon < 1 + 2\epsilon$).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23886
0 comments:
Post a Comment
Let us know your responses and feedback