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

[DRMacIver]

Summary

For a self-intersecting subject under EvenOdd, Strategy::Frag returns a smaller region than the
other three strategies. Strategy is documented as a choice about performance, so I would not
expect it to affect the result.

Steps to reproduce

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
        );
    }
}

Expected behavior

All four strategies return the same region. The query point (4.4, 0.55) is inside the subject under
EvenOdd, so it should be inside the output whichever strategy produced it.

Actual behavior

input, EvenOdd: contains (4.4, 0.55) = true

List  2*area = 7  contains (4.4, 0.55) = true  [[(4, 2), (0, 0), (1, 0), (4, 1), (4, 0), (5, 1)]]
Tree  2*area = 7  contains (4.4, 0.55) = true  [[(4, 2), (0, 0), (1, 0), (4, 1), (4, 0), (5, 1)]]
Auto  2*area = 7  contains (4.4, 0.55) = true  [[(4, 2), (0, 0), (1, 0), (4, 1), (4, 0), (5, 1)]]
Frag  2*area = 6  contains (4.4, 0.55) = false [[(4, 2), (0, 0), (1, 0), (4, 1), (5, 1)]]

Frag omits the triangle (4, 0), (4, 1), (5, 1) that the other three keep. The query point lies
inside that triangle, so this is a region difference rather than a different representation of the
same region.

Environment

• iOverlay version: 8.1.0, and current main (0022b34)
• Rust version: 1.98.0 (88d9e12ae 2026-08-18)
• OS: macOS 26.6.2, aarch64

Additional context

The reproduction also depends on i_float for IntPoint.

BTW, this bug was found using hegel. Happy to contribute the tests if you're interested.

[NailxSharipov]

Hi thanks for the report.
I did some research and here is an explanation problem picture:

So the fix must be in solver_fragment.rs 61
let index = buffer.layout.index(x) - 1;

Since the orange edge stored in left groups[1]

And since we cannot find the orange edge, we do not split it. This is a very important problem: we could end up not just with an incorrect result, but with something far worse.

If you'd like to submit a PR, I'll gladly accept it.

[NailxSharipov]

fixed in #89