KD 树和 R 树有什么区别? [英] What is the difference between a KD-tree and a R-tree?

问题描述

我看了KD-tree和R-tree的定义.在我看来，它们几乎相同.

I looked at the definition of KD-tree and R-tree. It seems to me that they are almost the same.

KD 树和 R 树有什么区别?

What's the difference between a KD-tree and an R-tree?

推荐答案

R-trees 和 kd-trees 基于类似的想法(基于轴对齐区域的空间分区)，但主要区别在于:

R-trees and kd-trees are based on similar ideas (space partitioning based on axis-aligned regions), but the key differences are:

• kd 树中的节点表示分离平面，而 R 树中的节点表示边界框.
• kd-trees 将整个空间划分为多个区域，而 R-trees 仅将包含感兴趣点的空间子集划分.
• kd-trees 代表一个不相交的分区(点只属于一个区域)，而 R-tree 中的区域可能重叠.

• Nodes in kd-trees represent separating planes, whereas nodes in R-trees represent bounding boxes.
• kd-trees partition the whole of space into regions whereas R-trees only partition the subset of space containing the points of interest.
• kd-trees represent a disjoint partition (points belong to only one region) whereas the regions in an R-tree may overlap.

(划分空间有很多类似的树结构:四叉树、BSP-树、R*-树等)

(There are lots of similar kinds of tree structures for partitioning space: quadtrees, BSP-trees, R*-trees, etc. etc.)

这篇关于KD 树和 R 树有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！