我有一个问题，在 x*y 大小的网格中，我提供了一个点，并且我需要找到最近的邻居。在实践中，我试图在 pygame 中找到距离光标最近的点，该点跨越颜色距离阈值，计算如下：
sqrt(((rgb1[0]-rgb2[0])**2)+((rgb1[1]-rgb2[1])**2)+((rgb1[2]-rgb2[2])**2))
到目前为止，我有一个函数可以计算网格的不同分辨率并将其减少两倍，同时始终保持最暗的像素。它看起来如下：
from PIL import Image
from typing import Dict
import numpy as np
#we input a pillow image object and retrieve a dictionary with every grid version of the 3 dimensional array:
def calculate_resolutions(image: Image) -> Dict[int, np.ndarray]:
resolutions = {}
#we start with the highest resolution image, the size of which we initially divide by 1, then 2, then 4 etc.:
divisor = 1
#reduce the grid by 5 iterations
resolution_iterations = 5
for i in range(resolution_iterations):
pixel_lookup = image.load() #convert image to PixelValues object, which allows for pixellookup via [x,y] index
#calculate the resolution of the new grid, round upwards:
resolution = (int((image.size[0] - 1) // divisor + 1), int((image.size[1] - 1) // divisor + 1))
#generate 3d array with new grid resolution, fill in values that are darker than white:
new_grid = np.full((resolution[0],resolution[1],3),np.array([255,255,255]))
for x in range(image.size[0]):
for y in range(image.size[1]):
if not x%divisor and not y%divisor:
darkest_pixel = (255,255,255)
x_range = divisor if x+divisor<image.size[0] else (0 if image.size[0]-x<0 else image.size[0]-x)
y_range = divisor if y+divisor<image.size[1] else (0 if image.size[1]-y<0 else image.size[1]-y)
for x_ in range(x,x+x_range):
for y_ in range(y,y+y_range):
if pixel_lookup[x_,y_][0]+pixel_lookup[x_,y_][1]+pixel_lookup[x_,y_][2] < darkest_pixel[0]+darkest_pixel[1]+darkest_pixel[2]:
darkest_pixel = pixel_lookup[x_,y_]
if darkest_pixel != (255,255,255):
new_grid[int(x/divisor)][int(y/divisor)] = np.array(darkest_pixel)
resolutions[i] = new_grid
divisor = divisor*2
return resolutions
这是我能想到的性能最高效的解决方案。如果此函数在不断变化的网格上运行，例如具有 x fps 的视频，则性能将非常紧张。我还考虑使用 kd 树算法，该算法可以简单地添加和删除网格上发生变化的任何点，但是当涉及到在静态网格上查找单个最近邻居时，此解决方案有可能提高资源效率。我愿意接受任何有关如何改进此功能的性能的建议。
现在，我正处于一个位置，例如，我尝试在 100x100 网格中找到当前光标位置的最近邻居。生成的缩小网格为 50^2、25^2、13^2 和 7^2。在网格的一部分如下所示的情况下：
我正在进行聚合步骤，其中网格的一部分由六个大方块组成，黑色的方块是当前光标位置，橙色的点是跨越颜色距离阈值的点，我不知道哪个对角线位置最近的邻居我想选择下一步进行搜索。在这种情况下，向下一级聚合表明左下角将是正确的选择。根据我有多少个网格层，这可能会导致最近邻搜索出现非常大的错误。有什么好的方法可以解决我这个问题吗？如果有多个方块显示它们具有相关位置，我是否必须在下一步中搜索所有方块才能确定？如果是这样的话，距离越远，我就越需要利用勾股定理等数学函数来断言我找到的两个正正方形在距离上是否重叠，并且可能包含最近的邻居，如果频繁调用该函数，这将再次开始成为性能密集型。在常规 kd 树上追求这个解决方案是否仍然有意义？目前网格大小仍然相当小（~800-600），但如果网格变大，性能可能会再次受到影响。对于这个问题，是否有一个可以在这里应用的良好的可扩展解决方案？
