特征坐标频繁更新时，使用哪种空间数据结构?我试过R树，2d网格

Question

我有N个地理点，这些点的坐标经常更新。数字N很大。我需要在矩形内找到点。我试过搜索所有的点，通过使用二维数组网格和R树。我必须移除然后再插入，这是一个昂贵的操作。

Answer 1

索引空间数据是一个复杂的主题。如果你只有点，你可以使用稀疏网格(比2d数组更好的内存利用率)索引它们:

class SpatialGrid:
def __init__(self, cell_size):
self._cells: DefaultDict[Tuple, Set] = defaultdict(set)
self._cell_size = cell_size
def __len__(self):
return len(self._cells)
def _key(self, x: float, y: float) -> Tuple:
return int(x / self._cell_size), int(y / self._cell_size)
def add(self, x: float, y: float, obj: object) -> None:
i_x, i_y = self._key(x, y)
for i in (-1, 0, 1):
for j in (-1, 0, 1):
self._cells[(i_x + i, i_y + j)].add(obj)
def get(self, x: float, y: float) -> Set:
return self._cells[self._key(x, y)]
def contains(self, x: float, y: float) -> bool:
return self._key(x, y) in self._cells

如果你需要查找by矩形那么你可以遍历矩形内的网格单元格

但是，当坐标改变时，当然需要删除和插入点。索引成本很高。