Tessellator flags a hole bridge that runs along an outer edge as internal, so LatLonShape and XYShape CONTAINS queries match boxes that stick out of a polygon whose two holes touch that edge

LatLonShape and XYShape index a polygon as triangles and store, for each triangle edge, a flag that says whether the edge lies on the polygon's boundary. CONTAINS queries rely on it: crossing a flagged edge means the query leaves the shape, crossing only unflagged edges means it stays inside. Before ear clipping, the Tessellator joins each hole to the outer ring with a bridge, and Tessellator.eliminateHole flags the bridge as a boundary edge only when one of four isPointInLine checks finds it on a ring edge next to one of its two ends (Tessellator.java:392-397). When two holes touch the same straight outer edge and the second hole's bridge runs along that edge (here because each hole touches it at its leftmost vertex), the bridge lies inside a long ring edge that is next to neither of its ends, so it is flagged internal. For the triangle (0,0) (7,12) (12,0) with holes (2,0) (5,1) (3,3) and (5,0) (8,1) (6,3), the piece (2,0)-(5,0) of the bottom edge is indexed as internal, and CONTAINS for the box x [3,4], y [-0.5,0.3], which sticks out below the polygon, matches; it still matches with the box stretched to y = -80. INTERSECTS and boxes inside the polygon are right, and no error is raised. The flag has been wrong since the flags were added (LUCENE-8620, 8.3.0) and visible since CONTAINS shipped in 8.4.0; every release executed through 10.5.2 and main is affected, and 10.6.0 has the same code (by reading). Adding the whole-ring scan isEdgeFromPolygon, which ear clipping already uses for its diagonals, to the bridge's flag fixes it: the repro passes, and 45 geo and shape suites (393 test cases, 367 run, 26 skipped as nightly-only or similar) pass with assertions on and off.

• Tessellation triangles and edge flags. LatLonShape.createIndexableFields and XYShape.createIndexableFields call Tessellator.tessellate (LatLonShape.java:85-114, XYShape.java:83-112) and index one ShapeField.Triangle per triangle, with three flags (ShapeField.java:80-92). Tessellator.Triangle.isEdgefromPolygon is documented as "get if edge is shared with the polygon for the given edge" (Tessellator.java:1723-1724).
• CONTAINS. Per triangle, the query is NOTWITHIN when it crosses a flagged edge and CANDIDATE when it crosses only unflagged edges (Component2D.java:101-115; LatLon boxes SpatialQuery.java:947-1001, XY boxes Rectangle2D.java:180); a document matches when some triangle is CANDIDATE and none is NOTWITHIN (SpatialQuery.java:591-650 records both; :376 drops the NOTWITHIN documents with result.andNot(excluded)). Only the queries' contains() functions read the flags.
• Hole bridge. Holes are processed left to right by their leftmost vertex (Tessellator.java:309-325). fetchHoleBridge casts a ray to the left from that vertex and picks a ring vertex to connect to (:536-592); splitPolygon links the hole into the ring through that bridge and stores the bridge's flag on both copies (:1175-1197).

1. createDoublyLinkedList ends with filterPoints (:243), which drops collinear vertices whose two edges have the same flag (:1424-1441). The outer ring reaches hole elimination as (0,0) (12,0) (7,12): the bottom edge is one ring edge, (0,0)-(12,0), even when the caller listed (2,0) and (5,0) as vertices.
2. Hole A (leftmost (2,0)) is bridged to (0,0). That bridge lies on the bottom edge and shares the end (0,0) with it, so it is flagged as boundary. The ring is now (2,0) (3,3) (5,1) (2,0) (0,0) (12,0) (7,12) (0,0): the edge (0,0)-(12,0) is still one ring edge, with both touch points in its interior.
3. Hole B (leftmost (5,0)): the ray to the left hits hole A's edge (5,1)-(2,0) at its end, so the bridge is (5,0)-(2,0), exactly along the bottom edge. eliminateHole (:392-397, under the comment "compute if the bridge overlaps with a polygon edge") asks four questions: is (5,0) on (2,0)-(0,0) or on (2,0)-(5,1), the ring edges at the bridge end? Is (2,0) on one of hole B's two edges at (5,0)? All four are no, so fromPolygon is false.
4. Ear clipping copies the flag into the triangle (:650-656): (5,1) (2,0) (5,0) is stored with its edge (2,0)-(5,0) unflagged, and the box that leaves through it is a CANDIDATE in that triangle and touches no other triangle, so the document matches.

