|
32. Fejezet - EGYSZERŰ ALGORITMUSOK I - VONALAK METSZÉSEI
Szerkesztette: David H. Douglas, University of Ottawa és
David M. Mark, State University of New York at Buffalo
Magyar változat: Sárközy Ferenc, Budapesti Műszaki Egyetem
A. BEVEZETÉS
B. MEGHATÁROZÁSOK
Algoritmusok
Heurisztika (ráérzések)
C. A LEGEGYSZERŰBB ESET
Kérdés
Eljárás
Megoldás
Általános alak
Egyszerű program
D. KÜLÖNLEGES ESETEK
Függőleges vonalak
Párhuzamos vonalak
Megoldás
E. KOMPLEX VONALAK
A legkisebb befoglaló téglalap
Monoton szakaszok
Vonalosztályozás
IRODALOM
ELLENŐRZŐ KÉRDÉSEK
32. Fejezet - EGYSZERŰ ALGORITMUSOK I - VONALAK METSZÉSEI
Szerkesztette: David H. Douglas, University of Ottawa és
David M. Mark, State University of New York at Buffalo
Magyar változat: Sárközy Ferenc, Budapesti Műszaki Egyetem
A. BEVEZETÉS
- két vonal metszése fontos művelet a GIS-ben
- használják a poligon fedvényezési műveletekben, poligonok és vonalak megszüntetésénél és egybeolvasztásánál
- alapja a "pont a poligonban" műveleteknek s fontos a szétcsúszások felszámolásánál
- ezért a két vonal metszéspontját meghatározó algoritmus igen fontos minden GIS számára
- a komplex folyamatok GIS algoritmusait rendszerint egyszerű algoritmusokból építik fel
- ez a rész néhány egyszerű algoritmust fog áttekinteni. A későbbi részek majd megmutatják, hogy miként lehet belőlük komplex műveleteket felépíteni
- az első művelet két vonal metszésére vonatkozik
- először két egyenes metszését vizsgáljuk, majd áttérünk két összetett vonal vagy poligon vizsgálatára
- végül is látni fogjuk, hogy ez az algoritmus számos GIS művelet magját képezi, ezek közé tartoznak a "pont a poligonban" és a poligon fedvényezési eljárások is.
- az algoritmus illusztrálja az ilyenfajta programozás egyik alapelvét, mégpedig azt, hogy számos speciális eset van, melyeket figyelembe kell venni
B. MEGHATÁROZÁSOK
Algoritmusok
- az algoritmus egy olyan eljárás, mely egyértelmű szabályegyüttes segítségével, véges műveletsorozattal megold egy problémát vagy probléma osztályt
- az algoritmus minden lépésének egyértelműnek és jól definiáltnak kell lennie
- a végrehajtandó lépéseket minden esetre szigorúan specifikálni kell
- az algoritmusnak véges lépésszám után minden esetben el kell jutnia a megoldáshoz
- a lépésszámnak egyben racionálisnak kell lennie
- minden tényleges algoritmus egy vagy több eredményt szolgáltat
- előnyösebbek azok az algoritmusok, melyek több rokon problémára is alkalmazhatók
- a probléma növekedésével általában növekszik a megoldás költsége is
- ha a probléma mérete eléggé kicsi, akkor még egy kevéssé hatékony algoritmus alkalmazása esetén sem lesz hosszú a futásidő
- következésképpen egy kis probléma esetén a megoldás keresése mindaddig nem jelent gondot, amíg a probléma megoldására nem kerül túl gyakran sor
Heurisztika
- a heurisztika összefoglaló neve azoknak a ráérzésen (tapasztalaton) alapuló módszereknek, melyek drasztikusan meggyorsítják a megoldás megkeresését nagy probléma-terekben
- nem biztosítják az optimális megoldást, sőt még az sem biztos, hogy egyáltalán találnak megoldást
C. A LEGEGYSZERŰBB ESET
Kérdés
Keresztezi-e a (4,2)-ből (2,0)-ba tartó egyenes a (0,4)-ből (4,0)-ba tartót, és ha igen, akkor hol?
Eljárás
- keresd meg a két egyenes egyenletét és a metszéspont meghatározására együtt oldd meg őket
- a vonal egyenlete:
y = a + bx ahol 'b' az egyenes meredeksége
- ha adva van az egyenes két pontja (x1,y1) és (x2,y2), úgy a meredekség az alábbi kifejezésből határozható meg:
b =(y1-y2) /(x1-x2)
- az 'a' értékét az egyenes egyenletéből nyerjük valamelyik pont behelyettesítésével
Megoldás
- a fönti első egyenes esetében
b = (2-0)/(4-2) = 1
- az első pont felhasználásával
2 = a + 4
azaz a = -2
- az egyenlet ezek után y = -2 + x
- a második egyenesnél hasonlóan y = 4 - x
- a kétismeretlenes egyenletrendszer megoldásából azt kapjuk, hogy a metszéspont koordinátái (3, 1)
Általános alak
- általánosan, a
y = a1 + b1x és y = a2 + b2x egyenesek az
xi = -(a1-a2) / (b1-b2)
yi = a1 + b1xi
pontban metsződnek
- ez a kifejezés azonban csak két, két ponton átmenő (végtelen hosszú) egyenes metszéspontját szolgáltatja
- még nem határoztuk meg, vajon a metszéspont az adott pontpárok között van-e, vagy pedig az egyik vagy mindkét egyenes képzetes meghosszabbításán
- az xi koordinátájú metszéspont akkor helyezkedik el x1 és x2 között, azaz akkor van rajta az első egyenesen, ha
(x1-xi) (xi-x2) >= 0
- hasonlóképpen, a metszéspont akkor van rajta az (u1, v1), (u2, v2) végpontokkal rendelkező egyenesszakaszon, ha
(u1-xi) (xi-u2) >= 0
- mivel bármelyik egyenes függőleges is lehet, amikor is x1=xi=x2, a fenti feltételeket meg kell vizsgálni az y koordinátákra is
Egyszerű program
32.1. melléklet - két egyenes metszéspontját számító egyszerű program
- a kiosztott lapokon egy kezdetleges program listája található, két egyenes szakasz metszéspontjának meghatározására
- az első egyenes koordinátáit x-szel és y-nal, a másodikét u-val és v-vel jelöljük
input x1,y1
input x2,y2
input u1,v1
input u2,v2
b1 = (y2-y1)/(x2-x1) (A)
b2 = (v2-v1)/(u2-u1) (B)
a1 = y1-b1*x1
a2 = v1-b2*u1
xi =-(a1-a2)/(b1-b2) (C)
yi = a1+b1*xi
if (x1-xi)*(xi-x2)>=0 AND
(u1-xi)*(xi-u2)>=0 AND
(y1-yi)*(yi-y2)>=0 AND
(v1-yi)*(yi-v2)>=0
then print "az egyenesek metszéspontja",xi,yi
else print "az egyenesek nem metsződnek"
end if
D. KÜLÖNLEGES ESETEK
- sajnos ez a program nem fog tudni megbirkózni bizonyos esetekkel:
Függőleges egyenesek
- ha az első egyenes függőleges, az (A)-val jelölt utasítás hibát fog okozni a zérussal osztás kísérlete következtében, mivel a numerikus processzor nem tud mit kezdeni a végtelennel
- hasonlóképpen, a kettes egyenes függőlegessége a (B)-vel jelzett hibát váltja ki
Párhuzamos egyenesek
- ha a két egyenes párhuzamos, a (C)-vel jelölt programsor fog hibát okozni
Megoldás
- a különleges esetek kezelése érdekében a programot kissé bonyolultabbá kell tennünk:
32.2. melléklet - Módosított metszéspont számító program
- ezek a speciális esetek sok egyszerű geometriai algoritmusban előfordulnak
- különböző módszerek segítségével bizonyos mértékig kezelhetőkké tehetők
E. KOMPLEX VONALAK
- vizsgáljunk meg két olyan összetett vonalat, melyek n1 illetve n2 számú egyenesdarabból állnak:
- az összes metszéspontot úgy számíthatjuk ki, ha a két egyenesdarab metszéspontjának meghatározására írt programot olyan ciklusba foglaljuk, amely megvizsgálja valamennyi első vonalbeli egyenes darab valamennyi második vonalbeli egyenes darabbal való metszéspontját
- az elvégzendő munka arányos a (n1 * n2) szorzattal
- az elvégzendő munka heurisztikus módszerrel csökkenthető
- bár a módszer alkalmazása újabb számítási lépés beillesztését igényli, a teljes számítási időnek csökkennie kell
- példák ilyen módszerekre:
A legkisebb befoglaló téglalap
- egy vonal legkisebb befoglaló téglalapját a vonal legkisebb és legnagyobb x és y koordinátái határozzák meg
32.1. ábra - Minimális befoglaló téglalapok
- a metszéspont keresése azzal indul, hogy megnézzük, vajon a két vonal befoglaló téglalapjai fedik-e egymást
- ha nincsenek fedésben, úgy a két vonal nem metszheti egymást
- ha fedésben vannak, akkor el kell készíteni mindkét vonal valamennyi szakaszára vonatkozóan a befoglaló téglalapot és megvizsgálni, van-e egyáltalán két olyan, más-más vonalhoz tartozó téglalap, mely fedésben van
Monoton szakaszok
- minden vonal felbontható olyan szakaszokra, melyek monoton nőnek vagy csökkennek x-ben és y-ban
- a monoton szakaszok olyanok, hogy:
- az x vagy az y tengellyel párhuzamos egyenes legfeljebb egyszer metszi a szakaszt
- van egy töréspontjuk, melyben x vagy y lokális maximumot vagy minimumot ér el
32.2. ábra - Monoton szakaszok
- ez olyan feltételeket teremt, melyek felhasználhatók a metszések keresésére fordított munka csökkentésére
- mivel a szakasz folyamatosan növekszik az egyik irányban, a tendencia nem fog megfordulni és a szakasz nem fogja ismét metszeni a másik vonalat
32.3. ábra - Monoton szakaszok metszése
- ezt a módszert használják az ARC/INFO és más gyártók GIS programjai
- a módszer alkalmazása esetén a két összetett vonal metszéspontjai számítására fordított gépidő olymértékben csökken, hogy az (n1 x n2) érték helyett az (n1 + n2) értékkel lesz arányos
A vonalak osztályozása
- ha sok vonal sok metszéspontját kell meghatározni, mint pl. két komplex fedvény egymásra fektetésénél (fedvényezésénél)
- osztályozni lehet a vonalakat végpontjaik koordináta tartományai szerint és csak a hasonló tartományba esőket kell figyelembe venni a metszéspontok számításánál
IRODALOM
Douglas, David H., 1974. "It makes me so cross," az előadást a Harvard Egyetem Tervezési Iskolájának
Számítógépes Grafika és Térbeli Elemzési Laboratóriuma terjesztette 1974-ben. (l. jelen jegyzék Marble, et al. 1984. kötetben újra megjelent)
Lee, D.T. és F.P. Preparata, 1984. "Computational Geometry: a survey," IEEE Transactions on
Computers C-33(12):1072-1101. Jó bevezetés a geometriai problémák alapvető algoritmusaihoz
Little, J.J. és T.K. Peucker, 1979. "A recursivee procedure for finding the intersection of two digital curves,"
Computer Graphics and Image Processing 10:159-71.
Marble, Duane F., Calkins, Hugh W. és Peuquet, Donna J.,eds. 1984. Basic Readings in Geographic
Information Systems, Williamsville N.Y., SPAD Systems Ltd.
Saalfeld, Alan, 1987. "It doesn't make me nearly as CROSS," International Journal of Geographical
Information Systems 1(4), pp 379-386
Taylor, George, 1989. "Letters," International Journal of Geographical Information Systems 3(20):192-3.
A vonal metszési problémája egy másik aspektusból
ELLENŐRZŐ KÉRDÉSEK
1. Miért olyan fontos a "metsző szakasz" vagy vonalmetszési probléma a GIS-ben?
2. Keresd meg azokat a szabályokat, amelyek felhasználhatók a feldolgozási idő csökkentésére, két x-ben és y-ban monoton vonal metszésének meghatározásakor. Mindegyik vonal a négy kombináció egyikét realizálja: nő vagy csökken x-ben, nő vagy csökken y-ban. Mivel két vonal kölcsönös helyzetét vizsgáljuk, ezért 16 kombinációra kell figyelemmel lennünk.
3. Ismertesd és vitasd meg a Little és Peucker, 1979-ben leírt vonalmetszési technikáját.
4. Hasonlítsd össze két vonal metszésének meghatározásánal a vektoros és a raszteres modellt. Léteznek-e olyan körülmények, melyek fennállása esetén a raszteres modell részesítendő előnyben?
5. Mivel a földrajzi adatok sohasem teljesen pontosak, az algoritmusban figyelembe vett különleges esetek sem realizálódnak szabatosan. Módosítsd a különleges esetekre vonatkozó algoritmusokat olymódon, hogy kezelni tudják a nem szabatos adatokat. Melyek az előnyei és lehetséges problémái ennek a megközelítésnek?
|
