LatLonShape circle queries miss a line or polygon whose edge crosses the circle with no vertex inside

LatLonShape.newDistanceQuery decides for each indexed edge whether it touches the query circle. When neither end point of an edge is inside the circle, Circle2D tests one more point of the edge and nothing else: the foot of the circle's centre on the edge, computed with a Euclidean dot product on raw (lon, lat) degrees. On the ground a degree of longitude is only cos(lat) times a degree of latitude, so for a diagonal edge away from the equator that foot is not the point nearest the centre, and an edge that enters only an outer band of the circle can be silently missed by INTERSECTS and matched by DISJOINT, depending on its direction; through the same test a polygon can also be reported to CONTAIN a circle that crosses one of its edges. In the repro, a line passes 8.95 km from the centre of a 10 km circle at latitude 60, the tested point is 11.19 km away, and the query returns 0 hits. For circles up to about 100 km the band's worst depth, 1 - 2c/(1+c²) of the radius with c = cos(lat), does not depend on the radius (at 1,000 km a scan found slightly deeper misses): the Circle javadoc's own 1 km example circle misses a line 953 m from its centre. Point documents and XYShape circles are not affected. The defect is as old as the API (8.5.0, LUCENE-8707) and present in 10.6.0 and main. In #10279 (2020) Ignacio Vera already named this mechanism for a CONTAINS test failure; only withinTriangle was changed then. Scaling longitude differences by cos(centre latitude) in the projection fixes the repro and keeps the geo and shape test suites green.

