python - 性能问题：查找点位于哪个多边形中

Question

我目前有一个工作脚本，但我遇到了性能问题。

我想要的是：获得建筑物的高度。

我所拥有的：一个包含我感兴趣的建筑物的 GPS 坐标的文件（数百万，可能/某些重复），全部位于荷兰 一个包含荷兰每座建筑物高度的文件。这是一个 GML 文件，但我无法使用 networkx 正确加载它，所以我有一个解决方法，使用 xml.etree.ElementTree 将其作为 XML 文件处理。如果你喜欢，你可以在这里下载。

方法：从 GML 文件中，我能够为每个建筑物（大约 300 万个）构建一个字典，其中多边形轮廓坐标作为键，高度作为值。例如：

dictHeights = {((157838.00015090595, 461662.000273708), (157838.00015090595, 461662.000273708), (157781.32815085226, 461515.93227361), (157781.32815085226, 461515.93227361), (157781.32815085226, 461515.93227361)): 9.41, ...}

我可以使用以下两个自制函数遍历所有键并找到高度，这工作正常，但是，因为我正在处理数百万个点（地址）和多边形（建筑物），所以我遇到了严重的性能问题. 只获得 5 个高度已经需要几分钟了...一种解决方案可能是使用树结构，但我看不出这将如何减少运行时间，因为我要么必须构建一棵巨大的树，这需要很多时间时间，或者树很小，然后所有步骤都很耗时。如果可能的话，基本上我想摆脱大的for循环。

import numpy as np
import matplotlib.path as mpltPath

这个功能是瓶颈

def getMedianHeight(dictHeights, points):
    heights = []
    for point in points:
        found = False
        for key, value in dictHeights.items():
            path = mpltPath.Path(key)
            if path.contains_point(point):
                heights.append(value)
                found = True
                break
        if not found:
            heights.append(-999)
    return heights

我不太确定如何创建虚拟数据来复制我的数据。我的主要来源是这里。问题是以正确的方式创建字典。

# random points set of points to test 
N = 1000 #this should be about 4 million
points = zip(np.random.random(N),np.random.random(N))

#this creates a an array of polygons,but they overlap, and don't in my data.
lenpoly = 100 
M = 100 # this should be about 3 million

polygons = tuple([tuple((np.sin(x)+0.5,np.cos(x)+0.5) for x in np.linspace(np.pi,lenpoly)[:-1]) for m in np.random.random(M)])

#create array of virtual heights
heights = 100*np.random.random_sample(M)

以下行导致只有 1 个条目的 dict，我已经尝试了大约 1000 种方法来以我想要的方式构建 dict（所有多边形作为键，高度作为值）但我无法做到......要么polygons是一个生成器，要么是 M 个生成器，或者它应该是（就像现在一样）但是字典不能正常工作。

dictHeights = dict((polygon, height) for polygon, height in zip(polygons, heights))

result = getMedianHeight(dictHeights, points)

为了制作 MWE，我将提供一小部分真实数据：

dictHeights = {((151922.594999999, 601062.109999999), (151915.193, 601067.614999998), (151919.848000001, 601073.874000002), (151927.25, 601068.368999999), (151922.594999999, 601062.109999999)): 9.16, ((151229.125999998, 601124.223999999), (151231.934, 601113.313000001), (151225.774, 601111.728), (151222.965999998, 601122.638999999), (151229.125999998, 601124.223999999)): 7.695}
points = [(157838.00015090595, 461662.000273708), (157838.00015090595, 461662.000273708), (157781.32815085226, 461515.93227361), (157781.32815085226, 461515.93227361), (157781.32815085226, 461515.93227361)]
result = getMedianHeight(dictHeights, points)

注意：这个 MWE 的结果对于所有点都是 -999，因为 dict 中的多边形不是正确的建筑物，但你应该明白这一点:-)

标签： pythonpython-3.xperformancedictionaryfor-loop