三维点云处理07-二叉树

三维点云处理07-二叉树

python实现

• 二叉树的构建
• KNN最近邻结果集合
• RNN最近邻结果集合
• KNN查找最近邻
• RNN查找最近邻
• 递归查找二叉树某一节点
• 迭代查找二叉树某一节点
• 前序，中序，后序遍历

result_set.py

import copy
# 存放dist和index的类
class DistIndex:
def __init__(self,distance,index):
self.distance = distance
self.index = index
def __lt__(self,other):
return self.distance < other.distance
# 存放KNN最近邻结果的集合
class KNNResultSet:
def __init__(self,capacity):
self.capacity = capacity
self.count = 0
self.worst_dist = 1e10
self.dist_index_list = []
for i in range(capacity):
self.dist_index_list.append(DistIndex(self.worst_dist,0))
self.comparison_counter = 0
def size(self):
return self.comparison_counter
def full(self):
return self.count == self.capacity
def worstDist(self):
return self.worst_dist
def add_point(self,dist,index):
self.comparison_counter += 1
if dist > self.worst_dist:
return
if self.count < self.capacity:
self.count += 1
i = self.count - 1
while i > 0:
if self.dist_index_list[i-1].distance > dist:
self.dist_index_list[i] = copy.deepcopy(self.dist_index_list[i-1])
i -= 1
else:
break
self.dist_index_list[i].distance = dist
self.dist_index_list[i].index = index
self.worst_dist = self.dist_index_list[self.capacity-1].distance
def __str__(self):
output = ''
for i, dist_index in enumerate(self.dist_index_list):
output += '%d - %.2fn' % (dist_index.index,dist_index.distance)
output += 'In total %d comparison operations'% self.comparison_counter
return output
# 存放RNN最近邻结果的集合
class RadiusNNResult:
def __init__(self,capacity):
self.capacity = capacity
self.count = 0
self.worst_dist = 1e10
self.dist_index_list = []
for i in range(capacity):
self.dist_index_list.append(DistIndex(self.worst_dist,0))
self.comparison_counter = 0
def size(self):
return self.comparison_counter
def full(self):
return self.count == self.capacity
def worstDist(self):
return self.worst_dist
def add_point(self,dist,index):
self.comparison_counter += 1
if dist > self.worst_dist:
return
if self.count < self.capacity:
self.count += 1
i = self.count - 1
while i > 0:
if self.dist_index_list[i-1].distance > dist:
self.dist_index_list[i] = copy.deepcopy(self.dist_index_list[i-1])
i -= 1
else:
break
self.dist_index_list[i].distance = dist
self.dist_index_list[i].index = index
self.worst_dist = self.dist_index_list[self.capacity-1].distance
def __str__(self):
output = ''
for i, dist_index in enumerate(self.dist_index_list):
output += '%d - %.2fn' % (dist_index.index,dist_index.distance)
output += 'In total %d comparison operations'% self.comparison_counter
return output

bst.py

import random
import math
import numpy as np
from result_set import KNNResultSet,RadiusNNResultSet
# 二叉树节点类
class Node:
def __init__(self,key, value = -1):
self.left = None
self.right = None
self.key = key
self.value = value
def __str__(self):
return "key:%s,value:%s"%(str(self.key),str(self.value))
# 递归实现二叉树插入
def insert(root,key,value = -1):
if root is None:
root = Node(key,value)
if key < root.key:
root.left = insert(root.left,key,value)
elif key > root.key:
root.right = insert(root.right,key,value)
else:
pass
return root
# KNN最近邻查找
def knn_search(root:Node, result_set:KNNResultSet,key):
if root is None:
return False
result_set.add_point(math.fabs(root.key - key),root.value)
if result_set.worstDist() == 0:
return True
if key <= root.key:
if knn_search(root.left,result_set,key):
return True
elif math.fabs(root.key - key) < result_set.worstDist():
return knn_search(root.right,result_set,key)
else:
return False
else:
if knn_search(root.right,result_set,key):
return True
elif math.fabs(root.key - key) < result_set.worstDist():
return knn_search(root.left,result_set,key)
else:
return False
# RNN最近邻查找
def rnn_search(root:Node, result_set:RadiusNNResult,key):
if root is None:
return False
result_set.add_point(math.fabs(root.key - key),root.value)
if key <= root.key:
if rnn_search(root.left, result_set, key):
return True
elif math.fabs(root.key - key) < result_set.worstDist():
return rnn_search(root.right,result_set,key)
else:
return False
else:
if rnn_search(root.right,result_set, key):
return True
elif math.fabs(root.key - key) < result_set.worstDist():
return rnn_search(root.left,result_set,key)
else:
return False
# 递归查找二叉树中某个节点
def search_recursive(root,key):
if root is None or root.key == key:
return root
if key < root.key:
return search_recursive(root.left,key)
else:
return search_recursive(root.right,key)
# 迭代查找二叉树中某个节点
def search_iterative(root,key):
current_node = root
while current_node is not None:
if key == current_node.key:
return current_node
elif key < current_node.key:
current_node = current_node.left
else:
current_node = current_node.right
return current_node
# 二叉树的前序遍历
def preorder(root):
if root is None:
return
print(root.key)
preorder(root.left)
preorder(root.right)
# 二叉树的中序遍历
def inorder(root):
if root is None:
return
inorder(root.left)
print(root.key)
inorder(root.right)
# 二叉树的后序遍历
def postorder(root):
if root is None:
return
postorder(root.left)
postorder(root.right)
print(root.key)
def main():
db_size = 100
data = np.random.permutation(db_size).tolist()
root = None
for i ,point in enumerate(data):
root = insert(root,point,i)
k = 5
radius = 2.0
query_key = 6
# 查找二叉树中是否存在某个节点
node1 = search_recursive(root,query_key)
node2 = search_iterative(root,query_key)
print(node1)
print(node2)
result_set1 = KNNResultSet(capacity=k)
result_set2 = RadiusNNResult(radius=radius)
knn_search(root,result_set1,query_key)
rnn_search(root,result_set2,query_key)
print(result_set1)
print(result_set2)
if __name__ == '__main__':
main()

递归实现二叉树节点的查找：

• 优点：
• 更容易理解和实现
• 代码更短

• 缺点：
• 很难一步一步的跟踪
• O(n)的空间复杂度，n是递归的次数

迭代实现二叉树节点的查找：

• 优点：
• 避免了堆栈，可以在嵌入式系统上运行，可以在GPU上运行
• 可以实现一步一步的跟踪
• O(1)的空间复杂度

• 缺点：
• 逻辑复杂

深度优先遍历

• 前序遍历：
• 根-左-右

• 中序遍历：
• 左-根-右

• 后序遍历：
• 左-右-根

最后

以上就是糟糕毛巾为你收集整理的三维点云处理07-二叉树的全部内容，希望文章能够帮你解决三维点云处理07-二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。