java - 是否可以在次二次时间内为多边形构造中轴？

Question

是否可以为一个复杂的非凸多边形构造一个中轴，该多边形在次二次时间中有孔？你能指出我的算法解释吗？

或者也许在Java中有一个库？

Answer 1

http://en.wikipedia.org/wiki/Medial_axis提示 Voronoi 图链接，IIRC Voronoi 图可以在 n log n 时间内计算（Fortunes 算法）。

不过，我认为之后仍有一些工作要做——从 Voronoi 图中选择边缘（可能还有部分边缘）。基本上，Voronoi 图基于多边形中的顶点，缺乏关于边的信息，以及关于哪些区域被填充以及哪些是洞的信息。因此，必须有一些事情要做才能考虑到这些额外的信息。

然而，一旦你有了 Voronoi 图，希望这些额外的工作可以在线性时间内完成。Voronoi 图本身提供了一个索引结构，您可以使用它来确定多边形的哪些边通过哪些 Voronoi 单元。

我没有正确考虑这一点，但一个想法是通过将 Voronoi 图裁剪到原始多边形，您可能会得到正确的结果。