graphics2d - 如何在 voronoi 的边界点上创建弧？

Question

我正在编写一些 2D 图形软件。在我的项目中，我使用了 Voronoi 算法。结果和我预期的一样正确（图1）。然后我想在边界点上添加一些特征，就像（图 2）一样。所以我认为我需要在边界点上实现凹壳，然后在其上创建弧。

图 1。

但是由于凹度参数，我的凹壳不能正常工作。将我的软件结果转换为图 2 的最佳方法和最佳算法是什么。

图 2。

Answer 1

您应该能够绕着 voronoi 走一圈，寻找只有一条相邻边的顶点（从只有一条相邻边的顶点开始不是一个坏主意）。找到第一个，走到下一个，然后用弧线连接边缘，重复直到你的背在第一个边缘。O(N)如果 voronoi 被结构化为图，则该算法应该相当有效。

步行：

步行是通过对边缘进行角度排序并将下一个顺时针边缘带到您开始的边缘来完成的。

例如：

如果角度（以度为单位）是 40、50、60、70，并且之前的边缘在 50 的方向上，那么您将沿着 60 或 40 边缘（取决于您决定顺时针还是逆时针) 但你不会跟随 70，因为它会导致内部而不是坚持外部。

Answer 2

您可以使用凹壳创建 ab/w 位图，并将其与 voronoi 图的每个点进行比较。我在我的 php 实现等高线图中使用了一个 php 函数 imagefilledpolygon：https ://cntm.codeplex.com/ 。

您也可以尝试这个答案并在边界处重建 voronoi 边缘，通常是无限边缘：Colorize Voronoi Diagram。