实现Voronoi图的简单算法是什么？

我找不到任何特殊的伪形式算法.请分享Voronoi图算法,教程等的一些链接.

我正在尝试着色使用创建的Voronoi图scipy.spatial.Voronoi.这是我的代码:

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

# make up data points
points = np.random.rand(15,2)

# compute Voronoi tesselation
vor = Voronoi(points)

# plot
voronoi_plot_2d(vor)

# colorize
for region in vor.regions:
    if not -1 in region:
        polygon = [vor.vertices[i] for i in region]
        plt.fill(*zip(*polygon))

plt.show()

结果图像:

正如您所看到的,图像边界处的一些Voronoi区域没有着色.这是因为这些区域的Voronoi顶点的一些索引被设置为-1,即,对于Voronoi图之外的那些顶点.根据文件:

区域:(整数列表,形状(nregions,*))形成每个Voronoi区域的Voronoi顶点的索引.-1表示Voronoi图外的顶点.

为了使这些区域着色,我试图从多边形中删除这些"外部"顶点,但这不起作用.我想,我需要在图像区域的边界填写一些点,但我似乎无法弄清楚如何合理地实现这一点.

有人可以帮忙吗？

我正在寻找一个简单的(如果存在的)算法来找到球体表面上一组点的Voronoi图.源代码会很棒.我是德尔福人(是的,我知道......),但我也吃C代码.

我正在制作一个游戏,在那里我创建一个随机的省份地图(风险或外交).为了创建该地图,我首先生成一系列半随机点,然后计算这些点的Delaunay三角剖分.

完成后,我现在正在寻找创建点的Voronoi图表作为省边界的起点.此时我的数据(没有双关语)由原始的点系列和Delaunay三角形的集合组成.

我已经在网上看到过很多方法可以做到这一点,但是大多数方法都与Delaunay的衍生方式有关.我很想找到一些不需要集成到Delaunay的东西,但可以单独根据数据工作.如果做不到这一点,我正在寻找相对几何新手可以理解的东西,而不是最佳速度.谢谢!

生成区域地图(例如风险)是否存在一种微不足道或至少是中等直接的方式？

我已经看过去了,我能找到的最好的是对Voronoi图的模糊引用.Voronoi图的一个例子是:

.

这些有希望,但我想我还没有看到任何直接的渲染方式,更不用说将它们保存在某种形式的数据结构中,将每个领域视为一个对象.

另一种有希望的方法是填充洪水,但我不确定从这种方法开始的最佳方式.

任何建议将不胜感激.

我一直在研究基于Qhull(R中的几何包)的R和MatLab中的一些函数,将圆形图中的局部笛卡尔X,Y,Z点投影到球面(theta,phi,R),以0为中心, 0,0.由于所有的Z值在原始坐标中都是正的(X和Y的中心位于0),这给了我所需的半球投影(点颜色按Z值缩放),用radial.plot绘制( )R plotrix的功能,使用phi(方位角)和theta(极角):

对于球面变换,在以0,0,0为中心之后,而不是使用Bourke(1996)的计算,我使用维基百科上列出的ISO规范(而不是物理惯例).

r     <- sqrt(x^2 + y^2 + z^2)
theta <- acos(z/r)
phi   <- atan2(y,x)

我想知道在这个半球投影中包含给定类点的Voronoi单元区域,保留透视失真.虽然计算二维笛卡尔X,Y点的二维Voronoi图很简单,但将这个Voronoi图转换为二维球形可能无法产生预期的结果,是吗？也许最好直接从半球投影点计算Voronoi图,然后返回每个细胞的面积.

更新:我已经解决了.我的解决方案将在新的R包中共享,我将在此处发布.

我需要在一组点中找到"附近"的邻居.

上图中有10个点.红线是Delaunay三角剖分的边缘,黑色星标记边缘的中线,蓝线是Voronoi镶嵌.点1具有三个"近"邻居,即4,6和7,但不是2和3,它们几乎与边缘1-7一致,但距离更远.

识别近邻(或"好"边缘)的好方法是什么？看看这个图,在我看来,要么选择中点落在与Voronoi线交叉点的边缘,要么考虑作为"近"邻居那些触摸Voronoi单元的边缘可能是一个很好的解决方案(3-5的分类)可以去任何一种方式).有没有一种有效的方法来实现Matlab中的任何一个解决方案(我很乐意得到一个好的通用算法,然后我可以转换为Matlab,顺便说一下)？

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

基于:http://en.wikipedia.org/wiki/Delaunay_triangulation("与Voronoi图的关系"部分)

......我想知道是否有一种简单的方法来获得这种三角测量的"双重图形",即Voronoi Tesselation.

有线索吗？我在这里搜索似乎没有显示预制的scipy函数,我觉得这几乎很奇怪!

谢谢,爱德华

使用此程序中的voronoi/delaunay图生成库,该库基于Fortune 其算法的原始实现,使用随机点集作为输入数据,我能够获得以下输出数据:

1. Delaunay三角剖分的边缘列表,意味着对于每个输入点,我可以看到哪些输入点是它的邻居.它们似乎没有任何特定的顺序.
2. 来自Voronoi图的顶点对列表,我可以用它一次绘制一行Voronoi图.再次,显然没有特别的顺序.
3. 一个未命名的点对列表,它们似乎与2的列表相同,但顺序不同.
4. Voronoi图中形成的顶点列表,也显然没有特定的顺序.

以下是使用此库的程序测试运行的数据示例:

Input points:
0   (426.484, 175.16)
1   (282.004, 231.388)
2   (487.891, 353.996)
3   (50.8574, 5.02996)
4   (602.252, 288.418)

Vertex Pairs: 
0   (387.425, 288.533)  (277.142, 5.15565)
1   (387.425, 288.533)  (503.484, 248.682)
2   (277.142, 5.15565)  (0, 288.161)
3   (387.425, 288.533)  (272.213, 482)
4   (503.484, 248.682)  (637.275, 482)
5   (503.484, 248.682)  (642, 33.7153)
6   (277.142, 5.15565)  (279.477, 0)

Voronoi lines?: 
0   (279.477, 0)    (277.142, 5.15565) …

背景

我正在尝试使用美国地图kmeans在以下数据voronoi polygons上可视化聚类过程的结果.

这是我到目前为止运行的代码:

input <- read.csv("LatLong.csv", header = T, sep = ",")

# K Means Clustering

set.seed(123)
km <- kmeans(input, 17)
cent <- data.frame(km$centers)


# Visualization
states <- map_data("state")
StateMap <- ggplot() + geom_polygon(data = states, aes(x = long, y = lat, group = group), col = "white")

# Voronoi
V <- deldir(cent$long, cent$lat)

ll <-apply(V$dirsgs, 1, FUN = function(x){
  readWKT(sprintf("LINESTRING(%s %s, %s %s)", x[1], x[2], x[3], x[4]))
})

pp <- gPolygonize(ll)=
v_df <- …