geometry.segment_intersection
=============================

.. py:module:: geometry.segment_intersection

.. autoapi-nested-parse::

   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)



Attributes
----------

.. autoapisummary::

   geometry.segment_intersection.points


Classes
-------

.. autoapisummary::

   geometry.segment_intersection.Point


Functions
---------

.. autoapisummary::

   geometry.segment_intersection.direction
   geometry.segment_intersection.on_segment
   geometry.segment_intersection.segments_intersect


Module Contents
---------------

.. py:class:: Point

   Bases: :py:obj:`NamedTuple`


   A point in 2D space.

   >>> Point(0, 0)
   Point(x=0, y=0)
   >>> Point(1, -3)
   Point(x=1, y=-3)


   .. py:attribute:: x
      :type:  float


   .. py:attribute:: y
      :type:  float


.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:data:: points