Geo3D outside distance to a lat/lon box that reaches a pole ignores the pole, so newOutsideBoxSort sorts documents beyond the pole after nearer ones

Geo3DDocValuesField.newOutsideBoxSort orders documents "by ascending outside distance from the box". For a box whose top latitude is the North Pole (or whose bottom latitude is the South Pole) and whose longitude extent is under 180 degrees, GeoBBoxFactory builds a GeoNorthRectangle (GeoSouthRectangle): a wedge whose two side edges meet at the pole, which is inside the box. Its outsideDistance takes the minimum over the bottom parallel, the two side meridians and the two bottom corners, never the pole. For a point on the far side of the pole neither side meridian offers a point on the box, so the result is the distance to a corner: for the box latitude 60..90 x longitude -10..10 and the point (80, 180), 39.88 degrees instead of 10, and in the WGS84 sort 4,434,716 m, so the document sorts after one at (35, 0), 25 degrees south of the box (sort value 2,779,879 m). In the three boxes measured, 26% to 37% of the outside grid points get values that are too large, most by tens of degrees; the hit set never changes. The same box with a top latitude of 89.9999 is a plain rectangle and gives 10.0001 degrees. The bug dates from the first outside-distance code (LUCENE-6578, 5.3.0, 2015) and is in every release since (the sort since 6.1.0); adding the pole distance to the minimum, as GeoLongitudeSlice already does, fixes it, with all of lucene/spatial3d passing.

