栅格块-云南师范大学地理空间信息技术虚拟仿真试验中心.PPT

7.三维模型7.2三维数据结构 （二）线性八叉树 线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式)，将八叉树转换成一个线性表，表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。 7.三维模型7.2三维数据结构 线性八叉树编码 7.三维模型7.2三维数据结构 （三）一对八式八叉树 一个非叶结点有八个子节点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特征值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假设了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的，那么相应的存储位置也必须空闲在那里，以保证不会错误地存取到其它同辈结点的记录。 7.三维模型7.2三维数据结构 这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非结点。为了克服这种缺陷，一是增加计算量，即在存取相应结点记录之前，首先检查它的父结点记录，看一下之前有几个叶结点，从而可以知道应该如何存取所需结点记录。这种方法的存储需求无疑是最小的，但是要增加计算量；另一个是在记录中增加一定的信息，使计算工作适当减少或者更方便。例如在原记录中增加三个字节，一分为八，每个子结点对应三位，代表它的子结点在指针指向区域中的偏移。因此，要找到它的子结点的记录位置，只要固定地把指针指向的位置加上这个偏移值（0-7）乘上记录所占的字节数，就是所要的记录位置，因而一个结点的描述记录为： 偏移 指针 SWB SWT NWB NWT SEB SET NEB NET 思考题 1.何为场模型？它和栅格数据模型有什么关系？ 2.何为要素模型？它和矢量数据模型有什么关系？ 3.空间要素有哪些空间关系？ 4.什么是拓朴关系？ 5.什么是拓朴关系的9交模型？ 7.何为八叉树结构？它主要用于什么目的？ * 在体元造型系统中,不再使用几何曲面或者曲线来表示三维实体,而是以体素作为基本造型单元,每一个体素都具备有一整套的属性,如颜色(纹理色),方向(通常等于物体表面法向量,可作为计算反射光的依据),透明度,密度,强度,温度,速度,变形等“体元模型较之面元模型的优越性是显而易见的,首先体元模型可精确地描述物体在各个方向上和各个层面上的细节,而不是象面元模型一样只能表示物体的表面特性,其次它的表示所用的数据结构也简单,都是用统一的体素结构来表示物体,(而且这样的体素通常表示为具有一套固定属性的正方体,当然对应不同的系统应用领域,体素对应的属性也是不同的),这样无疑就简化了在模型表示上一层的模型操作层的实现。 4.基于要素的空间分析 4.1空间关系的基本概念 (3)点——面关系 点面相邻：点落在面的边界上； 点面相交：与上述相同； 点面相离：点远离一个面； 点面包含：点落在面内； 点面不存在重合。 (4）线——线关系 线线相邻：两个线有公共结点 线线相交：两条线立体或平面相交； 线线相离：两条线没有交点和汇合点； 线线包含：一条线是另一条线的一部分 线线重合：一条线完全与另一条线重合 4.基于要素的空间分析 4.1空间关系的基本概念 (5）线——面关系 线面相邻：线是面的部分或全部边界； 线面相交：一条线部分或全部穿过一个面 线面相离：线与面相互隔离 线面包含：一条线完全落入一个面里 线面不存在重合关系 6）面——面关系 面面相邻：两个面至少有段共同的边界； 面面相交：一个面与另一个面部分相交 面面相离：两个面完全不相交 面面包含：一面完全被另外一个面包含 面面重合：两个面的边界完全相同 邻接 相交 重合 相离 包含 点—点 点—线 点—面 线—面 面—面 线—线 4.基于要素的空间分析4.2拓朴空间关系分析 (一)拓朴属性 拓扑学是几何学的一个分支，它研究在拓扑变换下能够保持不变的几何属性——拓扑属性。欧氏平面上实体对象所具有的拓扑和非拓扑属性 ： 4.基于要素的空间分析4.2拓朴空间关系分析 拓扑属性 一个点在一个弧段的端点 一个弧段是一个简单弧段（弧段自身不相交） 一个点在一个区域的边界上 一个点在一个区域的内部 一个点在一个区域的外部 一个点在一个环的内部 一个面是一个简单面（面上没有“岛”） 一个面的连续性（给定面上任意两点，从一点可以完全在面的内部沿任意路径走向另一点） 非拓扑属性 两点之间的距离 一个点指向另一个点的方向 弧段的长度 一个区域的周