# Find nearest EXCLUSIVE neighbor

9 replies to this topic

### #1 Oliver Markowski

Oliver Markowski

Peon

• Members
• 16 posts
• Joined: 09-December 08
• Location:MUNICH - GERMANY
• Name:Oliver Markowski

Posted 19 April 2012 - 01:17 PM

Hi guys,

i am having a little trouble building my SOP Network...maybe this is a ForEach & VOP Task but i am not that much of an expert in this area. so here is my problem

i have 500 random points in space and 500 other points where the first ones should move to.
The real problem is, that every point should move to it's nearest neighbor BUT: if the neareast neighbor is already occupied by another point then it should move to the 2nd nearest point.

What i could imagine is to calculate an array per point of distances to all other points
test if the nearest neighbor is already taken by a prior iteration - IF YES - then test the 2nd nearest point and so on - IF NOT then define this point as the goal AND also set an attribute on the point we found that it is now taken...maybe we call this attr "isOccupied" and make it a bool.

The only thing right now is, that i have no idea how to wire this into an forEach-SOP....can anyone help?

Oli

### #2 bandini

bandini

Peon

• Members
• 89 posts
• Joined: 08-January 09

Posted 19 April 2012 - 04:42 PM

I did the exact same thing not too long ago. Ended up using ForEach loop. Basically you have your source points going into one port and goal points going into the other port. On each iteration use a sort node to sort by distance to the point number or id matching the ForEach iteration. After assigning that point as some data (an attribute) onto the source points delete it from the target geometry so next time it evaluates the ForEach loop that point is no longer considered part of the available solution set. A bit tricky, but it works. Advantage of the sort node is that you can easily add a reverse sort after that so you can find the farthest available point, rather than nearest available. I don't have the file on me, but maybe I will post later in the week when I have a chance.

Good luck!

Oliver Markowski, on 19 April 2012 - 01:17 PM, said:

Hi guys,

i am having a little trouble building my SOP Network...maybe this is a ForEach & VOP Task but i am not that much of an expert in this area. so here is my problem

i have 500 random points in space and 500 other points where the first ones should move to.
The real problem is, that every point should move to it's nearest neighbor BUT: if the neareast neighbor is already occupied by another point then it should move to the 2nd nearest point.

What i could imagine is to calculate an array per point of distances to all other points
test if the nearest neighbor is already taken by a prior iteration - IF YES - then test the 2nd nearest point and so on - IF NOT then define this point as the goal AND also set an attribute on the point we found that it is now taken...maybe we call this attr "isOccupied" and make it a bool.

The only thing right now is, that i have no idea how to wire this into an forEach-SOP....can anyone help?

Oli

vimeo: vimeo.com/user2826323

### #3 tmdag

tmdag

Peon

• Members
• 72 posts
• Joined: 07-January 09
• Location:Wellington, NZ
• Name:Albert Szostkiewicz

Posted 19 April 2012 - 06:23 PM

you could also build an array of closest points and store them sorted based on distance just by using vex but in order to whenever previous point is already occupied, you have to iterate per point and you cannot do that using vops/vex. I would suggest giving a try with python where you could just go for i in hou.node().geometry().points().

Edited by tmdag, 19 April 2012 - 08:23 PM.

Albert 'tmdag' Szostkiewicz
http://tmdag.com

### #4 dennis.weil

dennis.weil

Peon

• Members
• 87 posts
• Joined: 11-May 11
• Name:Dennis Weil

Posted 20 April 2012 - 02:18 AM

I did a quick test with the setup Adam described and it seems to work fine except I'm getting some weird results where the nearest point seems to be really far away. Unfortunately I don't have the time to test a vex and/or python version.

-dennis

Bis Montag

#### Attached Files

Edited by dennis.weil, 20 April 2012 - 02:21 AM.

### #5 Oliver Markowski

Oliver Markowski

Peon

• Members
• 16 posts
• Joined: 09-December 08
• Location:MUNICH - GERMANY
• Name:Oliver Markowski

Posted 10 August 2012 - 02:24 PM

even if the setup from dennis is working i wanted to figure that out myself now and i got everything besides the following step in my for each

