Algorithms
Line intersection
Test whether two line segments intersect.
Line intersection
Testing whether two line segments intersect is a fundamental operation in line arrangement and collision detection.
The standard method works with orientation tests: if each segment separates the two ends of the other, the segments cross.
Four orientation tests suffice; each is computed in O(1) with the cross product. Special cases need extra checks.
Orientation test
For segments P₁P₂ and P₃P₄ we compute four cross products: d₁ = orient(P₃, P₄, P₁), d₂ = orient(P₃, P₄, P₂), d₃ = orient(P₁, P₂, P₃), d₄ = orient(P₁, P₂, P₄).
If d₁ and d₂ have opposite signs, P₁ and P₂ lie on opposite sides of line P₃P₄. If the same holds for d₃ and d₄, the segments intersect.
The sign check is (d > 0) != (d' > 0).
Exercise segments_intersect function
Write segments_intersect(p1, p2, p3, p4). Return True if the segments intersect, else False. Print True with print(segments_intersect((0,0), (4,4), (0,4), (4,0))).
Show example solution
def segments_intersect(p1, p2, p3, p4):
# Do the two segments intersect?
def orient(a, b, c):
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
d1 = orient(p3, p4, p1)
d2 = orient(p3, p4, p2)
d3 = orient(p1, p2, p3)
d4 = orient(p1, p2, p4)
if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
return True
return False
print(segments_intersect((0,0), (4,4), (0,4), (4,0)))
Test yourself
-
Intersection concepts
- orientation
- Cross product
- opposite sides
- Intersection
- same side
- No intersection
- O(1)
- Constant time
-
When do segments intersect?
d1 = orient(p3, p4, p1)
d2 = orient(p3, p4, p2)
- If d1 and d2 have the same sign
- If d1 and d2 have opposite signs
- If d1 is zero
- If d2 is zero
Show answer
If d1 and d2 have opposite signs — If d1 and d2 have opposite signs, P1 and P2 are on opposite sides.
-
orientation sign
if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > ____)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
Show answer
if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
Next lesson: Closest pair
