找到闭合折线的最大内切弦的算法

Question

我正在寻找一种算法来找到闭合折线的最长弦("直径").不幸的是,折线不必是凸的,但是弦应完全位于曲线内.这是一个例子:

我正在寻找的解决方案是虚线红色部分.

你能建议一个有效的算法吗？到目前为止我们能够实现的最好的是N²算法,它尝试所有顶点对,但即使这看起来也不正确,因为和弦不一定通过两个顶点(或者它是什么？).

我也对相关问题很感兴趣,我们正在寻找连接两个顶点的最大段(如果未完全刻录的段,则该段中位于曲线内的最长部分).在这种情况下,N²算法可以工作,但对于大量的点来说速度很慢.

Answer 1

我认为解决方案将始终包含至少两个顶点。因此，计算所有顶点之间的所有线段的列表，包括延伸到接触多边形线段的另一个的线段，就可以解决问题。

要计算转换为射线的任何线段是否与另一个线段相交，请参阅答案： 如何检查线段与从与水平面成一定角度的点发出的线射线之间的相交？

之后检查我们的线段列表是否完全在多边形内。以下答案将允许您检查这一点，消除超出范围的答案。 判断线段是否在多边形内部

现在剩下的最长的应该就是答案了。