基本概念数据结构被定义为专门用于保存数据的特殊类，即纯模型，例如汽车、儿童、动物、事件、员工、公司、客户……等等。这些数据通常在其他类的开头被声明或视为实例变量。此类的这些方法不应执行任何真正重要的工作，否则数据结构类就不再是数据结构了！因此，主要方法是 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 表示，该 B 表示由某些标准多边形格式外部定义，例如 wave front 或 java3D obj 文件，进入我们几何管道的输入流。多边形和法线提供的边界表示必须具有连贯的方向。对于主要在计算机图形学中实现的通常存档的几何模型，可能需要对输入文件进行过滤以处理非平面多边形和其他几何不准确性。然后，连贯定向三角形的输出流通过算法步骤转换为我们的双渐进 BSP（二叉搜索分区）树... 阅读更多

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

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

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

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

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