Continuous Generalization for Visualization on Small Mobile Devices

MonikaSesterandClausBrenner

InstituteofCartographyandGeoinformatics,UniversityofHannover,Appelstr.9a,30167Hannover,Germany

monika.sester@ikg.uni-hannover.de,claus.brenner@ikg.uni-hannover.de

1Introduction

Smallmobiledevicesarebecomingmoreandmoreimportantforthevisual-izationofspatialinformation.Thistendencyisontheonehanddrivenbytheavailabilityofsuchsmalldeviceswithdisplays(e.g.mobilephones,PDA’s),aswellasbyagrowingnumberofpopularapplications,namelyLocationBasedServices(LBS)ingeneralandnavigationinparticular.

However,thesesmalldevicesalsohavelimitations:firstofall,thecom-putingandstoragecapabilitiesarelimited,leadingtothesituationthathugedatasetsorcomplicatedcalculationscannotbeloadedorrunonthedevices,respectively.Furthermore,thedisplaysarequitesmallandofrelativelylowresolutionsothatthevisualizationisnotcomparabletoamappresentation.Inordertostillbeabletoemploythisnewtechnologyformobilenav-igation,thefollowingdemandscanbeformulated:firstly,spatialdatasetsindifferentresolutionsorlevelsofdetailhavetobemadeavailableforthemobileuserinordertoallowforaflexiblezoominginandoutforgettingbothdetailandoverviewinformation.Secondly,thisinformationhastobetransmittedtotheuserfromaservertakingthepossiblylimitedbandwidthofthecommunicationchannelintoaccount.

Inthepaperasolutionispresentedthatallowsforaprogressivetransmis-sionofspatialdatatoasmallmobiledevice,startingwithcoarseoverviewin-formationandprogressivelystreamingmoredetailedinformationtotheclient.Thisinformationwillbeinterpretedbytheclientandanimatedinawaytosimulateacontinuousgeneralizationfromcoarsetofineandviceversa.Aprototypehasbeendevelopedtoillustratethefunctionalityandevaluatetheresults.

Thepaperisstructuredasfollows:afterabriefreviewofrelatedwork,asetofelementarygeneralizationoperations(EGO’s)isdefined,whichallowsforthemodificationofspatialobjects.Basedonthiselementaryvocabulary,twogeneralizationapplicationsaredescribed:generalizationofbuildinggroundplansandtypificationofbuildings.Thelastsectiondescribestheclient-server

2MonikaSesterandClausBrenner

architecture,aswellasanextensiontograduallyanimatethechangesinordermakethediscretechangeslessvisible.Asummaryandoutlookconcludesthepaper.

2RelatedWork

Inordertoprovideadequateinformationtoauser,ithastobeadaptedtothepersonalsituation,thedeviceused,thetasktobesolved,etc.(seee.g.[Nivala,Sarjakoski,Jakobsson&Kaasinen2003,Reichenbacher2004]).Onemajorcomponentistheadaptiontothelevelofdetailoftheinfor-mation.Incartography,thederivationofinformationindifferentlevelsofdetailisbeingachievedusinggeneralizationoperations[Hake,Gru¨nreich&Meng2002],whichtraditionallyhavebeenappliedbyhumancartogra-phers.Over40yearsofresearchintheautomationofgeneralizationpro-cesseshaveleadtoaseriesofalgorithmsspecifiedfordedicatedpurposes,e.g.linegeneralization[Douglas&Peucker1973],areaaggregation,build-ingsimplification,typification[Regnauld1996,Sester2004]ordisplacement[Højholt1998,Harrie1999,Sester2000].Inrecentyears,theresearchhasfocusedontheintegrationofdifferentgeneralizationalgorithmsbymod-ellingtherelativedependenciesbetweentheoperationsandthespatialcon-textoftheobjects(seee.g.[Lamy,Ruas,Demazeau,Jackson,Mackaness&Weibel1999]).Inthecontextofmobileapplications,acombinationofrely-ingonpre-computedgeneralizationlevelsintermsofanMRDBandon-linegeneralizationusingweb-technologyhasbeenproposed(e.g.[Sarjakoski,Sar-jakoski,Lehto,Sester,Illert,Nissen,Rystedt&Ruotsalainen2002])

