teeline · algorithms/space-filling-curve
Space-Filling Curve Construction
The curve is a 1D sort key, not the tour path. Each city falls into a cell, the cell gets a curve index, and the tour connects the cities in that index order. Step through the stages to watch the construction.
Project
Each city falls into one grid cell. Cities sharing a cell will share a curve index.
The 1D curve index appears in the Index stage.
Curve order
Hilbert · p = 3 · sort key
| Visit | City | Cell | Index |
|---|---|---|---|
| — | #13 | (0,0) | — |
| cell (1,1) · index — · 2 cities · input order | |||
| — | #14 | (1,1) | — |
| — | #15 | (1,1) | — |
| — | #18 | (2,0) | — |
| — | #16 | (2,2) | — |
| — | #17 | (0,2) | — |
| — | #1 | (0,5) | — |
| — | #5 | (0,7) | — |
| cell (1,6) · index — · 2 cities · input order | |||
| — | #2 | (1,6) | — |
| — | #3 | (1,6) | — |
| — | #4 | (2,7) | — |
| — | #6 | (2,5) | — |
| — | #7 | (5,5) | — |
| — | #11 | (5,7) | — |
| cell (6,6) · index — · 2 cities · input order | |||
| — | #8 | (6,6) | — |
| — | #9 | (6,6) | — |
| — | #10 | (7,7) | — |
| — | #12 | (7,5) | — |
| — | #22 | (7,2) | — |
| — | #23 | (5,2) | — |
| — | #19 | (5,0) | — |
| cell (6,1) · index — · 2 cities · input order | |||
| — | #20 | (6,1) | — |
| — | #21 | (6,1) | — |
| — | #24 | (7,0) | — |
city · #index grid cell shared cell
grid order
p = 3
cities / cells
24 / 20
shared cells
4
largest bucket
2
Curve
Project stage. Hilbert curve, grid order 3 (8 by 8). 24 cities in 20 cells; 4 shared cells.