优化 python 用于 LineStrings 交集的代码

Question

我正在尝试查找列表中多个 LineString 的交集。你知道我如何优化这个吗？我不确定如何让它运行得更快（提供了一个小例子）：

from shapely.geometry import LineString
l1 = LineString([Point(-122.238615,37.78376699999999), Point(-122.237455,37.78220799999999)])
l2 = LineString([Point(-122.236899, 37.77980199999999), Point(-122.232146, 37.77611)])
l3 = LineString([Point(-122.232452, 37.775956), Point(-122.236212, 37.775573)])
l4 = LineString([Point(-122.234843, 37.77336199999999), Point(-122.231641, 37.77664699999999)])
l5 = LineString([Point(-121.908187, 37.67754099999999),Point(-121.908409, 37.67810899999999)])

linestrings = [l1,l2,l3,l4,l5,l1,l2,l3,l4,l5,l1,l2,l3,l4,l5,l1,l2,l3,l4,l5,l1,l2,l3,l4,l5,l1,l2,l3,l4,l5]

import time
the_time = time.time()
[ x.intersection(y) for idx1,x in enumerate(linestrings) for idx2,y in enumerate(linestrings) if idx1<idx2 and x.intersects(y)]
print("TIME:",time.time()-the_time)

输出：

TIME: 0.026987314224243164

这是一个小例子，但我有更多的数据，知道如何让它运行得更快吗？

Answer 1

使用空间索引可能会有用，这样可以将 LineString 上的内部循环减少为仅循环那些边界框与在外部循环中迭代的 LineString 的边界框相交的循环，即只考虑那些有可能相交的 LineStrings。

为此，有 rtree 包：

#!/usr/bin/env python
import time

from shapely.geometry import LineString, Point
import rtree

def main():
    l1 = LineString([Point(-122.238615,37.78376699999999), Point(-122.237455,37.78220799999999)])
    l2 = LineString([Point(-122.236899, 37.77980199999999), Point(-122.232146, 37.77611)])
    l3 = LineString([Point(-122.232452, 37.775956), Point(-122.236212, 37.775573)])
    l4 = LineString([Point(-122.234843, 37.77336199999999), Point(-122.231641, 37.77664699999999)])
    l5 = LineString([Point(-121.908187, 37.67754099999999),Point(-121.908409, 37.67810899999999)])

    linestrings = [l1,l2,l3,l4,l5]

    the_time = time.time()
    L = [ x.intersection(y) for idx1,x in enumerate(linestrings) for idx2,y in enumerate(linestrings) if idx1<idx2 and x.intersects(y) ]
    print("TIME: ", time.time() - the_time)

    the_time = time.time()
    index = rtree.index.Index()
    for idx, l in enumerate(linestrings):
        index.insert(idx, l.bounds)

    K = []
    for i1, l1 in enumerate(linestrings):
        for i2 in index.intersection(l1.bounds):
            if i2 >= i1: continue

            omega = l1.intersection(linestrings[i2])
            if omega.is_empty: continue

            K.append(omega)

    print("TIME: ", time.time() - the_time)

if __name__ == '__main__':
    main()

优化 python 用于 LineStrings 交集的代码

Optimize python code used for LineStrings intersection

python

shapely

multilinestring