Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : William
Date : Fri Sep 09 2005 11:32 am

"KRK" <karlk@eng.umd.edu> wrote in message
news:dfps46$585$1@grapevine.wam.umd.edu...
> Hi,
>
> I'm programming in C and have two separate structure arrays holding
> coordinates for points in space
>
> typedef struct{
>     double x;
>     double y;
>     double z;
> } Position;
>
> Position *array1;        /*Approx. 50,000 Entries*/
> Position *array2;        /*Approx 50,000 Entries*/
>
> My problem is this, I want to take each point in array 1, and find
> its 'nearest spatial neighbor' in array 2.  This can be done by
> brute force, but is rather slow, since to do this requires on the
> order of 10^10 multiplies.

This is essentially the "nearest color match" problem found in a
lot of graphics work. (Usually when going from a large color space
to a smaller one.) You can probably find some useful tips by
googling for things like "nearest color fast algorithm" (without
quotes) etc. In a lot of graphics work, speed is important, so
I'm thinking there's probably a lot of optimised stuff out there.

In graphics, there are other considerations than simple distance
in the color cube because the eye doesn't treat each color
channel equally. This usually involves weighting coefficients on
each index but it should be simple to modify most algorithms to
remove those. -Wm

.