一种快速相容三角剖分算法.pdf

《一种快速相容三角剖分算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1期刘海涛等：一种快速相容三角剖分算法·235·一种快速相容三角剖分算法刘海涛，张三元，叶修梓（浙江大学计算机科学与技术学院，CADSCG国家重点实验室，浙江杭州310027）摘要：提出了一种基于凹多边形凸分解的相容三角剖分方法。先将凹边形分解成凸多边形，再对子多边形进行三角剖分，即可实现相容三角剖分。在最坏的情况下添加0（jk）个辅助点，时间复杂度为0（jn+niogn+jkiogn）关键词：相容三角剖分；多边形分解；计算几何中图法分类号：TP391文献标识码：A文章编号：1001-3695（2007）01-0235-03FastCompatibieTrianguiations

2、AigorithmLIUHai-tao，ZHANGSan-yuan，YEXiu-zi（StateKeyLaboratoryofCAD&CG，CollegeofCompUterScience&Technology，ZhejiangUni1ersity，HangzhoUZhejiang310027，China）Abstract：Anewcompatibietrianguiationsaigorithmisproposed.Firstdecomposeconcavepoiygontoconvexpoiygons，thencompatibietrianguiateconvexpoiygon

3、stotrianguiations，itwiiiimpiementcompatibietrianguiations.Inworstcase，itwiiiadd0（jk）steinerpointsanditstimecompiexityis0（jn+niogn+jkiogn）.Keywords：CompatibieTrianguiations；DecomposeConcavePoiygon；ComputationaiGeometry设具有n个顶点的多边形P和O分别有j和k个凹点，且新的算法，该算法能添加较少的辅助点而实现相容三角剖分，3jSk。顶点分别为11，⋯，1n和U1，⋯，Un

4、，且1i与Ui一一对应。但是需要耗费大量的时间0（niogn）。本文提出的算法虽然如果存在三角剖分，使得P和O上的所有点和弦都一一对应，也要少量的辅助点，但耗时将大大减少。则称之为多边形P和O上的相容三角剖分。相容三角剖分是［7］!算法的提出变形（Morphing）中重要的一步。变形作为近几年的研究热［6］［17］［18］［6］点，在计算机图形学、动画、建模和影视制作等方面!.!凸多边形和凹多边形都有应用。凸多边形就是所有内角均小于180的多边形，凹多边形通常情况下P与O之间并不总是存在相容三角剖分，为则是内角至少有一个大于180。图1（a）是凸多边形，图1（b）了解决这个问题，需

5、要在多边形内添加辅助点（SteinerPoints）是凹多边形。来实现。然而太多的辅助点会影响实际应用中的效率，所以如结论1凹多边形不添加辅助点的任意三角剖分T，都能何使用一种有效的方法添加较少的辅助点而实现相容三角剖在顶点数相同的凸多边形上实现，反之则不成立。分成为一个重要问题。此问题最早由Goodman和Poiiack在［1］证明：因为凸多边形的弦都在多边形内，所以对于凹多边1989年提出，Aronov，Seidei和Souvaine给出了一种添加22形内的任意弦，凸多边形内都有相应的弦；反之凸多边形内的0（n）辅助点，在0（n）的时间实现相容三角剖分算法。该算某条弦，将可能在

6、相应的凹多边形外。故结论成立。其实现如法最早解决添加辅助点能否实现相容三角剖分的问题，但是添2［3］图2所示。加0（n）个辅助点并不适合实际应用。Gupta和Wenger给2出了一种算法，结果将添加0（Miogn+niogn）个三角形，其中M为最优情况下产生的三角形个数。在某些不需要添加辅助点的简单情况下，该算法也将添加大量的辅助点。算法中用到了大量的近二十年才在计算几何中提出的算法，无法在实际［4］应用中实现。Kranakis和Urrutia给出了两种不同的相容三角剖分方法，添加的辅助点数取决于多边形的凹点数：!添加20（（j+k））个辅助点（j，k分别为两个多边形的凹点数），同

7、样因为辅助点太多而不适用。"在最坏情况下添加0（jk）个辅如果两个多边形有一个为凸多边形，则可以非常方便地实助点，但是会在多变形的边界上添加辅助点，在应用中将受到现无须插入辅助点的相容三角剖分；如果两个多边形都是凹多限制。最近由Surazhsky和Gotsman在文献［9］中提出了一种边形，则只需要将其中一个分解为凸多边形，另外一个也作相同的剖分，再对子多边形进行三角剖分即可实现两个多边形的收稿日期：2005-10-25；修返日期：2005-12-16相容三角剖分。·