An XYShape point query exactly on a polygon's corner can miss the polygon: XY triangles can be stored clockwise, and the point-in-triangle test rejects the second corner of a clockwise triangle

An XYShape point query placed exactly on a polygon's corner can miss the polygon. Index the triangle (0,1) (1,2) (3,3) with XYShape.createIndexableFields and query each corner with XYShape.newPointQuery: INTERSECTS gives 1, 0, 1 hits and DISJOINT gives 0, 1, 0, while the same triangle moved by (8, 8) matches at all three corners. Two pieces combine. ShapeField.encodeTriangle makes stored triangles counter-clockwise, but it checks the winding on the encoded ints, and the XY encoding (floatToSortableInt) keeps the order of floats but not their spacing. So the tessellator's counter-clockwise triangle can look clockwise on the ints, and the swap meant to fix it leaves the stored triangle counter-clockwise as ints and clockwise as floats. The query tests the decoded floats with Component2D.pointInTriangle, which rejects the second corner of a clockwise triangle and accepts everything else. Every release from 8.5.0 to 10.5.2 and main is affected, with the default codec and no error. A one-function fix in pointInTriangle (accept when all three orientations are >= 0 or all <= 0) fixes it without reindexing.

• Triangles: XYShape.createIndexableFields tessellates a polygon into triangles and stores each one with its three corners, called a, b and c in the code.
• Winding: a triangle is counter-clockwise (CCW) when its signed area (the determinant) is positive, clockwise (CW) when it is negative. GeoUtils.orient(a, b, c) returns +1, -1 or 0.
• The XY encoding: XY coordinates are floats and are stored as NumericUtils.floatToSortableInt(x). This keeps the order of floats and is exact, but it is not linear: within one power-of-two range it is a plain scaling, and from one power-of-two range to the next the scale halves or doubles.

ShapeField.encodeTriangle takes the corners in the tessellator's order, rotates them so that the smallest x comes first (ShapeField.java:157-182 at a9779ef3c193), and then ("change orientation if CW", :214-228) swaps b and c when GeoUtils.orient of the encoded ints is -1. On the encoded ruler the values 0, 1, 2 and 3 sit at 0, 254, 256 and 257 (in units of 2^22): the encodings of 0 and 1 are 254 x 2^22 apart, those of 1 and 2 are 2^23 apart, and those of 2 and 3 are 2^22 apart. The tessellator hands over the triangle as (1,2) (0,1) (3,3); after the rotation it is a = (0,1), b = (3,3), c = (1,2).

The swap meant to normalise the winding is what makes the float triangle clockwise. On the lattice {0..5}^2 every one of the 6,768 tessellated triangles reaches encodeTriangle counter-clockwise as floats, and the 240 that end up stored clockwise as floats all got there through this swap. In metre-like data the same happens at 2^19 = 524,288 or 2^22 = 4,194,304: below 524,288 one unit holds 32 float steps, above it 16. The repro's hexagon has x from 517,494 to 539,509, and its triangle at the missed corner goes through the same swap.

XYShapeQuery decodes each stored triangle to floats and calls intersectsTriangle (XYShapeQuery.java:93-99); for a point this is Component2D.pointInTriangle (Point2D.java:83-95).

int a = orient(x, y, aX, aY, bX, bY);
int b = orient(x, y, bX, bY, cX, cY);
if (a == 0 || b == 0 || a < 0 == b < 0) {
  int c = orient(x, y, cX, cY, aX, aY);
  return c == 0 || (c < 0 == (b < 0 || a < 0));
}
return false;

At p = corner b the point lies on both edges that meet there, so a == 0 and b == 0, and the method returns c >= 0, where c = orient(b, c, a) is the triangle's own winding: true for a counter-clockwise triangle, false for a clockwise one. At corners a and c two orientations are 0 as well and the method returns true for either winding; edge and interior points are accepted for either winding too. An exhaustive comparison on the stock jar over every triangle and point of the integer grid {-4..4}^2 (43,046,721 cases) found that the stock method and the winding-independent fix disagree in exactly the 247,824 cases where p is corner b of a clockwise triangle. At the level of signs the two differ only for (a, b, c) = (0, 0, -1) of the 27 sign triples; reading that as "corner b of a clockwise triangle" assumes exact orientations, which holds here (every product is a small exact integer) but not for GeoUtils.orient in general.

