三角剖分算法的研究论文

《三角剖分算法的研究论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、哈尔滨理工大学理学硕士学位论文三角剖分算法研究摘要三角剖分是计算机辅助几何设计、几何造型及计算机图形学中研究的重要内容之一。对于设计一个三角剖分算法来说，最重要的就是其复杂度低和高质量网格的形成。三角剖分算法在计算几何、曲面重构及有限元网格生成中有着重大的应用价值。本文研究内容如下：1．首先介绍了离散点和多边形三角剖分的～些基本理论，以及Voronoi图和Delaunay三角剖分的定义，包括Delaunay三角剖分的优化准则、Delaunay三角／四面体剖分的相关定义。2．研究了多边形的三角剖分。首先介绍了凸多边

2、形的相关定义和凸划分算法。凸划分中特殊的情况就是生成的凸多边形为三角形。算法思想是先采用切割耳的方法删去歧点(同时又是凸点)，使剖分的时候的两条链都是单调链，然后剖分这个单调多边形。但是这样生成的三角形中狭长的三角形比较多。所以在产生三角形的同时，使用Delaunay三角剖分的优化准则，以便生成质量更好的三角形。3．本文重点在第四章，首先介绍了平面点集三角剖分的定义，接着对主要的平面点集三角剖分算法进行了介绍，并且采用了对比方式进行分析描述。在Delaunay三角剖分优化准则的基础下，提出了一种新的平面点集三角剖

3、分算法。该算法的基本思想就是生成一个满足的条件的三角形，以每条边为基础向周围寻找可以满足条件的点，生成新的三角形，再以新的三角形为基础向周围生长，直至覆盖平面中的所有点。该算法的时间复杂度为O(nlogn)，很好地避免了病态三角形的出现，提高了网格质量，特别适用于有限元网格生成。4．在二维三角剖分的基础上，推广到三维空间。首先介绍了凸壳的一些基本概念和平面点集凸壳的一些重要算法。接着给出了两个三维空间点集剖分算法。一种算法是：先求得点集的凸壳，然后在凸壳区域内根据点的坐标，利用四阶行列式的值来选择一个符合条件的点

4、进行点集剖分。从而提高了算法的效率。该算法的时间复杂度为O(nlogH)。另外一种是空间点集三角剖分算法，算法的思想是：首先生成一个凸壳，接着在剩下的点再形成一哈尔滨理工大学理学硕士学位论文个凸壳，依次类推。所有的点都划成凸壳，接着关键就是凸壳之间的连接。这样可以保证生成更好的三角形，从而保证剖分质量。关键词平面点集：Delaunay三角剖分；凸多边形；凸划分；有限元网格：筌鎏垩三奎兰垩耋罂圭兰竺丝兰ResearchonTriangulationAlgorithmAbstractTriangulationison

5、eoftheimportantresearchcontentsincomputeraidedgeometrydesign，geometrymodellingandcomputergraphics．Forthetriangulationalgorithmdesign，themostimportantiStomakethealgorithmhavelowtimecomplexityandtocreatenetlatticewithhigllquality．Triangulationalgorithmhassignif

6、icantapplicationsincomputationalgeometry,curvedsurfaceconstructionandfiniteelement鲥dgeneration．Researchcontentsofthispaperisasfollows：First，somefundamentaltheoriesofdiscretepointandpolygontriangulationareintroduced，andrelateddefinitionssuchasVoronoigraphandDe

7、launaytriangulationaredescribed，includingtheoptimizationrule．Secondly,thepolygontriangulationhasbeenstudied．Ithasintroducedthedefinitionsrelatedtoconvexpolygonandtheconvexpartitionalgorithmfirst．Inconvexpartition，thepeculiarcaseisthatthegeneratedconvexpolygon

8、isatriangle．Themainideaofthealgorithmistodeletethebranchpointfirst(meanwhileitisaconvexpoint)bycuttingtheearstomakethetwochainusedtothePartitionbemonotonous，thentoPartitionthetweehains．Un