Line intersection
- Algorithms course
- Expert
- Lesson 21/41
- 4 min
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).
Practice 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))).
Starter code
def segments_intersect(p1, p2, p3, p4):
# Do the two segments intersect?Sample 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)))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Intersection concepts
| Term | Meaning |
|---|---|
orientation |
Cross product |
opposite sides |
Intersection |
same side |
No intersection |
O(1) |
Constant time |
2 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 Correct answer
- If d1 is zero
- If d2 is zero
Explanation: If d1 and d2 have opposite signs, P1 and P2 are on opposite sides.
3 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)):if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):Explanation: d2 > 0 tests the opposite sign.