OverlayNGRobust symDifference returns an inverted polygon: the area check has no lower bound for SYMDIFFERENCE #1239

For a valid polygon and a valid line crossing near its vertices, OverlayNGRobust returns an invalid symmetric difference: the polygon's ring comes back as the hole of a tiny shell (area ~1.4e-22), so the result has area −0.03123 instead of 0.03123. Union and difference of the same pair are correct. The cause looks like a gap in OverlayUtil.isResultAreaConsistent: for SYMDIFFERENCE it only checks the upper bound, so the bad result of the first snapping try is accepted instead of rejected. Reproduces on 1.20.0 and current master (5a0a7363); GEOS 3.15.0 and current main return the same result.

Reproducer

WKTReader reader = new WKTReader();
Geometry a = reader.read("POLYGON ((20.58 46.965, 27.52 53.905, 28.52 54.914, 20.58 46.965))");
Geometry b = reader.read("LINESTRING (27.519999973297118 53.90499997329712, 52.192 78.577, 27.519 53.904, 28.519999999 54.913999999, 39.599 65.984)");

a.isValid(); b.isValid();                                         // true, true
Geometry r = OverlayNGRobust.overlay(a, b, OverlayNG.SYMDIFFERENCE);
r.getArea();                                                      // -0.031229999995478153
r.isValid();                                                      // false

OverlayNGRobust.overlay(a, b, OverlayNG.UNION).getArea();         // 0.03122999999997944, valid
OverlayNGRobust.overlay(a, b, OverlayNG.DIFFERENCE).getArea();    // 0.03122999999997944, valid

b has no area, so the areal part of a ⊕ b should be a itself: area 0.03123, valid. The returned polygon instead has a 4-vertex shell of area ~1.4e-22 near (28.52 54.914), and a's ring after snapping (area 0.0312299999955) as its hole. The input is reduced from a fuzzer case; every vertex of b is needed.

What happens

1. Floating-point OverlayNG throws TopologyException (non-noded intersection), so OverlayNGRobust falls back to snapping noding, starting from snapTolerance(a, b) = 78.577 / 1e12 = 7.8577e-11 and multiplying it by 10 on each try.

2. The first two tries, with OverlayNG.overlay(a, b, op, new SnappingNoder(tol)):

   tol	SYMDIFFERENCE	UNION	DIFFERENCE
   7.8577e-11 (first try)	area −0.03123, invalid — accepted	TopologyException: Result area inconsistent with overlay operation	same as union
   7.8577e-10 (second try)	0.03123, valid	0.03123, valid	0.03123, valid

3. On the first try the area check rejects the result for union and difference, so OverlayNGRobust moves on and the second try gives the correct answer; for symDifference it accepts the inverted result:

   case OverlayNG.SYMDIFFERENCE:
     isConsistent = isLess(areaResult, areaA + areaB, AREA_HEURISTIC_TOLERANCE);
     break;

   INTERSECTION checks only upper bounds, UNION only lower ones, and DIFFERENCE both. SYMDIFFERENCE checks only the upper bound, so a negative (or near-zero) area has nothing to fail against.

Possible fix

The symmetric difference can't be smaller than the difference of the input areas. Written the way #1005 wrote the lower bound for DIFFERENCE, so that nearly identical inputs (whose areas differ only by rounding) still get an empty result:

case OverlayNG.SYMDIFFERENCE:
  isConsistent = isLess(areaResult, areaA + areaB, AREA_HEURISTIC_TOLERANCE)
      && areaResult >= Math.abs(areaA - areaB) - AREA_HEURISTIC_TOLERANCE * Math.max(areaA, areaB);
  break;

On master 5a0a7363 with this change: the reproducer returns 0.031229999999978345, valid (equal to union); the input from #951 still gives an empty result, both through OverlayNGRobust and through SnappingNoder(1e-10) / SnappingNoder(1e-6); all 2307 tests in modules/core pass. A plainer isGreater(areaResult, Math.abs(areaA - areaB), AREA_HEURISTIC_TOLERANCE) is not enough: on the #951 input it rejects the correct empty result (|areaA − areaB| = 8.9e-16) and throws Result area inconsistent. The same change in GEOS 3.15.0's OverlayUtil::isResultAreaConsistent fixes the reproducer there too and keeps the #951 input empty.

This only fixes the safety net — the first snapping try still builds an inverted polygon, which may be worth a look on its own.

Results across engines

The SYMDIFFERENCE case of the area check is the same in JTS master 5a0a7363, GEOS main and NTS develop.

Related

• Add OverlayNG area check heuristic #812 — added the area check
• OverlayNG area check heuristic causing issues when snapping noder is used #951 / Fix OverlayNG Area Check heuristic for difference #1005 — the area check being too strict for DIFFERENCE
• Summary: OverlayNG failures #1000 — summary of OverlayNG wrong results on nearly-coincident linework; notes the area check "does not handle all cases"

Environment

• JTS 1.20.0 (Maven Central), Oracle JDK 24.0.1 on macOS (arm64)
• JTS master 5a0a7363 (2026-09-28), built from source, Temurin 21 on Linux (arm64, Docker)

Found by fuzzing NetTopologySuite's legacy overlay against OverlayNG, with each result checked against the bounds the input areas put on the operation; then reproduced in JTS and GEOS.

Edited after filing: the fix first proposed here (isGreater(areaResult, Math.abs(areaA - areaB), …)) would have brought #951 back for SYMDIFFERENCE; also corrected the snapping tolerances (computed from a alone at first) and the shell area.