5

我一直在寻找一种算法,可以优化两个坐标列表之间的距离并选择哪个坐标应该放在一起。

假设我有清单 1:

205|200
220|210
200|220
200|180

清单 2:

210|200
207|190
230|200
234|190

坐标之间的计算距离:

205|200 to 210|200 == 5.00
205|200 to 207|190 == 10.20
205|200 to 230|200 == 25.00
205|200 to 234|190 == 30.68

220|210 to 210|200 == 14.14
220|210 to 207|190 == 23.85
220|210 to 230|200 == 14.14
220|210 to 234|190 == 24.41

200|220 to 210|200 == 22.36
200|220 to 207|190 == 30.81
200|220 to 230|200 == 36.06
200|220 to 234|190 == 45.34

200|180 to 210|200 == 22.36
200|180 to 207|190 == 12.21
200|180 to 230|200 == 36.06
200|180 to 234|190 == 35.44

该算法将选择:

205|200 to 230|200 == 25.00
220|210 to 207|190 == 23.85
200|220 to 210|200 == 22.36
200|180 to 234|190 == 35.44

算法会选择这些数字,因为它们将是距离之间差异最小的组。条件:

  1. 坐标只能用于每个列表中的坐标
  2. 如果 List 1 或 List2 大于它仍然只使用每个坐标一次,但它会尝试获得最小的距离方差并且对未使用的坐标不做任何事情。

如果您需要更多说明,请询问。

PS我看过匈牙利算法,它似乎可以完成这项工作,但并不完全符合我的预期。匈牙利算法只会尝试使与所有坐标的距离最小,这可能意味着最小的方差,但并非每次都因为方差比最小距离优化更重要。

4

1 回答 1

1

ICP算法值得一看。它旨在解决类似的问题

于 2012-05-25T05:09:07.170 回答