合并二维线段

Question

我正在寻找一种方法来连接2D线段。一条线段由两个向量点组成，即线段的起点和终点。

我想要连接看起来应该形成同一直线的线段，如果它们朝向完全不同但恰好有2个接近的点，则不想连接线段。我将在计算机视觉系统中使用此系统，因此获得的线段不会是完美的，即方向可能略有偏差，线段可能不是完整长度等等。

我认为以下3个示例涵盖了我想要连接的线段类型：

谢谢

- Jkh2

Answer 1

这是一个计算几何问题，相关的教科书中可能有一些解决方案，但是请注意这些问题通常非常难以解决，并且有限精度是一个真正的问题。关于这个问题（在2D中），你可能正在寻找的术语是线条近似共线。通常，确定线是否共线的方法是首先将它们放入向量表示中，然后取向量之间的点积，这将等于线之间夹角的余弦值。因此，如果这个值接近于1，则它们接近共线，应该被合并。

下一个问题是确定线是否足够接近需要合并。你可以通过找到相交的线或找到起始和结束点非常接近的线来解决这个问题...总的来说并不容易，但你可以以这种方式找到95%的线。

- fairidox