问题标签 [voronoi]

我正在开发一个使用 Voronoi 创建地图的 Java 程序。我正在使用一个生成 Voronoi 的 Java 库，它非常快（http://sourceforge.net/projects/simplevoronoi/）。

我面临的问题是，然后，我必须扫描每个 Voronoi 边缘以了解边缘左侧和右侧的点，以创建包含每个点的多边形。它是包含每个 Voronoi 边的类：

坐标x1, y1, x2, y2是边缘的开始和结束坐标，site1和site2是边缘左侧和右侧的点的索引。因此，要创建包含每个点的多边形，我这样做：

WherexValues和yValues是我生成 Voronoi 图的点坐标，并且GPolygon是我创建的 Polygon 类，它从java.awt.Polygon. 这些是我测量的时间：

• Voronoi 时间： 283 mS（生成 Voronoi 图的时间）
• 多边形搜索时间： 34589 毫秒（完成生成多边形的 for 循环的时间）
• 多边形填充时间： 390 毫秒（填充多边形并保存到图像的时间，这是可选的）
• 点数： 26527（生成 Voronoi 的点数）
• 地图生成完成
• 多边形数量： 26527（多边形数量，每个点一个）

如您所见，与其他时间相比，时间确实很重要，如何加快 for 循环？我还有什么其他选择？非常感谢您提前。

我需要构建 Voronoi 图的边界框。我的问题是“如何将半无限边缘附加到它”。

我使用财富算法来计算图表，并遵循 de Berg、Cheong、van Kreveld 和 Overmars 的“计算几何”。

可能，我的几何知识很差，但我不知道怎么做！

有人知道构建边界框的算法吗？

我目前正在研究一个将 2D 点集修改作为子问题的项目。点集本身将包含几个点簇，我需要以某种方式将它们彼此分开，然后在它们的簇壳内放松它们的点。或者，获取集群的外壳点并将它们用作域并在其中分布（大致）均匀间隔的点就足够了。所以可以跳过放松。作为最坏的情况，我需要处理几个点集，包括约 100k 个顶点，因此使用的算法应该很快。我知道这个主题的复杂性，这就是为什么我不想重新发明轮子，而是尽可能使用现有代码。到目前为止，我发现了以下内容：

1. 用于点集松弛：Fortunes/Sullivans “Sweep Line”算法：据说是最快的单线程voronoi 图构造器。然而，代码似乎很难扩展，并且默认情况下可提取的信息不包含 voronoi 单元外壳数据（它们的顶点位置），至少需要计算质心并进行下一次松弛迭代。此外，矩形以外的任何域都将不可用。

2. CVT：一组用于创建 voronoi 图的多功能库。它支持点的松弛，也支持用户指定区域内的点集。

3. CGAL：具有基本 MP 支持的广泛框架，但显然没有集成的松弛方法。我需要为每个点集子集群创建一个 delaunay 三角剖分，并将其提供给一个 voronoi 适配器，然后给我提供迭代器来查询 voronoi 细胞外壳数据以进一步放松。就我通过文档而言，它应该支持域（几千页:)

4. 还有一些，例如 Voro++，它似乎主要在 3D 中工作；三角形，它使用区域约束从给定域创建 delaunay 三角剖分，以便可以使用三角形顶点作为结果点。

好的，目前在我看来，CVT 应该满足我的需求，同时保持这一切都非常简单。但我不确定，所以问题是：有没有人有过点集松弛实施的经验，最好是使用域？哪些现有代码更可取？

谢谢毛皮建议！t

在 d3js 网站的两个示例中：

简易版

更复杂

我发现他们的一些代码很难理解。D3 参考 API 没有提供深入的解释。在简单版本中，顶点是使用 Math.random() 生成的，如下所示：

宽度和高度是文档大小。这确保所有顶点都在 SVG 元素的范围内（ svg 标签也将 width 和 height 属性设置为这些值）。

然而在更复杂的版本中，它使用一种算法来生成顶点：

vertices在控制台中检查变量时。我发现它是一个二维数组。每个子数组的长度为 3，第一个和第二个元素是数字，最后一个元素是一个包含更多属性的对象，例如 x、y 和 index 等。

生成的 Voronoi 图非常不同。这是为什么？它们都是使用生成的，d3.geom.voronoi()并且（据我希望能理解）唯一的区别在于传递给它的对象。在简单的示例中，它只是一个二维数组，每个子数组中有 2 个数字。我似乎看不到复杂示例中的两行如何创建如此复杂的对象并将其附加到每个子数组的末尾。

如何确保 veritics 也在父 SVG 元素的范围内？

我真的被卡住了，非常感谢你的帮助。

我正在使用 CGAL 和 Qt 来绘制 Voronoi 图。我用过CGAL::Voronoi_diagram_2<DT,AT,AP>，因为我需要面孔。这是示例代码：

我需要剪辑具有无穷远源或目标的射线。如果我使用 Cropped_voronoi_from_delaunay 生成 voronoi，它只会给出片段而不是面。这些是 typedef：

如何使用 Qhull 确定哪些 voronoi 单元（按索引）是“正确的”（由“现有顶点”组成）

我正在尝试使用 LLoyds 算法和由 scipy.spatial Voronoi （这是 Qhull 的包装器）生成的输入来执行约束松弛。

就代码而言，它看起来像：

代码生成的输出图看起来没问题（见下文），但 vor 结构中的数据不足以执行 Lloyds 松弛。这是因为我应该只移动有效 voronoi 单元内的点（图像中的 #4）。另一个应该保持原样。Qhull 打乱了点/区域的顺序，所以我无法估计哪个区域属于哪个点。

这是问题的说明：

现在我应该以某种方式发现 vor.regions[7] 是属于点 vor.points[4] 的区域。如何做到这一点？

我在 GIS 工作。我有一组多边形。我想做一个算法，首先检查多边形集是否是有效的 Voronoi 图。如果是，则返回可以生成相同 voronoi 图的点集。

任何人都可以帮助我如何去做

谢谢

我正在使用一种算法，对于每次迭代，都需要找到一组任意坐标所属的 Voronoi 图的哪个区域。即每个坐标位于哪个区域内。（我们可以假设所有坐标都属于一个区域，如果这有什么不同的话。）

我还没有任何可以在 Python 中运行的代码，但是伪代码看起来像这样：

我知道 scipy.Delaunay 有一个名为 find_simplex 的函数，它几乎可以在 Delaunay 三角剖分中完成我想要的单纯形，但我需要 Voronoi 图，并且我希望避免构建两者。

问题：

1.是否有某种图书馆可以让我轻松做到这一点？

2. 如果没有，是否有一个好的算法可以让我有效地做到这一点？

更新

Jamie 的解决方案正是我想要的。我有点尴尬，虽然我自己没有想到它......

我有一个共享边的所有三角形的列表。如何绘制 voronoi 图？我遍历 Delaunay 三角形并将其与顶点 1 = 顶点 2 和顶点 2 = 顶点 1 进行比较，即 如果有相同的边缘。它还检查顶点 1 = 顶点 1 和顶点 2 = 顶点 2 的时间。在等式中，两边都是不同的三角形。这是来自 boywer watson 算法的相同循环。

我正在尝试使用 scipy 的 Voronoi 镶嵌

http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.spatial.Voronoi.html

但python不会导入它

但是，我从 scipy.spatial 导入其他类没有问题