Multiple ('n') Closest Points Search in VB

Hi guys,

I would like to search for multiple (n) closest points to a single test point using a VB component. I have found the 'Point3dList.ClosestIndex' function, but not one for finding more than one closest point.

I have come up with the workaround attached, but it's quite a lot slower than the standard Grasshopper component - see screenshot attached.

The workaround in the VB component looks like this:

Private Sub RunScript(ByVal Point As Object, ByVal Point_List As List(Of Object), ByVal Num_Points As Object, ByRef A As Object)

Dim pnt_list As New Point3dList
Dim closest_pnt_list As New point3dlist
Dim idx As int32
For i As int32 = 0 To Point_List.Count - 1
pnt_list.add(Point_List(i))
Next i

For i As int32 = 1 To num_points
idx = pnt_list.ClosestIndex(Point)
closest_pnt_list.Add(pnt_list(idx))
pnt_list.RemoveAt(idx)
Next i

A = closest_pnt_list

End Sub

Any help much appreciated!

Thanks,

Rob

Attachments:

Capture.JPG, 52 KB

Replies to This Discussion

Permalink Reply by David Rutten on May 27, 2014 at 4:53am

Step 1. Set the type-hint on your input parameters to Point3d instead of Object (and to Int32 instead of Object on your Num_Points input).

Step 2. Either use the Grasshopper octree data structure to speed up the search drastically, or...

Step 3. Write your own searcher, which aggregates the results.

(3) will probably be easier to code. One way to go about it would be:

Private Function FindClosestPoints(ByVal locus As Point3d, ByVal points As List(Of Point3d), ByVal count As Int32) As Point3d()
If (points Is Nothing) Then Return Nothing
If (points.Count < 2) Then Return points.ToArray()

Dim _pnt As Point3d() = points.ToArray()
Dim _dis As Double() = Nothing
Array.Resize(_dis, _pnt.Length)

For i As Int32 = 0 To _pnt.Length - 1
_dis(i) = locus.DistanceTo(_pnt(i))
Next

Array.Sort(_dis, _pnt)
If (count < _pnt.Length) Then
Array.Resize(_pnt, count)
End If
Return _pnt
End Function

The benefit of this approach is that there's plenty of room for speed improvement. You can switch to a computationally cheaper squared-distance metric instead of euclidean distance. You can compute the distances on multiple threads.

David Rutten

david@mcneel.com

Permalink Reply by Rob May on June 4, 2014 at 1:15am

Hi David,

Many thanks for this. I have added a function similar to your step 3 above, and saved it alongside the Grasshopper closest points search component for comparison, this is slightly faster. How would I compute distances on multiple threads? (or is this done automatically?).

I would like to try the octree method, I started looking at some of the classes - see the third component in the file. Please could you give some example or point me in the right direction?

Thanks,

Rob

Attachments:

ClosestPoints.gh, 16 KB

Permalink Reply by David Rutten on June 4, 2014 at 2:10am

It is not done automatically. You need to parallellize the for loop, which in .NET 3.5 is a lot harder than in .NET 4+

I'm using an iPad now so cannot write any code, but later today I can have a look. On the other hand, you'd be hard pressed to find a simpler example to learn threading with, I think any online tutorial can be easily adapted to fit this searcher.

Incidentally, the native component is slower because it builds a spatial tree of points, which vastly speeds up subsequent searches, obviously that is of no benefit here.

RSS