Boolean operations can produce OGC-invalid polygons with disconnected interiors

Summary

Boolean operations (difference, xor, etc.) can produce polygons where interior holes share two or more vertices, creating geometries with disconnected interiors. This violates the OGC Simple Feature Specification requirement that polygon interiors must be connected point sets.

This issue originates in iOverlay, which geo uses for boolean operations. See: iShape-Rust/iOverlay#27

Reproducible Example

use geo::{BooleanOps, MultiPolygon, Polygon, wkt};
use geo::algorithm::{Area, Validation};

// Create a 5x5 box
let exterior: Polygon<f64> = wkt!(POLYGON((0.0 0.0, 5.0 0.0, 5.0 5.0, 0.0 5.0, 0.0 0.0)));

// Create two L-shaped regions to subtract (4 boxes that form 2 L-shapes)
let interior: MultiPolygon<f64> = wkt!(MULTIPOLYGON(
    ((1.0 2.0, 2.0 2.0, 2.0 4.0, 1.0 4.0, 1.0 2.0)),
    ((2.0 3.0, 3.0 3.0, 3.0 4.0, 2.0 4.0, 2.0 3.0)),
    ((2.0 1.0, 4.0 1.0, 4.0 2.0, 2.0 2.0, 2.0 1.0)),
    ((3.0 2.0, 4.0 2.0, 4.0 3.0, 3.0 3.0, 3.0 2.0))
));

let result = exterior.difference(&interior);

// Area is correct: 25 - 3 - 3 = 19
assert_eq!(result.unsigned_area(), 19.0);

// But we get 1 polygon with 2 holes that share vertices at (2,2) and (3,3)
// This creates a disconnected interior, which is OGC-invalid
println!("Polygon count: {}", result.0.len()); // Prints: 1

Visual Representation

    0   1   2   3   4   5
  5 ┌───────────────────┐
    │                   │
  4 │   ┌───────┐       │
    │   │ ░   ░ │       │   Two L-shaped holes share vertices ● at (2,2) and (3,3)
  3 │   │   ┌───●───┐   │
    │   │ ░ │   │ ░ │   │   ░ = holes
  2 │   └───●───┘   │   │
    │       │ ░   ░ │   │   The shared diagonal disconnects the interior
  1 │       └───────┘   │
    │                   │
  0 └───────────────────┘

When two holes share 2+ vertices, they create a "corridor" that disconnects the polygon's interior into two separate regions.

Expected Behavior

The result should be split into multiple valid polygons at the pinch points, similar to how GEOS/Shapely handles this case:

• Current: 1 polygon with 2 holes sharing vertices (invalid)
• Expected: 2 polygons with 0-1 holes each (valid)

Both representations have the same total area (19.0), but only the split version is OGC-valid.

OGC Specification Reference

The OGC Simple Feature Specification (ISO 19125-1) states:

"The interior of every Surface is a connected point set."

Additional Notes

1. The Validation trait in geo does not currently detect this specific invalidity. The trait explicitly notes this limitation in geo/src/algorithm/validation/polygon.rs:

   • the polygon interior is simply connected (i.e. the rings must not touch in a way that splits the polygon into more than one part)
     Note: the simple connectivity of the interior is not checked by this implementation.

2. A failing test case has been added in Add failing test for issue iOverlay#27 (disconnected interiors) #1471 to track this issue.

3. The fix needs to happen in iOverlay, and as mentioned on the upstream issue, the author is willing to find a way to ensure OGC-valid results. Once fixed upstream, updating the iOverlay dependency version should resolve this, however it also shows that the validity checking algorithm is missing a core check.

Environment

• geo version: 0.32.0
• i_overlay version: 4.0.x