Tessellator rejects a valid polygon whose holes touch nothing, depending on where the outer ring's vertex list starts

A valid polygon with two holes that lie strictly inside it and touch nothing is indexed or rejected by XYShape/LatLonShape.createIndexableFields depending only on which vertex its outer ring is listed from: of the four listings of the ring (4,5) (5,1) (0,0) (1,1), two give 12 triangles of exact area 9 and two throw "Unable to Tessellate shape". The first hole's bridge continues an outer edge in a straight line, so the outer vertex (1,1) appears twice in the ring, and only its copy with a straight corner faces the second hole. Tessellator.isLocallyInside returns false for every straight corner, so fetchHoleBridge cannot move the second hole's bridge to that copy when its ray found the other one first. A regression in 8.2.0 (LUCENE-8775); 8.1.1 accepts every listing.

y=5   .   .   .   .   O   .        O  outer ring, clockwise: (4,5) (5,1) (0,0) (1,1), area 10
y=4   .   .   .   .   .   .        B  hole B, counter-clockwise: (2,2) (4,3) (3,3)
y=3   .   .   .   B   B   .        A  hole A, counter-clockwise: (3,2) (3,1) (4,1)
y=2   .   .   B   A   .   .
y=1   .   O   .   A   A   O        expected area 10 - 0.5 - 0.5 = 9
y=0   O   .   .   .   .   .
     x=0 x=1 x=2 x=3 x=4 x=5

The five polygon entry points that were run all fail the same way for the listing from (5,1): XYShape.createIndexableFields with either checkSelfIntersections value, XYShape.createDocValueField, LatLonShape.createIndexableFields and LatLonShape.createDocValueField (lat = y, lon = x); the checkSelfIntersections overloads not run make the same Tessellator.tessellate call (XYShape.java:100,112, LatLonShape.java:102,114). For the accepted listings, a point inside each hole does not match an INTERSECTS point query and a point in the polygon does.

