c++ - 匹配线段 - 稳健且快速的方式

Question

我有从单个图像数据中提取的 2D 线段，并希望与从其他源中提取的 3D 线段匹配。为此，首先我想使用共线性方程（我知道外部方向参数）将 3D 线段投影到图像空间。由于两条线段都在同一个坐标系中，现在我想找到与该线最匹配的线段。

我正在寻找一种快速且强大的算法来匹配相应的线段，以便稍后更新我的 3D 线段。

如果有人对此有任何想法，请提出一些建议。提前致谢。

Answer 1

您正在查看类似于line segment intersection的问题。所以不出所料，它的解决方案也可能相似。

直接的方法是将每个 2D 段与每个 3D 段进行比较，最佳匹配是与实际长度和位置最接近的匹配。实际是 2D 段。这类似于 O(AB)，其中 A 是 2D 段的数量，B 是 3D 段的数量。

您可以通过按字典顺序对 2D 线段进行排序来加快该方法的速度，然后使用我在这个问题中询问的相同类型的算法来获取所有线段，其 x 值在一定数量内的一个或两个的预期 x 值线段终点*。在最坏的情况下，你仍然可能会遇到 O(AB)，但平均时间应该更接近 O(B log A)。虽然，目前还不清楚你是否可以根据你所说的使用这种方法，所以这一段应该更多地被认为是一个大纲。

比 O(B log A) 或 O(A log B) 更快可能需要这是一个经过充分研究的问题。

• 如果您按字典顺序对 2D 端点进行排序，则您可能会摆脱 1 个端点。