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)]
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))?
8
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
Lets take a slightly different set, one that has an intersection in it.
[3, 7, 13, 4, 11]
This generates the set of lines of:
{3,7} {7,13}
{7,13} {13,4}
{13,4} {4,11}
{4,11} {11,3}
Lets assume a pre-existing function boolean intersect(x1, y1, x2, y2) (the math for this can be found on wikipedia, or various stack overflow questions – note that you want line segment intersection rather than a generic line intersection).
We are also going to take the set of lines and sort them by the left most X value and then rightmost X value ({4,11} {11,3} sorts before {4,11}, {13,4}).
{3,7} {7,13}
{4,11} {11,3}
{4,11} {13,4}
{7,13} {13,4}
Now, adding line by line to a queue in sorted order.
Each time a line is to be added to the queue, check for intersections against all lines currently in the queue.
queue: empty
test: none
add: {3,7} {7,13}
----
queue: (1) {3,7} {7,13}
test: 1: intersects
add: {4,11} {11,3}
---
queue: (1) {3,7} {7,13}
(2) {4,11} {11,3}
test: 1: intersects
2: does not intersect
add: {4,11} {13,4}
Furthermore, prior to running the tests, if the leftmost X value is equal to or greater than the rightmost X value of the first element in the queue, remove that element from the queue.
queue: (1) {3,7} {7,13}
(2) {4,11} {11,3}
(3) {4,11} {13,4}
{7,13} >= {7,13} - drop #1
queue: (2) {4,11} {11,3}
(3) {4,11} {13,4}
test: 2: does not intersect
3: does not intersect
add: {7,13} {13,4}
This is implementing a sweep line algorithm that is only concerning itself with the line segments that could possibly intersect with the list of line segments. Note the section on Applications that mentions Shamos and Hoey with an algorithm for identifying line segment intersections on a plane (exactly this problem). The full pseudo code is described at Intersections of a Set of Segments. You can see code for this on CodeReview.SE – Is this implementation of Shamos-Hoey Algorithm OK? and Stack Overflow – Implementing Hoey Shamos algorithm with C#. A handout on this from Tufts University
Line Segment Intersection Using a Sweep Line Algorithm goes into this and explains the various complexity and some further applications.
Note that the structures here can be simplified by using your own sorted list. The queue is a useful visualization, but the sorted list itself can be used by maintaining two indexes which identify the window of line segments to test. Instead of adding an element to the queue, the high end of the frame is incremented. Instead of removing an element from the queue, the low end of the frame is incremented.
1
Create a grid, map all the lines to the that grid. For each cell that contains more than one line, validate intersection.
It have O(CN) efficiency, where C is depended by the size of the grid.
2
