Shape INTERSECTS misses lines and polygons that cross a query polygon between its holes, and DISJOINT returns them

LatLonShape and XYShape polygon queries test each indexed segment and triangle with Polygon2D.intersectsLine / intersectsTriangle; DISJOINT is the negation of the same test. Both methods first ask whether a vertex lies inside the polygon, with the hole-aware contains() (a vertex in a hole counts as outside), or whether an edge crosses the outer ring; only then do they consult the holes, and only to exclude a shape that lies inside one hole. That first test never looks at hole edges. So a segment or triangle whose vertices all lie in holes, and which does not reach the outer ring, is reported as not intersecting even when it crosses polygon area between the holes. With the square [0,10] x [0,10] minus holes [1,3] x [4,6] and [7,9] x [4,6], the line (2,5)-(8,5) and the box [2,8] x [4.5,5.5] are missed by INTERSECTS and returned by DISJOINT, although contains(5,5) is true. It needs a query polygon with two or more holes (or one non-convex hole); point documents are not affected. LUCENE-9273 (8.6.0, 2020), a performance refactoring, dropped the hole-first check that 8.5.2 had; every release from 8.6.0 to 10.6.0 (10.6.0 by reading) and main is affected. Testing the vertices against the outer ring only fixes it.

• Query polygon with holes: an outer ring (clockwise) and holes (counter-clockwise) inside it, as the Polygon javadoc describes (XYPolygon takes holes the same way). Points in a hole are not part of the polygon.
• Polygon2D: the query-side geometry built from such a polygon. tree holds the outer ring's edges; the holes are a separate component (Polygon2D.java:45, :369-386).
• Leaf predicate: for every indexed segment and triangle, INTERSECTS calls intersectsLine / intersectsTriangle (LatLonShapeQuery.java:107, :117; XYShapeQuery.java:89, :99). A document matches if any of its segments or triangles does. DISJOINT is the negation (SpatialQuery.java:129-130).

1. contains(x, y) is "inside the outer ring and not in a hole" (Polygon2D.java:111-117, the hole test at :114).
2. intersectsLine (:155-174) returns true only if contains(a) || contains(b) || tree.crossesLine(...) (:168-170); then it excludes a segment that one hole contains (holes.containsLine(...) == false, :171). intersectsTriangle (:176-201) does the same with three vertices, the outer ring's first vertex and tree.crossesTriangle (:191-198).
3. tree is the outer ring only, so this first test never looks at hole edges. For the line (2,5)-(8,5): contains(2,5) is false (hole A), contains(8,5) is false (hole B), and the line does not reach the outer ring, so the method returns false at :173. The hole check that would accept it is never reached.
4. relate() (:119-153), used for BKD inner nodes, checks the holes first (:127-135), so nothing is pruned early; the wrong answer comes from the leaf predicate, which is final.
5. Multi-polygon and mixed geometry queries reach the same method through ComponentTree (ComponentTree.java:112-150, :153-195). Point documents use contains() and are correct.

Query: the square [0,10] x [0,10] with holes A = [1,3] x [4,6] and B = [7,9] x [4,6]; contains(5,5) is true.

Counts: INTERSECTS 1 instead of 3, DISJOINT 2 instead of 0, for XYShape and LatLonShape (degrees), with assertions on and off. The same counts with the holed polygon inside a two-polygon query or a polygon-plus-point geometry query (run with LatLonShape; XYShape goes through the same ComponentTree code, by reading). WITHIN on the same data is correct (1, the point). Other shapes that trigger it: a line between the two arms of one U-shaped hole, through the land in the notch; a triangle with one vertex in each of three holes.

• Who is exposed. Applications that query LatLonShape or XYShape fields with a polygon that has holes, through newPolygonQuery or newGeometryQuery, with INTERSECTS or DISJOINT, on every release since 8.6.0. Default codec, IndexWriterConfig and searcher; nothing has to be enabled. Downstream products that build their shape queries on these classes with holed polygons would inherit it; no downstream product was tested.
• What it takes. (1) A query polygon with two or more holes, or one non-convex hole: one convex hole cannot trigger it, because a segment or triangle with all its vertices in a convex hole lies inside it. (2) An indexed line or polygon whose every segment or triangle has all its vertices in holes, does not reach the outer ring, and crosses land between the holes. A single vertex on land, or one edge that crosses the outer ring, makes the document match. Examples: a straight two-point line between two lakes cut out of a region; a coarse rectangle whose corners fall in two lakes.
• What the damage looks like. Silent: no exception and no log line; INTERSECTS drops the document and DISJOINT returns it. The error is geometric, not a precision effect: every vertex of the repro is at least 0.5 units (or degrees) from every ring edge, more than a million times the encoding quantum (4.19e-8 degrees of latitude, 8.38e-8 of longitude). By reading, index size does not matter: a BKD cell holding such a shape also covers part of a hole, so relate() reports CROSSES and the leaf predicate decides.
• How likely. Rare: most indexed shapes have a vertex on land or cross the outer ring, and no report was found since 2020.
• Not affected. Point documents; LatLonPoint and XYPoint polygon queries; query polygons without holes; WITHIN on this data. CONTAINS has its own, independent hole bug in the same class (Polygon2D.withinTriangle, since 8.4.0). Not run: shape doc values. Their only public query is a box query (newSlowDocValuesBoxQuery), although ShapeDocValues calls the same two predicates.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<1> but was:<0>
       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.TestXYShapeLineBetweenHoles.testLineFromHoleToHoleIntersects(TestXYShapeLineBetweenHoles.java:47)

