6 posts tagged with "technical"

I was debugging a polygon-overlap test that worked locally and failed on the server. Same code. Same input. Different answer.

The function deciding the answer was small. Three points A, B, C; return the sign of (B - A) cross (C - A). That sign tells you whether a vertex is convex or reflex, whether a diagonal stays inside the polygon, whether a point is above a line or below. On x86, LLVM had folded the multiply and the subtract into a single fma — one rounding step instead of two. On WASM there is no FMA, so two roundings. A vertex sitting in the epsilon neighborhood of zero fell on opposite sides. From one bit of disagreement, the whole decomposition forked.

This wasn't a bug in my code. It was IEEE 754 working as advertised. The standard pins down the storage format. It does not pin down behavior. Reassociation, FMA contraction, x87 registers at 80 bits, denormal flush flags — four separate ways to get a different answer from the same inputs. Tightening tolerances doesn't help: convex decomposition is discrete. A vertex is reflex or it isn't. An epsilon at the input is a binary difference at the output.

So I wrote exact-poly, a 2D geometry library that uses no floats at all.

A 10-vertex star decomposed into 5 convex parts. Vertex labels (v0–v9) match input order; part labels (p0.0–p5.3) are emitted by the cascade. Sum of part areas equals the ring area, exactly.

Imagine a global map simulation, a distributed land registry, or a radio frequency allocator. They all share one unbreakable rule: two people cannot own the exact same space. Polygons must not overlap.

Traditional GIS solved this decades ago. But doing it on-chain—inside a strictly consensus-driven network without external servers—has long been considered impossible. Compute limits were simply too strict.

I wrote Mercator, an open-source spatial indexing library for Sui. It lets you register polygons of any shape directly in a smart contract, mathematically guaranteeing zero overlap.

Registering a 4-vertex polygon in Mercator costs about $0.0065. Registering twenty polygons costs exactly the same. The system scales logarithmically, not linearly. To achieve this, I didn't invent anything new. I just borrowed algorithms from 1990s game engines: the Separating Axis Theorem (SAT) for collision detection, and the Morton Z-curve for indexing.

Why are these classic tools only becoming smart contract primitives now? The answer lies in data model architecture. This code simply will not run on EVM, Solana, or Aptos. Here is why.

A spatial index is, at first glance, just a mapping: coordinates go in, parcel IDs come out. The data structure is straightforward. On testnet, though, grid cell dynamic fields consumed 68% of per-parcel insertion cost. Storage was 94–96% of total transaction cost. The data structure was fine. The storage cost wasn't.

Testnet, March 2026. We measured.

Storage was 94–96% of every transaction's cost. Grid cell dynamic fields consumed 68% of per-parcel insertion cost. As we derived in our Dynamic Fields article, the dominant cost term in the insertion formula is $2.7\text{M} \times K$, where K is the number of grid cells a parcel covers:

$$ \text{Cost} = 1\text{M} + 2.7\text{M} \times K + 3\text{M} + 0.5\text{M} \times m \quad (\text{MIST}) $$

A parcel spanning 36 cells paid 97.2M MIST in cell entries alone. That's 97% of the $2.7\text{M} \times K$ term — the dominant cost component, not 97% of total gas. The other terms (base overhead, geometry storage) were fixed. K was the variable. K scaled with geographic size.

This article is about the five approaches we analyzed to cut K. Four of them failed. The fifth — a hierarchical quadtree with depth-prefixed Morton keys — reduced K from up to 36 to exactly 1. This is the story of how we found it.

A new parcel arrives on-chain. Before the protocol writes it to the Index, it must answer one question: does this shape overlap anything already registered? A naive answer is to compare the newcomer against every existing parcel — but that's O(N), and N grows with every registration. On a blockchain, O(N) means gas that grows with the map's popularity. The more successful the protocol, the more expensive it becomes to use.

Computational geometry is the last thing you'd put inside a smart contract. It's complex, it's expensive, and conventional wisdom says handle it off-chain: run the collision check in your backend, then submit a transaction only if it passes. Keep the chain lean. Keep the math elsewhere.

merca.earth does the opposite. The Separating Axis Theorem — a full convex-polygon collision algorithm — runs inside every parcel registration. On-chain. In integer arithmetic. Without floating-point.

This isn't a performance stunt. It's the only way to make the non-overlap guarantee unconditional. Here's why.