从Voronoi细分到Shapely多边形 [英] From Voronoi tessellation to Shapely polygons

问题描述

我从以下几点出发，使用

from a set of points I built the Voronoi tessellation using scipy:

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

现在，我想从Voronoi算法的区域构建 Polygon in Shapely 创建.问题在于Polygon类需要一个逆时针顶点列表.尽管我知道如何排序这些顶点，我无法解决问题，因为通常这是我的结果:

Now I would like to build a Polygon in Shapely from the regions the Voronoi algorithm created. The problem is that the Polygon class requires a list of counter-clockwise vertices. Although I know how to order these vertices, I can't solve the problem because often this is my result:

(重叠的多边形).这是代码(一个随机示例):

(overlapping polygon). This is the code (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])

我该如何解决这个问题?

How can I solve this problem?

推荐答案

如果您只是在收集一组多边形，则无需对点进行预排序即可构建它们.

If you're just after a collection of polygons you don't need to pre-order the point to build them.

scipy.spatial.Voronoi对象具有ridge_vertices属性，该属性包含形成Voronoi脊线的顶点的索引.如果索引为-1，则凸脊将变为无穷大.

The scipy.spatial.Voronoi object has a ridge_vertices attribute containing indices of vertices forming the lines of the Voronoi ridge. If the index is -1 then the ridge goes to infinity.

首先从一些随机点开始构建Voronoi对象.

First start with some random points to build the Voronoi object.

import numpy as np
from scipy.spatial import Voronoi, voronoi_plot_2d
import shapely.geometry
import shapely.ops

points = np.random.random((10, 2))
vor = Voronoi(points)
voronoi_plot_2d(vor)

您可以使用它来构建Shapely LineString对象的集合.

You can use this to build a collection of Shapely LineString objects.

lines = [
    shapely.geometry.LineString(vor.vertices[line])
    for line in vor.ridge_vertices
    if -1 not in line
]

shapely.ops模块具有 polygonize 返回形状多边形对象的生成器.

The shapely.ops module has a polygonize that returns a generator for Shapely Polygon objects.

for poly in shapely.ops.polygonize(lines):
    #do something with each polygon

或者，如果您希望从Voronoi镶嵌封闭的区域中形成一个多边形，则可以使用Shapely unary_union方法:

Or if you wanted a single polygon formed from the region enclosed by the Voronoi tesselation you can use the Shapely unary_union method:

shapely.ops.unary_union(list(shapely.ops.polygonize(lines)))

这篇关于从Voronoi细分到Shapely多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！