impl/python.py

import math
from typing import List, Sequence

from .geo_point_in_polygon_types import GeoPoint


def point_in_polygon(point: GeoPoint, polygon: Sequence[GeoPoint]) -> bool:
    """Whether ``point`` lies inside ``polygon``, by ray casting on the lng/lat plane.

    A point exactly on an edge or a vertex counts as inside: a delivery address
    on the boundary line of a zone is in the zone. That is checked explicitly
    first, because plain ray casting answers boundary points inconsistently.

    Only + - * / and comparisons are used, in the same order in every
    language, so the answer is identical in Python, TypeScript and Rust even
    where floating point rounding decides it.
    """
    _check_point(point)
    if isinstance(polygon, (str, bytes)) or not isinstance(polygon, (list, tuple)):
        raise TypeError("polygon must be a list of points")
    for vertex in polygon:
        _check_point(vertex)

    # Work in floats throughout, as JavaScript and Rust do, so an integer
    # coordinate takes exactly the same arithmetic path.
    point = GeoPoint(lat=float(point.lat), lng=float(point.lng))
    ring: List[GeoPoint] = [GeoPoint(lat=float(v.lat), lng=float(v.lng)) for v in polygon]
    # A closed ring repeats its first vertex at the end; that is not an edge.
    if len(ring) >= 2 and _same(ring[0], ring[-1]):
        ring = ring[:-1]
    if _count_distinct(ring) < 3:
        raise ValueError("a polygon needs at least 3 distinct vertices")

    n = len(ring)
    for i in range(n):
        if _on_segment(point, ring[i], ring[(i + 1) % n]):
            return True

    inside = False
    for i in range(n):
        a = ring[i]
        b = ring[(i + 1) % n]
        # Half-open test so a ray passing exactly through a vertex counts it once.
        if (a.lat > point.lat) != (b.lat > point.lat):
            cross_lng = a.lng + ((point.lat - a.lat) * (b.lng - a.lng)) / (b.lat - a.lat)
            if point.lng < cross_lng:
                inside = not inside
    return inside


def _on_segment(p: GeoPoint, a: GeoPoint, b: GeoPoint) -> bool:
    cross = (b.lng - a.lng) * (p.lat - a.lat) - (b.lat - a.lat) * (p.lng - a.lng)
    if cross != 0:
        return False
    return (
        min(a.lng, b.lng) <= p.lng <= max(a.lng, b.lng)
        and min(a.lat, b.lat) <= p.lat <= max(a.lat, b.lat)
    )


def _same(a: GeoPoint, b: GeoPoint) -> bool:
    return a.lat == b.lat and a.lng == b.lng


def _count_distinct(ring: Sequence[GeoPoint]) -> int:
    count = 0
    for i in range(len(ring)):
        if not any(_same(ring[i], ring[j]) for j in range(i)):
            count += 1
    return count


def _is_number(value: object) -> bool:
    return isinstance(value, (int, float)) and not isinstance(value, bool) and math.isfinite(value)


def _check_point(p: object) -> None:
    if not hasattr(p, "lat") or not hasattr(p, "lng"):
        raise TypeError("a point must have lat and lng")
    if not _is_number(p.lat):  # type: ignore[attr-defined]
        raise TypeError("latitude must be a finite number of degrees")
    if not _is_number(p.lng):  # type: ignore[attr-defined]
        raise TypeError("longitude must be a finite number of degrees")
    if p.lat < -90 or p.lat > 90:  # type: ignore[attr-defined]
        raise ValueError("latitude must be between -90 and 90 degrees")
    if p.lng < -180 or p.lng > 180:  # type: ignore[attr-defined]
        raise ValueError("longitude must be between -180 and 180 degrees")