Progressivelytransmittingspatialinformationviaalimitedbandwidthhasbeenimplementedforimageformatse.g.intheGIF-Format.Bertolotto&Egenhofer[1999]proposedtoalsouseitforvectordata.vanKreveld[2001]presentedconceptsforthecontinuousvisualizationofspatialinformationinordertoreducethepoppingeffectwhendiscretechangesinthegeometryappear.Inordertorepresentdifferentlevelsofdetailofvectorgeometry,hierarchicalschemescanbeapplied.AnexampleistheGAP-treeforthecodingofareapartitioningindifferentlevelsofdetail([vanOosterom1995]).TheBLG(binarylinegeneralization)treehierarchicallydecomposesalineusinge.g.theDouglas-Peukeralgorithm.Inmeshsimplificationusedforthegeneralizationofsurfaces,therearemethodsthatanimatesmoothchanges,e.g.byanimatingtheinsertionorremovalofnodesinatriangularnetwork[Hoppe1998].

3ElementaryGeneralizationOperations

Theconceptofourideasisexplainedusingtheexampleofthesimplificationofbuildinggroundplans.Theycan,however,beexpandedtoothergeneral-izationoperations,whichwillbeshownlater.

ContinuousGeneralizationforVisualizationonSmallMobileDevices3

3.1TheGeneralizationChain

SimilartotheideasintroducedbyHoppe[1998]fortriangulatedmeshes,wedefineforapolygonPconsistingofnverticesamaximalrepresentationPn≡P,consistingofalloriginalvertices,andaminimalrepresentationPm,withm≤nvertices.Theminimalrepresentationistheonewhichisstillsensiblefromacartographicviewpoint,forexamplearectangle,m=4,ortheemptypolygon.

Whenapolygonisgeneralizedduringpre-processing,onestartsfrompoly-gonPn,successivelysimplifyingitsrepresentationusinggeneralizationoper-ations,finallyyieldingpolygonPm.Assumethatkgeneralizationstepsareinvolved(eachleadingtooneormoreremovedpolygonvertices),andthenumberofpolygonverticesarenumberedi0=n,i1,...,ik=m,thenasequenceofgeneralizedpolygons

P≡Pn≡Pi0−→g0Pi1−→g1...−→gk−1Pik≡Pm

isobtained,wheregjdenotesthej-thgeneralizationoperation.Everygener-alizationstepgjistiedtoacertainvalueofacontrolparameterεj,whichrelatestothedisplayscaleandcanbeforexamplethelengthoftheshort-estedgeinthepolygon.Sincegeneralizationproceedsusingincreasingedgelengths,thesequenceofεjismonotonicallyincreasing.Asafirstconsequenceofthis,onecanpre-computeandrecordalloperationsgj,inordertoderivequicklyanydesiredgeneralizationlevelεofpolygonPbytheexecutionofallgeneralizationoperationsg0,...,gj,whereε0,...,εj≤εandεj+1>ε.

However,itisobviousthatformostapplications,theinverseoperations−1

gjaremoreinteresting,producingamoredetailedpolygonfromageneral-izedone.Thus,wehavethesequence

Pm≡Pik−→g−1Pik−1−→g−1...−→g−1Pi0≡Pn,

k−1

k−2

0

whereagainonecandecideuptowhichpointthepolygonmodificationshouldbecarriedout,characterizedbythecorrespondingparameterε.Thisway,theinversegeneralizationchaincanbeusedforprogressivelytransmittinginformationoveralimitedbandwidthchannelbytransmittingPmfollowedbyasufficientnumberofinversegeneralizationoperations.

3.2ElementaryGeneralizationOperationsandSimpleOperationsWecandefineasetofelementarygeneralizationoperations(EGO’s)suchthateverygeneralizationchainwillbemadeupofacombinationofEGO’s.EGO’sareintendedtobe‘meaningful’operationssuchas‘removeanextru-sion’.EachEGOinturnconsistsofoneormoresimpleoperations(SO’s)modifyingthepolygon.SO’sarelow-level,basicoperations,andarethemostatomicoperationsavailable.Itisobviousthatthereareoperationswhichmod-ifythetopologyofapolygon,namelytheinsertionandremovalofvertices,

