algorithm - 如何表示 voronoi 图？

Question

我在一个矩形(边界是障碍物)内有一些多边形(障碍物)，我想找到 Voronoi 图，这意味着显示与两个障碍物距离相等的线的图。

例如(使用 this 创建，请忽略笑脸和旗帜):

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

我看过this , 但它没有多边形，只有点。

如何表示这样的 voronoi 图？

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

Answer 1

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

The Boost.Polygon library provides implementation of the Voronoi diagram data structure in 2D space. The internal representation consists of the three arrays, that respectively contain: Voronoi cells (represent the area around the input sites bounded by the Voronoi edges), Voronoi vertices (points where three or more Voronoi edges intersect), Voronoi edges (the one dimensional curves containing points equidistant from the two closest input sites). Each of the primitives (cell, vertex, edge) contains pointers to the other linked primitives, so that it's always possible to efficiently traverse Voronoi graph.

还有这个link使用该数据结构的可视化表示。