# Simple spatial ordering or TSP algorithms?

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 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?

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.

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.

• 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 Apr 29 '11 at 22:47
• @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 Apr 29 '11 at 23:43

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);
result = (result << 2) + distance;

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