希尔伯特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-rep流很明显，需要设置一个生产者进程，将由某种标准多边形格式（例如wavefront或java3D obj文件）外部定义的B-rep导入到我们几何管道的输入流中。多边形和法线提供的边界表示必须一致定向。对于主要在计算机图形学中实现的通常存档的几何模型，可能需要对输入文件进行过滤以应对非平面多边形和其他几何不准确性。然后，一致定向的三角形的输出流将通过算法步骤转换为我们的双重渐进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表示给定查询检索到的点的数量。范围树可以与区间树区分开来：而不是……阅读更多