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

首先，需要定义一个表示点的类，例如：

public class Point
{
    public double X { get; set; }
    public double Y { get; set; }
}

然后，使用以下代码创建 KD 树：

public class KdTree
{
    private Node _root;

    private class Node
    {
        public Point Point { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        public bool IsVertical { get; set; }
    }

    public KdTree(List<Point> points)
    {
        _root = BuildTree(points, true);
    }

    private Node BuildTree(List<Point> points, bool isVertical)
    {
        if (points.Count == 0)
        {
            return null;
        }

        if (points.Count == 1)
        {
            return new Node
            {
                Point = points[0],
                IsVertical = isVertical
            };
        }

        points.Sort((a, b) => isVertical ? a.X.CompareTo(b.X) : a.Y.CompareTo(b.Y));

        int medianIndex = points.Count / 2;

        return new Node
        {
            Point = points[medianIndex],
            Left = BuildTree(points.GetRange(0, medianIndex), !isVertical),
            Right = BuildTree(points.GetRange(medianIndex + 1, points.Count - medianIndex - 1), !isVertical),
            IsVertical = isVertical
        };
    }
}

接下来，使用以下代码查找距离指定点最近的点：

public Point FindNearest(Point queryPoint)
{
    Node nearestNode = _root;
    double nearestDistance = double.PositiveInfinity;

    Search(_root, queryPoint, ref nearestNode, ref nearestDistance);

    return nearestNode.Point;
}

private void Search(Node node, Point queryPoint, ref Node nearestNode, ref double nearestDistance)
{
    if (node == null)
    {
        return;
    }

    double distance = GetDistance(node.Point, queryPoint);

    if (distance < nearestDistance)
    {
        nearestNode = node;
        nearestDistance = distance;
    }

    double axisDistance = node.IsVertical ? Math.Abs(node.Point.X - queryPoint.X) : Math.Abs(node.Point.Y - queryPoint.Y);

    if (queryPoint < node.Point)
    {
        Search(node.Left, queryPoint, ref nearestNode, ref nearestDistance);
        if (axisDistance <= nearestDistance)
        {
            Search(node.Right, queryPoint, ref nearestNode, ref nearestDistance);
        }
    }
    else
    {
        Search(node.Right, queryPoint, ref nearestNode, ref nearestDistance);
        if (axisDistance <= nearestDistance)
        {
            Search(node.Left, queryPoint, ref nearestNode, ref nearestDistance);
        }
    }
}

private double GetDistance(Point a, Point b)
{
    double dx = a.X - b.X;
    double dy = a.Y - b.Y;
    return Math.Sqrt(dx * dx + dy * dy);
}

注意，这里的 `GetDistance` 方法使用的是欧几里得距离。如果需要使用曼哈顿距离或其他距离度量，请相应地更改该方法。