Do These Two Routes Cross?
In short: two segments p1-p2 and p3-p4 cross if p1 and p2 fall on
opposite sides of the line through p3 and p4, AND p3 and p4 fall
on opposite sides of the line through p1 and p2. That's four calls to
last lesson's orientation and one comparison each way. The naive version of
that test has a gap: two segments that run along the same line and
overlap give every orientation a 0, which the naive test reads as "no
crossing" — wrong. Closing that gap needs one more check: when an
orientation comes back 0, look at whether the point actually falls inside
the other segment's span.
A clean X crossing
Two Meridian delivery routes are proposed, and the dispatcher wants to know if they cross before either driver sets off:
route_a's endpoints land on opposite sides of route_b's line, and
route_b's endpoints land on opposite sides of route_a's line too — both
conditions hold, so d1 != d2 and d3 != d4 is already True and the
function returns on the first check, with no collinear case needed at all.
The case the naive test gets wrong
Here is the four-orientation test without the collinear fallback, on two routes that both run along the same east-west line, overlapping in the middle:
def orientation(a, b, c):
cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
if cross > 0:
return 1
if cross < 0:
return -1
return 0
def naive_crossing(p1, p2, p3, p4):
d1 = orientation(p3, p4, p1)
d2 = orientation(p3, p4, p2)
d3 = orientation(p1, p2, p3)
d4 = orientation(p1, p2, p4)
return d1 != d2 and d3 != d4
print(naive_crossing((0, 0), (4, 0), (2, 0), (6, 0)))The two routes genuinely overlap for two whole kilometres, and the naive
test waves it through. on_segment closes this gap: whenever an orientation
comes back 0, it means that point is collinear with the other segment, and
on_segment then asks the only remaining question — does it actually fall
within that segment's span, or off one end of it?
Both lines print False, but the first pair genuinely overlaps. Add the missing collinear-overlap checks.
Quick practice
def orientation(a, b, c):
cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
if cross > 0:
return 1
if cross < 0:
return -1
return 0
p1, p2, p3, p4 = (0, 0), (4, 0), (0, 2), (4, 2)
print(orientation(p3, p4, p1) != orientation(p3, p4, p2))def on_segment(p, a, b):
return (min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and
min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))
print(on_segment((4, 4), (0, 0), (4, 4)))🎯 Your turn
Build segments_intersect(p1, p2, p3, p4): return True if the two
segments share any point — a proper crossing, a touching endpoint, or a
collinear overlap.
segments_intersect((0,0), (4,4), (0,4), (4,0))→Truesegments_intersect((0,0), (4,0), (2,0), (6,0))→Truesegments_intersect((0,0), (4,0), (5,0), (8,0))→False
Hint: compute d1 = orientation(p3, p4, p1), d2 = orientation(p3, p4, p2), d3 = orientation(p1, p2, p3), d4 = orientation(p1, p2, p4). If
d1 != d2 and d3 != d4, return True. Otherwise, check on_segment for
each d that came back 0.
Press ▶ Run, try the Live App chips, then ✓ Check.