Version 2 (modified by Sam Hocevar, 17 years ago) (diff)

Cantor polynomial

Numbering tiles

If we want a straightforward way to linearly index tiles without necessarily knowing the image size, we can use the following enumeration:

0 1 3 6 10 15 21
2 4 7 11 16 22 29
5 8 12 17 23 30 38
9 13 18 24 31 39 …
14 19 25 32 40 …
20 26 33 41 …
27 34 42 …

One way to generate these values is using the Cantor polynomial:

$n = \dfrac{(x + y) (x + y + 1)}{2} + y$

Efficiently inverting that polynomial is not trivial. Here is one way to do it:

$k = E(\dfrac{\sqrt{8n+1}-1}{2})$ $y = n - \dfrac{k (k + 1)}{2}$ $x = k - y$