我如何表示voronoi图？

Question

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

例如(用这创建，请忽略笑脸和标志)：

​

​

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

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

我怎么能表示这样一个voronoi图？

(顺便说一句，我也很高兴你有一些关于voronoi路径规划问题的好文章.我只能找到很多作为障碍的积分。

Answer 1

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

Boost.Polygon库提供了在2D空间中Voronoi图数据结构的实现。内部表示由三个阵列组成，分别包含: Voronoi单元(表示以Voronoi边为界的输入点周围的面积)、Voronoi顶点(三个或多个Voronoi边相交的点)、Voronoi边(包含与两个最近输入点等距的一维曲线)。每个原语(单元格、顶点、边缘)都包含指向其他链接原语的指针，因此始终可以有效地遍历Voronoi图。

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