• A polygon's corner is missed only if every stored triangle that touches it misses it: always for a lone triangle, and in the repro's hexagon too, where only one of its four stored triangles touches the missed corner.
• INTERSECTS misses the document; DISJOINT (no triangle intersects) returns it. CONTAINS (Point2D.withinTriangle, same test) also answers differently per corner, but its correct boundary answer is debatable.
• The experimental XYShapeDocValues.relate(Component2D) also decodes XY triangles to floats and calls intersectsTriangle (ShapeDocValues.java:919-934), so with a point component it likely misses the same corner (not executed); the fix covers it too.
• LatLonShape is not affected in the scope checked: its decoding is a positive linear scaling of the encoded ints, so stored triangles decode with their encoded, counter-clockwise winding (0 of 281,203 grid triangles stored clockwise as decoded doubles).

• Who. Applications that index polygons with XYShape (building and floor plans, CAD drawings, game maps, projected GIS data in metres) and run XYShape.newPointQuery, or newGeometryQuery with an XYPoint, with INTERSECTS or DISJOINT at a coordinate that equals a polygon vertex exactly: corners shared by neighbouring shapes, a click snapped to a vertex, or a re-query with stored vertex coordinates.
• Default configuration. Public, non-experimental API, no special setting. The codec does not matter (the triangle encoding is in the field's bytes, the test runs at query time): the repro (Lucene's randomized test configuration) fails under every randomized test codec it met, and the independent reproducer's JUnit and the diagram probe, both with a plain new IndexWriterConfig(), fail with the default codec (Lucene104 in the adjudication's run).
• Silent. No exception and no assertion; the same with assertions off.
• How often (the finder's random-polygon probe; not re-run by the verifiers): polygons with a missed corner were 0.30% (60 of 20,000 triangles) and 0.16% (32 of 19,562 hexagons) in projected-metre ranges, 0.07% (13 of 18,933) in a narrower metre window, 0.15% (29 of 18,937) around 1,000-1,900, and about 3% (590 of 19,878; 650 of 19,533) around the origin. With the fix, 0 (re-run for the hexagon range and the lattice triangles only). On the lattice {-2..2}^2, 8 of 2,148 triangles miss a corner. These rates come from one synthetic generator (random star-shaped polygons, fixed seed, checked on their stored triangles), not from real data: they show that the miss is not confined to toy coordinates, not how often real queries hit it.
• Blast radius. A miss affects only the documents that hold a polygon with such a corner, and only point queries at exactly that corner; the index itself is not changed.
• Not affected. LatLonShape (scope check); points indexed with XYPointField, which stores no triangles.
• Rare in practice. Nobody has reported it since 8.5.0 (2020); the registry rates the likelihood "rare" and the priority low.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: INTERSECTS point query at vertex (1,2) expected:<1> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.document.TestXYShapePointQueryAtPolygonVertex.testPointQueryAtVertexOfClockwiseTriangle(TestXYShapePointQueryAtPolygonVertex.java:43)

• Contract. XYShape.newPointQuery: "create a query to find all indexed shapes that comply the QueryRelation with the provided point" (XYShape.java:236-239). CHANGES for LUCENE-8736: "Point in Polygon now correctly includes boundary points. Box and Polygon relations with triangles have also been improved to correctly include boundary points."
• Written for both windings. The method compares signs (a < 0 == b < 0, c < 0 == (b < 0 || a < 0)) instead of testing all three >= 0, and its javadoc states no precondition: "Compute whether the given x, y point is in a triangle; uses the winding order method".
• Upstream tests pass clockwise triangles to Component2D. TestLatLonShape.testTriangleCrossingPolygonVertices calls Component2D.intersectsTriangle on (-5,0) (10,0) (-5,-15), which is clockwise, and expects true.
• Position should not matter. The exact translation by (8, 8) makes the miss disappear; the independent reproduction's metre-like triangle is fixed by a (+10000, +10000) move.
• Precedent. LUCENE-8973 (#10016, fixed 2019): "XYShape encoding is not lineal and shapes loose their spatial relationship. XYRectangle2D should work then on the float space." A review comment on #1017 (2022): "XY queries should work on the float space."
• Why tests missed it. The random point-query check draws random points, which rarely land exactly on a stored vertex, and validates them with the same Component2D code; and the TRIANGLE branch of BaseShapeEncodingTestCase computes its "original" and "encoded" predicates from the same original coordinates, so it cannot see a change caused by the encoding.

The strongest case for "works as designed": Component2D is @lucene.internal, and ShapeField documents that triangles are stored counter-clockwise (since LUCENE-8581, 2018; LUCENE-9642 moved the check after the corner rotation), so a clockwise triangle would be a broken precondition, not a predicate bug.

Why it fails: the counter-clockwise guarantee holds only for the encoded ints, not for the floats the query actually tests; Lucene's own winding swap turns a triangle the tessellator emitted counter-clockwise into a clockwise float triangle, for a valid public XYPolygon (the reversed ring stores the same triangle); no precondition is documented; and the public result changes under an exact translation. The fallback argument, that boundary answers are best effort because GeoUtils.orient "does not yet have the floating point tricks to be exact", fails too: every product here is a small exact integer, so the miss is branch logic, not rounding. The XYShape precision WARNING covers double to float only; these coordinates are already floats, which the XY encoding keeps exactly. Maintainers may still see a decoded clockwise triangle as an encoding-side precondition violation and prefer to fix it there or with the narrowest predicate change; the fixes section lists both. Verdict: not intended (the intended-behaviour check, high confidence; the cross-model reviews rated the intended-behaviour argument weak).

One fix was applied in a scratch worktree at a9779ef3c193 and run through gradle (seed DEADBEEF); the two alternatives were not run. The zero-size box query is a user-side workaround checked on the two repro shapes only.

In Component2D.pointInTriangle, inside the bounding-box check, compute all three orientations and accept the point when they are all >= 0 or all <= 0. The independent reproducer's own fix has the same logic (only the comment differs).

     if (x >= minX && x <= maxX && y >= minY && y <= maxY) {
       int a = orient(x, y, aX, aY, bX, bY);
       int b = orient(x, y, bX, bY, cX, cY);
-      if (a == 0 || b == 0 || a < 0 == b < 0) {
-        int c = orient(x, y, cX, cY, aX, aY);
-        return c == 0 || (c < 0 == (b < 0 || a < 0));
-      }
-      return false;
+      int c = orient(x, y, cX, cY, aX, aY);
+      // inside or on the boundary for either winding order
+      return (a >= 0 && b >= 0 && c >= 0) || (a <= 0 && b <= 0 && c <= 0);
     } else {

Trade-offs

• Exactly one answer changes: the two return statements differ only for the sign triple (0, 0, -1) of the 27, which in exact arithmetic means the point is the second corner of a clockwise triangle (stock false, fix true); on every grid triangle and point that is the only difference. Counter-clockwise triangles get the same answers as before.
• Other callers. pointInTriangle is also called from Line2D, Rectangle2D, Circle2D, Polygon2D and SpatialQuery. SpatialQuery's two calls test encoded triangles, which are counter-clockwise or degenerate in encoded space (asserted by decodeTriangle), so in exact arithmetic their answers cannot change (GeoUtils.orient rounds when encoded ints are far apart, so a near-degenerate encoded triangle was not ruled out; not audited). For the float-space callers the change can only turn "outside" into "inside" when the tested point is exactly the second corner of a clockwise decoded triangle, the answer they already give at the other two corners; their user-visible effects were not audited separately.
• No reindexing and no format change: the stored triangles stay as they are.
• Cost: the fix computes the third orientation on every call inside the bounding box, where the stock code can reject after two; no benchmark was run. pointInTriangle is shared by several geometries, so measure it, or take the narrower variant below.

What the checks validated

• Stock main a9779ef3c193 (scratch worktree, gradle, seed DEADBEEF): the repro fails 3 of 3 with assertions on and off; the closest suites (TestPoint2D, TestXYShape, TestXYPolygonShapeQueries, TestXYMultiPolygonShapeQueries, TestXYPointShapeQueries, TestXYMultiPointShapeQueries) pass: 29 tests, 4 skipped.
• With the fix: the repro passes 3 of 3 with assertions on and off; the same closest suites pass (29 tests, 4 skipped); every geo and shape suite of lucene/core (the geo package, document *Shape*, TestXY* and TestLatLon*, search TestXY* and TestLatLon*; 54 classes with the repro) passes: 587 tests, 40 skipped, 0 failures; the whole :lucene:core:test passes: 8,892 tests, 322 skipped, 0 failures (run after the fix runs in the same worktree; its command line was not recorded, but every compile task in its log is up to date with the fix build, so it ran the fixed sources with the repro); ecjLintMain, ecjLintTest and checkGoogleJavaFormat pass, so the repro file is formatted as Lucene requires.
• After the comment-only edit of the repro (2026-10-28): it fails 3 of 3 on stock main and passes 3 of 3 with the fix, assertions on and off, and google-java-format 1.37.0 leaves it unchanged; fix-with-test.diff was regenerated and passes git apply --check.
• Exhaustive predicate comparison on the stock jar: the fix differs from the stock method only at the second corner of a clockwise triangle (247,824 of 43,046,721 grid cases on {-4..4}^2); at the sign level only for (0, 0, -1) of the 27 sign triples.
• Earlier hunt runs: the finder's random-polygon probe finds 0 missed corners with the fix in the two settings re-run with it (the lattice triangles and the hexagon range); the independent reproducer ran 355 upstream geo and shape tests with the same logic (0 failures), and the finder 584 together with another patch of its unit (40 skipped, 0 failures).

Keep the stock code and also accept when a == 0 && b == 0 in the inner return: return c == 0 || (a == 0 && b == 0) || (c < 0 == (b < 0 || a < 0));.

Trade-offs

Same answers as the recommended fix at the sign level, without computing the third orientation where the stock code rejects early; harder for a reader to see that it is winding-independent.

What the checks validated

Over all 27 sign triples it gives the same answers as the recommended fix (sign-enum.txt). Not run in Lucene.

Make ShapeField.encodeTriangle choose the winding of XY triangles from the float coordinates, so stored triangles decode counter-clockwise.

Trade-offs

encodeTriangle is shared with LatLon and works on ints; decodeTriangle asserts the encoded-space invariant, and the 3-bit reconstruction code relies on it ("Triangles are encoded with CCW orientation and might be rotated to limit the number of possible reconstructions to 2^3"), and a triangle that is counter-clockwise as floats can be clockwise as ints, so this is an encoding change. Existing indexes keep their clockwise triangles until reindexed. It touches the same swap block as LFV-204 (edge flags); test both together.

In XYShapeQuery (and other XY decoders), swap b and c, and the edge flags, when the decoded float triangle is clockwise.

Trade-offs

No reindexing, but it fixes only the call sites that decode, costs one orientation test per visited triangle, and the edge-flag swap must be right for withinTriangle (CONTAINS).

Query XYShape.newBoxQuery(field, relation, x, x, y, y) instead of newPointQuery at an exact vertex.

Trade-offs

Checked on two shapes only; a box query goes through a different relation code path.

What the checks validated

On main, for both repro shapes: INTERSECTS [1, 1, 1] and [1, 1, 1, 1, 1, 1], DISJOINT all 0, where the point query gives [1, 0, 1] and [1, 1, 1, 0, 1, 1]. Not an exhaustive check.

Method: metamorphic bounded-exhaustive translation validation of the stock main jar (semi-formal tier), in a hunt unit on orientation-preserving transforms of geo shapes.

• Every document and query of a 6 x 6 integer-lattice family (9,156 documents, including all 6,768 non-degenerate lattice triangles, and 1,631 queries) was indexed and queried as-is and under 22 exact transforms: quarter-turn rotations, reflections with vertex reversal, cyclic vertex rotation, translations by +-2^k and reversal. All four relations were run on the BKD, doc-values, point and point doc-values paths, and the correct side of each mismatch was decided by an exact DE-9IM reference plus the closed-set convention.
• With the fixes of the registered geo bugs shadowed in, most of the remaining mismatches, 80,128, were point or multi-point queries at polygon vertices; with this bug's fix also shadowed in, none of those remained, and the rest came from separate findings, mainly circle queries after ±2^23 translations. A component-level probe then showed that exactly the 240 lattice triangles stored clockwise in float space miss their second corner (0 with the fix).
• The finding was reduced to a public-API JUnit and checked by an independent reproducer, an intended-behaviour devil's advocate, reading-only reviews by a model from another family (OpenAI GPT-5.6), an adjudication, a history, prior-report and security follow-up, and an audit. Found 2026-10-27 on main a9779ef3c193.