C# 在 XY 网格上查找附近的点

Question

假设我有一个 100×100 的网格。

现在我在 23,70 有一个位置。

如何找到此网格上距离为 5 以内的所有 XY 点？

Answer 1

你的问题有点含糊，但可能有一些简单的方法可以快速，这取决于你的要求和定义。

假设我们讨论的是单位正方形网格，有 3 种主要方法来定义距离：

8个方向的步数：n, ne, e, se, s, sw, w, nw
4个方向的步数：n、e、s、w
细胞间的直线距离（毕达哥拉斯）

第一个是最简单的，就是一个从[x - 5, y - 5]到[x + 5, y + 5]的正方形。足够快，可以即时计算。

第二个选项是满足以下函数的菱形：

static bool InRange(Point C, Point P) => (Math.Abs(P.X - C.X) + Math.Abs(P.Y - C.Y)) <= 5;

最后，线性距离使用毕达哥拉斯计算单元格之间的距离并将其与您的阈值进行比较。最终形状将取决于您如何处理重叠。您可以使用以下测试函数：

static bool InRange(Point C, Point P) => ((P.X - C.X) * (P.X - C.X)) + ((P.Y - C.Y) * (P.Y - C.Y)) <= 25;

请注意，在所有情况下，可能的解决方案范围都落在第一个解决方案定义的正方形内，因此您不必测试网格上的每个单元格。最多有 24 个测试（距离为 5）由网格大小修改。

这是一个基于上述内容的通用解决方案，使用 LINQ 因为我喜欢它：

public static IEnumerable<Point> PointsInRange(this Point C, int range, int method)
{
    // select filter function
    Func<int, int, bool> filter = (x, y) => true;
    if (method == 1)
        filter = (x, y) => (Math.Abs(x) + Math.Abs(y)) <= range;
    else if (method == 2)
        filter = (x, y) => (x * x + y * y) <= (range * range);

    // apply filter to all cells in potential range
    var validOffsets = 
        from dx in Enumerable.Range(-range, range * 2 + 1)
        from dy in Enumerable.Range(-range, range * 2 + 1)
        where (dx != 0 || dy != 0) && filter(dx, dy)
        select new { dx, dy };

    // offset from center and clip to grid
    var result = 
        from o in validOffsets
        let x = C.x + o.dx
        let y = C.y + o.dy
        where x >= 0 && x < 100 && y >= 0 && y < 100
        select new Point(x, y);

    return result;
}

您可以一如既往地应用一些加速。

当然，如果您只想获取特定范围（例如 5）的有效单元格，则可以通过在数组中指定有效偏移量来进一步减少它，而不是像上面那样计算它们。您可以剪切该方法的整个开头，并将其替换为具有所需形状的常量数组。或者将这两种思路结合起来，缓存答案，这样你就可以灵活地选择任意范围，并且只计算一次有效偏移量的速度。

C# 在 XY 网格上查找附近的点

C# Find Nearby Points on a XY Grid

c#

grid

distance

points