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

Question

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

图1。

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

图2。

Answer 1

您可以使用凹壳创建黑白位图，并将其与voronoi图的每个点进行比较。我在PHP实现轮廓图中使用了PHP函数imagefilledpolygon：https://cntm.codeplex.com/。

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

Answer 2

您应该能够在voronoi周围走走，寻找仅具有一个相邻边的顶点（从只有一个相邻边的顶点开始这不是一个坏主意）。找到第一个，走到下一个，然后用弧形连接边缘，重复直到您的背部回到第一个边缘。如果voronoi被构造为图形，则该算法应该相当有效O(N)。

步行：

通过对边缘进行角度排序，然后将下一个顺时针边缘移到您开始的边缘，来完成行走。

例如：

如果角度（以度为单位）为40、50、60、70，并且上一条边沿50方向，那么您将沿着60或40边（取决于您是否决定顺时针旋转或逆时针），但您不会跟随70，因为它会引向内部而不是粘在外部。