Tessellator rejects a valid polygon whose holes touch the outer ring and each other at single vertices

Since 10.5.0, LatLonShape and XYShape refuse to index a valid polygon whose holes touch the outer ring and each other only at single vertices: createIndexableFields throws IllegalArgumentException: Unable to Tessellate shape. Possible malformed shape detected. #15739 made the reflex-corner branch of Tessellator.isLocallyInside inclusive (<= 0) to pick the right hole bridge for #15731; the same function also guards where splitEarcut may cut a ring in two, and there the inclusive test accepts a cut of length zero between two copies of a vertex the holes share with the outer ring. One piece is then a hole's own outline, which cannot be triangulated. 10.4.0 tessellates the repro polygon exactly (13 triangles, area 75.5); 10.5.0 to 10.5.2, 10.6.0 (by reading) and main reject it (on main, 810 of its 972 hole orders and start vertices fail). The failure is loud: one document cannot be indexed, nothing wrong is indexed.

• Hole merging. eliminateHoles joins each hole to the outer ring, either at a vertex they share or through a bridge, which leaves two copies of each bridge end in the ring. The result is one ring that can pass through the same point several times.
• Ear clipping. earcutLinkedList cuts off convex corners (ears) as triangles. When none is left it filters points, cures small self-intersections and finally calls splitEarcut, which looks for a diagonal that cuts the ring in two, checked by isValidDiagonal.
• isLocallyInside(a, b) answers "does b lie inside the corner of the ring at a?". For a reflex corner (more than 180 degrees) it accepts b when b is on the inner side of either edge at a. #15739 changed both tests from < 0 to <= 0 (Tessellator.java:1263-1266), so a b exactly on one of the edges now counts as inside.

Outer ring (0,0) (0,12) (4,12) (4,4) (12,4) (12,0); V = (4,4) is its reflex corner. Hole 0 (4,4) (1,2) (2,1) and hole 1 (3,4) (4,4) (3,5) touch the ring (and each other) only at V; hole 2 (2,6) (1,5) (3,4) touches hole 1 only at (3,4). Area 80 - 2.5 - 0.5 - 1.5 = 75.5.

1. Hole merging gives a 17-vertex ring that passes through V three times: (1,2) (4,4) (4,12) (0,12) (0,0) (1,5) (2,6) (3,4) (3,5) (4,4) (3,4) (1,5) (0,0) (12,0) (12,4) (4,4) (2,1).
2. Ear clipping cuts 4 triangles and is stuck with 13 vertices; it falls back to splitEarcut (Tessellator.java:681-689, :909-950).
3. isValidDiagonal(a, b) (:1205-1229) is asked about a and b, two copies of V. Its first checks, isLocallyInside(a.previous, b) and isLocallyInside(b.next, a) (:1209-1210), look at the reflex corners (3,5) and (2,1). Because a and b are the same point, the tested point lies exactly on the corner's own edge to V, so one area is exactly 0: <= 0 passes both checks, < 0 fails both. For equal points the method then returns true at once (:1216-1217).
4. The ring is cut at V into (3,5) (4,4) (2,1) (1,2) (4,4) (4,12) (2,6) (3,4) and (12,4) (3,4) (1,5) (0,0). The first piece clips 3 ears and is left with (1,2) (4,4) (2,1): hole 0's outline, wound the wrong way. It has no ear and no diagonal, so earcutLinkedList throws (:687-688).
5. 10.4.0, with < 0, refuses that cut, cuts (1,2)-(1,5) instead and returns 13 triangles of total area 75.5.

isLocallyInside is called seven times, in four places: the bridge search (fetchHoleBridge, :584), cureLocalIntersections (:875, :876), and isValidDiagonal's neighbour checks (:1209-1210) and main checks (:1219-1220). Running all 16 strict/inclusive combinations against the repro and upstream TestTessellator (70 tests run; its 6 @Nightly tests and 1 @AwaitsFix test are skipped): the repro fails exactly when the neighbour checks are inclusive, and testComplexPolygon64 (#15731) fails exactly when the bridge search is strict. The other two sites change neither result.

