XYPolygon computes its winding order in float, so XYShape rejects valid polygons with very large coordinates

XYPolygon(float[] x, float[] y, XYPolygon... holes) accepts every finite float coordinate and works out the ring's orientation from a signed-area sum: double windingSum accumulates (x[j] - x[n]) * (y[i] - y[n]) - (y[j] - y[n]) * (x[i] - x[n]), and a sum below 0 is labelled CCW, anything else CW. The accumulator is double, but x and y are float[], so both products are float multiplications. Once coordinate differences reach about sqrt(Float.MAX_VALUE) = 1.8e19 (2^64), the products overflow: in the example triangle both products of a term become Infinity, the term is Infinity - Infinity = NaN, and a NaN sum is labelled CW (infinite terms of opposite sign also give NaN, and a single infinite term can give the wrong sign). Tessellator.tessellate(XYPolygon) links the ring in the order the label implies, so a ring whose correct label is CCW is linked backwards; ear clipping finds no ear and XYShape.createIndexableFields / createDocValueField throw "Unable to Tessellate shape. Possible malformed shape detected." for a valid polygon. A whole-plane box at +/-Float.MAX_VALUE listed clockwise fails the same way, through an overflowing difference. Only that document is affected: no wrong triangulation, index damage or query effect was observed. Present since XY shapes were added (LUCENE-8632, 8.2.0) through 10.6.0 and main. The fix is one statement: cast the differences to double before multiplying, as the lat/lon Polygon already computes the same sum.

• Winding order: the direction a ring's vertices go round. XYPolygon.getWindingOrder() "Returns the winding order (CW, COLLINEAR, CCW) for the polygon shell" (XYPolygon.java:150-153). Lucene labels a negative sum CCW; with y pointing up such a ring runs clockwise (the example triangle does).
• Fan term: the constructor sums, for each vertex pair (j, i) and the last vertex n, (x[j] - x[n]) * (y[i] - y[n]) - (y[j] - y[n]) * (x[i] - x[n]), twice the signed area of one fan triangle.

1. The constructor (XYPolygon.java:48) checks the first vertex and every vertex the loop visits with checkVal (:93, :95, :101, :103; the closing vertex must equal the first, :64, :73), which rejects only non-finite values (XYEncodingUtils.java:35-41; range -/+Float.MAX_VALUE, :28-29).
2. double windingSum = 0d; (:98), then windingSum += (x[j] - x[numPts]) * (y[i] - y[numPts]) - (y[j] - y[numPts]) * (x[i] - x[numPts]); (:106-107). x and y are the float[] parameters: the differences and both products are float; only the term's result is widened.
3. Triangle (0,0), (s,s), (2s,s): the first term is 0, the second s*s - s*(2s). Scale 1: -1, label CCW. Scale 2^66: 2^132 and 2^133 overflow to Infinity in float, the term is NaN (in double it would be -5.44e39).
4. this.windingOrder = (windingSum < 0) ? CCW : CW; (:113): NaN gives CW.
5. Tessellator.tessellate(XYPolygon, boolean, Monitor) (Tessellator.java:155) converts the coordinates to double (:162-163) and calls createDoublyLinkedList(..., polygon.getWindingOrder(), ..., WindingOrder.CW) (:160-167), which keeps the vertex order when the label is CW and reverses it otherwise (:227-235). The mislabelled ring is linked backwards.
6. No vertex of a backwards ring is an ear; after the INIT, CURE and SPLIT passes (:670-689) the Tessellator throws IllegalArgumentException("Unable to Tessellate shape. Possible malformed shape detected.") (:687-688; the same message at :206-207 when no triangle was produced).
7. XYShape.createIndexableFields (XYShape.java:83-85, :96-106) and createDocValueField (:88-90, :109-112) call the Tessellator at :100 and :112 and pass the exception to the caller, before any IndexWriter call.

• Overflow needs coordinate differences of about sqrt(Float.MAX_VALUE) = 1.84e19 (about 2^64) or more. Once a float product (or a difference) overflows, the label can go wrong in three ways:
  • Infinity - Infinity inside one term: both products of a term overflow with the same sign, so the term and the sum are NaN, labelled CW. This is the triangle: its products are 2^126 and 2^127 at scale 2^63 (finite: labelled CCW, indexes) and 2^128 and 2^129 at 2^64 (both Infinity: labelled CW, rejected).
  • Infinite terms of opposite sign: a term with one overflowing product is +Infinity or -Infinity, and two such terms of opposite sign add up to NaN. The notched square (0,0), (0,2^65), (2^65,2^65), (2^20,2^64), (2^65,0) has terms -Infinity, +Infinity, -Infinity, none with both products overflowing; it should be CCW but is labelled CW and rejected, while its exact 2^-64 copy indexes (fact-check probe).
  • One infinite term that outweighs the rest: a single +/-Infinity term carries that term's sign, which can be wrong for the ring. This path also mislabels rings whose correct label is CW.
  • One overflowing product does not always break the label: the independent reproduction's quadrilateral at 2^63 has two -Infinity terms, the correct sign, and is labelled right.
