# How to detect disconnected parts within a selection?

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!

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 if e.vertices in vert_indices else e.vertices

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
v1 = e.vertices
d[v0].append(e)
d[v1].append(e)

# While some edges are not encountered so far
while not_done:
# Take a starting one
e = not_done.pop()
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])

• Both lemon and batFINGER have done the job perfectly. However, lemon's code seems to be quite a lot faster, so I will mark lemon's answer as most helpful. – Niels Oct 18 '20 at 11:52
• @lemon in case you missed comment on answer below, this needs a minor fix. It appears the poles on the UV sphere cause a keyerror trying to remove edge from list again. – batFINGER Oct 21 '20 at 14:02
• @batFINGER, thanks. Bug corrected I think. Replaced a loop by difference_update (which should be faster, by the way). – lemon Oct 22 '20 at 6:57
• @lemon I ran your script in a .blend with an active object (in both Edit and Object modes, with and without geometry selected). But the output is always just - It never does print([e.index for e in island]) What am I misunderstanding or doing wrong? Thanks. – Mentalist Dec 16 '20 at 9:48
• @Mentalist if you want to consider all edges, change this line edges = [e for e in obj.data.edges if e.select] – lemon Dec 16 '20 at 9:56

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".

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
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()?

• Both lemon and batFINGER have done the job perfectly. However, lemon's code seems to be quite a lot faster, so I will mark lemon's answer as most helpful. – Niels Oct 18 '20 at 11:54
• NP. Been meaning to have a look into the loose parts re optimize for speed, as well as fix recursion limit. . Favour the logic of recursion. – batFINGER Oct 19 '20 at 17:56
• Hi @batFINGER, as for the previous question, the elapse rely on island count/edge count ratio... so (I've commented about it on blender.stackexchange.com/questions/75332/… – lemon Oct 19 '20 at 18:08
• @batFINGER, as I've corrected my bug. 6x6x6 sphere is around 0.56s, and 0.45s for yours (which is faster here, so). But if I merge by distance the spheres (so 1 island), yours is 1.16s and mine is 0.59s. – lemon Oct 22 '20 at 7:12
• @lemon Yes get similar results. (Albeit with a 3x slower PC) and agreed (and noted above) the iterative approach is faster for a large contiguous area. Growing the selection sent back via recursion has reduced the time considerably, compared to prior incarnation... where it was absolutiely awful. (One mega sub'd edge would be the worst, akin to version 1) – batFINGER Oct 22 '20 at 7:27