geometry.segment_intersection

Given two line segments, determine whether they intersect.

This is based on the algorithm described in Introduction to Algorithms (CLRS), Chapter 33.

Reference:

Attributes

points

Classes

Point

A point in 2D space.

Functions

direction(→ float)

Return the cross product of vectors (pivot->query) and (pivot->target).

on_segment(→ bool)

Check whether point, known to be collinear with the segment, lies on it.

segments_intersect(→ bool)

Return True if line segment p1p2 intersects line segment p3p4.

Module Contents

class geometry.segment_intersection.Point

Bases: NamedTuple

A point in 2D space.

>>> Point(0, 0)
Point(x=0, y=0)
>>> Point(1, -3)
Point(x=1, y=-3)
x: float
y: float
geometry.segment_intersection.direction(pivot: Point, target: Point, query: Point) → float

Return the cross product of vectors (pivot->query) and (pivot->target).

The sign of the result encodes the orientation of the ordered triple (pivot, target, query):

  • Negative -> counter-clockwise (left turn)

  • Positive -> clockwise (right turn)

  • Zero -> collinear

>>> direction(Point(0, 0), Point(1, 0), Point(0, 1))
-1
>>> direction(Point(0, 0), Point(0, 1), Point(1, 0))
1
>>> direction(Point(0, 0), Point(1, 1), Point(2, 2))
0
geometry.segment_intersection.on_segment(seg_start: Point, seg_end: Point, point: Point) → bool

Check whether point, known to be collinear with the segment, lies on it.

>>> on_segment(Point(0, 0), Point(4, 4), Point(2, 2))
True
>>> on_segment(Point(0, 0), Point(4, 4), Point(5, 5))
False
>>> on_segment(Point(0, 0), Point(4, 0), Point(2, 0))
True
geometry.segment_intersection.segments_intersect(p1: Point, p2: Point, p3: Point, p4: Point) → bool

Return True if line segment p1p2 intersects line segment p3p4.

Uses the CLRS cross-product / orientation method. Handles both the general case (proper crossing) and degenerate cases where one endpoint lies exactly on the other segment.

>>> segments_intersect(Point(0, 0), Point(2, 2), Point(0, 2), Point(2, 0))
True
>>> segments_intersect(Point(0, 0), Point(2, 2), Point(1, 1), Point(3, 3))
True
>>> segments_intersect(Point(0, 0), Point(1, 0), Point(2, 0), Point(3, 0))
False
>>> segments_intersect(Point(0, 0), Point(1, 1), Point(1, 0), Point(2, 1))
False
>>> segments_intersect(Point(0, 0), Point(1, 1), Point(0, 1), Point(0, 2))
False
>>> segments_intersect(Point(0, 0), Point(1, 0), Point(1, 0), Point(2, 0))
True
geometry.segment_intersection.points