<p>A naive solution is to multiply the coordinates by the LCM of the denominators and apply your Z-ordering. The relative order of points will be preserved.</p>

<p>If this will carry you over the word size, you can use a simple $\varepsilon$-net technique. Round each coordinate to within the nearest multiple of $\varepsilon$, for some $\varepsilon$ you pick. I assume you have 2-dimensional points, so this rounding distorts each distance by at most $\pm \sqrt{2}\varepsilon$. This implies that, given a point $p$, if you order the remaining points $P = \{p_1, \ldots, p_n\}$ by their distance from $p$, the rounding will only swap pairs of points $p_i, p_j$ such that $|\|p - p_i\| - \|p - p_j\|| \leq \sqrt{2}\varepsilon$. That is the relative order of points will be preserved unless the points are very close. Then multiply all coordinates by $1/\varepsilon$ and you have integers which are no bigger than $1/\varepsilon$ times the integer parts of the original coordinates.</p>

CC BY-SA 3.0
2011-04-29T22:47:06.797Z
That is some mathy, mathy talk my friend :). I'm not sure what the purpose would be of ordering the points by their distance from some arbitrary point p... but I think scaling by 1/ε is basically step (3) of my answer.
Qwertie
CC BY-SA 3.0
2011-04-29T23:43:35.203Z
@Qwertie The purpose is simply to show that neighborhoods are preserved approximately. Think of it this way: whatever "perfect" ordering you can come up with on the original coordinates, the ordering after rounding to $\varepsilon$ will be the same except points which were closer than $\sqrt{2}\varepsilon$ might be switched. So approximately everything is ok. What I am suggesting is essentially the same as what you did, but I am essentially saying you can afford to round off the least significant bits and that way you need to use not such a large integer to multiply.
Sasho Nikolov
CC BY-SA 3.0
2011-04-29T17:03:26.453Z
2011-04-29T17:03:26.453Z
Sasho Nikolov
<p>A relatively simple way of implementing this would be to simply divide your map recursively into a quad-tree until every node of the quad-tree is either empty or contains at most one point.</p>

<p>Now simply apply your Z-ordering to the nodes of the quad-tree.</p>

CC BY-SA 3.0
2011-04-28T22:04:32.563Z
2011-04-28T22:04:32.563Z
Rehno Lindeque
<p>I decided to try for a Hilbert ordering by (1) computing a <em>square</em> bounding box of all points, (2) converting each point to a fraction (0..1, 0..1) within that bounding box, (3) multiplying the fractional coordinates by a large integer, (4) convert the coordinates to a pair of integers, (5) computing a Hilbert value and (6) sorting by it. Actually computing the Hilbert number proved very tricky to get right. Here's my method for doing so (C#).</p>

<pre><code>ulong ToHilbertOrder(uint x, uint y)
{
    ulong result = 0;

    for (int i = 31; i &gt;= 0; i--)
    {
        uint mask = (1u &lt;&lt; i) - 1;
        uint xb = x &gt;&gt; i;
        uint yb = y &gt;&gt; i;
        uint distance = (xb &lt;&lt; 1) ^ (xb ^ yb);
        x &amp;= mask;
        y &amp;= mask;
        result = (result &lt;&lt; 2) + distance;

        if (yb == 0) {
            // Transpose \
            G.Swap(ref x, ref y);
            if (xb != 0) {
                // Transpose /
                x = mask - x;
                y = mask - y;
            }
        }
    }
    return result;
}
</code></pre>

<p>Despite the embarrassing amount of time it took to write that code, I'm still not really happy with the Hilbert order, because if the points are not uniformly distributed (or fairly one-dimensional), there are often several long-distance jumps in the resulting order.</p>

<p>Oh well, I suppose it's good enough for now. I can't really afford to spend any more time on it.</p>

<p>If I'm not mistaken, the simpler Z-order is achieved simply by interleaving bits, which is <a href="http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN" rel="nofollow">a much simpler task</a>. I decided it was not a very good ordering because adjacent Z-order numbers are sometimes separated by large distances (I didn't actually experiment with it though).</p>

CC BY-SA 3.0
2011-04-29T22:34:45.310Z
2011-04-29T22:43:51.137Z
2011-04-29T22:43:51.137Z
Qwertie
<p>I'm not sure if this is the right place to ask, but I suppose you'll tell me.</p>

<p>I'm writing a program that produces a series of points on a map, and I need to put the points in some linear order so that adjacent points in the list are usually near each other. I just want to tack this on as a minor feature, so I need a simple algorithm that won't be hard to implement, and won't take more than O(N<sup>2</sup>) time.</p>

