I have a collection of lines:

List<Line> _lines;

Each has the properties: X1, X2, Y1, Y2

How can I determine whether any given line in the list (Line[n]) intercepts, at any point, any other line in the list?


1 Answer 1


There is a sweeping algorith for this with logarithmic complexity, precisely (n+k)log(n).
The algorithm is described as follows:

  • initialize priority queue = add every endpoint of your lines with priority of x coordinate
  • while queue is not empty, pop one point, depending on type:
    1. If it is line segment start point, add to y-sorted-collection and test this with line segments directly below and above for intersection, if there is intersection, add it to the queue as future event.
    2. If it is line segment end point, test intersection between segments directly below and above, if there is an intersection, add it to the queue. Lastly remove this from y-sorted-collection.
    3. If it is previously added crossing(see above), swap the points below and above and test them for intersection with their new points below and above respectively. Remove crossing from y-sorted-collection.

it is quite simple and easy algorithm, but tricky to describe... Should you have difficulties with understanding, I am sure you can with tons of alternative resources describing this algorithm and probably even implementing it.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .