三维边界表示法.doc

2.5 三维数据结构二、三维边界表示法1、方法原理首先考虑一个简单的四面体应如何表示。它是一个平面多面体，即它的每个表面均可以看成是一个平面多边形。为了做到无歧义地、有效地表示，需指出它的顶点位置以及由哪些点构成边，哪些边围成一个面等一些几何与拓扑的信息。比较常用的表示一个平面多面体的方法是采用三张表来提供这些信息(如图25-4)，这三张表就是：1）顶点表：用来表示多面体各顶点的坐标；2）边表：指出构成多面体某边的两个顶点；3）面表：给出围成多面体某个面的各条边。对于后两个表一般使用指针的方法指出有关的边、点存放的位置。为了更快地获得所需信息，更充分地表达点、线、面之间的拓扑关系，可以把其它一些有关的内容结合到所使用的表中。图25-4中的扩充后的边表就是将边所属的多边形信息结合进边表中以后的形式。这样利用这种扩充后的表，可知某条边是否为两个多边形的公共边，如果是，相应的两个多边形也立即知道。这是一种用空间换取时间的方法。是否要这样做，应视具体的应用而定，同样也可根据需要适当地扩充其它两张表来提高处理的效率。除了描述它的几何结构，还要指出该多面体的一些其它特性。例如每个面的颜色、纹理等等。这些属性可以用另一个表独立存放。当有若干个多面体时，还必须有一个对象表。每个多面体在这个表中列出围成它的诸面，同样也可用指针的方式实现，这时面表中的内容，已不再是只和一个多面体有关。2、特点采用这种分列的表来表示多面体，可以避免重复地表示某些点、边、面，因此一般来说存贮量比较节省，对图形显示更有好处。例如，由于使用了边表，可以立即显示出该多面体的线条画，也不会使同一条边重复地画上两次。可以想象，如果表中仅有多边形表而省却了边表，两个多边形的公共边不仅在表示上要重复，而且很可能会画上两次。类似地，如果省略了顶点表，那么作为一些边的公共顶点的坐标值就可能反复地写出好多次。3、拓扑检查对于比较复杂的多面体要输入大量的数据。检查输入的数据是否一致、是否完全，是一项必不可少的工作，这就是通常所说的拓扑检查。一般来说，在数据表中包含的信息越多，输入时有错的可能性也越大，但是可用来检查是否有错的手段也会随之增加。对上面提及的数据结构，至少可以检查以下诸项：1)顶点表中的每个顶点至少是两条边的端点；2)每条边至少是一个多边形的边；3)每个多边形是封闭的；4)每个多边形至少有一条边是和另一个多边形共用的；5)若边表中包含了指向它所属多边形的指针，那么指向该边的指针必在相应的多边形中出现。这些检查对于维护表示多面体的数据库的全体一致性是有效的，而复杂的情况应当有专门的程序来检查。4、应用以上讨论的只是简单的平面多面体的三维边界表示，但是GIS研究的对象是自然实体，其三维形状的复杂程度难以描述。例如岩石的外表不规则，组成的平面可有成千上万，如何用三维边界表示法表示呢?从理论上讲，对任意的三维形体只要它满足一定的条件，总可找到一个适合的平面多面体来近似地表示这个三维形体，且使误差保持在一定的范围之内。但是在实际上，这种逼近受到多方面因素的制约，解决这个问题的方法也不一而足。通常，这个问题可以叙述成：要表示某个三维形体，又仅知道从这个形体的外表面S0上测得的一组点P1Pn的坐标。为了解决这个问题，首先要为这些点建立起某种关系。这种关系被称为这些点代表的形体结构。可以由一个图来表示，图的顶点就是这里给定的那组点P1Pn，而图的边的给定方式则恰好反映了所设想的结构。不同的图，有不同的边(也就是连接这些顶点的方法不同)，相应地，这个图对应的平面多面体也不同，这可由图25-5来示意。在众多的结构中，每个面均是三角形的平面多面体起着很重要的作用(这跟不规则三角网TIN很类似)。即使对结构加上了这种限制，同一组点仍可得到不同的平面多面体。因此，人们自然会想到，在这类多面体中，究竟在拥有