• Or a difference overflows by itself: in a whole-plane box from -Float.MAX_VALUE (-M) to +Float.MAX_VALUE (M) listed (-M,-M), (-M,M), (M,M), (M,-M), the first term starts with (x[0] - x[4]) * (y[1] - y[4]): the y-span M - (-M) is Infinity in float and 0 * Infinity is NaN. That listing is rejected; the opposite listing indexes.
• Mainly rings whose correct label is CCW are hit, because NaN falls back to CW. In the intended-behaviour check's search over about 81,000 random star polygons per orientation, 18, 7 and 2 rings whose correct label is CW were labelled CCW at scales 2e19, 3e19 and 5e19, all through a single infinite term (the fact check's replay). A few wrong labels come from a finite but wrongly rounded sum: 8 of the 4,115 rejected reversed generator rings in the generator check run for the read-only cross-model review. So the root cause is the float evaluation, not only the overflow to NaN.
• Holes are linked by their own getWindingOrder() (Tessellator.java:260) and are affected too (shown in an exploratory run).
• Edges parallel to an axis give zero products, so ordinary axis-aligned boxes mostly avoid it.

• Who is hit. Callers of XYShape.createIndexableFields or XYShape.createDocValueField (both overloads, either checkSelfIntersections value) with the default codec and IndexWriterConfig; nothing to opt into. Also anyone who reads the public XYPolygon.getWindingOrder().
• What it takes. Coordinate differences of about 1.8e19 or more, mostly in a ring whose correct label is CCW (the exact-trigger list above has the rarer cases), or a whole-plane box at +/-Float.MAX_VALUE listed clockwise with y up. Typical projected, CAD and game coordinate systems are far below this magnitude. A plausible boundary case for an indexed geometry is such a whole-plane polygon; an ordinary "match everything" query box (XYShape.newBoxQuery) does not use this code. No user report was found since 2019.
• What happens. The field factory throws "Unable to Tessellate shape. Possible malformed shape detected.", so that document cannot be built; getWindingOrder() returns CW for a CCW ring.
• What does not happen. No silent wrong triangulation (0 in the study's 51,240 tessellations; every verifier saw only clean exceptions), no index damage, no effect on other documents. Query geometries never read the winding order (XYShape.newGeometryQuery -> XYGeometry.create -> Polygon2D), so this winding-label defect is not on the query path.
• Scale in the study's harness. Every simple polygon with 3 to 5 vertices on a 4x4 grid, scaled by 2^66, 2^100 and 2^126 (exact): 21,452 of 51,240 tessellations rejected at each scale, none at scale 1, none with the fix. The share reflects the harness's mix of orientations, not a real-world rate.
• Why the tests miss it. ShapeTestUtil.nextFloat draws coordinates from the full float range (ShapeTestUtil.java:239-240), but every polygon generator emits the orientation Lucene labels CW, which the NaN fallback gets right, and BaseXYShapeTestCase retries any polygon whose tessellation throws (BaseXYShapeTestCase.java:228-233). Reversed, 4,115 of 10,530 generator rings that index forwards are rejected; 0 with the fix.

Public API only: XYPolygon and XYShape.createIndexableFields; the exception comes from the Tessellator before any index is touched. The test uses no randomness, so the seed does not matter (5 of 5 iterations with another seed fail too).

The same file fails unchanged on 10.6.0 with assertions on and off. On releases before 9.1.0 LuceneTestCase lives elsewhere; the study used a framework-free main() there.

As the regression test: this same test, for example as a method in TestXYShape.

cp TestXYShapeLargeTriangle.java $LUCENE/lucene/core/src/test/org/apache/lucene/document/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.document.TestXYShapeLargeTriangle -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (same result)

# gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, assertions on (trimmed)
TestXYShapeLargeTriangle > testTriangleScaledBy2Pow66CanBeIndexed FAILED
    java.lang.AssertionError: expected: the scaled triangle indexes as at scale 1; actual: Unable to Tessellate shape. Possible malformed shape detected.
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:AA81DB64071B184D]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.apache.lucene.document.TestXYShapeLargeTriangle.testTriangleScaledBy2Pow66CanBeIndexed(TestXYShapeLargeTriangle.java:30)

