Shape CONTAINS with a holed query polygon returns shapes whose own boundary runs through the polygon between its holes

LatLonShape and XYShape CONTAINS queries ask Polygon2D.withinTriangle about each triangle of an indexed shape in the BKD cells that cross the query: NOTWITHIN, CANDIDATE or DISJOINT. A document matches if one triangle is CANDIDATE and none is NOTWITHIN. Each triangle knows which of its edges are real boundary edges of the indexed shape; a real edge that runs through the query polygon proves that the shape does not cover the query and must give NOTWITHIN. withinTriangle gives NOTWITHIN only when a vertex lies inside the query (the hole-aware contains()) or a real edge crosses the query's outer ring; it never tests the query's holes. So a real edge that starts in one query hole, crosses land and ends in another is missed. With the query [0,10] x [0,10] minus holes [1,3] x [4,6] and [7,9] x [4,6], the square [-1,11] x [-1,11] with its own hole [2,8] x [4.5,5.5] is returned by CONTAINS although it does not cover (5,5), and although CONTAINS of [4,6] x [4,6], a part of the query, correctly leaves it out. It needs a query polygon with two or more holes, or one non-convex hole. The method was written with CONTAINS in LUCENE-8620 (8.4.0, 2019); every release from 8.4.0 to 10.6.0 (10.6.0 by reading) and main is affected. One added check for real edges that leave the holes fixes the repro; lines between holes (withinLine has the same gap) and an edge between two corners of one non-convex hole need more.

• 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; the rest of it is called land here.
• Real edge: indexed polygons are tessellated into triangles; each triangle edge carries a flag that says whether it is an edge of the original shape (real) or one added by tessellation.
• withinTriangle: the CONTAINS leaf predicate in Polygon2D (Polygon2D.java:277-342), called for each indexed triangle in a BKD leaf cell that crosses the query (LatLonShapeQuery.java:193, XYShapeQuery.java:175; a cell wholly inside the query excludes its documents without that call, SpatialQuery.java:601-604). It answers NOTWITHIN, CANDIDATE or DISJOINT; a document matches if some triangle is CANDIDATE and none is NOTWITHIN (SpatialQuery.java:619-628, :376).
• CONTAINS per geometry: Lucene does not take the union of a document's geometries; a document matches only if one of its geometries contains the query and no other geometry of the document intersects it (the comments at TestXYShape.java:266-270 and TestLatLonShape.java:1002-1006). So any real edge of any of the document's shapes that runs through the query rules the document out.

1. withinTriangle first returns NOTWITHIN if a vertex is inside the query (:298-300); contains() is hole-aware (:111-117, the hole test at :114), so a vertex in a hole does not count.
2. It then tests each real edge against tree, the query's outer ring only (:306-327), and returns NOTWITHIN if one crosses it; a tessellation edge that crosses it makes the triangle CANDIDATE.
3. It never consults holes, unlike intersectsLine, intersectsTriangle, containsLine and containsTriangle in the same class (:171, :197-198, :219, :243-244). A real edge whose ends lie in query holes and which crosses land between them is therefore never seen.
4. The documented rule is broken: NOTWITHIN means "The query shape intersects an edge that does belong to the original shape or any point of the triangle is inside the shape" (Component2D.java:108-111), and the method's own comment says the same (:303).

Query: [0,10] x [0,10] minus holes A = [1,3] x [4,6] and B = [7,9] x [4,6]; (5,5) is land. Documents: squares [-1,11] x [-1,11].

Doc 0 is stored as 8 triangles. Its hole's bottom and top edges cross land from x = 3 to x = 7, but their ends lie in the holes and they never reach the outer ring, so all 8 triangles answer CANDIDATE and none NOTWITHIN (executed per-triangle trace). With the fix, the two triangles that hold those edges answer NOTWITHIN. Results: CONTAINS [0, 1, 2] instead of [1, 2] for XYShape and LatLonShape, assertions on and off; doc 0 is also wrongly returned for one U-shaped hole (arms [1,3] x [3,6] and [7,9] x [3,6]), for a two-polygon CONTAINS query and for a polygon-plus-point geometry query, which Lucene runs as a conjunction of one-geometry CONTAINS queries (LatLonShape.java:354-370, XYShape.java:263-270).

• Who is exposed. Applications that query LatLonShape or XYShape fields with CONTAINS (newPolygonQuery, newGeometryQuery) and a query polygon that has holes, on every release since 8.4.0 (in 8.4.x the shape API lived in the sandbox module, in core since 8.5.0). Default codec, IndexWriterConfig and searcher; nothing has to be enabled. Downstream products that build CONTAINS shape queries on these classes with holed polygons would inherit it; no downstream product was tested.
• What it takes. (1) CONTAINS, which is used less than INTERSECTS. (2) A query polygon with two or more holes, or one non-convex hole: an edge with both ends in one convex hole stays inside it. (3) An indexed shape with a real edge that starts and ends in query holes and crosses land, while none of its vertices is on land and none of its real edges crosses the query's outer ring. By the independent reproducer's reasoning (not exhaustively checked), for a single indexed polygon that means its own hole. These are necessary, not sufficient: the document also needs at least one CANDIDATE triangle (a tessellation edge that crosses the outer ring, or the query's first vertex inside a triangle) and no NOTWITHIN from any other triangle or BKD cell (SpatialQuery.java:601-628).
• What the damage looks like. Silent extra hits: no exception and no log line. The error is geometric, not a precision effect: no vertex of the query's rings is closer than 0.5 units (or degrees) to an edge of the rings of docs 0-2, and no vertex of theirs to an edge of the query's (computed; only the U-hole variant's subset control touches that hole). Only query answers are wrong and this bug stores nothing wrong, so its fix needs no reindex (by reading). The fix reads the stored edge flags, though: indexes hit by the separate LFV-204 (8.8.0 on), which can store wrong flags, need that bug's fix and a reindex of the affected shapes. By reading, index size does not matter: a BKD cell that holds one of the offending triangles also holds a point outside the query or in a hole, so it is never treated as inside the query and the leaf predicate decides.
• How likely. Rare: real boundaries are dense, so a vertex usually falls on land, which is caught; it takes a long, vertex-free edge spanning the land between two holes. No report was found since 2019.
• Not affected (executed). Query polygons without holes; an indexed hole wholly inside one query hole; an indexed hole with a corner on land. Indexed holes whose edges lie on a query hole's edge give the same answers with and without the fix; those answers are not always right (a separate boundary effect, see the repro). INTERSECTS and DISJOINT have their own, independent hole bug in intersectsLine / intersectsTriangle of the same class (LFV-698). Not run: shape doc values, whose only working public queries are box queries (ShapeDocValuesField.newGeometryQuery always throws).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: doc must not CONTAIN the query 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.TestXYShapeContainsHoledQuery.testContainsChecksQueryHoleEdges(TestXYShapeContainsHoledQuery.java:58)

• Self-contradiction. On the same index, CONTAINS of the holed query returns doc 0 and CONTAINS of [4,6] x [4,6], a subset of it, does not; any shape that contains a region contains each part of it. The point query at (5,5) also leaves doc 0 out. All 16 ring-orientation combinations give the same wrong answer, so it is not a winding misuse.
• Contract. Component2D.WithinRelation.NOTWITHIN (Component2D.java:108-111, @lucene.internal): "The query shape intersects an edge that does belong to the original shape or any point of the triangle is inside the shape". The method's comment (Polygon2D.java:303): "if any of the edges intersects an the edge belongs to the shape then it cannot be within". The public ShapeField.QueryRelation.CONTAINS says only "used for CONTAINS Queries" (ShapeField.java:126-127); the newPolygonQuery javadoc says "intersect" for every relation and names the dateline as its only limitation (LatLonShape.java:294-297); XYShape.java:227-230 has the same "intersect" prose and states no limitation at all. Polygon.java:31-36: clockwise shells, counter-clockwise holes, closed rings, no self-crossing; the repro follows all of them, and its shapes pass createIndexableFields(..., true).
• Tests. The random CONTAINS validators compute the expected answer with the same method (TestLatLonPolygonShapeQueries.java:46-52 returns testWithinQuery(...) == CANDIDATE; BaseSpatialTestCase.java:800-845 calls query.withinTriangle), and the random polygon generators build no query holes (TestPolygon2D.java:364: "currently we don't generate these"). No test asserts the current answer, and the fix breaks no test.
• History. LUCENE-8620 (2019-12-11) wrote the method together with CONTAINS and tested real edges against the outer ring only from its first version; the issue (#9666) and PRs #546, #608 and #872 never discuss query holes. Later edits (LUCENE-9152, LUCENE-9273, LUCENE-9570) never touched hole handling.
• Precedent. Comparable CONTAINS false positives were fixed as bugs: LUCENE-10514 (#11550 / #809) and #12020 / #12022.

The strongest "intended" case: the public CONTAINS javadoc is one line and newPolygonQuery says "intersect"; Component2D and its WithinRelation contract are @lucene.internal; Polygon is @lucene.experimental and points to spatial-extras for more advanced operations; CONTAINS is a per-triangle approximation, and maintainers accepted rounding at shared boundaries (LUCENE-8736, #9782, open); the random tests pass; the trigger is rare.

Why it fails: the subset contradiction holds under any meaning of "contains"; @lucene.experimental is about API stability, not wrong answers; the repro is half a unit from every boundary, far from the encoding quantum of about 1e-7 degrees; the method's own comment and the internal contract state the rule that is broken; the passing tests use the method as their oracle and never build holed query polygons; nothing documents a limit on holed query polygons; rarity bounds the impact but does not make the answer intended. 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 add the same test for each real edge of the triangle, "does it touch a hole without lying inside a single hole?" (holes.intersectsLine && !holes.containsLine); after the vertex test, such an edge crosses land (or passes from one hole into another through a shared corner). They differ only in where the test sits, and since NOTWITHIN wins in either order they return the same relation for every triangle (executed: identical outputs on every test and probe). Boundary behaviour (executed, 15 component-level cases): only the three cases where a real edge leaves the holes change, from CANDIDATE to NOTWITHIN: hole A to hole B across land, and, for two holes that touch at the corner (4,4), an edge from one into the other across land and one through the shared corner only. By reading, NOTWITHIN is right for the last one too (near the corner both sides of the edge are land, and the shape lies on one side only), but only the component probe was run; whether holes that touch at a corner are valid input, and what the public query returns, were not checked, so it is behaviour for maintainers to review. Real edges inside a hole, ending on its edge or corner, or running along its edge keep their answer, and so do indexed holes equal to or sharing an edge with a query hole, end to end. Only query code changes, so this bug's fix needs no reindex; the check reads the stored edge flags, so it is only as right as those flags (LFV-204). Limits of both options (executed, probe-limits): (1) Polygon2D.withinLine (Polygon2D.java:255-274) has the same outer-ring-only test and neither option touches it: a document holding the square [-1,11] x [-1,11] plus the line (2,5)-(8,5) from hole A to hole B is still returned by CONTAINS, for XYShape and LatLonShape, although under Lucene's per-geometry CONTAINS it must not match (the same square with a line that ends on land is correctly left out); a matching check in withinLine is the obvious extension, not written or run. (2) The helper asks holes.containsLine, which, by reading, accepts a segment whose ends are on the hole's boundary when no hole edge crosses it strictly (Polygon2D.java:204-221, GeoUtils.java:217-227; the shortcut behind LFV-206); so a real edge (3,6)-(7,6) between two corners of one U-shaped hole, which crosses land, stays CANDIDATE, and XYShape still returns a square whose own hole has this edge (LatLonShape answered correctly here already on stock). It needs coordinates exactly equal to the hole's corners; with two holes the same chord is caught. (3) The missing boundary-sharing documents of the reach probe are unchanged. Add the component tests to TestPolygon2D, and consider letting the random shape tests build query polygons with holes: their CONTAINS oracle calls the method under test. The INTERSECTS sibling (LFV-698) needs its own change in the same file.

After the vertex test, return NOTWITHIN when a real edge touches the query's holes but is not inside a single hole; a private helper leavesHoles does the two hole lookups. +14 lines in Polygon2D.java (12 non-blank); the finder's fix, and an independent reproducer wrote an equivalent one. Query polygons without holes are untouched (holes == null).

if (contains(aX, aY) || contains(bX, bY) || contains(cX, cY)) {
  return WithinRelation.NOTWITHIN;
}

// an edge of the original shape that touches a hole but is not inside a single hole runs
// through the polygon (between holes, or out of a hole), so the polygon cannot be within it
if (holes != null
    && ((ab && leavesHoles(aX, aY, bX, bY))
        || (bc && leavesHoles(bX, bY, cX, cY))
        || (ca && leavesHoles(cX, cY, aX, aY)))) {
  return WithinRelation.NOTWITHIN;
}
...
/** true if the segment touches a hole and is not contained in a single hole */
private boolean leavesHoles(double aX, double aY, double bX, double bY) {
  return holes.intersectsLine(aX, aY, bX, bY) && holes.containsLine(aX, aY, bX, bY) == false;
}

Trade-offs

• Smallest reviewable change, next to the vertex test it complements.
• Like option B, it leaves withinLine and a chord between two corners of one non-convex hole uncovered (see above).
• Cost: up to one intersectsLine and one containsLine on the hole tree per real edge of each triangle that passes the vertex test, only for holed query polygons; no benchmark was run.

What the checks validated

• Scratch worktree of a9779ef3c193, gradle, JDK 25: the new tests fail 6 of 7 on stock (assertions on and off) and pass 7 of 7 with the fix; the 50 geo and shape suites, 426 tests, 0 failures with assertions on and off; checkGoogleJavaFormat passes; the whole :lucene:core:test, 750 suites and 8,896 tests, 0 failures, with assertions on and off.
• Standalone runner: 7 of 7 pass with -ea and -da; the reach probe no longer returns doc 0 and is otherwise unchanged; 12 of the 15 boundary cases keep their answer. Earlier, the independent reproducers' and reviewers' tests and 57 upstream shape and Polygon2D tests passed with the same fix.

Put the same block below the three tree.crossesLine checks, before the CANDIDATE return. +14 lines (12 non-blank). Same relation for every triangle.

Trade-offs

Skips the hole lookups for triangles whose real edge already crosses the outer ring, so slightly cheaper than the recommended option in that case and the same otherwise; not benchmarked.

What the checks validated

Same worktree: the new tests, the 50 geo and shape suites (426 tests) with assertions on and off, checkGoogleJavaFormat, and the whole :lucene:core:test (8,896 tests) with assertions on and off, 0 failures; standalone 7 of 7 pass with -ea and -da, and every probe prints exactly what the recommended option prints.

Build the crossing test from the outer ring and the holes together.

Trade-offs

Changes the data structure of every holed Polygon2D for one method. Not written or run, so this is a judgement, not a measurement; how it would treat the boundary cases is not known.

State that CONTAINS may be wrong for query polygons with holes.

Trade-offs

No javadoc limits holed query polygons today and the fix is small. Not recommended.

Method: code reading (non-formal), a hunt unit, "shape relations against an exact reference", 2026-10-27.

• The unit's bounded-exhaustive comparison of LatLonShape / XYShape relation queries with JTS DE-9IM relations had found the sibling INTERSECTS bug (intersectsLine / intersectsTriangle ignore hole edges).
• While triaging it, the finder read the other Polygon2D predicates for the same pattern. withinTriangle tests real edges against the outer ring only; an executed component-level probe and a public-API JUnit confirmed the CONTAINS false positive.
• The lattice comparison itself did not hit it: its query polygons have at most one hole, and its holed documents never had a hole edge crossing the land between two query holes.
• Then independent AI tools reproduced, reviewed and judged it (see the checks).