4MonikaSesterandClausBrennerSOIVDVMVRVDescriptionInsertVertexDuplicateVertexMoveVertexRemoveVertexParametersIV[edgeid][rel.position]DV[vertexid]MV[vertexid][dx][dy]RV[vertexid]InverseOperationRV[edgeid+1]RV[vertexid+1]MV[vertexid][-dx][-dy]–Table1.Setofsimplegeneralizationoperations.

andoperationswhichaffectthegeometryonly.Table1showsalistofsimpleoperations.Thislistisnotminimal,sincee.g.a’DVi’operationisequiva-lentto’IVi,0’.However,forconvenienceandforachievingamostcompactencoding,theoperationsmightbedefinedredundantly.Theparametersin-volvedareedgeandvertexid’sandrelativepositions.Edgeandvertexid’srefertoanimplicitnumberingofpolygonedgesandverticesinclockwiseorcounterclockwiseorder.Knowingtheparametersofasimpleoperationallowstoimmediatelygivetheinverseoperationexceptforthe’removevertex’oper-ationforwhichtheinversewouldrequireanadditionalparametertospecifythelocationofthevertextobeinserted.

4GeneralizationOperations

Inthissection,theuseofthesimpleoperations(SO’s)describedaboveisappliedtotwogeneralizationproblemsthatrelatetothegeneralizationofbuildings.Whenpresentingbuildingsinincreasinglysmallerscalerepresen-tations,differentgeneralizationoperationshavetobeapplied,whichcanbedistinguishedintothreemaingroupsofoperations,dependingonthescalelevels:inscalerangesupto1:20.000theindividualbuildingshapesaresim-plifiedbyinspectingthevisibilityoftheshortestfacades.Thisisshowninsection4.1.Furtherreducingthescalerequiresanamalgamationofadjacentbuildingstoformlargerobjects,asindividualbuildingswouldbetoosmalltostillberepresented.Inevensmallerscales,buildingshavetobeselectivelyremoved,enlargedandsymbolized.Thisrequiresthetypificationoperation,wheregroupsofindividualbuildingsarereplacedbynewgroupswithlessbuildings.Thisisdemonstratedinsection4.2.Thus,inthefollowing,theencodingoftwobuildinggeneralizationfunctionsintermsofEGO’swillbedemonstrated.Amalgamationisnottreatedhereindetail,howeverinsection6.1anoverviewisgiven,howothergeneralizationoperationscanberealized.4.1BuildingGeneralization

Thegeneralizationofbuildinggroundplanshastotaketheregularitiesoftheobjectintoaccount.Thus,especiallyrectangularityandparallelismhavetoberespectedandevenenforced.Weusearule-basedapproachwhichiteratively

ContinuousGeneralizationforVisualizationonSmallMobileDevices5

inspectssmallbuildingfacadesandtriestoreplacethemdependingonthespatialcontext,i.e.itsprecedingandsucceedingbuildingfacades[Sester2000].Inthisway,intrusionsandextrusionscanbeeliminated,aswellasoffsetsandcorners.Threerulescanbedecomposedintosimpleoperations.Inthefollowing,thegenerationofthesequenceofsimpleoperationsisdescribedforeachofthethreerules,leadingtothreeEGO’s.Theoperationsaretriggeredbyabuildingsidesnthatissmallerthanaminimumvalue󰀑,correspondingtoaminimumsidejustvisibleatagivenscale.Asnotedabove,theinverseoperationisdescribed,namelygoingfromageneralizedversiontothemorespecificone.Offset

Anoffsetisremovedbyextendingthelongersideoftheadjacentneighborsoftheshortestedgesn.InFigure1,sn−1isintersectedwithsn+2toproducethenewnodennew.Invertingthisprocessanddescribingitwiththesimpleoperationsdescribedabove,leadstothefollowingsequenceofSO’s,composingtheEGOforremovingoffsets.

Pn+1

sn+1

Pn

sn+1, new

Pn+1

Pnew

sn-1

sn-2

sn

sn+2

Pn

