I think there's still some work to do afterwards, though - selecting edges (and perhaps partial edges) from that Voronoi diagram. Basically, the Voronoi diagram is based on the vertices in the polygon and lacks the information about the edges, and about which regions are filled and which are holes. So there must be something left to do to take that extra information into account.
However, once you have the Voronoi diagram, hopefully this extra work can be done in linear time. The Voronoi diagram itself gives an index structure you can use, e.g., for determining which edges of the polygon pass through which Voronoi cells.
I haven't thought this through properly, but one idea is that by clipping the Voronoi diagram to the original polygon, you may get the correct result.
发布评论
评论（1）
http://en.wikipedia.org/wiki/Medial_axis 提示 Voronoi 图链接，以及IIRC Voronoi 图可以在 n log n 时间内计算（Fortunes 算法）。
不过，我认为之后还有一些工作要做 - 从 Voronoi 图中选择边缘（也许是部分边缘）。基本上，Voronoi 图基于多边形中的顶点，缺乏有关边缘的信息，以及有关哪些区域被填充、哪些区域是孔的信息。因此，必须需要采取一些措施来考虑这些额外信息。
然而，一旦你有了 Voronoi 图，希望这些额外的工作可以在线性时间内完成。 Voronoi 图本身提供了一个可以使用的索引结构，例如，用于确定多边形的哪些边经过哪些 Voronoi 单元。
我还没有正确地思考这一点，但一个想法是，通过将 Voronoi 图剪切到原始多边形，您可能会得到正确的结果。
http://en.wikipedia.org/wiki/Medial_axis hints at a Voronoi diagram link, and IIRC Voronoi diagrams can be calculated in n log n time (Fortunes algorithm).
I think there's still some work to do afterwards, though - selecting edges (and perhaps partial edges) from that Voronoi diagram. Basically, the Voronoi diagram is based on the vertices in the polygon and lacks the information about the edges, and about which regions are filled and which are holes. So there must be something left to do to take that extra information into account.
However, once you have the Voronoi diagram, hopefully this extra work can be done in linear time. The Voronoi diagram itself gives an index structure you can use, e.g., for determining which edges of the polygon pass through which Voronoi cells.
I haven't thought this through properly, but one idea is that by clipping the Voronoi diagram to the original polygon, you may get the correct result.