arrays - 如何找到最近的N个网格点(贪心)

Question

我正在使用二维数组来处理游戏中的对象。数组的维度就像笛卡尔网格上的坐标。当玩家选择一个点时，我想从数组中收集 N 个最近的网格单元，即使该点不是有效的数组索引。

例子:从 [0,0] 到 [10,10] 的数组如果玩家选择 (-1,-1)，N=3，则最近的点将是 [(0,0),(0,1),(1,0)]

蛮力方法是计算所选点与每个阵列网格单元之间的欧式距离，将其放入列表中，然后进行排序。对于非常大的阵列，这可能会导致性能过高。有没有更贪婪的方法来做到这一点，例如，如果我知道 N 是什么？

我知道如果选择的点在网格内部，我们可以使用圆的公式来获得一个粗略的区域来检查，例如N/Pi = R^2。我们可以检查此 R 值在 x 和 y 维度上创建的正方形，这要快得多。

但是如果选择的点靠近网格边缘呢？还是关闭它？或者，如果您想忽略某些网格单元格？

Answer 1

我将从找到最接近给定点的小数坐标(即不一定是整数)的点开始。如果只有一个坐标在网格范围之外，则只需将此坐标设置为最近的范围内坐标即可。如果两个坐标都在网格范围之外，那么最近的点将是其中一个角。

给定起点，您需要找到 N 个具有整数坐标的点。如果最近的点是一个角，它已经有整数坐标。否则，最近点是最近点任一侧的网格点之一。

您知道其他 N-1 个点将连接到最近的网格点，因为您正在计算两个凸形的交集 - 圆形和矩形。我会保留一堆按距离排序的点。从最近的网格点的邻居开始。重复移除堆中离网格外的原始点最近的点，并将其邻居放入堆中，如果它们不在堆中，直到您提取了其他 N-1 个点。