Tessellator rejects valid polygons whose holes meet at one vertex, depending on the order of the holes

LatLonShape and XYShape index a polygon as triangles made by the Tessellator, which first joins every hole into the outer ring, left to right. A hole that touches the ring at a vertex is spliced in there, and the splice copies that vertex: in the repro, splicing hole A in at the vertex P where it touches hole C leaves four nodes at P, so the ring visits P twice, through two adjacent copies each time, and each visit bounds a different gap ("wedge") between the holes around P. Since #15700 (10.4.0), when a later hole's left-most vertex is P, maybeMergeHoleWithSharedVertices takes the first copy of P in ring order without checking that the hole lies in that copy's wedge, and an index comparison that follows the input order of the holes decides whether that copy is used. When a copy in the wrong wedge is used, the merged ring winds more than a full turn around P, ear clipping fails and createIndexableFields throws IllegalArgumentException: Unable to Tessellate shape. Possible malformed shape detected. A valid three-hole polygon is rejected in 3 of its 6 hole orders, and so is upstream's own LUCENE-9400 regression polygon (TestTessellator#testComplexPolygon41); every release checked from 9.11.1 to 10.3.2 accepts every order of both. The failure is loud: a rejected polygon yields no fields, and no wrong triangles were observed in the accepted orders.

• Hole elimination: before ear clipping, the Tessellator splices every hole into the outer ring, so that one ring is left. Holes are spliced left to right, by their left-most vertex (smallest x, then smallest y): fetchLeftmost (Tessellator.java:595-611), the sort in eliminateHoles (:310-323) and its loop (:326-363).
• Shared vertex and copies: a hole that touches the ring at a vertex is spliced in at that vertex (maybeMergeHoleWithSharedVertices, :411-472). splitPolygon (:1175-1199) inserts a copy of both nodes (new Node(a), new Node(b), :1176-1177), so the splice leaves extra copies of the shared vertex in the ring. In the repro the one splice of A at P takes P from one ring node to four: two visits of two adjacent copies.
• Wedge: around a vertex where several holes meet, the polygon's interior is split into gaps between the holes. Each visit of the ring to the vertex (one copy, or several adjacent copies) bounds one of these gaps; a hole can only be spliced in at a copy whose gap contains it.
• Node index (idx): the number given to each input vertex: the outer ring first, then each hole in the order the caller passed them (:284, :302 for Polygon; :253, :271 for XYPolygon). Copies keep the idx of the original (:1650-1651).

1. In the repro the holes are spliced in the order C (left-most (6,4)), A ((6,7)), B ((7,6)), whatever the input order.
2. C touches nothing on the outer ring: it is bridged from (6,4) to the outer vertex (0,0) (:388-399), which leaves one node at P = (7,6). A touches C at P and is spliced in there; that one splice leaves four nodes at P, so the ring visits P twice, through two adjacent copies each time. One visit bounds the gap between A and C (directions 135° to 180° from P), the other the gap from C round the right-hand side to A (270° through 0° to 63°), the only gap that can hold B (304° to 326°).
3. For B, whose left-most vertex is P, the scan keeps the first ring copy of P (if (leftmostSharedVertexConnection == null), :434-436; "For leftmost, take first match only — don't use getSharedInsideVertex.", :437) and, separately, the older angle-based choice getSharedInsideVertex (:439-446, :487-518). If leftmostSharedVertexConnection.idx >= sharedVertexConnection.idx (:455-456) it splices B at the first copy (:457), otherwise at the angle choice (:466-469). Nothing checks that B lies in the chosen copy's gap.
4. The comment above the guard assumes a higher idx means "from a hole that was already merged" (:452-454), but idx follows the input order while holes are merged in sorted order. Order ABC: first copy idx 13, in the A-C gap (wrong); angle choice idx 5, in the right gap; 13 >= 5, so B is spliced at the copy in the wrong gap; the merged ring then winds more than a full turn around P (its corners at P span 535.8° instead of 175.8°), although Lucene's self-intersection check, run on the merged ring with checkSelfIntersections=true, finds no crossing, and ear clipping throws at :687-688. Order CAB: first copy idx 5 (wrong gap), angle choice idx 10 (right gap); 5 >= 10 is false, so the angle choice is used and the result is 13 triangles with area 59.

The same orders fail through both XYShape and LatLonShape (the LatLon version of the small polygon uses x as longitude and y as latitude) with checkSelfIntersections true and false, for the LUCENE-9400 polygon with true too, with assertions on and off, and after translating the small polygon by +100 or scaling it by 0.5. Every one- and two-hole subset tessellates with the exact area. JTS 1.20.0 IsValidOp says the polygon is valid.

