一种支持三维Delaunay三角剖分与Voronoi图生成的数据结构

1、第10卷第12期2010年4月167121815(2010)1222974205科学技术与工程ScienceTechnologyandEngineeringVol110No112Apr120102010Sci1Tech1Engng1一种支持三维Delaunay三角剖分与Voronoi图生成的数据结构温来祥刘金义3(辽宁石油化工大学计算机通信与工程学院,抚顺113001)摘要目前,很多三维Voronoi图生成算法都是先构造Delaunay三角剖分,然后根据剖分后的数据结构来提取出Voronoi信息。在这个过程中,一种简单易处理的数据结构可以提高算法的效率,而在提取Voronoi多的拓扑信息,以便

2、快速简便地提取Voronoi信息。描述了一种数据结构,使Delaunay三角剖分算法的实现更加直观,Voronoi信息的提取过程。关键词Delaunay三角剖Voronoi图中图法分类号TP311.12;ADelaunay(以下简称DT)和Voronoi图(以下简称VD)是两种互相依存的空间结构,具有广泛的应用背景。目前,很多三维Voronoi图生成算法都是先构造Delaunay三角剖分,然后根据剖分后的数据结构来提取出Voronoi信息。在这个过程中,数据结构简单易处理是问题的关键。描述三维空间和空间内的物体,主要有以下两种类型:(1)空间内摆放着很多的物体,而这些物体是独立的位于空间的某个

3、位置,也就是说这些物体之间没有任何联系,每个物体是被单独描述的。例如基于向量的GIS,当对城市建模时,每个建筑物都是被独立描述的,只是它被放在指定的位置上。(2)给定的空间S被划分成多个连续的子空间,在明显,Delaunay三角剖分便是如上述的第(2)种情况。一个连续的空间可以按照以下两种方式来划分:(1)空间被规则地划分成子空间,每个子空间都用相同的三维几何体表示,这样的数据结构有vox2el,octree1。(2)空间被不规则地划分,子空间或2者用简单体表示,或者用任意的多面体来表示,这样的数据结构有fecet2edgeedge5,G2map3,4,half2。在进行Delaunay三角剖

4、分时,被剖分的空间是连续的,而且划分成的子空间也是不规则的,但都属于四面体。所设计的数据结构必须能全面地表示出每个子空间及子空间之间的相邻关系,另外,这种数据结构还要适用于Delaunay剖分算法,能使算法简明高效,以及从这种数据结构能容易地提取出Voronoi信息。本文描述了一种空间数据结构能全面地描述连续空间的子划分,适用于增量式Delaunay三角剖分算法,具有局部修改性,而且能提供足够多的拓扑信息,便于提取Voronoi信息,在此称它为“三角剖分数据结构”。描述空间S的时候,子空间之间的相邻关系是必须被考虑的。也就是说在描述这样的空间时,不仅要表示出每个子空间,还要描述它们之间的关系。

5、很2010年1月26日收到第一作者简介:温来祥(1985),男,山东潍坊人,硕士研究生,研究方向:几何建模,算法设计与分析。E2mail:wenlaixiang1985。3通信作者简介:刘金义(1966-),男,辽宁法库县人,教授,博士,研究方向:几何建模,计算几何,算法设计与分析。E2mail:j_y_liu。12期温来祥,等:一种支持三维Delaunay三角剖分与Voronoi图生成的数据结构29751几何与拓扑关系的描述本文描述的三角剖分数据结构其实上就是cell和vertex的容器,并且存储了它们的几何拓扑信息和几何点所具有的属性信息。为了便于描述,做如下规定:在Delaunay空间划

6、分中,几何坐标点称为vertex,划分后的一个子空间称为一个cell,cell的边称为edge,cell的面称为facet,与cell相邻的cell称为neighbor。在Voronoi空间划分中几何元素的描述,只需在每个上述规定前加“voronoi_”加以限制,如voronoi_vertex,表示Voronoi空间划分中的几何坐标点。1.1表示法2对cell的facet与edge并不显式地给出的。(1)facet是通过该面所属的cell和一个标记i由于三维面体,所以每个4(vertex),并且通过该cell4个相邻的cell。每个vertex应当能直接访问它所附属的一个cell,这样当需要时

7、,可以遍历该vertex所附属的全部cell。为了表示更多的拓扑关系,需要对cell的4个附属点和其4个neighbor规定其标记顺序,对一个cell的4个附属点标记顺序为0,1,2,3,并规定此顺来规定的,faceti就是cell中与vertexi相对的那个面,即cell中除vertexi外,其它3个vertex所构成的面,它是一个二元组(cell,i)。(2)edge是通过该边所属的cell和两个标记i与j来规定的,其中i,j代表cell中的vertexi和vertexj,它是一个三元组(cell,i,j)。对于facet和edge的规定如图3所示。序为正向,正向的规定与欧几里德三维空间中

8、坐标系统的方向相一致,如图1。图3对cell中facet和edge的标记规定经过上述标记规定后,还需要对数据结构进行图1对cell中四个附属点标记顺序的正向规定有效性规定,即各个cell是如何组合在一起构成的DT才算是有效。我们说已经构造好的三角剖分数对cell的4个vertex标记为0,1,2,3后,cell的4个neighbor同样标记为0,1,2,3,规定为标记i的vertex向以i为顶点的cell底面看去,所对应的neighbor标记为i,也就是标记为i的vertex与标记据结构的组合是局部有效的,当且仅当满足以下两个条件:(1)若cellc1和cellc2是相邻的两个cell,则c1

9、为i的neighbor是相对的,如图2所示。中有一个neighbor指向c2,同样地,c2中也应当有一个neighbor指向c1,并且c1和c2有一共面,即两个2976科学技术与工程10卷cell中有3个vertex是相同的。(2)这些cell的方向应当是一致的。对于两个相邻cell的方向一致性描述如下:如果相邻两cellc1与c2的共享面含有3个vertex为u,v,w,则这3个点在c1和c2中的存储顺序分别为:c1中4点的标记顺序为v1=u,v1=v,v1=w,v3,c2中4点的标记顺序应为v2=v,v2=u,v2=w,v2或者为v2=u,v2=w,v2=v,v3。但必须要保证的是,当分别

10、1221212从c1的第4点v1和c2的第4点v2向共享面看去时,u,v,w这3点的顺序应当是相反的,如图4所示。33图5二维情况下初始化一个无穷大的三角形,在进行三角剖分之前先对数据结构初始化一个很大的四面体,可以给构造DT(S)带来很多的便利,因此本文描述的三角剖分数据结构也采用这种方法。2数据结构设计为了最大可能的满足各种应用的需求,应当允许按需求灵活地改变数据结构的某部分或是替换某部分,而且能充分地利用已提供的功能。本文设图4三角剖分数据结构的局部有效性计的数据结构能够允许用户定义自己Vertex和Cell(可以加上自己的信息),以及自由指定几何点的数1.2无穷大的四面体对于点集S,在

11、构造DT(S)的时候,经常对数据结构初始化一个大的四面体,使这个四面体能包含点集S,并且该四面体相对点集S的凸包conv(S)是无穷大的。图5给出了在二维情况下的例子。这样做是有很多的优点,而且在很多算法68据类型(float,double等)。2.1总体结构设计为了保证灵活性,采用适用于表示多面体的三层结构模型10来设计三角剖分数据结构,应用此模中都有用型带来许多的灵活性,如定义自己的Vertex和Cell,如图6所示的三层结构图。最底层是构成三角剖分数据结构的基本元素类,这些类包含必需的几何信息和应用程序可能需要的其他信息,有CellBase和VertexBase,及其子类GeoCellB

