问题标签 [voronoi]

Is there a code/library that can calculate a Voronoi diagram for planes (parallelograms) in 3D? I checked Qhull and it seems it can only work with points, in its examples Voro++ works with different size of spheres but I couldn't find anything for polygons.

In this image (sample planes in 3d) the parallelograms are 3D since they have a thickness, but in this case the thickness will be zero.!

使用这个程序中找到的voronoi/delaunay图生成库，它基于Fortune的算法的原始实现，以一组随机点作为输入数据，我能够得到以下输出数据：

1. 来自Delaunay Triangulation的边列表，这意味着对于每个输入点，我可以看到哪些输入点是它的邻居。它们似乎没有任何特定的顺序。
2. 来自Voronoi 图的顶点对列表，我可以用它一次绘制一条线的 Voronoi 图。同样，显然没有特定的顺序。
3. 一个未命名的点对列表，似乎与 2 相同，但顺序不同。
4. 在 Voronoi 图中形成的顶点列表，显然也没有特定的顺序。

这是使用此库对我的程序进行测试运行的数据示例：

虽然如果我只需要绘制 Voronoi 和 Delaunay 图，上述数据就足够了，但对于我尝试使用这些图进行的实际工作来说，这些信息还不够。我需要的是一个由 Voronoi 顶点形成的多边形字典，由每个多边形围绕的输入点索引。优选地，对于每个多边形，这些点将按顺时针顺序排序。

有了上述信息，我可以隐式地将数据分配给每个区域，必要时将数据分配给角点，告诉哪些区域共享边（使用 Delaunay 边），并进行相应的分析。

简而言之，我如何使用可用的数据来组合一个字典，其中键是输入点之一，由该键索引的数据是形成周围多边形的 Voronoi 顶点的列表？或者，这些信息是否隐含在我获得的数据中？

我正在实施财富的扫描线算法来计算 Voronoi 图。我的主要参考资料是 de Berg 等人的“计算几何：算法和应用”，虽然他们对该主题的报道非常清楚，但他们忽略了几个小但重要的细节，而这些细节我一直难以解决。我在网上搜索过帮助，但其他网站要么提供比教科书更高的概述，要么提供与本书提供的完全相同的伪代码。

我需要一种方法来确定由海滩线上的三重弧线确定的一对断点是收敛还是发散，以便检测即将发生的圆形事件。似乎要做出决定，我需要了解随着 Fortune 算法的进展断点追踪的 Voronoi 单元边缘的形状。例如，如果我能找到断点跟踪的边缘的斜率，我可以计算断点形成的两条线及其各自斜率相交的位置，并根据该结果决定它们是否收敛。但是，我不知道如何获取有关斜坡的信息，只知道断点的当前位置。

我必须使用的唯一信息是三个站点的 x、y 位置和扫描线的当前 y 坐标（我使用的是水平扫描线）。

实际上，我确实有一个确定收敛的想法。给定两个地点，它们定义的两段海滩线之间的断点仅由扫描线的当前位置决定。想着记录下两个断点的位置，暂时将扫掠线推进一点，记录下它们的新位置。因为正常Voronoi图中的边不弯曲，如果新断点对之间的距离小于旧对之间的距离，则断点收敛；否则，它们会发散。但这似乎既危险（我不知道它是否总是有效）又丑陋。肯定有更好的方法。

任何想法都会受到赞赏，尤其是伪代码（如果可能，使用类似 C# 的语法）。我也知道有一些计算几何库可以用来获取 Voronoi 图，但这是个人学习练习，所以我想自己实现算法的所有部分。

我将使用一组数千个点。我可以实现或使用现有的财富算法实现来生成点的 Voronoi 图，但我的应用程序还要求我知道每个 Voronoi 单元的邻接关系。

更具体地说，对于任何 Voronoi 单元，我需要知道与其相邻的单元。在这一点上，我不关心输出或存储方法，因为我可能会按摩实现以对我有利。

有没有人知道算法，或者更好地知道可以完成小区邻接确定的已实现算法？我将要做的工作是在 python 中，但任何事情都会很棒，因为我可以轻松地翻译代码。

谢谢！

CGAL 库中有一个用于分段的 VD 实现，但它仅适用于欧几里德度量情况。是否可以在那里使用我自己的度量函数？

假设我们想要对一个具有 N 个点的矩形表面进行 Voronoi 分区。Voronoi 细分导致 N 个区域对应于 N 个点。对于每个区域，我们计算其面积并将其除以整个表面的总面积 - 称这些数字为 a1，...，aN。它们的总和等于一。

假设现在我们有 N 个数字的预设列表，b1，...，bN，它们的总和等于 1。

如何找到用于 Voronoi 分区的 N 个点的坐标的选择（任意），例如 a1==b1、a2==b2、...、aN==bN？

编辑：

经过一番思考，Voronoi 分区可能不是最好的解决方案，关键是要对表面进行随机不规则划分，以使 N 个区域具有适当的大小。Voronoi 在我看来是合乎逻辑的选择，但我可能弄错了。

我正在尝试计算 matlab 中每个 Voronoi 单元的面积，但我被卡住了。我在网上找到了这段代码：

此代码不起作用，因为 v 中的点之一是 [Inf,Inf]。这是无穷大的一点。我怎样才能绕过这个问题？

我有大约 50,000 个 3D 数据点，我从新的 scipy 运行 scipy.spatial.Delaunay（我使用的是 0.10），这给了我一个非常有用的三角测量。

基于：http ://en.wikipedia.org/wiki/Delaunay_triangulation （“与 Voronoi 图的关系”部分）

...我想知道是否有一种简单的方法可以到达这个三角剖分的“双图”，即 Voronoi Tesselation。

有什么线索吗？我在这方面的搜索似乎没有显示预建的 scipy 函数，我觉得这几乎很奇怪！

谢谢，爱德华

我正在尝试提出一种算法来执行以下操作：

如果给定一组点，则为查询点找到不包含该组任何点的最大圆（以查询点为中心）。

到目前为止，我一直在考虑使用 Voronoi 图来查找包含最接近集合中某个站点点的点的区域（单元格），然后使用 Voronoi 中的边列表来构造梯形分解。从分解中我将能够找到查询点位于哪个单元格，然后圆的半径将是查询点到该单元格的点（站点）的距离。我认为创建这样的东西所需的存储是线性的，因为 Voronoi 需要 O(n) 存储，并且从 Voronoi 创建梯形分解也可以使用 O(n) 存储来完成。

*编辑：查询时间必须是 O(logn)，这意味着我不能一次遍历集合中的所有点。

这听起来对吗，还是我在这里遗漏了什么？

另外，如果有人有一些关于这个算法的参考资料，请告诉我。谢谢 ：）

我想知道如何在下面的 FCM 方法中显示/绘制 voronoi 图？还有一种方法可以让您从图中观察程序，因为它在 matlab 中放置和计算每个点？几乎就像一辆正在运行的拖车。