java - 围绕多边形计算 Voronoi

Question

我需要生成一个 Voronoi diagram围绕多边形内部的凹(非凸)。我在网上找过方法，但我一直无法弄清楚如何做到这一点。基本上，我生成点的凸包，计算对偶点并在这些点之间构建边缘网络。然而，当遇到内部多边形的边缘时，它必须看起来像形状的边缘，就像凸包一样。因此，通过执行此操作并剪裁边界处的所有边，我最终应该得到一个 Voronoi 图，该图在内部多边形的边界处具有漂亮的边，并且内部多边形两侧都没有单元格。

举个例子:

问题是细胞穿过内部多边形边缘，细胞结构和多边形形状之间没有视觉关系。

有人知道如何解决这个问题吗？是否有某种算法已经做到了这一点或接近我想要实现的目标？

非常感谢您的任何输入!

Answer 1

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

看看三角包here ，作为此类方法的引用。根据我的经验，它是一个快速而强大的库，尽管它是用 c 而不是 java 编写的。

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

编辑:看起来您也可以直接形成一般线段的 Voronoi 图，查看 VRONI 库，here .解决您的评论 - 我不确定您是否总是期望有一个统一的 Voronoi 图也符合一般的多边形边界。我希望多边形边界的形状会对边界 Voronoi 单元施加最大尺寸。

希望这对您有所帮助。