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

Question

我正在寻找一种算法来找到闭合折线的最长弦（“直径”）。不幸的是，该折线不必是凸的，但弦应完全位于曲线内。下面是一个例子：

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

您能否提供一个高效的算法？到目前为止，我们已经实现了 N² 算法，该算法尝试所有顶点对，但即使如此，似乎仍然不正确，因为弦不一定通过两个顶点（或者说是吗？）

我还对相关问题感兴趣，即寻找连接两个顶点的最大线段（如果线段不完全内切，则为该线段中最长的部分在曲线内）。在这种情况下，N² 算法可以工作，但对于大量的点来说速度较慢。

- static_rtti

---

你考虑过可见性多边形算法吗？https://dev59.com/SmrXa4cB1Zd3GeqPEvlo 不确定它是否在这里有用。 - MBo

如果我没错的话，两条线段之间最长的距离必定连接它们的端点（这并不适用于最短距离）。如果这个距离被其他多边形的边“挡住了”，那么挡住距离的是一个顶点。因此，在所有情况下，最长的线段应该经过两个顶点。 - user1196549

@YvesDaoust：我同意，这似乎是真的。 - static_rtti

令人惊讶的是，这个问题在这里或[math.se]都没有出现过，尽管两个地方都有类似的问题。 - AakashM

对于平面折线的“曲线中心”，请参见Circular approximation of polygon (or its part)，@YvesDaoust。 - Spektre

Answer 1

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

要计算线段转换为射线后是否与另一个线段相交，请参见答案： 如何检查线段和从离水平线一定角度的点发出的线射线之间的交点？ 之后，请检查我们的线段列表是否完全在多边形内。以下答案将帮助您进行检查，消除超出边界的线段。 确定线段是否在多边形内 现在，剩下的最长线段应该是答案。

- HelloWorld

---

没错，YvesDaoust用更少的话概括了它！ - HelloWorld

是的，那就是我们最终所做的。还有一个未解决的问题是，我们能否更聪明地只检查顶点对的子集？避免O（N²）的复杂度会很好。 - static_rtti