1. Holes are joined one at a time, sorted by their left-most vertex (:310-323, :325). For each, fetchHoleBridge (:536) picks an outer vertex and splitPolygon (:399, :1175-1199) cuts a two-way bridge, duplicating both ends (:1176-1177).
2. Hole B goes first (left-most vertex (2,2)) and is bridged to (1,1). (0,0), (1,1) and (2,2) are collinear, so the bridge continues the outer edge (0,0)-(1,1). The ring now holds two copies of (1,1): one between (4,5) and (2,2), whose corner does not contain hole A, and one between (2,2) and (0,0), whose corner is a straight angle; only that copy faces hole A.
3. Hole A's bridge vertex is (3,1) (its left-most, lowest vertex; fetchLeftmost tie-break :600-601). Step 1 of fetchHoleBridge (:542-560) casts a ray to the left and keeps the nearest hit; on a tie, the first segment in ring order from the start node (x > qx is strict, :549). The ray hits exactly (1,1), so the ring's start decides which copy it keeps (:555). Trace: listings from (4,5) and (1,1) keep the straight copy; listings from (5,1) and (0,0) keep the other one.
4. Step 2 (:568-591) replaces the step-1 vertex only with one that passes isLocallyInside(p, holeNode) (:584). isLocallyInside (:1251-1268) starts with if (area == 0) { // parallel return false; } (:1255-1257). Trace: the wrong copy is rejected (corner area -1.0, correctly), and the straight copy is rejected too (area 0.0), so the unchecked step-1 vertex stays.
5. The bridge from the wrong copy runs outside that copy's corner, ear clipping finds no ear and no valid split, and earcutLinkedList throws (:681-688).

• Who is hit: applications that index polygons with two or more holes through LatLonShape or XYShape (createIndexableFields and createDocValueField; LatLonShape.java:102,114, XYShape.java:100,112), with the default codec and IndexWriterConfig, either checkSelfIntersections value. One 10-vertex polygon is enough; no scale.
• Effect: loud. The document's polygon is refused with an IllegalArgumentException; no wrong triangles and no wrong query result were seen. The simplest caller-side workaround is to list the ring from another vertex.
• Trigger: one hole's bridge must continue an outer edge exactly (its left-most vertex on that edge's line through the bridge end), and a later hole's leftward ray must pass exactly through that bridge end; then the ring's listing decides (2 of 4 listings in the example).
• Others meet this geometry: five small integer test polygons with this kind of geometry (outer rings of 4 to 11 vertices, coordinates between -9 and 9), published independently by others against earcut (#219, #221), are rejected by Lucene main in 18 of 74 listing/hole-order configurations, by 8.2.0 in 10 and by 8.1.1 in none.
• Real-world frequency was not measured.

One test method, public API only (XYPolygon, XYShape.createIndexableFields); the seed only drives the framework's per-class settings (seeds DEADBEEF and 5EED1234 fail the same way). :lucene:core:check -x test passes with the file in place, and the test doubles as the regression test.

Left out on purpose: the other three listings (from (0,0) it fails too; from (4,5) and (1,1) it passes), LatLonShape, checkSelfIntersections=true, the doc-values entry points (all fail the same way) and the point queries of the accepted listings.

cp $REPRO/TestTessellatorDisjointHolesCollinearBridge.java $LUCENE/lucene/core/src/test/org/apache/lucene/document/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.document.TestTessellatorDisjointHolesCollinearBridge -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (same failure)

# gradle, main 5adff78bb168, -Ptests.seed=DEADBEEF (assertions on; -Ptests.asserts=false gives the same)
TestTessellatorDisjointHolesCollinearBridge > testPolygonWithDisjointHolesIsIndexed FAILED
    java.lang.IllegalArgumentException: Unable to Tessellate shape. Possible malformed shape detected.
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:72C1CB05BBA48B47]:0)
        at org.apache.lucene.geo.Tessellator.earcutLinkedList(Tessellator.java:687)
        at org.apache.lucene.geo.Tessellator.splitEarcut(Tessellator.java:936)
        at org.apache.lucene.geo.Tessellator.earcutLinkedList(Tessellator.java:683)
        at org.apache.lucene.geo.Tessellator.splitEarcut(Tessellator.java:938)
        at org.apache.lucene.geo.Tessellator.earcutLinkedList(Tessellator.java:683)
        at org.apache.lucene.geo.Tessellator.tessellate(Tessellator.java:202)
        at org.apache.lucene.geo.Tessellator.tessellate(Tessellator.java:152)
        at org.apache.lucene.document.XYShape.createIndexableFields(XYShape.java:100)
        at org.apache.lucene.document.XYShape.createIndexableFields(XYShape.java:84)
        at org.apache.lucene.document.TestTessellatorDisjointHolesCollinearBridge.testPolygonWithDisjointHolesIsIndexed(TestTessellatorDisjointHolesCollinearBridge.java:32)
:lucene:core:test (FAILURE): 1 test, 1  failure

# all four listings of the outer ring, both hole orders (Tessellator.tessellate, main)
start (4,5): 12 triangles, area 9.0      start (5,1): Unable to Tessellate shape
start (0,0): Unable to Tessellate shape  start (1,1): 12 triangles, area 9.0

# with the recommended fix: :lucene:core:test (SUCCESS): 1 test; every start 12 triangles, area 9.0

