Nearest Neighbor Problem

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

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