Delaunay2D

DelaunayTriangulationsPresentedbyGlennEguchi6.838ComputationalGeometryOctober11,2001Motivation:Terrains•SetofdatapointsAR2•Heightƒ(p)definedateachpointpinA•HowcanwemostnaturallyapproximateheightofpointsnotinA?Option:Discretize•Letƒ(p)=heightofnearestpointforpointsnotinA•DoesnotlooknaturalBetterOption:Triangulation•DetermineatriangulationofAinR2,thenraisepointstodesiredheight•triangulation:planarsubdivisionwhoseboundedfacesaretriangleswithverticesfromATriangulation:FormalDefinition•maximalplanarsubdivision:asubdivisionSsuchthatnoedgeconnectingtwoverticescanbeaddedtoSwithoutdestroyingitsplanarity•triangulationofsetofpointsP:amaximalplanarsubdivisionwhoseverticesareelementsofPTriangulationismadeoftriangles•Outerpolygonmustbeconvexhull•Internalfacesmustbetriangles,otherwisetheycouldbetriangulatedfurtherTriangulationDetailsForPconsistingofnpoints,alltriangulationscontain2n-2-ktriangles,3n-3-kedges•n=numberofpointsinP•k=numberofpointsonconvexhullofPTerrainProblem,Revisited•Sometriangulationsare“better”thanothers•Avoidskinnytriangles,i.e.maximizeminimumangleoftriangulationAngleOptimalTriangulations•CreateanglevectorofthesortedanglesoftriangulationT,(1,2,3,…3m)=A(T)with1beingthesmallestangle•A(T)islargerthanA(T’)iffthereexistsanisuchthatj=’jforalljiandi’i•Besttriangulationistriangulationthatisangleoptimal,i.e.hasthelargestanglevector.Maximizesminimumangle.AngleOptimalTriangulationsConsidertwoadjacenttrianglesofT:•Ifthetwotrianglesformaconvexquadrilateral,wecouldhaveanalternativetriangulationbyperforminganedgeflipontheirsharededge.•Edgeeisillegalif:•OnlydifferencebetweenTcontainingeandT’witheflippedarethesixanglesofthequadrilateral.IllegalEdgesIllegalTriangulations•IftriangulationTcontainsanillegaledgee,wecanmakeA(T)largerbyflippinge.•Inthiscase,Tisanillegaltriangulation.Thale’sTheorem•WecanuseThale’sTheoremtotestifanedgeislegalwithoutcalculatinganglesLetCbeacircle,lalineintersectingCinpointsaandbandp,q,r,andspointslyingonthesamesideofl.SupposethatpandqlieonC,thatrliesinsideC,andthatsliesoutsideC.Then:TestingforIllegalEdges•TheedgepipjisillegaliffplliesinsideC.•Ifpi,pj,pk,plformaconvexquadrilateralanddonotlieonacommoncircle,exactlyoneofpipjandpkplisanillegaledge.ComputingLegalTriangulations1.ComputeatriangulationofinputpointsP.2.Flipillegaledgesofthistriangulationuntilalledgesarelegal.•Algorithmterminatesbecausethereisafinitenumberoftriangulations.•Tooslowtobeinteresting…Sidetrack:DelaunayGraphs•Beforewecanunderstandaninterestingsolutiontotheterrainproblem,weneedtounderstandDelaunayGraphs.•DelaunayGraphofasetofpointsPisthedualgraphoftheVoronoidiagramofPDelaunayGraphsToobtainDG(P):•CalculateVor(P)•PlaceonevertexineachsiteoftheVor(P)ConstructingDelaunayGraphsIftwositessiandsjshareanedge(siandsjareadjacent),createanarcbetweenviandvj,theverticeslocatedinsitessiandsjConstructingDelaunayGraphsFinally,straightenthearcsintolinesegments.TheresultantgraphisDG(P).PropertiesofDelaunayGraphsNotwoedgescross;DG(P)isaplanargraph.•ProvedusingTheorem7.4(ii).•LargestemptycirclepropertyDelaunayTriangulations•Somesetsofmorethan3pointsofDelaunaygraphmaylieonthesamecircle.•Thesepointsformemptyconvexpolygons,whichcanbetriangulated.•DelaunayTriangulationisatriangulationobtainedbyadding0ormoreedgestotheDelaunayGraph.PropertiesofDelaunayTrianglesFromthepropertiesofVoronoiDiagrams…•Threepointspi,pj,pkPareverticesofthesamefaceoftheDG(P)iffthecirclethroughpi,pj,pkcontainsnopointofPonitsinterior.PropertiesofDelaunayTrianglesFromthepropertiesofVoronoiDiagrams…•Twopointspi,pjPformanedgeofDG(P)iffthereisacloseddiscCthatcontainspiandpjonitsboundaryanddoesnotcontainanyotherpointofP.PropertiesofDelaunayTrianglesFromtheprevioustwoproperties…•AtriangulationTofPisaDT(P)iffthecircumcircleofanytriangleofTdoesnotcontainapointofPinitsinterior.LegalTriangulations,revisitedAtriangulationTofPislegaliffTisaDT(P).•DTLegal:EmptycirclepropertyandThale’sTheoremimpliesthatallDTarelegal•LegalDT:Provedonp.190fromthedefinitionsandviacontradiction.DTandAngleOptimalTheangleoptimaltriangulationisaDT.Why?•IfPisingeneralposition,DT(P)isuniqueandthus,isangleoptimal.WhatifmultipleDTexistforP?•NotallDTareangleoptimal.•ByThale’sTheorem,theminimumangleofeachoftheDTisthesame.•Thus,alltheDTareequally“good”fortheterrainproblem.AllDTmaximizetheminimumangle.TerrainProblem,revisitedTherefore,theproblemoffindingatriangulationthatmaximizestheminimumangleisreducedtotheproblemoffindingaDelaunayTriangulation.SohowdowefindtheDelaunayTriangulation?HowdowecomputeDT(P)?•WecouldcomputeVor(P)thendualizeintoDT(P).•Instead,wewillcomputeDT(P)usingarandomizedincrementalmethod.AlgorithmOverview1.InitializetriangulationTwitha“bigenough”helperboundingtrianglethatcontainsallpointsP.2.RandomlychooseapointprfromP.3.Findthetrianglethatprliesin.4.Subdivideintosmallertrianglesthathaveprasavertex.5.Flipedgesuntilalledgesarelegal.6.Repeatsteps2-5untilallpointshavebeenaddedtoT.Let’sskipsteps1,2,and3fornow…TriangleSubdivision:Case1of2Assumingwehavealreadyfoundthetrianglethatprlivesin,subdividein