Check if a point lies in a polygon in linear time.

poly.rs

macro_rules! p {
    ($x:expr, $y:expr) => { Point { x: $x, y: $y } }
}

#[derive(Debug, Copy, Clone)]
struct Point {
    x: f32,
    y: f32,
}

fn main() {
    let ok = point_inside_poly(
        &[
            p!(0.0, 0.0),
            p!(1.0, 0.0),
            p!(1.0, 1.0),
            p!(0.0, 1.0),
        ],
        p!(0.3, 0.5),
    );
    println!("Point inside? {}.", if ok { "Yes" } else { "No" });
}

// https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
fn point_inside_poly(poly: &[Point], p: Point) -> bool {
    if poly.len() < 3 {
        return false
    }

    let mut j = poly.len() - 1;
    let mut c = false;

    for i in 0..poly.len() {
        let pi = poly[i];
        let pj = poly[j];
        let b = ((pi.y > p.y) != (pj.y > p.y)) && (p.x < ((pj.x-pi.x)*(p.y-pi.y))/(pj.y-pi.y)+pi.x);
        c = b != c;
        j = i;
    }

    c
}