Delaunay refinement algorithms for triangular mesh generation.pdf

《Delaunay refinement algorithms for triangular mesh generation.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、DelaunayRefinementAlgorithmsforTriangularMeshGenerationJonathanRichardShewchukjrs@cs.berkeley.eduMay21,2001DepartmentofElectricalEngineeringandComputerScienceUniversityofCaliforniaatBerkeleyBerkeley,CA94720SupportedinpartbytheNationalScienceFoundationunderAwardsACI-9875170,CMS-9980

2、063,CMS-9318163,andEIA-9802069,inpartbytheAdvancedResearchProjectsAgencyandRomeLaboratory,AirForceMaterielCommand,USAFunderagreementnumberF30602-96-1-0287,inpartbytheNaturalSciencesandEngineeringResearchCouncilofCanadaundera1967ScienceandEngineeringScholarship,andinpartbygiftsfrom

3、theOkawaFoundationandIntel.Theviewsandconclusionscontainedinthisdocumentarethoseoftheauthor.Theyarenotendorsedby,anddonotnecessarilyreflectthepositionorpoliciesof,theU.S.Governmentorothersponsors.AbstractDelaunayrefinementisatechniqueforgeneratingunstructuredmeshesoftrianglesforusei

4、ninterpolation,thefiniteelementmethod,andthefinitevolumemethod.Intheoryandpractice,meshesproducedbyDelaunayrefinementsatisfyguaranteedboundsonangles,edgelengths,thenumberoftriangles,andthegradingoftrianglesfromsmalltolargesizes.ThisarticlepresentsanintuitiveframeworkforanalyzingDelau

5、nayrefinementalgorithmsthatunifiesthepioneeringmeshgenerationalgorithmsofL.PaulChewandJimRuppert,improvesthealgorithmsinseveralminorways,andmostimportantly,helpstosolvethedifficultproblemofmeshingnonmanifolddomainswithsmallangles.Althoughsmallanglesinherentintheinputgeometrycannotber

6、emoved,onewouldliketotriangulateadomainwithoutcreatinganynewsmallangles.Unfortunately,thisproblemisnotalwayssoluble.Acompromiseisnecessary.ADelaunayrefinementalgorithmispresentedthatcancreateameshinwhich
orgreaterandnoangleissmallerthan"!#mostanglesare

7、  ,where

%$'&isthesmallestangleseparatingtwosegmentsoftheinputdomain.Newanglessmallerthanappearonlynearinputanglessmallerthan
(&.Inpractice,thealgorithm'sperformanceisbetterthantheseboundssuggest.AnothernewresultisthatRuppert'sanalysistechniquecanbeusedtor

8、eanalyzeoneofChew'salgorithms.Che