如何优化几何运算的性能

Question

我正在寻找一种优化几何运算性能的方法。我的目标是计算一系列多边形（21562）内有多少个点（205779）。最好使用python和R以及GIS软件，如ArcGIS、QGIS。在

以下是我搜索并编写的解决方案。在

1. 使用ArcGIS：其中一个例子是在http://support.esri.com/cn/knowledgebase/techarticles/detail/30779->；虽然我没有尝试过，但根据我以前的经验，在空间连接中总是要花费大量的时间。

2. 使用GDAL，OGR：下面是一个示例：http://geoexamples.blogspot.tw/2012/06/density-maps-using-gdalogr-python.html->；每个多边形需要5到9秒。

3. 对循环使用Shapely准备的几何操作：这是我的示例，每个多边形需要2.7到3.0秒。（请注意，点是列表中的点对象）

   prep_poly=[]
   for i in polygons:
       mycount=[]
       for j in points:
           if prep(i).contains(j):
               mycount.append(1) #count how many points within polygons
       prep_poly.append(sum(mycount)) #sum once for every polygon
       mycount=[]
   

4. 使用Shapely-prepared geometry操作和过滤器：这是我的示例，每个多边形大约需要3.3到3.9秒（注意点是一个多点对象）

   prep_poly=[]
   for i in polygons:
       prep_poly.append(len(filter(prep(i).contains, point1)))
   

虽然准备好的几何操作确实提高了性能，但是处理大量多边形仍然很耗时。有什么建议吗？谢谢！在

Answer 1

您可以在屏幕上查找每个像素（而不是在屏幕上查找每个像素）：

first_pixel = any pixel in the polygon
px_list = [] # array with pixels left to check
px_list.append(first_pixel) # add pixel to list of pixels to process

count = 0

while len(array) > 0: # pixels left in pixel list
    curr_pixel = array[0]
    for pixel in get_adjacent_pixels(curr_pixel): # find adjacent pixels
                                                  # ie (vertical, horizontal, diagonal)
        if pixel in shape:
            px_list.append(pixel) # add pixel to list

    px_list.remove(curr_pixel)
    count += 1

基本上，路径查找的工作方式是一样的。查看此wiki文章以获取上述算法的可视化表示： http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Algorithm

如果找不到起点，可以循环一次所有点，检查每个点是否包含在一个形状中，然后将该点与形状一起存储在一个单独的列表中，并从原始形状中删除它，我们还没有点列表。在