I have N numbers of geographical points and coordinates of the points are being updated frequently. And the number N is very big. I need to find points within a rectangle. I have tried searching by all points, by using 2d Array grid and R tree. I had to remove and then insert again which is costly operation.
2
-
1quad tree? GIST?Ian Turton– Ian Turton2021-09-16 15:36:12 +00:00Commented Sep 16, 2021 at 15:36
-
Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.Community– Community Bot2021-09-22 03:59:15 +00:00Commented Sep 22, 2021 at 3:59
Add a comment
|
1 Answer
Indexing spatial data is a complex topic. If you just have points you can index them using a sparse grid (better memory utilization than just 2d array):
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
if you need to find by rectangle then you can just iterate over grid cells that are in that rectangle
But of course you will need to remove and insert points whenever the coordinates change. Indexing is costly.
2 Comments
Marcin Cuprjak
clarification: for the get() and contains() methods you can put coordinate of the cell, that's how you can find things within a rectangle - you just need to check all cells in that rectangle
fahad hasan
I have already done that. I need to periodically update coordinate positions.