12、ase和GeoVertexBase,前两个类中只含有组到。首先,当一个点v要插入到DT(S)中时,使得点v必定处在某个四面体的内部,这样就不需要专门处理点v落在conv(S)外部的情况9。其次,如果需要对已经生成好的DT(S)进行删除点的操作,而且当要删除的点恰好在conv(S)的表面上时,这种情况也是不必专门做处理的。当然这样做也是有缺点的,最主要的就是生成的四面体数要比实际的多,如图5所示的二维情况下,只有实线表示的三角形属于DT(S),其他的三合结构信息,后两个类中增添了几何信息(坐标点)。当需要定义自己的Cell或Vertex来添加额外的信息,从GeoCellBase或GeoVerte

13、xBase派生即可,通过GeoVertexBase可以指定几何点的数据类型12期温来祥,等:一种支持三维Delaunay三角剖分与Voronoi图生成的数据结构2977图6三层结构模型图(float,double等),如果需要也可从CellBase和Ver2texBase派生,但需要保证原有几何信息的完整。locator的实现方法来解决:cell和vertex的基类用一个dummyTDS来初始化。所谓的dummyTDS是对vertex和cell中所用到类型只做一个声明,详见下面中间层是一种单纯的组合结构,不包含有任何的几何信息,对外提供的只是修改组合结构的一系列操作,如从给定的Cell中插入或

14、删除一个Vertex,以及保持DT组合结构的完整性。该层中可以指定应用哪种类型的Cell和Vertex,例如自定义的Cell与Vertex。顶层定义的是构成DT所必要的操作,保证几何拓扑信息满足DT的定义,本文的三角数据结构只涉及低层和中间层,对顶层的结构不加赘述,可参见文献10给出的代码。在TDS中,这些基类被重新绑定为真实的TDS类型,从而获得真正所需要的vertex和cell基类,重新绑定是通过在基类中加一个嵌套模板类来实现的。DummyTDS类的定义代码:structDummy_tdsstructVertex;structCell;structVertex_handle;structC

15、ell_handle;.;VertexBase类的定义代码:template<typenameTDS=Dummy_tds>classVertexBasepublic:typedeftypenameTDS:Cell_handleCell_handle;typedeftypenameTDS:Vertex_handleVertex_handle;template<typenameTDS1>structRebind_TDStypedefVertexBase<TDS1>Other;。2.2循环依赖相邻关系是保存在Vertex和Cell中的,也就是说vertex和cel

16、l的基类要保存TDS(triangulationda2tastructure)中指向它们neighbor的指针(也叫han2dle),而vertex和cell应当能识别出TDS中定义的指针类型,对于这种关系可以简单的描述为,基类需要TDS来初始化,而TDS需要vertex和cell的基类来初始化,这样就出现了一个难题:循环依赖。对于这一难题可以参考标准类库中的std:al2.;2978TDS类的定义代码:科学技术与工程10卷template<typenameVb=VertexBase<>,typenameCb=CellBase<>>classTriangul

17、ation_DStypedefTriangulation_DS<Vb,Cb>Tds;public:typedeftypenameVb:templateRebind_TDS<Tds>:OtherVertex;typedeftypenameCb:templateRebind_TDS<Tds>:OtherCell;typedef.Vertex_handle;typedef.Cell_handle;3Voronoi信息提取VD与DT图DT与VD对偶性质分,而且两者存在对偶关系,3.1DT与VDcell的共享的facet。voronoi_facet:一个voronoi

