Why Floats Fail in Geometric Determinism: The Case for Integer Arithmetic

In the world of computational geometry, a single bit of difference can be the difference between a successful operation and a catastrophic failure. For many developers, the assumption is that the same code with the same input will yield the same result regardless of the machine it runs on. However, as the creator of exact-poly discovered, this is not always true when floating-point numbers are involved.

When debugging a polygon-overlap test, the author found that a function determining whether a vertex was convex or reflex worked locally but failed on a server. The culprit was not a bug in the logic, but the way different architectures handle floating-point operations. On x86, the compiler used Fused Multiply-Add (FMA) to reduce rounding steps; on WASM, it did not. This tiny discrepancy in rounding caused a vertex sitting near zero to flip signs, triggering a domino effect that completely altered the polygon's decomposition.

The Illusion of IEEE 754 Reproducibility

Many developers believe that IEEE 754 compatibility ensures consistent behavior. In reality, the standard primarily defines how floats are stored, not how they behave across different execution environments. Several mechanisms can leak reproducibility:

• Intermediate Registers: The x87 FPU often keeps values in 80-bit precision, rounding only when spilling to memory, whereas ARM or WASM may not.
• Fused Multiply-Add (FMA): fma(a, b, c) performs a multiply and add with a single rounding step, producing a more accurate but different result than separate operations.
• Reassociation: Compilers using flags like -ffast-math may rewrite (a + b) + c as a + (b + c), which changes the rounding order.
• Denormals: The "flush-to-zero" flag can be silently flipped per process, altering how subnormal numbers are handled.

As one commenter noted, while some environments like the JVM (via strictfp or StrictMath) attempt to guarantee strict reproducibility, the fundamental nature of floating-point arithmetic remains an approximation. For applications requiring absolute determinism—such as lockstep game simulations or ZK witness generation—these approximations are insufficient.

The "One Bit" Problem in Convex Decomposition

In geometry, the cross_sign(A, B, C) function is the primary signal for decision-making. It determines if a turn is left, right, or collinear. When three points are nearly collinear, one machine might return +1e-12 and another -2e-13.

This sign flip is critical because convex decomposition is a discrete process. A vertex is either reflex or it isn't. If a sign flips, a different vertex is identified as reflex, leading to a different starting cut and a completely different decomposition graph. Using an epsilon (e.g., "round to a micrometer before comparing") does not solve this, as any epsilon zone will eventually capture a real polygon and cause the behavior to fork.

The Solution: Exact Integer Arithmetic

To achieve bit-for-bit identity across x86, ARM, and WASM, exact-poly abandons floats entirely in favor of integers. By mapping coordinates to a fixed scale (e.g., 1 unit = 1 micrometer for geodesy), the library ensures that the sign of a cross product is a matter of bit-logic, not approximation.

Managing the Integer Budget

Integer arithmetic requires a careful choice of scale. With i64::MAX (approximately $9.2 \times 10^{18}$), developers must balance the unit of measure against the maximum coordinate size. For geodesy, a scale of $10^6$ allows for micrometer precision while covering the entire planet's circumference with ample headroom.

Preventing Overflow with i128

The cross product formula—$(bx - ax)(cy - ay) - (by - ay)(cx - ax)$—can easily exceed the limits of i64. To prevent this, exact-poly employs a strict rule: coordinates are stored as i64, but any multiplication is performed in i128.

Crucially, the library widens the values before subtraction: (bx as i128) - (ax as i128). Subtracting in i64 first can lead to overflows that result in garbage data even when stored in an i128 container.

Implementing a Robust Decomposition Cascade

Because no single convex decomposition algorithm is perfect for all inputs, exact-poly uses a "cascade" of algorithms. If the first fails, the next takes over:

1. ExactPartition: A greedy partitioner prioritizing reflex vertices.
2. Bayazit: A recursive approach that can insert Steiner points (mid-edge vertices).
3. EarClip + Hertel-Mehlhorn: A triangulation followed by a merge step to reduce the number of parts.

If all three fail, the library rotates the ring (changing the starting vertex) and retries. This heuristic works because pathological cases are often tied to a specific vertex traversal order.

Handling the Edge Cases of Discrete Math

Moving to integers introduces new challenges that aren't present in continuous float math:

• Midpoint Precision: Simple integer division (a + b) / 2 discards the low bit. The library uses round_div2 to ensure points don't drift.
• Steiner Point Snapping: Midpoints must be nudged if they land too close to existing vertices to prevent accidental collinearity.
• Bookkeeping: Synthetic vertices must be tagged to ensure the final output vertex count matches the input, preventing downstream validation failures.

Conclusion: Agreement Over Precision

Floating-point numbers are designed for precision, but integer arithmetic is designed for agreement. When two different processes must arrive at the exact same answer, the precision of a float is irrelevant if the rounding direction differs. By utilizing i128 for intermediate calculations and avoiding floats entirely, exact-poly provides a deterministic foundation for geometric operations that is guaranteed to be identical across any architecture that supports 64-bit integers.