算法设计：在 3D 中跟踪移动点 space

Question

这是一个与语言无关的问题，更面向算法设计。

假设我们有两个 3D 点数组 space（每个看起来都像 [(1, 0, 2), (2, 4, 32), ...]）

第一个数组表示点的第一个状态，第二个数组表示点移动少量（不一定每个移动相同的距离）后的状态。 注意：在第二个状态中可以删除一些点并添加一些新点。

问题：给定这两个数组，如何将每个移动点匹配（以合理的准确度）到其原始点，同时还识别哪些点是新的和不存在于第一个状态？

想法： 我在想可以应用某种 k-means 聚类，但我不确定它会如何处理某些点可能已经存在的事实removed/added 在各州之间 - 所以我认为这种方法不会奏效。

编辑：

不一定要在数组中的任何特定位置添加点，并且不一定要为状态之间的持久化点维护顺序。与唯一点之间的距离相比，点在状态之间移动的距离应该相对较小 - 否则这个问题基本上是不可能的。

Answer 1

假设：

点可能会以随机角度和长度移动，
积分可能会随机消失，
可以在随机位置随机添加点，
点（在每个数组中）仅由它们的坐标定义，没有任何类型的 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!!!!!!
        ..........
    }
}

Answer 2

这基于一个假设：与第一组和第二组之间的唯一点之间的距离相比，偏移距离非常小（本质上是模糊测量）。

首先，点集的一般结构不受平移、旋转或缩放的显着影响。这为您提供了很多选择。

对每个维度（x、y、z 等）取 min/max。平移和重新缩放两个点集。确切的缩放比例无关紧要，但您可以使用它，以便所有点都是正数并且在每个维度上都在 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)]

既然不再有一对一的映射，就说明有东西被添加或删除了。由于 a 中的值未映射回，因此它可能已被删除。相反，它可能被添加了。如果添加了它，您将需要重新运行算法来尝试确定原始最近点是什么。

这可以通过查看不同的点并查看它是否是 1-1 映射的一部分（并因此被考虑在内）来验证。基本上，您要考虑所有 1-1 映射点（它们很可能是同一点），然后尝试整理出不整齐匹配的点

您可能希望获得两个点集的 Delaunay 三角剖分，以便更快地查找所有点的最近邻居，因为知道哪些点在空间上与给定点相邻。如果我没记错的话，Delaunay 图中的边数是 O(V)，因此每个顶点的平均边数是 O(1)。一旦找到最近的点。但是，您可能需要对延迟图进行一些调整以说明 added/removed 边。

Answer 3

将每个点与其最近的邻居匹配，除非距离超过阈值。

如果您有多个可能的匹配项，您需要制定一个好的解决策略。

考虑删除或添加不匹配的点。

为了加快速度，将八叉树或网格文件放在数据上，这样您只需测试相邻的网格单元，而不是将每个点与其他每个点进行比较。

算法设计：在 3D 中跟踪移动点 space

Algorithm design: Track moving points in 3D space

algorithm

cluster-analysis