根据相互距离对 2D/3D 点数组进行排序的启发式方法

Question

考虑 2D、3D、(4D...) space 中的点数组（例如 unstructured mesh 的节点）。最初数组中点的索引与其在 space 中的位置无关。在简单的情况下，假设我已经知道一些最近邻连接图。

我想要一些启发式方法来增加 space 中彼此靠近的两个点具有相似索引（在数组中接近）的概率。

我知道精确解很难（可能类似于 Travelling salesman problem ）但我不需要精确解，只需要增加概率的东西。

我的解决思路：

一些天真的解决方案如下：

1. for each point "i" compute fitness E_i given by sum of distances in array (i.e. index-wise) from its spatial neighbors (i.e. space-wise)
   E_i = -Sum_k ( abs( index(i)-index(k) ) ) 
   where "k" are spatial nearest neighbors of "i" 
2. for pairs of points (i,j) which have low fitness (E_i,E_j) 
   try to swap them, 
   if fitness improves, accept

但是具体实现和性能优化不是很清楚

不需要预先计算的最近邻的其他解决方案将基于一些 Locality-sensitive_hashing

我觉得这个可能是比较普遍的问题，可能会有好的解决方案，我不想重新发明轮子

申请：

改进缓存局部性，考虑到内存访问通常是图遍历的瓶颈
它可以加速非结构化网格的插值，更具体地搜索靠近smaple的节点（例如径向基函数的中心）。

Answer 1

我会说 space filling curves (SPC) are the standard solution to map proximity in space to a linear ordering. The most common ones are Hilbert-curves and z-curves (Morton order)。

希尔伯特曲线具有最佳的邻近映射，但计算起来有些昂贵。 Z 排序仍然具有良好的邻近映射，但非常容易计算。对于 z 排序，交错每个维度的位就足够了。假设整数值，如果你有一个 64 位 3D 点 (x,y,z)，z 值是 $x_0,y_0,z_0,x_1,y_1,z_1, ... x_63,y_63,z_63$，即一个192位的值，由每个维度的第一位组成，后面是每个维度的第二位，依此类推。如果您的数组是根据该 z 值排序的，则 space 中接近的点通常通常也在数组中接近。

Here 是将 (merge) 值交织成 z 值的示例函数（nBitsPerValue 通常为 32 或 64）：

public static long[] mergeLong(final int nBitsPerValue, long[] src) {
    final int DIM = src.length;
    int intArrayLen = (src.length*nBitsPerValue+63) >>> 6;
    long[] trg = new long[intArrayLen];

    long maskSrc = 1L << (nBitsPerValue-1);
    long maskTrg = 0x8000000000000000L;
    int srcPos = 0;
    int trgPos = 0;
    for (int j = 0; j < nBitsPerValue*DIM; j++) {
        if ((src[srcPos] & maskSrc) != 0) {
            trg[trgPos] |= maskTrg;
        } else {
            trg[trgPos] &= ~maskTrg;
        }
        maskTrg >>>= 1;
        if (maskTrg == 0) {
            maskTrg = 0x8000000000000000L;
            trgPos++;
        }
        if (++srcPos == DIM) {
            srcPos = 0;
            maskSrc >>>= 1;
        }
    }
    return trg;
}

您还可以交错浮点值的位（如果使用 IEEE 754 编码，因为它们通常在标准计算机中），但这会导致非欧几里得距离属性。您可能必须先转换负值，请参阅 here，第 2.3 节。

编辑两个回答评论中的问题：

1) I understand how to make space filling curve for regular rectangular grid. However, if I have randomly positioned floating points, several points can map into one box. Would that algorithm work in that case?

有多种使用浮点 (FP) 值的方法。最简单的方法是将它们乘以一个大常数，将它们转换为整数值。例如，将所有内容乘以 10^6 以保留 6 位精度。

另一种方法是使用 FP 值的位级表示将其转换为整数。这样做的好处是不会损失精度，而且您不必确定乘法常数。缺点是欧氏距离度量不再起作用。

它的工作原理如下：诀窍是浮点值没有无限精度，但仅限于 64 位。因此它们会自动形成一个网格。与整数值的区别在于浮点值不形成二次网格，而是矩形网格，其中矩形随着与 (0,0) 的距离增加而变大。网格大小取决于给定点的可用精度。接近(0,0)，精度(=grid_size)为10^-28，接近(1,1)，为10^-16见here。这个扭曲的网格仍然有邻近映射，但距离不再是欧几里得。

这是执行转换的代码（Java，取自 here；在 C++ 中，您可以简单地将 float 转换为 int）：

public static long toSortableLong(double value) {
    long r = Double.doubleToRawLongBits(value);
    return (r >= 0) ? r : r ^ 0x7FFFFFFFFFFFFFFFL;
}

public static double toDouble(long value) {
    return Double.longBitsToDouble(value >= 0.0 ? value : value ^ 0x7FFFFFFFFFFFFFFFL);
}

这些转换保留了转换值的顺序，即对于每两个 FP 值，生成的整数相对于 <、>、= 具有相同的顺序。非欧几里得行为是由编码在位串中的指数引起的。如上所述，这也在 here 的第 2.3 节中进行了讨论，但是代码的优化程度略有下降。

2) Is there some algorithm how to do iterative update of such space filling curve if my points moves in space? ( i.e. without reordering the whole array each time )

space 填充曲线强加了特定的顺序，因此对于每组点只有一个有效顺序。如果移动了一个点，则必须将其重新插入到由其 z 值确定的新位置。

好消息是，小的移动可能意味着一个点可能经常停留在数组的相同 'area' 中。所以如果你真的使用一个固定的数组，你只需要移动它的一小部分。

如果您有很多移动对象并且数组太麻烦，您可能需要查看 'moving objects indexes'（MX-CIF-quadtree 等）。我个人可以推荐我自己的 PH-Tree。它是一种使用 z 曲线进行内部排序的按位基数四叉树。它对于更新（和其他操作）非常有效。但是，我通常只推荐它用于较大的数据集，对于小型数据集，一个简单的四叉树通常就足够了。

Answer 2

当且仅当，给定点 p 及其 NN q，则你要解决的问题有意义，则 q 的 NN 为 p。

那是不微不足道的，因为例如两个点可以代表风景中的位置，所以一个点可以代表山的高处，所以从下往上到山上比反过来（从山到底部）花费更多。所以，请务必检查这不是您的情况。

既然TilmannZ已经提出了解决方案，我想强调一下你提到的LSH。我会不选择那个，因为你的点位于一个真正 低维 space，它甚至不是 100，所以为什么要使用 LSH ？

我会选择 CGAL's algorithm on that case, such as 2D NNS, or even a simple kd-tree. And if speed is critical, but space is not, then why not going for a quadtree（3D 八叉树）？我建了一个，它在 8GB RAM 中不会超过 10 个维度。

但是，如果您觉得您的数据将来可能属于更高维度space，那么我建议使用：

LSH 来自 Andoni，非常酷的家伙。
FLANN，它提供了另一种方法。
kd-GeRaF，这是我开发的

根据相互距离对 2D/3D 点数组进行排序的启发式方法

Heuristics to sort array of 2D/3D points according their mutual distance

sorting

caching

distance

nearest-neighbor

computational-geometry