<p>I don't need much accuracy so maybe <a href="http://en.wikipedia.org/wiki/Z-order_curve" rel="nofollow">Z-order</a> or <a href="http://en.wikipedia.org/wiki/Hilbert_curve" rel="nofollow">Hilbert order</a> would suffice, but the points are floating-point, and I only know how to implement Z-order for integer coordinates.</p>

<p>So, what algorithm would you suggest?</p>

<ds.algorithms><application-of-theory><tsp>
Simple spatial ordering or TSP algorithms?
Qwertie
# Simple spatial ordering or TSP algorithms?

(Asked by: username_0 on 2011-04-28)

I'm not sure if this is the right place to ask, but I suppose you'll tell me.

I'm writing a program that produces a series of points on a map, and I need to put the points in some linear order so that adjacent points in the list are usually near each other. I just want to tack this on as a minor feature, so I need a simple algorithm that won't be hard to implement, and won't take more than O(N2) time.

I don't need much accuracy so maybe [Z-order](http://en.wikipedia.org/wiki/Z-order_curve) or [Hilbert order](http://en.wikipedia.org/wiki/Hilbert_curve) would suffice, but the points are floating-point, and I only know how to implement Z-order for integer coordinates.

So, what algorithm would you suggest?

**Tags:** ds.algorithms, application-of-theory, tsp


---

## 3 answers

### Answer by username_1 on 2011-04-29. Score: 1

A naive solution is to multiply the coordinates by the LCM of the denominators and apply your Z-ordering. The relative order of points will be preserved.

If this will carry you over the word size, you can use a simple $\varepsilon$-net technique. Round each coordinate to within the nearest multiple of $\varepsilon$, for some $\varepsilon$ you pick. I assume you have 2-dimensional points, so this rounding distorts each distance by at most $\pm \sqrt{2}\varepsilon$. This implies that, given a point $p$, if you order the remaining points $P = \{p\_1, \ldots, p\_n\}$ by their distance from $p$, the rounding will only swap pairs of points $p\_i, p\_j$ such that $|\|p - p\_i\| - \|p - p\_j\|| \leq \sqrt{2}\varepsilon$. That is the relative order of points will be preserved unless the points are very close. Then multiply all coordinates by $1/\varepsilon$ and you have integers which are no bigger than $1/\varepsilon$ times the integer parts of the original coordinates.

> **Comments:**
> **username_0**: That is some mathy, mathy talk my friend :). I'm not sure what the purpose would be of ordering the points by their distance from some arbitrary point p... but I think scaling by 1/ε is basically step (3) of my answer.  
> **username_1**: @username_0 The purpose is simply to show that neighborhoods are preserved approximately. Think of it this way: whatever "perfect" ordering you can come up with on the original coordinates, the ordering after rounding to $\varepsilon$ will be the same except points which were closer than $\sqrt{2}\varepsilon$ might be switched. So approximately everything is ok. What I am suggesting is essentially the same as what you did, but I am essentially saying you can afford to round off the least significant bits and that way you need to use not such a large integer to multiply.  

---

### Answer by username_2 on 2011-04-28. Score: 1

A relatively simple way of implementing this would be to simply divide your map recursively into a quad-tree until every node of the quad-tree is either empty or contains at most one point.

Now simply apply your Z-ordering to the nodes of the quad-tree.


---

### Answer by username_0 on 2011-04-29. Score: 0

I decided to try for a Hilbert ordering by (1) computing a square bounding box of all points, (2) converting each point to a fraction (0..1, 0..1) within that bounding box, (3) multiplying the fractional coordinates by a large integer, (4) convert the coordinates to a pair of integers, (5) computing a Hilbert value and (6) sorting by it. Actually computing the Hilbert number proved very tricky to get right. Here's my method for doing so (C#).
ulong ToHilbertOrder(uint x, uint y)
{
    ulong result = 0;

    for (int i = 31; i >= 0; i--)
    {
        uint mask = (1u << i) - 1;
        uint xb = x >> i;
        uint yb = y >> i;
        uint distance = (xb << 1) ^ (xb ^ yb);
        x &= mask;
        y &= mask;
        result = (result << 2) + distance;

        if (yb == 0) {
            // Transpose \
            G.Swap(ref x, ref y);
            if (xb != 0) {
                // Transpose /
                x = mask - x;
                y = mask - y;
            }
        }
    }
    return result;
}

Despite the embarrassing amount of time it took to write that code, I'm still not really happy with the Hilbert order, because if the points are not uniformly distributed (or fairly one-dimensional), there are often several long-distance jumps in the resulting order.
Oh well, I suppose it's good enough for now. I can't really afford to spend any more time on it.
If I'm not mistaken, the simpler Z-order is achieved simply by interleaving bits, which is a much simpler task. I decided it was not a very good ordering because adjacent Z-order numbers are sometimes separated by large distances (I didn't actually experiment with it though).


---

