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

Question

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

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

您能为此推荐一个有效的算法吗？到目前为止，我们能够实现的最好结果是尝试所有顶点对的 N² 算法，但即使这样似乎也不正确，因为和弦不一定通过两个顶点(或者确实如此？)。

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

Answer 1

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

要计算转换为射线的任何线段是否会与另一条线段相交，请参阅答案: How do you check for intersection between a line segment and a line ray emanating from a point at an angle from horizontal?

之后检查我们的线段列表是否完全在多边形内。下面的答案将允许你检查，消除那些越界的。 determine if line segment is inside polygon

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