简单多边形内的小圆圈

Question

我一直在研究计算几何问题和 运行 解决以下问题（需要作为子例程），但未能找到任何好的参考或算法。

给定一个简单的（可能是凹的）多边形 P，目标是计算完全包含在 P（空圆）中但至少在两个地方（点或边缘）。如果两个 "places" 恰好是多边形的点，则没有约束。如果我们碰到一个点和一条边，也没有约束。但是如果我们碰到两条边那么它们不应该是连续的（假设顺时针或逆时针顺序）。

我的目标是实现 n^3 或更好的算法 运行。任何指示、参考或想法都会非常有帮助。

谢谢！ 阿米尔

Answer 1

既然您只是在寻找指点或想法，我会很简短。多边形的中轴是在两个或多个位置 (https://en.wikipedia.org/wiki/Topological_skeleton#Centers_of_bi-tangent_circles) 接触边界的圆的中心集。中轴也称为骨架，由直线和抛物线组成的树状图形组成。如果检查此图顶点处的圆（忽略与多边形顶点重合的图顶点），则可以找到最大和最小的圆。您必须进行微调以满足您的 "no consecutive edges" 要求。