# fact-check probe, main 645d4fe14a20, assertions off
scale 2^0: getWindingOrder()=CCW, createIndexableFields: indexes, 1 field(s)
scale 2^63: getWindingOrder()=CCW, createIndexableFields: indexes, 1 field(s)
scale 2^64: getWindingOrder()=CW, createIndexableFields: IllegalArgumentException: Unable to Tessellate shape. Possible malformed shape detected.
scale 2^66: getWindingOrder()=CW, createIndexableFields: IllegalArgumentException: Unable to Tessellate shape. Possible malformed shape detected.
scale 2^66 reversed: getWindingOrder()=CW, createIndexableFields: indexes, 1 field(s)
float s*s=Infinity, s*2s=Infinity, difference=NaN, NaN < 0 is false; in double: -5.444517870735016E39

# the same probe with the fix: every row indexes; scales 2^0 to 2^66 are labelled CCW

• Any finite float is a valid coordinate. checkVal rejects only non-finite values (XYEncodingUtils.java:34-41); the constructor's other checks are on array lengths, ring closure and nested holes (XYPolygon.java:49-87); upstream TestXYPolygon rejects only NaN and +/-Infinity (testPolygonNaN, testPolygonPositiveInfinite, testPolygonNegativeInfinite, TestXYPolygon.java:81-116).
• The label describes the ring. getWindingOrder(): "Returns the winding order (CW, COLLINEAR, CCW) for the polygon shell" (XYPolygon.java:150-153; the constructor only ever sets CW or CCW, :113). No javadoc says "scale invariant" in those words; the argument is the meaning of "winding order" plus the accepted range.
• Both orientations are supported. "should be CCW, but this will correct" (Tessellator.java:157-158), and the linking reverses a ring whose label differs (:227-235). The same triangle listed the other way round indexes at 2^66, so the rejected one is not malformed. The rejected triangle even runs clockwise with y up, the order the lat/lon Polygon javadoc asks for ("Coordinates must be in clockwise order, except for holes", Polygon.java:31); the XYPolygon javadoc names no order.
• History. Inside the introducing PR (apache/lucene-solr#726, LUCENE-8632), commit 4d0c96f40b8 ("change XYPolygon and XYLine API to accept floats instead of doubles", 2019-06-26) changed the constructor parameters from double[] to float[]; they shadow the then double[] fields and the loop kept reading them. At its parent 1c982b90199 the sum was in double. The author (nknize) wrote in the PR: "Internally we still use doubles for the tessellation but the user must pass floats to the Geometry so it's consistent with the encoding." Nobody discussed the winding sum; the PR was squash-merged. LUCENE-9218 (4a54ffb553a, 8.5.0) made the fields float[] and kept the expression.
• The lat/lon twin is double. Polygon computes the same sum on double[] (Polygon.java:118-134).

The strongest case for "intended" (built by two of the study's verifiers): the Tessellator class notes say it is "sensitive to overflow (e.g, subatomic values such as E-200 can cause unexpected behavior)" (Tessellator.java:49-50); XYShape warns that vertex values are indexed "with some loss of precision" (XYShape.java:71-72); coordinates near 1e19 are not realistic, and the failure is loud (one document gets an exception), not silent; and the shape test base class retries polygons that fail to tessellate.

Why it fails: the overflow happens in the public XYPolygon constructor, not in the Tessellator, which works in double and tessellates these exact polygons once the label is right; the note is about tiny values and predates XY shapes (it came with the lat/lon shape indexing of LUCENE-8396, b5ef13330f1, 2018); the precision warning is about converting from double, and the XY encoding stores floats exactly (XYEncodingUtils.encode is floatToSortableInt, XYEncodingUtils.java:50-52); "not realistic" and "loud" are impact arguments, not intent: the API accepts the range, Lucene's own random tests draw from it, and the public getWindingOrder() returns a wrong label; and the retry's own comment says it skips shapes the "random polygon generator created" as malformed. On PR #12287 its author, heemin32, pointed out that this retry hides XY tessellation failures, and a reviewer, nknize (the author of XYShape), replied: "That try-catch is intentional. The evil, esoteric / invalid test geometry generation is also intentional so we can maximize our test coverage across the tessellator and Shape indexing." So the retry is a deliberate choice for malformed generated shapes, not a statement that valid shapes may be rejected. The argument is a fair one for low priority, not for intended behaviour.

Fix A was validated through gradle in a scratch worktree of 645d4fe14a20; the study's finder and the independent reproduction wrote the same change independently, and the intended-behaviour check, the executed cross-model review and a separate run for the read-only cross-model review ran the finder's file. B was not run.

Widen each float difference to double before the multiplication. A difference of two finite floats is at most 2 x Float.MAX_VALUE (6.8e38), so each product is at most about 4.6e77, far below Double.MAX_VALUE (1.8e308). Double arithmetic on the float inputs is also far more precise, which also fixed every rounding case the study found. The comment line is optional.

--- a/lucene/core/src/java/org/apache/lucene/geo/XYPolygon.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/XYPolygon.java
@@ -103,8 +103,10 @@ public final class XYPolygon extends XYGeometry {
       minY = Math.min(checkVal(y[i]), minY);
       maxY = Math.max(y[i], maxY);
       // compute signed area
+      // in double: float products of coordinate differences overflow from about 1.8e19
       windingSum +=
-          (x[j] - x[numPts]) * (y[i] - y[numPts]) - (y[j] - y[numPts]) * (x[i] - x[numPts]);
+          ((double) x[j] - x[numPts]) * ((double) y[i] - y[numPts])
+              - ((double) y[j] - y[numPts]) * ((double) x[i] - x[numPts]);
     }
     this.minX = minX;
     this.maxX = maxX;

Trade-offs

• One statement in the constructor; one double multiply-add per vertex, once per polygon.
• getWindingOrder() changes only where the float and double sums disagree in sign (NaN included); the upstream geo and shape suites pass unchanged.
• It avoids the float-product overflow but is not an exact orientation predicate: a nearly degenerate ring can still round in double, and a ring whose float sum had rounded to the wrong sign or to 0 gets a new label, so it may be triangulated differently when indexed again.
• Same arithmetic as the lat/lon Polygon (Polygon.java:126-128).

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.
• ./gradlew :lucene:core:test --tests 'org.apache.lucene.geo.*' --tests 'org.apache.lucene.document.TestXY*' --tests org.apache.lucene.document.TestShapeDocValues with the fix: 30 classes (including TestTessellator, 77 tests, TestXYPolygon, 9, TestXYShape, 5, and the repro), 270 tests, 0 failures, 16 skipped by their own nightly or awaits-fix annotations.
• ./gradlew :lucene:core:check -x test with the fix and the repro as a new test file: passes (formatting, ecj lint, forbidden APIs; Error Prone and eclint did not run, as neither is configured on this host). The full Lucene test suite was not run.
• With the fix shadowed into the stock jars, the fact-check probe labels the triangle CCW at 1, 2^63, 2^64 and 2^66 and every case indexes.
• In the study: the finder's harness goes from 21,452 to 0 rejections per scale, the reversed generator rings from 4,115 to 0; the verifiers' and the cross-model reviewer's own tests pass; 27 upstream geo/shape suites pass with this fix and four sibling fixes together (306 passed, 0 failed, 21 aborted by nightly and awaits-fix assumptions).

Derive the ring's direction in Tessellator.tessellate(XYPolygon) from the double coordinates it already builds (Tessellator.java:162-163) instead of trusting polygon.getWindingOrder().

Trade-offs

A larger change in shared code (the lat/lon path uses the same linking), and the public XYPolygon.getWindingOrder() would still return the wrong label.

Tighten checkVal so the products cannot overflow.

Trade-offs

Changes documented behaviour, breaks existing whole-plane boxes at +/-Float.MAX_VALUE, and leaves the rounding cases.

Method: code reading, then measurement with a bounded-exhaustive translation-validation harness (study unit on the geo Tessellator and shapes, main ea57360912ed, 2026-10-26).

• The harness enumerates every simple polygon with 3 to 5 vertices on a 4x4 grid (12,810 shells, 51,240 tessellations per run) and checks each tessellation for coverage, overlap and area against the polygon.
• Scaled by 2^66, 2^100 and 2^126 (exact in float and double): 29,788 ok and 21,452 rejected with IllegalArgumentException at each scale; 0 wrong triangulations (no Steiner points, outside or overlapping triangles, or area mismatches). With the winding sum in double: 51,240 ok, 0 rejected.
• The finder then wrote a public-API JUnit test; the one-test repro was reduced from it.