写给 Baby 的 Kd-tree 的实现原理 - demo程序

import numpy as np import math import global_parameters import point_array import tree_zone """ 1.kd树节点对应区域 region of a kd-tree node 2.kd树节点对应区域的产生(包括划分线段的产生) generate the regions of kd-tree nodes kd树节点数列已包含kd树的全部信息 kd树节点侧重于对树形数据结构的描述 kd树节点对应区域侧重于对点列分割结果的几何描述 这里额外计算kd树节点对应区域是为了数据更直观, 也方便可视化画图 @author wzf@robotics_notes @web_address https://blog.csdn.net/woyaomaishu2?type=blog @version 1.0 """ global root_point, min_range, max_range min_range = global_parameters.get_min_range() max_range = global_parameters.get_max_range() # 每一个kd树节点对应的区域范围 class TreeZone: def __init__(self, node_point, start_point, end_point, leftbottom_corner, righttop_corner, parent_zone): self.node_point_ = node_point # kd树节点坐标 self.start_point_ = start_point # 经过对应kd树节点的kd树区域的划分线的起始点，X轴划分时对应垂直线的最下点，Y轴划分时对应水平线的最左点 self.end_point_ = end_point # 经过对应kd树节点的kd树区域的划分线的终止点，X轴划分时对应垂直线的最上点，Y轴划分时对应水平线的最右点 self.leftbottom_corner_ = leftbottom_corner # kd树节点代表的矩形区域的左下点 self.righttop_corner_ = righttop_corner # kd树节点代表的矩形区域的右上点 self.parent_zone_ = parent_zone # 包含当前kd树节点矩形区域的父区域 # self.below_zone_ = None # self.above_zone_ = None def printTreeZone(self): print("Node: {},\t LineStart: {},\t LineEnd: {},\t LeftBottom: {},\t RightTop: {}" .format(self.node_point_, self.start_point_, self.end_point_, self.leftbottom_corner_, self.righttop_corner_)) # 产生每一个kd树节点对应的区域范围以及划分线段 class GenerateKdTreeZones: def __init__(self, kd_tree, leftbottom_corner, righttop_corner): self.tree_nodes_ = kd_tree.getKdNodes() # kd树节点数列,已包含kd树的完整信息 self.root_index_ = kd_tree.getRootIndex() # 根节点在kd树节点数列的位置指标 self.tree_zones_ = [] # 待计算填充的kd树区域数列 self.leftbottom_corner_ = leftbottom_corner # 左下角坐标 self.righttop_corner_ = righttop_corner # 右上角坐标 root_tree_zone = self.computeTreeZone_root() # 计算根节点对应矩形区域,即全部区域 root_tree_node = self.tree_nodes_[self.root_index_] # kd树根节点 self.computeTreeZone(root_tree_node, root_tree_zone) # 迭代计算根节点以下各个节点对应的区域 self.printTreeZones() def computeTreeZone_root(self): # 计算根节点对应矩形区域,即全部区域 root_point = self.tree_nodes_[self.root_index_].point_ if self.tree_nodes_[self.root_index_].partition_axis_ == 0: # 如果将全部区域在X轴方向上分为左右两半 start_point = np.array([self.tree_nodes_[self.root_index_].point_[0], min_range]) # 垂直的划分线段，经过根节点，Y坐标在上下限之间 end_point = np.array([self.tree_nodes_[self.root_index_].point_[0], max_range]) else: # 如果将全部区域在Y轴方向上分为上下两半 start_point = np.array([min_range, self.tree_nodes_[self.root_index_].point_[1]]) # 水平的划分线段，经过根节点，X坐标在左右限之间 end_point = np.array([max_range, self.tree_nodes_[self.root_index_].point_[1]]) a_tree_zone = tree_zone.TreeZone(root_point, start_point, end_point, self.leftbottom_corner_, self.righttop_corner_, None) # 产生根节点对应区域以及该区域的划分线段 self.tree_zones_.append(a_tree_zone) return a_tree_zone def computeTreeZone(self, parent_tree_node, parent_tree_zone): """ 迭代计算根节点以下各个节点对应的区域 输入: parent_tree_node —— kd树架构中的父节点 parent_tree_zone —— 父节点对应的区域 输出: 无 数据传输： self.tree_zones_ —— 填充的kd树对应几何区域的数组结果 """ if (parent_tree_node.below_child_ is not None): # 通过kd树判断父节点是否有低子节点，如有则计算低子节点对应的区域几何和划分线段 current_tree_node = parent_tree_node.below_child_ # 父节点的低子节点 (左侧或者下侧) 作为要计算对应区域几何的当前节点 if (current_tree_node.partition_axis_ == 0): # 如果当前kd树节点上的划分轴是X轴 """ 参考图形 ----------- | | | | -----+----- | | | | | | -----+----- """ start_point = np.array([current_tree_node.point_[0], parent_tree_zone.leftbottom_corner_[1]]) # 当前kd树节点上的划分线段的起始点, X坐标同经过的当前节点的X坐标，Y坐标同父区域左下角的Y坐标 end_point = np.array([current_tree_node.point_[0], parent_tree_zone.node_point_[1]]) # 当前kd树节点上的划分线段的终止点, X坐标同经过的当前节点的X坐标，Y坐标同父节点的Y坐标 a_tree_zone = tree_zone.TreeZone(current_tree_node.point_, start_point, end_point, parent_tree_zone.leftbottom_corner_, parent_tree_zone.end_point_, parent_tree_zone) # 当前kd树节点代表的区域，左下角就是父节点区域的左下角，右上角就是父节点的区域划分线段的终止点 self.tree_zones_.append(a_tree_zone) #写入区域划分数组 else: # 如果当前kd树节点上的划分轴是Y轴 """ 参考图形 ----------- | | | | | | +----+ | | | | | | | ----------- """ start_point = np.array([parent_tree_zone.leftbottom_corner_[0], current_tree_node.point_[1]]) # 当前kd树节点上的划分线段起始点，X坐标同父区域左下角的X坐标，Y坐标同当前节点的Y坐标 (水平方向，通过当前kd树节点) end_point = np.array([parent_tree_zone.node_point_[0], current_tree_node.point_[1]]) # 当前kd树节点上的划分线段终止点，X坐标同父节点的X坐标，Y坐标同当前节点的Y坐标 (水平方向，通过当前kd树节点) a_tree_zone = tree_zone.TreeZone(current_tree_node.point_, start_point, end_point, parent_tree_zone.leftbottom_corner_, parent_tree_zone.end_point_, parent_tree_zone) # 当前kd树节点代表的区域，左下角就是父节点区域的左下角，右上角就是父节点的区域划分线段的终止点 self.tree_zones_.append(a_tree_zone) #写入区域划分数组 self.computeTreeZone(current_tree_node, a_tree_zone)