Python在2D数据上应用网格，将非空网格单元格保存在树中

Question

我有一个 ~500 个 2D 点的数据集，给定坐标（也意味着我可以用单个整数引用每个点）（x，y）在 0 到 10 之间。现在，我正在尝试通过应用网格将该区域划分为规则的方形单元格。请注意，此过程在算法中重复，在某些时候会有>>>500 个平方单元格。

我想要实现的：遍历所有点，为每个点找到该点所在的方形单元格并保存此信息。
几步后：再次遍历所有点，为每个点标识其单元格和单元格的相邻单元格。获取这些单元格的所有点并将它们添加到例如列表中，以供进一步使用。

我的思考过程：由于会有很多空单元格，我不想为它们浪费内存，请使用树。
示例：在cell_39_41和cell_39_42中是一个点。第一级：根节点与子节点 39
第二级：39 节点，子节点 41，42
第三级：41 个节点（带子点 1）和 42 个节点（带子点 2
）第四级：代表实际点
的节点如果我在cell_39_41或cell_39_42中找到更多点，它们将被添加为各自三级节点的子节点。

class Node(object):
def __init__(self, data):
    self.data = data
    self.children = []
def add_child(self, obj):
    self.children.append(obj)

我省略了一个不相关的方法来返回单元格中的点。

此实现的问题：
1.如果我添加第二级或第三级节点，我将不得不引用它才能添加子级或在某个单元格及其相邻单元格中查找点。这意味着我必须进行大量昂贵的线性搜索，因为子列表没有排序。
2.我将添加数百个节点，但我需要能够通过唯一的名称来引用它们。这可能是一个很大的个人失败，但我想不出一种在循环中生成这些名称的方法。

所以我基本上很确定我的思维过程中有一些错误，或者可能使用的树实现不合适。我已经阅读了很多b树或类似工具的实现，但由于这个问题仅限于2D，我觉得它们太多了，不适合。

Answer 1

这个怎么样...

def add_point(data_dict, row, column, point):
    # modifies source of data_dict in place, since dictionaries are mutable
    data_dict.setdefault(row, {}).setdefault(column, []).append(point)
def get_table(data):
    out_dict = {}
    for row, column, point in data:
        add_point(out_dict, row, column, point)
    return out_dict

if __name__ == "__main__":
    data = [(38, 41, 38411), (39, 41, 39411), (39, 42, 39421)]
    points = get_table(data)    
    print points    
    add_point(points, 39, 42, 39422)    
    print points

Answer 2

使用 dict 的字典作为树：

tree = {
    '_data': 123,
    'node1': {
        '_data': 456,
        'node11': {
           'node111': {}
        },
    'node2': {
    }
}

在字典中搜索很快！

tree['node1']['node12']['node123']['_data'] = 123 # adding

唯一名称：

shortcuts = {}
shortcuts['name'] = tree['node1']['node11']['node111']
print shortcuts['name']['_data']