• Who is hit. LatLonShape.createIndexableFields and XYShape.createIndexableFields with either checkSelfIntersections setting [exec], and createDocValueField of both [read: same Tessellator.tessellate call], on 10.4.0, 10.5.0-10.5.2 and main. The exception comes before any IndexWriter call, so the codec and IndexWriterConfig play no part. 10.6.0 (branch_10_6, released 2026-10-29) and the unreleased branch_10x carry the 10.5.2 Tessellator.java [read].
• Trigger. Both executed polygons have three holes that meet at one vertex P, one of them with P as its left-most vertex, and fail in the hole orders for which the guard picks a copy in the wrong gap (3 of 6 for each). Their one- and two-hole subsets all work; other layouts were not searched, so three holes is shown to be enough, not to be required. No size is needed: 13 triangles, integer coordinates.
• Effect. The exception is thrown while the document's fields are built, before IndexWriter sees anything, so that one document cannot be indexed; a rejected polygon yields no fields at all. No wrong triangles were observed in the accepted orders (the small polygon's triangles add up to exactly its area; a total-area check, not a full containment check), and no other document, query or index state is affected.
• Order dependence. Whether a document is accepted depends on how the data source happens to order the holes. Listing the holes in another order indexed both tested polygons, but no documented rule tells an application which order works, so it can only retry other orders.
• How likely. Probably rare (a judgement): the layout is uncommon, and the documented search found no report in the 8 months since 10.4.0. Real-world frequency was not measured. It is the topology LUCENE-9400 fixed in 2020, and its test polygon now fails again in half of its hole orders.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected: indexes as with the original hole order; actual: Unable to Tessellate shape. Possible malformed shape detected.
       org.junit.Assert.fail(Assert.java:89)
       org.apache.lucene.document.TestTessellatorThreeHolesSharedVertex.testComplexPolygon41WithLastHoleFirst(TestTessellatorThreeHolesSharedVertex.java:36)

