3 An Efficient Implementation of Fortune’s Plane-S

Abstract1IntroductionKennyWongHausiA.M¨ullerVoronoiedgesVoronoiverticesDepartmentofComputerScienceUniversityofVictoria,Victoria,BC,V8W3P6,CanadaAnEfficientImplementationofFortune’sPlane-SweepAlgorithmforVoronoiDiagramsThisworkwassupportedinpartbytheNaturalSciencesandEngineeringResearchCouncilofCanadaandtheBritishColumbiaAdvancedSystemsInstitute.TheVoronoidiagramisafundamentalgeometricobjectforencodingproximityinformation.AnefficientCimplementationofFortune’splane-sweepalgorithmforconstructingtheVoronoidiagramandtheDelaunaytriangulationofasetofpointsintheplaneispresented.Datastructurerepresentationsandgeometricprimitivesaredescribed.TheimplementationcanproducetheVoronoidiagramof10000sitesinaboutfoursecondsonaSPARCstationIPC.Functionstocomputenearestneighbors,theclosestpair,andtheconvexhullareincludedinthedistributionpackage.TheVoronoidiagramisanimportantgeometricobjectwhichhasmanypracticalusesindiversefields.Figure1depictstheplanarVoronoidiagramofasetofpointsites.Theregionaroundeachsitecontainsallthosepointsforwhichthatsiteisthenearestamongallsites.Theedges,called,containpointswhichareequidistantbetweentwoneighboringsites.Theedgesintersectatpointscalled,whichareequidistanttothreeormoreneighboringsites.Thediagramencodesproximityinformationandisusefulinstudyingaphysicalsystemwhosepropertiesdependonthespatiallayoutofitsentities.Moreover,itcanbeusedinsolvingvariousgeometricproblems,includingfindingthenearestneighborforeachsite,computingtheclosestpairofsites,andproducingtheconvexhull[8].CloselyrelatedisadualdiagramcalledtheDelaunaytriangulation,whichhasapplicationsinsurveying,contouring,andfastgeometrictravellingsalespersonproblems[9].ONNN(log)READMEsweeplineplane-sweepeventqueuesweeptableTherearemanyalgorithmsforconstructingtheVoronoidiagram[2].However,Fortune’salgorithm[4]hasthecombinedadvantagesofbeingoptimallikedivide-and-conqueralgorithms(i.e.,forsites)andbeingrelativelysimplelikeincrementalalgorithmsbyavoidingadifficultmergestep.Itconceptuallysweepsastraightlineoracrossthesetofsites,constructingtheVoronoidiagrambehindthismovingfront.Thistechniqueisgenericallycalledandappearsinothergeometricalgorithms[5,6,11].Therearetwofundamentalplane-sweepdatastructures:theandthe.Generalformsofthesedatastructuresareknownaspriorityqueuesandordereddictionaries.Theeventqueuecontainsasequenceoflexicographi-callyorderedpointsoreventswhichdefinewherethesweepmustmomentarilystop.Thisqueueisupdatedasthesweepproceeds.Thesweeptablemaintainsacross-sectionofhowthesweeplineintersectstheregionsandedgesoftheVoronoidiagram.Thistableisupdatedateachevent.Efficientrepresentationsforthesedatastructuresaredescribed.Fortune’salgorithminvolvesageometrictransformandcomputesatransformeddiagram.TheprimaldiagramandtheDelaunaytriangulationcanbecomputedsimultaneously[4,12].Efficientgeometricprimitivesforimplementingtherequirednumericalcalculationsinfloating-pointarithmeticarepresented.Ourimplementation,whichwecallTess,iswrittencompletelyinCandhasbeentestedonSun3,Sun4(SPARC),RS/6000,NeXT,andSGI4DarchitectureswiththesuppliedCcompilers.(TheheaderfilesarealsocompatiblewithC++.)ThisimplementationcanproducetheVoronoidiagramof10000sitesinaboutfoursecondsonaSPARCstationIPCusingdouble-precisionfloating-pointarithmetic.Thesourcecodeistoolongtobelistedhere;refertothedistributionfiles.Seethefileforinstallationinstructionsandusageinformation.WedevelopedTessbeforediscoveringFortune’sownimplementationintheNETLIBarchives.Naturally,bothimplementationssharesomecommondesignideas.Forexample,theybothpresortthesetofsitesandseparatesitesfromverticesintheeventqueue.Nevertheless,therearesomemajordifferences.First,Fortune’seventqueueandsweeptablearerepresentedbylinkedlistswithanintricatebucketingschemetoallowrelativelyefficientsearches.Theperformanceofthisschemeissensitivetothebucketsize.Tessusesanimplicitheapandathreadedbinarytreewithrandomization.TheefficiencyofthesedatastructuresiscomparabletoFortune’sschemeandarguablysimpler.Second,Tessprovidesacompact,doubly-connectededgelistrepresentation[8]forholdingthecomputedVoronoidiagram.UnlikeFortune’sapproach,thisrepresentationcapturesalltheincidencerelation-shipsamongtheVoronoiedgesandvertices.Finally,Fortune’simplementationwasnotdesignedtobealibraryroutine;itisastand-aloneprogram.Assuch,itdoesnotcleanupandfreememoryafterprocessing.Tessisalibraryroutine.Wesupplydriversthatdemonstrateitsuse.Section2ofthispaperpresentssomegenerallyaccepteddefinitionsandsomeneedednewterminology.Section3brieflyoutlinesFortune’salgorithm.Theimplementationdetailsaredividedbetweenthenexttwosections.Sections4and52TS26222222222=222Preliminaries=()()()=()()()1=()==()=()=()()22222f2jg2f2jg2f2j926gxyyyyyxxppqqppqpqqppqqppqpqppqS;qppqpppSppqpqqrrppqqppqpqbisectorVoronoiregionneighboringVoronoidiagramVoronoivertexcandidatevertexcandidatecircleVoronoicircleVoronoiedgepppxypqpqpqpqpqSNpSzdzzpdzzBBpqSzdzdzHpHqHpqHpqSHzdzdzpSRpNSRHRpRVRzp;qS;pq;dzdzdzVVVVVpqrBBBpqrVpqeeepqSRRONNdescribethedatastructuresandthegeometricprimitives.Section6presentssomeperformancecha