Yeah, I did not attach the file because the KdTree stuff is inside a library that I am developing within VS.
Sorry for not being clearer, what I mean was that there where 1 million hay points and 1 million needles in my test.
But the code for the KDTree is as follows:
protected override void SolveInstance(IGH_DataAccess DA)
{
GH_Structure<GH_Number> _PointCloud = new GH_Structure<GH_Number>();
GH_Structure<GH_Number> _testPoints = new GH_Structure<GH_Number>();
int _num = 0;
DA.GetDataTree(0, out _PointCloud);
DA.GetDataTree(1, out _testPoints);
DA.GetData(2, ref _num);
DataTree<Point3d> result = SharpKDTree.Knearest(_PointCloud, _testPoints, _num);
DA.SetDataTree(0, result);
}
@arendvw here I take the opportunity to answer your question regarding the inputs. KDTree obviously will not take a Point3d
because that type only lives within the Rhino world. It will ask for a more “generic” .NET type as input, so in this case a double [][]
So I have to convert from a DataTree<Point3d>
to DataTree<double>
and then to a double [][]
and to display the result in Rhino I convert the output in to Point3d
again. But of course, I could only output the indexes if I wanted to, to save a couple of seconds.
Continuing with the rest of the code:
/// <summary>
/// Find K-nearest points from a collection of points to a cloud of points to search
/// </summary>
/// <param name="PointCloud"></param>
/// <param name="testPoints"></param>
/// <param name="num"></param>
/// <returns>For every testPoint it will return K-neighbours </returns>
///
public static DataTree<Point3d> Knearest(GH_Structure<GH_Number> PointCloud, GH_Structure<GH_Number> testPoints, int num)
{
DataTree<Point3d> output = new DataTree<Point3d>();
// Conversions between data structures
GH_Number[][] pointCloudTemp = PointCloud.GH_StructureToJaggedArray();
double[][] pCloud = Utilities.ConvertGH_NumberToDouble(pointCloudTemp);
GH_Number[][] testPointsTemp = testPoints.GH_StructureToJaggedArray();
double[][] tPoints = Utilities.ConvertGH_NumberToDouble(testPointsTemp);
KDTree<int> tree = KDTree.FromData<int>(pCloud);
for (int i = 0; i < tPoints.Length; i++)
{
GH_Path path = new GH_Path(i);
// Actually use KDTree's Nearest Neighbour Search
KDTreeNodeCollection<KDTreeNode<int>> neighbours = tree.Nearest(tPoints[i], num);
List<double[]> neighbourNodes = new List<double[]>();
for (int k = 0; k < neighbours.Count; k++)
{
KDTreeNode<int> node = neighbours[k].Node;
neighbourNodes.Add(node.Position);
}
foreach (var item in neighbourNodes)
{
double[] d = item;
output.Add(new Point3d(d[0], d[1], d[2]), path);
}
}
return output;
}
So yeah, its pretty straight forward I am just implementing the Acord.NET KDTree.
http://accord-framework.net/docs/html/T_Accord_Collections_KDTree_1.htm#!
I am not sure if the GH ClosestPoints
uses an Octree
or not , but I highly doubt it from what I understood from Giulio’s comment above.