在标准Delaunay三角网中引入约束边

在标准Delaunay三角网嵌入约束边过程中，需要由三角网拓扑信息快速搜索到约束边所影响的三角形，并且在嵌入约束边的过程中，三角网的拓扑关系在动态变化。因此，保证三角网拓扑信息的正确性对于建立CDT至关重要。在三角网内查询的拓扑信息包括：

（1）对于一个三角形，获得其3个顶点，3条边以及3个邻接三角形的信息。

（2）对于一个点，定位以该点为顶点的所有三角形。

设CDT三角形集合T（V；L），需在CDT中嵌入约束边l，l＝pipj，pi，pj∈V，与约束边l相交的三角形所构成的区域称为约束边l的影响域。区域的边界所构成的多边形称为影响多边形Q。l将Q分成两部分Qu和Qd，如图4-6所示。为了说明嵌入约束边的算法，下面给出关于影响域性质的几个定理：

设T′＝（V，L′）为CDT T＝（V；L）嵌入约束边l后调整获得，L′＝L∪｛i｝。则只有约束边l影响域内的三角形需要调整。

约束边l＝pipj，Q为影响多边形，p为Q上的顶点且p≠pi∧p≠pj，则在l上必存在一点m使得pm完全在Q的内部。

约束边l＝pipj，p为Qu（或Qd）中与l构成最大角的一点（图4-7），则ppi和ppj位于Qu（或Qd）内部，并且△pipjp为DT，即△pipjp的外接圆内不包含Qu（或Qd）上的其他点。

图4-6　约束边l的影响域

图4-7　按角度最大原则生成DT

在CDT内嵌入一条约束边pipj的算法过程如下：

在三角网中找出以pi为顶点的三角形t1，且t1与pipj相交。由点结构信息可即时定位以pi为顶点的三角形t，再由三角形拓扑信息从t开始以pi为顶点逆时针方向寻找到三角形t1。如图4-8（a）所示。

从t1开始，由三角形拓扑信息依次找到影响域内三角形t2，t3，…，tk，存入影响域三角形数组中，同时生成Qu和Qd影响域边界数组，其边界点具有拓扑性。如图4-8（b）所示。

图4-8　在CDT内嵌入一条约束边

（a）定位和pipj边相交的首三角形；（b）寻找影响域三角形t1，t2，…，tk(www.xing528.com)

由pipj开始对Qu和Qd按角度最大原则在影响域内生成新三角形。新生成的三角形信息写入影响域三角形数组存储的三角形空间中。由于未插入新点，三角形个数不变，所以不用再开辟新空间。为了确定三角形生成的先后次序，使用了栈这种数据结构。

严格说来，影响域Q不一定是通常意义上的多边形，影响域边界可能包含重复的顶点。如图4-9（a）所示，ab边为约束边，ab将Q分为上半部分Qu和下半部分Qd，Qu＝｛acdcb｝，c为重复点，cd和dc边重合，对于这样的边界边，其两侧的三角形都需要重建，不像一般意义下的边界，如cb边，只是边界内侧的三角形需要重建。这种情况并不影响算法的整个过程，只是在建立三角形拓扑关系时需作一下特殊处理。为了在任何情况下重建影响域内的三角网同时保证其拓扑信息的正确性，使用平衡二叉树这种数据结构存储每条影响域边界边外侧的三角形号和对应于内侧三角形的邻接号，同时用num记录影响域边界边入平衡二叉树的次数。在平衡二叉树中寻找任何一个节点的时间复杂度为O（lgN），N为平衡二叉树中节点的个数。为了说明如何在重建三角网的同时正确建立拓扑信息，以图4-9为例说明整个处理过程。

图4-9　在CDT内嵌入一条约束边

（a）包含重复点的约束边影响域边界；（b）重构约束边影响域内的三角形

在寻找ab边影响域内三角形和影响域边界Qu和Qd过程中，同时找出边界边的外侧三角形号及外侧三角形对应与内侧邻接三角形的邻接号入平衡二叉树。如边界边cb的外侧三角形号为7，与邻接三角形5的邻接号为2。对于重复边界cd会入两次平衡二叉树，在平衡二叉树节点中记录边界边所入次数，以便在建立拓扑信息时作特殊处理。寻找ab边影响域结束后，影响域三角形数组内依次存有三角形号1，2，3，4，5。影响域上边界数组内依次存有点号a，c，d，c，b，其数组下标号为0，1，2，3，4。影响域下边界数组内依次存有点号a，k，e，b。同时建立了边界信息平衡二叉树。对Qu和Qd区域按角度最大原则分别进行三角形的重构，为了便于三角形拓扑信息的建立，重构三角形时约定：

（1）三角形3个顶点存储按逆时针顺序。

（2）按角度最大原则找到的扩展点号存储在V［2］中。

在对Qu区域进行三角形重构时，先将ab和三角形号1入栈，弹出ab边，按角度最大原则在Qu边界数组｛acdcb｝中找到扩展点d，用三角形1存储△abd，新生成边ad和db。由于a的数组下标号为0，d的数组下标号为2，2-0＞1，则ad边为非边界边，将ad和三角形号2入栈，将三角形2的A［2］＝1，将三角形1的A［1］＝2。同理，对于db边，b的下标号为4，4-2＝2＞1，则db边为非边界边，将db和三角形号3入栈，将三角形3的A［2］＝1，将三角形1的A［0］＝3。由先入后出原则，先弹出db边，在｛c｝中找到扩展点c，用三角形3存储△dbc，下标号3-2＝1，则dc边为边界边，在平衡二叉树中找到dc边节点，该节点num＝2，表明dc边为重复边界，修改dc边节点，使该节点三角形号为3，邻接号为1，同时使该节点num＝1。b和c点下标号4-3＝1，则cb边为边界边，在平衡二叉树中找到cb边节点，该节点num＝1，则取出该节点的三角形号7和邻接号2，将三角形7的A［2］＝3，将三角形3的A［0］＝7。依次出栈，直至栈空。同法对Qd区域进行三角形重构。嵌入约束边ab后的三角网如图4-9（b）所示。