如何找到最近的N个网格点（贪心）
How to find nearest N grid points (greedy)
我正在使用二维数组来处理游戏中的对象。数组的维度就像笛卡尔网格上的坐标。当玩家选择一个点时，我想从数组中收集 N 个最近的网格单元，即使该点不是有效的数组索引。
示例：
从 [0,0] 到 [10,10] 的数组
如果玩家选择 (-1,-1)，N=3，则最近的点将为 [(0,0),(0,1),(1,0)]
蛮力的方法是计算选中的点和每个数组网格单元之间的欧几里得距离，将其放入列表中，然后排序。对于非常大的阵列，这可能会导致性能过高。有没有更贪婪的方法来做到这一点，例如，如果我知道 N 是什么？
我知道如果选择的点在网格内部，我们可以使用圆的公式来获得一个粗略的区域来检查，例如N/Pi = R^2。我们可以检查这个 R 值在 x 和 y 维度上创建的平方，这要快得多。
但是如果选择的点靠近网格边缘呢？还是关闭它？或者，如果您想忽略某些网格单元格？
我将从找到最接近给定点的小数坐标（即，不一定是整数）的点开始。如果只有一个坐标在网格范围之外，则只需将此坐标设置为最近的范围内坐标即可。如果两个坐标都在网格范围之外，那么最近的点将是其中一个角点。
鉴于该起点，您需要找到 N 个具有整数坐标的点。如果最近的点是一个角，它已经有整数坐标。否则最近点是最近点任一侧的网格点之一。
你知道其他 N-1 个点将连接到最近的网格点，因为你正在计算两个凸形的交集 - 一个圆形和一个矩形。我会保留一堆按距离排序的点。从最近的网格点的邻居开始。重复移除堆中最接近网格外原始点的点，并将其邻居放入堆中，如果它们不存在，直到您提取了其他 N-1 个点。
我正在使用二维数组来处理游戏中的对象。数组的维度就像笛卡尔网格上的坐标。当玩家选择一个点时，我想从数组中收集 N 个最近的网格单元，即使该点不是有效的数组索引。
示例： 从 [0,0] 到 [10,10] 的数组 如果玩家选择 (-1,-1)，N=3，则最近的点将为 [(0,0),(0,1),(1,0)]
蛮力的方法是计算选中的点和每个数组网格单元之间的欧几里得距离，将其放入列表中，然后排序。对于非常大的阵列，这可能会导致性能过高。有没有更贪婪的方法来做到这一点，例如，如果我知道 N 是什么？
我知道如果选择的点在网格内部，我们可以使用圆的公式来获得一个粗略的区域来检查，例如N/Pi = R^2。我们可以检查这个 R 值在 x 和 y 维度上创建的平方，这要快得多。
但是如果选择的点靠近网格边缘呢？还是关闭它？或者，如果您想忽略某些网格单元格？
我将从找到最接近给定点的小数坐标（即，不一定是整数）的点开始。如果只有一个坐标在网格范围之外，则只需将此坐标设置为最近的范围内坐标即可。如果两个坐标都在网格范围之外，那么最近的点将是其中一个角点。
鉴于该起点，您需要找到 N 个具有整数坐标的点。如果最近的点是一个角，它已经有整数坐标。否则最近点是最近点任一侧的网格点之一。
你知道其他 N-1 个点将连接到最近的网格点，因为你正在计算两个凸形的交集 - 一个圆形和一个矩形。我会保留一堆按距离排序的点。从最近的网格点的邻居开始。重复移除堆中最接近网格外原始点的点，并将其邻居放入堆中，如果它们不存在，直到您提取了其他 N-1 个点。