vb.net: closest point from a list of points with index in list

Replies to This Discussion

Permalink Reply by Damien Alomar on January 15, 2010 at 9:41pm

Well, there's no tricks here. I think that even if you turn your points into a list, then use one of those methods its just going to do the same thing you can do yourself, which is take the distance for all the points in the list, then find which one's closest. Personally I'd do this with two functions; one that does that will take care of the closest point to the list of points, and one that is a custom distance function that doesn't square the distance. The reason being for the second function is that removing the square (which isn't needed if you just want the index) will be faster and make it work better on longer lists of points. This solution also doesn't cross the managed code barrier (ie translation from dotNET to C++) at all, so that will help with speed a little bit as well. The "extreme" solution here is to do some space partitioning, but that will really only be useful if your testing with thousands of points and is much more work. Anyway here's the two functions

Function ClosestPtToPtList (ByRef testPt as On3dPoint, _
ByRef PtList as List(of On3dPoint)) as Integer
Dim minDistIDX as Integer = 0 'set to first index
Dim minDist as double = Dist_NoSquare(testPt, ptList(0))
Dim currDist as double

For i as integer = 1 to ptList.Count - 1
currDist = Dist_NoSquare(testPt, ptList(i))

If minDist > currDist Then
minDist = currDist
minDistIDX = i
End If
Next

Return minDistIDX
End Function

Function Dist_NoSquare (ByRef pt1 as On3dpoint, _
ByRef pt2 as On3dpoint) as double
'This is basically the Pythagorean theorem with an extra dimension
Dim dX, dY, dZ as double
dX = pt2.x - pt1.x
dY = pt2.y - pt1.y
dZ = pt2.z - pt1.z

Return dX^2 + dY^2 +dZ^2
End Function


Note that I put the line continuation character (underscore) in there so that the lines wouldn't wrap, so make sure that there isn't an error there when you paste it into GH. Also, I didn't actually run this code, so there might be a typo in it or something...

Permalink Reply by Benjamin Golder on January 15, 2010 at 10:58pm

Thank you Damien! It works like a charm! You are the man!

I was trying to find a method because it seemed like something that would have a method, since there are already methods for closest point on a curve or all manner of other things.
Also, I am using a list of thousands of points. The script works fine right now on a list of about 2000 points, but I was hoping to have a much larger list. I am using an image to create a list of vectors that correspond to a point grid. I then "flow" a series of seed points through that grid, and use the vectors to influence them. So, the bigger my list of points, the more fine the influence of the image.

Check it out:

Permalink Reply by Benjamin Golder on January 15, 2010 at 11:15pm

And it works at full capacity! with 13,000 points, 200 seed points, and 177 iterations for each seed point, but I had to wait about 3 min or so.

Permalink Reply by Damien Alomar on January 16, 2010 at 6:42am

Interesting stuff. Glad its working for you. With that many points, I think it may be a good idea to see if there's a quicker solution. As I said before, space partitioning is probably going to be the best/quickest solution, but I haven't done any of that before, so I really can't offer up that much help. David has, so he'd definitely have some more to offer up than I would.

One thing I would look at is either quadTrees or octTrees depending on whether your solution is in 2D or 3D, respectively. These seam to work conceptually in a much simpler manner than something like BSP Trees, which will have a more complex division/structure.

Permalink Reply by Suryansh Chandra on January 18, 2010 at 7:44am

I assume you are using the ClosestPt logic here to find the closest point in the grid of image sampling points, and then use the sampled information to drive the direction of the vector?

If that is the case, perhaps it might be faster+more accurate to sample the image within the VB node itself, only and exactly at the pixel you desire, instead of sampling it at a fairly high density first and then use the closest sample...? If you need help with the coding of that, you could look at this. Marc Hoppermann is the man to thank for this.. and I remember David mentioning somewhere that the native GH image sampler uses the lock bits instead of GetPixel.

And yes, interesting work indeed!