The whole-ring scan that would have found (0,0)-(12,0) exists: isEdgeFromPolygon (:1067-1083), used by ear clipping for its own diagonals (:654). The commit that added the flags introduced both and used the scan for every diagonal except the bridge.

INTERSECTS is 1 for every box. With the fix, every wrong 1 becomes 0 and the controls are unchanged. The credibility audit found the same false positive for XY polygon, line and circle CONTAINS queries, and for three other outer rings (a rectangle, a pentagon, a wider triangle) with the same two holes.

• Who. Applications that index polygons with holes through LatLonShape.createIndexableFields or XYShape.createIndexableFields (the default path, either checkSelfIntersections setting, default IndexWriterConfig and codec) and query them with QueryRelation.CONTAINS.
• Trigger. Two holes that each touch the same straight outer edge at one point (as vertices of both rings or in the interior of the outer edge), in a layout where the later hole's bridge runs along that edge, plus a CONTAINS query that leaves the polygon through the piece of that edge between the touch points. Every outer-ring start vertex and both hole orders fail. It is geometry-sensitive: the second hole's bridge must run along the edge, which needs that hole's leftmost vertex to be its touch point (read from the mechanism). An independent reviewer's rectangle whose holes touch the bottom edge with a vertex that is not their leftmost one did not trigger it; the audit's rectangle with these two holes did.
• How often. Not measured on real data. Touching-hole layouts are supported input and have come up in upstream bug reports (upstream fixed tessellation failures for them, for example #15205, #15554, #15695 and #15731). In the finder's random lattice polygons, built so that about half of the holes touch something, about 1-2% of polygon/mode pairs hit this fix site (a generator rate, not a real-data rate). The documented search found no prior report of the symptom.
• Effect. Silent false positives only, possibly large (a box 99.6% outside matched). No exception. INTERSECTS, WITHIN and DISJOINT do not read the flags; boxes inside the polygon and single-hole polygons are right.
• Default vs opt-in. Indexing is the default path; CONTAINS is a relation the caller must choose explicitly; how often it is used was not measured. Shape doc-values queries reject CONTAINS (BaseShapeDocValuesQuery.java:47-49).
• Persistence. The flag is computed at index time and stored with each triangle, so shapes indexed with an affected version keep it until reindexed (read, not executed for this bug).
• Not executed. LatLon polygon, line and circle CONTAINS queries (the XY ones were); polygons above 80 vertices, which use Morton-ordered ear clipping after the same bridge code; other JDKs or CPUs than JDK 25 on aarch64.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: CONTAINS hits for a box that leaves the polygon 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.apache.lucene.document.TestHolesTouchingSameOuterEdgeContains.testBoxCrossingOuterEdgeIsNotContained(TestHolesTouchingSameOuterEdgeContains.java:51)

• The contract is the flag. Tessellator.Triangle.isEdgefromPolygon: "get if edge is shared with the polygon for the given edge" (Tessellator.java:1723-1724). The comment on the expression: "compute if the bridge overlaps with a polygon edge" (:392). 8.3.0 CHANGES: "Tessellator labels the edges of the generated triangles whether they belong to the original polygon" (lucene/CHANGES.txt:6219-6220).
• CONTAINS is built on it. Component2D.WithinRelation: CANDIDATE when the query "intersects only edges that do not belong to the original shape", NOTWITHIN when it "intersects an edge that does belong to the original shape" (Component2D.java:101-115); 8.4.0 CHANGES: "LUCENE-8620: Add CONTAINS support for LatLonShape and XYShape" (lucene/CHANGES.txt:6049). The newBoxQuery javadoc says "intersect a defined bounding box" for every relation (LatLonShape.java:238, XYShape.java:204), so the CONTAINS meaning comes from the relation name, the CHANGES entry and the WithinRelation javadoc.
• Upstream's test asserts exact flags. TestTessellator.checkPolygon -> checkTriangleEdgesFromPolygon (TestTessellator.java:1011-1024, 1047-1120) asserts that every triangle edge's flag equals "lies on a ring segment". The intended-behaviour devil's advocate ran it verbatim on 32 combinations (ring starts, hole orders, both checkSelfIntersections values): 32 mismatches on main and on 9.12.2, 0 with the fix. A 7-line TestTessellator method with this polygon fails on main.
• Upstream treats such errors as bugs. #12020 / #12022 fixed a CONTAINS false positive from a lost boundary flag at another site (ShapeField.resolveTriangleType, 2022); LUCENE-9251 fixed conflicting flags in filterPoints; #15739 (2026) widened this expression from 2 to 4 adjacent-edge checks for another touching-hole layout.
• Legal input. Clockwise outer ring, counter-clockwise holes (Polygon.java:31-32), disjoint holes, each touching the shell at one point (Tessellator.java:47), small integer coordinates; JTS 1.20 IsValidOp reports it valid, with and without (2,0) and (5,0) listed as outer-ring vertices. Listing them removes any doubt about "touch at one vertex", and that variant fails the same way. The 0.5 overhang is far above the coordinate quantization (below 1e-7 degrees). The wrong answer comes through the public XYShape/LatLonShape calls.

The strongest "works as designed" case (an independent reviewer from another model family, the devil's advocate and the adjudication all built it): the four adjacent-edge checks are a deliberate constant-time shortcut, Tessellator is @lucene.internal (Tessellator.java:72), and CONTAINS is thinly documented.

Why it fails: the public LatLonShape/XYShape entry points carry no such tag, and nothing documents CONTAINS as approximate beyond quantization; the commit that added the flags used the whole-ring scan for every other diagonal; upstream's own oracle asserts exact flags; and the fix costs at most one extra ring scan per bridged hole, which fetchHoleBridge already pays. The reviewer rated the argument weak, and the devil's advocate found no intended, documentation, misuse or reachability argument that survives (both from their review records, which rest on executed probes).

Option 1 was applied in a scratch worktree at a9779ef3c193 and run through gradle; option 2 was not run.

Wider effect (option 1). In the finder's lattice sweeps, on top of the registered Tessellator fixes, it cut the polygon/mode pairs whose only error is a missing flag from 54, 66 and 70 to 2, 0 and 0 (6x6, 8x8 and 13x13 lattices) and added no failure; on 8x8 two pairs of one polygon, where a degenerate triangle also misses a flag, remain. So it covers more layouts than the repro; how many of those gave a wrong query answer was not measured.

Not sufficient: keeping the touch vertices on the outer ring. A full-ring filterPoints variant (another unit's experiment, not a registered fix) happens to fix this polygon, because the adjacent-edge checks then see the outer edge, but the same sweeps still show 26, 12 and 4 pure missing-flag pairs with it (13x13, 8x8, 6x6), and 0 with option 1 added (the two composite 8x8 pairs above remain).

Coupling. Other hunt rows fix other Tessellator sites (LFV-210, LFV-755, LFV-757, LFV-762, LFV-795, LFV-796; none owns this expression); LFV-755 comes from #15739, the commit that also widened this expression. The repro still fails with the LFV-210, LFV-757 and LFV-762 fixes applied, and option 1 passed the 123 upstream geo-shape tests together with the LFV-795 and LFV-796 fix sketches.

Workaround until a fix (not executed): an application that needs exact answers can re-check CONTAINS hits against the source geometry.

In Tessellator.eliminateHole (Tessellator.java:393-397) add || isEdgeFromPolygon(bridge, holeNode, false) as a fifth term. isEdgeFromPolygon walks the ring and returns the flag of the ring edge that contains both ends of the bridge (:1067-1083), so it adds true only when the bridge lies on a ring edge that is itself flagged as boundary; for a bridge along an internal edge the added term returns false (the four existing terms are unchanged). isMorton = false is right, because holes are eliminated before the ring is sorted by Morton code (:115-133). The finder wrote this line, and the independent reproducer reports writing the same line itself. Add the repro's tests (or the TestTessellator method) as regression tests, and a CHANGES line saying affected shapes must be reindexed.

           isPointInLine(bridge, bridge.next, holeNode)
               || isPointInLine(bridge, bridge.previous, holeNode)
               || isPointInLine(holeNode, holeNode.next, bridge)
-              || isPointInLine(holeNode, holeNode.previous, bridge);
+              || isPointInLine(holeNode, holeNode.previous, bridge)
+              // the bridge may also lie inside a longer ring edge that is not next to either end
+              || isEdgeFromPolygon(bridge, holeNode, false);

Trade-offs

• Cost: one extra ring scan per bridged hole, only when the four cheap checks fail; fetchHoleBridge already walks the ring for every hole (twice on its normal path), so the work per hole stays linear in the ring size (read, not benchmarked).
• Existing indexes: the flag is stored at index time, so the fix helps only shapes indexed after it.
• Scope: it fixes the bridge flag only; ear clipping and split diagonals already use the scan.

What the checks validated

Gradle, scratch worktree at a9779ef3c193: the 4 repro tests pass; org.apache.lucene.geo.*, org.apache.lucene.document.*Shape* and the new class (45 suites, 393 test cases: 26 skipped (24 nightly-only, 1 awaits-fix, 1 other), 367 run; including TestTessellator (78 cases, 7 skipped, many through the exact-flag checkPolygon), TestLatLonShape, TestXYShape and the polygon, multi-polygon, line, point and doc-values shape-query suites) pass with assertions on (seed DEADBEEF) and off (5EED0794); :lucene:core:check -x test (format, ecjLint, forbiddenApis) passes. The full :lucene:core test suite was not run. The standalone runner passes the class with the fix shadowed (assertions on and off), and every outside box of the probe gives 0. Earlier stages: the same line cures 8.3.0, 8.4.0, 9.12.3, 10.5.2 and main in the version-independent check.

Replace the four isPointInLine terms with isEdgeFromPolygon(bridge, holeNode, false). Simpler and uniform with the other diagonals. Not run (no check executed this option).

Trade-offs

It changes behaviour beyond this bug: when an adjacent edge that contains the hole vertex is itself an internal bridge, the current terms say true and the scan returns that edge's false (read). That case would need its own analysis and tests.

Method: bounded translation validation on the real jar (semi-formal tier).

• The finder tessellated JTS-valid polygons with 0 to 4 holes on 6x6, 8x8 and 13x13 XY lattices and on grid-exact LatLon lattices, with every outer-ring start, every hole order (sampled for polygons with 4 holes), the 8 symmetric images and both checkSelfIntersections modes, about half of the holes touching something: about 21 million tessellations, compared with exact oracles, among them "Triangle.isEdgefromPolygon(k) is true exactly when edge k lies on a ring".
• Every registered Tessellator fix was switched in as a patched class; the missing-flag rows that survived matched a lead an earlier unit had left unexecuted. A debug copy of the Tessellator traced it to the bridge expression, and the finder turned it into an end-to-end CONTAINS test through the public API and shrank it to the 3-ring lattice polygon (2026-10-27).
• Then an independent reproducer, executing reviews by a model from another family (OpenAI GPT-5.6, refute and intended lenses), an intended-behaviour devil's advocate, an adjudication and a credibility audit.