impl/typescript.ts

import { type GeoPoint } from "./geo_point_in_polygon_types.ts";

/**
 * Whether a point lies inside a polygon, by ray casting (the even-odd rule)
 * on the flat longitude/latitude 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
 * (inside on some edges, outside on others).
 *
 * Only + - * / and comparisons are used, in the same order in every language,
 * so the answer is identical in TypeScript, Python and Rust even where
 * floating point rounding decides it.
 */
export function pointInPolygon(point: GeoPoint, polygon: readonly GeoPoint[]): boolean {
  checkPoint(point);
  if (!Array.isArray(polygon)) throw new TypeError("polygon must be a list of points");
  polygon.forEach(checkPoint);

  let ring = polygon;
  // A closed ring repeats its first vertex at the end; that is not an edge.
  if (ring.length >= 2 && same(ring[0], ring[ring.length - 1])) ring = ring.slice(0, -1);
  if (countDistinct(ring) < 3) throw new RangeError("a polygon needs at least 3 distinct vertices");

  const n = ring.length;
  for (let i = 0; i < n; i++) {
    if (onSegment(point, ring[i], ring[(i + 1) % n])) return true;
  }

  let inside = false;
  for (let i = 0; i < n; i++) {
    const a = ring[i];
    const b = ring[(i + 1) % n];
    // Half-open test (one end strictly above, the other not) so a ray passing
    // exactly through a vertex counts it once, not twice.
    if (a.lat > point.lat !== b.lat > point.lat) {
      const crossLng = a.lng + ((point.lat - a.lat) * (b.lng - a.lng)) / (b.lat - a.lat);
      if (point.lng < crossLng) inside = !inside;
    }
  }
  return inside;
}

function onSegment(p: GeoPoint, a: GeoPoint, b: GeoPoint): boolean {
  const cross = (b.lng - a.lng) * (p.lat - a.lat) - (b.lat - a.lat) * (p.lng - a.lng);
  if (cross !== 0) return false;
  return (
    p.lng >= Math.min(a.lng, b.lng) &&
    p.lng <= Math.max(a.lng, b.lng) &&
    p.lat >= Math.min(a.lat, b.lat) &&
    p.lat <= Math.max(a.lat, b.lat)
  );
}

function same(a: GeoPoint, b: GeoPoint): boolean {
  return a.lat === b.lat && a.lng === b.lng;
}

function countDistinct(ring: readonly GeoPoint[]): number {
  let count = 0;
  for (let i = 0; i < ring.length; i++) {
    let seen = false;
    for (let j = 0; j < i; j++) {
      if (same(ring[i], ring[j])) {
        seen = true;
        break;
      }
    }
    if (!seen) count++;
  }
  return count;
}

function checkPoint(p: GeoPoint): void {
  if (p === null || typeof p !== "object") throw new TypeError("a point must have lat and lng");
  if (typeof p.lat !== "number" || !Number.isFinite(p.lat)) throw new TypeError("latitude must be a finite number of degrees");
  if (typeof p.lng !== "number" || !Number.isFinite(p.lng)) throw new TypeError("longitude must be a finite number of degrees");
  if (p.lat < -90 || p.lat > 90) throw new RangeError("latitude must be between -90 and 90 degrees");
  if (p.lng < -180 || p.lng > 180) throw new RangeError("longitude must be between -180 and 180 degrees");
}