PDA

View Full Version : Grouping touching items


beentheunseen
03-08-2011, 11:14 AM
Hi all,

I'm trying to write a script that groups touching objects together, as demonstrated in the attached image.

Writing a script that finds the neighbours for each item and lists them is not a problem (ie. A finds B and C; C finds A, B and D; D finds C...).

However, I cant figure out how to group the objects into 2 lists of all directly and indirectly touching objects... Does any body have a script that can do this? Or could anybody help me out with a method for acheiving this?

Thanks! Ben

beentheunseen
03-16-2011, 01:35 PM
any ideas?

NaughtyNathan
03-16-2011, 04:13 PM
I don't understand what your problem is here Ben?
if "writing a script that finds the neighbours for each item and lists them" is not a problem, then why cant you put these listed objects into a group as you find them?

to summarise with pseudo code:

list all (selected?) meshes
while this list has content:
choose the first mesh in the list and iteratively find all it's neighbouring meshes
put the ones found into a group.
remove them from the iterated list
continue.
where are you stuck?
:nathaN

beentheunseen
03-16-2011, 04:53 PM
Thnaks for your reply Nathan,

Unfortunately it's not as simple as that, as my neighbour finding script can only find the objects that are directly touching - for example, how can D know it belongs in in the same group as A, when it's only connection is via other cubes?

I don't understand what your problem is here Ben?
if "writing a script that finds the neighbours for each item and lists them" is not a problem, then why cant you put these listed objects into a group as you find them?

to summarise with pseudo code:

list all (selected?) meshes
while this list has content:
choose the first mesh in the list and iteratively find all it's neighbouring meshes
put the ones found into a group.
remove them from the iterated list
continue.
where are you stuck?
:nathaN

NaughtyNathan
03-16-2011, 08:14 PM
it is as simple as that ;) but you're seeing the psuedo-code as even simpler than it is. when I say "Iteratively find all its neighbours" what I mean is when you find a neighbour, you have to find ITS neighbours too, and you keep iterating through every neighbour until you run out of meshes. What you need is a recursive `get neighbours` function.

A) create a new group: "group$N"
B) start with the first mesh in your list of all meshes to process
C) put it into "group$N" and REMOVE it from the process list.
D) find all it's neighbours, and for each neighbour, recurse from step B
(it won't find the first mesh again as you removed it from the process list)
E) if no more neighbours are found once the recursions finish, increment $N and continue from step A

is that any clearer? are you doing this in Python or MEL btw?
:nathaN

whisperwing
03-17-2011, 08:40 AM
It might be easier to understand if you ask different question: how to find out if any two shapes belong to the same group.

I'm assuming you have the script to find out if any two shapes are in direct contact (which is different from "belong to the same group"), so now it becomes a dynamic programming question, and should only take O(n^2) time.

And once you know about that, it's very easy to do what NaughtyNathan suggested, something like this in Python:

unprocessedShapesList = [shape1, shape2, ..., shapeN]
groups = []
while len(unprocessedShapesList) > 0:
shape = unprocessedShapesList[0]
unprocessedShapesList.remove(shape)
group = [shape]
while len(unprocessedShapesList) > 0:
s = unprocessedShapesList[0]
if isInSameGroup(s, shape):
group.append(s)
unprocessedShapesList.remove(s)
groups.append(group)

beentheunseen
03-17-2011, 03:26 PM
Oooh, ok - this is starting to make some sense, thanks a lot guys! I will give it a go. I'm working in Python BTW.

beentheunseen
03-17-2011, 06:22 PM
Sorry guys ,i'm still having real trouble with this - i'm an architect so i have no problem with the spatial aspects of scripting, but as soon as it gets abstract and list based i get into trouble...

This is the line that references my neighbour finding script which returns a list of all adjoining items:

checkRoadAccessComm.findAdjoining(thisBuild)

Could anybody help me incorporate this into a recursive Python script as suggested? I tried incorporating it into whisperwing's suggestion, but ended up in an infinate loop...

whisperwing
03-17-2011, 06:41 PM
Hmmm, in my pseudo code, isInSameGroup() should just return if two shapes are in the same group or not. And my pseudo code is not even a recursive one, it simply goes through a list, so I think you are confusing loop with recursion. And to implement isInSameGroup(), you'll need to solve the first question.

I don't think your question is simple. Dynamic programming is easier to solve in theory but difficult to implement depending on the data structure you use and all the corner cases to consider.

Sorry guys ,i'm still having real trouble with this - i'm an architect so i have no problem with the spatial aspects of scripting, but as soon as it gets abstract and list based i get into trouble...

This is the line that references my neighbour finding script which returns a list of all adjoining items:

checkRoadAccessComm.findAdjoining(thisBuild)

Could anybody help me incorporate this into a recursive Python script as suggested? I tried incorporating it into whisperwing's suggestion, but ended up in an infinate loop...

beentheunseen
03-17-2011, 07:07 PM
Yup, i understood that, here's what i have so far - isnt really working, just seems to be forming a lot of random groups. I really dont mind what method is used or how fast it is, just need to run this thing once to sort some existing objects into groups...


groups = []
while len(unprocessedBuildList) > 0:
thisBuild = unprocessedBuildList[0]
unprocessedBuildList.remove(thisBuild)
group = [thisBuild]
while len(unprocessedBuildList) > 0:
thisNextBuild = unprocessedBuildList[0]
buildsAdjoining = checkRoadAccessComm.findAdjoining(thisNextBuild,1)
sameGroup = False
for eachAdjoining in buildsAdjoining:
if eachAdjoining == thisBuild:
sameGroup = True
if sameGroup == True:
group.append(thisNextBuild)
unprocessedBuildList.remove(thisNextBuild)
else:
break
groups.append(group)
print groups

whisperwing
03-17-2011, 07:19 PM
oh man, if I don't have a day job to do right now, I'll definitely spend time to verify my solution :D

beentheunseen
03-17-2011, 09:00 PM
I got it!


unprocessedBuildList = cmds.ls(selection=True,type="transform")
print unprocessedBuildList


groups = []
while len(unprocessedBuildList) > 0:
thisBuild = unprocessedBuildList[0]
group = [thisBuild]
unprocessedBuildList.remove(thisBuild)

for eachItem in group:
buildsAdjoining = checkRoadAccessComm.findAdjoining(eachItem,1)
for eachGroupedAdj in buildsAdjoining:
exists = False
for eachUnprocessed in unprocessedBuildList:
if eachGroupedAdj == eachUnprocessed:
exists = True
break
if exists == True:
group.append(eachGroupedAdj)
unprocessedBuildList.remove(eachGroupedAdj)
print group
groups.append(group)
print groups


Thanks for your help guys!

CGTalk Moderation
03-17-2011, 09:00 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.