Is there an easy way to detect line segment intersections?

Question

This is a lot more complicated than it might seem at first. What I have is a giant array which consists of more arrays which contain points [in the form of an array "x,y"] like so:

Array (
    [0] => Array (
        [0] => "0,9",
        [1] => "0,0",
        [2] => "9,0",
        [3] => "9,9",
        [4] => "0,9"
        )
    [1] => Array (
        [0] => "1,5",
        [1] => "1,6",
        [2] => "3,6",
        [3] => "3,8",
        [4] => "4,8"
    )
    ... and so on ...
)

So what I need to do is process through all the points and see if any point in an array, say $points[0][1] to $points[0][2], intersects with any other line segment that could exist in the array. All the line segments are consecutive following the order they are in within each of their respective arrays. So in the first array, "0,9" goes to "0,0" and no other point in that array. The last point in an array does not loop back around to the first point in an array. Also, it should not be considered an intersection if a line segment ends at the intersection of another line segment, it actually needs to cross the line segment it intersects.

I was thinking of plotting the segments as I processed them. So like run through the arrays plotting each point on a 'virtual' grid per say and then each array after that would calculate if it intersects another segment which is already plotted, if that makes any sense, but that still seems like it might take a while to calculate if there are a lot of line segments in the array. It seems like what I'd be doing is for each segment in an array, calculate if it intersects any segments previous to it (because theoretically it could intersect a segment in the same array it is in). There has got to be a simpler way to do this, right?

P.S. I couldn't really think of what tags this should fall under other than PHP. If you think of any please feel free to retag it.

Answer 1

Here's a simple method which would be acceptable if the number of points in each list is small:

1. Take the first two line segments in your array and check if they intersect.
2. If not, check the next line segment against the previous line segments
3. Continue till the last point and reiterate for another array (I'm assuming this check you're doing is for each sub array).

This is O(n²) where n is the number of points in all your subarrays --- if n is small - awesome, if not, let us know.

Update: If O(n²) is not good enough ...

Sweep line algorithm for segment intersection - supposedly O(n log (n))

Input: A set of line segments in the plane.

Output: The set of intersection points among the segments in S.

Answer 2

It's fairly easy. You start by computing the equation (slope and Y intercept) of each line. The slope is (Y₁-Y₂)/(X₁-X₂). The Y intercept is Y₁ - slope * X₁. We can then express that line in the form Y=mX+b, where m = the slope, and b = the Y intercept.

Once you've computed those for a pair of lines, you compute the place those lines would cross. This is where the X and Y coordinate of one line equal the X and Y of the other line. In other words, where the equation for one line equals the equation for the other line: m₁X + b₁ = m₂X+b₂. You can then solve that equation by isolating X. For example, given two lines Y = 3x+5 and Y = .5x+2:

3x+5 = .5x+2 // subtract 5 from both sides
3x = .5x - 3 // subtract .5x fro both sides
2.5x = -3    // divide by 2.5
x = -3/2.5   // reduce term
x = -1.2

Now we've established the intersection point of the two lines, but we don't know whether both segments extend far enough to include that point. To do that, we need to check that our X value is between X₁ and X₂ for both line segments.

If you're going to check intersections for a lot of lines, you'll probably want to look up the "plane sweep algorithm" (I won't try to include a link, but Googling for that should give a fair number of hits).