3
$\begingroup$

Given a set of 2D polylines such that each polyline:

  • May have self-intersections;
  • May intersect some of (or all) the other polylines,

How do I efficiently find all pairs of intersecting segments and the coordinates of each corresponding intersection point? (We may assume that no three segments intersect in the same point.)

In other words: is it possible to find all intersections more efficiently than using algorithms designed for finding intersections in a set of segments? If it is possible, how? If it isn't, why not?

Illustration

Each polyline is represented as a sequential list/array of points corrensponding to the endpoints of the segments (so if there are N points, there are N-1 segments in a polyline).

Ideas:

  • Using the Bentley-Ottmann sweep line algorithm. The problem is that it takes a set of segments as its input, which means we have to first convert our polylines into a set of segments which seems to eliminate the potentially useful information about the connected endpoints and increases the number of input points. This seems to be a waste of computing resources if there is a way to use the input polyline points directly instead.
  • Sweep line algorithms rely on sorting the input points by one of the coordinates. Knowing that each of the input polylines is already a sequential list of points, perhaps this could help at least partially to eliminate the need for sorting?
$\endgroup$
  • $\begingroup$ I don't see why you've rejected Bentley-Ottmann. It should work correctly and be efficient. You're not really increasing anything, since a polyline with $k$ segments already contains $k+1$ points. If you're going to reject Bentley-Ottman, it seems like you need to be clearer about your requirements -- I don't see any requirement that it violates. $\endgroup$ – D.W. Sep 24 '17 at 2:02
  • $\begingroup$ What about in-place Vahrenhold $\mathcal O(n\log^2n + k)$ or randomized, in-place Chan and Chen in $\mathcal O(n\log n +k)$? $\endgroup$ – Evil Sep 24 '17 at 7:09
  • $\begingroup$ @D.W. What I meant was using Bentley-Ottmann requires to double the number of input points (except for the first and last points of each polyline), since each input segment in Bentley-Ottmann is represented by two points. However, while writing this comment I realized that doubling the points can be substituted with simply reusing them for any pair of adjacent segments... $\endgroup$ – Neat Sep 24 '17 at 8:03
  • $\begingroup$ @Evil Vahrenhold, Chan and Chen, Bentley-Ottmann all use a set of segments as the input. And while a set of polylines can be represented as a set of segments, a set of polylines stores more information about the input segments (i.e., their connections with each other). What I'm wondering is, can this additional information be used to further improve the efficiency of these algorithms or to create a new more efficient algorithm? $\endgroup$ – Neat Sep 24 '17 at 8:06
  • $\begingroup$ @Evil No, my question is what is the efficient algorithm (if there is one) that is designed specifically to address the polyline intersection problem. There is an explanation in my question why I suspect that a generic segment intersection algorithm that omits the fact that we are dealing with polylines may not be the best choice. Modifying an existing segment intersection algorithm is just one option that I think might be possible. $\endgroup$ – Neat Sep 24 '17 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.