Figure1.Removinganoffsetandgeneratingsimpleoperationsforit.

1.Notelengthlnoftheshortestedgesn:

EPSl_nsn+1,old

2.InsertvertexPnonsidesn+1,newatrelativeposition:RelPos=sn

+1,new

IVS_n-1,RelPos

3.Duplicatethisvertex,andthuscreatenewpointPn+1.

DVP_n

4.MovethisnewvertexPn+1tothepositionoftheoldvertexPn+1,andmovevertexPntothepositionoftheoldvertexPn+2byincrementsdx1/dy1anddx2/dy2:

MVP_n+1,dx1,dy1MVP_n,dx2,dy2Extrusion

Anextrusioniseliminatedbyshiftingitbackorforthtobeinlinewiththecorrespondingmainbuildingside.Figure2showshowtheextrusionisshiftedbacktothecorpusofthebuilding.

6MonikaSesterandClausBrenner

Pn

sn

Pn+1

PnPn-1

Pn+1

sn-1sn-2Pn-1

sn+1sn+2

sn-2,new

Pnew

Figure2.Removinganextrusionandgeneratingsimpleoperationsforit.

Theextrusioniscutoffalongtheshortestneighboringfacadeofsn.InthecaseofFigure2,itissn−1,thusthenewstructureisderivedbyinter-sectingsidesn−2withsn+1leadingtotheintersectionvertexPnew.Invertingthisoperationleadstothefollowingsequenceofoperations,representinganextrusion-EGO:

1.Notelengthlnoftheshortestedgesn:

EPSl_ns−2,new

2.InsertvertexPn−1onsidesn−2,newatrelativeposition:RelPos=sn

n−2,old

IVs_n-2,RelPos

3.Duplicatethisvertex,thuscreatingnewvertexPn

DVP_n-1

4.MovethisvertextothepositionoftheoldvertexPn,andmovevertexPnewtothepositionoftheoldvertexPn+1byincrementsdx1/dy1anddx2/dy2:

MVP_n,dx1,dy1MVP_new,dx2,dy2Corner

Acornerisremovedbyintersectingtheadjacentedges(seeFigure3).

sn-1

Pn

sn

Pn+1

sn-1,new

Pn

Pnew

sn+1

Figure3.Removingacornerandgeneratingsimpleoperationsforit.

AnewnodeisinsertedattheintersectionpointPnewandthuscreatingtwonewbuildingsidessn−1,newandsn+1,new,andremovingsn.Invertingtheoperationleadstothefollowingsequence:

1.Notelengthlnoftheshortestedgesn:

EPSl_n

2.InsertvertexPnonsidesn−1,newatrelativeposition:RelPos=

IVs_n-1,RelPos

sn−1,oldsn−1,new

ContinuousGeneralizationforVisualizationonSmallMobileDevices7

3.MovevertexPnewtothepositionoftheoldvertexPn+1byincrementsdx1/dy1:

MVP_new,dx1,dy1UsingtheEGO’sdefinedaboveiterativelyallfacadesofthebuildingsareremoved–startingwiththeshortestoneandendingwhentheremovalofonefacadeleadstotheremovaloftheentirebuilding.Figure4showsasequenceofoperationsintheinversegeneralizationprocess.InthiscasethebuildingiscreatedatanEPSof5,whichisthewidthofbuilding,thenanextrusioniscreatedusingtheSO’sspecified.

v3EPS 5

e2v2e1

IV 1,60%

v4e4v0

e3e3v0

e0

v3e2v2e1v1

v5DV 2

e4e5v0

e0

v4e3, v3v2e1v1

v5MV 3,2,0MV 4,2,0

e4e5v0

e0

v4e3

v2e2v3e1v1

v1

e0

Figure4.SequencegeneratingasimplebuildingandcorrespondingSO’s.

InFigure5,theprogressiverefinementoffourbuildingsisshown:thesnapshotsvisualizehow–atcertainstagesoftheparameterEPSthatdescribesthediscernableminimaldistance–moreandmorebuildingsandbuildingdetailsappear.Figure6showssomesnapshotsofalargerareainincreasing

Figure5.Progressivevisualizationoffourbuildingsatfourlevelsofdetail.

