48. Fejezet - VONALGENERALIZÁLÁS
Szerkesztette: Robert McMaster, Syracuse University
Magyar változat: Márton Mátyás, Eötvös Loránd Tudományegyetem, Budapest
A. BEVEZETÉS
B. A VONALGENERALIZÁLÁS ELEMEI
Egyszerűsítés
Simítás
Objektum (képződmény, tereptárgy) eltolása
Kiemelés/texturálás
Összevonás
C. A LINEÁRIS ADATEGYSZERŰSÍTÉS IGAZOLÁSA
Rajzolási idő csökkentése
Tárolási hely csökkentése
A plotter felbontóképességének problémái csökkentett méretarány esetén
Feldolgozás
D. LINEÁRIS EGYSZERŰSÍTÉSI ALGORITMUSOK
Független-pont eljárások
Lokális (szomszédospont-vizsgálati) módszerű eljárások
Nem-korlátozottan kiterjesztett lokális módszerű eljárások
Korlátozottan kiterjesztett lokális módszerű eljárások
Globális eljárások
E. AZ EGYSZERŰSÍTÉSI ELJÁRÁSOK MATEMATIKAI ÉRTÉKELÉSE
F. LINEÁRIS SIMÍTÁS
IRODALOM
ELLENŐRZŐ KÉRDÉSEK
48. Fejezet - VONALGENERALIZÁLÁS
Szerkesztette: Robert McMaster, Syracuse University
Magyar változat: Márton Mátyás, Eötvös Loránd Tudományegyetem, Budapest
A. BEVEZETÉS
- generalizáláson a (térképészeti) eljárások olyan csoportját értjük, amely lehetővé teszi, hogy az információmennyiséget megőrizzük annak ellenére, hogy az adatmennyiséget csökkentjük
- pl. amikor egy vonalon levő pontok számát csökkentjük, a megtartott pontokat úgy választjuk ki, hogy a vonal képe ne változzék
- bizonyos esetekben a generalizálás tulajdonképpen az információmennyiség növekedését eredményezi
- pl. egy partvonalat reprezentáló vonal generalizálását jobban végezhetjük, ha felhasználjuk azt az ismeretet, hogy hogyan kell egy partvonalnak kinéznie
- ebben a fejezetben a vonalgeneralizálással foglalkozunk
- a vonalgeneralizálás a kartográfiai generalizálás kérdéskörének csupán kis része - az átfogóbb kérdéskör tartalmazza pl. a területek generalizálását pontokká
- a hangsúly e fejezetben a vonalak egyszerűsítésén van
- az egyszerűsítés a generalizálásnak csupán az egyik megközelítése (lásd alább)
B. A VONALGENERALIZÁLÁS ELEMEI
- a generalizálást végző mértanilag változtatja meg az x-y koordinátapárok sorozatát
Egyszerűsítés
- az egyszerűsítési algoritmusok kiválogatják a valamilyen geometriai szempont szerint feleslegesnek vagy szükségtelennek ítélt koordinátapárokat; ilyen szempont lehet a pontok közötti távolság vagy egy középvonalhoz viszonyított eltérés
Simítás
- a simító rutinok áthelyezik vagy eltolják a koordinátapárokat, s így megkísérelik elegyengetni a kis "perturbációkat" és csak a vonal legjelentősebb trendjeit megragadni
Objektum (képződmény, tereptárgy) eltolása
- az eltolás magába foglalja két képződmény helyének megváltoztatását egy méretaránycsökkentésnél, hogy megelőzzük egybeolvadásukat vagy átfedésüket
- a vektoralapú objektumáthelyezésre készített legtöbb számítógépes algoritmus interaktív megközelítésre épít, ahol a kartográfus adja meg az eltolási vektort annak érdekében, hogy meghatározza az elmozdítás irányát
- egy másik módszer az objektum kisebb méretarányú változatát használja az áthelyezési folyamat vezérléséhez
Kiemelés/textúrálás
- a kiemelés részletek visszaállítását (újra-generálását) teszi lehetővé egy már egyszerűsített adatkészletben
- pl. egy sima görbe nem partvonalnak látszik, így a vonalat találomra texturáljuk, hogy javítsuk a képét
- egy eljárás a vonal fraktalizálására (részletgazdadabbá tételére) szolgál, pontok hozzáadásával és az eredeti változathoz való hasonlóság fenntarásával
- ez hamisított (véletlenszerű) részleteket eredményez
Összevonás
- az egybemásolás csökkenő méretarányban összevon (összeolvaszt) két párhuzamos (egynemű, egy kategóriába tartozó) objektumot
- pl. a folyó két partja vagy az autópálya két széle összeolvad kis méretarányokban, egy sziget ponttá válik
- az összemásolásra szolgáló algoritmus egybeolvasztja a két vonalas objektumot
C. A LINEÁRIS ADATEGYSZERŰSÍTÉS IGAZOLÁSA
Rajzolási idő csökkentése
- a plottolási (nyomtatási) idő gyakran a szűk keresztmetszet számos GIS-ben
- mivel az egyszerűsítési eljárás során sok koordinátapárt kiszűrünk, a nyomtatási sebesség nő
Tárolási hely csökkentése
- sok GIS-ben a koordinátapárok képezik az adatok zömét
- az egyszerűsítés 70%-ra csökkentheti az adatállományt anélkül, hogy megváltoznának a vonal érzékelhető jellegzetességei
- ez jelentős memória-megtakarítást eredményez
A plotter felbontóképességének problémái csökkentett méretarány esetén
- amint egy digitális térkép méretaránya csökken, a koordinátapárok egymáshoz közelebb kerülnek
- jelentős méretaránycsökkenés mellett a számítógépes felbontás könnyen meghaladhatja a kimeneti eszköz grafikus felbontását
- pl. a (0,1; 6,3) koordinátapár 50%-os redukció esetén (0,05; 3,15) lesz, s ez gyakorlatilag nem jeleníthető meg olyan eszközzel, amelynek pontossága 0,1. Az egyszerűsítés eltünteti az ilyen koordinátapárokat még a (méretarány)redukció előtt
Feldolgozás
- gyorsabb vektor®
raszter átalakítás
- gyorsabb vektorműveletek
- a sokféle vektorművelet elvégzéséhez szükséges idő, ide értve az eltolást, az elforgatást, a méret(arány)-változtatást, a kartometriai analízist, nagymértékben csökken egy egyszerűsített adatkészlettel
- sokfajta jelgenerálási művelet szintén felgyorsul
- pl. sok árnyékolási (summer-) algoritmus kiszámítja a poligonhatárok és az árnyékvonalak metszéspontjait - egy egyszerűsített poligonhatár-vonal mind a határoló szakaszok számát, mind a szükséges metszéspontok kiszámításának mennyiségét csökkenti
D. LINEÁRIS EGYSZERŰSÍTÉSI ALGORITMUSOK
48.1. ábra - Lineáris egyszerűsítési algoritmus
Független-pont eljárások
- ezek az eljárások természetükből adódóan nagyon egyszerűek, és semmilyen módon nem veszik számításba a topológiai összefüggéseket a környező koordinátapárokkal
- 1. n-edik pont eljárás
- minden n-edik (pl. minden 3., vagy minden 10.) koordinátapárt megtartunk
- 2. a koordinátapárok halmazának n-ed részét véletlenszerűen kiválasztjuk
Lokális (szomszédospont-vizsgálati) módszerű eljárások
- ezek felhasználják a közvetlenül szomszédos pontok jellegzetességeit annak eldöntéséhez, hogy a vizsgált koordinátapár megmaradjon-e
- 1. Pontok euklideszi távolsága
- 2. pontok közötti szögváltozás
48.2. ábra - Merőleges távolság és szögváltozás
- 3. Jenks egyszerűsítési algoritmusa
48.3. ábra - Jenks egyszerűsítési algoritmusának ábrája
- három bemenő paraméter:
MIN1 = minimális megengedett távolság az 1. ponttól a 2. pontig
MIN2 = minimálisan megengedett távolság az 1. ponttól a 3. pontig
ANG = a három pontot összekötő két vektor maximális megengedett irányváltozása
- algoritmus:
If távolság(1.pont,2.pont) < MIN1,
or
távolság(1.pont,3.pont) < MIN2
then a 2.pontot elhagyjuk
else
If szög(1.pont,2.pont,3.pont) < ANG
then a 2.pontot elhagyjuk
Nem-korlátozott kiterjesztett lokális módszerű eljárások
- ezek az algoritmusok a közvetlenül szomszédos koordinátapárokon és a vonal kiértékelt szakaszain túl keresnek
- a keresés kiterjesztése számos kritériumtól függ; ilyenek:
- a vonal bonyolultsága (összetettsége)
- a koordinátakészlet sűrűsége
- a szakaszos vizsgálat kezdőpontja
- Reumann-Witkam egyszerűsítési algoritmusa
48.4. ábra - Reumann-Witkam egyszerűsítési algoritmus
- az algoritmus két párhuzamos vonalat használ a vizsgálati sáv meghatározásához
- a kezdő irány kiszámítása után a vizsgálati sáv addig húzódik, amíg valamelyik széle belemetsz a vonalba; az eljárás szakaszosan ismétlődik
Korlátozottan kiterjesztett lokális módszerű eljárások
- ezek az algoritmusok az előzőekhez hasonlóak, azonban megszorításokat tartalmaznak a keresésben:
- 1. koordinátavizsgálati régiók
- 2. távolságvizsgálati régiók
- Opheim egyszerűsítési algoritmusa
48.5. ábra - Opheim egyszerűsítési algoritmusa
- a Reumann-Witkam eljárással azonos, kivéve hogy az algoritmus egy minimum- és maximumtávolság-ellenőrzéssel szigorított, igen hasonlóan Jenks eljárásához
- miután a kezdő vizsgálati régiót beállítottuk, amely a Reumann-Witkam eljáráshoz hasonlóan történik, a DMIN-on belüli pontokat elhagyjuk
- amint a vonal bármely oldalon kilép, a DMAX-ot a végén tartalmazó vizsgálati régióból, az utolsó, még a régióba eső pontot megtartjuk és új vizsgálati folyosót jelölünk ki
- egy ív mentén az eljárás viselkedését (működését) a C és D ábrarész mutatja
- Lang egyszerűsítési algoritmusa
- Johannsen egyszerűsítési algoritmusa
Globális eljárások
- a vonalat teljes terjedelmében vizsgálják működés közben
- Douglas egyszerűsítési algoritmusa
48. 6.a és 6.b ábra - Douglas egyszerűsítési algoritmusa I és II
- válasszunk egy tűrési sávot vagy folyosót (az ábrán az árnyékolt terület) - ez a folyosó úgy határozható meg, mint az első és utolsó koordinátapárral definiált pontokat (példánkban 1 és 40) összekötő egyenes két oldalán fekvő t1 szélességű sáv
- az 1. pont a rögzített pont, 40. a mozgó pont
- a folyosó létrehozása után kiszámítjuk a 2-39. koordinátapárokkal meghatározott pontok merőleges távolságát a folyosó tengelyétől, hogy kiválaszthassuk a legtávolabbi pontot
- ez a legnagyobb távolság esetünkben a 32. ponthoz tartozik, amely a folyosótól elég távol helyezkedik el
- ezt a koordinátapárt egy verem első helyén őrizzük meg
- következő lépésben új folyosót hozunk létre az 1. és 32. pont között, ekkor a 23. a legtávolabbi pont - itt a 32. pont a mozgópont
- ez az eljárás folytatódik mindaddig, amíg az összes pont a folyosón belülre nem kerül
- miután az eljárás visszajuttat a 4. ponthoz, új rögzített és mozgó pontot jelölünk ki: a 4. és a 23. (azaz az utolsó elvermelt) pontot
- ilyen módon a Douglas-algoritmus feldolgozza a teljes vonalat, visszalépegetve addig, amíg az összes közbülső pont a folyosón belülre nem kerül és akkor kiválasztja a veremből a következő elmentett koordinátapárt
- így végül a 23. és 32. koordinátapár közé eső vonalszakaszt kiértékeltük, és a 32. ponttól a vonal végpontjáig tartó folyosó lesz a végső számítási szakasz
E. AZ EGYSZERŰSÍTÉSI ELJÁRÁSOK MATEMATIKAI ÉRTÉKELÉSE
- számos különböző típusú mérés használható az egyszerűsítési eljárások értékelésére
- az egyik típus az egyszerű tulajdonságok mérése
- a másik típus az eltolás mérése
- az egyszerű tulajdonság - mint a vonalhossz, szögletesség, görbület - méréseket, egyszerű vonalakhoz alkalmazhatunk
- ezek akár az alapvonalra, akár az egyszerűsített vonalra alkalmazhatók
- másoldalról, az eltolási vagy összehasonlító mérések, az alapvonal és az egyszerűsített vonal közötti különbséget értékelik ki
48.7. ábra - Mérések a lineáris egyszerűsítésre
48.8. ábra - Területi eltolás
- úgy tűnik, hogy bizonyos algoritmusok sokkal jobbak másoknál az adatok kritikus mértani jellegzetességeinek megtartásában
- Douglas, Lang, Reumann-Witkam és Opheim algoritmusa mind észszerű választásnak tűnik
- a két legjobb a Douglas és a Lang-féle
F. LINEÁRIS SIMÍTÁS
- simítást alkalmaznak digitális vonaladatokhoz annak érdekében, hogy a vonal esztétikai értékét javítsák és eliminálják a digitalizáló eszköz hatásait
- általában véve úgy érezzük, hogy a simítás javítja ezen adatok értékét
- a simítás növeli a szükséges koordináták számát, így rendszerint csak a kimenetnél alkalmazzák
IRODALOM
Buttenfield, B.P., 1985. "Treatment of the Cartographic Line," Cartographica 22(2):1-26.
Douglas, D.H. and T.K. Peucker, 1973. "Algorithms for the Reduction of the Number of Points Required to
Represent a Line or Its Character," The American Cartographer 10(2):112-123.
McMaster, R.B., 1987, "Automated Line Generalization," Cartographica 24(2):74-111.
McMaster, R.B., 1987. "The Geometric Properties of Numerical Generalization," Geographical Analysis
19(4):330-346.
McMaster, R.B.,1989. "The Integration of Simplification and Smoothing Algorithms," Cartographica 26(1).
Persson, I. and Jungert, E. 1992. "Generation of multi-resolution maps from run-length-encoded data",
International Journal of GIS Vol. 6, No. 6., p. 497-510.
Peucker, T.K., 1975. "A Theory of the Cartographic Line," Proceedings, Second International Symposium
on Computer-Assisted Cartography, AUTO-CARTO-II, September 21-25, 1975 U.S. Dept. of Commerce, Bureau of Census and ACSM, pp. 508-518.
Ware, J.M. and Jones C.B. 1992. "A multiresolution topographic surface database", International Journal of
GIS, Vol. 6., No. 6., p. 479-496.
White, E., 1985. "Assessment of Line-Generalization Algorithms Using Characteristic Points," The American
Cartographer 12(1):17-27.
Irmédi-Molnár L.,1970. "Térképalkotás", Tankönyvkiadó, Budapest
Klinghammer I.-Papp-Váry Á., 1983. "Földünk tükre a térkép", Gondolat, Budapest
Stegena L. (szerk.), 1970. "A térképi generalizálás", Studia Cartographica,ELTE, Budapest
Stegena L. (szerk.), 1971. "Térképi generalizálás", Tankönyvkiadó, Budapest
Stegena L.-Klinghammer I.-Füsi L.,1972. "Az automatizálás a kartográfiában II.", Tankönyvkiadó, Budapest
ELLENŐRZŐ KÉRDÉSEK
1. Fejtse ki a vonalegyszerűsítés szakaszos és a globális megközelítése közötti különbségeket!
2. Nevezze meg az öt - a digitális vonaladatok esetében alkalmazott - generalizálási műveletet! Ismertesse ezek egyikét részletesen és mondjon példákat!
3. Az ábrasort használva fejtse ki a Douglas-algoritmus működési módját!
4. Fejtse ki azokat a különböző megközelítési módokat, amelyeket a vonalegyszerűsítés hatékonyságának kiértékelésére használna! Minden esetben ismertesse a mellettük szóló és az ellenérveket!
|