我一直在研究计算几何问题，并遇到了以下问题(需要作为子例程)，但未能找到任何好的引用资料或算法。
给定一个简单(可能是凹)多边形 P，目标是计算完全包含在 P(空圆)中但至少在两个位置(点或边)接触多边形的最小圆的中心和半径。如果这两个“地点”恰好是多边形的点，则没有约束。如果我们击中一个点和一条边，也没有任何限制。但如果我们击中两条边，那么它们不应该是连续的(假设顺时针或逆时针顺序)。
我的目标是实现一个按 n^3 或更好的顺序运行的可实现算法。任何指示、引用或想法都会非常有帮助。
谢谢! 阿米尔
最佳答案
由于您只是在寻找指针或想法，所以我会简短地说。多边形的中轴是在两个或多个位置接触边界的圆心的集合 ( https://en.wikipedia.org/wiki/Topological_skeleton#Centers_of_bi-tangent_circles )。中轴也称为骨架，由直线和抛物线组成的树状图形组成。如果检查该图顶点处的圆(忽略与多边形顶点重合的图顶点)，您可以找到最大和最小的圆。您必须进行微调才能满足“无连续边”的要求。
关于computational-geometry - 简单多边形内的小圆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31887638/