• Who is hit. Applications on 10.5.0, 10.5.1, 10.5.2, 10.6.0 (by reading) or main that index polygons with holes through LatLonShape or XYShape: createIndexableFields (run) and createDocValueField (read: the same Tessellator.tessellate call), with the default checkSelfIntersections=false and with true. No special configuration and no scale needed: the exception comes from building the fields, before any codec or IndexWriterConfig setting plays a part. Users upgrading from 10.4.x are exposed: 10.4.0 was cut from branch_10_4, which never got the change.
• Effect. That document cannot be indexed: the exception comes while its fields are built, so the application never gets fields to hand to IndexWriter. The repro builds the fields only and opens no writer; by reading the code, nothing wrong is produced and nothing reaches the index, so other documents, queries and the index are not affected.
• What it takes. The minimised repro needs two holes that share a reflex vertex of the outer ring, and a third hole that touches one of them at another vertex, all at exact shared vertices; this is one known trigger, not a proven necessary condition. The outcome depends on the hole order and the start vertex of each ring (810 of 972 combinations fail) and on the coordinates: of 8 scales x 5 real-world offsets, 15 of 40 LatLon and 17 of 40 XY variants fail on main and none of 80 on 10.4.0. 29 of the 32 failures are at scales 1, 0.5 and 0.25, where the scaled coordinates are exact binary fractions, 3 at 1e-3 or 1e-5, none at 0.1, 0.01 or 1e-4. That points to floating-point rounding, not lat/lon quantization: the Tessellator computes on the input coordinates, not the encoded ones (Tessellator.java:1665-1672). A tilted variant without collinear edges fails too.
• How likely. Touching holes do occur in real data (upstream fixed #15554, #15695 and #15731 for valid touching-hole polygons in early 2026), but this chained layout is narrow, and no public report of it was found since 10.5.0 shipped (2026-06-25). In a sweep of 9,000 random valid lattice polygons with the other known Tessellator bugs fixed, 8 were still rejected, 2 of them for this reason.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected the valid polygon to be tessellated, got java.lang.IllegalArgumentException: Unable to Tessellate shape. Possible malformed shape detected.
       org.apache.lucene.document.TestTessellatorChainedTouchingHoles.testHolesTouchingAtSingleVertices(TestTessellatorChainedTouchingHoles.java:35)
     Caused by: java.lang.IllegalArgumentException: Unable to Tessellate shape. Possible malformed shape detected.
       org.apache.lucene.geo.Tessellator.earcutLinkedList(Tessellator.java:687)
       org.apache.lucene.geo.Tessellator.splitEarcut(Tessellator.java:936)
       org.apache.lucene.geo.Tessellator.earcutLinkedList(Tessellator.java:683)
       org.apache.lucene.geo.Tessellator.tessellate(Tessellator.java:202)
       org.apache.lucene.geo.Tessellator.tessellate(Tessellator.java:152)
       [...]

• Contract. The class javadoc (Tessellator.java:40-52, abridged) requires "valid polygons: No self intersections; Holes must be inside the polygon; Holes may only touch at one vertex; Polygon must have an area (e.g., no "line" boxes)", plus a note on overflow with tiny values. Every touch here is one shared vertex. JTS 1.20 IsValidOp accepts the polygon and all 8 hole subsets; an independent check with exact integer arithmetic agrees. XYShape/LatLonShape promise "indexable fields for polygon geometry", and the strict path rejects this valid polygon as well.
• Correct before. 10.4.0 and 10.3.0 return 13 triangles, area 75.5, whose union equals the polygon. Every proper subset of the holes tessellates on main with the right area and full coverage on a sample grid.
• Tests. TestTessellator requires polygons whose holes touch the rest of the polygon at two or more distinct vertices to tessellate with the area matching. In testComplexPolygon41 (:724), 57 (:897), 61 (:932) and 62 (:938) one hole touches both the shell and another hole at different vertices, as hole 1 does here; in 53 (:863), 54 (:869) and 55 (:875) 8 to 11 holes each touch other rings at two or more points. The area is compared with delta 0 for 41, 53-55 and 62, and 3e-11 and 1e-11 for 57 and 61 (:900, :935). The #15731 tests 64 and 65 are not examples: no hole in them touches other rings at two or more points.
• History. Upstream fixed every earlier rejection of a valid touching-hole polygon as a bug: #13841, #15205, #15554, #15695, #15731. #15739's PR text and CHANGES entry only describe #15731. The PR text: "We were failing to detect this case and choosing an invalid bridge to eliminate the hole"; the CHANGES entry: "In this case we might fail to detect it and choose a wrong bridge to eliminate the hole" (lucene/CHANGES.txt:1174-1175); its one review is an LGTM.
• The ported library. mapbox/earcut keeps the strict < 0 in locallyInside.

The strongest case for "intended" (built by the intended-behaviour checker, the cross-model reviewer and the adjudication): read "Holes may only touch at one vertex" as one contact per hole (hole 1 touches at two); note that Tessellator is @lucene.internal (Tessellator.java:72), that Polygon is @lucene.experimental and warns that self-crossing input "may result in unexpected behavior" (Polygon.java:34, :41), and that the message says "Possible malformed shape"; add that three rings meet at V, and call the collinear edges degenerate input. JTS validity is an outside standard and does not settle how maintainers read the one-vertex rule.

Why it fails: the two-hole control {hole 1, hole 2} has the same two contacts on hole 1 and passes on main; upstream's own tests require holes that touch at two or more distinct vertices to tessellate (41, 53-55, 57, 61, 62); the polygon is not self-crossing; the public XYShape and LatLonShape methods carry no internal tag; a tilted variant with no collinear hole and shell edges still fails; and 10.4.0 returns an exact tessellation, so 10.5 replaced a correct result with a rejection. The cross-model fact check of this doc rated the case moderate (the literal precondition, the two tags, three rings at V) and still found the evidence against it more persuasive; the earlier reviewers rated it weak or rejected it. Verdict: not intended, a regression.

Three scoped variants of #15739's comparison were built and checked; one is recommended. The call-site matrix (all 16 strict/inclusive combinations of the four places that call isLocallyInside) shows why a scoped change is needed: #15731 needs <= 0 in the bridge search (:584), this polygon needs < 0 in isValidDiagonal's neighbour checks (:1209-1210). Add a CHANGES entry under Bug Fixes.

isLocallyInside gets a flag; its two-argument form keeps today's <= 0, and only isLocallyInside(a.previous, b) and isLocallyInside(b.next, a) in isValidDiagonal (:1209-1210) pass false, the pre-10.5 strict test; the ccw branch picks <= 0 or < 0 by the flag. Tessellator.java only, +23/-5 lines, ./gradlew tidy clean.

        // check next edges are locally visible; use the strict test, since for a diagonal
        // between two copies of the same vertex b always lies on the edge (a.previous, a)
        || isLocallyInside(a.previous, b, false) == false
        || isLocallyInside(b.next, a, false) == false
  ...
  private static boolean isLocallyInside(final Node a, final Node b) {
    return isLocallyInside(a, b, true);
  }
  ...
      if (includeCollinear) {
        return areaPrevious <= 0 || areaNext <= 0;
      }
      return areaPrevious < 0 || areaNext < 0;

Trade-offs

• Smallest behavioural change: the bridge search and the other callers are exactly as on main, so #15731 is untouched; only zero-area cases in the neighbour checks change. That is not limited to zero-length diagonals: any candidate collinear with those edges is now refused there; the sweep found no other change, which is evidence, not proof.
• cureLocalIntersections and isValidDiagonal's main checks (:1219-1220) keep <= 0, which #15739 introduced there without a test needing it; neither the repro nor TestTessellator depends on that choice, and in the sweep it only changes polygons that are already wrong on main (see the next option).
• Cost not benchmarked: the ccw branch now computes both area terms before testing them, where stock stops after the first term that passes (||, :1265-1266). Composes with the fix sketch of the sibling bug LFV-757 (which also edits isLocallyInside): with both, both repros and TestTessellator pass.

What the checks validated

• Gradle in a clean scratch worktree at a9779ef3c193 (removed afterwards): stock fails the repro 2 of 3 and the new TestTessellator test (1 of 78), seeds DEADBEEF (assertions on) and 1234ABCD (off). With the fix: org.apache.lucene.geo.* and org.apache.lucene.document.*, 77 classes, 695 tests, 33 skipped, 0 failures on both seeds; -Ptests.nightly=true geo and document.*Shape*, 45 classes, 392 tests, 0 failures; checkGoogleJavaFormat, ecjLintMain/Test, forbiddenApisMain/Test pass.
• Standalone, shadowed onto the stock jars: repro 3 of 3, the reproducer's own test 3 of 3 (assertions off, seed 0C0FFEE1), upstream TestTessellator 70 of 70 (7 nightly or disabled tests skipped); the repro, the tilted variant and the strict path give the exact area for XY and LatLon; all 972 orderings accepted with the exact area.
• Translation validation (9,000 XY lattice polygons, 3 seeds x 3,000; seed 0x249 again in strict mode and, for its first 1,500 polygons, as LatLon), polygon by polygon: identical to stock except poly#389 and poly#2114, which become exact; the same with LFV-210's fix applied.
• Backport: applies unchanged to 10.5.2's Tessellator.java; on the 10.5.2 jars the repro passes 3 of 3 (assertions on and off; stock 10.5.2 fails 2 of 3) and TestTessellator 70 of 70.

The other way round: isLocallyInside is strict again everywhere (the 10.4.0 behaviour), and only fetchHoleBridge (:584) asks for <= 0, matching #15739's own description ("choosing an invalid bridge"): the two-argument form passes false, and the bridge candidate check passes true. +20/-3 lines.

  private static boolean isLocallyInside(final Node a, final Node b) {
    return isLocallyInside(a, b, false);
  }
  ...
        if ((tan < tanMin || (tan == tanMin && p.getX() > connection.getX()))
            && isLocallyInside(p, holeNode, true)) {

Trade-offs

• Closest to the long-tested pre-10.5 code, and scoped to what #15739 was about.
• Changes outcomes beyond this bug: in the sweep, 36 cases that main indexes with wrong triangles (the LFV-210 wrong-bridge family) are rejected instead (9-12 per 3,000 XY, 4 of 1,500 LatLon runs; 32 distinct polygons, since the 4 LatLon ones repeat seed 0x249's XY polygons); with LFV-210's fix applied, 1 (poly#1528). No polygon goes from correct to wrong, but documents that index today (wrongly) would fail to index.

What the checks validated

• Gradle (same scratch worktree): org.apache.lucene.geo.* and org.apache.lucene.document.* with the regression test, 77 classes, 695 tests, 33 skipped, 0 failures, seed DEADBEEF; checkGoogleJavaFormat passes.
• Standalone: repro 3 of 3, the reproducer's test 3 of 3, TestTessellator 70 of 70, 972 of 972 orderings exact; sweep as above (no polygon from correct to wrong; poly#389 and poly#2114 fixed).

Narrowest: keep <= 0 unless a and b are the same point.

        || isLocallyInside(a.previous, b, isVertexEquals(a, b) == false) == false
        || isLocallyInside(b.next, a, isVertexEquals(a, b) == false) == false

Trade-offs

Special-cases the observed trigger rather than the comparison; checked standalone only (not through gradle).

What the checks validated

Standalone: repro 3 of 3, TestTessellator 70 of 70, 972 of 972 orderings exact; the four non-strict sweep families give the same per-polygon results as the recommended option (stock and with LFV-210's fix); no strict-mode sweep run.

Fixes this polygon, but re-breaks the case #15739 fixed.

Trade-offs

• TestTessellator.testComplexPolygon64 (#15731) fails with Polygon self-intersection.
• In the sweep, 11 cases that main tessellates exactly fail: 10 distinct valid polygons, 9 rejected and 1 with wrong triangles (poly#373 fails both as XY and as LatLon).

What the checks validated

Run by the finder, the independent reproducer and this doc's call-site matrix (70 tests, 1 failure); sweep per polygon.

Method: translation validation (semi-formal): the stock Tessellator's output on generated inputs is checked against an exact oracle.

• A harness generated JTS-valid polygons with 0-4 holes on a 13 x 13 lattice (3 seeds x 3,000 XY polygons; one seed also with checkSelfIntersections=true and, for its first 1,500 polygons, as lat/lon), many of them with holes touching the shell or each other at a vertex. For each it checked: no rejection; every triangle non-degenerate and inside the polygon; triangles pairwise interior-disjoint (both with JTS); total area exactly equal (doubled integer areas); edge flags equal to "this edge lies on a ring".
• On stock main most failures belong to already known Tessellator bugs. With their fixes and two sibling candidates' fixes applied, 8 rejections remained: 5 with a hole vertex in the middle of another ring's edge (filed with the known LFV-210 family) and 3 with only vertex touches. Two of those (poly#389, poly#2114) pass with #15739's comparison reverted; the third (poly#2529) does not, so it has another cause, not analysed here.
• Shadowing the versions of Tessellator.java before and after #15739 onto the main jars (an A/B of the two adjacent file versions, not a git bisect) pinned it to #15739; reverting its two hunks separately showed that the comparison change causes it. Dropping holes from poly#2114 gave the three-hole repro.
• This doc's work then localised the call site (16 combinations) and traced the zero-length cut.