基本概念数据结构被定义为专门用于存储数据的特殊类，即纯模型，例如汽车、儿童、动物、事件、员工、公司、客户等。这些数据通常在其他类的开头被声明或视为实例变量。此类的方法不应该执行任何真正重要的工作，否则数据结构类就不再是数据结构了！因此，主要的方法是 getter 和 setter（即访问器和修改器），通常是因为实例变量被视为私有的。还有一种替代观点：数据结构变量应该是公共的，并且可以直接从实例访问…… 阅读更多

基本概念运动数据结构被定义为一种数据结构，用于跟踪持续移动的几何系统的属性。例如，运动凸包数据结构跟踪一组 n 个移动点的凸包。运动数据结构的开发受到涉及连续运动的物理对象的计算几何问题的启发，例如机器人、动画或计算机图形学中的碰撞或可见性检测。概述运动数据结构在存在一组随时间变化的值的系统上实现，以所谓的顺序方式。因此，系统…… 阅读更多

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

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

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

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

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

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