C#中等间距点2D数组半径范围内点快速查询方案咨询

看你的问题，应该是在处理规则网格上的点搜索吧？之前我做类似的地图网格点查询时，也踩过kdTree和低效循环的坑，针对等间距点的特性，有几个能显著提升效率的方案，给你参考：

既然你的点是等间距排列的，那完全不用遍历所有点或者依赖kdTree（kdTree更适合不规则分布的点集）。核心思路是先算出半径范围内覆盖的网格索引区间，只遍历这个区间内的点，再做距离校验：

1. 先确定网格的间距（假设为d，如果是整数网格，d就是1）；
2. 根据中心点坐标和半径，计算x/y方向上需要遍历的最小/最大索引；
3. 遍历这个索引区间内的所有点，判断是否在半径范围内。

示例代码（C#）：

// 替换成你的实际参数
double gridSpacing = 1.0;
double centerX = 50.0;
double centerY = 50.0;
double radius = 10.0;
double squaredRadius = radius * radius;

// 计算x/y方向的索引范围
int xMin = (int)Math.Floor((centerX - radius) / gridSpacing);
int xMax = (int)Math.Ceiling((centerX + radius) / gridSpacing);
int yMin = (int)Math.Floor((centerY - radius) / gridSpacing);
int yMax = (int)Math.Ceiling((centerY + radius) / gridSpacing);

List<int[]> resultPoints = new List<int[]>();
for (int xIdx = xMin; xIdx <= xMax; xIdx++)
{
    for (int yIdx = yMin; yIdx <= yMax; yIdx++)
    {
        // 计算当前点的实际坐标
        double pointX = xIdx * gridSpacing;
        double pointY = yIdx * gridSpacing;
        
        // 计算距离平方（避免开根号，提升速度）
        double dx = pointX - centerX;
        double dy = pointY - centerY;
        if (dx * dx + dy * dy <= squaredRadius)
        {
            resultPoints.Add(new int[] { (int)pointX, (int)pointY });
        }
    }
}

这个方案的时间复杂度是O((2r/d)^2)，比遍历所有点或者kdTree搜索快得多，尤其是当网格间距越小、半径越大时，优势越明显。

如果需要多次执行相同半径的搜索，可以先预计算出所有相对于中心点的偏移量，之后每次搜索只需要把偏移量加到中心点坐标上，再用哈希表快速判断这些点是否存在于你的点集中：

1. 预计算所有满足dx² + dy² ≤ 半径²的整数偏移量（如果是浮点网格，调整为浮点偏移）；
2. 把所有点的坐标存入哈希表（比如用Tuple<int, int>作为键），实现O(1)的存在性检查；
3. 每次搜索时，遍历预计算的偏移量，生成候选点，检查是否在哈希表中，存在则加入结果。

优化后的偏移量生成代码：

List<int[]> precomputedOffsets = new List<int[]>();
int radiusInt = (int)radius;
double squaredRadius = radius * radius;

// 处理x=0的情况（包括y=0的原点）
for (int y = 0; y * y <= squaredRadius; y++)
{
    precomputedOffsets.Add(new int[] { 0, y });
    if (y != 0)
    {
        precomputedOffsets.Add(new int[] { 0, -y });
    }
}

// 处理x≠0的情况，只遍历第一象限再对称生成其他象限
for (int x = 1; x * x <= squaredRadius; x++)
{
    int maxY = (int)Math.Floor(Math.Sqrt(squaredRadius - x * x));
    for (int y = 0; y <= maxY; y++)
    {
        precomputedOffsets.Add(new int[] { x, y });
        if (y != 0)
        {
            precomputedOffsets.Add(new int[] { x, -y });
        }
        precomputedOffsets.Add(new int[] { -x, y });
        if (y != 0)
        {
            precomputedOffsets.Add(new int[] { -x, -y });
        }
    }
}

// 初始化哈希表存储所有点
HashSet<Tuple<int, int>> pointSet = new HashSet<Tuple<int, int>>();
foreach (var point in your2DPointArray)
{
    pointSet.Add(Tuple.Create(point[0], point[1]));
}

// 搜索时直接用偏移量生成候选点
List<int[]> result = new List<int[]>();
foreach (var offset in precomputedOffsets)
{
    int candidateX = (int)centerX + offset[0];
    int candidateY = (int)centerY + offset[1];
    var candidate = Tuple.Create(candidateX, candidateY);
    if (pointSet.Contains(candidate))
    {
        result.Add(new int[] { candidateX, candidateY });
    }
}

这个方案的优势是预计算一次后，每次搜索的时间复杂度是O(k)，k是半径内的点数量，非常适合高频次的相同半径查询。

如果你的点集规模极大（比如百万级以上），可以把整个空间划分成大小为radius×radius的块，每个块存储内部的点。搜索时只需要检查中心点所在块以及周围的8个块，就能覆盖所有半径内的点，避免遍历整个点集：

1. 定义块的大小为blockSize = radius；
2. 用字典存储块索引（比如Tuple<int, int>，由x//blockSize和y//blockSize生成）到点列表的映射；
3. 搜索时，计算中心点所在的块索引，然后遍历该块和周围8个块的所有点，判断是否在半径范围内。

这个方案能把搜索范围从整个空间缩小到9个块，极大降低需要检查的点数量，适合动态点集或者超大规模场景。

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