geo3d path distances throw "Can't find world intersection" for a point inside the path at the edge of a cutoff plane's 1e-12 tolerance

A geo3d path is a chain of great-circle segments with a half-width. Each segment is bounded by two side planes and two cutoff planes, one through each end point, and every plane test in geo3d counts a point up to 1e-12 on the wrong side as inside. To measure a distance, every segment that contains the point projects it onto its centre line: it intersects its great-circle plane with the plane through the point square to it, gets two candidate feet (the projection and its antipode) and keeps the one that passes both cutoff planes, else throws RuntimeException("Can't find world intersection ..."). The foot lies farther from the cutoff plane than the point (by 1/cos of the point's offset from the centre line; near the centre line rounding decides), so for a point at the very edge of the 1e-12 band of a cutoff plane the point passes and its foot does not, and computeDistance, computeDeltaDistance, computeNearestDistance and computePathCenterDistance throw, and so does IndexSearcher.search with Geo3DDocValuesField.newPathSort. In the repro, a point 3.45e-6 rad beside the path (0,0)-(0,0.1)-(0,0.2) and 1.0e-12 rad past its middle point evaluates to 9.99992e-13 on segment 1's end plane (inside) and its foot to 1.0000056e-12 (outside). The throw came with LUCENE-6578 (2015, first released in 5.3.0); 5.2.1 returns the distance. The call throws rather than returning a wrong value, and membership queries are not affected. The window is about 1e-12·b²/2 rad per band edge for a point at offset b, plus about 1e-17 rad of rounding (one representable longitude for the repro point, a few 1e-15 rad near the edge of a 500 km path), so it needs searched-for coordinates. Candidate fix: when neither foot passes, take the one on the point's side (to be checked on very wide paths).

• Cutoff plane: the plane through a segment's start or end point, square to the segment (startCutoffPlane, endCutoffPlane, GeoStandardPath.java:1443-1446). On a straight path like the repro's, the end plane of one segment and the start plane of the next coincide; on a bent path they are two different planes through the same point (each contains its own segment's normal, :1443, :1446).
• Tolerance: SidedPlane.isWithin returns true when |evaluate| < MINIMUM_RESOLUTION = 1e-12 (SidedPlane.java:300-308, Vector.java:26), so a point up to 1e-12 past a cutoff plane still belongs to the segment.
• Foot: the intersection of the segment's great-circle plane with the plane through the point square to it. There are always two, antipodal; the code keeps the one that passes both cutoff planes.

1. computeDistance returns +Infinity if the path does not contain the point, else asks the tree of segments and end caps; a PathNode asks both children and takes the minimum (GeoBaseDistanceShape.java:46-53, GeoStandardPath.java:301-307, :679-686).
2. Segment 1 (longitude 0 to 0.1) contains the repro point by the tolerance: its end cutoff plane evaluates to 9.999917560676863E-13 (PathSegment.isWithin, :1504-1510).
3. pathDistance computes the two feet (:1740-1758). The real foot is at the point's own longitude, 0.10000000000100001, and evaluates to 1.0000056338554941E-12 on the same plane: outside. The other foot, at longitude -3.04, fails the start plane. Neither passes, so it throws (:1766-1774).
4. Why the foot fails: on this straight path, a point at offset b from the centre line and s past the plane evaluates to cos(b)·sin(s), its foot to sin(s). So even in exact arithmetic, points with sin(s) between 1e-12 and 1e-12/cos(b) pass while their foot fails: a window of about 1e-12·b²/2 rad per band edge, plus about 1e-17 rad of rounding. For the repro point (b = 3.45e-6) the geometric part is 6e-24, so rounding decides: the two values differ by 1.4e-17, one ulp of 0.1, and one representable longitude throws. Off the centre line of a 500 km path the window is geometric: 89 throwing longitudes (1.2e-15 rad) at b = 0.035, 355 (4.9e-15 rad) at b = 0.07 (fact-check sweep over every representable longitude).
5. The exception leaves the tree, so neither the joint at the middle point (answers 0.1000034486773084) nor segment 2 (contains the point by a full 1e-12, answers 0.10000344864511553) is ever asked.

The same else-throw sits in pathCenterDistance (:1615), nearestPathDistance (:1663) and pathDeltaDistance (:1717) of GeoStandardPath, and in GeoDegeneratePath (:735, :790, :847), whose nearest and centre distances were shown to throw. The path sort reaches it through Geo3DPointDistanceComparator.copy -> computeMinimumDistance -> computeDistance for each document value (Geo3DPointDistanceComparator.java:137-138, :163-183). Not the same bug: newOutsidePathSort uses computeOutsideDistance, which returns 0 for a contained point and otherwise measures distances to the segments' planes and corners, with no foot choice (GeoBaseMembershipShape.java:46-53, GeoStandardPath.java:1783-1838).

• Who is hit. Callers of GeoPath.computeDistance, computeDeltaDistance, computeNearestDistance and computePathCenterDistance (geom API, @lucene.experimental), and searches sorted by Geo3DDocValuesField.newPathSort. No upstream test calls newPathSort. Membership queries (Geo3DPoint.newPathQuery) are not affected.
• What happens. A RuntimeException from an explicit throw instead of the distance. With the sort, IndexSearcher.search fails for the whole request. No wrong value, hang, extra resource use or index change was observed.
• What it takes. A point about 1e-12 rad (6 micrometres on Earth) past a segment's cutoff plane, inside a window about 1e-12·b²/2 rad wide per band edge for a point at offset b from the centre line, plus about 1e-17 rad of rounding: one representable longitude (1.4e-17 rad) for the repro point, about 6e-16 rad for the sort repro's document, a few 1e-15 rad near the edge of a 500 km path. At interior path points and at a path's end point.
• How likely. By accident practically never: 0 of 200,000 points placed exactly at path vertices and 0 of 200,500 grid points threw; uniform sampling within ±3e-12 rad of a vertex gave about 0 to 5e-6. Sweeps that sample only the band find a few: 10-12 per 1.92 million points on SPHERE, 6 on WGS84; 14 per 800,001 at one of seven offsets on a bent path; 12 per 3.6 million on a straight path (hit counts on each sweep's own lattice, not rates for real data). On purpose, a path can be chosen so that sorting a given stored document throws every time.
• Default vs opt-in. Opt-in: the spatial3d module and its geom API, or the path sort. Impact class crash, likelihood contrived, priority Low.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.RuntimeException: Can't find world intersection for point x=0.995004165272009 y=0.09983341664722949 z=-3.448684587606668E-6
       org.apache.lucene.spatial3d.geom.GeoStandardPath$PathSegment.pathDistance(GeoStandardPath.java:1773)
       org.apache.lucene.spatial3d.geom.GeoStandardPath$PathSegment.distance(GeoStandardPath.java:1544)
       org.apache.lucene.spatial3d.geom.GeoStandardPath$PathNode.distance(GeoStandardPath.java:685)
       org.apache.lucene.spatial3d.geom.GeoStandardPath$PathNode.distance(GeoStandardPath.java:684)
       org.apache.lucene.spatial3d.geom.GeoStandardPath$PathNode.distance(GeoStandardPath.java:684)
       org.apache.lucene.spatial3d.geom.GeoStandardPath.distance(GeoStandardPath.java:306)
       org.apache.lucene.spatial3d.geom.GeoBaseDistanceShape.computeDistance(GeoBaseDistanceShape.java:52)
       org.apache.lucene.spatial3d.geom.GeoBaseDistanceShape.computeDistance(GeoBaseDistanceShape.java:43)
       org.apache.lucene.spatial3d.geom.TestGeoPathDistanceAtCutoffPlane.testDistanceOfPointInsidePath(TestGeoPathDistanceAtCutoffPlane.java:35)

• Contract. GeoDistance: "The following methods compute distances from the shape to a point expected to be INSIDE the shape. Typically a value of Double.POSITIVE_INFINITY is returned for points that happen to be outside the shape." and computeDistance "@return the distance." (GeoDistance.java:28-30, :45-57). GeoPath: the nearest distance is computed "to a point that doesn't need to be inside the shape" (GeoPath.java:26-28); the centre distance is documented as "the shortest distance from the path center to the point" (GeoPath.java:57-80). The internal pathCenterDistance javadocs promise +Infinity outside a segment (GeoStandardPath.java:565-566, GeoDegeneratePath.java:695). newPathSort documents only an IllegalArgumentException for a null field or invalid coordinates (Geo3DDocValuesField.java:214).
• The shape says the point is inside (path.isWithin(p) is true), and its neighbours 1e-15 rad away get a distance.
• Tests. TestGeoPath.testPathDistance uses the same three-point path (half-width 0.1) and expects a distance (for example 0.15 + 0.05) or +Infinity (TestGeoPath.java:22-43).
• History. Before LUCENE-6578 the segment code took the other foot when the first failed a cutoff plane and could not throw; LUCENE-6578 added the strict check and the throw while the tolerance already existed. 5.2.1 returns 0.1000034487 for this point. None of the upstream discussions that added or copied the throw (#7636, #9011, #9004, #9087) or added the sort (#8267) mentions it.
• Precedent. #9292 (LUCENE-8245), a boundary-tolerance exception in GeoComplexPolygon, was fixed as a bug.

The strongest case for "intended" (rated weak by the lenses that built it; rated moderate by a later cross-model fact check, which added the last two points): the throw is a deliberate fail-fast guard in an experimental API at the limit of numerical resolution; geo3d already turns fragile geometry into exceptions (#8411 "Ambiguous boundary points; path too short", #7817 tiny circles); the test passes slightly off-unit coordinates; the guard may protect wide-path geometry.

Why it fails: those are construction-time IllegalArgumentExceptions that reject a degenerate shape. Here the shape is ordinary, it reports the point as inside, and the joint and the neighbouring segment have the answer. The guard's assumption (a point inside the section has a foot inside the section) is wrong by construction, not only at the limit of numerical resolution: in exact arithmetic the foot is 1/cos(b) farther from the cutoff plane than a point at offset b, so off-centre points throw with no rounding involved. The test's coordinates are the doubles GeoPoint(pm, lat, lon) builds on this JVM, off the unit sphere only by rounding like every GeoPoint, and the latitude/longitude form throws the same. That the fallback reaches farther on very wide paths is a reason to review a fix, not for a contained point to throw. "Experimental" allows API changes, not undocumented runtime failures. Verdict: a defect, of low priority.

Fix A was tested through gradle in a scratch worktree of 645d4fe14a20, on the reproduced cases and the spatial3d suite; it was not tested on very wide paths. B and C are alternatives that were not run.

The same hunk replaces the else-throw after the foot choice in pathDistance, pathCenterDistance, nearestPathDistance and pathDeltaDistance of GeoStandardPath and in the three GeoDegeneratePath methods (+42/-14 lines in two files). It is the study's fix sketch with a neutral comment.

         } else if (startCutoffPlane.isWithin(intersectionPoints[1])
             && endCutoffPlane.isWithin(intersectionPoints[1])) {
           thePoint = intersectionPoints[1];
         } else {
-          throw new RuntimeException(
-              "Can't find world intersection for point x=" + x + " y=" + y + " z=" + z);
+          // The point passed the tolerant section test, but rounding put both feet just outside
+          // a cutoff plane: use the foot on the point's side of the world.
+          thePoint =
+              intersectionPoints[0].dotProduct(x, y, z) >= intersectionPoints[1].dotProduct(x, y, z)
+                  ? intersectionPoints[0]
+                  : intersectionPoints[1];
         }

Trade-offs

• Changes behaviour only where the code throws today; no extra cost on the normal path.
• How far outside the segment the foot used can be depends on the point's offset b: up to about 1e-12/cos(b) rad past the cutoff plane. For ordinary widths that is about 1e-12 (in the repro segment 1 then answers 1.0e-12 above segment 2, and the path's minimum returns segment 2's value). For points far off the centre line of a very wide path (half-widths up to π/2 are accepted) it is not small: at cos(b) ≈ 5e-10 an overshoot of 1e-3 rad still evaluates inside the band (a cross-model fact check's analysis, not run). Check wide-path, near-pole and bent-path cases before adopting A as is.
• The two feet are antipodal, so for a point near the path their dot products have opposite signs and the choice is unambiguous.
• Keeps the separate intersectionPoints.length == 0 throws. Seven copies of one block: a small shared helper may read better.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, 2026-11-01: without the fix the repro fails with assertions on and off; with it, it passes with assertions on and off (the study's latitude/longitude form too).
• ./gradlew :lucene:spatial3d:test with the fix: 182 tests (the whole module plus the study's latitude/longitude form of the repro; the exact-coordinate test ran separately), 0 failures, 3 skipped.
• ./gradlew :lucene:spatial3d:check -x test with the fix and the repro as a new test file: passes (google-java-format, ecj lint, forbidden APIs). The full Lucene test suite was not run.
• Earlier: with the study's version of this fix shadowed into the stock jars, the finder's, the independent verifier's, the adjudication's and the cross-model reviewers' own tests pass.

Drop the cutoff tests on the feet and always take the intersection with the larger dot product. For a point inside a segment's corridor this is the same foot, since the other is its antipode.

Trade-offs

Removes the throw and two plane tests per call, but touches the choice for every point, not only the failing branch; not run.

Treat the point as outside this segment when neither foot passes, as the internal javadoc describes, and let the neighbouring segment or end cap answer.

Trade-offs

If no other component claims the point, computeDistance returns +Infinity for a point the path contains: a silent wrong value instead of an exception. Not run.

Method: bounded-exhaustive translation validation of the real jar against an independent reference, in a study unit on the geo3d distance functions (main a9779ef3c193, 2026-10-27).

• The harness compared the path, circle and other shape distances with exact reference formulas over grids of shapes and points. In the path family it reported one exception class: 5 RuntimeExceptions on a straight zero-width path at a lateral offset of 1e-9 next to an interior point.
• A targeted random sweep around path points then found 5 to 55 throwing points per 200,000 sampled within ±2e-12 rad of the cutoff plane on SPHERE, for widths 1e-6 to 1e-2 (on a 1e-15 lattice of along-path offsets that lands on the band edges: a hit count, not a density or a width); an ulp search found a path-point longitude that puts a stored document's decoded point in the window, for the sort repro.
• The finder wrote a three-test JUnit (SPHERE distance, zero-width nearest distance, WGS84 path sort); the one-test minimal repro was reduced from its first test, and this doc's test gives the same doubles as (x, y, z) coordinates.