geo.point-in-polygon

Imports name this capability’s declared dependencies, which fune builds next to it in your project; each one links to its page.

use super::funejson::Value;  ← the fune runtime: the JSON value the test vectors use; fune build keeps it only where a signature takes one

/// 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 Rust, TypeScript and Python even where
/// floating point rounding decides it.
///
/// # Panics
/// Panics if a coordinate is out of range or the polygon has fewer than 3
/// distinct vertices.
pub fn point_in_polygon(point: &GeoPoint, polygon: &[GeoPoint]) -> bool {
    check_point(point);
    for vertex in polygon {
        check_point(vertex);
    }

    let mut ring: &[GeoPoint] = polygon;
    // A closed ring repeats its first vertex at the end; that is not an edge.
    if ring.len() >= 2 && same(&ring[0], &ring[ring.len() - 1]) {
        ring = &ring[..ring.len() - 1];
    }
    if count_distinct(ring) < 3 {
        panic!("a polygon needs at least 3 distinct vertices");
    }

    let n = ring.len();
    for i in 0..n {
        if on_segment(point, &ring[i], &ring[(i + 1) % n]) {
            return true;
        }
    }

    let mut inside = false;
    for i in 0..n {
        let a = &ring[i];
        let 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) {
            let cross_lng = a.lng + ((point.lat - a.lat) * (b.lng - a.lng)) / (b.lat - a.lat);
            if point.lng < cross_lng {
                inside = !inside;
            }
        }
    }
    inside
}

fn on_segment(p: &GeoPoint, a: &GeoPoint, b: &GeoPoint) -> bool {
    let cross = (b.lng - a.lng) * (p.lat - a.lat) - (b.lat - a.lat) * (p.lng - a.lng);
    if cross != 0.0 {
        return false;
    }
    p.lng >= a.lng.min(b.lng)
        && p.lng <= a.lng.max(b.lng)
        && p.lat >= a.lat.min(b.lat)
        && p.lat <= a.lat.max(b.lat)
}

fn same(a: &GeoPoint, b: &GeoPoint) -> bool {
    a.lat == b.lat && a.lng == b.lng
}

fn count_distinct(ring: &[GeoPoint]) -> usize {
    let mut count = 0;
    for i in 0..ring.len() {
        if !(0..i).any(|j| same(&ring[i], &ring[j])) {
            count += 1;
        }
    }
    count
}

fn check_point(p: &GeoPoint) {
    if !p.lat.is_finite() {
        panic!("latitude must be a finite number of degrees");
    }
    if !p.lng.is_finite() {
        panic!("longitude must be a finite number of degrees");
    }
    if p.lat < -90.0 || p.lat > 90.0 {
        panic!("latitude must be between -90 and 90 degrees");
    }
    if p.lng < -180.0 || p.lng > 180.0 {
        panic!("longitude must be between -180 and 180 degrees");
    }
}

pub fn geo_point_from_value(v: &Value) -> GeoPoint {
    GeoPoint {
        lat: v.get("lat").as_f64(),
        lng: v.get("lng").as_f64(),
    }
}

pub fn geo_point_to_value(p: &GeoPoint) -> Value {
    Value::obj(vec![("lat", Value::Float(p.lat)), ("lng", Value::Float(p.lng))])
}

pub fn fune_vector(args: &[Value]) -> Value {
    let polygon: Vec<GeoPoint> = args[1].as_arr().iter().map(geo_point_from_value).collect();
    Value::Bool(point_in_polygon(&geo_point_from_value(&args[0]), &polygon))
}