Delaunay三角网格化算法及实现

在实践的基础上，探讨了Ｄｅｌａｕｎａｙ三角网格化算法的实现技巧，提出了改进措施．是后就平面单连通城的Ｄｅｌａｕｎａｙ三角网格化算法及在空间中的应用做了深入的讨论。

An Improved Delaunay Triangulation Algorithm for Multiply-Connected Domain

We know that famous software companies like CV,EDS,PTC can deal efficiently with triangulation of multiply-connected domains,but no paper has been found in the open literature. Chinese engineers have been busy about finding an algorithm better than those theynow use. To our best knowledge, we are the first to present such an algorithm in P. R. China.Our aigorithm improves on Delaunay algorithm, so named in honor of Delaunay's 1934theorem. Previously, in the Case of multiply- connected domains, the fOllowing troublesomematters were encountered: iterated intersection- test, topological readjustment, and boundary trimming. We bypass these troubles in the following way: the polygons of a domain arerecorded with a constraint edge list' In this way, we can avoid forming triangles in invalidreStons. Our triangulation algorithm fully satisfies MCC (Modified CircumCircle ) criterion,which was proposed by past researchers working on Delaunay algorithm.Triangulation results obtained with our improved Delaunay algorithm are presented inFigs. 3 through 6.