Full Example Program

Below is a simple command line program example showing how to use the KDTree.

    class Program
    {
        public static double[][] GenerateData(int points, double range)
        {
            var data = new List<double[]>();
            var random = new Random();

            for (int i = 0; i < points; i++)
            {
                data.Add(new double[] { (random.NextDouble() * range), (random.NextDouble() * range) });
            }

            return data.ToArray();
        }

        static void Main(string[] args)
        {
            // Define the metric function
            // This will be called many times make it as fast as possible
            Func<double[], double[], double> L2Norm = (x, y) =>
            {
                double dist = 0f;
                for (int i = 0; i < x.Length; i++)
                {
                    dist += (x[i] - y[i]) * (x[i] - y[i]);
                }

                return dist;
            };

            // Spatial points for the KDTree
            var treePoints = GenerateData(1000000, 1000);

            // Node objects associated with each point
            // These can be type, for this example we will just take the .ToString() of each point
            var treeNodes = treePoints.Select(p => p.ToString()).ToArray();

            // Test points used for spatial queries
            // Notice that we don't need nodes for the test points. 
            var testPoints = GenerateData(10000, 1000);

            // Build the KDTree.
            var tree = new KDTree<double, string>(dimensions: 2, points: treePoints, nodes: treeNodes, metric: L2Norm);

            // Measure the time to search
            var stopwatch = new Stopwatch();
            stopwatch.Start();
            for (int i = 0; i < testPoints.Length; i++)
            {
                // Get the three closest points from the target
                var nnTest = tree.NearestNeighbors(point: testPoints[i], neighbors: 3);

                // Get all points with in a distance of 100 from the target.
                var radialTest = tree.RadialSearch(center: testPoints[i], radius: 100);
            }
            stopwatch.Stop();

            Console.WriteLine("Milliseconds: " + stopwatch.ElapsedMilliseconds);
            Console.Read();
        }
    }