Python/geometry/segment_intersection.py at d1cbb018835dd89209403e034b431ac4dfc1e446 · TheAlgorithms/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
"""
Given two line segments, determine whether they intersect.

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

Reference:
    - https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
    - https://en.wikipedia.org/wiki/Orientation_(geometry)
"""

from __future__ import annotations

from typing import NamedTuple


class Point(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


def 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
    """
    return (query.x - pivot.x) * (target.y - pivot.y) - (target.x - pivot.x) * (
        query.y - pivot.y
    )


def 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
    """
    return min(seg_start.x, seg_end.x) <= point.x <= max(
        seg_start.x, seg_end.x
    ) and min(seg_start.y, seg_end.y) <= point.y <= max(seg_start.y, seg_end.y)


def 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
    """
    d1 = direction(p3, p4, p1)
    d2 = direction(p3, p4, p2)
    d3 = direction(p1, p2, p3)
    d4 = direction(p1, p2, p4)

    if ((d1 < 0 < d2) or (d2 < 0 < d1)) and ((d3 < 0 < d4) or (d4 < 0 < d3)):
        return True

    if d1 == 0 and on_segment(p3, p4, p1):
        return True
    if d2 == 0 and on_segment(p3, p4, p2):
        return True
    if d3 == 0 and on_segment(p1, p2, p3):
        return True
    return d4 == 0 and on_segment(p1, p2, p4)


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    print("Enter four points as 'x y' pairs (one per line):")
    points = [Point(*map(float, input().split())) for _ in range(4)]
    p1, p2, p3, p4 = points
    result = segments_intersect(p1, p2, p3, p4)
    print(1 if result else 0)