Find all connected edges and split them into groups

[george.sladkovsky]

Hello everyone!

I'm trying to figure out a way to find all the connected edges from a random selection (blue edges) and split them into groups based on their connection.

Example: In the attached image I have 4 selected "groups". How can I get those four groups?

My only idea is to select a random edge and brute force compare its verts to all of the verts of the remaining edges. The matching verts are my next edges. Repeat this in a cycle until it found all the connected edges.

I would really appreciate your help and examples in code. This problem looks fairly simple in theory but I just can't wrap my head around it for some reason.

P.S. I code in MEL but Python examples will be very helpful as well!

[olarn · Accepted solution]

Still a little brute force but how bout

1 Construct a set of selected edge ids

2 And then create a hash map/dict of no.1 set's edge vtx id -> edge id

3 Pick edge at random, call it a new edge id set

4 Starting from that edge crawl through all connected edge that is in no.1 set by looking up each vtx id map in no. 2, adding each discovered edge id to new set.

5 repeat 3-4 until no new edge are found and then record new edge id set as a unique group.

6 pop edge ids in no. 5 from no. 1 set.

7 repeat from 3 until no. 1 is exhausted.

[george.sladkovsky]

Thanks for the reply!

I already experimented with some of the options and the method you described is the fastest so far. The only caveat is that you really need to work with integers and pure edge/vert numbers here, not the full string name.

Just as a comparison, using only integer IDs it sorted a bunch of edges in about .5 seconds, but using full string names, the same code took about 10 seconds...

So if someone is going to repeat this in the future:
1. Use only integers and edge/vert IDs. Strings are extremely slow here.

2. Put edge IDs and its two verts IDs into three separate arrays so that their element number is in sync.

3. Pick a random edge (for me it's element 0 in the array)

4. Cycle through the remaining edges and compare (element $i in the cycle that starts from 1, because element 0 is our original edge)

5. Remember that you have two directions your "crawler" can go from the original edge. I solved it by comparing only one vert of the original edge in the first cycle, so I can get two "directions" in the first cycle, then compare both verts for all consecutive edges.

6. Remember to exclude already "discovered" edges and verts from the original arrays so that they are not interfering with the cycle. If you don't do that your "crawler" will go backwards sometimes. intArrayRemoveAtIndex works flawlessly.

7. Put all discovered edges into an array, combine it to string with " " as a separation string, and put this combined string into an array for storage.

8. All this code should repeat itself in a while loop until the original edge array is empty. On each while loop you will get your edge group and it will be stored in a string array as a string with separation string that can be converted to array whenever you need it.

All in all, this code is quite a trivial matter but sometimes it's simple tasks like that that are the most confusing for some reason.