最佳拟合算法，以适应一组线到多边形

Question

我有两套线，设置A和B是已知的这两套所有线路的起点和终点，我想找到旋转而最适合集B到集A转换没有脱屑：

• 没有一个一对一的映射。我相信这排除了Kabsch算法，尽管我可以设想一个使用这个的蛮力算法。
• 组B很可能包含在A.它可能包含一个相当稀疏数量的行线的部分片段。
• 在B中的线将是错误的 - 有可能观察到线中不存在A.
• 有可能的，当然，是多于一个可能的“匹配”

对于一些背景，这是一个粗糙的基于图像的机器人定位系统的一部分。

• Set A是'map' - 数据是从导入的dxf文件导入的。
• 组B是观察到线一组一个。

我已经环顾四周，例如这里：

How to align shapes together? (Geometrical Best-Fit Algorithm)

是这样做的一个聪明的办法？通过图像处理文学形状匹配轻弹似乎是更多的模式匹配的光栅图像 - 可能是这个问题矫枉过正。

我可以在时刻感知的最好方法是使用Hough变换式的方法服用每行中沿乙所述的各条线和具有箱为旋转/转换这些表示。我还没有编码，并尝试过 - 有人想避免重新发明轮子。

任何想法和输入大加赞赏。

Answer 1

的一般解决方案是从集合A中提取的“特征”，并与集B.比较特征

一个例子：考虑所述组A的所有独特的角度和计算的角度的不同的唯一对。在你的例子A中，只有三种可能的情况：（0,0），（0,90），（90,0）。例如：如果角度为0,5,50,93,129，则角度为（0,5），（0,93），（ 5,93），（50,129）是匹配的候选人。一旦你有了候选人，你可以进一步过滤他们。

根据您集合A中有线条的类型，你可以提取相关特征。例如：如果你所有的线都是垂直或平行的，你可以拥有线之间的距离等特征。