18、_facet对偶于DT空间的一条edge,这个voronoi_facet是由附属于edge的所有cell的外接球球心(voronoi_vertex)构成的,也就是说以这条edge为轴旋转,便可找到这些voronoi_vertex,这样可以保证这些点是共面的,并且在三维空间内,VD与DT之间的对偶性是比较简单的,可以描述为一个空间内的结构元素(点,线,面,体)都与其对偶空间内的唯一结构元素相对应:体对应点,线对应面,或反之。如图7所示,DT中的一个vertexp对应于VD中的一个voronoi_cell(图7(a),DT中的一条edge对应于VD中的一这同这些点构成的voronoi_facet是

19、凸的。voronoi_cell:一个voronoi_cell是一个多面体,对偶于DT空间的一个vertex,这个多面体是由DT空间中所有含有此vertex的cell的外接球球心(voronoi_vertex)构成。可以通过计算这些voronoi_vertex的凸包来求出voronoi_cell,但更简单的方法个voronoi_facet(图7(b),相对应的,DT中的一个facet对应于VD中的一条voronoi_edge(图7(c),DT中的一个cell对应于VD中的一个voronoi_vertex(图7(d)。VD中的一个voronoi_vertex是DT中的一个cell的外接球球心,如果

20、DT是,识别出所有含有vertex的edge,然后以每条edge为轴旋转,求出voronoi_cell的各个voronoi_facet来,从而得到voronoi_cell。的两个vertex相邻,则与该两个vertex对应的voronoi_cell也是相邻的。3.2提取过程描述4结论本文所描述的三角剖分数据结构中做了许的规定,也正是有了这些规定使得该数据结构隐含了大量的拓扑信息,从而对基本几何元素的操作更加简单。通过对该数据结构定义所需的操作,可以使本来由算法承担的操作转移到该数据结构自身上来,使算法更加简洁,例如向指定的cell中插入新点的操作,另一方面,为了便于通过DT与VD的对偶性来提取

21、VD,同样可以定义所需的操作,来简化对VD信息从DT提取VD的时候,主要是用VD与DT的对偶性质,将大体思路描述如下:voronoi_vertex:一个voronoi_vertex就是其对偶空间DT中的四面体的外接球球心,对应于DT空间中的一个cell(四面体)。voronoi_edge:一条voronoi_edge就是两个相邻voronoi_vertex的连线,即其对偶空间DT中两个相邻cell的外接球球心之间的连线,对应于对偶空间12期温来祥,等:一种支持三维Delaunay三角剖分与Voronoi图生成的数据结构2979的提取过程,例如,给定一条边edge,遍历所有以edge为边的cel

22、l,也就是说edge为轴旋转360度。该三角剖分数据结构已经C+程序语言实现,并在linux上通过测试实例证明是有效的,图8给出了40个散乱点所生的DT和VD。2DobkinDP,LaszloMJ.Primitivesforthemanipulationofthree2di2mensionalsubdivisions.Algorithmica,1989;4(1):3323BertrandY,DufourdJ,FranconJ,etal.Algebraicspecificationanddevelopmentingeometricmodeling.volume668ofLNCS,1993:758

23、94LienhardtP.N2dimensionalgeneralizedcombinatorialmapsandcel2lularquasi2manifolds.InternationalJurnalofComputationalGeome2tryandApplications,1994;4(3):2753245LopesH,TavaresG.Structuraloperatorsformodeling32manifolds.In:Proceedings4thACMSymposiumonSolidModelingandAppli2cations,1997:10186BoissonnatJD,

24、DevillersO,P,etal.TriangulationsinIn:ProceedingsTAPSOFT93,CGAL.andApplications,2002:EP.riplementationforthree2dimensionalDelau2ons.InternationalJournalofComputationalGeometryandApplications,1998;8(2):2552768LiuY,SnoeyinkJ.TESS3:aprogramtocompute3DDelaunaytes2sellationsforwell2distributedpoints.In:Pr

25、oceedings2ndInterna2tionalSymposiumonVoronoiDiagramsinScienceandEngineering,图8测试实例参考文献1SametH.Thedesignandanalysisofspatialdatastructures.Massa2chusetts,USA;Addison2WesleyPublishingCompany,1990Seoul,Korea,2005:2252349JoeB.Constructionofthree2dimensionalDelaunaytriangulationsu2singlocaltransformations.1991:12314210KettnerL.Designingadatastructureforpolyhedralsurfaces.Proc14thAnnuACMSymposComputGeom,1998;146154In:ComputerAidedGeometricDesign,ADataStructureforDelaunayTriangulationandComputingVoronoiDiagraminThree2dimensionsWENLai2xiang,LIUJin2yi3(S