Tessellator can bridge a later hole across an earlier hole that touches the outer ring, so a valid polygon is indexed covering its own hole

The Tessellator joins each hole to the outer ring with a bridge, holes sorted left to right, before it clips ears. When a hole touches the outer ring at exactly one vertex V (allowed: "Holes may only touch at one vertex"), the merge at V leaves four nodes with V's coordinates in the ring, in two adjacent pairs; since #15211 they are filtered only once, after all holes. A later hole whose left-most vertex lies at exactly V's y first gets the far end of the outer edge that ends at V as its bridge candidate; the copies of V are the right candidates, but each has a same-coordinate neighbour, so isLocallyInside sees a zero area and rejects all of them. The bridge then crosses the earlier hole. On the default indexing path the triangles cover that hole and the document matches queries inside it, silently; with checkSelfIntersections=true the valid polygon is rejected. 9.12.2 and 10.3.x tessellate the repro polygon exactly; 9.12.3, 10.4.0 to 10.5.2, 10.6.0 (by reading) and main do not.

• Tessellation: LatLonShape and XYShape index a polygon as triangles (Tessellator.tessellate); a point query matches the document when a triangle contains the point.
• Bridge: to turn a polygon with holes into one ring, eliminateHoles joins each hole to the outer ring with a two-way cut from the hole's left-most vertex to a visible vertex of the ring, holes sorted by x (Tessellator.java:307-366, sort at :309-323).
• Copies: splitPolygon (:1175-1199) links two vertices and adds a copy of each, so the ring can run along both sides of the cut. A cut of zero length (a hole merged at a vertex it shares with the ring) leaves copies with the same coordinates next to each other.

1. Hole A (left-most x = 2) goes first. Its left-most vertex is the shared vertex V = (2,5), so maybeMergeHoleWithSharedVertices (:411-472) splits the ring there (:455-457). The ring becomes (0,0) (10,0) (10,10) (0,10) V V (4,8) (5,6) V V (debug trace).
2. Nothing removes the copies before hole B. #15211 removed the filterPoints call after each split; duplicates are filtered once after all holes (:364-365). The per-hole filterPoints(result, result.next) (:347) removes nothing here: it tests only result, (0,0), against its two neighbours and stops (:1405-1453).
3. Hole B's ray goes left from (6,5) along y = 5 (fetchHoleBridge, :536-592). The first edge it meets in ring order is (0,10) -> V, and the candidate is that edge's end with the smaller x (:555): (0,10). The edges (5,6) -> V and V -> (0,0) hit at the same x and do not replace it (:549).
4. The search for a better vertex in the triangle (6,5) (0,10) (2,5) (:568-590) finds the four copies of V at angle 0, the right answer, but requires isLocallyInside(p, holeNode) (:583-584). That test starts with area(a.previous, a, a.next) and returns false if (area == 0) (:1251-1257). Each copy has its twin as a neighbour, so all four fail.
5. The bridge (6,5)-(0,10) is kept (:388-399). It crosses hole A's edge (2,5)-(4,8) at (24/7, 50/7). Ear clipping of that ring produces 11 triangles that also cover hole A. With checkSelfIntersections=true, checkIntersection runs on the ring after hole elimination (:178-199) and reports the crossing point.

On 10.3.0 the copies were merged after each split, each V kept its real neighbours, and the copy between (5,6) and (0,0) passed the test, giving the bridge (6,5)-(2,5) along y = 5.

