Re: [pygame] Need Help with Distance Algorithm in Numeric

[Magnus Lie Hetland <magnus@xxxxxxxxxxx>]

Kamilche <klachemin@xxxxxxxxxxx>:
>
> Hi all! I'm really impressed with the speed I can get out of Numeric, 
> but it is still a head scratcher to me. I appreciate all the help I've 
> gotten here... and I've come for your assistance on another little problem.
> 
> Given two lists of RGB values, for each entry in the first list, I would 
> like to find its 'nearest neighbor' in the second list. I can do it 
> manually... but I bet Numeric gurus would win THAT speed contest! :-)
> 
> Any ideas?

Well, there *are*, of course, specialized algorithms for finding the
nearest neighbours in a metric space like this (various search trees
and the like), but a simple solution in numarray/Numeric ought to be
way fast enough unless you have really huge arrays. Here's one way to
do it (using numarray, which is what I have -- use take() instead of
index arrays for Numeric, I guess).

# Your distance function, for measuring how similar two RGB triples
# are. I'm just using plain ol' Euclidean distance here. Note that it
# returns the pairwise distances for all elements in a and b (which
# must have the same shapes).
def dist(a, b):
    "Euclidean distance"
    return sqrt(sum((a - b)**2, -1))

# In order to compare two arrays of different sizes, I'll just add a
# new axis (to get "all-against-all" comparisons). Then I use argmin
# to get the indices of the smallest distances and use the result as
# an index array in the second array, returning an array with the
# shape of the first array but with elements from the second:

first = array([[10, 20, 30],
               [ 0,  0,  1],
               [50, 60, 50]])

second = array([[10, 10, 10],
                [20, 20, 20],
                [30, 30, 30],
                [40, 40, 40],
                [50, 50, 50]])

print second[argmin(dist(first, second[..., NewAxis]), 0)]


At least that seems to work for me :)

-- 
Magnus Lie Hetland                   Fall seven times, stand up eight
http://hetland.org                                 [Japanese proverb]