bandini, on 19 April 2012 - 04:42 PM, said:

After assigning that point as some data (an attribute) onto the source points delete it from the target geometry so next time it evaluates the ForEach loop that point is no longer considered part of the available solution set.

How do i delete points from my 2nd input so they will not be present in the next iteration? Attached is my hip....maybe someone can help me out!

Oliver

### #6 bandini

bandini

Peon

• Members
• 89 posts
• Joined: 08-January 09

Posted 10 August 2012 - 02:56 PM

Hey Oliver,

Hopefully, it is not too much of a shameless promotion but I ended up creating an asset to do this (in python) and uploaded it to the new orbolt store.  You can get it here: http://www.orbolt.co...tch_by_distance

I ended up storing all the information in arrays and then using python sort tools to filter by distance.  Not the quickest method, but much faster and cleaner than the foreach route I was using previously - and you don't need to handle deleting points from the second object at all.  Check out the trial version.  Maybe it does what you need?  I don't know if the python code gets protected in the asset or not, but if not you should be able to check it out.

Oliver Markowski, on 10 August 2012 - 02:24 PM, said:

even if the setup from dennis is working i wanted to figure that out myself now and i got everything besides the following step in my for each

How do i delete points from my 2nd input so they will not be present in the next iteration? Attached is my hip....maybe someone can help me out!

Oliver

vimeo: vimeo.com/user2826323

### #7 Oliver Markowski

Oliver Markowski

Peon

• Members
• 16 posts
• Joined: 09-December 08
• Location:MUNICH - GERMANY
• Name:Oliver Markowski

Posted 11 August 2012 - 04:40 AM

thx for your reply...i really liked your cmiVFX video on connections! I think i will start my hou.python.career soon, but for know i would really like to know how to simply remove points from my 2nd forEach-Input...can anybody help?

cheerio
Oli

### #8 bandini

bandini

Peon

• Members
• 89 posts
• Joined: 08-January 09

Posted 11 August 2012 - 08:17 AM

Oliver,

Check this .hip file. It should work for you, but the python solution is really better, I believe. Ask away if you have any questions.

One thing in the file... Inside the foreach node the sort_reverse node is not necessarily needed. Just showing how to sort by closest or furthest. This is set up for furthest, but if you want closest just bypass that node. Everything after the delete sop in geo1 is not needed - just doing some sops animation there (which may be useful for some people to see).

#### Attached Files

Edited by bandini, 11 August 2012 - 08:23 AM.

vimeo: vimeo.com/user2826323

### #9 Oliver Markowski

Oliver Markowski

Peon

• Members
• 16 posts
• Joined: 09-December 08
• Location:MUNICH - GERMANY
• Name:Oliver Markowski

Posted 13 August 2012 - 03:14 AM

thx for this great example....this is exactly what i was trying to do! But this also kind of answers the question of how to delete points from an auxillary input of the forEach...it looks like you just can't or am I wrong? I already thought about merging the tow pointGroups as you did, but i wasn't sure if there wouldn't be a better way....

thank you very much....beer is on me next time you are in germany (i also know the ladies from luxvonmorgen)

cheers
Oli

### #10 bandini

bandini

Peon

• Members
• 89 posts
• Joined: 08-January 09

Posted 13 August 2012 - 09:46 AM

Oliver Markowski, on 13 August 2012 - 03:14 AM, said:

thx for this great example....this is exactly what i was trying to do! But this also kind of answers the question of how to delete points from an auxillary input of the forEach...it looks like you just can't or am I wrong? I already thought about merging the tow pointGroups as you did, but i wasn't sure if there wouldn't be a better way....

thank you very much....beer is on me next time you are in germany (i also know the ladies from luxvonmorgen)

cheers
Oli

It did not seem to me like it was possible to delete from the second input.  The problem is that you can only output one node for each loop iteration.  So, doing some kind of parallel operation did not seem possible.  Like I said before, I think this solution is a bit sloppy and kind of hack-ish, but if it does what you need, awesome!

I am dying to get to Germany one of these days!  Would love to take you up on that beer offer!

Good luck!