Strategy::Frag drops a filled region that List, Tree and Auto keep #87

use i_float::int::point::IntPoint;
use i_overlay::core::fill_rule::FillRule;
use i_overlay::core::overlay::Overlay;
use i_overlay::core::overlay_rule::OverlayRule;
use i_overlay::core::solver::{Solver, Strategy};

type P = IntPoint<i32>;

fn area2(contours: &[Vec<P>]) -> i64 {
    let mut a = 0;
    for c in contours {
        for i in 0..c.len() {
            let (p, q) = (c[i], c[(i + 1) % c.len()]);
            a += p.x as i64 * q.y as i64 - q.x as i64 * p.y as i64;
        }
    }
    a
}

// Even-odd containment of (4.4, 0.55), tested in i64 with everything scaled by
// 20 so the query point is the lattice point (88, 11).
fn contains_query_point(contours: &[Vec<P>]) -> bool {
    let (px, py) = (88i64, 11i64);
    let mut crossings = 0;
    for c in contours {
        for i in 0..c.len() {
            let (a, b) = (c[i], c[(i + 1) % c.len()]);
            let (x0, y0) = (a.x as i64 * 20, a.y as i64 * 20);
            let (x1, y1) = (b.x as i64 * 20, b.y as i64 * 20);
            if (y0 <= py) != (y1 <= py) {
                let s = (py - y0) * (x1 - x0) - (px - x0) * (y1 - y0);
                if (s > 0) == (y1 > y0) {
                    crossings += 1;
                }
            }
        }
    }
    crossings % 2 == 1
}

fn main() {
    let subj: Vec<Vec<P>> = vec![
        vec![P::new(0, 0), P::new(5, 1), P::new(4, 0), P::new(4, 2)],
        vec![P::new(0, 0), P::new(1, 0), P::new(4, 1)],
    ];

    println!("input, EvenOdd: contains (4.4, 0.55) = {}\n", contains_query_point(&subj));

    for (name, strategy) in [
        ("List", Strategy::List),
        ("Tree", Strategy::Tree),
        ("Auto", Strategy::Auto),
        ("Frag", Strategy::Frag),
    ] {
        let solver = Solver { strategy, ..Default::default() };
        let shapes = Overlay::with_contours_custom(&subj, &[], Default::default(), solver)
            .overlay(OverlayRule::Subject, FillRule::EvenOdd);
        let contours: Vec<Vec<P>> = shapes.iter().flatten().cloned().collect();
        let pts: Vec<Vec<(i32, i32)>> =
            contours.iter().map(|c| c.iter().map(|p| (p.x, p.y)).collect()).collect();
        println!(
            "{:<5} 2*area = {}  contains (4.4, 0.55) = {:<5} {:?}",
            name,
            area2(&contours),
            contains_query_point(&contours),
            pts
        );
    }
}