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,
(p1: Point, p2: Point, p3: Point, p4: Point)
| 64 | |
| 65 | |
| 66 | def segments_intersect(p1: Point, p2: Point, p3: Point, p4: Point) -> bool: |
| 67 | """Return True if line segment p1p2 intersects line segment p3p4. |
| 68 | |
| 69 | Uses the CLRS cross-product / orientation method. Handles both the |
| 70 | general case (proper crossing) and degenerate cases where one endpoint |
| 71 | lies exactly on the other segment. |
| 72 | |
| 73 | >>> segments_intersect(Point(0, 0), Point(2, 2), Point(0, 2), Point(2, 0)) |
| 74 | True |
| 75 | >>> segments_intersect(Point(0, 0), Point(2, 2), Point(1, 1), Point(3, 3)) |
| 76 | True |
| 77 | >>> segments_intersect(Point(0, 0), Point(1, 0), Point(2, 0), Point(3, 0)) |
| 78 | False |
| 79 | >>> segments_intersect(Point(0, 0), Point(1, 1), Point(1, 0), Point(2, 1)) |
| 80 | False |
| 81 | >>> segments_intersect(Point(0, 0), Point(1, 1), Point(0, 1), Point(0, 2)) |
| 82 | False |
| 83 | >>> segments_intersect(Point(0, 0), Point(1, 0), Point(1, 0), Point(2, 0)) |
| 84 | True |
| 85 | """ |
| 86 | d1 = direction(p3, p4, p1) |
| 87 | d2 = direction(p3, p4, p2) |
| 88 | d3 = direction(p1, p2, p3) |
| 89 | d4 = direction(p1, p2, p4) |
| 90 | |
| 91 | if ((d1 < 0 < d2) or (d2 < 0 < d1)) and ((d3 < 0 < d4) or (d4 < 0 < d3)): |
| 92 | return True |
| 93 | |
| 94 | if d1 == 0 and on_segment(p3, p4, p1): |
| 95 | return True |
| 96 | if d2 == 0 and on_segment(p3, p4, p2): |
| 97 | return True |
| 98 | if d3 == 0 and on_segment(p1, p2, p3): |
| 99 | return True |
| 100 | return d4 == 0 and on_segment(p1, p2, p4) |
| 101 | |
| 102 | |
| 103 | if __name__ == "__main__": |
no test coverage detected