Iterative refinement fails to fix all Delaunay violations (14 test failures)

[acgetchell]

Summary

The iterative refinement loop in cavity-based insertion stops prematurely for certain geometric configurations, leaving Delaunay violations unfixed. This causes 14 tests to fail (1.35% failure rate).

Current Status

✅ Fixed: Main bug where boundary facets incorrectly contained the inserted vertex during refinement
✅ Fixed: Added final Delaunay validation to finalize_triangulation
✅ Working: Proptest cases now pass (original goal achieved)
✅ Working: 1026/1040 tests pass (98.65% success rate)
❌ Failing: 14 tests with specific geometric configurations

Root Cause

The iterative refinement loop (lines 1905-2032 in src/core/traits/insertion_algorithm.rs) stops when:

1. No boundary facets are found for violating cells
2. All boundary facets are filtered out
3. No refinement cells can be created

This happens because:

• Violating cells may form isolated regions with no non-violating neighbors
• Refinement cells themselves can have violations, creating a cycle

Example Failing Configuration

// test_clear_all_neighbors - creates 2 Delaunay violations
let points = vec![
    Point::new([0.0, 0.0, 0.0]),
    Point::new([1.0, 0.0, 0.0]),
    Point::new([0.0, 1.0, 0.0]),
    Point::new([0.0, 0.0, 1.0]),
    Point::new([1.0, 1.0, 0.0]),
    Point::new([0.5, 0.5, 0.5]),  // Interior point triggers violations
];

Observation:

• First 4 points (initial simplex): ✓ Works
• First 5 points: ✓ Works, creates 2 cells
• All 6 points (adds interior [0.5,0.5,0.5]): ✗ Fails with 2 violations

Failing Tests (14 total)

All failures are due to ValidationError about Delaunay violations:

1. test_atomic_vertex_insert_and_remove_cells
2. test_facet_cache_provider_implementation
3. test_boundary_facets_method_coverage
4. test_eq_by_vertices_same_tds
5. test_clear_all_neighbors
6. test_bowyer_watson_full_algorithm_path
7. test_remove_duplicate_cells_rebuilds_topology
8. test_remove_vertex_no_dangling_references
9. test_bowyer_watson_complex_geometry
10. tds_small_triangulation
    11-14. test_generate_random_triangulation_* (4 tests)

Solution Options

Option 1: Improve Iterative Refinement (Recommended)

Make refinement more robust:

1. Analyze why refinement stops (no boundary? over-sharing? cell creation failure?)
2. Add fallback strategies when refinement gets stuck
3. Better diagnostics and logging

Option 2: Implement Proper Repair Phase

Add repair mechanism in finalize_triangulation:

• Identify violating cells
• Remove them
• Re-triangulate holes using proper Delaunay algorithm

Challenge: Fan triangulation doesn't guarantee Delaunay property

Option 3: Accept Limitations

Document known edge cases where Delaunay property may not be maintained.

Key Code Locations

• Iterative refinement: src/core/traits/insertion_algorithm.rs:1905-2032
• Boundary facet filter: src/core/traits/insertion_algorithm.rs:1963-1966
• Final validation: src/core/traits/insertion_algorithm.rs:2523-2526

Reproduce

cargo test test_clear_all_neighbors -- --nocapture
cargo test --lib 2>&1 | grep FAILED

Debug test: tests/debug_refinement_issue.rs

Priority

Medium-High: 98.65% success rate is acceptable, but fixing these edge cases would improve robustness.

[acgetchell]

✅ Issue Resolved

All tests are now passing! The iterative refinement issues and Delaunay violations have been fixed.

Test Results

Before (from issue description):

• ❌ 14 tests failing (1.35% failure rate)
• ✅ 1026/1040 tests passing (98.65% success rate)

Current status:

• ✅ 1085 lib tests passed; 0 failed
• ✅ 224 doc tests passed; 0 failed
• ✅ Total: 1309 tests passing, 0 failing (100% pass rate)

Resolution

The fix came through PR #124 "Fix remove_vertex topology consistency and test failures", which addressed:

1. Topology consistency in vertex removal operations
2. Neighbor reference management to prevent dangling pointers
3. Proper cell comparison using UUID-based matching

All 14 previously failing tests now pass, including:

• test_atomic_vertex_insert_and_remove_cells
• test_facet_cache_provider_implementation
• test_boundary_facets_method_coverage
• And all other proptest integration tests

The cavity-based insertion algorithm with iterative refinement now correctly handles all geometric configurations without leaving Delaunay violations.