levelsofdetail:itisclearlyvisible,howmoreandmoresmallbuildingsappear,andtheyaredisplayedwithmoreandmoredetail.

Figure6.Snapshotsofincrementallyaddingmoreandmoredetail.

8MonikaSesterandClausBrenner

4.2Typification

Typificationdenotestheprocessofreducingthenumberofobjectsoutofasetofsimilarobjectswhilepreservingtheirrelativespatialdensity.Typificationisadiscreteprocess,whereasetofobjectsisreplacedbyanothersetcontainingasmallernumberofobjects.SuchachangeinrepresentationcanbecodedwiththeabovedescribedSO’s.Ithastoberealizedbyremovingtheobjectsatonegeneralizationlevelandintroducingnewobjectsatthesametime.ThesequenceinFigure7showsthegenerationandremovalofabuilding:anewpolygoniscreatedatthegeneralizationlevelEPS=10atposition(65,65)byfirstinsertingavertex;threeotherverticesarecreatedbyduplicationofthisvertex,thenallfourverticesaremovedtofourpositionsaroundthecenterpointandthusasquarewithasideof20isfinallycreated.Thisobject’survives’untilthelevelEPS=5whenit’collapses’bymovingallitsfourcornerstothecenterpointagain.

POLYEPS10NPR6565DV0DV0DV0

MV0-1010MV1-10-10MV210-10MV31010EPS5

MV010-10MV11010MV2-1010MV3-10-10

newPolygon

thefollowinginstructionappearsatmin.distance10

createnewpolygonring,consistingofonlyonepointatposition65/65;thispointgetsID0

duplicatethispointthreetimes,thuscreatepoints1to3

movepoint0totheleftandupwardsalsomoveotherpoints

nexteventhappensatminimumvalueEPS=5

movepoints0totherightanddownwards(i.e.totheoriginalzero-position65/65)

dothesamewiththeotherpoints

Figure7.Exampleoperationstogenerateandcollapseanobject.

Inthisway,adiscretechangeinrepresentationcanbecoded.Figure8showsthesequenceofatypificationofaregularstructureof16buildingsbeingreplacedbyfourandfinallybyoneinthedifferentscales,respectively.

Figure8.Threedifferentresolutions:high,mediumandlow,correspondingto󰀃=1.8,6,11,respectively.

Thegenerationofthedifferentrepresentationshastobedoneinaseparateprocess.Inourcase,weusedanapproachbasedonKohonenFeatureNetsinordertodotherearrangementofthereducednumberofobjects[Sester2004].

ContinuousGeneralizationforVisualizationonSmallMobileDevices9

Figure9showsaspatialsituationbeforeandaftertypification.Intheprocessthenumberofbuildingsisreduced,theremainingobjectsarerearrangedandthenpresentedbyeithertheoriginalbuidldingorasquaresymboldependingonitssize.Figure9.Situationbefore(left)andaftertypificationofbuildings(right).

5ContinuousGeneralizationandTransmission

5.1ContinuousGeneralization

Whenanobjectrepresentationisswitchedduetogeneralization,thisusuallyleadstoavisible‘popping’effect.Comparedtoswitchingbetweendifferent,fixedlevelsofdetail,theuseofEGO’sisalreadyanimprovement,sinceitgraduallymodifiesthepolygonratherthanjustreplacingitasawhole.How-ever,onecanstillimprovethis.IntermediatestatescanbedefinedwhichcontinuouslychangetheobjectinresponsetoanEGO.Forexample,a‘col-lapseextrusion’EGO(seeFigure2)wouldbeinterpretedas‘moveextrusionuntilincoincideswiththemainpart,thenchangethetopologyaccordingly’.Wetermthisapproachcontinuousgeneralizationasiteffectivelyallowstomorphtheobjectcontinuouslyfromitscoarsesttoitsfinestrepresentation.SinceeachEGOismadeoutofoneormoreSO’s,theireffectsondisplaypoppinghastobetakenintoaccount.However,thisistrivial,sincewecandeduceimmediatelythatIVandDVarenotchangingtheobject’sgeometry.RVwillonlyleadtoavisibleeffectifthevertex,itspredecessoranditssucces-sorarenon-collinear.Thus,MVistheonlySOthathastoberegarded.Thismeansthatacontinuousgeneralizationcanbeachievedbyusinganappro-priateencodingofEGO’sintermsofSO’s,togetherwithananimationintheclientwhichgraduallyshiftsverticesinsteadofmovingtheminonestepuponencounteringaMVoperation.Thisisimplementedintheprototype.5.2AClient-ServerCommunicationSchemeforProgressivelyStreamingMapData

