How to group intersecting Shapely geometric objects in a list of tuples

Question

I have one list of data as follows:

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

The list 'data' has following elements:

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

I have to check if an element intersect with any other elements. If intersects, they should put in one tuple; and if not intersect they should put in different tuple. The expected result is:

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

How to do it?

I tried it as:

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

Keep a dict of objects mapped to A,B and C, a set of matched objects and only add the single elements that have no matches after we get to a new letter if they are not in our matched set as all possible combinations will have been tested:

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

Answer 2

For each value in data, make a tuple of all elements having intersecting value. Add it to the results list if the list is not in the list already.

results=[]
for b in data
    same_b = tuple([d for d in data if d.intersects(b)])
    if not same_b in results:
        results.append(same_b)

The result is a list of tuples, each of which has all elements with the same value, ie intersecting elements.

You can make this more efficient by not making a tuple if that element has already been extracted into results.

Note that for the given data set, equality with == would work instead of intersects.

If you want codes instead of data, use a dictionary not variable names. codes={'A':box(...),..}

Answer 3

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

Create a dictionary to map your code to your boxes:

d = dict(zip(codes, data))

Check all combinations:

intersecting = set()

for i, a in enumerate(codes, 1):
    for b in codes[i:]:
        if d[a].intersection(d[b]):
            intersecting |= {a, b}

print(tuple(intersecting), tuple(set(codes)^intersecting))
# ('C', 'A') ('B',)

Tuples will be unordered because sets were used.