《用c++实现Delaunay三角剖分》由会员分享，可在线阅读，更多相关《用c++实现Delaunay三角剖分（5页珍藏版）》请在金锄头文库上搜索。
1、Delaunay三角剖分void main(PointLink *ptUpOutline, PointLink *ptDownOutline) /首先分别对上下轮廓线的点集进行三角化，ptUpOutline, ptDownOutline 为对应点集TrianglizationInPlan(ptUpOutline) ; TrianglizationInPlan(ptDownOutline) ; /根据两层三角化的结果进行Delaunay剖分，得到四面体链表GetTetrahedron( UpTriangle , DownTriangle ) ; /后处理用于删除不正确的四面体PostProces
2、s() ; 其中：1函数 TrianglizationInPlan() 用于平面三角化void TrianglizationInPlan( PointLink * Head ) /对不符合 Delaunay剖分的边进行细分bool Over = 1; while( Over ) First = Head ; Second = First-next ; while( Second ) if( !NotIncludeOtherPoint( First-Point , Second-Point , Head ) ) PointLink* Point = new PointLink ; First-n
3、ext = Point ; Point-next = Second ; Over = false ; First = Second ; Second = Second-next ; /对平面进行三角化，保存结果到TriangleLink 的链表Trianglization( Head ) ; 2函数GetTetrahedron()进行 Delaunay剖分得到四面体链表void GetTetrahedron( TriangleLink * First, TriangleLink * Second ) Cur = First ; while( Cur ) Temp1 = Cur-Triangle
4、 ; Center = GetCenter( Temp1 ) ; Cur = ContourUp ; while( Cur ) /初始化 min if( Cur = ContourUp ) min = Center.distance( Cur-Point ) ; Value = min ; Result = Cur-Point ; /找距离最小的点else Value = Center.distance( Cur-Point ) ; if( min Value ) min = Value ; Result = Cur-Point ; Cur = Cur-next ; TetrahedronLi
5、nk *T1 = new TetrahedronLink ; T1-volume.Point0 = Cur-Triangle.Point0 ; T1-volume.Point1 = Cur-Triangle.Point1 ; T1-volume.Point2 = Cur-Triangle.Point2 ; T1-volume.Point3 = Result ; T1-type = 1 ; ResultCur-next = T1 ; T1-next = 0 ; ResultCur = T1 ; Cur = Cur-next ; Cur = Second ; while( Cur ) Temp1
6、= Cur-Triangle ; Center = GetCenter( Temp1 ) ; /逐个比较找到离圆心最近的点Cur = ContourDown ; while( Cur ) /初始化 min if( Cur = ContourDown ) min = Center.distance( Cur-Point ) ; Value = min ; Result = Cur-Point ; else /找距离最小的点 Value = Center.distance( Cur-Point ) ; if( min Value ) min = Value ; Result = Cur-Point
7、 ; Cur = Cur-next ; TetrahedronLink *T2 = new TetrahedronLink ; T2-volume.Point0 = Cur-Triangle.Point0 ; T2-volume.Point1 = Cur-Triangle.Point1 ; T2-volume.Point2 = Cur-Triangle.Point2 ; T2-volume.Point3 = Result ; T2-type = 2 ; ResultCur-next = T2 ; T2-next = 0 ; ResultCur = T2 ; Cur = Cur-next ; E
8、dgeCur1 = EdgeUp ; EdgeCur2 = EdgeDown ; Edge tempEdge1 , tempEdge2 ; while( EdgeCur1 ) tempEdge1 = EdgeCur1-line ; while( EdgeCur2 ) tempEdge2 = EdgeCur2-line ; /判断两条边投影是否相交if( EdgesIntersect( tempEdge1 , tempEdge2 ) ) TetrahedronLink *T12 = new TetrahedronLink ; T12-volume.Point0 = tempEdge1.Start
9、 ; T12-volume.Point1 = tempEdge1.End ; T12-volume.Point2 = tempEdge2.Start ; T12-volume.Point3 = tempEdge2.End ; T12-type = 12 ; ResultCur-next = T12 ; T12-next = 0 ; ResultCur = T12 ; EdgeCur2 = EdgeCur2-next ; EdgeCur1 = EdgeCur1-next ; 3函数 EdgesIntersect()两条边投影相交的判断bool EdgesIntersect(Edge edge1,
10、 Edge edge2) C3DPoint Vector , Vector1 , Vector2 ; C3DPoint Middle = edge1.End + edge1.Start ; Middle.x /= 2 ; Middle.y /= 2 ; Middle.z = edge2.Start.z ; Vector = edge1.End - edge1.Start ; Vector1 = edge2.Start - Middle ; Vector2 = edge2.End - Middle ; if( ( Vector*Vector1 = 0 Temp.Point1 = Cur-volu
11、me.Point1 ; Temp.Point2 = Cur-volume.Point2 ; /根据向量间的叉乘，判断是否在轮廓线外if( IsOutSide( ContourUp , Temp ) ) if( Cur = Head ) p = Head ; Head = Cur-next ; delete p ; else p = Cur ; Pre-next = Cur-next ; delete p ; break; case 2:Temp.Point0 = Cur-volume.Point0 ; Temp.Point1 = Cur-volume.Point1 ; Temp.Point2 = Cur-volume.Point2 ; if( IsOutSide( ContourDown , Temp ) ) if( Cur = Head ) p = Head ; Head = Cur-next ; delete p ; else p = Cur ; Pre-next = Cur-next ; delete p ; break; default: break; Pre = Cur ; Cur = Cur-next ;
