启发式方法根据2D/3D点的相互距离对它们进行排序 [英] Heuristics to sort array of 2D/3D points according their mutual distance
问题描述
考虑2D，3D，(4D ...)空间中的点阵列(例如非结构化网格的节点).最初，数组中的点的索引与其在空间中的位置无关.在简单的情况下，假设我已经知道一些最近的邻居连接图.
Consider array of points in 2D,3D,(4D...) space ( e.g. nodes of unstructured mesh ). Initially the index of a point in array is not related to its position in space. In simple case, assume I already know some nearest neighbor connectivity graph.
我想要一些启发式方法，以提高在空间上彼此靠近的两个点具有相似索引(将在数组中接近)的可能性.
I would like some heuristics which increase probability that two points which are close to each other in space would have similar index (would be close in array).
我知道确切的解决方案非常困难(也许类似于旅行商问题)，但是我不需要精确的解决方案，只需增加概率的事情即可.
I understand that exact solution is very hard (perhaps similar to Travelling salesman problem ) but I don't need exact solution, just something which increase probability.
我对解决方案的想法
一些幼稚的解决方案将是:
some naive solution would be like:
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
，但是具体实现及其性能优化尚不清楚.
but the detailed implementation and its performance optimization is not so clear.
不需要预先计算的最近邻居的其他解决方案将基于某些本地性敏感哈希值
Other solution which does not need precomputed nearest-neighbors would be based on some Locality-sensitive_hashing
我认为这可能是一个非常普遍的问题，并且可能存在良好的解决方案，我不想重蹈覆辙.
I think this could be quite common problem, and there may exist good solutions, I do not want to reinvent the wheel.
应用程序:
- 考虑到内存访问通常是图遍历的瓶颈，因此改善了缓存的局部性 它可以加快非结构化网格的插值速度，更具体地说，是搜索靠近smaple的节点(例如，径向基函数的中心).
- improve cache locality, considering that memory access is often bottleneck of graph-traversal
- it could accelerate interpolation of unstructured grid, more specifically search for nodes which are near the smaple (e.g. centers of Radial-basis function).
推荐答案
我会说空间填充曲线(SPC)是将空间中的邻近度映射为线性顺序的标准解决方案.最常见的是希尔伯特曲线和
I'd say 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值对数组进行排序，则通常在数组中 会在空间上闭合点.
Hilbert curves have the best proximity mapping, but they are somewhat expensive to calculate. Z-ordering still has a good proximity mapping but is very easy to calculate. For z-ordering, it is sufficient to interleave the bits of each dimension. Assuming integer values, if you have a 64bit 3D point (x,y,z), the z-value is $x_0,y_0,z_0,x_1,y_1,z_1, ... x_63,y_63,z_63$, i.e. a 192 bit value consisting of the first bit of every dimension, followed by the second bit of every dimension, and so on. If your array is ordered according to that z-value, points that are close in space are usually also close in the array.
此处是将(merge)值交织为z值(nBitsPerValue通常为32或64)的示例函数:
Here are example functions that interleave (merge) values into a z-value (nBitsPerValue is usually 32 or 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进行编码，因为它们通常在标准计算机中使用)，但这会导致非欧几里得距离属性.您可能必须先转换负值，请参见此处，第2.3节.
You can also interleave the bits of floating point values (if encoded with IEEE 754, as they usually are in standard computers), but this results in non-euclidean distance properties. You may have to transform negative values first, see here, section 2.3.
编辑 有两个人回答了评论中的问题:
EDIT Two answer the questions from the comments:
1)我了解如何定期绘制空间填充曲线 矩形网格.但是，如果我随机放置浮动 点，几个点可以映射到一个盒子中.该算法可行吗 在那种情况下?
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位数字的精度.
There are several ways to use floating point (FP) values. The simplest is to convert them to integer values by multiplying them by a large constant. For example multiply everything by 10^6 to preserve 6 digit precision.
另一种方法是使用FP值的位级表示形式将其转换为整数.这样做的好处是不会损失精度，并且您不必确定乘法常数.缺点是欧氏距离度量不再起作用.
Another way is to use the bitlevel representation of the FP value to turn it into an integer. This has the advantage that no precision is lost and you don't have to determine a multiplication constant. The disadvantage is that euclidean distance metric do not work anymore.
它的工作原理如下:诀窍是浮点值没有无限的精度，但被限制为64位.因此，它们自动形成网格.与整数值的不同之处在于，浮点值不是形成二次网格，而是形成矩形网格，其中矩形随着距(0,0)的增大而变大.网格大小由给定点的可用精度决定.接近(0,0)，精度(= grid_size)是10 ^ -28，接近(1,1)，它是10 ^ -16参见
It works as follows: The trick is that the floating point values do not have infinite precision, but are limited to 64bit. Hence they automatically form a grid. The difference to integer values is that floating point values do not form a quadratic grid but a rectangular grid where the rectangles get bigger with growing distance from (0,0). The grid-size is determined by how much precision is available at a given point. Close to (0,0), the precision (=grid_size) is 10^-28, close to (1,1), it is 10^-16 see here. This distorted grid still has the proximity mapping, but distances are not euclidean anymore.
Here is the code to do the transformation (Java, taken from here; in C++ you can simply cast the float to 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值，所得整数相对于<，>，=具有相同的顺序.非欧几里得式的行为是由位串中编码的指数引起的.如上所述，此处在第2.3节中进行了讨论，但是代码的优化程度稍差.
These conversion preserve ordering of the converted values, i.e. for every two FP values the resulting integers have the same ordering with respect to <,>,=. The non-euclidean behaviour is caused by the exponent which is encoded in the bit-string. As mentioned above, this is also discussed here, section 2.3, however the code is slightly less optimized.
2)是否有一些算法如何对这种空间进行迭代更新 如果我的点在空间中移动，则填充曲线吗? (即，无需重新排序 整个数组)
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 )
空间填充曲线施加特定的顺序，因此对于每组点，只有一个有效的顺序.如果移动了点，则必须将其重新插入到由其z值确定的新位置.
The space filling curve imposes a specific ordering, so for every set of points there is only one valid ordering. If a point is moved, it has to be reinserted at the new position determined by it's z-value.
好消息是，小的移动可能意味着一个点可能经常停留在阵列的同一区域"中.因此，如果您确实使用固定数组，则只需移动其中的一小部分即可.
The good news is that small movement will likely mean that a point may often stay in the same 'area' of your array. So if you really use a fixed array, you only have to shift small parts of it.
如果您有很多移动对象，而数组又繁琐，则可能需要研究移动对象索引"(MX-CIF-四叉树等).我个人可以推荐我自己的 PH-树.它是一种使用Z曲线进行内部排序的按位基数四叉树.它对于更新(和其他操作)非常有效.但是，我通常只推荐用于较大的数据集，对于较小的数据集，通常只需一个简单的四叉树就足够了.
If you have a lot of moving objects and the array is to cumbersome, you may want to look into 'moving objects indexes' (MX-CIF-quadtree, etc). I personally can recommend my very own PH-Tree. It is a kind of bitwise radix-quadtree that uses a z-curve for internal ordering. It is quite efficient for updates (and other operations). However, I usually recommend it only for larger datasets, for small datasets a simple quadtree is usually good enough.
这篇关于启发式方法根据2D/3D点的相互距离对它们进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
