计算多边形周围的沃罗诺伊图。

Question

我需要生成一个凹多边形（非凸）的 沃罗诺伊图。我在网上寻找方法，但是一直没有能够弄清如何实现。基本上，我会生成点的凸包，计算对偶点并在这些点之间建立边网络。然而，当遇到内部多边形的边缘时，它必须看起来像形状的边缘一样，就像凸包一样。因此，通过这样做，并将所有边缘剪切在边界处，我应该得到一个沃罗诺伊图，其边缘与内部多边形的边缘相对应且没有在内部多边形两侧的单元格。

让我给你举个例子：

这种方法的问题是单元格穿过内部多边形的边缘，并且单元格结构与多边形形状之间没有视觉关系。

有人知道如何解决这个问题吗？是否已经有一些算法可以实现或接近我想要实现的内容？

感谢任何帮助！

- Alex

Answer 1

您可能能够构建符合 Delaunay 三角剖分（即包含多边形边缘作为约束的三角剖分），然后将 Voronoi 图形成为对偶图。符合性三角剖分将确保三角剖分中的任何边都不与约束边相交 - 所有约束边都将是三角剖分中的一条边。

可以参考 Triangle 包这里，作为这种方法的参考。根据我的经验，这是一个快速而强大的库，尽管它是用 C 而不是 Java 编写的。

我现在不确定您的图中的点（Voronoi 中心）是如何生成的。如果您实际上正在进行多边形域中的网格生成，则可能需要考虑其他方法，尽管 Triangle 包支持（符合性）Delaunay 细化网格生成。

编辑：看起来你也可以直接生成一般线段的 Voronoi 图，可以查看 VRONI 库，这里。回答你的评论 - 我不确定你是否总是期望具有符合一般多边形边界的均匀 Voronoi 图。我预计多边形边界的形状将对边界 Voronoi 单元的最大维度施加限制。

希望这可以帮助到你。

- Darren Engwirda

---

达伦，我正在使用泊松盘采样器（http://devmag.org.za/2009/05/03/poisson-disk-sampling/）生成沃罗诺伊中心，以生成大小相对均等的沃罗诺伊单元。接下来，我会移除那些距离内部多边形太近的点，以减少人工痕迹。 - Alex

我认为Triangle可以帮助我。如果我是正确的，我应该生成一个形状的三角网格，然后使用该网格生成双重点，并从那里构建我的Voronoi？ - Alex

@Alex：是的，这正是我所想的。不过，在某些情况下，强制三角剖分符合一组约束边界时，仍需要小心处理边界。这可能会在局部上牺牲Delaunay标准，导致带有外部外接圆心（Voronoi顶点）的边界三角形。如果您允许足够的边界细化，我认为可以获得符合要求、真正的Delaunay三角剖分，尽管我需要再深入思考一下…… - Darren Engwirda

唯一的问题是，生成的三角形必须具有相似的表面积（误差不超过2倍），因此我不能奢侈地进行大量边界细化。另一方面，内部多边形非常简单（顶点不多），这可能会使它更容易处理？ - Alex

Answer 2

显然，您需要根据更大多边形的限制生成您的沃罗诺伊图。尽管您将其称为多边形，但我注意到您的示例图具有基于样条的边缘。现在让我们暂时忘记它。

您想要做的是确保您从包含多边形（无论是由您生成还是来自其他来源）开始具有相当长度的边缘；方差因子会使其看起来更自然。我可能会选择10-20％的方差。

现在，您的包含多边形由大约相等长度的线段界定，您有了一个基础，可以从中开始生成您的沃罗诺伊图。对于容器上的每个边缘：

• 确定边缘法线（从该段中心向内突出的垂线）。
• 使用边缘法线作为滑动比例尺，在上面放置一个新的 Voronoi 节点中心。距离边缘本身的距离将由你希望平均 Voronoi 单元格“直径”是多少来确定，如果它们都被视为圆形。在你的示例中，看起来可能是30个像素（或者在你的世界单位中的等价物）。同样，你应该对此应用一个变异因素，以便每个单元格中心不是等距离地放置在其源边缘之间。
• 为您新放置的中心生成 Voronoi 单元格。
• 将您的 Voronoi 单元格源点存储在列表中。

当您逐步生成每个点时，您应该开始看到该算法以径向方式将凸“成分区域”细分为您的凹容器。

你可能会想知道这个列表是用来干什么的。显然，你还没有完成，你只生成了你想要的Voronoi图案的一小部分。一旦你创建了这些凹空间的“边界”单元，你不希望新的单元比边界单元更靠近边界，你只希望它们在那个区域内。通过维护一个边界单元源点的列表，你可以确保任何进一步创建的点都在那个区域内。这有点像进行内部Minkowski求和以确保你有一个缓冲区。现在你可以在这个派生的凹形空间中随机生成其余的单元，直到完成。

（买家须知：你必须小心处理上一个步骤。如果任何“通道”区域太窄，那么这个派生空间的边界将重叠，你将得到一个非简单多边形，并且你可能会发现自己尽管努力但仍然把点放在错误的位置。解决方案是确保你从边缘的最大放置距离永远不超过你的最小通道宽度的一半...或者使用其他几何手段，包括Minkowski求和作为一种可能性，以确保你不会得到一个退化的派生多边形。你最终可能会得到一个多多边形，即碎片。）

我自己还没有应用过这种方法，但是虽然肯定会有一些需要解决的错误，但我认为这个总体思路可以让你朝着正确的方向开始。

- Engineer

Answer 3

请查找一篇名为：

《高效计算连续骨架》的论文，作者是David G Kirkpatrick，发表于1979年。

以下是摘要：

提出了一种O(n lgn)算法，用于构建任意n线多边形图形的骨架。该算法基于一种O(n lgn)算法，用于构建广义Voronoi图（我们的泛化将点集替换为仅在端点处相交的线段集）。广义Voronoi图算法采用线性时间算法合并两个任意（标准）Voronoi图。

“仅在端点处相交的线段集”是您描述的凹多边形。

- Tim Gee