• Who is hit. Applications on 9.12.3, 10.4.0 to 10.5.2, 10.6.0 (by reading) or main that index polygons with holes through LatLonShape or XYShape: createIndexableFields and createDocValueField (both executed). No custom codec or IndexWriterConfig: the JUnit runs under the test framework's randomized codec, and the diagram probe, a plain main, gets the same counts with Lucene's default codec; the defect is in tessellation, before any codec runs. No scale needed.
• Default vs opt-in. The two-argument methods pass checkSelfIntersections=false (XYShape.java:83-90, LatLonShape.java:85-92), so the wrong triangles are indexed silently. Callers that pass true get an IllegalArgumentException for a valid polygon.
• Effect. The document matches queries inside its own hole: executed for point INTERSECTS and DISJOINT and a doc-values box; WITHIN and CONTAINS evaluate the same triangles (by reading). Here all of hole A and a sliver of hole B are covered. Other documents and queries are not affected: queries do not tessellate.
• What it takes. A hole touching the outer ring at exactly one vertex V, and a later hole whose left-most vertex has exactly V's encoded y, with no other vertex in the bridge search triangle that would be picked first. Moving either hole slightly makes the tessellation exact. One-vertex touches occur in real data (#15554, #15695 and #15731 reported valid polygons with touching holes); exact alignment is rare in arbitrary data and more likely in grid-snapped data. No public report of this symptom was found (see Prior reports), 13 months after 9.12.3.
• The symptom varies. For other shapes with the same trigger the default path rejects the polygon (Unable to Tessellate shape) instead of covering a hole.
• Wider sweep. In the finder's sweep of 3,000 valid lattice polygons with seven known geo fixes applied, 6 valid polygons were still rejected; the recommended fix removes 3 of those rejections (the other 3 have other causes). Two become exact; the third then shows a missing edge flag instead, so the count of wrong results drops from 8 to 6.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<0> but was:<1>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.junit.Assert.assertEquals(Assert.java:633)
       org.apache.lucene.document.TestTessellatorSharedVertexLaterHoleBridge.testPointInsideHoleDoesNotIntersect(TestTessellatorSharedVertexLaterHoleBridge.java:49)

