标签: voronoi

我正在尝试使用scipy.spatial.Voronoi计算Voronoi图的每个区域的精确边界,在所有点都在预定义多边形内的情况下.

例如,使用文档中的示例,

global_boundaries = np.array([[-2, -2], [4, -2], [4, 4], [-2, 4], [-2, -2]])

我需要计算每个voronoi区域的精确边界,就像那样？

voronoi_region_1_boundaries = [[-2, -2], [0.5, -2], [0.5, 0.5], [-2, 0-5], [-2, -2]]
voronoi_region_2_boundaries = [[-2, 1.5], [0.5, 1.5], [0.5, 4], [-2, 4], [-2, 1.5]]
voronoi_region_3_boundaries = [[-2, 0.5], [0.5, 0.5], [0.5, 1.5], [-2, 1.5], [-2, 0.5]]

等等所有9个地区,而不是

vor.regions 
[[], [-1, 0], [-1, 1], [1, -1, 0], [3, -1, 2], [-1, 3], [-1, 2], [3, 2, 0, 1], [2, -1, 0], [3, -1, 1]] …

我试图在一组固定的地理区域内创建Voronoi多边形(又名Dirichlet镶嵌或Thiessen多边形).但是,我在R中找到一个方法会遇到地图边界内的多边形.我的主要目标是获得准确的面积计算(不仅仅是生成视觉图).例如,以下内容直观地传达了我想要实现的目标:

library(maps)
library(deldir)
data(countyMapEnv)
counties <- map('county', c('maryland,carroll','maryland,frederick', 'maryland,montgomery', 'maryland,howard'), interior=FALSE)
x <- c(-77.208703, -77.456582, -77.090600,  -77.035668, -77.197144)
y <- c(39.188603, 39.347019, 39.672818, 39.501898, 39.389203)
points(x,y)
vt <- deldir(x, y, rw=counties$range)
plot(vt, wlines="tess", lty="solid", add=TRUE)

产生以下内容:

从概念上讲,我想counties与之相交vt,应该提供一组由县界限定的多边形,并为每个多边形进行准确的面积计算.现在,vt$summary为每个多边形提供面积计算,但除了一个内部多边形之外,它们显然被夸大了,并且deldir()似乎只接受其rw参数的矩形包围.我是R的geospacial能力的新手,所以我可以接受超出我上面概述的其他方法.

从一组点我用scipy建立了Voronoi曲面细分:

from scipy.spatial import Voronoi
vor = Voronoi(points)

现在我想从Voronoi算法创建的区域构建Shapely中的Polygon.问题是Polygon类需要一个逆时针顶点列表.虽然我知道如何订购这些顶点,但我无法解决问题,因为这通常是我的结果:

(重叠多边形).这是代码(ONE RANDOM EXAMPLE):

def order_vertices(l):
    mlat = sum(x[0] for x in l) / len(l)
    mlng = sum(x[1] for x in l) / len(l)

    # https://stackoverflow.com/questions/1709283/how-can-i-sort-a-coordinate-list-for-a-rectangle-counterclockwise
    def algo(x):
        return (math.atan2(x[0] - mlat, x[1] - mlng) + 2 * math.pi) % 2*math.pi

    l.sort(key=algo)
    return l

a = np.asarray(order_vertices([(9.258054711746084, 45.486245994138976),
 (9.239284166975443, 45.46805963143515),
 (9.271640747003861, 45.48987234571072),
 (9.25828782103321, 45.44377372506324),
 (9.253993275176263, 45.44484395950612),
 (9.250114174032936, 45.48417979682819)]))
plt.plot(a[:,0], a[:,1])

我怎么解决这个问题？

我有点(例如,lat,lon对的细胞塔位置),我需要得到它们形成的Voronoi细胞的多边形.

from scipy.spatial import Voronoi

tower = [[ 24.686 ,  46.7081],
       [ 24.686 ,  46.7081],
       [ 24.686 ,  46.7081]]

c = Voronoi(towers)

现在,我需要为每个单元格的lat,lon坐标获取多边形边界(以及该多边形所包围的质心).我需要这个Voronoi也是有限的.意味着边界不会变为无穷大,而是在边界框内.

我已成功实现了一种使用Fortune方法生成2维维度Voronoi图的方法.但是现在我正在尝试将它用于一个点的最近邻查询(这不是用于生成图的原始点之一).我一直看到人们说它可以在O(lg n)时间内完成(我相信它们),但我找不到它是如何实际完成的描述.

我熟悉二进制搜索,但我无法找出保证上限的良好标准.我也想过可能它可能与将点插入图表并更新周围的单元格有关,但不能思考(或找到)这样做的好方法.

任何人都可以提醒我,或指向一个描述更全面的地方？

我需要在凹面(非凸面)内部多边形周围生成Voronoi图.我在网上寻找方法,但我无法弄清楚如何做到这一点.基本上,我生成点的凸包,计算双点并在这些点之间建立边缘网络.但是,当遇到内部多边形的边缘时,它必须看起来像形状的边缘,就像凸包一样.因此,通过这样做并剪切边界处的所有边缘,我应该得到一个Voronoi图,它具有内部多边形边界的良好边缘,并且没有位于内部多边形两侧的单元格.

让我给你举个例子:

这个问题是单元格穿过内部多边形边缘,并且单元格结构和多边形形状之间没有视觉关系.

有人知道如何解决这个问题吗？是否有一些算法已经做到这一点或接近我正在努力实现的目标？

非常感谢你的任何输入!

有人能指出我如何构建(乘法和/或加法)加权voronoi图的参考实现,最好是基于Fortune的voronoi算法吗？

