c# 使用点集创建KD树，并查找距某个点最近的点

以下是C#实现使用点集创建KD树，并查找距某个点最近的点的代码示例：

using System;
using System.Collections.Generic;
using System.Linq;

namespace KdTreeDemo
{
    class Node
    {
        public double[] Point { get; set; }
        public int Axis { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
    }

    class KdTree
    {
        private Node root;

        public KdTree(double[][] points)
        {
            root = BuildKdTree(points, 0);
        }

        private Node BuildKdTree(double[][] points, int depth)
        {
            if (points.Length == 0)
            {
                return null;
            }

            int axis = depth % points[0].Length;
            Array.Sort(points, new PointComparer(axis));

            int medianIndex = points.Length / 2;
            Node node = new Node
            {
                Point = points[medianIndex],
                Axis = axis,
                Left = BuildKdTree(points.Take(medianIndex).ToArray(), depth + 1),
                Right = BuildKdTree(points.Skip(medianIndex + 1).ToArray(), depth + 1)
            };

            return node;
        }

        public double[] FindNearestNeighbor(double[] query)
        {
            double[] closest = null;
            double closestDist = double.PositiveInfinity;
            FindNearestNeighbor(root, query, ref closest, ref closestDist);
            return closest;
        }

        private void FindNearestNeighbor(Node node, double[] query, ref double[] closest, ref double closestDist)
        {
            if (node == null)
            {
                return;
            }

            double dist = EuclideanDistance(node.Point, query);
            if (dist < closestDist)
            {
                closest = node.Point;
                closestDist = dist;
            }

            double r = Math.Abs(node.Point[node.Axis] - query[node.Axis]);
            if (query[node.Axis] < node.Point[node.Axis])
            {
                FindNearestNeighbor(node.Left, query, ref closest, ref closestDist);
                if (r < closestDist)
                {
                    FindNearestNeighbor(node.Right, query, ref closest, ref closestDist);
                }
            }
            else
            {
                FindNearestNeighbor(node.Right, query, ref closest, ref closestDist);
                if (r < closestDist)
                {
                    FindNearestNeighbor(node.Left, query, ref closest, ref closestDist);
                }
            }
        }

        private double EuclideanDistance(double[] p1, double[] p2)
        {
            double sum = 0.0;
            for (int i = 0; i < p1.Length; i++)
            {
                double diff = p1[i] - p2[i];
                sum += diff * diff;
            }
            return Math.Sqrt(sum);
        }

        private class PointComparer : IComparer<double[]>
        {
            private readonly int axis;

            public PointComparer(int axis)
            {
                this.axis = axis;
            }

            public int Compare(double[] x, double[] y)
            {
                return x[axis].CompareTo(y[axis]);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            double[][] points = new double[][]
            {
                new double[] {2, 3},
                new double[] {5, 4},
                new double[] {9, 6},
                new double[] {4, 7},
                new double[] {8, 1},
                new double[] {7, 2},
            };

            KdTree kdTree = new KdTree(points);
            double[] query = new double[] { 4, 5 };
            double[] closest = kdTree.FindNearestNeighbor(query);

            Console.WriteLine("The closest point to ({0}, {1}) is ({2}, {3})", query[0], query[1], closest[0], closest[1]);
        }
    }
}

在上面的示例中，我们定义了一个KdTree类，包含一个Node节点类和一个KdTree类。使用点集创建KD树的过程在BuildKdTree方法中实现，查找距某个点最近的点的过程在FindNearestNeighbor方法中实现。

我们在Main方法中创建了一个点集points和一个查询点query，然后使用KdTree类来构建KD树，并查找最近的点closest。最后输出结果。