Hole binding: collinear-start tie in VSegment::Ord causes panic or wrong hole owner

[nickdbush]

Summary

VSegment::is_under_segment_order returns Ordering::Equal for two different segments when one of them starts on the other's line. Output collinear simplification creates exactly that situation (a T-junction) when result shapes touch at a point, and the hole binder's scan cannot order the tie. Depending on the scan structure this:

1. panics with index out of bounds … the index is 9223372036854775807 in bind/solver.rs (32+ shapes, KeyExpTree),
2. binds a hole to the wrong shape without panicking (32+ shapes, KeyExpTree),
3. links a shape to a hole it is not inside in overlay_hierarchy (no threshold, KeyExpList).

All inputs below are valid simple triangles/quads with small integer coordinates, default options (ogc off), i32 engine. Reproduces on 8.1.1 and main (1e33a35), i.e. after #80 and #81. We hit (1) on real OSM building footprints (three map tiles in a planet-wide run).

Steps to reproduce

(1) Panic -- Union, NonZero:

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

let core = [
    vec![[4079, 3454], [4090, 3462], [4083, 3471], [4073, 3464]],
    vec![[4078, 3464], [4084, 3463], [4081, 3460]],
    vec![[4072, 3463], [4080, 3471], [4061, 3471]],
];
let mut contours: Vec<Vec<IntPoint<i32>>> = core
    .iter()
    .map(|c| c.iter().map(|&[x, y]| IntPoint::new(x, y)).collect())
    .collect();
// 30 separate squares: the result reaches 32 shapes, so the binder uses the tree.
for i in 0..30 {
    let x = 100 + i * 40;
    contours.push(vec![
        IntPoint::new(x, 100), IntPoint::new(x + 10, 100),
        IntPoint::new(x + 10, 110), IntPoint::new(x, 110),
    ]);
}
let mut overlay: Overlay<i32> = Overlay::new(64);
for c in &contours {
    overlay.add_contour(c, ShapeType::Subject);
}
let _ = overlay.overlay(OverlayRule::Union, FillRule::NonZero); // panics

With 29 squares (31 result shapes) it succeeds.

(2) Wrong hole owner -- Union, NonZero, these 7 triangles plus 31 separate squares far away:

[[-4,3],[-7,6],[-4,6]], [[-4,2],[-1,5],[-4,5]], [[-3,2],[-10,5],[-6,5]], [[-3,0],[-4,1],[-1,0]],
[[-3,2],[-3,5],[-2,5]], [[-4,2],[-4,4],[0,4]], [[-2,1],[-5,1],[-2,4]]

The hole [(-4,3),(-4,4),(-3,2)] is attached to the small triangle [(-1,0),(-4,1),(-3,0)] instead of the 13-vertex shape that contains it.

(3) Wrong hierarchy link -- overlay_hierarchy(Union, NonZero), no extra squares:

[[-3,-1],[-3,-4],[-7,-4]], [[0,-4],[-1,-4],[-1,0]], [[0,-4],[-3,-7],[-3,-4]], [[0,-2],[-1,-3],[-1,-1]],
[[-1,-1],[-2,-2],[-2,-1]], [[-3,-4],[-3,-7],[-6,-4]], [[0,-2],[-3,-5],[-3,-2]]

The separate triangle [(-2,-2),(-2,-1),(-1,-1)] gets a link to the hole [(-1,-3),(-2,-4),(-1,-4)]; it should have no parent.

Expected

No panic; each hole belongs to the shape that contains it; independent shapes have no hierarchy link.

Actual

thread panicked at i_overlay-8.1.1/src/bind/solver.rs:186:13:
index out of bounds: the len is 1 but the index is 9223372036854775807

for (1); wrong results without warning for (2) and (3).

Environment

• iOverlay: 8.1.1 (also main at 1e33a35)
• Rust: 1.96.1
• OS: macOS 26.6.2 (Apple Silicon)

Additional context

When the hole's anchor (4078,3464)->(4081,3460) is looked up, the scan holds two live edges:

• A = (4072,3463)->(4080,3471) above the anchor
• B = (4073,3464)->(4079,3454) below the anchor (the correct parent)

The two result shapes touch at (4073,3464) and A's contour dropped that vertex as collinear, so B starts on A's line. is_under_segment_order takes the self.a < other.a branch and returns clock_order(A.a, B.a, A.b) = Equal. KeyExpList inserts the equal key before A, so its binary search still finds B; KeyExpTree sends it right (B = A.right), so first_less goes left from A and returns ContourIndex::EMPTY, and resolve_required_parent indexes parent_for_child with EMPTY.index(). The graph build sweep is not affected: it splits at intersections, so its segments never meet this tie.

preserve_output_collinear = true avoids it (no T-junctions survive), at the cost of collinear vertices in the output.

PR #70 reported the same panic and suspected Equal in VSegment::Ord, without a valid repro.

Proposal: break the tie on the later segment's far end, the same argument pattern the shared-start (Equal) branch already uses:

Ordering::Less => Triangle::clock_order(self.a, other.a, self.b)
    .then_with(|| Triangle::clock_order(self.a, other.b, self.b)),
Ordering::Equal => Triangle::clock_order(self.a, other.b, self.b),
Ordering::Greater => Triangle::clock_order(other.a, other.b, self.a)
    .then_with(|| Triangle::clock_order(other.a, other.b, self.b)),

The second orientation test only runs on a tie, so the common path is unchanged (a 300k-polygon union benchmarked within noise). Both branches are needed for antisymmetry: fixing only the Greater branch still gives wrong results. Checked against a brute-force "first segment below the anchor" oracle inside the binder over 70k random touching-polygon cases (overlay and overlay_hierarchy, list and tree paths): 3,631 wrong bindings without the change, 0 with it.

I have the change with tests (the three repros plus a comparator unit test) ready and can open a PR if helpful! But wanted to check with you first.

[NailxSharipov]

Hi @nickdbush!

Thank you for the detailed report. I confirmed this bugs.
The key trigger here is preserve_output_collinear = false. This option removes collinear vertices from the output contours. In the image below, T is removed from edge A but remains a vertex of shape B. The shapes still touch geometrically, but they no longer share an explicit vertex at T.(In valid/good geometry A must start at T) The current comparator does not handle this case correctly.
As a workaround, you can use preserve_output_collinear = true. This keeps edge A split at T.
I plan to fix this soon. I haven't decided yet whether to improve the comparator by checking the other endpoint, or to postpone collinear simplification until hole binding and hierarchy construction are complete.

[NailxSharipov]

fixed in #92