How to check if two line segments intersect?
Home -> Solved problems -> How to check if two line segments intersect?
Solution
Determining whether two line segments intersect is a fundamental problem in computational geometry.
This is not just about two infinite lines crossing — we need to verify if that intersection point actually lies within the finite bounds of both segments.
In the solution below, we express each segment parametrically, set up a system of equations, compute the determinant, and check parametric values to decide if, where and how the segments intersect.
If \(M\) is a point of the line segment \(AB\)
\[\begin{aligned}
\overrightarrow{O M} & =\overrightarrow{O A}+\overrightarrow{A M} \quad, \overrightarrow{A M}=t_1 \overrightarrow{A B}, t_1 \in[0,1] \\\\
& =a_1 \vec{i}+b_1 \vec{j}+t_1\left(\left(c_1-a_1\right) \vec{i}+\left(d_1-b_1\right) \vec{j}\right) \\\\
& =a_1 \vec{i}+t_1\left(c_1-a_1\right) \vec{i}+b_1 \vec{j}+t_1\left(d_1-b_1\right) \vec{j} \\\\
& =\left(a_1+t_1\left(c_1-a_1\right)\right) \vec{i}+\left(b_1+t_1\left(d_1-b_1\right)\right) \vec{j}
\end{aligned}\]
\[\begin{aligned}
& \overrightarrow{O M}=x \vec{i}+y \vec{j} \\\\
& x=a_1+t_1\left(c_1-a_1\right) \\\\
& y=b_1+t_1\left(d_1-b_1\right)
\end{aligned}\]
If \(M\) is a point of the line segment \(CD\)
\[\begin{aligned}
& x=a_2+t_2\left(c_2-a_2\right) \\\\
& y=b_2+t_2\left(d_2-b_2\right) \\\\
& t_2 \in[0,1]
\end{aligned}\]
A point \(M(x,y)\) of the plane is common to the line segment \(AB\) and the line segment \(CD\) if and only if, its coordinates \(x\) and \(y\) are solutions of the parametric equations of the two segments:
\[\begin{gathered}
\left\{\begin{array}{c}
x=a_1+t_1 \left(c_1-a_1\right) \\\\
y=b_1+t_1 \left(d_1-b_1\right) \\\\
0\leq t_1\leq1
\end{array}\right. \\\\
\left\{\begin{array}{c}
x=a_2+t_2 \left(c_2-a_2\right) \\\\
y=b_2+t_2 \left(d_2-b_2\right) \\\\
0\leq t_2\leq1
\end{array}\right.
\end{gathered}\]
The line segments \(AB\) and \(CD\) intersect if the following system has at least one solution \((t_1 ,t_2)\), \(0\leq t_1\leq 1\) and \(0\leq t_2\leq 1\):
\[\left\{\begin{array}{l}
a_1+t_1 \left(c_1-a_1\right)=a_2+t_2 \left(c_2-a_2\right) \\
b_1+t_1 \left(d_1-b_1\right)=b_2+t_2 \left(d_2-b_2\right)
\end{array}\right.\]
This system can be rewritten as follows:
\[\left\{\begin{array}{l}
t_1 \left(c_1-a_1\right)-t_2 \left(c_2-a_2\right)=a_2-a_1 \\
t_1 \left(d_1-b_1\right)-t_2 \left(d_2-b_2\right)=b_2-b_1
\end{array}\right.\]
let’s find the determinant
\[\operatorname{det}\left(\left[\begin{array}{ll}
c_1-a_1&-\left(c_2-a_2\right) \\
d_1-b_1&-\left(d_2-b_2\right)
\end{array}\right]\right)=-\left(c_1-a_1\right) \left(d_2-b_2\right)+\left(c_2-a_2\right) \left(d_1-b_1\right)\]
There are several possible cases:
If the determinant is not equal to \(0\) therefore we get a single solution \(t_1\) and \(t_2\). If these are between \(0\) and \(1\) then the two line segments have a single point of intersection.
\[\begin{aligned}
& \text { If } \operatorname{det}\left(\begin{array}{cc}
c_1-a_1 & a_2-c_2 \\
d_1-b_1 & b_2-d_2
\end{array}\right) \neq 0 \\\\
& t_1=\frac{\operatorname{det}\left(\begin{array}{ll}
a_2-a_1 & a_2-c_2 \\
b_2-b_1 & b_2-d_2
\end{array}\right)}{\operatorname{det}\left(\begin{array}{ll}
c_1-a_1 & a_2-c_2 \\
d_1-b_1 & b_2-d_2
\end{array}\right)}\\\\
& t_2=\frac{\operatorname{det}\left(\begin{array}{ll}
c_1-a_1 & a_2-a_1 \\
d_1-b_1 & b_2-b_1
\end{array}\right)}{\operatorname{det}\left(\begin{array}{ll}
c_1-a_1 & a_2-c_2 \\
d_1-b_1 & b_2-d_2
\end{array}\right)}
\end{aligned}\]
\[\begin{aligned}
&\text { If }\\\\
&0 \leqslant t_1 \leqslant 1\\\\&and\\\\ &0 \leqslant t_2 \leqslant 1 \\\\&and\\\\ &c_1 \neq a_1\\\\&and\\\\ &c_2 \neq a_2\\\\&then\\\\
&x=a_1+t_1(c_1−a_1) \\\\
&y=b_1+t_1(d_1−b_1) \\\\
\end{aligned}
\]
– The determinant is not equal to \(0\) but the solutions \(t_1\) and \(t_2\) are not between \(0\) and \(1\) so the two segments do not cross.
In fact, in this case, the lines that extend the line segments have a point of intersection but does not belong to the two line segments.
– The determinant is equal to \(0\). In this case there are either \(0\) solutions (parallel line segments or belong to the same line but have no intersection), or there are infinities of solutions: the two segments “overlap” (their intersection is a line segment).
By expressing both segments in a parametric form and solving for parameters \(t_1\) et \(t_2\), we can determine whether their lines intersect — and crucially, whether that intersection lies within each segment.
The use of the determinant provides a clean way to check for a unique intersection, while edge cases (parallel segments or overlapping) can also be handled.
This method is robust and widely used in geometry algorithms, computer graphics, and collision detection.
\[a1=100*rand(1,1);
b1=100*rand(1,1);
c1=100*rand(1,1);
d1=100*rand(1,1);
a2=100*rand(1,1);
b2=100*rand(1,1);
c2=10*rand(1,1);
d2=10*rand(1,1);
A=[c1-a1 d1-b1; a2-c2 b2-d2];
if det(A)~=0
t_1=det([a2-a1 b2-b1;a2-c2 b2-d2])/det([c1-a1 d1-b1;a2-c2 b2-d2]);
t_2=det([c1-a1 d1-b1;a2-a1 b2-b1])/det([c1-a1 d1-b1;a2-c2 b2-d2]);
if (t_1>=0 && t_1<=1) && (t_2>=0 && t_2<=1)
if (c1==a1 && c2~=a2)
cond='YES intersection';
x=a1;
elseif (c1~=a1 && c2==a2)
cond='YES intersection';
x=a2;
elseif (c1~=a1 && c2~=a2)
cond='YES intersection';
x=a1+t_1*(c1-a1);
y=b1+t_1*(d1-b1);
else
cond='NO intersection';
x='NO';
end
else
cond='NO intersection';
x='NO';
end
elseif c1==a1 && c2==a2
if a2==a1
if abs(b1-d1)+abs(b2-d2)==max(max(b1,d1),max(b2,d2))-min(min(b1,d1),min(b2,d2))
cond='YES intersection';
x=a2;
vtri=[b1 d1 b2 d2];
vtri=unique(vtri);
y=vtri(2);
elseif abs(b1-d1)+abs(b2-d2)>max(max(b1,d1),max(b2,d2))-min(min(b1,d1),min(b2,d2))
cond=’intersection is not a point’;
x=’segment’;
else
cond=’NO intersection’;
x=’NO’;
end
else
cond=’NO intersection parallel’;
x=’NO’;
end
elseif d1==b1 && d2==b2
if b2==b1
if abs(a1-c1)+abs(a2-c2)==max(max(a1,c1),max(a2,c2))-min(min(a1,c1),min(a2,c2))
cond=’YES intersection’;
y=b2;
vtri=[a1 c1 a2 c2];
vtri=unique(vtri);
x=vtri(2);
elseif abs(a1-c1)+abs(a2-c2)>max(max(a1,c1),max(a2,c2))-min(min(a1,c1),min(a2,c2))
cond=’intersection is not a point’;
x=’segment’;
else
cond=’NO intersection’;
x=’NO’;
end
else
cond=’NO intersection parallel segments’;
x=’NO’;
end
else
cond=’NO intersection’;
x=’NO’;
end
\]
Home -> Solved problems -> How to check if two line segments intersect?
Every problem you tackle makes you smarter.
↓ Scroll down for more maths problems↓
Find the equation of the curve formed by a cable suspended between two points at the same height
Prove that the function \(f(x)=\frac{x^{3}+2 x^{2}+3 x+4}{x}
\) has a curvilinear asymptote \(y=x^{2}+2 x+3\)
Why does the number \(98\) disappear when writing the decimal expansion of \(\frac{1}{9801}\) ?
if we draw an infinite number of circles packed in a square using the method shown below, will the sum of circles areas approach the square's area?
Is it possible to solve for \(x\) so that \(ln(x)\), \(ln(2x)\), and \(ln(3x)\) form a right triangle?