• Contract. Tessellator javadoc (Tessellator.java:40-52): "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) / sensitive to overflow (...)". The polygon meets every condition. Polygon NOTES (Polygon.java:28-39) ask for counter-clockwise, closed, non-crossing holes and say nothing about their order; XYPolygon(float[] x, float[] y, XYPolygon... holes) takes them as varargs.
• Validity. JTS 1.20.0 IsValidOp: valid; each pair of holes intersects only in POINT (7 6).
• History. CHANGES.txt:5813: "LUCENE-9400: Tessellator might build illegal polygons when several holes share the shame vertex." and LUCENE-9417 (:5815). The LUCENE-9400 issue (#10440) says "We found a new case where tessellation might fail on a valid polygon. The issue shows when a polygon has several holes sharing the same vertex". Its test, testComplexPolygon41 (TestTessellator.java:724-731), passes only because its hole order happens to be one of the 3 accepted orders.
• Precedent. Earlier "Unable to Tessellate" reports on valid polygons were fixed as bugs: #15554, #15695 (CHANGES.txt:1494, fixed by #15700 itself), #15731, #15205, #13841.
• Regression. Every release checked from 9.11.1 to 10.3.2 (10.3.0, 10.3.1 and 10.3.2 among them) accepts all 6 orders of both polygons; the change is pinned to one sub-change of #15700.

The strongest case for "intended" (built by the devil's-advocate checker; the cross-model reviews rated it moderate): #15700's comments say "the first copy from outerNode is the correct connection point for chained shared-vertex holes" (Tessellator.java:422-424) and "Prefer this connection point if it is from a hole that was already merged (higher idx)" (:452-454); Tessellator is @lucene.internal (:72); and the message says "Possible malformed shape detected".

Why it fails: the comments are design claims, not a documented limitation, and the trace refutes their premise (idx follows the input order, not the merge order). @lucene.internal does not cover the public createIndexableFields that reaches the code. The shape is not malformed: it meets the documented conditions and JTS accepts it. The #15700 review reports "a set of 400 million polygons" passing; the PR is about holes that share a left-most vertex with an outer ring vertex, and nobody in it mentions hole order, three or more holes at one vertex, or a copy in the wrong wedge. Verdict: not intended, a regression.

One fix was validated in a scratch worktree; it is a clean rewrite of the independent reproducer's selection-only variant. A plain revert of #15700 is not a fix.

In maybeMergeHoleWithSharedVertices, right after the scan, replace the first-match copy with the next copy of the same point whose wedge contains holeNode.next; if no copy passes, the first copy is kept, as on main. The new private helper isInsideVertexWedge(a, b) is isLocallyInside measured between a's nearest neighbours at a different position, skipping adjacent copies of a. The full change, with the helper, is +42 lines in Tessellator.java.

// Earlier holes merged at this vertex leave several copies of it in the ring, and different
// copies can bound different wedges around the vertex. The first copy in ring order may lie
// in a wedge that does not contain this hole: then use a copy whose wedge does.
if (leftmostSharedVertexConnection != null
    && isInsideVertexWedge(leftmostSharedVertexConnection, holeNode.next) == false) {
  Node candidate = leftmostSharedVertexConnection.next;
  while (candidate != leftmostSharedVertexConnection) {
    if (isVertexEquals(candidate, holeNode) && isInsideVertexWedge(candidate, holeNode.next)) {
      leftmostSharedVertexConnection = candidate;
      break;
    }
    candidate = candidate.next;
  }
}

Trade-offs

• Cost: the helper runs once whenever a left-most shared copy was found; the ring walk runs only when that copy fails the test.
• It keeps the idx guard, and keeps #15700's first match when that copy's wedge contains the hole's next vertex; otherwise it replaces the first match with a later copy, so "take first match only" no longer holds there. The #15695 polygon (testComplexPolygon63) still passes. The guard's dependence on input order remains; the fix makes it harmless for the tested polygons only.
• The helper tests one direction (from P to holeNode.next), not the whole hole. If no copy passes, the first copy is silently kept; degenerate wedges return false with no explicit failure path.
• The helper's reflex branch uses a strict < 0, like earcut's locallyInside; Lucene's isLocallyInside is inclusive there since #15739 (LFV-755).
• Not run with this fix: a benchmark, the 3,000-polygon sweep, earcut, the full Lucene suite, x86 or another JDK.
• The 10.x backport should apply as is: 10.5.2's Tessellator.java differs from main's only in three hunks elsewhere (two comment typo fixes, #16255; final removed on Node.getX/getY, #16063) [read], and the fix diff applies to it in a dry run; not built there.

What the checks validated

• Stock a9779ef3c193 through gradle: the repro fails 2 of 2, the regression test fails, and the finder's and verifiers' tests fail 10 of 13; the other 70 executed TestTessellator tests pass.
• With the fix, org.apache.lucene.geo.* and org.apache.lucene.document.* including all those tests: 81 classes, 707 tests, 0 failures (33 skipped), seed DEADBEEF with assertions on and seed 1234ABCD with assertions off.
• Nightly: TestTessellator (all six @Nightly tests: five fixed polygons, among them LUCENE-9417's testComplexPolygon42, and testSimpleTessellationAtNight, a 1,000,000-vertex regular polygon with two holes) and every document.*Shape* suite: 31 classes, 280 tests, 0 failures.
• checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain, forbiddenApisTest pass with the fix, the repro and the regression test (with the finder's and verifiers' test files also copied in, the format check fails on three of those files only).
• Together with the LFV-757 fix: 82 classes, 713 tests, 0 failures. Shadowed onto the stock jars: the repro passes 2 of 2.
• After a comment-only rewording (the fix's comment, one javadoc line of the repro), shadowed onto the stock jars: 17 of 17 pass (repro, checkSelfIntersections=true check, finder, the independent reproduction, the intended-behaviour check) with assertions on and off; stock fails 14 of 17.

Make isLocallyInside skip same-position neighbours for every caller (the same change as LFV-757's fix) and, during the scan, replace the first copy with a later copy of the same idx whose wedge contains the hole's next vertex.

Trade-offs

Validated by the finder on the repro (4 of 4) and 123 geo shape tests, but it changes ear and diagonal tests everywhere and only switches between copies with equal idx.

What the checks validated

Finder: repro 4 of 4; TestTessellator and six shape query and shape suites, 123 tests, two seeds.

Compare candidates by the order in which holes were merged, or drop the idx comparison and always use a wedge-checked copy.

Trade-offs

Removes the order dependence at its source, but needs checking against the #15695, #15554 and LUCENE-9400/9417 polygons.

Accepts this polygon in every order.

Trade-offs

Makes upstream's testComplexPolygon63 (the #15695 polygon) fail again: TestTessellator 69 of 70.

Method: translation validation of the stock Tessellator.tessellate against exact geometric checks (semi-formal: no model checker or prover found it).

• The harness generated 3,000 JTS-valid XY polygons with 0 to 4 holes on a 13 x 13 integer lattice (seed 585), 1,608 of them with holes touching each other or the outer ring at a vertex, and checked every result: no rejection of a valid polygon, every triangle inside the polygon, pairwise disjoint interiors, exact doubled-area equality, edge flags.
• With the fixes of the already registered Tessellator bugs shadowed in, 8 polygons still failed, 6 of them valid polygons rejected with "Unable to Tessellate shape" (#8, #139, #1499, #1919, #2013, #2379). With the fix of the sibling bug LFV-757 (found in the same unit) also shadowed in, 3 rejections remained: #8 and #2379, which have a hole touching an outer edge (filed under the LFV-210 family), and the four-hole polygon #1499 (this repro plus a small square hole touching hole A at (8,8)). With the finder's fix for this bug too, #1499 is accepted and only #8 and #2379 remain.
• Minimising it by hole subsets gave the three-hole polygon; a bisection over the Tessellator.java history pinned #15700. Independent verifiers then showed that upstream's own LUCENE-9400 polygon fails the same way when its holes are reordered.