Algorithms – Finding All Line Segment Intersections

algorithmsarraysearch

I have a collection of lines segments, represented by an array.

Ex: [3,7,13,6,9] is 4 line segments: [(3,7)(7,13)] , [(7,13)(13,6)] , [(13,6)(6,9)] , ([6,9)(9,3)]

enter image description here

I want to find all the lines segments intersections(not including the common point), is there any better way of doing it rather than brute force(Checking all the options with O(N^2))?

Best Answer

sort the lines by the X of the leftmost point

then for each line look at the next lines and check each of them until the x of their leftmost point is further right than the current line's rightmost point

this will be n*log n best case (for the sorting) but will degenerate into the naive n^2 in bad data sets

Related Topic