测试几何项是否在python列表中相交

Question

我有一个数据列表如下:

from shapely.geometry import box

data = [box(1,2,3,4), box(5,6,7,8), box(1,2,3,4)]
codes = ['A','B','C']

列表"数据"包含以下元素:

A = box(1,2,3,4)
B = box(5,6,7,8)
C = box(1,2,3,4)

我必须检查元素是否与任何其他元素相交.如果相交,他们应该放入一个元组; 如果不相交,他们应该放入不同的元组.预期的结果是:

result = [(A,C), (B)]

怎么做？

我试过它:

results = []
for p,c in zip(data,codes):
    for x in data:
        if p.intersects(x): ##.intersects return true if they overlap else false
            results.append(c)
print results

Answer 1

保留映射到 A、B 和 C 的对象的字典，一组匹配的对象，并且在我们到达新字母后仅添加没有匹配的单个元素（如果它们不在我们的匹配集中），因为所有可能的组合都将被测试：

from shapely.geometry import box
from itertools import combinations

codes = ["A", "B", "C"]
d = dict(zip(codes, data))
prev = codes[0]
matched, out = set(), []
for p1, p2 in combinations(codes, 2):
    if d[p1].intersects(d[p2]):
        out.append((p1, p2))
        matched.update([p1, p2])
    # when p1 is a new letter, we have tried all combs for that prev
    # if prev is not in matched it did not intersect any other so
   # add it as a single tuple and add to matched to avoid dupes
    elif p1 != prev and prev not in matched:
        out.append(tuple(prev,))
        matched.add(prev)
    prev = p1
# catch the last letter
if p2 not in matched:
    out.append(tuple(p2,))
print(out)
[('A', 'C'), ('B',)]