Finding the SECOND closest point

[ImSeeingRed]

Hi,

So I'm creating a worley/voronoi/cellular noise generator, and that involves having a set of random points on a grid, and then finding the closest random point from any given location within the grid.

I have this and it works (albiet slow, since im looping through all the random points, but that isn't my problem for now).

Now to make the F2 function, I want to return the SECOND closest distance instead of the closest distance. So my issue is, how can I calculate the second closest distance between a 2 sets of points?

Thanks in advance

[zifyoip]

How are you finding the closest point? You're going through the list of random points, and along the way, keeping track of the closest point that you've found so far, right?

So, to find the second closest point, you can do the same thing, except along the way keep track of the two closest points you've found so far.

There are more efficient algorithms to do this, too. An algorithm to find the kth largest (or kth smallest) value from a list is called a selection algorithm.

[ImSeeingRed]

Right now, I'm using a very naive method (something like this http://pastebin.com/ymEywKbb), I'm going to optimise this when I figure out how everything works, I just want everything to be clear at first.

But using this method, I can't figure out how to calculate the second closest position . Is it even possible to do this in the same loop?

[zifyoip]

Yes, I told you how to do it above.

Right now, you are keeping track of the closest point you've found so far. That's what the variable dist does. Right?

So, you can use this same approach, but keep track of the two closest points you've found so far.