寻找闭合折线的最大内切弦的算法
Algorithm to find the largest inscribed chord of a closed polyline
我正在寻找一种算法来找到闭合折线的最长弦（“直径”）。不幸的是，折线不一定是凸的，但弦应该完全位于曲线内。这是一个例子：
我正在寻找的解决方案是红色虚线部分。
你能推荐一个有效的算法吗？到目前为止，我们能够实现的最好结果是尝试所有顶点对的 N² 算法，但即使这样似乎也不正确，因为和弦不一定通过两个顶点（或者是吗？）。
我也对相关问题感兴趣，我们正在寻找连接两个顶点的最大线段（或者如果线段未完全内切，则该线段位于曲线内的最长部分）。在这种情况下，N² 算法可以工作，但对于大量点来说速度很慢。
我认为解决方案将始终包含至少两个顶点。因此，计算所有顶点之间的所有线段的列表，包括延伸到接触多边形的另一个线段的线段就可以了。
要计算转换为射线的任何线段是否会与另一条线段相交，请参阅答案：
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
现在剩下的最长的应该是答案。
我正在寻找一种算法来找到闭合折线的最长弦（“直径”）。不幸的是，折线不一定是凸的，但弦应该完全位于曲线内。这是一个例子：
我正在寻找的解决方案是红色虚线部分。
你能推荐一个有效的算法吗？到目前为止，我们能够实现的最好结果是尝试所有顶点对的 N² 算法，但即使这样似乎也不正确，因为和弦不一定通过两个顶点（或者是吗？）。
我也对相关问题感兴趣，我们正在寻找连接两个顶点的最大线段（或者如果线段未完全内切，则该线段位于曲线内的最长部分）。在这种情况下，N² 算法可以工作，但对于大量点来说速度很慢。
我认为解决方案将始终包含至少两个顶点。因此，计算所有顶点之间的所有线段的列表，包括延伸到接触多边形的另一个线段的线段就可以了。
要计算转换为射线的任何线段是否会与另一条线段相交，请参阅答案： 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
现在剩下的最长的应该是答案。