Todescribethemechanismsofaprogressivestreamingofmapdata,wenowintroducethenotionofaclientandaserver.Incaseofinternetmapdisplays,

10MonikaSesterandClausBrenner

off-boardcarnavigationaswellaspersonalnavigationsystems,thesetakejusttherolesasexpected.However,inotherapplications,theymightbedefineddifferently.Forexample,on-boardcarnavigationsystemsmightdefinetheserverasthemainCPUunitwherethemassstorageresides,andtheclientasbeingtheheadunitCPUusedformapdisplayanduserinput.

OnepossiblerealizationisdepictedinFigure10,basedontheassumptionthattheserverkeepstrackofthestateoftheclient.Astatelessapproachcouldbeusedinstead,howeverthiswouldimplyalargeramountofcommunication,tellingtheservereachtimetheobjectid’sandgeneralizationlevelspresentintheclientinordertoallowtheservertocomputetheappropriatedifferentialSO’s.

Whentheuserrequestsanewpartofthemap,theclientisabletocomputetheboundingboxinworldcoordinatesandthegeneralizationlevelε,thelatterpossiblybeingbasedonthescaleaswellassomepreferenceswhichcouldbalancespeedversus‘mapquality’.Theclientsendsthisinformationtotheserverwhichcanretrievetheappropriateobjectsfromthedatabase.Sincetheserverkeepstrackofwhichobjectshavealreadybeensenttotheclient,itcandeducetheappropriateSO’sneededtoupdatethedisplayandsendthemtotheclient.WhilereceivingSO’s,theclientwillconstantlyrefreshitsdisplay.IftheuserinteractsbeforetheentiresetofSO’shasbeensent,theclientmaysendabreakrequesttotheserverwhichinturnwillstopsendingSO’s.Theremightbeadditionalcommunicationitems,forexampletoallowtheclienttodropobjectscurrentlyoutofviewtoconservememory.

UserStart systemClientStart a new sessionStore session idSession idServerGenerate unique session idPan / zoom to a certain map areaUser inputCompute world bounding box and generalization level neededBounding boxGeneralization levelRetrieve objects inside world bounding boxCompare with objects and levels already sent to the clientGenerate SO’srequired to update client’s displaySO’sVisual outputView results as they appearUpdate display progressivelyPan / zoom to another map areaUser inputEtc.Figure10.Exampleinteractiondiagramforclient-servercommunication.

ContinuousGeneralizationforVisualizationonSmallMobileDevices11

6Evaluationofresultsanddiscussion

6.1DiscussiononapplicationforothergeneralizationoperationsGeneralizationoperationscanbecharacterizedbychangesoccurringtoob-jectswhichareeitherdiscreteorcontinuous.Thesechangescanaffectindi-vidualobjectsandgroupsofobjects,respectively.

Thetwogeneralizationoperationsdescribedaboveareofthetypeofdis-cretechangesaffectingindividualobjects(section4.1)andgroupsofobjects(section4.2).Whathasbeenshownforthesetwogeneralizationoperationscanbeextendedtootherfunctionsaswell:amalgamationisanoperationthatleadstodiscretechangesofgroupsofobjects,andthusisinthesamecategoryasthetypificationoperation.Onceanappropriatealgorithmisavailable(e.g.[Bundy,Jones&Furse1995]),thecodinghastobedoneintermsofSO’sandEGO’s.Inthiscase,similartothetypification-encoding,objectshavetobereplacedbyotherobjects(inthecaseofmergingtwobuildings,thetwoobjectsceasetoexistandarereplacedbythemergedone).

