Find Nearest Point

[GregFreeman]

I am writing a function that will take an array of xy pairs and find the nearest point, but with two caveats. The two restrictions are:

1) Once a point is chosen, it can't be rechosen (duh or you'd keep going back and forth between two points). 

2) The x direction is weighted more than the y direction (i.e. it should move in x before y). 

I have implemented this and it works, but for ~15k elements it obviously takes a while -- about 8 seconds.

I can't find any way to optimize further. Any thoughts?

edit: woops, sorry, the y and x are going into real and imaginary, respectively. Forgot to realign those wires.

 

[Intaris]

A VI would help.

Soyou're trying to find the nearest neighbour for each of the points in the array or are you traing to traverse the whole array taking each shortest step available.  Like a simpler version of the travelling salesman problem?

Shane

[Intaris]

Do you realise your XYGraph you are building is essentially the same as the shift register on the right-sideof your loop?

[GregFreeman]

I am sorry, I can't post the code otherwise I would. I can explain  what it is doing -- it's actually pretty simple. It gets a starting point, swaps it with index 0, then starts search for the next nearest point, excluding index 0. Then, the second time around it swaps the point we just found with index 1, and starts searching at index 2. After it finds the next nearest point, i swaps i with the point in index 3, and starts searchin at index 3 and so on. That way, used points are placed at the top of the array and I only seach for the nearest point from my counter on down. 

Good call about the repeated array. Before I was using delete from array, which I knew was inefficient but it was just to see if the concept would work. Then I started refacoring. That building of an array is left over from before but I ddn't even notice. Thanks for point that out.

Edit: didn't notice your traveling salesman reference. We are really looking more for neighbor, but trying to account for the case where they are not exactly on the same vertical plane. So, we can't just hold Y constant and look for all points with the same Y, then move on to the next Y. Traveling salesman assumes a constant rate of movement I assume, whereas we are limited by certain directions being faster than others.

Edit2: I'm not opposed to using a traveling salesman type solution and seeing where that gets us.

[JÞB]

Select your Point - subtract the remaining array of clusters from the deleted cluster, Convert to polar.  find min Rho,rinse repeat til you run out of points

which is pretty much what I see you doing except for actually deleting the point of interest and wiring it to a indexing tunnel.  at 15K points that IPE is eating your lunch with the 2010 compiler or later

[JimChretz]

This code runs in 1 or 2 seconds with 15k points, I'm not sure if I perfectly understood what you need to do though.

What do you think?

[JimChretz]

Well I realize it doesn't make much sense to index the initial array. My code doesn't work for sure but I just hope one or two elements will give you ideas to improve your code.

[altenbach]

I'll try a few things....

[nathand]

If you can post a VI (in LabVIEW 2012 or earlier) with sample data and expected results, I'll try to find time to play with algorithms.

Here are some things I would play with, although I don't know without testing whether they'll help:

- move the subtract inside the case structure (inside the for loop) from outside the for loop, so that you only have to allocate one new cluster element rather than a new array as the result of the subtraction.

- instead of rearranging the existing array, allocate a new one of the correct size (you can probably do this with auto-indexing the output). Mark the used elements of the original array by changing their data (for example set the coordinates to NaN).

- If you stick with the current approach of rearranging elements, use "array subset" to skip all the already-processed points.

[GregFreeman]

Thanks guys. We may also try "Binning" x and having some sort of buffer. At that point we can call X values that are sufficiently close on the same plane and sort, then go from there. Just a thought.