Geek Answers Handbook

How to group intersecting geometric objects in a list of tuples

I have one data list 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 data list has the following elements :

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

I need to check if an element intersects with any other elements. If they intersect, they must fit in one tuple; and if they do not intersect, they must be placed in different tuples. Expected Result:

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

How to do it?

I tried this 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
+5
source share
3 answers

Keep a pointer to the objects mapped to A, B and C, with a set of matched objects and add only individual elements that do not have matches after we get a new letter if they are not in our matched set, since all possible combinations will be checked:

 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',)]
+2
source 
 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 display the code in your fields:

 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 have been used.

+1
source

For each value in the data, create a tuple of all elements that have an intersecting value. Add it to the list of results if the list is not already listed.

 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 the elements with the same value, i.e. intersecting elements.

You can make this more efficient without creating a tuple if this element has already been extracted into results .

Note that for this dataset, instead of cross-references, equality with == will be == .

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

-1
source

More articles:


All Articles