• Contract. Component2D.java:49 and :60: "return true if this component2D intersects the provided line" (triangle). LatLonShape.java:294-297: "create a query to find all indexed geo shapes that intersect a provided polygon (or array of polygons) note: does not support dateline crossing"; XYShape.java:227-230 says the same for cartesian shapes. Polygon.java:31-32: "Coordinates must be in clockwise order, except for holes. Holes must be in counter-clockwise order." Polygon.java:33-35 adds closed rings, no self-crossing and decimal degrees. The repro follows all of these rules: closed rings, clockwise shells, counter-clockwise holes strictly inside and disjoint.
• Self-contradiction. The same object says (5,5) is inside (contains) and that the segment (2,5)-(8,5), which runs through (5,5), does not intersect.
• History. Before 8.6.0, Polygon2D.relateTriangle began with "// check any holes": a shape crossing a hole edge counted as crossing the polygon (parent 37ad0e552dc, Polygon2D.java:145-152; the step dates from LUCENE-8435, 7.5.0). LUCENE-9273 (f914e08b364, 2020-04-20, "Speed up geometry queries by specialising Component2D spatial operations") replaced it with the specialised methods and dropped the step. CHANGES lists it under Optimizations; the issue, the PR and its single review never mention holes. Commit-level builds: both parents pass, both commits fail.
• Tests. The random shape tests take their expected answer from the same predicates (BaseSpatialTestCase.java:747-797 calls intersectsLine / intersectsTriangle), and the random polygon generators build no query polygons with holes (TestPolygon2D.java:364: "currently we don't generate these"). TestLatLonShape's hole tests query indexed holed polygons with a box. No test asserts the current answer for a hole-to-hole shape, and the fix breaks no test.
• Todo left open. LUCENE-8435 (gh#9481), which added these queries, lists "add testing for arbitrary polygons with holes".

The strongest "intended" case: Component2D is @lucene.internal (Component2D.java:27) with one-line javadocs; Polygon is @lucene.experimental; LatLonShape warns that vertex values lose precision (LatLonShape.java:72); TestPolygon2D says relate(box) "can conservatively return CELL_CROSSES_QUERY" (TestPolygon2D.java:50); the random shape tests pass; and the trigger is rare.

Why it fails: the public newPolygonQuery states the contract and lists only the dateline as a limitation; @lucene.experimental is about API stability, not wrong answers; the precision warning covers about 1e-7 degrees, while every repro vertex is at least half a degree from any ring edge; "conservative" covers the inner-node relate(box) pre-filter, while the leaf predicate is final and DISJOINT is its negation; the passing tests use the code under test as their oracle and never build holed query polygons; rarity bounds the impact but does not make the answer intended; and 8.5.2 answered correctly. Verdict: a defect (adjudication: confirmed, high; the reproducer, the devil's advocate and the intended-lens review all rated the intended case weak).

Both options give the same answers on every test and probe here; by reading, their whole pre-tests accept the same shapes whenever the holes lie inside the outer ring, so they differ only in cost. Near a single hole's edge nothing changes: of nine component-level cases, seven of them around hole A, only the two hole-to-hole cases flip, from false to true, with either option (executed). One case to decide first: holes may touch at one vertex (Tessellator.java:43-48). With holes [2,4] x [2,4] and [4,6] x [4,6], the line (3,3)-(5,5), which passes from one hole into the other through the shared corner only, is reported as intersecting by both options and by 8.5.2, but not by stock 8.6.0 and later, and contains(4,4) is false (executed, component level and end to end). Keep 8.5.2's answer, or add an exclusion that knows about the union of holes (not written), and add a test for this case either way. Only query answers change, so no reindex is needed. Add the component tests to TestPolygon2D, and consider letting the random shape tests build query polygons with holes: their current oracle calls the code under test. The CONTAINS sibling (Polygon2D.withinTriangle) needs its own change in the same file.

A private shellContains(x, y) (bounding box and tree.contains) replaces contains() in the pre-tests of intersectsLine and intersectsTriangle; the existing holes.containsLine / containsTriangle check removes shapes that lie inside one hole. When the holes are strictly separated, a segment or triangle that lies wholly in holes lies in one hole; for holes that touch at a vertex, see above. Without holes, shellContains equals contains, so such polygons behave exactly as before. +13/-5 in Polygon2D.java.

/** true if the point is inside or on the outer ring, ignoring holes */
private boolean shellContains(double x, double y) {
  return Component2D.containsPoint(x, y, minX, maxX, minY, maxY) && tree.contains(x, y);
}
...
// test against the outer ring only: a segment whose end points lie in holes can still cross
// the polygon between them; the holes are excluded by the containsLine check below
if (shellContains(aX, aY)
    || shellContains(bX, bY)
    || tree.crossesLine(minX, maxX, minY, maxY, aX, aY, bX, bY, true)) {
  return holes == null || holes.containsLine(minX, maxX, minY, maxY, aX, aY, bX, bY) == false;
}
// intersectsTriangle: the same three shellContains calls

Trade-offs

• The smallest change. By reading it is slightly cheaper than today for vertices on land (it skips the per-vertex hole lookup in contains()); no benchmark was run.
• At a single hole the boundary behaviour is unchanged: a segment or triangle inside a hole that touches or runs along the hole's edge is still excluded, as on stock (executed). A segment through the shared corner of two touching holes now intersects (see above).

What the checks validated

• Scratch worktree of a9779ef3c193, gradle, JDK 25: the new tests fail 4 of 5 on stock (assertions on and off) and pass with the fix; the 50 geo and shape suites, 424 tests, 0 failures with assertions on and off; checkGoogleJavaFormat passes; the whole :lucene:core:test, 750 suites and 8,894 tests, 0 failures, three times (assertions from the seed, on, off).
• Standalone runner: 5 of 5 pass with -ea and -da; the reach probe prints 3 / 0 / 1 for all three query forms. Earlier, the independent reproducers' and reviewers' tests, TestPolygon2D (16 of 16) and TestXYPolygonShapeQueries (4 of 4) passed with the same fix.

Keep the current tests and add || (holes != null && holes.intersectsLine(...)) (and holes.intersectsTriangle(...)) to the pre-test: a shape that touches a hole but is not inside one hole must cross land. Closest in spirit to the pre-8.6 hole-first step. +7/-2.

Trade-offs

One extra hole traversal for every segment or triangle that fails the first tests (shapes inside a hole, or outside the polygon within its bounding box), so a little more work than the recommended option; no benchmark was run. Holes that touch at a vertex behave as with the recommended option (executed).

What the checks validated

Same worktree: the 50 geo and shape suites, 424 tests, 0 failures with assertions on and off; checkGoogleJavaFormat passes; the whole :lucene:core:test with assertions on, 8,894 tests, 0 failures; standalone 5 of 5 pass with -ea and -da, and the probe prints 3 / 0 / 1.

Use the 8.5.2-style hole-first relation for holed query polygons.

Trade-offs

Correct (8.5.2 is), but gives back the LUCENE-9273 speed-up for every holed query. Not run.

State that INTERSECTS and DISJOINT may be wrong for query polygons with holes.

Trade-offs

No javadoc limits holes today, 8.5.2 answered correctly, and the fix is small. Not recommended.

Method: bounded-exhaustive differential testing against an exact reference (the hunt's "semi-formal" tier). A hunt unit, "shape relations against an exact reference", 2026-10-27.

• Documents: lattice points, segments, triangles, quadrilaterals, 5-6-gons, polygons with a hole and multi-part documents; query shapes from the same lattices, on 6 x 6 grid-exact coordinates in 9 XY and LatLon families (including the dateline and the poles); all four relations, through the BKD shape index, shape doc values and the point fields.
• Reference: JTS 1.20 DE-9IM relations on the decoded coordinates, with strict and permissive boundary bands; about 1.94 billion checks.
• With the hunt's already-known geo fixes shadowed in, the only remaining INTERSECTS misses and DISJOINT false matches were documents whose vertices lie in or on a hole of the query polygon. The AI finder read the cause from Polygon2D, confirmed it at the Component2D level, and reduced it to a public-API JUnit.
• A narrower hole-boundary form had been noted earlier, untriaged, by a hunt verifier of another geo bug.
• Then independent AI tools reproduced, reviewed and judged it (see the checks).