Nearest Neighbor Problem

Ok, I have no experience with the KD-tree method so would be interested to know how you get on. Your method of solving this problem will depend on your requirement. The time to sort all the points may not be that important if you only need to do it once but, if you have to do it often you're probably on th eright track.

Have you tried this for speed:

nearestObj = cadar(sortcar(mapcar(lambda((objId) list(axlDistance(pt1, objId ->xy), objId)), objs), 'lessp))

Where objs is the list of objects you are measuring to and pt1 is the point. 

Hi Dave

Basically I am trying to probe all the vias depending on their padstack, then foreach type of padstack I need to find the nearest GND via with the same padstack

that being said, there are further more complications like some nets have different ground + I have to ignore whoever passes the minimum requirement

foreach via i am checking the distance and sorting this operation takes a huge amount of time for a large dataset

the kd-tree appeals to me since it looks like i could implement it, I have all the basic things coded, like

a. getting the datasets (xy for all the gnd w.r.to their respective layerset)

b. sort the list

Now for building the tree I am thinking how to implement the following

c. find the median then split them into 2 sets right and left sets based on if the length of the divided list is odd or even

d. then for each left right list form childs and sort them by either x(even) or y(odd) value

 I am thinking of using

defstruct(node data datalen depth leftmax leftdata rightmin rightdata)

now the leftdata will have child node but i will add a depth so i do that for the right data similar child operation

 I would stop this when i reach ceiling(log(length(data)/log(2))

Now I haven't even thought about finding the NNN using the tree

but as you can see in the node defstruct i might add some data to each structure that way i can skip them using basic checks like if the xCoord of the input is larger than the righmin

 please let me know your thoughts

regards

Ok, I can see how this might work (without necessarily following the k-d tree method to the letter).

I created a simple utility that divides a design into 1mm squares. I used this to reduce the number of checks per via. It's very fast with about 8000 vias. There are limitations and flaws with my code but to go further I would be writing the utility for you ;-)

Regards,

Dave 

 sketching on the back of a napkin, you could try build a list of neighbors, something like this pseudocode:

<pre>

pin_list_outer = getListOfAllPins();

pin_list_inner = copy( pin_list_outer);   // need a deep copy

foreach( pin_db_outer  pin_list_outer

    foreach( pin_db_inner pin_list_inner

          unless( pin_db_outer == pin_list_inner     // skip over collisions

               if( axlDistance( pin_db_outer.x_coord , pin_db_inner.x_coord)  =<  yourDesiredFence AND

                  axlDistance( pin_db_outer.y_coord , pin_db_inner.y_coord)  =<  yourDesiredFence

                          neighbor_list = neighbor_array[ pin_db_outer]

                          cons( pin_db_inner neighbor_list)

                         neighbor_array[ pin_db_outer] =  neighbor_list

              );end-if

         );end-unless

    );end-foreach-inner

);end-foreach-outer

winding up with an array, keyed by pin_db , listing all other pin_dbs that are within a square window of desired size

HTH,

Chris Walters

rusty former Cadence guru