Home > Community > Forums > PCB SKILL > Nearest Neighbor Problem

## Email

Recipients email * (separate multiple addresses with commas)

Message *

 Send yourself a copy

## Subscribe

Intro copy of the newsletter section here, some intro copy of the newsletter. Instruction of how to subscribe to this newsletter.

First Name *

Last Name *

Email *

Company / Institution *

 Send Yourself A Copy

# Nearest Neighbor Problem

Last post Wed, Aug 8 2012 11:23 PM by knuhcrek. 9 replies.
 Started by vramananx 06 Aug 2012 02:45 PM. Topic has 9 replies and 2408 views
• #### Mon, Aug 6 2012 2:45 PM

• vramananx
• Joined on Tue, Jun 7 2011
• Posts 23
• Points 385
Nearest Neighbor Problem
 HiI am trying to implement the nearest neighbor problem in skill, can anyone help me with some examples and tutorials?basically i am tryint to get the closest point in a list of points for a given x,yI am using sortcar to do this but it is very slow since there is a huge amount of calculation goes onSo I would like to use any NNP algorithm and would like some pointers, regardsVenkata
• Post Points: 20
• #### Tue, Aug 7 2012 3:46 AM

• Ejlersen
• Joined on Mon, Jul 28 2008
• Aalborg, Copenhagen
• Posts 569
• Points 10,080
Re: Nearest Neighbor Problem
 HiIf you just need the closest point, what's wrong with just running through each element and calculating the distanceclosestpoint = car(listofpoints)shortestdistance = axlDistance(referencepoint closestpoint)foreach(pid listofpointswhen(axlDistance(referencepoint lid) < shortestdistanceshortestdistance = axlDistance(referencepoint lid)closestpoint = lid))that should return the closest point and the shortest distance.Best regardsOle Best regards Ole
• Post Points: 20
• #### Tue, Aug 7 2012 8:27 AM

• vramananx
• Joined on Tue, Jun 7 2011
• Posts 23
• Points 385
Re: Nearest Neighbor Problem
 Hi OleLong timethere is nothing wrong with your suggestion, that's what i do currentlyfor 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 onnow 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 setsThis becomes an huge issue for a big databaseI was looking at implementing KD-Tree, i will let you know how it goesregardsvenkata
• Post Points: 5
• #### Tue, Aug 7 2012 10:15 PM

• vramananx
• Joined on Tue, Jun 7 2011
• Posts 23
• Points 385
Re: Nearest Neighbor Problem
 Hi OleI used 1000! infact it should be 1000 times 1000:-)regards
• Post Points: 5
• #### Tue, Aug 7 2012 10:20 PM

• vramananx
• Joined on Tue, Jun 7 2011
• Posts 23
• Points 385
Re: Nearest Neighbor Problem
 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
• Post Points: 35
• #### Tue, Aug 7 2012 10:57 PM

• Ejlersen
• Joined on Mon, Jul 28 2008
• Aalborg, Copenhagen
• Posts 569
• Points 10,080
Re: Nearest Neighbor Problem
 Hi VenkataI'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 regardsOle Best regards Ole
• Post Points: 5
• #### Wed, Aug 8 2012 4:24 PM

• eDave
• Joined on Sun, Jul 13 2008
• Christchurch, 00-NZ
• Posts 738
• Points 16,055
Re: 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.  Dave Elder, Tait Communications
• Post Points: 20
• #### Wed, Aug 8 2012 5:14 PM

• vramananx
• Joined on Tue, Jun 7 2011
• Posts 23
• Points 385
Re: Nearest Neighbor Problem
 Hi DaveBasically 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 padstackthat being said, there are further more complications like some nets have different ground + I have to ignore whoever passes the minimum requirementforeach via i am checking the distance and sorting this operation takes a huge amount of time for a large datasetthe 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 listNow for building the tree I am thinking how to implement the followingc. 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 evend. then for each left right list form childs and sort them by either x(even) or y(odd) value I am thinking of usingdefstruct(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 treebut 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 thoughtsregards
• Post Points: 20
• #### Wed, Aug 8 2012 10:30 PM

• eDave
• Joined on Sun, Jul 13 2008
• Christchurch, 00-NZ
• Posts 738
• Points 16,055
Re: Nearest Neighbor Problem
 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  Dave Elder, Tait Communications
• Post Points: 20
• #### Wed, Aug 8 2012 11:23 PM

• knuhcrek
• Joined on Tue, Jul 29 2008
• Posts 7
• Points 95
Re: Nearest Neighbor Problem
 sketching on the back of a napkin, you could try build a list of neighbors, something like this pseudocode:
pin_list_outer = getListOfAllPins();pin_list_inner = copy( pin_list_outer);   // need a deep copyforeach( 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 Waltersrusty former Cadence guru
• Post Points: 5