是否有可能为一个复杂的非凸多边形构造一个中间轴，该多边形具有亚二次时间的孔？你能指点我算法解释吗？
或者也许Java中有一个库？
_2540806_提示Voronoi图表链接，IIRC Voronoi图表可以在n log n时间内计算（Fortunes算法） .
我认为之后还有一些工作要做 - 从Voronoi图中选择边缘（也许是部分边缘） . 基本上，Voronoi图基于多边形中的顶点，缺少有关边的信息，以及填充哪些区域以及哪些是空洞 . 因此，必须要做一些事情来考虑额外的信息 .
但是，一旦你有Voronoi图，希望这个额外的工作可以在线性时间内完成 . Voronoi图本身给出了一个可以使用的索引结构，例如，用于确定多边形的哪些边通过哪个Voronoi单元 .
我没有想到这一点，但有一个想法是通过将Voronoi图剪切到原始多边形，您可以得到正确的结果 .
1 回答
_2540806_提示Voronoi图表链接，IIRC Voronoi图表可以在n log n时间内计算（Fortunes算法） .
我认为之后还有一些工作要做 - 从Voronoi图中选择边缘（也许是部分边缘） . 基本上，Voronoi图基于多边形中的顶点，缺少有关边的信息，以及填充哪些区域以及哪些是空洞 . 因此，必须要做一些事情来考虑额外的信息 .
但是，一旦你有Voronoi图，希望这个额外的工作可以在线性时间内完成 . Voronoi图本身给出了一个可以使用的索引结构，例如，用于确定多边形的哪些边通过哪个Voronoi单元 .
我没有想到这一点，但有一个想法是通过将Voronoi图剪切到原始多边形，您可以得到正确的结果 .