Stats

  • Replies 9
  • Subscribers 162
  • Views 15240
  • Members are here 0
More Content

Nearest Neighbor Problem

vramananx

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

Parents

  •  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

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

Children
No Data
Cadence Guidelines

Community Guidelines

The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.