问题标签 [voronoi]

我手头有一个创建的函数文件，用于在图像中画线，[img]=drawline(point1,point2,color,img). 它用于连接图像内部的任意两个点。我被要求在图像中创建 voronoi 图（不使用绘图功能）。目前，我正在尝试在图像中显示线条，但我不知道如何获取多边形边缘的顶点。

我一直在使用一些测试代码：

我只知道上面，接下来我想我需要使用for loop来排列顶点。只是不知道如何开始。如果我需要在图像（像素坐标）中显示它们，我也被困在如何解决负面和无限问题上。

是否有任何算法来实现限制椭圆的 Voronoi 图？该图看起来像这里的图片voronoi diagram of ellipses

任何人都可以分享一些与它相关的链接、教程、代码等吗？

提前致谢。

我对mathematica（使用版本8）有很大的了解。绘制 Voronoi 图很简单，但是改变规范怎么样？

给了我对应于 L_2 范数（欧几里得范数）的 Voronoi 图。我也需要与 L_1-norm 和 L_infinity-norm 相关的图表...

我知道从 Voronoi 镶嵌计算 k 最近邻的集合相对容易。反过来的问题呢？我已经有了一组 k 最近邻（3D），我想计算 Voronoi 单元的体积和中心。直观地说，应该有一个 O(n) 算法可以做到这一点，对吧？

有没有人在某处看到过这样的事情？

提前致谢

PS：我假设没有 Voronoi 单元的边数超过 k （这种关于点位置的先验知识可能使计算 O(n) 中的图表成为可能，与维度无关）。

PPS：我进一步假设对于给定的点，Voronoi 单元的顶点属于 kNN 的集合（见下面的评论）。

给定 2D 空间中的两个凸多边形，您将如何构建线段，该线段在线上的任何点都与任一凸多边形的最近点等距？

我正在寻找凸多边形而不是点的 Voronoi 图的实现，但我不确定如何开始计算仅两个多边形的线。所以我想我会一步一步从这里开始。

编辑为了使问题更清楚一点，我想将平面（或其子集）一分为二。

假设我们在左边有多边形 A，在右边有多边形 B。会有一条平分线将平面分成左边的点和右边的点。线上的每个点与任一多边形的距离相等。直线左侧的每个点都比多边形 B 更接近多边形 A。直线右侧的每个点都最接近多边形 B。

这是由我编写的 Matlab 脚本生成的图像，该脚本强力逼近近似值：

我相信，这个问题并不像检查两个多边形“之间”的空间那么简单，因为线必须直接延伸到两个形状之间的区域之外。理想情况下，我想找到一个可以推广到两个以上形状的解决方案，在我看来，这似乎使问题更加复杂。这是一个（显然非常粗略的）近似值：

我试图在给定的数据集中找到边缘相邻的 Voronoi 区域的点。我是计算几何的新手，但从网上阅读来看，使用 Delaunay 镶嵌似乎是一种简单的方法。这个 PDF甚至有一个引理指出

引理 2.4 S 的两个点由一条 Delaunay 边连接如果它们的 Voronoi 区域是边相邻的。

所以，我发现我的数据集的 delaunay 细分为

但是现在，当我将此与该数据集的 voronoi 图一起绘制时，我发现 delaunay 边返回的连接点的区域实际上并不相邻。

这是我用来将 Voronoi 和 Delaunay 绘制在一起的代码：

这是输出：

作为问题的一个例子，看图右端的点 X 连接到左下角附近的点 Y。

另一个例子是在这个 SO question - 点 1 连接到 2 和 3，即使它们不相邻，而且即使扩展到无穷大，1 和 2 似乎也没有任何方式可以共享一条边。这个问题实际上是促使我用上面的代码测试 delaunayn 输出的原因。

为什么会发生这种情况，我如何真正获得我需要的边缘相邻区域？

注意：要查看完整尺寸和清晰度的图像，请右键单击并选择“查看图像”或类似选项。

节点分配问题

我要解决的问题是将蓝色节点（源节点）作为给定输入点的地图进行细分，一旦我能够做到这一点，我想看看每个单元格中有多少黑色节点（需求节点）和将其分配给与该单元格关联的蓝色节点。

我想知道是否有更简单的方法可以在不使用 Fortune 算法的情况下执行此操作。我在 Mahotas 下遇到了这个名为 Mahotas.segmentation.gvoronoi(image) source的函数。但我不确定这是否能解决我的问题。

如果有更好的分割方法（Voronoi tessellation 除外），也请建议我。我不确定聚类算法是否是一个不错的选择。我是一个编程新手。

我在 QT 的 QGraphicsScene 上绘制了一些点，并将它们封装到一个点类中。我想计算这些点的 Voronoi 图并将其显示到场景中。做这个的最好方式是什么？

我正在考虑使用 CGAL，但我找不到这样做的好方法..

我必须实现财富算法来构建 Voronoi 图。

该算法的重要部分是一种称为“海滩线数据结构”的数据结构。

它是一个二叉平衡树，类似于 AVL，但不同之处在于数据仅存储在叶子上（还有其他区别，但对问题不重要）。

我不确定如何实现它。显然，“按原样”使用 AVL 是行不通的，因为在平衡 AVL 时，叶子节点可以成为内部节点，反之亦然。

我还尝试在 wikipedia 上查看其他一些已知的数据结构，但没有一个适合需求。我已经看到一些使用链表执行此操作的实现，但这并不好，因为搜索链表是 O(n)，并且它需要 O(log n) 才能使算法有效。

我希望计算与点集的 Delaunay 三角剖分相关的 Voronoi 单元的面积，而无需将 Delaunay 三角剖分明确转换为 Voronoi 图。因为我只关心 Voronoi 单元的区域，所以我想避免显式构建 Voronoi 数据结构的成本。这可能吗？Delaunay三角剖分/圆与双Voronoi单元区域之间是否存在任何关系？谢谢，

菲利普