algorithm - 如何表示 voronoi 图？

Question

我在一个矩形（边界是障碍物）中有一些多边形（障碍物），我想找到 Voronoi 图，这意味着该图显示了与两个障碍物等距的线。

例如（用这个创建，请忽略笑脸和旗帜）：

voronoi 图似乎不是一组多边形（这很容易表示）。这个好像有曲线。它是通过计算每个像素到每个障碍物的距离来生成的。

我见过这个，但它没有多边形，只有点。

如何表示这样的 voronoi 图？

（顺便说一句，如果你有一些关于这个 voronoi 路径规划问题的好文章，我也会很高兴......我只能找到很多 for 点作为障碍。）

Answer 1

您可以使用Boost.Polygon中的Voronoi 图实现。也许如果您想要自己的实现，您可以学习查看 Boost 源代码。

Boost.Polygon 库提供了二维空间中 Voronoi 图数据结构的实现。内部表示由三个数组组成，它们分别包含：Voronoi 单元（表示由 Voronoi 边缘界定的输入站点周围的区域）、Voronoi 顶点（三个或更多 Voronoi 边缘相交的点）、Voronoi 边缘（一维曲线包含与两个最近的输入站点等距的点）。每个基元（单元格、顶点、边）都包含指向其他链接基元的指针，因此始终可以有效地遍历 Voronoi 图。

还有这个链接与来自该数据结构的可视化表示。