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

Email

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

 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
Page 1 of 1 (10 items)
Sort Posts:
  • Mon, Aug 6 2012 2:45 PM

    • vramananx
    • Top 500 Contributor
    • Joined on Tue, Jun 7 2011
    • Posts 23
    • Points 385
    Nearest Neighbor Problem Reply

    Hi

    I 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,y

    I am using sortcar to do this but it is very slow since there is a huge amount of calculation goes on

    So I would like to use any NNP algorithm and would like some pointers,

     regards

    Venkata

    • Post Points: 20
  • Tue, Aug 7 2012 3:46 AM

    • Ejlersen
    • Top 10 Contributor
    • Joined on Mon, Jul 28 2008
    • Aalborg, Copenhagen
    • Posts 569
    • Points 10,080
    Re: Nearest Neighbor Problem Reply

    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

    Best regards Ole
    • Post Points: 20
  • Tue, Aug 7 2012 8:27 AM

    • vramananx
    • Top 500 Contributor
    • Joined on Tue, Jun 7 2011
    • Posts 23
    • Points 385
    Re: Nearest Neighbor Problem Reply

    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

    • Post Points: 5
  • Tue, Aug 7 2012 10:15 PM

    • vramananx
    • Top 500 Contributor
    • Joined on Tue, Jun 7 2011
    • Posts 23
    • Points 385
    Re: Nearest Neighbor Problem Reply

    Hi Ole

    I used 1000! infact it should be 1000 times 1000

    :-)

    regards 

    • Post Points: 5
  • Tue, Aug 7 2012 10:20 PM

    • vramananx
    • Top 500 Contributor
    • Joined on Tue, Jun 7 2011
    • Posts 23
    • Points 385
    Re: Nearest Neighbor Problem Reply

    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
    • Top 10 Contributor
    • Joined on Mon, Jul 28 2008
    • Aalborg, Copenhagen
    • Posts 569
    • Points 10,080
    Re: Nearest Neighbor Problem Reply

    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

    Best regards Ole
    • Post Points: 5
  • Wed, Aug 8 2012 4:24 PM

    • eDave
    • Top 10 Contributor
    • Joined on Sun, Jul 13 2008
    • Christchurch, 00-NZ
    • Posts 738
    • Points 16,055
    Re: Nearest Neighbor Problem Reply

    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
    • Top 500 Contributor
    • Joined on Tue, Jun 7 2011
    • Posts 23
    • Points 385
    Re: Nearest Neighbor Problem Reply

    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

    • Post Points: 20
  • Wed, Aug 8 2012 10:30 PM

    • eDave
    • Top 10 Contributor
    • Joined on Sun, Jul 13 2008
    • Christchurch, 00-NZ
    • Posts 738
    • Points 16,055
    Re: Nearest Neighbor Problem Reply

    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
    • Not Ranked
    • Joined on Tue, Jul 29 2008
    • Posts 7
    • Points 95
    Re: Nearest Neighbor Problem Reply

     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

    • Post Points: 5
Page 1 of 1 (10 items)
Sort Posts:
Started by vramananx at 06 Aug 2012 02:45 PM. Topic has 9 replies.