How to detect disconnected parts within a selection?

Question

Consider the following edge selection:

What would be the fastest way to return the indices of the different parts of this selection? I am aiming for an output similar to this: edge_indices = [[24, 46, 29, 47], [32, 52, 37, 53]]. The goal is to detect separate (disconnected) parts within a selection.

One possibility would be to loop over every edge and check for selected connected edges and save the different edge loops, but I feel there should be a faster way to do this.

Thanks!

Answer 1

An iterative version

Each line is commented below but ask in comment if anything is unclear.

import bpy
from collections import defaultdict

# Get edge vertex that is not inside the vert_indices
def other_vert(e, vert_indices):
    return e.vertices[1] if e.vertices[0] in vert_indices else e.vertices[0]

def islands(edges):
    # Will store vertex index to concerned edge list
    d = defaultdict(list)
    # Will store not encountered edges
    not_done = set()
    
    # Prepare the dict and set above
    for e in edges:
        v0 = e.vertices[0]
        v1 = e.vertices[1]
        d[v0].append(e)
        d[v1].append(e)
        not_done.add(e)

    # While some edges are not encountered so far 
    while not_done:
        # Take a starting one
        e = not_done.pop()
        # Start with one of its vertices
        verts = set(e.vertices)
        # This first edge belong to the loop
        loop = [e]
        # While next vertices
        while verts:
            # Gets corresponding new edges
            new_edges = set(e for v in verts for e in d[v] if e in not_done)
            # Remove them: they are encountered
            not_done.difference_update(new_edges)
            #for e in new_edges: not_done.remove(e)
            # Get next vertices
            verts = set(other_vert(e, verts) for e in new_edges)
            # Add the edges to the loop
            loop.extend(new_edges)
        # Yield return each loop
        yield loop

obj = bpy.context.object

edges = [e for e in obj.data.edges if e.select]

print("-")
for island in islands(edges):
    print([e.index for e in island])

Answer 2

Recursively walk the selection.

Similarly to the method employed here How to find the number of loose parts with Blender's Python API?

1. Take one edge of the selection, tag it as "visited" then recursively do same with its connected edges until no more. This will be an "island".
2. Remove the island from the selection, and return to 1.

The tag property of a bmesh element remains persistent, even without updating the bmesh, and AFAIK will need to be reset each time.

Test script, run in edit mode with edges selected.

import bpy
import bmesh
from collections import defaultdict
import sys
from functools import lru_cache


def recursion_limit(method):
    def rec(edges, **kwargs):
        sys.setrecursionlimit(max(len(edges) >> 1, 1000))
        result = method(edges, **kwargs)
        sys.setrecursionlimit(1000)
        return result
    return rec
        
@recursion_limit    
def edge_islands(edges, as_indices=True):
    tags = defaultdict(bool)
    tags.update({e : True for e in edges})
    @lru_cache(128)
    def walk(tree):
        for edge in tree:
            if tags[edge]:
                yield edge.index if as_indices else edge
                del tags[edge]        
        
        leaves = tuple(
            set(
                e for edge in tree 
                for v in edge.verts
                for e in v.link_edges 
                if tags[e]
                )
            )
        if leaves:
            yield from walk(leaves)
        
    return list(
        list(walk((e,))) 
        for e in list(tags.keys()) 
        if tags[e]
        )

if __name__ == "__main__":
    # test call on mesh in edit mode
    context = bpy.context
    ob = context.object
    me = ob.data

    bm = bmesh.from_edit_mesh(me)
    selected_edges = [e for e in bm.edges if e.select]
    print("Input", len(selected_edges))
    islands = edge_islands(selected_edges)
    print(len(islands), "Islands", islands)

Time It

However, lemon's code seems to be quite a lot faster, so I will mark lemon's answer as most helpful

On answering lemon commented he may not answer. Had a feeling (s)he would, with an iterative approach, it would be faster and would be accepted.

Did some optimizing for speed (it was pretty much a copy paste job from an older answer)

• As noted and striked-though removed the use of the tag property
• . Took out set conversion and arithmetic.
• Cached the recursion using functools.lru_cache
• Recursed on all connected each time, rather than a single edge. This greatly reduces the recursion depth.

Have included the script used to test the two scripts for speed, with the caveat the script is run in edit mode, and the result desired needs to be converted to a list of lists. (Timing method that returns a generator will not consume the data and give a result of 0.01 or less milliseconds)

@lemon's script is designed to run in object mode. To make sure the selection is updated the mesh is updated. The input edges are calculated for both. Anything outside the method eg imports, prints, creating the bmesh is not included.

Once again: reports the time taken to generate a list of lists using the two methods. Make sure to edit the text block name the scripts are in. In example below this is in "batFINGER", lemon's in "lemon".

import bpy
import bmesh
from random import randint

bat = bpy.data.texts["batFINGER"].as_module()
lem = bpy.data.texts["lemon"].as_module()

def timeit(method):
    import time
    def timed(*args, **kw):
        ts = time.time()
        result = method(*args, **kw)
        te = time.time()   
        print(f"{method.__name__ : <23} {(te - ts) * 1000 :6.2f} ms")  
        return result    
    return timed

@timeit
def batfinger(edges):
    return bat.edge_islands(edges)    
    
@timeit
def lemon(edges):
    return [[e.index for e in island] for island in lem.islands(edges)]


context = bpy.context
ob = context.object
me = ob.data

bm = bmesh.from_edit_mesh(me)
selected_edges = [e for e in bm.edges if e.select]

batfinger(selected_edges)

#lemon test, 
ob.update_from_editmode()
selected_edges = [e for e in me.edges if e.select]

lemon(selected_edges)

Results

Ran over a test mesh with both loose parts and large contiguous areas. As a rule of thumb the iterative approach is quicker for large connected areas.

After the optimizations results are comparable.

----------------------------------------
79010 Edges
batfinger               741.60 ms
lemon                   707.91 ms
Islands: 3625 Largest: 4124

----------------------------------------
79010 Edges
batfinger               759.15 ms
lemon                   830.18 ms
Islands: 3625 Largest: 4124

----------------------------------------
79010 Edges
batfinger               759.82 ms
lemon                   710.61 ms
Islands: 3625 Largest: 4124

----------------------------------------
79010 Edges
batfinger               750.31 ms
lemon                   836.75 ms
Islands: 3625 Largest: 4124

Related

Is there a way to assign vertex groups to all loose elements via python

How to use loopcut_slide operation without any UI?

What is the bmesh equivalent to bpy.ops.mesh.shortest_path_select()?