nearest neighbor assignment - harder than just a pclookup

[yourdaftpunk]

So I've often run into the issue in Houdini where I have two sets of points - let's say green and orange -- and I want one set to be assigned to its closest neighbor in the other set. I'd like to start with this (maybe 1k to 10k orange points):

And assign like so:

The problem is that I'll often have a couple of green points doing a pclookup into a huge set of orange points. The green end up sharing, naively, the orange points they are nearest to as I cannot write into the point cloud that an orange is already nearer and paired to another green. So basically the fracked up result looks like:

Only #1 should be paired with the orange point in the lower right, but 0 and 2 also returned with the same orange paired to them as they had no knowledge that 1 was closer.

Does anyone have any creative of ways of getting around this problem? There are many algorithms, like goals, where you want to do a fast pclookup and then pair away points in a specific manner.

Thanks for reading!

-shawn

Edited June 3, 2013 by yourdaftpunk

[edward]

Sorry, what's wrong with doing a pclookup from the orange's POV?

[yourdaftpunk]

Nothing in some cases, but for example I'm playing with implementing this algo: http://algorithmicbotany.org/papers/colonization.egwnp2007.html At the beginning, we start with one or a few green points (the tree nodes) and many attractors which the tree nodes grow towards and consume (the orange). I may start with several thousand orange and one green so doing the lookup from the orange POV seems like it might be to slow (though I haven't tried yet! I may do so tonight).

In my other use case, a flocking sim, I always had less "green" points and many, many orange points (the landing goals), so I kept trying to come up with a green's POV solution.

[yourdaftpunk]

Another thought, in the flocking sim I was doing a pc lookup then limiting it to a cone of view so it made sense in my mind to search from the green POV/AOV.