二维空间中随时间动态查询指定点附近运动点的高效方案

针对二维空间内大量恒定运动点的邻域查询需求，无需每次时间递增都重构空间索引，可利用点的恒定速度特性设计高效方案，以下是具体思路和实现：

核心思路 #

每个运动点的位置可参数化为时间的线性函数：Pos(t) = PosT0 + Velocity * t（其中Velocity是提前合并速度大小与方向的向量，避免重复计算）。查询t=T时中心点P半径R内的点，本质是求解不等式：

||(Q.PosT0 + Q.Velocity*T) - (P.PosT0 + P.Velocity*T)|| ≤ R

变形后可得：

||Q.PosT0 - (P.GetPos(T) - Q.Velocity*T)|| ≤ R

基于此，我们可以用速度分组+静态空间索引的方式，避免实时更新索引的开销。

最优方案：速度分组+静态空间树 #

方案步骤 #

1. 速度分组：将所有点按速度向量分组（可对速度做量化处理，避免浮点精度问题导致的冗余分组）。
2. 静态索引构建：为每个速度组构建基于初始位置PosT0的静态空间划分树（如Quad-Tree、KD-Tree），树结构无需随时间更新。
3. 查询流程：
   • 计算中心点P在t=T时的位置P_pos(T)。
   • 对每个速度组，计算等效初始查询中心：P_pos(T) - 组速度*T，以该中心为圆心、R为半径，在对应组的静态树中查询候选点。
   • 对候选点逐一验证t=T时的实际距离，过滤掉不符合条件的点。

优势 #

• 静态树无需更新，每次查询仅需计算等效查询区域，时间复杂度稳定为O(logN + K)（K为候选点数量）。
• 适配任意递增的查询时间t=T，无需额外维护动态索引的开销。

C# 代码实现 #

定义运动点结构 #

using System.Numerics;

public struct MovingPoint
{
    public Vector2 PosT0; // t=0时刻的初始位置
    public Vector2 Velocity; // 预计算的速度向量（Speed * Direction）

    // 获取指定时刻的位置
    public Vector2 GetPos(ulong t)
    {
        return PosT0 + Velocity * t;
    }

    // 可选：根据速度向量获取方向和速度大小
    public Vector2 Direction => Vector2.Normalize(Velocity);
    public float Speed => Velocity.Length();
}

实现索引与查询方法 #

using System.Collections.Generic;
using System;

public class MovingPointIndex
{
    // 键：量化后的速度向量；值：对应速度组的静态Quad-Tree
    private readonly Dictionary<Vector2, QuadTree<MovingPoint>> _velocityGroupedTrees;

    public MovingPointIndex(IEnumerable<MovingPoint> points)
    {
        _velocityGroupedTrees = new Dictionary<Vector2, QuadTree<MovingPoint>>();
        
        // 初始化所有点的分组与索引
        foreach (var point in points)
        {
            var quantizedVel = QuantizeVelocity(point.Velocity);
            if (!_velocityGroupedTrees.TryGetValue(quantizedVel, out var tree))
            {
                // 根据实际场景调整Quad-Tree的初始边界
                tree = new QuadTree<MovingPoint>(new Rectangle(-10000, -10000, 20000, 20000));
                _velocityGroupedTrees[quantizedVel] = tree;
            }
            tree.Insert(point, point.PosT0);
        }
    }

    // 速度量化：避免浮点精度问题导致相同速度被拆分到不同组
    private Vector2 QuantizeVelocity(Vector2 velocity)
    {
        // 保留两位小数，可根据精度需求调整
        return new Vector2(
            (float)Math.Round(velocity.X, 2),
            (float)Math.Round(velocity.Y, 2)
        );
    }

    public HashSet<MovingPoint> GetPointsNear(MovingPoint centerPoint, float radius, ulong time)
    {
        var result = new HashSet<MovingPoint>();
        var centerPosT = centerPoint.GetPos(time);

        foreach (var kvp in _velocityGroupedTrees)
        {
            var groupVel = kvp.Key;
            var tree = kvp.Value;

            // 计算等效初始查询中心
            var equivalentCenter = centerPosT - groupVel * time;
            // 查询静态树中的候选点
            var candidates = tree.QueryCircle(equivalentCenter, radius);

            // 验证实际距离，过滤无效点
            foreach (var point in candidates)
            {
                var pointPosT = point.GetPos(time);
                if (Vector2.Distance(pointPosT, centerPosT) <= radius)
                {
                    result.Add(point);
                }
            }
        }

        return result;
    }
}

// 简化版Quad-Tree实现（核心功能示例）
public class QuadTree<T>
{
    private readonly Rectangle _bounds;
    private readonly List<T> _points = new List<T>();
    private QuadTree<T>[] _children;
    private const int MaxPointsPerNode = 4;

    public QuadTree(Rectangle bounds)
    {
        _bounds = bounds;
    }

    // 插入点到Quad-Tree
    public void Insert(T point, Vector2 position)
    {
        if (_children == null)
        {
            _points.Add(point);
            if (_points.Count > MaxPointsPerNode)
            {
                Split();
            }
        }
        else
        {
            // 将点插入到对应子节点
            var childIndex = GetChildIndex(position);
            _children[childIndex].Insert(point, position);
        }
    }

    // 查询圆区域内的所有点
    public List<T> QueryCircle(Vector2 center, float radius)
    {
        var result = new List<T>();
        if (!IsCircleIntersectBounds(center, radius))
        {
            return result;
        }

        result.AddRange(_points);
        if (_children != null)
        {
            foreach (var child in _children)
            {
                result.AddRange(child.QueryCircle(center, radius));
            }
        }
        return result;
    }

    // 辅助方法：判断圆与当前节点边界是否相交
    private bool IsCircleIntersectBounds(Vector2 center, float radius)
    {
        // 可参考标准圆与矩形相交算法实现，此处简化返回true
        return true;
    }

    // 辅助方法：获取点对应的子节点索引
    private int GetChildIndex(Vector2 position)
    {
        var midX = _bounds.X + _bounds.Width / 2;
        var midY = _bounds.Y + _bounds.Height / 2;
        bool isLeft = position.X < midX;
        bool isTop = position.Y < midY;

        if (isLeft && isTop) return 0;
        if (!isLeft && isTop) return 1;
        if (isLeft && !isTop) return 2;
        return 3;
    }

    // 分裂当前节点为四个子节点
    private void Split()
    {
        var halfWidth = _bounds.Width / 2;
        var halfHeight = _bounds.Height / 2;
        _children = new QuadTree<T>[4];
        _children[0] = new QuadTree<T>(new Rectangle(_bounds.X, _bounds.Y, halfWidth, halfHeight));
        _children[1] = new QuadTree<T>(new Rectangle(_bounds.X + halfWidth, _bounds.Y, halfWidth, halfHeight));
        _children[2] = new QuadTree<T>(new Rectangle(_bounds.X, _bounds.Y + halfHeight, halfWidth, halfHeight));
        _children[3] = new QuadTree<T>(new Rectangle(_bounds.X + halfWidth, _bounds.Y + halfHeight, halfWidth, halfHeight));

        // 将当前节点的点分发到子节点（实际需存储点与位置的映射，此处简化）
        foreach (var point in _points)
        {
            // 示例省略位置获取逻辑，需根据实际实现补充
        }
        _points.Clear();
    }
}

内容的提问来源于stack exchange，提问作者Koen