Simple spatial ordering or TSP algorithms?

Question

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(N²) time.

I don't need much accuracy so maybe Z-order or Hilbert order 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?

Answer 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 2

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.

Answer 3

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).