Here’s a script doing the task on any mesh:
from Blender import *
#
# Script made by Emil Lozanov, a.k.a. Abidos @ Blender Artists Forum
#
# *** August 2010 ***
#
############################################
def Make_viv(me):
viv = {}
for edge in me.edges:
v1 = edge.v1.index
v2 = edge.v2.index
try: viv[v1].append(v2)
except KeyError: viv[v1]=[v2]
try: viv[v2].append(v1)
except KeyError: viv[v2] = [v1]
return viv
def Get_next_i(dv_bool,i):
for i in range(len(dv_bool)):
if not dv_bool[i]:
return i
return -1
def Get_verts_links(me):
viv = Make_viv(me)
d = {}
lst = [] # list of verts-indeces connected to currently processed vertex
k = 0 # number of verts already processed
vi = 0 # index of currently processed vertex
i = 0 # index of currently processed vertex-index from lst
nv = len(me.verts)
dv_bool = dict([ind,False] for ind in range(nv))
while (vi<>-1):
lst.extend(viv[vi])
for v_ind in lst:
dv_bool[v_ind] = True
j = 0
fl_go = True
while fl_go:
n = len(lst)
dv_bool[vi] = True
for j in range(n):
for v_ind in viv[lst[j]]:
if not (v_ind in lst):
if not dv_bool[v_ind]:
lst.append(v_ind)
dv_bool[v_ind] = True
fl_go = (n<>len(lst)) # i.e. something new is added
d[vi] = lst
k += len(lst)
lst = []
if (vi<nv):
vi = Get_next_i(dv_bool,vi)
return d
############################################
editmode = Window.EditMode()
Window.EditMode(0)
Window.WaitCursor(1)
t1 = sys.time()
sce = Scene.GetCurrent()
ob = Object.GetSelected()[0]
me = ob.getData(mesh=1)
d = Get_verts_links(me)
t2 = sys.time()
T = 1000*(t2-t1)
lst_rows = []
for ind,data in d.items():
lst = [ind]
lst.extend(d[ind])
lst_rows.append(lst)
nv,ne,nf = len(me.verts),len(me.edges),len(me.faces)
print nv,ne,nf
print T
for elem in lst_rows:
print elem
print
#Redraw()
Window.WaitCursor(0)
Window.EditMode(editmode)
I guess it works at a mesh with “special” cases (not tested yet due to lack of time) such as isolated verts or verts with just 1 neighbor in the group or even in cases of overlapped edges. The latter doesnt really matter in our task, right?
Script gives results such as:
20 32 16
0.220186997467
[0, 1, 3, 4, 2, 5, 7, 6]
[8, 9, 11, 12, 19, 10, 13, 18, 15, 16, 14, 17]
meaning it gives processing times of about 0.3 milliseconds when applied on a mesh of 20 verts (2 parts it the above example). Lists of vertices in the “connected” groups are not sorted - it is relatively easy, I think
Sorry PKHG - script is 2.49 style - you know Im still with 2.49
Script give processing time of about 16 milliseconds on a mesh with about 500 verts (on my comp). But increasing N_vets to some 4000-5000 results in a very prolonged processing time of about 11-12 seconds! This is due the fact I produced the script fairly quickly using the straight-forward approach. Also due to Python specifics - dealing with BIG-BIG list and a lot of IFs is real time-pain, ok?
If you’re planning to use the script on meshes with N_verts < 500, NO real improvements are needed!!! Trully!!! Just please report any BUG noticed
Some vers may also NOT needed for the script work - just havent had time to purge ALL these but - if any such vars - they dont mess script work :rolleyes:
For real BIG N_meshes with N_verts > 2000, improvments lye at re-working the Get_next_i proc - may result of about 10-20% improvement. Greater improvement at BIG meshes may come when re-working the main cycle to directly collecting info about verts indices to be added in the final list by using TREE structure of dictionaries, for example. I expect the use of a TREE-like data structure to result to linear relationship between N_vert and processing time, rather than exponential one as it is now.
As the role of passing a second var to the proc Get_next_i is to start from there to the end (abandoned in my solution above), perhaps, a better solution for the Get_next_i proc is (not tested yet):
def Get_next_i(dv_bool,j):
for i in range(j,len(dv_bool)):
if not dv_bool[i]:
return i
return -1
Script is planned to work with ANY mesh, not only 2D…
@ PKHG - I studied Applied Math some time ago. May be I will have time to implement your suggested algorithm and compare the timings one day! Hope the above helps you!
Regards,