0

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

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

我的思考过程：由于会有很多空单元格，我不想为它们浪费内存，所以使用树。
示例：在 cell_39_41 和 cell_39_42 中是一个点。第一级：具有子节点
39 的根节点 第二级：具有子节点 41,42 的 39 个节点
第三级：具有子点 1 的 41 个节点和具有子点 2 的 42 个节点
第四级：代表实际点的节点
如果我在 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-trees 或类似的实现，但由于这个问题仅限于 2D，我觉得它们太多了，不适合。

4

2 回答 2

2

这个怎么样 ...

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
于 2012-06-11T13:45:43.713 回答
1

使用 dict 的 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']
于 2012-06-11T12:31:21.283 回答