overlay: ring self-intersection check is quadratic and re-runs on already valid regions

validate_ring checks a ring for self-intersection by comparing every pair of its edges:

kernel/crates/algorithms/planar/overlay/src/lib.rs

Lines 257 to 276 in b4da64d

    
           fn self_intersects(r: &Ring, t: Tolerance) -> bool { 
        
               let n = r.points.len(); 
        
               for i in 0..n { 
        
                   for j in i + 1..n { 
        
                       if j == i + 1 || (i == 0 && j + 1 == n) { 
        
                           continue; 
        
                       } 
        
                       if segments_intersect( 
        
                           r.points[i], 
        
                           r.points[(i + 1) % n], 
        
                           r.points[j], 
        
                           r.points[(j + 1) % n], 
        
                           t.linear(), 
        
                       ) { 
        
                           return true; 
        
                       } 
        
                   } 
        
               } 
        
               false 
        
           }

It also runs on operands the overlay itself produced and already validated, in every overlay call. On large rings that check is the dominant cost. Measured by axioval/engine on axiolid-overlay 0.3.18 (release, a disc search at radii 0.4, 1.0 and 1.6 m on large floors):

corners	whole search	of which
50,000	4.1–4.5 s	about 4 s per call in this check alone
100,000	16–18 s	nearly all ring validation

That is quadratic, and it is now the last thing keeping the engine's corner limit at 50,000 (engine#435).

Needed

A sub-quadratic test. Replace the all-pairs test with a sweep line or a box-tree (BVH) candidate search, then the same exact segments_intersect decision on each candidate pair. Its result must be identical to today's, including the tolerance-based "edges meeting within t.linear()" rule. Only the candidate generation changes.
No re-validation of known-valid rings. Don't re-validate rings that are already known valid, for example a Region built by the overlay or by Region::new. Carry that through the type rather than a flag a caller can set. Public entry points taking raw polygons still validate.
Determinism: the refusal order and OverlayError variants stay as today.

Done when

A 50,000- and a 100,000-corner ring validate in about n log n time.
Repeated overlay calls on a validated Region skip the check.
Every existing refusal test still refuses with the same error.
A benchmark is committed, and a mutation probe covers the candidate search (a missed pair must be caught).

Reported by axioval/engine.

Triage: accepted, high. It is the last cost holding axioval/engine's corner limit at 50,000.

Decision, as stated in the issue:

Candidate search: the crate's own box tree (exact_arc::boxes, already pub(crate), used by Erode regions without quadratic cost in collinear and sub-millimetre corners #323's proved) proposes the edge pairs whose boxes, grown by t.linear(), overlap. The unchanged exact segments_intersect decides each pair, and the first pair found must be the same as today's (lowest i, then j), so the refusal order is deterministic.
No re-validation: a ring already known valid is not checked again. That is carried by the type: an internal validated-ring marker set by Region::new and by the overlay's own settled output, never by a caller.

Benchmark at 50k and 100k corners, and add a mutation probe for a dropped candidate pair.

perf(overlay): ring validation by box tree, and regions validated once (

Fixed in 370488b, released in axiolid-overlay 0.3.19. 100k-corner Region::new 17.1 → 0.059 s; regions validated once.

perf(axiolid): search free floors of up to 100,000 corners for a disc

Navigation Menu

Repository navigation

overlay: ring self-intersection check is quadratic and re-runs on already valid regions #341

Needed

Done when

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	fn self_intersects(r: &Ring, t: Tolerance) -> bool {
	let n = r.points.len();
	for i in 0..n {
	for j in i + 1..n {
	if j == i + 1 \|\| (i == 0 && j + 1 == n) {
	continue;
	}
	if segments_intersect(
	r.points[i],
	r.points[(i + 1) % n],
	r.points[j],
	r.points[(j + 1) % n],
	t.linear(),
	) {
	return true;
	}
	}
	}
	false
	}

overlay: ring self-intersection check is quadratic and re-runs on already valid regions #341

Description

Needed

Done when

Activity

GeneralPawz commented on Oct 19, 2026

GeneralPawz commented on Oct 20, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions