WITHIN shape queries with a non-convex polygon match lines and polygons that leave it between boundary vertices

XYShape and LatLonShape WITHIN queries test each indexed triangle with Polygon2D.containsLine (a segment) or Polygon2D.containsTriangle. Both return true when every vertex is contains()-ed, where a point on the polygon's boundary counts as inside, and no polygon edge crosses the shape strictly, where an edge that only ends on the shape or runs along it does not count. That implies containment only for convex polygons: on a non-convex polygon a segment or triangle can meet the boundary only at its own vertices and still pass outside between them. For the polygon (0,0) (4,0) (4,4) (2,1) (0,4), WITHIN returns the segment (0,4)-(4,4) and the triangle (0,4) (4,4) (2,1), although (2,4) and (2,3) are outside the polygon. No error is raised; the wrong region has positive area, so it is not a precision effect. XYShape hits it with exactly shared float coordinates, LatLonShape only with coordinates on its encoding grid. The current form dates from LUCENE-8736 (8.1.0, polygons) and LUCENE-9152 (8.5.0, lines), a narrower one from 7.7.0; it is on main and in 10.6.0 and is not fixed upstream.

// Polygon2D.java at 5adff78bb168 (excerpt, "// :NNN" notes added)
public boolean containsLine(...) {                                   // :204
  if (contains(aX, aY)                                                // :216
      && contains(bX, bY)
      && tree.crossesLine(minX, maxX, minY, maxY, aX, aY, bX, bY, false) == false) {
    return holes == null || holes.intersectsLine(...) == false;      // :219
  }
  return false;
}
public boolean containsTriangle(...) {                               // :225
  if (contains(aX, aY) && contains(bX, bY) && contains(cX, cY)        // :239-241
      && tree.crossesTriangle(..., aX, aY, bX, bY, cX, cY, false) == false) { // :242
    return holes == null || holes.intersectsTriangle(...) == false;
  }
  return false;
}

// EdgeTree.java: contains() "Returns true if the point is on an edge or crosses the edge subtree
// an odd number of times" (:65-68); with includeBoundary == false the crossing test is
// GeoUtils.lineCrossesLine (:205-207, :318), which needs both orientation products < 0 (GeoUtils.java:217-228)

1. XYShapeQuery.within() calls containsLine for a LINE triangle and containsTriangle for a TRIANGLE (XYShapeQuery.java:109, :127, :137; LatLonShapeQuery.java:127, :145, :155). A document matches only if every triangle passes (SpatialQuery.java:296-300, :354-356, :560-569).
2. Segment (0,4)-(4,4). Both ends are polygon vertices, so contains returns true (on an edge). Each of the four polygon edges that reach the segment ends exactly on it: every orientation product is 0, so lineCrossesLine is false for all of them and crossesLine(..., false) is false. containsLine returns true; contains(2,4) is false.
3. Triangle (0,4) (4,4) (2,1). All three vertices are polygon vertices; two of its edges lie on polygon edges (collinear, orientation 0) and the third is the segment above. crossesTriangle(..., false) is false, so containsTriangle returns true; its centroid (2,3) is outside.
4. With includeBoundary == true both crossing tests would return true. That is why the shortcut was safe in 7.5.0-7.6.0, while a touch still counted as a crossing; LUCENE-8669 (7.7.0, 8.0.0) first made the test strict, and LUCENE-8736 (8.1.0, triangles) and LUCENE-9152 (8.5.0, segments) gave it today's strict form (history below).
5. For a convex polygon the shortcut is exact: a segment or triangle whose vertices are in the closed polygon is inside it. The reflex vertex (2,1) is what lets the shape leave.

Executed on main 5adff78bb168 (diagram probe, assertions on and off identical): contains(2,4) false, contains(2,3) false, containsLine((0,4),(4,4)) true, containsTriangle((0,4),(2,1),(4,4)) true, the control containsTriangle((0,0),(4,0),(2,1)) true. Shape vertices on edge interiors trigger it too: containsLine((1,2.5),(3,2.5)) is true while contains(2,2.5) is false.

• Who is hit. XYShape/LatLonShape polygon queries with QueryRelation.WITHIN against a non-convex polygon, with indexed shapes whose vertices lie exactly on that polygon's boundary, at its vertices or on its edges.
• Planar data. Likely when query polygons and indexed shapes come from one dataset and share corners. In an L-shaped zone (0,0) (10,0) (10,4) (4,4) (4,10) (0,10), the road (10,4)-(4,10) across the inner corner and a neighbouring parcel (10,4) (4,4) (4,10) that fills the corner (two of its edges lie on the zone's boundary, its interior is outside the zone) both match WITHIN; a road that stays inside is the control (main and 10.5.2, assertions on and off).
• Lat/lon data. Only when the shared coordinates sit on the encoding grid, for example a query polygon built from decoded index data: placed 300 times at random positions and scales, the configuration reproduces 300 of 300 times on-grid and 0 of 300 times with arbitrary doubles, because quantization moves the indexed vertices off the query vertices.
• No special settings. No codec or setting chosen by hand: the plain-program probe used the real default codec and IndexWriterConfig, the gradle runs the test framework's seed-chosen codec; assertions on and off. Multi-polygon queries delegate to each polygon (ComponentTree.java:198-277) and inherit it (read, not run). Box queries use the convex Rectangle2D and are not affected (read).
• Silent, not a precision effect. No exception. The wrongly accepted region has positive area (the whole notch, 6 of the square's 16) and grows with the input; XY float coordinates are stored exactly.
• How likely. Rare: a non-convex query polygon, every shape vertex exactly on its boundary and a path that leaves it are needed together; no user report was found since 2019.

Public API only (XYShape, XYLine, XYPolygon, newPolygonQuery); the package org.apache.lucene.document is only for locality, and the file belongs in lucene/core/src/test/org/apache/lucene/document/. It passes :lucene:core:checkGoogleJavaFormat, :lucene:core:ecjLintTest and :lucene:core:forbiddenApisTest. It does not compile before 9.1.0 (older test-framework package). The geometry is fixed; the test framework still picks the directory and codec from the seed (newDirectory(); gradle reported codec=Asserting(Lucene104)), and the plain-program probe with the real default codec gives the same result.

Regression test: this same test. It passes with fix A, with assertions on and off.

# gradle, main 5adff78bb168, seed DEADBEEF, assertions on; -Ptests.asserts=false gives the same failure
TestXYShapeWithinNotchedPolygon > testShapesAcrossTheNotchAreNotWithin FAILED
    java.lang.AssertionError: expected:<0> but was:<2>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:A5C964C3A8848642]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.junit.Assert.assertEquals(Assert.java:633)
        at org.apache.lucene.document.TestXYShapeWithinNotchedPolygon.testShapesAcrossTheNotchAreNotWithin(TestXYShapeWithinNotchedPolygon.java:63)

# release jars, plain JUnit runner: 10.6.0 (seed DEADBEEF assertions on; seed 5EEDF00D assertions off), 9.12.3, 9.1.0
testShapesAcrossTheNotchAreNotWithin  expected:<0> but was:<2>

# with fix A: BUILD SUCCESSFUL, assertions on and off

• The contract. Component2D.java:73: "return true if this component2D contains the provided line"; :84: "... the provided triangle". No approximation is documented. The public QueryRelation.WITHIN says only "used for WITHIN Queries" (ShapeField.java:122), so what the user sees promised is the plain meaning of WITHIN, which these internal methods implement.
• The tests. The hand-written shared-boundary tests use convex polygons: TestLatLonShape.testTriangleTouchingEdges (TestLatLonShape.java:560) checks shared points on the unit square and asserts containsTriangle == false for "1 shared point but out" (:602-614); testLUCENE8736 (:656) queries a 4x7 rectangle and testTriangleCrossingPolygonVertices (:701) a convex pentagon; TestPolygon2D.testIntersectsSameEdge (TestPolygon2D.java:333) asserts that a corner-to-corner diagonal of a convex square is contained (:339). No targeted test exercises containsLine/containsTriangle on a non-convex query polygon with every shape vertex on its boundary. Random tests do use non-convex polygons (GeoTestUtil.nextPolygon returns surpriseMePolygon() half the time, GeoTestUtil.java:453-479), but cannot see it: testIndexAndQuerySamePolygon (TestLatLonShape.java:769-812) queries a polygon WITHIN itself, which checks only the positive direction, and the random spatial tests' oracle calls the same containsLine/containsTriangle (BaseSpatialTestCase.java:769, :781).
• The history. LUCENE-8736 (CHANGES.txt:6535-6538, "Point in Polygon now correctly includes boundary points") is about boundary points. LUCENE-9152 (#10192) states the line rule "If all points are inside the polygon, then do not consider the boundary". Neither discusses non-convex polygons.

The strongest case for "intended": boundary inclusion is deliberate (LUCENE-8736), Component2D is @lucene.internal, XYShape warns that vertices are indexed "with some loss of precision" (XYShape.java:71), and #9782 is an open umbrella for wrong WITHIN results with shared boundaries, where boundary cases were treated as best effort.

Why it fails: inclusion covers boundary points, not shape interiors that lie outside the polygon; the failure goes through the public WITHIN query with valid simple polygons; the coordinates are exact and the wrong area is a whole region; and #9782 is open as a bug about the opposite direction (false negatives), with no statement accepting false positives. Every reviewer, including the one asked to argue for "intended", rated it real.

Option A is the validated sketch; B is the shape an upstream patch should take for large polygons, C a cheap complement, D the rejected alternative.

fix.diff, +60/-2 in Polygon2D.java only. Only when the existing checks already say "contained": containsLine splits the segment at every polygon vertex lying on it and requires the midpoint of each piece to be contains()-ed; containsTriangle does the same for its three edges and also requires that no polygon vertex lies strictly inside the triangle.

// containsLine: after the existing checks
    && tree.crossesLine(minX, maxX, minY, maxY, aX, aY, bX, bY, false) == false
    && segmentPiecesInside(aX, aY, bX, bY)
// containsTriangle: after the existing checks
    && segmentPiecesInside(aX, aY, bX, bY)
    && segmentPiecesInside(bX, bY, cX, cY)
    && segmentPiecesInside(cX, cY, aX, aY)
    && vertexStrictlyInside(aX, aY, bX, bY, cX, cY) == false
// segmentPiecesInside: split the segment at every polygon vertex on it
//   and require the midpoint of each piece to be contains()-ed.
// vertexStrictlyInside: true if a polygon vertex has the same nonzero
//   orientation against all three triangle edges.

Trade-offs

Shows the root cause, but scans every polygon vertex on each call that passes the cheap checks (O(polygon vertices) per candidate triangle) and uses a boxed list: it may be too costly for WITHIN queries with large polygons (no benchmark was run). Holes keep their existing check.

What the checks validated

Gradle in a scratch worktree of 5adff78bb168, seed DEADBEEF: the repro fails stock and passes with the fix, assertions on and off; with the fix, the repro, every org.apache.lucene.geo test class and every org.apache.lucene.document.Test*Shape* class pass (45 classes, 390 tests, 26 skipped, 0 failures). Earlier the same sketch made the finder's, an independent reproducer's, reviewers' and a devil's-advocate verifier's repros pass, and passed the 16 TestPolygon2D tests. Targeted runs, not a full build, on simple polygons only: no targeted run used a query polygon with holes or a multi-polygon query, and numerical edge cases are covered only by the existing suites.

Find "a polygon vertex on the segment" and "a polygon vertex strictly inside the triangle" with a bounding-box walk of the existing edge tree (every polygon vertex is an edge end point).

Trade-offs

The extra cost is bounded by the edges near the shape, not by the polygon size; more code than A. The shape an upstream patch should take.

Compute once at construction whether the polygon is convex; for a convex polygon without holes the current shortcut is exact.

Trade-offs

Keeps today's cost for convex query polygons; adds a flag and a construction-time pass.

Call the crossing tests with includeBoundary == true in these two methods.

Trade-offs

Removes the false positives but, by reading, brings back the false negatives LUCENE-8736 and LUCENE-9152 fixed: shapes that share a boundary with a convex query would stop matching WITHIN (testTriangleTouchingEdges, testIntersectsSameEdge). Not run.

Method: semi-formal (a bounded-exhaustive consistency check on the stock main jar).

• The oracle: exact integer geometry with sample points on a 1/4 grid, over every simple polygon with 3-5 vertices on 3x3 and 4x4 grids (with triangular holes for 3-4 vertices), every half-grid box and every grid triangle, degenerate ones included.
• relate() against contains(), and intersectsTriangle and contains() against the oracle: 0 violations.
• containsTriangle/containsLine returned true while a point strictly outside the polygon lay in the shape in 104 cases (3x3 grid, 3-4 vertices and holes), 868 (3x3, 3-5 vertices and holes), 4,908 (4x4, 3-4 vertices and holes) and 58,792 (4x4, 5 vertices).
• The root cause was then read from Polygon2D and EdgeTree, and a JUnit on the public XYShape/LatLonShape API reproduced it on main, 10.5.2 and 9.12.3 with assertions on and off.