Geo3dShape.relate swaps WITHIN and CONTAINS for rectangles the Geo3d factory did not build

In the opt-in Geo3d spatial context (Geo3dSpatialContextFactory, @lucene.experimental), relating a Geo3d shape to a spatial4j Rectangle that is not itself a Geo3d shape returns WITHIN where the answer is CONTAINS and CONTAINS where it is WITHIN; DISJOINT and INTERSECTS are right. A 10-degree circle at (0, 0) is CONTAINS ctx.getWorldBounds() and WITHIN a 2x2 degree RectangleImpl at its centre, while the same boxes built by the Geo3d shape factory give WITHIN and CONTAINS. Geo3dShape.relate(Shape) maps the answers of two helpers with one switch, but the two helpers ask spatial3d the question from opposite sides. Lucene builds such rectangles itself (the Geo3d context's world bounds, every PackedQuadPrefixTree cell), so SerializedDVStrategy IsWithin / Contains queries with the world bounds return the opposite set (and CompositeSpatialStrategy IsWithin misses), and RecursivePrefixTreeStrategy over PackedQuadPrefixTree returns documents far outside small query circles and polygons. Nothing throws. It came in with LUCENE-7951 in 7.1.0 (2017) and fails on every release tested since and on main.

• Spatial context: spatial4j's SpatialContext decides how shapes are built and related. Geo3dSpatialContextFactory (opt-in, @lucene.experimental) makes one whose shapes wrap spatial3d (Geo3d) shapes in Geo3dShape.
• a.relate(b): how a relates to b: WITHIN (a lies inside b), CONTAINS (a covers b), INTERSECTS or DISJOINT. SpatialOperation.IsWithin and Contains test indexedShape.relate(queryShape) for WITHIN and CONTAINS (SpatialOperation.java:84, 134).
• Plain rectangle: a spatial4j RectangleImpl, not built by the Geo3d shape factory. The Geo3d context's ctx.getWorldBounds() is one, and so is every PackedQuadPrefixTree cell (PackedQuadPrefixTree.java:400). ctx.getShapeFactory().rect(...) and WKT envelopes build a Geo3dRectangleShape instead, which is a Geo3dShape.

1. Geo3dShape.relate(Shape) (Geo3dShape.java:54-75) sends a Geo3dShape argument to one helper (:58), any other Rectangle to a second (:59) and a Point to a third (:60), then maps the helper's spatial3d GeoArea constant with one switch (:66-74): GeoArea.CONTAINS -> WITHIN for non-points, GeoArea.WITHIN -> CONTAINS.
2. spatial3d's contract (GeoArea.java:34-38, 46-50): CONTAINS = "The referenced shape CONTAINS this area"; getRelationship(shape)'s "return value is how the GeoShape relates to the GeoArea, not the other way around".
3. The Geo3d-shape helper returns shape.getRelationship(s.shape) (:77-79): the area is this shape and the answer describes the other one. "The other contains this" means "this is WITHIN the other", so the switch is right.
4. The rectangle helper builds a GeoArea from the rectangle and returns geoArea.getRelationship(shape) (:81-92): the area is the rectangle and the answer already describes this shape. The same switch turns it around: WITHIN and CONTAINS come back swapped.
5. For a shape that is neither a point nor a rectangle, spatial4j's RectangleImpl.relate(shape) returns shape.relate(this).transpose() (spatial4j 0.8), so rectangle.relate(circle) is swapped too.

• Exact predicates. SerializedDVStrategy checks IsWithin / Contains for every document, so with ctx.getWorldBounds() or a hand-built rectangle as the query shape it returns the opposite set. CompositeSpatialStrategy checks them only for the candidates of an RPT query: its IsWithin(world bounds) matched 0 of 3 documents, while its Contains(world bounds) gave the correct 0, because it narrows Contains with an RPT Contains query first (CompositeSpatialStrategy.java:139-142).
• PackedQuad prefix tree. When indexing, a cell reported WITHIN the shape becomes a leaf (PackedQuadPrefixTree.java:476-483); when querying, IntersectsPrefixTreeQuery collects every document under a cell reported WITHIN the query shape (IntersectsPrefixTreeQuery.java:71-73). A quarter-world cell that really contains a small circle or polygon is reported WITHIN it, so a 1-degree circle document is indexed as that one quarter-world cell instead of 351 cells, and a half-degree query circle matches every point in its quarter of the world. Rectangles from the Geo3d factory or WKT are not affected: spatial4j relates a cell to any Rectangle with its own rectangle code (a factory rectangle query of the same extent gave 0 false hits).
• Not affected, as tested. Geohash and quad trees build their cells with the Geo3d factory, so RPT over them in the Geo3d context is right (the geohash control gives 0 false hits). No effect was shown for S2 trees or heatmaps, whose world cell and default input shape are ctx.getWorldBounds().

• Who is hit. Applications using Geo3dSpatialContextFactory (opt-in, @lucene.experimental) that relate Geo3d shapes to rectangles the Geo3d factory did not build:
  • RecursivePrefixTreeStrategy over PackedQuadPrefixTree (the non-default prefixTree=packedQuad; a geo context defaults to geohash): wrong cells at index time and at query time for small and medium circles, polygons and other shapes that are neither points nor rectangles (factory and WKT rectangles take spatial4j's own rectangle code and are not affected). Only false positives (0 false negatives in the probe).
  • SerializedDVStrategy with IsWithin or Contains and ctx.getWorldBounds() or a hand-built RectangleImpl as the query shape: the opposite set (in a 342-document probe Contains(world bounds) matched all 342 circles and IsWithin none). CompositeSpatialStrategy IsWithin(world bounds) matched 0 of 3 documents; its Contains(world bounds) gave the correct 0, because it narrows Contains with an RPT Contains query first.
  • Direct relate() calls: a Geo3d shape related to such a rectangle, and the rectangle related to a Geo3d shape that is neither a point nor a rectangle (spatial4j answers those two kinds with its own code).
  • Also, in one constructed case: code that wraps a spatial3d shape in Geo3dShape inside the standard SpatialContext.GEO, as the 7.0 upstream tests did. There the geohash cells are plain rectangles, and a point at (40, 40) matches Intersects of a 5-degree circle at (22.5, 22.5) on 7.1.0 and later, not on 7.0.1.
• Scale of the PackedQuad effect (PackedQuadPrefixTree(12), the factory's default SPHERE model, 20 random Intersects circle queries over 20,000 random points, hits summed over the 20 queries):

The fixed build's surplus is RPT's normal grid approximation. At distErrPct 0.025, circle documents of 0.5, 5 and 20 degrees are indexed as 1 term each instead of 109, 1,151 and 1,072, and the over-coarse cells stay in the index until it is rebuilt (code reading, not run).

• Silent. No exception; the index opens and answers queries normally (its integrity was not checked further); other filter clauses and deletions still apply (0 documents of another tenant and 0 deleted documents returned in the probe).
• How likely. Rare: it takes the opt-in context plus a second uncommon choice, and no report was found since 7.1.0 (2017).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<WITHIN> but was:<CONTAINS>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.spatial.spatial4j.TestGeo3dShapeRelateWorldBounds.testCircleIsWithinWorldBounds(TestGeo3dShapeRelateWorldBounds.java:30)

• Self-contradiction. For a 10-degree circle at (0, 0), the boxes (-1..1, -1..1), (-30..30, -30..30) and the world give CONTAINS, WITHIN, WITHIN from the Geo3d factory and WITHIN, CONTAINS, CONTAINS as RectangleImpl, on SPHERE and WGS84; disjoint and crossing boxes agree. The factory path agrees with exact point membership (0 contradictions in 10,000 random pairs).
• Contracts. spatial4j Shape.relate: "Describe the relationship between the two objects. For example: this is WITHIN other, this CONTAINS other ...", with INTERSECTS the only allowed approximation of WITHIN or CONTAINS. GeoArea.getRelationship (GeoArea.java:46-60): the "return value is how the GeoShape relates to the GeoArea, not the other way around"; OVERLAPS may replace WITHIN "if the shape intersects with the area at even a single point" and CONTAINS only for a shape made of several overlapping subshapes; the opposite nested answer is "not permissible". IsWithin and Contains are documented as OGC CoveredBy and Covers (SpatialOperation.java:75, 124).
• History. Before LUCENE-7951 (035523ba7a8), relate(Rectangle) made the same geoArea.getRelationship(shape) call and mapped WITHIN to WITHIN and CONTAINS to CONTAINS. The commit added the Geo3d-shape helper and one shared mapping written for it, and in the same change moved the rect-relation tests to the Geo3d context, whose rectangles take the other branch.
• On purpose. On lucene-solr#246 the author wrote "I have added the possibility to relate no geo3d rectangles. I was trying to avoid that but I see that for the time being it is necessary.", and on #9000 noted that the Geo3d world bounds are a spatial4j RectangleImpl.
• Tests. No spatial-extras test relates a Geo3d shape to a RectangleImpl or the world bounds, and TestGeo3dRpt uses only geohash, quad and S2 grids. No test, CHANGES entry or discussion accepts the swapped answer.

The strongest case for "intended" (an intended-behaviour checker): every class involved is @lucene.experimental; the Geo3d context is meant to produce only Geo3d shapes, so a RectangleImpl is foreign input; getWorldBounds() is documented only as the coordinate extent, so it could be read as metadata rather than a query shape; and both contracts allow approximate answers.

Why it fails: experimental status covers API changes, not reversed answers; Lucene creates these rectangles itself (PackedQuad cells, the world bounds, the S2 world cell, the heatmap default input), and the rectangle branch was added for them; getWorldBounds() is a public, non-deprecated Rectangle that Lucene's heatmap code uses as a shape; both approximation clauses allow only a weaker answer, never the opposite nested one. Verdict: not intended, a defect (the adjudication and independent checks; the cross-model reviewer rated the intended-behaviour argument weak).

Two options were built and validated in a scratch worktree at a9779ef3c193 with gradle (JDK 25) and with the standalone runner against this page's test, the finder's, the independent reproducer's and the devil's advocate's repros and differential family G1 (patched class shadowed). They gave the same answer on 40,000 random shape and box pairs; that is a sample, not a proof, since the two directions of getRelationship may legitimately differ where the contract allows OVERLAPS. Either needs a regression test; this page's test is one.

Keep the spatial3d computation of 7.0 and earlier (GeoBBox.getRelationship(shape)) and swap CONTAINS and WITHIN before the shared mapping, so both helpers hand it an answer about the other shape. The finder's fix, with the comment shortened to fit the line limit.

    // geoArea.getRelationship(shape) says how this shape relates to the rectangle; the caller
    // expects how the rectangle relates to this shape (as relate(Geo3dShape) returns): transpose.
    final int relationship = geoArea.getRelationship(shape);
    return switch (relationship) {
      case GeoArea.CONTAINS -> GeoArea.WITHIN;
      case GeoArea.WITHIN -> GeoArea.CONTAINS;
      default -> relationship;
    };

Trade-offs

• Smallest change; restores the 7.0 answers exactly (a 7.1.0 port makes the history tests pass there).
• Leaves two helpers that ask from opposite sides, so the class still needs the comment to stay right.
• Indexes built on Geo3d plus PackedQuad while the bug was present keep their over-coarse cells until reindexed (code reading, not run): worth a CHANGES or MIGRATE line.

What the checks validated

• Gradle, scratch worktree at a9779ef3c193, seed DEADBEEF, with this page's test added: :lucene:spatial-extras:check passes: 27 suites, 121 tests (the module's 117 plus the 4 new), 5 skipped, 0 failures, and the format, ecjLint and forbiddenApis checks. The finder's original comment had one 102-character line that fails the format check, hence the rewording.
• Standalone, fix shadowed: this page's test 4/4 (assertions on and off), the finder's 3/3, the independent reproducer's 4/4, its PackedQuad probe 1/1, the devil's advocate's 2/2; the differential harness's family G1 gives 0 contradictions on all three paths (its other families, unrelated findings, report the same counts with and without the fix).
• Earlier, by the hunt: the module's 117 tests with all six fixes of the same hunt unit applied (fix A in the finder's original wording among them; :test, not :check); a 7.1.0 port makes the history tests pass on 7.1.0.

Build a GeoBBox from the rectangle and return shape.getRelationship(bbox), the computation a Geo3dRectangleShape already gets, so the same box gives the same answer in both forms by construction. +5/-5 (GeoAreaFactory.makeGeoArea with four bounds is GeoBBoxFactory.makeGeoBBox anyway, so its import goes).

    GeoBBox bbox =
        GeoBBoxFactory.makeGeoBBox(
            shape.getPlanetModel(),
            r.getMaxY() * DistanceUtils.DEGREES_TO_RADIANS,
            r.getMinY() * DistanceUtils.DEGREES_TO_RADIANS,
            r.getMinX() * DistanceUtils.DEGREES_TO_RADIANS,
            r.getMaxX() * DistanceUtils.DEGREES_TO_RADIANS);

    return shape.getRelationship(bbox);

Trade-offs

• Removes the second direction from the class; plain rectangles use the path the existing rect-relation tests cover.
• Switches plain rectangles from GeoBBox.getRelationship(shape) to shape.getRelationship(bbox). Both gave the same answer on all 40,000 random pairs of a comparison probe (circles and convex polygons, SPHERE and WGS84), but that is a sample, not a proof; B would want broader testing (degenerate and composite shapes) before it is called equivalent.
• The same reindex note as A.

What the checks validated

• Gradle, the same worktree and test: :lucene:spatial-extras:check passes: 27 suites, 121 tests, 5 skipped, 0 failures, and the format, ecjLint and forbiddenApis checks.
• Standalone, fix shadowed: the same repros all pass (4/4, 3/3, 4/4, 1/1, 2/2); family G1 of the differential harness gives 0 contradictions.

Let each helper return a SpatialRelation, as before 7.1.0, instead of sharing one switch.

Trade-offs

Larger diff, same behaviour as A; makes the direction explicit per branch.

Method: randomized differential and model-based testing (non-formal; the finder tagged it semi-formal), in a hunt unit on the spatial4j bridge to spatial3d.

• The harness Geo3dBridgeDiff (family G1) generated random and boundary shapes on SPHERE and WGS84 (seed 5EED220) and required that A.relate(B) never contradict exact spatial3d membership of 2,000 sampled points per pair. B was a Geo3d shape, the same box as a plain RectangleImpl, or ctx.getWorldBounds().
• On stock main: 0 contradictions on the Geo3d-shape path, 999 of 1,000 against the world bounds and 179 of 2,863 against plain rectangles, all WITHIN or CONTAINS; 0 with the fix. Re-run for this doc with the same numbers.
• Reading Geo3dShape.relate gave the cause. The swap had been noted earlier, untriaged, as a side lead in the verification of a different spatial3d bug.
• Verifiers widened the reach: an independent reproducer found the PackedQuad false positive, and the devil's advocate showed the flip with rectangles that Lucene itself creates.