Displacementisanotherimportantgeneralizationoperationtosolvespa-tialproximityconflictsbyshiftingobjectsapartandpossiblydeformingtheshapesslightly;itcanbecategorizedasacontinuousoperation.DisplacementcanbecodedeasilyashereonlyaMV-operationwithrespecttoallobjectpointsisneeded.IntermsofEGO’sacompoundmovementofallpointsofanobjectcanbebundled–onlyhowever,whennodeformationoftheobjectoccurs.ExistinggeneralizationalgorithmscanbeextendedtogeneratethecodingintermsofSO’s,e.g.Sester[2004].6.2Datavolume

Inordertoevaluatethedatavolumetobetransmittedusingthecodingschemeproposedabove,thefollowingestimationcanbedone:inourcodingscheme,onlyincrementalrefinementshavetobesenttotheclient,insteadofsendinganewrepresentationofthewholedatawheneverachangeinthedetailofthedataoccurs.Incaseofbuildingsimplificationabuildingconsistingofnpointsisiterativelysimplifieduntilapolygonwithtypically4pointsisreachedandthenitvanishes.IneachoftheEGO’soneortwopointsareremoved,thusinordertopresentallpossibleLOD’sapprox.n/2differentrepresentationshavetobetransmitted,leadington∗n/2points.Ourcodingscheme,however,requiresonlyn/2operationsleadingtoareductionfactorofapprox.1/n.

Therepresentationinourcodingschemeiscomparedtotheoriginalrepre-sentationofthedatasetintermsofanESRIshapefilefordifferentdatasets:thesizeofthedatasetinFigure6consistingof119buildingsis30Kbyte;theoriginalrepresentationintermsoftheESRIshapefile(the.shp-file)is20kByte.Anotherdatasetconsistingof2000buildingsrequires0.45MByteintermsofSO’s.Theoriginalshapefileneeds0.312MByte.Thefollowingobservationshavetobeconsideredwhenevaluatingthesenumbers:

12MonikaSesterandClausBrenner

•••

Therehavenotyetbeenanyconsiderationsconcerningefficientstorageofthecode.

TheSO-codingincludesallgeneralizationlevelsthatarepossiblebetweenthemostdetailedrepresentationoftheobjectsanditsmostgeneralone.ThecodingintermsofEGO’sallowstogroupseveralSO’stoahigherlevelstandardoperation.Inthecurrentimplementation,however,theEGO’snotyethavebeenefficientlycoded,butaredescribedintermsofSO’s.

7ConclusionandFutureWork

TheresearchpresentedinthispaperwasmotivatedbythefactthataspatialdatasetonasmalldisplaydevicelikeaPDAtypicallyhastobevisualizedindifferentlevelsofdetail:foranoverviewonlycoarseinformationofalargerextentofthemapisneeded;whentheuserzoomsininordertoinspectdetails,progressivelynewinformationisloadedforthatsmallersectionofthemaptheuserisinterestedin.However,theapproachisgenerallyapplicable,whenspatialdatatobepresentedisnotavailableonthedeviceitself,buthastobetransmittedfromaremoteserver.Besidesthetransmissiontomobiledevicesdescribedabove,thisalsoholdsforthepresentationofspatialdataintheinternet.

Inthepaperanapproachwaspresentedthatdecomposesgeneralizationoperationsintosimpleoperationsleadingtochangesintopologyandgeometry.Itwasshownhowthesesimpleoperationscanbeusedtocodemorecomplexoperationsdealingwithcontinuousandalsodiscretechangesintheobjects.Finally,animplementationforaclient-serverdatatransmissionwaspresented.Inthecurrentconcept,thegenerationoftheEGO’sisanoff-lineprocess,thatisdonebeforehand.Itis,however,alsopossibletogeneratethecodeon-the-flyuponarequestoftheclient.Inthiscase,theresponsetimeontheclientwillbedelayedbythetimeneededforthegeneralizationprocess.Thusthetrade-offbetweenstoringoverheadofthedataintermsofEGO’sandprocessingtimeforthegeneralizationhastobebalanced.Thiswillbesubjecttofurtherinvestigations.Futureworkwillalsoconcentrateofimplementingthisconceptinadistributedsystemenvironmentandontheintegrationofothergeneralizationoperations.