• Contract: the class javadoc's notes (Tessellator.java:40-50) list "Requires valid polygons:" with the items "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)" and "sensitive to overflow (e.g, subatomic values such as E-200 can cause unexpected behavior)"; small integer coordinates are far from the last one. Polygon.java:31-32: "Coordinates must be in clockwise order, except for holes. Holes must be in counter-clockwise order." The polygon meets all of them without using the "touch at one vertex" allowance, and no contract lets the result depend on where a ring's list starts.
• History: before LUCENE-8775 a straight corner fell into a strict half-plane test, as in earcut's locallyInside. LUCENE-8775 ("Improve tessellator to handle better cases where a hole share a vertex with the polygon", 8.2.0) added area == 0 -> false; its PR and issue discuss diagonal choice and shared vertices only.
• Precedent: comparable "Unable to Tessellate" reports on valid polygons were fixed as bugs (#15205 / #15211, #15554 / #15657, #15695 / #15700, #15731 / #15739, #13841 / #13980, ...).
• Reference behaviour: earcut, whose locallyInside has no such branch (src/earcut.js:738-742 at 934e54d8be), gives area 9 for all four listings and both hole orders; Lucene 8.1.1 accepts every listing.

The strongest case for "intended" (a devil's-advocate verifier and an independent reviewer from another model family, OpenAI GPT-5.6): the branch is deliberate code, Tessellator is @lucene.internal (:72) and only "inspired by" earcut (:34), the trigger needs exact collinearity, and the failure is loud.

Why it fails: the public XYShape and LatLonShape APIs reach the code with a valid polygon; no javadoc, commit, CHANGES entry or issue documents the limitation; the branch was added for holes that share a vertex, not to reject straight corners; the same ring is accepted when re-listed; and the release before the change handled it. All verifiers rated the "intended" argument weak.

One option was built and validated in a scratch worktree of 5adff78bb168; two simpler changes were tried earlier and are not fixes.

If the vertex found by the ray fails the corner test, walk the ring for a coincident copy that passes it. The test is a private helper, isSectorContaining(a, b): earcut's locallyInside (no area == 0 branch; strict < 0 where isLocallyInside's ccw branch uses <= 0 since #15739), with neighbouring copies of a skipped. isLocallyInside itself, used for diagonals elsewhere, is unchanged.

    // an earlier hole's bridge can leave several copies of this vertex: if the angle of the copy
    // found by the ray does not contain the hole vertex, take a copy whose angle does (step 2
    // below never picks a copy with a straight angle)
    if (isSectorContaining(connection, holeNode) == false) {
      Node q = connection.next;
      while (q != connection) {
        if (isVertexEquals(q, connection) && isSectorContaining(q, holeNode)) {
          connection = q;
          break;
        }
        q = q.next;
      }
    }

Trade-offs

• A sketch checked at one seed. The extra ring walk runs only when the ray's vertex fails the test (at most one O(n) pass per hole).
• It touches the same code as LFV-757 (the same area == 0 line, reached there through coincident copies after a shared-vertex merge); this diff leaves LFV-757's polygon failing, and maintainers may prefer one rewrite of copy selection that covers both.

What the checks validated

• Scratch worktree of 5adff78bb168, gradle, JDK 25, seed DEADBEEF (removed afterwards): the minimal test passes with assertions on and off and fails without the diff; org.apache.lucene.geo.*, document.*Shape* and document.*Polygon*, assertions on: 45 classes, 390 tests, 0 failures (26 skipped); TestTessellator with nightly tests, assertions on: 77 tests, 0 failures, 1 skipped; :lucene:core:check -x test passes.
• With the patched file applied on main: all four listings and both hole orders give 12 triangles, area 9; the five entry points run succeed; the finder's two-method test and the independent reproducer's test pass.
• Earlier, the same logic (differing only in names and comments) accepted the five earcut polygons in all 74 configurations, and in the finder's random grid runs removed every disjoint-hole rejection without adding one (not re-checked by a verifier).

Makes this repro and every disjoint-hole failure of the grid runs pass.

Trade-offs

In the finder's grid runs it adds rejections for polygons whose holes touch other rings, so it only shows where the bug is.

On main the upstream geo-shape suites still pass (123 tests, one seed).

Trade-offs

On 8.2.0 it breaks that release's own testComplexPolygon31 (a hole sharing a vertex with the outer ring, added with the branch), so the branch protects shared-vertex cases and needs a replacement.

Method: bounded translation validation (the hunt's semi-formal tier): the oracle is the polygon's exact area and acceptance, which must not change under re-listing a ring from another vertex, reordering the holes, or rotating or mirroring the grid. The polygons were drawn on 8x8 and 13x13 integer grids, so every coordinate and area is exact in double.

The failing polygons were then reduced to a public-API JUnit test, separated from the other Tessellator defects by applying their fixes (this one still fails), and checked by an independent reproducer, cross-model reviews (OpenAI GPT-5.6), a devil's-advocate verifier and an adjudication. The finder's population counts (for example 9 of 1,455 polygons on 8x8 rejected in some form) were not re-checked by a verifier.