Two polygons, one border: storing map shapes as faces and edges

Why two parcels that share a border drift apart in most map editors, and how a planar partition keeps them together. With runnable TypeScript.

Disclosure: I make vectorstream, the library in this post.

I wanted to edit land parcels on a web map. In the tools I tried, I moved a corner of one parcel and a thin gap opened along the border. I closed the gap by hand, moved the next corner, and it opened again. That is when I stopped patching and started on a different data model.

Here is the problem in two parcels. Parcel 101 and parcel 102 touch along one line. Most editors store each polygon as its own ring of coordinates. The shared line then exists twice, once per ring. Nothing keeps the two copies equal. Drag a corner on one parcel and you get a gap or an overlap along the border.

You can patch this with snapping and a validation step after every edit. That works until it doesn't. I decided to remove the cause instead: store the border once.

The model

vectorstream keeps a planar partition. It has three kinds of elements:

• Nodes are points with coordinates.
• Edges are straight segments between two nodes. Each edge is stored as two half-edges, one per direction. A half-edge knows the face on its left.
• Faces are the areas the edges enclose. One outer face surrounds everything and has no outline.

The rule is: every location belongs to exactly one face. A border between two faces exists once, as one edge, and both faces use it.

Four things follow from that, and they are the reason I'd pick this model:

1. Dragging a corner on a shared border moves both faces.
2. Drawing an outline across two parcels splits them. The outline doesn't lie on top of them.
3. Drawing the same outline twice does nothing. The editor reports unchanged.
4. An outline that crosses itself, like a bow tie, is split into the cells it encloses. It isn't rejected.

Point 2 surprised me most when I used it, and it's where people disagree with this design. In an editor with independent polygons, a new shape sits above the old ones. Here, a new shape changes them. If you want overlapping, independent shapes, this model is the wrong tool. Use separate layers, or a different library.

Running it

This example uses only @vectorstream/core. It is a file in the repository, and a test runs it. The test checks the numbers I give below.

import {
  History,
  SpatialIndex,
  checkGeometry,
  importGeoJSON,
  insertPolygon,
  type FaceId,
  type FeatureCollection,
  type Partition,
  type Point,
} from '@vectorstream/core';

export function insertOutline(data: FeatureCollection, outline: Point[]): { partition: Partition; history: History; faces: FaceId[] } {
  const partition = importGeoJSON(data);
  const history = new History(partition, {
    checkInvariants: true, // structure: half-edge pairs, closed cycles, Euler's formula, ...
    validators: [(p) => checkGeometry(p, new SpatialIndex(p), 0)], // geometry: crossings, overlaps
  });
  // All or nothing: if a check fails, the transaction is rolled back and throws.
  const faces = history.transaction('insert-outline', (tx) => insertPolygon(tx, outline));
  return { partition, history, faces };
}

The input is two adjacent parcels that meet at longitude 7.4555, and a building outline that crosses that line. After import, the shared boundary is one edge, not two.

I insert the building outline. The call returns two new faces, one piece per parcel. The partition then has four bounded faces. Each piece keeps the attributes of the parcel it was cut from, so you get parcel: '101' and parcel: '102' back. Inserting the same outline again applies no operation. One undo() restores the original two parcels.

The History object does the safety work. Every change runs in a transaction, and two kinds of check run before it commits. The structure check covers half-edge pairs, closed cycles and Euler's formula. The geometry check covers crossings and overlaps. If either fails, the transaction rolls back. I would not ship an editor on this model without both checks, because a half-edge structure fails in confusing ways when it is slightly wrong.

A decision I'd defend: the grid

Every node coordinate lies on a grid with a mesh size of 2⁻²⁶. That is about 1.5 · 10⁻⁸ coordinate units. With longitude and latitude, it is between one and two millimeters at 51.5° north. The editor rounds inserted and imported coordinates onto this grid, so 51.51 is stored as 51.51000000536442.

That looks like a bug in a debugger. It isn't. Crossings, the snapping of crossing points and area signs are all decided on the rounded values, so they are exact and repeatable. Floating-point predicates that give different answers on a second run are what break topology code, and the grid removes that class of problem.

The cost is real. Data with features smaller than the mesh size needs a finer grid: importGeoJSON(data, { gridExponent }). Coordinates too large for the chosen grid are rejected on import. And layers that exchange faces must use the same exponent. If your data is in a projected system with metre units, check the exponent before you import.

My first version used plain floating-point coordinates and tested crossings on them. Two runs on the same data could disagree about whether a point lay left or right of a line. A border that was fine on the first run came out with a sliver on the second. I threw that version away.

Putting it on a map

The model works without a map. To edit on one, you add an adapter. This excerpt comes from the tested Leaflet quickstart in the docs:

const map = L.map(container).setView([51.5112, 7.4555], 17);
const adapter = new LeafletAdapter(map);
const editor = new Editor(importGeoJSON(data), adapter);
const toolbar = new Toolbar(editor, defaultToolbarEntries());
toolbar.select('draw');

// Every transaction ends in exactly one of three events.
editor.on('change', ({ label }) => console.log('changed:', label));
editor.on('unchanged', ({ label }) => console.log('nothing to do:', label));
editor.on('rejected', ({ label, violations }) => {
  console.warn('rejected:', label, violations.map((v) => v.detail));
});

const save = () => exportGeoJSON(editor.partition);

Leaflet takes [lat, lng], and the editor works with x as longitude and y as latitude. That is why setView reads the other way round. Adapters for MapLibre GL and OpenLayers exist too. Export gives you plain GeoJSON, with holes written as inner rings.

When not to use it

• Your shapes are independent and may overlap. Use ordinary polygons.
• You only need to draw a few shapes and export them. A simpler drawing library is less to learn.
• You need a stable API today. vectorstream is a pre-release. The free packages are on npm at version 0.1.0, so expect changes.

The editor is free under the MIT license. A paid Pro license adds rules between layers. You don't need it for anything in this post.

If your data has shared borders and you've fought gaps and overlaps, try the model on your own parcels: npm install @vectorstream/core @vectorstream/editor @vectorstream/leaflet leaflet. There's a playground at https://vectorstream.dev/playground/. I'd like to hear where it breaks.