References

Bertolotto,M.&Egenhofer,M.[1999],ProgressiveVectorTransmission,in:‘Trans-actionsoftheACMGIS99’,KansasCity,MO,pp.152–157.

Bundy,G.,Jones,C.&Furse,E.[1995],Holisticgeneralizationoflarge-scalecarto-graphicdata,inMu¨ller,Lagrange&Weibel[1995],pp.106–119.

Douglas,D.&Peucker,T.[1973],‘Algorithmsforthereductionofthenumberof

pointsrequiredtorepresentadigitizedlineoritscaricature’,TheCanadianCartographer10(2),112–122.

ContinuousGeneralizationforVisualizationonSmallMobileDevices13

Hake,G.,Gru¨nreich,D.&Meng,L.[2002],Kartographie,Gruyter.

Harrie,L.E.[1999],‘Theconstraintmethodforsolvingspatialconflictsincar-tographicgeneralization’,CartographiyandGeographicInformationScience26(1),55–69.

Højholt,P.[1998],SolvingLocalandGlobalSpaceConflictsinMapGeneraliza-tionUsingaFiniteElementMethodAdaptedfromStructuralMechanics,in:T.Poiker&N.Chrisman,eds,‘Proceedingsofthe8thInternationalSymposiumonSpatialDatahandling’,Vancouver,Canada,pp.679–6.

Hoppe,H.[1998],Smoothview-dependentlevel-of-detailcontrolanditsapplication

toterrainrendering,in:‘IEEEVisualization’98’,pp.35–42.

Lamy,S.,Ruas,A.,Demazeau,Y.,Jackson,M.,Mackaness,W.&Weibel,R.[1999],

TheApplicationofAgentsinAutomatedMapGeneralization,in:‘Proceedingsofthe19thInternationalCartographicConferenceoftheICA’,Ottawa,Canada,pp.1225–1234.Mu¨ller,J.-C.,Lagrange,J.-P.&Weibel,R.,eds[1995],GISandGeneralization-MethodologyandPractice,Taylor&Francis.

Nivala,A.-M.,Sarjakoski,L.,Jakobsson,A.&Kaasinen,E.[2003],UsabilityEvalu-ationofTopographicMapsinMobileDevices,in:‘Proceedingsofthe21stInter-nationalCartographicConferenceoftheICA’,Durban,SouthAfrica,pp.1903–1913,CD–ROM.

Regnauld,N.[1996],RecognitionofBuildingClustersforGeneralization,in:

M.Kraak&M.Molenaar,eds,‘AdvancesinGISResearch,Proc.of7thInt.SymposiumonSpatialDataHandling(SDH)’,Vol.1,FacultyofGeod.Engi-neering,Delft,TheNetherlands,pp.4B.1–4B.14.

Reichenbacher,T.[2004],MobileCartography:AdaptiveVisualizationofGeo-graphicInformationonMobileDevices,PhDthesis,TechnischeUniversit¨atMu¨nchen.

Sarjakoski,T.,Sarjakoski,L.,Lehto,L.,Sester,M.,Illert,A.,Nissen,F.,Rystedt,R.

&Ruotsalainen,R.[2002],GeospatialInfo-mobilityServices-aChallengeforNationalMappingAgencies,in:‘ProceedingsoftheJointInternationalSympo-siumon’GeoSpatialTheory,ProcessingandApplications’(ISPRS/CommissionIV/SDH2002)’,Ottawa,Canada,CD-Rom.

Sester,M.[2000],GeneralizationbasedonLeastSquaresAdjustment,in:‘IAPRS’,

Vol.33,ISPRS,Amsterdam,Holland.

Sester,M.[2004],OptimizingApproachesforGeneralizationandDataAbstraction,

Technicalreport,acceptedforpublicationin:InternationalJournalofGeograph-icalInformationScience.

vanKreveld,M.[2001],SmoothGeneralizationforContinuousZooming,in:‘Pro-ceedingsoftheICA’,Beijing,China.

vanOosterom,P.[1995],TheGAP-tree,anapproachto’on-the-fly’mapgeneral-izationofanareapartitioning,inMu¨lleretal.[1995],pp.120–132.