Nearest Neighbor Problem

Hi

If you just need the closest point, what's wrong with just running through each element and calculating the distance

closestpoint = car(listofpoints)

shortestdistance = axlDistance(referencepoint closestpoint)

foreach(pid listofpoints

when(axlDistance(referencepoint lid) < shortestdistance

shortestdistance = axlDistance(referencepoint lid)

closestpoint = lid

)

)

that should return the closest point and the shortest distance.

Best regards

Ole

Hi Ole

Long time

there is nothing wrong with your suggestion, that's what i do currently

for each point

i append the axldistance from that point to the nearest point's db (list=cons(axldistance(pt1 pt2) list) list=cons(pt2db list))

then I append that list to another list, then i use sortcar to find the shortest distance and its db

------ 

But the number of points is based upon the number of layer sets, for a 6 layer board it is 3 sets, 8 layer is 4 sets and so on

now lets say i got 1000+points in each layer set and have to check each and everyone of them to another set of 1000 so it is a factor of

4.02387260077093773543702433923e+2567 calculations times then number of layer sets

This becomes an huge issue for a big database

I was looking at implementing KD-Tree, i will let you know how it goes

regards

venkata

Hi Ole

I used 1000! infact it should be 1000 times 1000

:-)

regards 

in anycase I am trying to implement kd-tree

I have a way to sort the list of points,

divide them by their median,

then sort them by y value

now i have to figure out a way to add them to a parent->child relation

I am considering using arrays and tables

if you have any ideas please let me know

basically i want this structure

Parent

    -right child----left and right child

      -left child----left and right child

please refer http://en.wikipedia.org/wiki/K-d_tree regards vramanan

Hi Venkata

I'm sorry but I have no experience in kd tree's and never done anything to handle so much data that computing speed would be an issue, so I have no real experience in recommending arrays versus lists.

Best regards

Ole