Delaunay Triangulations_Hight interpolation

《Delaunay Triangulations_Hight interpolation》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、9DelaunayTriangulationsHeightInterpolationWhenwetalkedaboutmapsofapieceoftheearth’ssurfaceinpreviouschapters,weimplicitlyassumedthereisnorelief.ThismaybereasonableforacountryliketheNetherlands,butitisabadassumptionforSwitzerland.Inthischapterwesetouttoremedythissituation.Wecanmodelapieceoftheearth’

2、ssurfaceasaterrain.Aterrainisa2-dimensionalsurfacein3-dimensionalspacewithaspecialproperty:everyverticallineintersectsitinapoint,ifitintersectsitatall.Inotherwords,itisthegraphofafunctionf:AR2!Rthatassignsaheightf(p)toeverypointpinthedomain,A,oftheterrain.(Theearthisround,soonaglobalscaleterrainsd

3、efinedinthismannerarenotagoodmodeloftheearth.Butonamorelocalscaleterrainsprovideafairlygoodmodel.)AterraincanbevisualizedwithaperspectivedrawingliketheoneinFigure9.1,orwithcontourlines—linesofequalheight—likeonatopographicmap.Figure9.1AperspectiveviewofaterrainOfcourse,wedon’tknowtheheightofeverypoi

4、ntonearth;weonlyknowitwherewe’vemeasuredit.Thismeansthatwhenwetalkaboutsometerrain,weonlyknowthevalueofthefunctionfatafinitesetPAofsamplepoints.Fromtheheightofthesamplepointswesomehowhavetoapproximatetheheightattheotherpointsinthedomain.Anaiveapproachassignstoeveryp2Atheheightofthenearestsamplepoin

5、t.However,thisgivesadiscreteterrain,which191Chapter9doesn’tlookverynatural.ThereforeourapproachforapproximatingaterrainDELAUNAYTRIANGULATIONSisasfollows.WefirstdetermineatriangulationofP:aplanarsubdivisionwhoseboundedfacesaretrianglesandwhoseverticesarethepointsofP.(Weassumethatthesamplepointsaresuc

6、hthatwecanmakethetrianglescoverthedomainoftheterrain.)Wethenlifteachsamplepointtoitscorrectheight,therebymappingeverytriangleinthetriangulationtoatrianglein3-space.Figure9.2illustratesthis.Whatwegetisapolyhedralterrain,thegraphofacontinuousfunctionthatispiecewiselinear.Wecanusethepolyhedralterraina

7、sanapproximationoftheoriginalterrain.Figure9.2ObtainingapolyhedralterrainfromasetofsamplepointsThequestionremains:howdowetriangulatethesetofsamplepoints?Ingeneral,thiscanbedoneinmanydifferentways.Butwhichtr