• 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". The repro meets every condition, and JTS IsValidOp reports it valid. (The XYPolygon/Polygon constructors check only the ring format, not topology: XYPolygon.java:48-90.)
• Public entry points (LatLonShape.java:84, :94-97): "create indexable fields for polygon geometry"; "If checkSelfIntersections is set to true, the validity of the provided polygon is checked". The check rejects Lucene's own bridge, not the input.
• Tests: TestTessellator.checkPolygon asserts that the tessellation's area equals the polygon's (TestTessellator.java:1016-1023); testComplexPolygon60 (:916-930) does so with delta 0.0 for twenty holes that touch the shell at four vertices (dented (1 5) and (5 1), convex (11 5) and (5 11)): exact area is required for holes on shell vertices, though that test is more complex than the repro and has no free hole level with a shared vertex.
• CHANGES: GITHUB#13841 "Improve Tessellatorlogic when two holes share the same vertex with the polygon which was failing in valid polygons" (lucene/CHANGES.txt:2136-2137); #15205, #15554, #15695 and #15731 are bug-fix entries for the same family (:1467-1470, :1488, :1494, :1174).
• History: #15211's CHANGES text moves co-planar removal to "once after all holes are removed instead of doing it for each removed hole"; its PR has one LGTM review and does not discuss later holes. The area == 0 rule in isLocallyInside dates from LUCENE-8775 (2019); in that version every split was still followed by filterPoints(node, node.next), so split copies were merged right away (by reading).
• Reference algorithm: current mapbox/earcut still heals the points around both new slit edges right after each hole is joined (eliminateHole, with one narrow exception), and its locallyInside has no zero-area rule. Its source comment there is about the opposite risk, filtering too much ("leave bridge2 alone: dropping it as collinear would leave bridge lying on the healed edge, where a later hole could bridge into it from outside its sector", added for earcut #219), so it is no argument for per-hole filtering.

The strongest case for "intended": the Tessellator is @lucene.internal (Tessellator.java:72) and a port of earcut, whose README says it "doesn't guarantee correctness of triangulation"; #15211 keeps the copies on purpose and #15700 relies on them; the zero-area rule is deliberate; and the default path skips validation.

Why it fails: earcut's disclaimer covers input that breaks its assumptions ("The input is assumed to be a valid polygon"), and this input is valid by JTS and by Lucene's own javadoc; the zero-length edges come from Lucene's splitPolygon, not from the input. The public createIndexableFields reaches the code with the default flag, and the strict path is wrong too: it rejects a valid polygon. Keeping copies is a design choice; covering a hole is not its intended outcome. The cross-model reviewer rated the intended-behaviour argument weak in all three of its reviews and in its fact check; the devil's-advocate checker found none of its eight 'intended' arguments holds; the other checkers gave no rating.

One fix was validated with gradle in a scratch worktree, a narrower variant with the standalone runner; two filtering variants were tried and break existing tests. The fix does not cover three sibling Tessellator findings (LFV-755, LFV-762, LFV-795), which still fail with it alone and need their own changes.

Tessellator.java only. The copies stay in the ring, so the #15211 and #15700 logic that relies on them is untouched; only the corner test sees each copy with the neighbours of the vertex it stands for. The old body becomes isLocallyInside(aprev, a, anext, b).

private static boolean isLocallyInside(final Node a, final Node b) {
  // skip copies of a (zero-length edges left by a shared-vertex hole merge) to find the
  // vertex's real neighbours
  Node prev = a.previous;
  while (prev != a && isVertexEquals(prev, a)) {
    prev = prev.previous;
  }
  Node next = a.next;
  while (next != a && isVertexEquals(next, a)) {
    next = next.next;
  }
  return isLocallyInside(prev, a, next, b);
}

Trade-offs

• isLocallyInside is also used by ear clipping (:875-876, isValidDiagonal :1205-1225). After the final filterPoints(outerNode, null) adjacent copies are normally gone, so ear clipping should be unchanged, but that rests on the test suites, not on a proof.
• The loops stop at a, so they terminate; each is linear in the number of consecutive same-coordinate neighbours, so a vertex without copies costs one extra comparison per side.
• In the repro both copies of the pair between (5,6) and (0,0) then pass, and the tie rule of fetchHoleBridge (:583) keeps the first one met; the effect beyond this case rests on the test suites.
• Backport: the same wrapper applies to 10.5.2 and 9.12.3 (9.x keeps its strict < 0 comparisons); with it the repro passes on both release jars. Add a CHANGES entry under Bug Fixes.

What the checks validated

• Scratch worktree at a9779ef3c193, gradle. Stock: the repro fails 5 of 5; TestTessellator with testComplexPolygon66 added fails 1 of 78 (two seeds).
• With the fix: org.apache.lucene.geo.* and org.apache.lucene.document.*, 77 classes, 697 tests (33 skipped), 0 failures with seed DEADBEEF and assertions on, and with seed 1234ABCD and assertions off; -Ptests.nightly=true for geo.* and document.*Shape*, 393 tests, 0 failures; checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain and forbiddenApisTest pass. The worktree was removed afterwards.
• Shadowed onto stock jars: the repro passes 5 of 5 with assertions on and off; also on the 9.12.3 and 10.5.2 jars with the change applied to their own sources. Earlier checks with the same change: an independent 7-test repro and TestTessellator 70 of 70 on two seeds.

Leave isLocallyInside as is and call a copy-skipping variant only at fetchHoleBridge's candidate check (:584).

Trade-offs

Leaves ear clipping untouched by construction. Validated less: the repro (5 of 5) and TestTessellator (71 run, 0 failed) pass with the standalone runner; not run through the wider suites.

Filter the split nodes after each hole again, as before #15211.

Trade-offs

Both forms tried pass the repro but break existing tests: filterPoints(split, split.next) after the two shared-vertex splits fails 4 of 70 TestTessellator tests (testComplexPolygon17/41/60/61, 61 being #15211's own test); merging only adjacent identical nodes after each hole fails testComplexPolygon41 and 60 (Unable to Tessellate shape). Later shared-vertex merges need the copies.

Re-filter after every hole and break equal-coordinate ties by which copy's sector contains the hole, as earcut's findHoleBridge does.

Trade-offs

A larger change; Lucene has a shared-vertex merge that earcut does not.

Go back to filtering after every split.

Trade-offs

On main and 10.4.0, undoing exactly #15211's three hunks still fails this repro, because #15657's leftmost-shared-vertex split never had a filter; filtering after every split site passes the repro but was not run through TestTessellator. A revert would also remove the code that fixed #15205 (the independent reproduction's narrower restore fails #15211's own test for it).

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 polygons that JTS calls valid, with 0 to 4 holes on a 13 x 13 integer lattice (seed 585), about half with holes touching each other or the outer ring at a vertex. For each it checked: no rejection, every triangle inside the polygon, pairwise disjoint interiors, exact doubled-area equality, and edge flags equal to "the triangle edge lies on a ring".
• With the fixes of seven registered geo bugs shadowed, 8 polygons were still wrong, 6 of them valid polygons that were rejected. Minimising them by hole subsets and tracing hole elimination with a debug copy of the Tessellator showed the copies of the shared vertex and the rejected bridge candidates.
• The mechanism was then reduced by hand to the 3-ring polygon of the repro, where the default path covers a hole without any error. With the recommended fix, 3 of the 6 rejections disappear; the other 3 have other causes.