Find all line intersections with tolerance (preferably a pre existing implementation)

Question

The Bentley-Ottmann algorithm can be used to scan for all intersections in a set of line segments in n log n time. But is there a version out there that can do this with variable precision? i.e. where lines are considered to intersect if they come closer than a certain distance?

Are you talking about lines or line segments? – sloriot Sep 18 '12 at 06:23 — sloriot, Sep 18 '12 at 06:23

score 1 · Answer 1 · edited May 23 '17 at 11:53

1

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

AFAIK, there's nothing special about that. You simply adjust the intersects(...) function of the LineSegment class/object. Instead of returning a boolean (or other) value indicating a "real" intersection, you return true if the smallest distance between the two segments is below your predefined threshold, indicating your definition of an intersection. No change in the algorithm.

¹ See:

edited May 23 '17 at 11:53

Community

1
1

answered Sep 18 '12 at 08:15

Bart Kiers

166,582
36
299
288

That's fine for two line segments but doesn't solve for all intersecting pairs in `n log n` time as Bentley-Ottmann does. (Sorry I should have said as much in the original post - will fix). – Sideshow Bob Sep 18 '12 at 10:24

score 1 · Answer 2 · answered Sep 19 '12 at 09:00

If 2 segments do not intersect, than minimal distance between them is on at least one segment end point. Because of that, in your case, it is enough to test if pair of segments intersect or some segment end point is near other segment.

First test is standard in Bentley-Ottmann algorithm, second part can be done in adding and removing segment from sweep line. When segment is added to SL (left endpoint) than it is enough to test segments on SL that are near left endpoint and segments that ended on given distance from SL to left. Similar when segment is removed from SL.

I think, because of symmetry, that is enough to test only one side, e.g. adding of segment to SL.

Since end points are sorted, this search should be fast. If there is some guaranty that segments are not dense regarding tolerance, than this change doesn't change n log n running time of original algorithm.

Find all line intersections with tolerance (preferably a pre existing implementation)

2 Answers2