0

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))?

8
  • How many line segments are we talking about? Assuming you care about all of the intersections, you're going to have to check every two-line combination. But it's pretty simple math; unless you've got millions of them, performance shouldn't be an issue. Nov 1, 2013 at 19:24
  • I'd have to dig into it more (math/geometry isn't my strong suit) - anything I write will be strongly influenced by line segment intersection from wikipedia which appears to be the essence of this problem.
    – user40980
    Nov 1, 2013 at 19:35
  • Digging into the Bentley-Ottmann algorithm a little bit, it appears that even an optimal approach is really quite close to O(n^2) -- its O((n + o(n^2/log n)) * log n)
    – user40980
    Nov 1, 2013 at 19:43
  • @MichaelT I just added my own solution that seems to be better than that, but I am not done optimizing, I hope a better solutions will be found. Nov 1, 2013 at 20:19
  • Are you asking for intersections or endpoint connections (a path)? Your sample shows connections which is a subset of the possible intersections of 4 line segments.
    – cdkMoose
    Nov 1, 2013 at 20:36

3 Answers 3

5

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

3

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
  • Look at the answer that I awarded it is the same idea as yours, only you have few mistakes. "check for intersections against all lines currently in the queue", no need to check them all, this is why we got the sort. But you did a great work here so I am upvoting. P.S how do you do the drawing? Nov 2, 2013 at 6:51
0

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
  • As far as I remember from university: a linear factor C is not taken into consideration when talking about efficiency in O(N). Therefore you have N which stands for all the linear part.
    – Andy
    Nov 2, 2013 at 9:29
  • @Andy In worst case C can be equal to N, so you can't ignore it. Nov 2, 2013 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.