grids-9.py

import collections
import math


class Grids9:
    unit_width = 10
    unit_height = 10

    def __init__(self, w, h):
        grids = {(i, j): set()
                 for i in range(math.ceil(w / self.unit_width))
                 for j in range(math.ceil(h / self.unit_height))}

        deltas = -1, 0, 1
        relations = collections.defaultdict(set)

        for grid in grids:
            x, y = grid
            for i in deltas:
                for j in deltas:
                    neighbor = x + i, y + j
                    if neighbor in grids:
                        relations[grid].add(neighbor)

        self.relations = relations  # readonly
        self.grids = grids
        self.ids = {}
        self.w = w
        self.h = h

    def disappear(self, id):
        grid = self.ids.pop(id, None)
        if not grid:
            return
        self.grids[grid].discard(id)

    def appear(self, id, x, y):
        grid_curr = x // self.unit_width, y // self.unit_height
        grid_prev = self.ids.get(id)
        if grid_prev == grid_curr:
            return
        if grid_prev:
            self.grids[grid_prev].discard(id)
        self.grids[grid_curr].add(id)
        self.ids[id] = grid_curr

    def find_nearby(self, id):
        grid = self.ids[id]
#         return set.union(*(self.grids[i] for i in self.relations[grid]))
        l = []
        for neighbor in self.relations[grid]:
            l.extend(self.grids[neighbor])
        return l


m = Grids9(1000, 1000)

m.appear(0, 0, 0)
m.appear(1, 0, 0)
m.appear(2, 19, 0)
m.appear(3, 20, 0)
m.appear(3, 1, 0)

m.find_nearby(3)