为了查找附近对象的速度而将地理空间对象划分为“桶”的方法

import math

class Grid:
    def __init__(self, width, height, cell_size):
        self.cell_size = cell_size
        self.grid = [[[] for _ in range(height // cell_size)] for _ in range(width // cell_size)]

    def insert(self, point):
        x, y = point
        cell_x = int(x // self.cell_size)
        cell_y = int(y // self.cell_size)
        self.grid[cell_x][cell_y].append(point)

    def query(self, point, radius):
        results = []
        x, y = point
        start_x = max(0, int((x - radius) // self.cell_size))
        end_x = min(len(self.grid) - 1, int((x + radius) // self.cell_size))
        start_y = max(0, int((y - radius) // self.cellial_size))
        end_y = min(len(self.grid[0]) - 1, int((y + radius) // self.cell_size))

        for i in range(start_x, end_x + 1):
            for j in range(start_y, end_y + 1):
                for p in self.grid[i][j]:
                    if math.sqrt((p[0] - x) ** 2 + (p[1] - y) ** 2) <= radius:
                        results.append(p)
        return results

# 示例使用
grid = Grid(1000, 1000, 100)
grid.insert((150, 200))
grid.insert((250, 300))
print(grid.query((200, 250), 150))