这是一个与语言无关的问题，更多的是面向算法设计。
想象一下，我们在 3D 空间中有两个点数组(每个看起来像[(1, 0, 2), (2, 4, 32), ...])
第一个数组表示点的第一个状态，第二个数组表示点移动少量(不一定每个点移动相同的距离)的后期状态。注意：可以删除一些点，并在第二个状态中添加一些新点。
问题：给定这两个数组，如何匹配(以合理的精度)每个移位点到其原始点，同时识别哪些点是新的，并且在第一个状态下不存在？
想法：我在想可以应用某种 k 均值聚类，但我不确定它将如何处理某些点可以在状态之间删除/添加的事实 - 所以我认为这种方法效果不佳。
编辑：
不必在数组中的任何特定位置添加点，并且不必为状态之间的持久点保持顺序。与唯一点之间的距离相比，点在状态之间移动的距离应该相对较小 - 否则这个问题基本上是不可能的。
将每个点与其最近的邻点匹配，除非距离超过阈值。
如果您有多个可能的匹配项，则需要制定一个好的解决策略。
将不匹配的点视为已删除或添加的点。
为了加快速度，请在数据上放置八叉树或格网文件，这样您只需要测试相邻的格网像元，而不是将每个点与其他每个点进行比较。
这基于一个假设：与第一组和第二组之间唯一点之间的距离相比，移位距离非常小(本质上是模糊测量)。
首先，点集的一般结构不受平移、旋转或缩放的显著影响。这为您提供了相当多的选择。
取每个维度(x，y，z等)的最小值/最大值。平移并重新缩放两个点集。确切的缩放比例无关紧要，但您可以采用它，使所有点都是正数，并且在每个维度上都在 0 到 100 之间。这使您可以更一致地比较点。尽管它可能不是严格需要的，并且可能会跳过
然后，您应该在点集 A 和点集 B 之间创建一个双向映射(双向图)，即 O(|A|+ |B|)其中 |A|和 |B|是集的大小。 双向映射示例：a_to_b[(1.001,2.001)] = [(1.005,1.995)]b_to_a[(1.005,1.995)] = [(1.001,2.001)]
如果a_to_b和b_to_a相互映射，那么这是同一点，概率相对较高。
如果没有，那么您可能会看到如下所示的内容：a_to_b[(1.001,2.007)] = [(1.005,1.995)]b_to_a[(1.005,1.995)] = [(1.500, 2.004)]
a_to_b[(1.500, 2.004)] = [(1.495, 2.009)]b_to_a[(1.495, 2.009)] = [(1.500, 2.004)]
由于不再有 1-1 映射，这意味着已添加或删除某些内容。由于 中的值未映射回来，因此可能已被删除。在相反的情况下，很可能被添加。如果已添加，则需要重新运行算法以尝试确定原始最近点是什么。
这可以通过查看不同的点并查看它是否是 1-1 映射的一部分(因此被考虑)来验证。基本上，你要考虑所有的1-1映射点(它们很有可能是同一个点)，然后尝试整理出不匹配的点。
您可能希望获得两个点集的 Delaunay 三角测量，以便更快地查找所有点的最近邻，因为知道哪些点在空间上与给定点相邻。如果我没记错的话，Delaunay 图中的边数是 O(V)，所以每个顶点的平均边是 O(1)。找到最近的点后。但是，您可能需要对Delaunary图进行一些调整，以考虑添加/删除的边缘。
假设：
- 点可能会以随机的角度和长度移动，
- 积分可能会随机消失，
- 积分可以随机添加，并在随机位置，
- 点(在每个数组中)仅由其坐标定义，没有任何类型的 ID。
如果上述所有内容都是正确的，则没有解决方案可以提供合理水平的可靠性。
我可以添加许多例子来证实我的断言，但它看起来非常直观，因此并不是真正需要的。
编辑：
在与 Ted Hopp 讨论之后，我包括了一种基于两个插入的关键假设的替代方法：
点移动一次- 且仅移动一次，
- 可以说任何两点之间的最小初始距离是已知的，我们称之为
Lmin而任何运动的最大距离都是<<LMin，我们称之为Mmax.
有了这两个额外的假设，你可以考虑如下机制(类似JavaScript的代码 - 未检查！
for (i = 0 ; i < Points.Count ; i++) {
for (j = i + 1 ; j < Points.Count ; j++) {
if ((ABS(Array1[i].x - Array2[j].x) > Mmax ) ||
(ABS(Array1[i].y - Array2[j].y) > Mmax ) ||
(ABS(Array1[i].z - Array2[j].z) > Mmax ) ) {
// Distance between two points is for sure equal or bigger than max.
continue ; // Meaning, go to check next point.
}
// The check of the distance is split into two stages
// because, if the first if is true, the actual distance
// calculation is not needed (and hence time is saved).
if (Distance_Between_Points(Array1[i],Array2[j]) > Mmax) {
// Distance between two points is for sure bigger than max.
continue ; // Meaning, go to check next point.
}
// Points appear to be related!!!!!!
..........
}
}