我需要围绕多边形内的凹（非凸）生成Voronoi 图。我已经在网上寻找方法，但我无法弄清楚如何做到这一点。基本上，我生成点的凸包，计算对偶点并在这些点之间建立边缘网络。但是，当遇到内部多边形的边缘时，它必须看起来像形状的边缘，就像凸包一样。因此，通过这样做并剪裁边界处的所有边缘，我最终应该得到一个 Voronoi 图，该图在内部多边形的边界上有很好的边缘，并且内部多边形的两侧没有单元格。
让我给你举个例子：
这样做的问题是单元格穿过内部多边形边缘，并且单元格结构和多边形形状之间没有视觉关系。
有人知道如何解决这个问题吗？是否有一些算法已经做到这一点或接近我想要实现的目标？
非常感谢您的任何意见！
您可能能够构建一个符合要求的 Delaunay 三角剖分（即包含多边形边作为约束的三角剖分），然后将 Voronoi 图形成为对偶。一致的三角剖分将确保三角剖分中的任何边都不会与约束边相交 - 所有约束边都将是三角剖分中的边。
在这里查看 Triangle 包，作为此类方法的参考。以我的经验，它是一个快速而强大的库，尽管它c不是用java.
我不确定在这个阶段我是否理解点（Voronoi 中心）是如何在您的图表中生成的。如果您实际上希望在多边形域中进行网格生成，那么可能需要考虑其他方法，尽管 Triangle 包支持（符合）Delaunay 细化网格生成。
编辑：看起来你也可以直接形成一般线段的 Voronoi 图，查看 VRONI 库，在这里。解决您的评论-我不确定您是否总是可以期望拥有一个统一的 Voronoi 图，该图也符合一般的多边形边界。我希望多边形边界的形状会对边界 Voronoi 单元施加最大尺寸。
希望这可以帮助。
显然，您需要根据更大多边形的约束生成 Voronoi 图。尽管您将其称为多边形，但我注意到您的示例图具有基于样条的边。让我们暂时忘记这一点。
您要做的是确保从包含多边形（无论是由您生成还是从其他来源生成）开始时具有相当等长的边；方差因子会使这看起来更自然。我可能会选择 10-20% 的差异。
既然您的包含多边形由大约相等长度的线段界定，您就有了开始生成 Voronoi 图的基础。对于容器上的每个边缘：
随着您逐步生成每个点，您应该开始看到该算法以径向方式细分了凹容器的每个凸“成分区域”。
您可能想知道该列表的用途。好吧，显然，您还没有完成，您只生成了您想要的全部 Voronoi 细分的一小部分。一旦你创建了凹空间的这些“边界”单元，你不希望新单元生成比边界单元更靠近边界，你只希望它们在那个区域内。通过维护边界单元源点的列表，您可以确保您创建的任何其他点都在该区域内。这有点像采用内部 Minkowski 和来确保您有一个缓冲区。现在，您可以在这个派生的凹形空间中随机化其余的单元格，直到完成。
（注意事项：您必须小心上一步。如果任何“通道”区域太窄，则此派生空间的边界将重叠，您将拥有一个非简单多边形，您可能会发现自己放置尽管您很努力，但仍指向错误的位置。解决方案是确保您与边缘的最大放置距离永远不会超过最小通道宽度的一半......或使用其他一些几何方法，包括 Minkowski 求和作为一种可能性, 以确保您不会以退化的派生多边形结束。很有可能您将以多多边形结束，即片段。）
我自己还没有应用这种方法，但是虽然肯定会有错误需要解决，但我认为总体思路会让你朝着正确的方向开始。
查找名为：
Kirkpatrick, David G于 1979 年撰写的“连续骨架的有效计算” 。
这是摘要：
提出了一种 O(n lgn) 算法，用于构建任意 n 线多边形图形的骨架。该算法基于用于构造广义 Voronoi 图的 O(n lgn) 算法（我们的泛化将点集替换为限制为仅在端点相交的线段集）。广义 Voronoi 图算法采用线性时间算法来合并两个任意（标准）Voronoi 图。
“线段集被限制为仅在端点处相交”是您描述的凹多边形。