计算多边形周围的Voronoi

Question

我需要在凹面(非凸面)内部多边形周围生成Voronoi图.我在网上寻找方法,但我无法弄清楚如何做到这一点.基本上,我生成点的凸包,计算双点并在这些点之间建立边缘网络.但是,当遇到内部多边形的边缘时,它必须看起来像形状的边缘,就像凸包一样.因此,通过这样做并剪切边界处的所有边缘,我应该得到一个Voronoi图,它具有内部多边形边界的良好边缘,并且没有位于内部多边形两侧的单元格.

让我给你举个例子:

这个问题是单元格穿过内部多边形边缘,并且单元格结构和多边形形状之间没有视觉关系.

有人知道如何解决这个问题吗？是否有一些算法已经做到这一点或接近我正在努力实现的目标？

非常感谢你的任何输入!

Answer 1

您也许能够构建一致的 Delaunay 三角剖分（即包含多边形边作为约束的三角剖分），然后将 Voronoi 图形成为对偶图。一致的三角剖分将确保三角剖分中没有边与约束边相交 - 所有约束边都将是三角剖分中的边。

请查看此处的Triangle 包，作为此类方法的参考。根据我的经验，它是一个快速且强大的库，尽管它是用cnot编写的java。

我不确定现阶段我是否理解图中的点（Voronoi 中心）是如何生成的。如果您实际上希望在多边形域中生成网格，那么尽管 Triangle 包支持（符合）Delaunay 细化网格生成，但可能还有其他方法可以考虑。

编辑：看起来你也可以直接形成一般线段的Voronoi图，查看VRONI库，在这里。解决您的评论 - 我不确定您是否总是可以期望拥有一个也符合一般多边形边界的统一的 Voronoi 图。我预计多边形边界的形状会给边界沃罗诺伊单元施加最大尺寸。

希望这可以帮助。