希尔伯特 R 树，一种 R 树的变体，被定义为多维对象（如线、区域、3D 对象或高维基于特征的参数对象）的索引。可以将其想象为 B+ 树对多维对象的扩展。R 树的性能取决于聚类节点上数据矩形的算法质量。希尔伯特 R 树实现空间填充曲线，特别是希尔伯特曲线，以对数据矩形强加线性排序。希尔伯特 R 树有两种类型：一种用于静态数据库，另一种用于动态数据库。在这两种情况下，都实现了希尔伯特空间填充曲线以实现多维对象的更好排序…… 阅读更多

基本概念在数据处理的情况下，R* 树被定义为一种用于索引空间信息的 R 树变体。R* 树的构建成本略高于标准 R 树，因为数据可能需要重新插入；但生成的树通常会具有更好的查询性能。与标准 R 树相同，它可以存储点数据和空间数据。R* 树的概念由 Norbert Beckmann、Hans-Peter Kriegel、Ralf Schneider 和 Bernhard Seeger 于 1990 年提出。R* 树与 R 树的区别 R* 树通过重复插入构建。此树中的重叠很少（即几乎没有），从而产生良好的查询性能。…… 阅读更多

1 B 表示流明确规定设置一个生产者进程，该进程导入由某些标准多边形格式（例如波前或 java3D obj 文件）外部定义的 B 表示，并将其导入到我们几何管道的输入流中。多边形和法线提供的边界表示必须一致地定向。对于主要在计算机图形学中实现的通用存档几何模型，可能需要对输入文件进行过滤以应对非平面多边形和其他几何不准确性。然后，由算法步骤将一致定向三角形的输出流转换为我们的双渐进 BSP（二叉搜索分区）树…… 阅读更多

空间搜索结构基于 60 年代和 70 年代在计算机科学中发明的相同思想，用于解决快速处理大型符号数据集的问题，而不是几何数据，例如人员姓名列表。发明了首先根据字母表对姓名列表进行排序，并将排序后的列表存储在数组中，可以使用二叉搜索算法在 log2n 个操作中计算某个新名称是否已在列表中，而不是使用顺序搜索所需的 n/2 个预期操作。这是…… 阅读更多

在计算机科学中，一种称为二叉空间分割 (BSP) 的方法用于通过实现超平面作为分区来递归地将空间细分为两个凸集。这种细分过程导致以树形数据结构（称为 BSP 树）的形式表示区域内的对象。二叉空间分割发明于 1969 年的 3D 计算机图形学背景下，其中 BSP 树的结构允许有关场景中对象的地理空间信息，这在渲染中很有用，例如相对于某个对象的物体按从前到后的顺序排列…… 阅读更多

压缩四叉树在存储与细分单元相对应的每个节点时，我们最终可能会存储大量空节点。可以通过仅存储其叶子具有有趣数据（即“重要子树”）的子树来减少此类稀疏树的大小。我们实际上可以进一步减少大小。当我们只考虑重要的子树时，修剪过程可能会避免树中度数为二（到一个父节点和一个子节点的链接）的路径。事实证明，我们只需要存储节点 U…… 阅读更多

区域四叉树用于表示通过将区域划分为四个相等的象限、子象限等来对二维空间进行分区，每个叶节点包含与特定子区域相对应的数据。树中的每个节点要么与恰好四个子节点相关联，要么没有子节点（叶节点）。遵循此分解策略（即细分子象限，直到和除非子象限中有有趣的数据需要进一步细化）的四叉树的高度对被细化空间中有趣区域的空间分布敏感并依赖于它…… 阅读更多

点四叉树是二叉树的一种适应，用于表示二维点数据。点四叉树共享所有四叉树的特征。它通常在比较二维有序数据点方面非常有效，通常在 O(log n) 时间内执行。出于完整性考虑，点四叉树值得一提，但 k-d 树作为广义二叉搜索的工具超过了它们。点四叉树的构建如下。给定要插入的下一个点，我们计算它所在的单元格并将其添加到树中。新的点被添加，使得包含它的单元格被该点划分成象限…… 阅读更多

四叉树是用于有效存储二维空间中点数据的树。在这棵树中，每个节点最多有四个子节点。我们可以通过执行以下步骤从二维区域构建四叉树当前二维空间被划分为四个盒子。如果一个盒子包含一个或多个点，则构建一个子对象，并在其中存储盒子的二维空间。如果一个盒子不包含任何点，则不要为它构建子节点。对每个子节点执行递归。四叉树在图像压缩中实现，其中每个节点包含…… 阅读更多

范围树被定义为一种有序树形数据结构，用于保存点列表。它允许有效地检索给定范围内的所有点，并且通常在二维或更高维度中实现。它与 kd 树相同，只是查询时间更快（O(logd n + k)），但存储空间更差（O(n logd-1 n)），其中 d 表示空间的维度，n 表示树中点的数量，k 表示给定查询检索到的点数。范围树可以与区间树区分开来：而不是…… 阅读更多