1. Contracts. LatLonShape.newDistanceQuery: "create a query to find all polygons that intersect a provided circle" (document/LatLonShape.java:315-319). Component2D.intersectsLine: "return true if this component2D intersects the provided line" (geo/Component2D.java:49).
2. The query. For an indexed LINE the INTERSECTS predicate calls component2D.intersectsLine (document/LatLonShapeQuery.java:101-108), for a TRIANGLE intersectsTriangle (:109-118). DISJOINT is intersects().negate() (document/SpatialQuery.java:129-130), so each INTERSECTS miss is a DISJOINT match.
3. Vertices first. Circle2D.intersectsLine returns contains(a) || contains(b) || calculator.intersectsLine(a, b) (geo/Circle2D.java:81); intersectsTriangle checks the vertices, the centre in the triangle, then the three edges the same way (:99-106). withinLine (:165) and withinTriangle (:198-205, used by CONTAINS) use the same edge test.
4. The haversine calculator calls the shared static helper with the centre, and again with the centre shifted by 360° for circles that cross the dateline (geo/Circle2D.java:449-459).
5. The defect (fix site). The static intersectsLine (geo/Circle2D.java:219-256) projects the centre onto the segment with the Euclidean dot product on raw (lon, lat) degrees (:229-238), rejects a foot outside the segment (:240-242), builds that one point (:244-245) and returns calculator.contains(pX, pY) (:253), the haversine test (:427-447: a bounding-rectangle pre-check, then SloppyMath.haversinSortKey compared with the radius's sort key). No other point of the edge is tested.
6. Why that point is wrong. The raw-degree foot minimises lon² + lat² differences, so it counts east-west steps as 1/cos(lat) times too long and slides along a diagonal edge towards the part that is closer to the centre in longitude (and farther in latitude): in the repro (60.09, 10.09) is 0.09° off the centre in both coordinates, the nearest point (60.036, 10.144) 0.036° in latitude and 0.144° in longitude. The Cartesian calculator (XYShape circles, :356-357) uses the same helper in its own matching metric and is correct. Point documents use contains only (document/LatLonShapeQuery.java:95-100).

Circle(lat 60, lon 10, 10 km); line A = (60.38, 9.8), B = (59.78, 10.4), 74.6 km long; A is 43.7 km and B 33.1 km from the centre.

• Raw-degree foot: t = 0.483, (60.09, 10.09), 11,186 m from the centre: outside, so intersectsLine is false.
• Nearest point of the line: t = 0.573, (60.036, 10.144), 8,947 m: inside. The test's witness (60.04, 10.14) is on the line at t = 17/30, 8,961 m away. About 12% of the line lies inside the circle.
• Through LatLonGeometry.create(circle) the same component answers contains(10.14, 60.04) = true and intersectsLine = false.
• The index stores quantized vertices (about 4.2e-8° latitude, 8.4e-8° longitude); with margins of about a kilometre this does not matter here.

In local metric coordinates the tested distance is at most (1 + c²)/(2c) times the true minimum, c = cos(lat), so an edge whose true minimum lies between 2c/(1 + c²)·R and R can be missed: a band of depth 1 - 2c/(1 + c²) of the radius R. Latitude 0: 0%; 30°: 1.0%; 45°: 5.7%; 48.86° (the javadoc example): 8.2%; 60°: 20%; 75°: 51.5%. In this small-circle approximation it does not depend on R: a numerical scan of random crossing segments found worst depths just below the bound for radii from 100 m to 100 km, and slightly deeper misses at 1,000 km (6.5% at 45°, 21.5% at 60°). Whether an edge in the band is missed depends on its direction: in that scan the stock code missed about half of the band crossings (53.4% at 45° and at 60°, R = 10 km).

• The repro's line itself: INTERSECTS 0, DISJOINT 1; with the fix INTERSECTS 1, DISJOINT 0.
• A triangle polygon with the repro's edge, not containing the centre: INTERSECTS 0, DISJOINT 1.
• The Circle javadoc's own example circle, 1 km around (48.8584, 2.2945): a line from (48.8782, 2.2903) to (48.8542, 2.3143), ends 2,223 m and 1,522 m away, passes 953 m from the centre: INTERSECTS 0, DISJOINT 1; a triangle with that edge: INTERSECTS 0, DISJOINT 1.
• A polygon that contains that centre but has the same edge 953 m from it: CONTAINS 1, although the circle crosses the polygon's boundary.
• With the fix all four turn correct (INTERSECTS 1, DISJOINT 0, CONTAINS 0); a control line at the equator whose nearest point is 11.79 km from a 10 km circle stays unmatched.

• Who is hit. Users of LatLonShape line and polygon fields queried with newDistanceQuery, or with newGeometryQuery and a Circle: INTERSECTS misses the document, DISJOINT matches it, and CONTAINS can match a polygon whose edge cuts the circle (through withinTriangle). No special configuration: the repro uses a plain IndexWriterConfig and searcher and fails under every seed run (the test framework randomizes the codec), with assertions on or off; no error, and the index itself is fine.
• Ordinary parameters. For ordinary radii (up to about 100 km) the band depends on latitude only: 5.7% of the radius at 45°, 20% at 60°. The Circle javadoc's own 1 km example circle misses a line 953 m from its centre.
• What it takes. Both end points of the edge outside the circle while the edge passes through the outer band, so the edge must be long relative to the circle and run diagonally in lon/lat: two-point lines, coarse polygons, long road or pipeline segments. Densely sampled shapes likely have a vertex inside first (not measured). The finding is rated rare; no user report was found in the recorded searches.
• How often on random crossings (a synthetic scan: end points uniform in a box of ±3 radii around the centre, only segments with both ends outside that truly cross, 5,071-5,286 per cell): the stock code misses 0% at the equator, 0.5-0.8% at 30°, 3.5-3.8% at 45°, 10.7-12.1% at 60° and 24.7-26.2% at 75°, for every radius from 100 m to 1,000 km (at 75° only up to 100 km: the 1,000 km cell leaves the lat/lon range).
• Not affected. Point documents (they use contains), XYShape circles (matching Cartesian metric), and edges with a vertex inside the circle.

The test is the hunt's minimal repro, unchanged; it passes :lucene:core:check -x test (google-java-format, ecj lint, forbidden APIs). It uses a plain IndexWriterConfig, a ByteBuffersDirectory and fixed geometry; the test framework still randomizes codec, locale and time zone per seed, but the outcome does not depend on it (the test failed under every seed run).

Executed: gradle on main 5adff78bb168 with assertions on and off: fails at the count assertion (line 48) after the haversine precondition passed; with the fix it passes. The hunt's standalone runs, a separate re-run and the audit's and judge's re-runs fail the same way.

Use the same test as the regression test.

cp $REPRO/TestLatLonShapeCircleCrossingEdge.java $LUCENE/lucene/core/src/test/org/apache/lucene/document/
cd $LUCENE && ./gradlew :lucene:core:test --tests TestLatLonShapeCircleCrossingEdge
# fails the same way with -Ptests.asserts=false and under every seed tried

TestLatLonShapeCircleCrossingEdge > testLineThroughCircleWithBothEndsOutside FAILED
    java.lang.AssertionError: expected:<1> but was:<0>
        at __randomizedtesting.SeedInfo.seed([5EED1128:E3B67604A7BF46BD]: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.TestLatLonShapeCircleCrossingEdge.testLineThroughCircleWithBothEndsOutside(TestLatLonShapeCircleCrossingEdge.java:48)

# with the fix: BUILD SUCCESSFUL, the test passes with assertions on and off

• Self-contradiction. Through LatLonGeometry.create(circle), contains(10.14, 60.04) is true for a point of the edge while intersectsLine is false for the edge. Lucene's edges are straight lines in lon/lat by design, and the expected answer holds in that model; as a cross-check only, the great-circle arc between the same end points also comes within the radius (9.10 km in the repro, 953.6 m in the javadoc example).
• Contracts are unqualified: "find all polygons that intersect a provided circle" (LatLonShape.java:315), "return true if this component2D intersects the provided line" (Component2D.java:49).
• Maintainer's words. In #10279 (LUCENE-9239), explaining a CONTAINS test failure, Ignacio Vera wrote: "The current implementation uses cartesian geometry to find the closest point from a line to a point (our edges are cartesian!). Then it uses the spherical geometry to calculate the distance between this two points. This error is a side effect of this approach." The fix (b732ce70025) changed only withinTriangle; the projection stayed.
• Precedent. #10909 (LUCENE-9870, PR #41) fixed another way this method missed matches along indexed lines, as a bug, in 8.8.2.
• Why the tests are silent. The random shape-query tests use the query's own Circle2D as the oracle (BaseSpatialTestCase.java:641, :664), and TestCircle2D's fixed line cases use circles at latitude 0, where the band is empty.

Strongest case for "intended": Circle is @lucene.experimental; its javadoc says "The circle is approximated on the spherical Earth model" and "For very large circles or circles near poles, consider using polygons instead" (geo/Circle.java:29-47); Component2D is @lucene.internal; and LUCENE-9239 knowingly kept the Cartesian closest point.

Why it fails: the miss happens inside Lucene's own spherical model (the same component says the point is inside); for ordinary radii the band depends on latitude, not on size, so a 1 km circle at 48.86° is neither "very large" nor "near poles"; @lucene.experimental allows API changes, not wrong answers; the maintainer called the effect an error, and #10909 treated a sibling miss as a bug. Cross-model reviews (OpenAI GPT-5.6) rated the argument moderate and rejected it, as did the devil's-advocate verifier and the adjudication. Verdict: not intended, a defect.

Every point the helper tests lies on the edge, so within Lucene's model (lon/lat-straight edges and the existing contains predicate) a positive answer is right; a fix only has to test a better point, or more points, and options A-C add no geometric false match beyond that predicate's existing boundary behaviour. One fix was built and tested (not proven) in a scratch worktree of 5adff78bb168; the alternatives are listed with their trade-offs.

Add an xScale parameter to the static helper and scale both x differences by it; build the foot from the unscaled difference. HaversinDistance passes cos(toRadians(centerLat)), computed once in its constructor, for both the normal and the dateline-shifted call; CartesianDistance passes 1 (unchanged behaviour). Full patch: 13 insertions, 7 deletions in geo/Circle2D.java.

    final double vectorAPX = (centerX - aX) * xScale; // xScale: 1 cartesian, cos(centerLat) haversine
    final double vectorAPY = centerY - aY;
    final double vectorABX = (bX - aX) * xScale;
    final double vectorABY = bY - aY;
    ...
    final double pX = aX + (bX - aX) * distance; // the foot itself stays in degrees

    // HaversinDistance: this.lonScale = Math.cos(Math.toRadians(centerLat));
    // Circle2D.intersectsLine(centerLon, centerLat, aX, aY, bX, bY, this, lonScale)

Trade-offs

Approximate, not exact: cos(lat) is taken at the centre. On the random crossings of the scan it misses none for radii up to 100 km at latitudes 0-75°; at 1,000 km it misses 0.02-0.15% (1, 7 and 8 of about 5,160 at 30°, 45° and 60°), all within 0.74% of the radius of the rim, and in one cell it missed one crossing the stock code caught. Cost: one multiplication per difference and one Math.cos per circle. At a pole the projection becomes a latitude-only projection. Not run separately at the poles, on dateline-crossing segments or circles, on zero-length segments, or for long edges of large circles beyond the scan, which models the helper only (no quantization, rectangle pre-check or dateline path).

What the checks validated

Scratch worktree of 5adff78bb168, gradle, JDK 25: the repro fails stock and passes fixed, with assertions on and off; 54 suites (org.apache.lucene.geo.*, document.TestLatLon*, TestXY*, TestShape*, search.TestLatLon*, TestXY*; 585 tests, 0 failures) pass twice with random root seeds (and a third time in the fact check); :lucene:core:check -x test passes. The diagnostic probe's javadoc-example line and polygon, 45° line and CONTAINS polygon all turn correct; its equator control stays unmatched. Tested, not proven: these runs do not cover every input.

Search t in [0, 1] for the minimum of haversinSortKey along the edge (for example golden-section or Newton steps seeded by fix A's foot, on the part of the edge inside the circle's bounding box) and compare it with the radius.

Trade-offs

Removes fix A's residual, including for large circles, but costs several distance evaluations per edge on a hot leaf path, and its convergence needs an argument (the distance along a lon/lat-straight edge is not guaranteed to be unimodal for very long edges). Not implemented or run.

Keep today's raw-degree foot and also test fix A's foot.

Trade-offs

Never worse than today on any input (it only adds a test of a point on the edge); still approximate; two contains calls per edge. Not run.

Accept the edge when the tested point is within the radius plus an error bound.

Trade-offs

Not recommended: it adds false matches for edges that pass just outside the circle, trading one wrong answer for another. Not run.

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

• The obligation: Component2D.intersectsLine must be true when the segment shares a point with the circle. For the haversine calculator the proof step "the tested foot is the nearest point of the segment" does not hold, because the foot is computed in raw degrees; a public-API JUnit (circle at 45°, a diagonal two-point line) witnessed the miss on main, 10.6.0 and 9.12.3, and a cos-latitude fix sketch made it pass.
• Then an independent reproducer wrote its own test from the claim (the 60° repro here), cross-model reviews (OpenAI GPT-5.6, intended and refute lenses, executed) wrote and ran their own tests, a devil's-advocate verifier argued the intended-behaviour case and found the javadoc-example miss, and an adjudication re-ran the tests and checked the geometry. An audit and a final repro check followed.
• Earlier hunt coverage had not reached it: its Circle2D checks used XY circles only, and its distance-query checks used point documents, which this bug does not affect.