12.2. Line-segment Intersections

A line-segment can be described by its two endpoints, \(p_1\) and \(p_2\), and denoted by \(p_1p_2\). Note that the set of points on this segments can be expressed as \(p_1 + s(p_2-p_1)\) for a parameter value \(s\in[0,1]\).

To determine if \(p_1p_2\) intersects another line-segment \(q_1q_2\), we express the points on both segments in this way (with different parameters \(s,t\)), and set the points equal. This leads to the problem: Find \(s,t\in[0,1]\) s.t.

\[ p_1 + s(p_2 - p_1) = q_1 + t(q_2 - q_1) \]

which can be reorganized as a 2-by-2 linear system of equations for \(s,t\):

\[\begin{split} \begin{pmatrix} p_2 - p_1 & q_1 - q_2 \end{pmatrix} \begin{pmatrix} s \\ t \end{pmatrix} = \begin{pmatrix} q_1 - p_1 \end{pmatrix} \end{split}\]

If the line-segments are parallel, the matrix is singular. For simplicity we simply say that they do not intersect in this case, but a better implementation would determine if they actually overlap.

We implement the method in the function below, where we have also included a tolerance \(\delta\). This is useful to handle the case when the intersection is close to one of the endpoints, then \(\delta>0\) would allow for a small positive overlap and \(\delta<0\) a small negative overlap.

using LinearAlgebra
using PyPlot
function linesegment_intersect(p1, p2, q1, q2, δ)
    A = [p2-p1 q1-q2]
    b = q1-p1
    if rank(A) == 2
        st = A \ b
        if all(-δ .≤ st .≤ 1 + δ)
            pintersect = p1 + st[1] * (p2 - p1)
            return true, pintersect
        else
            return false, nothing
        end
    else
        # Warning: parallel lines, should check if they actually overlap
        return false, nothing
    end
end

linesegment_intersect (generic function with 1 method)

# Example: n random lines, find and plot all intersections
n = 10
lines = [ [rand(2), rand(2)] for i = 1:n ]

# Plot all lines
for line in lines
    plot([line[1][1], line[2][1]], [line[1][2], line[2][2]])
end

# Find all intersections - note that we only consider j>i to avoid checking
# the same 2 line-segments twice
for i = 1:n
    for j = i+1:n
        isect, pq = linesegment_intersect(lines[i][1], lines[i][2], lines[j][1], lines[j][2], 0)
        if isect
            plot(pq[1], pq[2], "o")
        end
    end
end

axis("equal"); grid(true);