Python, efficient list processing

Coding
1

Looking for input on how to process some polygonal data, that’s just a nested list of connected faces. I’d like an algorithm that scales up, and am not sure if a solution already exists as a standard python pattern/process. This seems like a problem that’s been solved a bajillion times already.

I’d like to turn this list of sets, that contain overlapping values, into a list of sets with no overlaps. I can do it for small chunks of data, but this solution doesn’t scale well at all.


#two cubes, combined into one object = two shells.
poly_lists = [[0, 5, 1, 4, 3],
 [1, 5, 2, 4, 0],
 [2, 5, 3, 4, 1],
 [3, 0, 5, 4, 2],
 [4, 1, 0, 2, 3],
 [5, 1, 2, 0, 3],
 [6, 11, 7, 10, 9],
 [7, 11, 8, 10, 6],
 [8, 11, 9, 10, 7],
 [9, 6, 11, 10, 8],
 [10, 7, 6, 8, 9],
 [11, 7, 8, 6, 9]]

shell_sets = []
shell_sets_temp = []


for poly_list in poly_lists:
    shell_sets_temp = shell_sets
    found = False
    for i, a_shell in enumerate(shell_sets_temp):
        if len(set(a_shell ) & set(poly_list)):
            shell_sets[i] = set(a_shell ) | set(poly_list)
            found = True
            break
    if not found:
        shell_sets.append(set(poly_list))
        
print shell_sets


#shell_sets = [set([0, 1, 2, 3, 4, 5]), set([6, 7, 8, 9, 10, 11])]
#Two sets == Two polygonal shells!  It works!
#but not for very large lists, takes too long.
2

Just to make sure I get the problem:

given a list of sets:
[1,2,3]
[3,4,5]
[6,7,8,9]
[9,10]

you’d expect to get back [1,2,3,4] and [6,7,8,9,10] ?

3

Exactly.

The initial list contains every face_index of an object, with their connected faces. The answer you get back reveals how many shells there are in the object, of non connected faces. (that probably doesn’t help!)

4

Are you just interested in finding all the shells in an object and the polygons that comprise them? Or are you just looking for a faster way to parse your faces-and-connected-faces nested list?

If it’s the former: function for returning the selectable shells of a poly · GitHub

5

depending on the data layout, this should probably be faster than brute force, since it will remove each shell from further consideration as it is found:


def shell_separate(*listofsets):
    comp_set = listofsets[0]
    test_sets = listofsets[1:]
    
    disjoint = []
    for each_set in test_sets:
        if comp_set.intersection(each_set):
            comp_set.update(each_set)
        else:
            disjoint.append(each_set)
    
    return comp_set, disjoint

def get_shells (*list_of_sets):
    shells = []
    while list_of_sets:
        new_shell, remainder = shell_separate (*list_of_sets)
        shells.append(new_shell)
        list_of_sets = remainder
        
    return shells

lists = (set((1,2,3)),
         set((3,4,5)),
         set((5,8)),
         set((6,7,9)),
         set((10,11,12)),
         set((10,13,14,15)),
         set((12,13,14,16,17)))
         
print get_shells(*lists)

// [set([1, 2, 3, 4, 5, 8]), set([9, 6, 7]), set([10, 11, 12, 13, 14, 15, 16, 17])]

In the particular case of poly meshes, you could try extracting a separate set with the highest and lowest index in each list, and see where those overlaps. If they don’t, there’s no chance of an intersection so it would allow you to do early rejections on some of the data. I didn’t bother to include this in the code, but if you sort the sets in size order (largest first) that should also make it faster as the hardest comparisons will be rejected first.

6

I’ve avoided looking closely at your answers yet, still rolling this around in my head. (but thank you!)

Is it guaranteed that shells only contain non-overlapping ranges of polys?

7

the code just peels off the first set in a list of sets, then intersects it with all the others. If the next set intersects it, the contents of the set are glommed onto the first and the set is removed from future tests (because it is already in a shell). So, AFAIK this will find all the disjoint islands in the set. Of course, if the original data didn’t have disjoint sets you’d get back one big set. It’s not quite linear time since the intersections are slower than linear - but as it iterates it gets faster because the list of comparisons is getting pruned down.

8

I don’t have maya handy at the moment, but can’t you already get the breakdown of poly shells with standard commands?

9

The only way that I know of to get a breakdown of poly shells using standard commands is to use polySelect. It has an extendToShell flag which takes a faceId and returns all of the other faces in that shell.