Find all intersections of lines with a tolerance (preferably, to the existing implementation)

Question

The Bentley-Ottman algorithm can be used to scan all intersections in a set of line segments at n log n time. But is there a version that can do this with variable accuracy? that is, when lines are considered intersecting if they are approaching a certain distance?

Answer 1

Assuming you're talking about line segments in 2D.

AFAIK, this is nothing special. You simply configure the intersects(...) function for the LineSegment class / object. Instead of returning a boolean value (or another) indicating a “real” intersection, you return true if the minimum distance between two segments is below your predetermined threshold, indicating your definition of intersection. No change in the algorithm.

---

¹ See:

• The shortest distance between two line segments
• Connect two line segments

Answer 2

If two segments do not intersect, the minimum distance between them is at least one endpoint of the segment. Because of this, in your case it is enough to check if a pair of segments intersect or if any endpoint of a segment is next to another segment.

The first test is standard in the Bentley-Ottman algorithm, the second part can be performed by adding and removing a segment from the scan line. When a segment is added to SL (left endpoint), than enough to test segments on SL that are near the left endpoint and segments that end at a given distance from SL to left. Similarly, when a segment is removed from SL.

I think that because of the symmetry, this is enough to check only one side, for example. Adding a segment to SL.

Since endpoints are sorted, this search should be quick. If there is a certain guarantee that the segments are not dense relative to the tolerance, then this change does not change the time n log n original algorithm.