我的目标:给定一组点(每个点都有一个权重)和一组边界边(通常是一个矩形),我想用python或processing.org-framework构建一个加权的voronoi图.这是一个例子.

到目前为止我所做的工作:到目前为止,我已经实现了Fortune的算法以及Michael Balzer的论文中提出的"centroidal voronoi tessellation" .算法3说明了如何调整权重,但是,当我实现这个时,我的几何不再适用.要解决此问题,必须更新扫描线算法以考虑权重,但到目前为止我无法做到这一点.因此,我想看看其他人是如何解决这个问题的.

我有(x,y,z)形式的数据,其中x和y不在常规网格上.我希望显示这些数据的2D色彩图,其中强度(例如,灰度)映射到z变量.一个明显的解决方案是在常规网格上插值(见下文),

d <- data.frame(x=runif(1e3, 0, 30), y=runif(1e3, 0, 30))
d$z = (d$x - 15)^2 + (d$y - 15)^2


library(akima)
d2 <- with(d, interp(x, y, z, xo=seq(0, 30, length = 30),
                     yo=seq(0, 30, length = 50), duplicate="mean"))

pal1 <- grey(seq(0,1,leng=500))
with(d2, image(sort(x), sort(y), z, useRaster=TRUE, col = pal1))
points(d$x, d$y, col="white", bg=grey(d$z/max(d$z)), pch=21, cex=1,lwd=0.1)

然而,这会丢失初始网格的信息(点与实际数据的位置),这些信息在某些位置可能非常精细或非常粗糙.我倾向于使用三角形进行delaunay平铺,这准确地表示原始数据点的实际位置和密度.

理想情况下,解决方案会

• 计算镶嵌绘图功能的外部,使得所得到的多边形可以与任一被绘制ggplot2,lattice或碱图形

• 快点 在我的实际例子中(~1e5分),tesselation via的计算deldir可能非常慢.

通过"tesselation"我的意思是Delaunay三角形或Voronoi图,虽然我的偏好是前者.然而,它带来了基于原始数据点插入每个三角形的颜色的额外复杂性.

使用Emgu CV我从道路网络图像中的轮廓中提取了一组闭合多边形.多边形代表道路轮廓.结果如下所示,绘制在OpenStreetMaps地图上(来自Emgu CV的'像素'形式的多边形已转换为要绘制的纬度/经度形式).

代表道路轮廓的多边形集:

我现在想要计算这组多边形的Voronoi图,这将帮助我找到道路的中心线.但在Emgu CV中,我只能找到一种方法来获得一组点的Voronoi图.这是通过找到点集的Delaunay三角剖分(使用Subdiv2D类)然后使用GetVoronoiFacets计算voronoi面来完成的.

我已经尝试计算由集合中所有多边形定义的点的Voronoi图(每个多边形是一个点列表),但这给了我一个非常复杂的Voronoi图,正如人们可能期望的那样:

点集的Voronoi图:

该图像显示了第一张图片的较小部分(为清楚起见,因为它是如此复杂).事实上,图中的某些线条似乎代表了道路中心线,但是还有很多其他线路,很难找到提取"好"线的标准.

我面临的另一个潜在问题是,正如你应该能够从第一张图片中看出的那样,一些多边形在其他人的内部,所以我们不处于一组不相交的闭合多边形的标准情况.也就是说,有时道路位于一个多边形的外边界和另一个多边形的内边界之间.

我正在寻找关于如何使用Emgu CV(或Open CV)计算多边形集的Voronoi图的建议,希望能够克服我已经概述的第二个问题.我也对其他建议如何在不使用Emgu CV的情况下实现这一点.

毫无疑问，Voronoi 算法提供了一种可行的方法，可以根据到平面特定子集中的点的距离将平面划分为多个区域。这样一组点的 Voronoi 图是其 Delaunay 三角剖分的对偶。 现在可以通过使用模块 scipy 作为直接实现这个目标

import scipy.spatial

point_coordinate_array = np.array(point_coordinates)
delaunay_mesh = scipy.spatial.Delaunay(point_coordinate_array)
voronoi_diagram = scipy.spatial.Voronoi(point_coordinate_array)

# plot(delaunay_mesh and voronoi_diagram using matplotlib)

当预先给定点数时。结果如图1所示，

其中绿色虚线包围的区域是所有点的德劳内三角形，蓝色实线的封闭区域当然是中心点的voronoi单元（为了更好的可视化，这里只显示封闭区域）

直到现在，一切都被认为是完美的。但在实际应用中，所有的点都可能有自己的物理意义。（例如，当这些点代表自然粒子时，它们可能具有“半径”变量）。而上面常见的voronoi算法，对于这种可能需要考虑复杂物理限制的情况，或多或少是不合适的。如图 2 所示，voronoi 单元的脊可能与粒子边界相交。已经不能满足生理要求了。

我现在的问题是如何创建一个修改过的 voronoi 算法（也许它不能再被称为 voronoi）来处理这个物理限制。这个目的大致如图3所示，蓝色虚线封闭的区域正是我想要的。

所有的点数要求是：

1.numpy-1.13.3+mkl-cp36-cp36m-win_amd64.whl

2.scipy-0.19.1-cp36-cp36m-win_amd64.whl

3.matplotlib-2.1.0-cp36-cp36m-win_amd64.whl

并且都可以直接在http://www.lfd.uci.edu/~gohlke/pythonlibs/下载

我的代码已更新以进行更好的修改，它们是

import numpy as np
import scipy.spatial
import matplotlib as mpl
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
from matplotlib.collections import PatchCollection

# give the point-coordinate array for contribute the tri-network.
point_coordinate_array = np.array([[0,0.5],[8**0.5,8**0.5+0.5],[0,-3.5],[-np.sqrt(15),1.5]])

# give …