Function _det

divide_and_conquer/convex_hull.py:188–220

Computes the sign perpendicular distance of a 2d point c from a line segment ab. The sign indicates the direction of c relative to ab. A Positive value means c is above ab (to the left), while a negative value means c is below ab (to the right). 0 means all three points are on a str

(a: Point, b: Point, c: Point)

def _det(a: Point, b: Point, c: Point) -> float:
    """
    Computes the sign perpendicular distance of a 2d point c from a line segment
    ab. The sign indicates the direction of c relative to ab.
    A Positive value means c is above ab (to the left), while a negative value
    means c is below ab (to the right). 0 means all three points are on a straight line.

    As a side note, 0.5 * abs|det| is the area of triangle abc

    Parameters
    ----------
    a: point, the point on the left end of line segment ab
    b: point, the point on the right end of line segment ab
    c: point, the point for which the direction and location is desired.

    Returns
    --------
    det: float, abs(det) is the distance of c from ab. The sign
    indicates which side of line segment ab c is. det is computed as
    (a_xb_y + c_xa_y + b_xc_y) - (a_yb_x + c_ya_x + b_yc_x)

    Examples
    ----------
    >>> _det(Point(1, 1), Point(1, 2), Point(1, 5))
    0.0
    >>> _det(Point(0, 0), Point(10, 0), Point(0, 10))
    100.0
    >>> _det(Point(0, 0), Point(10, 0), Point(0, -10))
    -100.0
    """

    det = (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x)
    return det


def convex_hull_bf(points: list[Point]) -> list[Point]: