标签: voronoi

我正在使用voronoi镶嵌细分.我有不同的多边形表示镶嵌中的区域.

以下几点用于绘制图中的曲面细分.

tessdata
    [,1]       [,2]
1  -0.4960583 -0.3529047
2  -2.4986929  0.8897895
3   3.6514561 -1.3533369
4  -1.7263101 -5.5341202
5   2.2140143  0.3883696
6  -2.5208933 -1.4881461
7  -3.2556913  4.4535629
8   0.6423109 -2.8350062
9  -0.4160715  1.2676151
10  4.4059361  4.5641771

使用tessdata输入来绘制曲面细分如下:

library(deldir)
dd<-deldir(tessdata[,1], tessdata[,2])
plot(dd,wlines="tess")

Sammon坐标如下.

       [,1]        [,2]
1   3.14162704 -1.45728604
2   2.35422623  2.46437927
3  -0.85051049  2.71503294
4   1.94310458 -0.45936958
5   0.08737757  3.74324701
6   1.23007799  1.34443842
7   0.01571924  2.19322032
8   1.43320754  2.64818631
9  -0.05463431  0.66980876
10   1.51344967  5.03351176

我想构建输入了sammon坐标点的镶嵌细分.使用这些点的曲面细分应该在所示图中的一个区域内,为此,应该缩放上述点,或者我们可以限制上图中某个区域内曲面细分的图.

希望我已经涵盖了所有必要的数据.

PS:

sammon的投影以"MASS"包装出现.来自"deldir"包的voronoi镶嵌.

deldir函数输出的dirsgs参数将给出在曲面细分中形成线的点的坐标. …

这实际上更像是一个数学问题.但鉴于3分,你如何计算最远点voronoi图？

首先找到通过所有这些并抓住其中心的圆圈.不知道从哪里开始.画面很奇怪

首先,我是CGAL的新手,但是很多用C++编程.我想用CGAL构建球体上点的Voronoi图.我自己实施了一项研究,但数据结构不是很通用,我想使用更强大的工业库,如CGAL.从CGAL的文档来看,似乎我们需要使用3D Delaunay三角剖分结合凸壳.另外,我找到了一篇Robust and Efficient Delaunay Triangulations of Points on Or Close to a Sphere以CGAL为基础的论文,但我找不到它的代码.

那么任何人都可以提供一个关于如何在CGAL中执行此操作的示例？CGAL有没有计划直接用更有效的算法支持球形Delaunay和Voronoi？

提前致谢!

注意:aqueiros 的回答,虽然投票结果更高,但是不正确.特别是这句话" vor.regions在第一个索引中总是有一个空数组 ",这不是真的.

我正在使用scipy.spatial.Voronoi函数生成一个简单的2D Voronoi曲面细分.我使用点的随机2D分布(参见下面的MCVE).

我需要一种方法来遍历每个定义的区域(由其定义scipy.spatial.Voronoi)并获得与其相关联的点的坐标(即:所述区域所包含的点).

问题是N+1为N点定义了区域(多边形),我不确定这意味着什么.

这是一个MCVE,当它到达最后一个区域时会失败:

from scipy.spatial import Voronoi
import numpy as np

# Generate random data.
N = 10
x = [np.random.random() for i in xrange(N)]
y = [np.random.random() for i in xrange(N)]
points = zip(x, y)

# Obtain Voronoi regions.
vor = Voronoi(points)

# Loop through each defined region/polygon
for i, reg in enumerate(vor.regions):

    print 'Region:', i
    print 'Indices of vertices …

我试图调整我在stackoverflow上找到的代码来创建一个有限边界的voronoi单元.我在/sf/answers/1447505321/上找到了下面的代码,但我的问题是虽然voronoi单元格在边界处没有进入无限远,但它们仍然太远了.即使半径= 0,脊顶点也太远了.我理想地希望边界voronoi顶点与中心的其余voronoi单元的间隔大约相同,即我希望边界处的voronoi单元的大小与中心的大小相似.

我正在使用的数据点是

points = [[-30.0, 30.370371], [-27.777777, 35.925926], [-34.444443, 58.51852], [-2.9629631, 57.777779], [-17.777779, 75.185181], [-29.25926, 58.148151], [-11.111112, 33.703705], [-11.481482, 40.0], [-27.037037, 40.0], [-7.7777777, 94.444443], [-2.2222223, 122.22222], [-20.370371, 106.66667], [1.1111112, 125.18518], [-6.2962961, 128.88889], [6.666667, 133.7037], [11.851852, 136.2963], [8.5185184, 140.74074], [20.370371, 92.962959], [17.777779, 114.81482], [12.962962, 97.037041], [13.333334, 127.77778], [22.592592, 120.37037], [16.296295, 127.77778], [11.851852, 50.740742], [20.370371, 54.814816], [19.25926, 47.40741], [32.59259, 122.96296], [20.74074, 130.0], [24.814816, 84.814819], [26.296295, 91.111107], [56.296295, 131.48149], [60.0, 141.85185], [32.222221, 136.66667], [53.703705, 147.03703], [87.40741, 196.2963], [34.074074, 159.62964], [34.444443, …

我想根据中心列表和图像尺寸生成Voronoi区域。

我尝试了基于https://rosettacode.org/wiki/Voronoi_diagram的下一个代码

def generate_voronoi_diagram(width, height, centers_x, centers_y):
    image = Image.new("RGB", (width, height))
    putpixel = image.putpixel
    imgx, imgy = image.size
    num_cells=len(centers_x)
    nx = centers_x
    ny = centers_y
    nr,ng,nb=[],[],[]
    for i in range (num_cells):
        nr.append(randint(0, 255));ng.append(randint(0, 255));nb.append(randint(0, 255));

    for y in range(imgy):
        for x in range(imgx):
            dmin = math.hypot(imgx-1, imgy-1)
            j = -1
            for i in range(num_cells):
                d = math.hypot(nx[i]-x, ny[i]-y)
                if d < dmin:
                    dmin = d
                    j = i
            putpixel((x, y), (nr[j], ng[j], nb[j]))
    image.save("VoronoiDiagram.png", "PNG")
    image.show()

我有所需的输出： …

我想计算2D中一组Voronoi区域的面积的平均值和标准偏差(如果区域延伸到无穷大,我只是将其剪切到单位正方形).

但是,如果可能的话,我想在不明确计算Voronoi区域的情况下从Delaunay Triangulation进行计算？这甚至是可能的,还是明确地计算Voronoi图更好？

我有一个与人工智能做tron游戏的分配.我和我的团队几乎成功,但我们正试图找到一个好的启发式.我们教过Voronoi,但它有点慢:

for yloop = 0 to height-1
for xloop = 0 to width-1

// Generate maximal value
closest_distance = width * height

for point = 0 to number_of_points-1
  // calls function to calc distance
  point_distance = distance(point, xloop, yloop)

  if point_distance < closest_distance
    closest_point = point
  end if
next

 // place result in array of point types
 points[xloop, yloop] = point

next
next

我们有5秒钟的时间来移动,这个算法听起来不太好!我不需要代码......我们只需要一个ideea!谢谢 !

稍后编辑:我们应该尝试Delaunay Triangulations吗？

我写了一个小脚本来显示本教程M中点的voronoi 图。我用.scipy.spatial

我想给出一个新的平面点，并说这个点在 voronoi 图的哪个位置。是否可以？

这是我的代码：

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

N = 70
M = 10

Matrix = [(random.random()*100,random.random()*100)  for x in range(M)]
points = np.array(Matrix)


vor = Voronoi(points)
print(vor.ridge_vertices)

voronoi_plot_2d(vor)
plt.show()

我正在尝试使用 scipy 包构建有界 Voronoi 图，在每次迭代中，我计算 Voronoi 单元的质心，并向质心移动一点（比如一些增量），并通过更新生成器点重新计算 Voronoi 图。当我尝试绘制更新的点时，我收到一个奇怪的错误，因为我绘制的点不是预期的位置。这是代码

import matplotlib.pyplot as pl
import numpy as np
import scipy as sp
import scipy.spatial
import sys

np.random.seed(1)
eps = sys.float_info.epsilon

n_robots = 10
robots = np.random.rand(n_robots, 2)
#print(robots)
bounding_box = np.array([0., 1., 0., 1.]) 

def in_box(robots, bounding_box):
    return np.logical_and(np.logical_and(bounding_box[0] <= robots[:, 0],
                                         robots[:, 0] <= bounding_box[1]),
                          np.logical_and(bounding_box[2] <= robots[:, 1],
                                         robots[:, 1] <= bounding_box[3]))


def voronoi(robots, bounding_box):
    i = in_box(robots, bounding_box)
    points_center = robots[i, :]
    points_left = np.copy(points_center)
    points_left[:, 0] = …