18

从一组点我使用scipy构建了 Voronoi 镶嵌：

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

现在我想从 Voronoi 算法创建的区域中构建一个Shapely 多边形。问题是 Polygon 类需要一个逆时针顶点列表。虽然我知道如何对这些顶点进行排序，但我无法解决问题，因为通常这是我的结果：

在此处输入图像描述

（重叠多边形）。这是代码（一个随机示例）：

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])

我怎么解决这个问题？

4

4 回答 4

42

如果您只是在收集多边形之后，则不需要预先订购点来构建它们。

该scipy.spatial.Voronoi对象具有ridge_vertices包含形成 Voronoi 脊线的顶点索引的属性。如果索引是，-1那么山脊会趋于无穷大。

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

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)

来自 scipy.spatial 的 Voronoi 图

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

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

该shapely.ops模块有一个polygonize返回 Shapely Polygon 对象的生成器。

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

来自 Voronoi 的多边形与一些样本点

或者，如果您想要一个由 Voronoi 镶嵌所包围的区域形成的单个多边形，您可以使用 Shapelyunary_union方法：

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

合并的 Voronoi 镶嵌多边形

于 2014-12-30T09:48:27.740 回答
3

正如其他人所说，这是因为您必须根据索引正确地从结果点重建多边形。尽管您有解决方案，但我想我应该提到还有另一个 pypi 支持的镶嵌包，称为Pytess（免责声明：我是包维护者），其中 voronoi 函数返回完全为您构建的 voronoi 多边形。

于 2015-06-25T20:39:54.123 回答
0

该库能够生成坐标的有序列表，您只需要使用提供的索引列表：

import numpy as np
from scipy.spatial import Voronoi

...

ids = np.array(my_points_list)
vor = Voronoi(points)
polygons = {}
for id, region_index in enumerate(vor.point_region):
    points = []
    for vertex_index in vor.regions[region_index]:
        if vertex_index != -1:  # the library uses this for infinity
            points.append(list(vor.vertices[vertex_index]))
    points.append(points[0])
    polygons[id]=points

字典中的每个多边形polygons都可以导出到 geojson 或带入形状，我能够在 QGIS 中正确渲染它们

于 2019-08-05T15:04:40.020 回答
-1

您实现的功能（order_vertices()）在您的情况下无法使用，因为它只需要一个已经排序的坐标序列，该序列构建一个矩形，并反转多边形的方向（并且可能仅适用于矩形......） . 但是你有一个无序的坐标序列

一般来说，您不能从任意序列的无序顶点构建多边形，因为凹多边形没有唯一的解决方案，如下例所示：https ://stackoverflow.com/a/7408711/4313133

但是，如果您确定您的多边形始终是凸的，则可以使用以下代码构建凸包：https ://stackoverflow.com/a/15945375/4313133 （现已测试，它对我有用）

可能您也可以使用 scipy 构建凸包，但我尝试对其进行测试：scipy.spatial.ConvexHull

于 2014-12-22T11:48:29.600 回答