标签: voronoi

我想在几对纬度/经度上创建一个 Voronoi 图，但想使用它们之间的大圆距离，而不是（不准确的）毕达哥拉斯距离。

我可以让 qhull/qvoronoi 或其他 Linux 程序执行此操作吗？

我考虑将点映射到 3D，让 qvoronoi 创建 3D Voronoi 图 [1]，并将结果与​​单位球体相交，但我不确定这是否容易。

[1] 我意识到两个纬度/经度之间的 3D 距离（“穿过地球”路径）与大圆距离不同，但很容易证明这种变换保留了相对距离，这才是最重要的对于 Voronoi 图。

我正在实施Voronoi细分,然后进行平滑处理.为了平滑,我打算做劳埃德放松,但我遇到了一个问题.

我正在使用以下模块来计算Voronoi边:

https://bitbucket.org/mozman/geoalg/src/5bbd46fa2270/geoalg/voronoi.py

为了平滑,我需要知道每个多边形的边缘,这样我就可以计算出中心,遗憾的是这个代码没有提供.

我可以访问的信息包括:

• 所有节点的列表,
• 所有边的列表(但只是它们所在的位置,而不是它们所关联的节点).

任何人都可以看到一个相对简单的计算方法吗？

我正在使用一种算法,对于每次迭代,需要找到一组生态协调所属的Voronoi图的哪个区域.也就是说,每个坐标位于哪个区域内.(我们可以假设所有坐标都属于一个区域,如果这有任何区别的话.)

我还没有任何适用于Python的代码,但伪代码看起来像这样:

## we are in two dimensions and we have 0<x<1, 0<y<1.

for i in xrange(1000):
  XY = get_random_points_in_domain()
  XY_candidates = get_random_points_in_domain()
  vor = Voronoi(XY) # for instance scipy.spatial.Voronoi
  regions = get_regions_of_candidates(vor,XY_candidates) # this is the function i need

  ## use regions for something

我知道scipy.Delaunay有一个名为find_simplex的函数,它会在Delaunay三角剖分中完成我想要的简单操作,但是我需要Voronoi图,并且我希望避免构建它们.

问题:

1.是否有某种类型的库可以让我轻松完成这项工作？

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

更新

Jamie的解决方案正是我想要的.我有点尴尬,虽然我自己也没想过......

我试图找到一种方法来计算Python中的2d功率图.为此,我想利用这样一个事实,即2d功率图可以解释为常规3d voronoi图与平面的交点.

使用SciPy Voronoi模块,我可以计算出一个3d Voronoi图 - 是否有可能将它与一个平面相交并将其转换为二维图？

给定N边线图中的点，Map<Point, List<Edge>>可以得到这些边线形成的多边形O(N log N)？

我知道的是，您必须遍历所有顶点，并以包含该顶点的边为起点。这些是voronoi图的边缘，每个顶点最多包含3个艺术家。因此，在映射中，键是顶点，值是列表，其中顶点是起始节点。

例如：

要点：a,b,c,d,e,f,g

边缘：[a,b]; [a,c]; [a,d], [b,c], [d,e], [e,g], [g,f]

我的想法是逆时针迭代地图，直到获得初始顶点。那是一个多边形，然后我将其放在多边形列表中，然后继续寻找其他多边形。问题是我不想克服复杂性O(N log N)

谢谢！

我正在从一组点计算voronoi图,如下所示:

from scipy.spatial import Voronoi
import numpy as np


np.random.seed(0)
points = np.random.uniform(-0.5, 0.5, (100, 2))
// Compute Voronoi
v = Voronoi(points)
voronoi_plot_2d(v)
plt.show()

这将创建如下图像:

可以看出,这是创建无限远(虚线)的顶点,也是创建点的原始边界框之外的顶点:

 bbox = np.array([[-0.5, -0.5], [0.5, -0.5], [0.5, 0.5], [-0.5, 0.5]])

我想要做的是将voronoi图剪辑到此边界框,即将出界和无限顶点投影到此边界框上的适当位置.因此,需要重新排列顶点并将其投影回来自无限远或有限顶点的适当交叉点,但这些顶点超出了剪切区域的界限.

今天是个好日子，

我有以下代码段：

import numpy as np
from random import randint
import matplotlib.pyplot as plt
from scipy.spatial import Voronoi, voronoi_plot_2d

NUM_OF_POINTS = 20

points = []
for i in range (0, NUM_OF_POINTS):
    points.append([randint(0, 500), randint(0, 500)]) 

points = np.array(points)
vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.show()

这会产生像这样的 Voronoi 图：

我的目标是找到“射线”（从绘图中出来的线，虚线或实线）与给定线（例如 x = 500）相交的位置。我该怎么做呢？

我已经尝试ridge_vertices在Voronoi对象中使用列表，但是，这些“射线”仅与列表中的一个顶点相关联，因此我无法计算出线方程。

编辑：

我的最终目标是，给定平面的边界，为给定的边缘单元找到与这些边界相交的点。例如，给定左上角的边缘单元格，边界 y = -50 和 x = 525，我会找到用红色 X 标记的点。

因此，如果您对此有任何见解，将不胜感激。

谢谢你。

有没有像Voronoi图这样的简单算法将任何矩形平面划分为三角形,最终使用预先定义的点数.

说实话,我已经写了一个非常简单的片段着色器像这样.

从理论上讲,这个Voronoii着色器可以通过Delaunay三角测量"升级",但想找到更优雅的解决方案.

假设我们从某处获得了一张 Voronoi 图，但没有点。

像这样但没有红点：

我们只有边界。

有什么算法可以帮助检索积分吗？

如果我们有无限延伸的 Voronoi 图怎么办？我们可以至少计算一个点吗？或者是否有任何启发式算法？

我有一个名为包含其 x 和 y 坐标的点矩阵start_coord，以及表示其分类 (1-5) 的列。即第一行看起来像 [75, 100, 4]。

我使用下面的代码计算了该数据的 voronoi 图

[vc_x, vc_y] = voronoi(start_coord(:,1), start_coord(:,2));

我将如何根据每个多边形中包含的点的分类值（即中的第三列）对结果多边形进行着色start_coord？

编辑 要按颜色快速绘制多边形，请参考下面评论中的答案，这有助于告知此编辑。要获取写入可保存为图像的数组的数千个点的 voronoi 多边形，请参阅以下代码：

new_map = zeros(sm_size(1), sm_size(2));
        start_coord = readmatrix(char(join([csv_path, '/', run_types(run), common_name_csv], "")));
        sc_size = size(start_coord);
        
        dt = delaunayTriangulation(start_coord(:,1:2));
        [V,R] = voronoiDiagram(dt);
                
        for i = 1:sc_size(1)
            A=V(R{i},:);
            B=A(any(~isinf(A),2),:); % omit points at infinity
            bw = poly2mask(B(:,1), B(:,2), sm_size(1), sm_size(2));
            new_map(bw == 1) = color_map(start_coord(i,3));
        end

new_map然后可以保存为数组或转换为 RGB 并保存为图像。