• Outside distance: the arc distance from a point to the nearest point of a shape, 0 inside it. Geo3DDocValuesField.newOutsideBoxSort sorts by it and reports it in meters (the arc distance times the planet's mean radius).
• Polar rectangle: GeoBBoxFactory.makeGeoBBox builds a GeoNorthRectangle when the top latitude is the pole, the bottom latitude is not the other pole, the box has nonzero width and height, and its longitude extent is under 180 degrees (strictly, under pi minus pi x 1e-12 rad), a GeoSouthRectangle for the South Pole (GeoBBoxFactory.java:58-131). Its boundary is the bottom (top) parallel between two corners and two meridian segments from the corners to the pole.
• Pole tolerance: the factory treats a latitude as the pole when it is within pi x 1e-12 rad of it or its sine is within 1e-12 of 1 (GeoBBoxFactory.java:137-150). The sine test reaches about 0.00008 degrees (9 m) from the pole, so 89.999999 and 89.99992 build a GeoNorthRectangle and 89.9999 a plain GeoRectangle. The sine tolerance dates from LUCENE-10673 (first released in 9.4.0); in older releases only latitudes essentially at the pole count.

1. newOutsideBoxSort (Geo3DDocValuesField.java:281-291) calls Geo3DUtil.fromBox (Geo3DUtil.java:173-189), which checks the latitudes against +/-90 and calls GeoBBoxFactory.makeGeoBBox; the factory returns GeoNorthRectangle / GeoSouthRectangle for a pole-reaching box narrower than GeoWideRectangle.MIN_WIDE_EXTENT (GeoBBoxFactory.java:101, :128-131; GeoWideRectangle.java:31).
2. The sort's comparator calls computeOutsideDistance(DistanceStyle.ARC, x, y, z) on each decoded doc value (Geo3DPointOutsideDistanceComparator.java:101, :143), which returns 0.0 inside the box and outsideDistance otherwise (GeoBaseMembershipShape.java:47-53).
3. GeoNorthRectangle.outsideDistance (GeoNorthRectangle.java:283-298) returns min(bottom, left, right, LRHC, LLHC); GeoSouthRectangle.outsideDistance (GeoSouthRectangle.java:254-269) is the mirror. The pole is never a candidate.
4. Each side term measures only to the perpendicular foot on the meridian plane and its antipode and drops those outside the box (Plane.java:600-636). For (80, 180) and the side at longitude -10 the foot is (80.1489, 170), on the far half of the meridian, and the antipode (-80.1489, -10), below the box: the term is +infinity, and the same for the other side.
5. What is left: the bottom parallel's point (60, 0) at 40 degrees and the corners (60, +-10) at 39.882280 degrees. The pole, 10 degrees away, is never asked.
6. The class itself lists the pole as the end point of both side edges (leftPlanePoints, rightPlanePoints, edgePoints, GeoNorthRectangle.java:156-159) and adds it to its bounds (:279). GeoLongitudeSlice.outsideDistance adds both poles (GeoLongitudeSlice.java:196-207); the wide polar rectangles search the whole side meridians, so the pole lies on their arc (GeoWideNorthRectangle.java:258-274).

In grid sweeps against an independent spherical-trigonometry reference, 226 of 801 outside points (north box lat 45..90 x lon -20..30) and 205 of 790 (south box lat -90..-40 x lon 100..160) were wrong; the worst points were (81.5, -177.5) with 52.65 degrees instead of 8.50 and (-86.5, -45.5) with 52.91 instead of 3.50. For the box lat 60..90 x lon -10..10 a 1-degree grid in the fact check found 37% of the outside points wrong, by up to 30 degrees. The points need not be polar: for the tall box lat -89.5..90 x lon -10..10 the finder's sweep has wrong values near the equator, about 1.2 degrees too large.

• Who. Users of the optional lucene/spatial3d module who sort with Geo3DDocValuesField.newOutsideBoxSort, or call computeOutsideDistance on a GeoBBoxFactory box (alone or inside a composite shape), where the factory builds a GeoNorthRectangle or GeoSouthRectangle: a box of nonzero size that reaches latitude 90 or -90 (or lies within the factory's pole tolerance, such as 89.999999), not both, and spans under 180 degrees of longitude, for example a polar sector such as lat 60..90 x lon -10..10, and the index holds documents on the far side of the pole.
• Effect. Those documents get sort values that are too large (meters in the FieldDoc), mostly by tens of degrees, so they sort after farther documents or fall out of the top N. Every returned hit still matches the query. No exception, with assertions on or off.
• Default vs opt-in. An optional module and an apparently niche sort: no in-tree caller or test uses it and no matching public report was found (there is no usage data). The caller must pass a PlanetModel; the repro passes WGS84, with new IndexWriterConfig() and the codec the test framework picks (Asserting(Lucene104) in the logged run). The bug is in the shape geometry and does not depend on the codec or the writer settings.
• Scale. None: one document triggers it, deterministically, at any index size. The share depends on the box: in the independent reproducer's grid sweeps 28% (north box) and 26% (south box) of the outside points were wrong, by up to about 44 and 49 degrees; for the headline box lat 60..90 x lon -10..10 a 1-degree grid in the fact check found 37% wrong, by up to 30 degrees. On the fact check's grid, 81-87% of the wrong values in these three boxes were off by 10 degrees or more.
• Not affected. Boxes whose top (bottom) latitude is outside the factory's pole tolerance, about 0.00008 degrees from the pole (89.9999 is already correct; 89.99992 and 89.999999 are not), boxes spanning 180 degrees or more, boxes away from the poles, and the hit set of any query.
• Workaround. Until a fix ships, a top latitude just outside the tolerance, such as 89.9999, gives correct values; it leaves out a cap of about 11 m around the pole, so points in that cap get a small positive distance instead of 0.
• How likely. Rare: it needs both a pole-reaching narrow box and documents beyond the pole. No public report was found in the 11 years since 5.3.0.
• Related findings (separate reports, other fix sites): LFV-737 (GeoExactCircle outside distance skips the slice end points) is the same missing-end-point pattern; LFV-735 (GeoStandardPath measures its end caps to the end point instead of the cap edge) is a related outside-distance error at the ends of a shape.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: outside distance in degrees expected:<10.0> but was:<39.882280145867114>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:555)
       org.apache.lucene.spatial3d.geom.TestPolarRectangleOutsideDistance.testPointBeyondNorthPole(TestPolarRectangleOutsideDistance.java:34)

• The contract. newOutsideBoxSort: "This sort orders documents by ascending outside distance from the box. Points within the box have distance 0.0." Latitude bounds "must be within standard +/-90 coordinate bounds" (Geo3DDocValuesField.java:260-280). GeoOutsideDistance: shapes "that can compute the distance from a point to the closest outside edge" (GeoOutsideDistance.java:19-21).
• The stated intent. LUCENE-6578 (now #7636), which introduced outside distances, asked for the arc distance "from a GeoPoint to the nearest edge/point of a GeoShape".
• The class's own geometry. The pole is inside the box (the repro asserts isWithin(NORTH_POLE)) and is the end point of both side edges (GeoNorthRectangle.java:156-159); the method already measures the other end points, the corners.
• The same commit did it right elsewhere. 688c67f8ff2 gave GeoLongitudeSlice.outsideDistance its NORTH_POLE / SOUTH_POLE terms in the same diff.
• Not an approximation. On the same point the value jumps from 10.000098 degrees (top 89.9999) to 39.882280 (top 90): about 3,300 km for an 11 m change of the box. spatial3d's documented accuracy caveats are orders of magnitude smaller: the doc-value precision loss (4.19e-8 for the latitude component and 8.38e-8 for longitude, Geo3DDocValuesField.java:45-47), "up to 0.5% error" for the WGS84 distance query (Geo3DPoint.java:112-113) and the accuracy setting of exact circles (GeoCircleFactory.java:50-57).
• Tests and history. No upstream test calls newOutsideBoxSort; the only box outside-distance assertions use a plain rectangle (lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/TestGeoBBox.java:75-77). The two methods are unchanged since 2015 except for a reformat (LUCENE-9570), and no CHANGES entry or issue documents a polar limitation.

The strongest case for "intended" (the intended-behaviour checker built it; cross-model reviews rated it weak): GeoNorthRectangle and GeoSouthRectangle are @lucene.internal, and GeoOutsideDistance, GeoBBox and GeoBBoxFactory are @lucene.experimental, as are PlanetModel, which the sort requires, and Geo3DPoint; the Geo3DDocValuesField class javadoc still lists its factory methods as "TBD" and warns about precision loss; "the closest outside edge" does not say that edge end points count; LUCENE-7212 (#8267), which added the sort, is still open and its last maintainer comment lists tests as still needed; and a fix changes existing sort values and top-N results.

Why it fails: newOutsideBoxSort itself carries no stability tag and promises the ascending outside distance for any latitude in +/-90; "edge" must include its end points, because the method already measures the corners; neither an open feature issue nor a precision warning in the 1e-8 range documents that values may be off by tens of degrees; and the jump between 89.9999 and 90 shows a missing case, not a design. Upstream has treated geo3d distance errors as bugs before (for example LUCENE-7139, "Fix bugs in geo3d's Vincenty surface distance"). The compatibility effect is real; it bears on how the fix is announced (a CHANGES entry), not on whether the current values are correct. Expect a maintainer to say the sort is rarely used: that bears on priority, not on validity.

Option A was applied in a scratch worktree at a9779ef3c193 and run through gradle (seed DEADBEEF); B and C were not run. Until a fix ships, a top latitude just outside the pole tolerance, such as 89.9999, avoids the bug; it leaves out a cap of about 11 m around the pole.

In GeoNorthRectangle.outsideDistance (:283-298) add distanceStyle.computeDistance(planetModel.NORTH_POLE, x, y, z) to the minimum; in GeoSouthRectangle.outsideDistance (:254-269) the same with SOUTH_POLE. The boundary is the bottom (top) parallel and two meridian segments ending at the corners and the pole; the existing terms cover the parallel, the segments' interiors and the corners, so the pole is the only missing end point. For a point whose perpendicular feet fall off both segments, the nearest point of each segment is an end point, so this completes the minimum.

--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoNorthRectangle.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoNorthRectangle.java
@@ -291,9 +291,11 @@ class GeoNorthRectangle extends GeoBaseBBox {
     final double LRHCDistance = distanceStyle.computeDistance(LRHC, x, y, z);
     final double LLHCDistance = distanceStyle.computeDistance(LLHC, x, y, z);
+    // the left and right edges end at the pole, which is part of the rectangle
+    final double northDistance = distanceStyle.computeDistance(planetModel.NORTH_POLE, x, y, z);
 
     return Math.min(
-        bottomDistance,
+        Math.min(bottomDistance, northDistance),
         Math.min(Math.min(leftDistance, rightDistance), Math.min(LRHCDistance, LLHCDistance)));
   }
(GeoSouthRectangle: the same with SOUTH_POLE)

Trade-offs

• Cost: one extra point distance per call, only in the two narrow polar classes. No format, API or index change.
• Compatibility: existing users of the sort get smaller values for documents beyond the pole, a different order and possibly a different top N; worth stating in the CHANGES entry.
• Distance styles: the pole is a point of the box for every DistanceStyle, and the term uses the same computeDistance(GeoPoint, x, y, z) as the corners; only ARC, the style the sort uses, was validated.
• With the PR: add the repro (or a polar case in TestGeoBBox plus a first newOutsideBoxSort test in TestGeo3DDocValues) and a CHANGES entry.

What the checks validated

• Stock main a9779ef3c193 (gradle, seed DEADBEEF): the repro fails 3 of 4 with assertions on and off; TestGeoBBox (11 tests) and TestGeo3DDocValues (1) pass.
• With the fix: the repro passes 4 of 4 with assertions on and off; TestGeoBBox and TestGeo3DDocValues pass; all of :lucene:spatial3d:test with the repro class added passes (20 classes, 185 tests, 0 failures, 3 skipped); ecjLintMain, ecjLintTest and checkGoogleJavaFormat pass for spatial3d; fix.diff applies cleanly to a clean tree.
• With the fix shadowed onto the main jars: the repro 4 of 4, the hunt's JUnit 3 of 3, the independent reproducer's JUnit 7 of 7 and the cross-model reviewer's own test 5 of 5 pass.
• In the hunt: the upstream spatial3d suite gives the same result with and without the change (181 tests: 178 pass, 3 assumption-aborted, on ea57360912ed), and the bounded sweep drops from 81,742 to 0 violations in 17,068,396 checks (not re-run independently).

Say in the newOutsideBoxSort javadoc that boxes reaching a pole give too large values beyond the pole, and keep the current values. Users can work around it with a top latitude such as 89.9999.

Trade-offs

Keeps existing sort values and top-N results stable and is cheaper to review, but leaves errors of tens of degrees (up to about 49 in the boxes measured) for a legal input when a two-line fix exists, and the factory's pole tolerance (89.999999 counts as 90) makes the trigger hard to describe.

GeoWideNorthRectangle bounds its side planes only by the latitude plane, which is safe because, for an extent of 180 degrees or more, the far half of each side meridian lies inside the box (GeoWideNorthRectangle.java:262-267).

Trade-offs

For a narrow box the far half of each side meridian is outside the box, so the same change would make distances too small: for (80, 180) the left-side candidate (80.1489, 170), 1.727941 degrees away, is rejected only by the right side plane, so dropping that bound would return 1.73 degrees instead of 10 (the diagram probe trace; the change itself was not run).

Method: bounded-exhaustive translation validation on the stock jar (semi-formal tier), in a hunt unit on the geo3d distance sort fields.

• The harness built 540 GeoBBoxFactory boxes (9 latitudes including +-90 and +-89.5 x 12 longitude pairs including dateline-crossing, full, wide and degenerate boxes) and 600 simple star polygons (599 built on WGS84), and compared each one's outside distance at about 3,700 to 5,400 decoded doc-value points with an independent exact reference of the arc distance to the boundary. Geo3D parallels are horizontal planes and its meridians planes through the origin, so the same direction-based reference is exact on SPHERE and WGS84 for Lucene's ARC distance (the angle between the points' direction vectors, not an ellipsoidal surface distance). Only ARC was checked, and 27,398 checks within 3e-6 rad of an edge were skipped.
• Of 17,068,396 checks, 81,742 failed, all in two classes: GeoNorthRectangle (20,963 per planet model) and GeoSouthRectangle (19,908 per planet model), always with Lucene's value too large. With the pole term added, 0.
• The unit's plan targeted the sort comparators; it did not name this lead. The cause was read off the two outsideDistance methods and reduced to a public-API JUnit on the stock main jars.
• Found 2026-10-27 on main a9779ef3c193; then checked by an independent reproducer, an intended-behaviour devil's advocate, reviews by a model from another family (OpenAI GPT-5.6), an adjudication, a history, prior-report and security follow-up, and a credibility audit.