匹配点集的算法
Algorithm for matching point sets
我有两组点 A 和 B，而这些点可以是 2D 或 3D。两组具有相同的大小 n，这是相当低的 (5 - 20)。
我想知道这些集合的一致性如何。也就是说，理想情况下，我会找到点之间的配对，使得所有欧几里德对距离之和 d(A,B) 最小。所以
d(A,B) = \sum_{i=1}^n ||A_i - B_i||_2
最终结果用于与其他点集进行比较。所以，例如：
- A = (1,1), (1,2), (1,3)
- B = (1,1), (2,2), (1,3)
会给我 d(A,B) = 1.
- C = (1,1), (2,1), (3,1)
- D = (2,1), (2,2), (3,1)
会给我 d(C,D) = 1.414.
有什么好主意吗？
例如，您可以将问题建模为分配问题 (Wikipedia link), where you define the cost C_ij of assigning point A_i (from set A) to point B_j (from set B) to be equal to the distance between them. This assignment problem can then be solved using the Hungarian algorithm (Wikipedia link)。
我有两组点 A 和 B，而这些点可以是 2D 或 3D。两组具有相同的大小 n，这是相当低的 (5 - 20)。
我想知道这些集合的一致性如何。也就是说，理想情况下，我会找到点之间的配对，使得所有欧几里德对距离之和 d(A,B) 最小。所以
d(A,B) = \sum_{i=1}^n ||A_i - B_i||_2
最终结果用于与其他点集进行比较。所以，例如：
- A = (1,1), (1,2), (1,3)
- B = (1,1), (2,2), (1,3)
会给我 d(A,B) = 1.
- C = (1,1), (2,1), (3,1)
- D = (2,1), (2,2), (3,1)
会给我 d(C,D) = 1.414.
有什么好主意吗？
例如，您可以将问题建模为分配问题 (Wikipedia link), where you define the cost C_ij of assigning point A_i (from set A) to point B_j (from set B) to be equal to the distance between them. This assignment problem can then be solved using the Hungarian algorithm (Wikipedia link)。