Dr. Sárközy Ferenc: Térinformatika
Ebben a részben a vektoros adatokkal végezhető számítások
közül megismerkedünk:
- a síkbeli transzformációkkal,
- a távolság fogalmakkal,
- az egyenes szakaszok metszéspontjainak megkeresésével,
- a hossz-, terület-, kerület-, súlypont számításokkal,
- a pont a poligonban algoritmussal.
A térbeli objektumok helyzetét úgy tudjuk a legkényelmesebben
figyelembe venni, ha valamilyen, derékszögű vagy görbe vonalú, alapnak
elfogadott, koordináta rendszerben rögzítjük jellemző pontjaik
koordinátáit. Az alapként elfogadott koordináta rendszerekről, az úgy nevezett referencia rendszerekről, még részletesen szólunk. Egyelőre
elég annyit figyelembe vennünk, hogy bár e rendszereket csak két csoportra
osztják abszolút és relatív (a Föld olyan fizikai tulajdonságaival
meghatározott mint a tömegközéppont és a forgástengely, illetve önkényesen a Földhöz
rögzített), mégis mindkét csoportnak a gyakorlatban sokféle realizálását
használják. Ezek a koordináta rendszerek térbeliek. A gyakorlati térképezés
igényeiből kiindulva azonban ma még az esetek túlnyomó többségében nem a pontok
térbeli koordinátáit használják, hanem azok vetületeit valamely célszerűen
felvett síkra vagy síkba fejthető felületre (henger, kúp). E vetületekből
gyakorlatilag végtelen sokkal találkozunk. Ha a vetítés során a harmadik
komponenst a magasságot is meghatározzuk úgy azt a térinformatikai rendszerek
szinte kizárólag mint attributív adatot kezelik. Ha ezen kívül még arra is
gondolunk, hogy a különböző referencia rendszerekből különböző módszerekkel
különböző elhelyezkedésű síkokra vetített térképek elvileg végtelen sok
méretarányban készülhetnek, úgy feltehetőleg igazolt az az elképzelésünk, hogy a transzformációknak sulyponti szerepük van a térinformatikai
rendszerek alapműveletei között.
Meg kell még indokolnunk, hogy miért foglalkozunk e helyen
csak a síkbeli transzformációkkal. Ennek legfőbb oka, amint már utaltunk rá,
hogy a kereskedelmi GIS és LIS rendszerek tulajdonképpen kétdimenziós
rendszerek, bár egyesek közülük a magasságok felhasználásával térbeli
ábrázolásra is alkalmasak. A 3D-s megjelenítéshez tartozó transzformációkról a
vizualizálási műveletekkel kapcsolatban fogunk szólni. A valódi térbeli
transzformációkról pedig a referencia rendszerrel és a fotogrammetriai és GPS
adatnyeréssel kapcsolatban közlünk rövid összefoglalást. Didaktikai szempontból
is szerencsésnek tartjuk, hogy egy nem matematikai könyvben az egzaktabb
fogalmak bevezetését egyszerűbb formájukban végezzük.
A sík transzformáció legegyszerűbb esete ha pontjainkat olyan
koordináta rendszerbe akarjuk átszámítani, mely kezdőpontja nem esik egybe az
eredeti koordináta rendszer kezdőpontjával, X tengelye pedig szöget zár
be az eredeti koordináta rendszer X tengelyével (2.38 ábra).
|
2.38 ábra -
eltolás és elforgatás a síkban
|
Az átszámított
koordináták az új rendszerben:
|
ha
és
akkor:
|
A második
koordinátarendszer kezdőpontjának első rendszerbeli koordinátái:
|
|
|
A transzformációs paraméterek tehát kiszámíthatóak, ha
ismerjük két pont koordinátáit mind a két rendszerben. A
valóságban azonban a két rendszer között rendszerint méretarány különbség is
van gondoljunk csak arra, hogy a helyi vízszintes ipartelepi geodéziai
hálózatokat nem redukálják a tengerszintre és gyakran vetületi korrekciókkal
sem látják el ez pedig azt eredményezi, hogy a két hálózatban a méter más és
más fizikai hossznak felel meg. A két pont (P1, P2 ) két
rendszerbeli koordinátáiból (xP1,yP 1 , xP2,yP 2 ), (xP1,yP 1 , xP2,yP 2 ) a méretarány tényezőt egyszerűen
kiszámíthatjuk hisz
azaz m a két pont kétféle koordinátarendszerben
kiszámítható távolságának hányadosával egyenlő. Érdemes megjegyezni, hogy a
számlálóba az a koordináta rendszer kerül (esetünkben a dültbetűs), amelybe az
átszámítást végezzük.
A gyakorlatban a transzformáció végrehajtásához kettőnél több mindkét rendszerben ismert koordinátájú pont
koordinátáit vesszük igénybe. Ezt a feladatot HELMERT féle
hasonlósági transzformációnak hívják. A transzformációt azért nevezik
hasonlóságinak, mivel nem változtatja meg a transzformált pontok által képzett
idomok alakját. A feladat legkisebb négyzetek módszere szerinti
megoldása az alábbi egyszerű képletekre vezethető vissza.
Legyen:
akkor a keresett síkkoordináták a második
rendszerben:
.
Különösen fényképeken ábrázolt
objektumok reális alakjának helyreállítására gyakran alkalmaznak affin
transzformációt. Ennél a transzformációnál hat különböző paraméter
figyelembevételére van szükség, azaz legalább három pont mindkét
rendszerbeli koordinátáit kell ismernünk a paraméterek meghatározásához.
Korábbi jelöléseinket megtartva (az
ismeretlen együtthatókat kis dűlt betűkkel jelölve) a transzformációs
egyenletek az alábbiak:
Affin transzformációt eredményez az a speciális
eset is amikor a két koordináta tengely irányában különböző méretarány tényezőt
indokolt alkalmazni. Ilyen eset állhat elő akkor, ha a térképlapok helytelen
tárolása következtében a két főirányban különböző zsugorodások jönnek létre.
Szinte valamennyi kereskedelmi GIS szoftver ismeri az u.n. gumilepedő
transzformációt. A transzformációt szakszerűbben polinomos
transzformációnak nevezhetjük, mivel a két koordináta rendszer között két
n-edfokú polinom teremti meg a kapcsolatot az alábbiak szerint:
A polinomok együtthatóinak
meghatározásához esetünkben tíz pont mindkét rendszerbeli koordinátáit
kell ismerni. A gyakorlatban rendszerint megelégednek a másodfokú közelítéssel,
harmadfokúnál magasabb fokszámú polinomot pedig szinte soha sem használnak,
ugyanis azt tapasztalták, hogy a magasabb fokszámú polinomok, bár figyelembe
veszik a helyi torzulásokat, a két koordináta rendszer globális
elhelyezkedésére nem nyújtanak megnyugtatóbb választ.
A síkbeli (és térbeli) transzformációk iránt érdeklődő
olvasóinknak ajánljuk Wolf [11] és Detrekői
[12] kiegyenlítő számításokat tárgyaló összefoglaló munkáit.
Bár a transzformáció lényegén mit sem változtat, hogy mire
használjuk, a gyakorlat mégis úgy hozta, hogy a geodéziai transzformációk
eszköztárukban is különböznek a számítógépes
grafika által használt transzformációs módszerektől. Ez a
jelenség mindenek előtt azzal magyarázható hogy a geodéziában a pontok
rögzítettek és a koordináta rendszereket transzformálják, tehát azok
tolódnak el, forognak és zsugorodnak. A kompjuter grafikában fordított a
helyzet: a rögzített képernyő koordináta rendszerhez képest a pontok
mozognak és e mozgásoknak megfelelő új helyet jellemző koordináták a
transzformáció eredményei. Ez a különbség megfelelő előjel konvenciókkal ugyan
a korábbi módszerekkel is figyelembe vehető lenne, mégis érthető az új
módszerek megjelenése, ha arra gondolunk, hogy a kompjuter grafikában a
szemléletesség érdekében nagy tömegben végzik a transzformációkat, s ezek
megfogalmazását igyekeznek maximálisan leegyszerűsíteni, másrészt ezek a
módszerek csak a közelmúltban alakultak ki, s a hosszabb időre visszatekintő
geodéziai és fotogrammetriai transzformációk, kialakulásuk idején, még nem
használhatták őket.
A transzformációk leegyszerűsítését
a homogén koordináták bevezetése tette lehetővé. E koordináták
bevezetésével minden transzformáció önálló matematikai egységként kezelhető, s
egyben biztosítható az egymás után következő transzformációk összekapcsolása (konkatenálása).
A módszer lényege, hogy
a síkbeli pontokat két koordináta helyett három koordinátával azonosítjuk, azaz
valamely P pont [x, y] koordináta párosa helyett a [xk, yk, w]
koordináta hármast használjuk. Az eredeti koordináták a homogén koordinátákból
az alábbi egyszerű kifejezésekből számíthatók:
.
Matematikailag a homogén koordináták alkalmazása
azt jelenti, hogy az n dimenziós térből áttérünk az n+1 dimenziós térbe,
ahol az n dimenziós pontok úgy tekinthetők mint az n+1 dimenziós
tér alterei.
A leképezés az n dimenziós térből az n+1
dimenziós térbe többértékű, azaz az n dimenziós térbeli alakzat végtelen
sok formulával adható meg az n+1 dimenziós térben. E leképezés inverze a
projekció, ez az n+1 dimenziós tér pontjait képezi le az n
dimenziós térbe.
Ha a gyakorlati oldalról próbáljuk megközelíteni a kérdést,
úgy egyszerűen azt mondhatjuk, hogy a homogén koordináták bevezetése a mátrix algebra szabályai
alapján lehetővé teszi, hogy minden transzformáció az eredeti homogén
koordinátákból álló vektor és egy transzformációs mátrix szorzataként álljon
elő (azaz a homogén koordináták az eredeti koordináták egy
olyan azonos átalakításának eredményei, melyek ezt az egyszerű transzformációs
műveleti szabályt lehetővé teszik).
Általános esetben a transzformációt a következő kifejezéssel
írhatjuk le:
.
Ha a 3x3-as transzformációs mátrixot a továbbiakban Mi-vel jelöljük, ahol i
a transzformáció milyenségére utaló index (i=e - eltolás, i=s -
skálázás, i=r - forgatás), úgy az egyes rész transzformációkra a
következő kifejezéseket kapjuk:
eltolás
esetén
|
|
eredménye:
|
|
skálázás
(méretarány változtatás) esetén
|
|
eredménye pedig:
|
|
|
Szeretnénk a szövegben is felhívni arra a figyelmet, hogy
matematikai koordináta rendszerben dolgozunk azaz a 2.38 ábrán látható
geodéziai koordináta rendszer X és Y koordináta tengelyei helyet cserélnek, és
nem a koordináta tengely forog a ponthoz képest, hanem fordítva.
Az a tény, hogy w értéke az eddigi transzformációk során nem
változott azt jelenti, hogy a transzformáció eredménye az eredeti altérben
marad. A gyakorlatban w = 1 értékkel szokták a számításokat végezni. Ha mi is
elfogadjuk ezt az egyszerűsítő konvenciót, és azt az általános esetet keressük,
amely eltolás, skálázás és forgatás együttes alkalmazásával mozgatja a pontot,
akkor az eredő transzformációs mátrixot a komponens mátrixok összeszorzásával
nyerjük az alábbiak szerint:
.
A transzformált pontkoordináta vektor pedig mint a
transzponált transzformációs mátrix és az eredeti koordináta vektor szorzata
nyerhető:
Az ismertetett síkbeli transzformációk állandó velejárói az
összetettebb GIS műveletek végrehajtásának. Ugyanezen műveletek térbeli
megfelelői viszont sokkal kevesebb térinformatikai szoftverben kerülnek
alkalmazásra. Ezért tartjuk indokoltnak, hogy a térbeli transzformációkkal csak
azután foglalkozzunk miután megismerkedtünk a 3 és 2.5 dimenziós adatmodell
fogalmával, mely modellekben összefoglalt adatok manipulálására és
megjelenítésére ezek a transzformációk felhasználhatók.
Vektoros adatmodell alkalmazása esetén megszokott
szemléletünkhöz legközelebb az Euklides-i távolság fogalom áll, mely két, egy
síkban fekvő pont távolságát a Pythagoras tétel
segítségével definiálja:
azaz a két pont közötti távolság a két pontot összekötő
egyenes hosszával egyenlő.
Számunkra szokatlan, de a térinformatikában gyakran használt
távolság fogalom u.n. Manhattan vagy háztömb távolság,
mely meghatározás szerint
a
azaz a háztömb távolság nem más, mint a két pont
koordinátakülönbségei abszolút értékeinek összege. E távolság fogalom
keletkezésével (amint elnevezése is mutatja) az amerikai városok derékszögű
utcahálózatához kötődik, hisz reálisabban tükrözi az Euklides-i távolságnál a
két különböző utcán található pont közötti valódi távolságot. Különösen
használatos e fogalom a raszter grafikában, ahol két pixel közötti diszkrét
távolság, pixelekben kifejezve, másképpen nem is adható meg.
Az egyenes darabok metszéspontjainak meghatározása szinte
valamennyi FIR művelet alapját képezi vektoros adatmodell esetén, ezért a
feladat egyszerű volta ellenére is megérdemli, hogy röviden összefoglaljuk. A
térinformatikai feladatokban az egyenesek általában végpontjaikkal kerülnek
megadásra. Ha az első egyenes kezdő illetve végpontjának koordinátái (x1, y1), (x2, y2), a másodiké
pedig (u1, v1), (u2, v2), akkor a két egyenes iránytangenseire, tisztatagjaira és
metszéspontjaira a következő értékeket kapjuk:
A jobboldali kifejezés azonban csak a két - két pont által
meghatározott végtelen hosszú egyenesek metszéspontját szolgáltatja, mely nem
feltétlenül van rajta a figyelembe veendő szakaszokon. Azt, hogy a pont valóban
rajta van e az első egyenes szakaszon a
feltétel teljesülése tanúsítja. Hasonlóképpen, a
feltétel teljesülése arról tanúskodik, hogy a metszéspont a
második egyenes szakaszon is rajta van. Mivel bármelyik egyenes függőleges is
lehet, amikor is x1=x2=xi vagy u1=u2=ui a feltételeket az y koordinátákra is meg kell vizsgálni.
A fenti képletek programozásakor figyelembe kell venni, hogy
ha valamelyik egyenes függőleges az iránytangens egyenletek egyike a zérussal
való osztás következtében hibát jelez. Hasonló hiba jelentkezik párhuzamos
egyenesek esetén az xi számításakor.
E hibák megkerülhetők, ha függőleges egyenes esetén (x1=x2 , vagy u1=u2 ) a
metszéspont koordinátáját egyenlővé tesszük a függőleges egyenes x
koordinátájával (xi=x1 , vagy xi=u1), és ezt az értéket a nem függőleges egyenes egyenletébe
behelyettesítve nyerjük a metszéspont y koordinátáját. Párhuzamos
egyenesek esetén azaz, ha b1=b2 véges
metszéspont hiányában a programot leállítjuk.
A térinformatikai feladatokban rendszerint nem két izolált
egyenes metszéspontjára van szükségünk, hanem egyenes szakaszokból álló vonalak
metszéspontjait keressük. Ezek a vonalak gyakran zártak, az így létrejövő zárt
sokszögeket a térinformatikai irodalom az angol szaknyelvből átvéve
poligonoknak nevezi. A térinformatikai szoftver funkciók kapcsán bemutatandó fedvényezési művelet nagytömegű metszéspont számítást
igényel összetett vonalak illetve poligonok között. Ezért indokolt röviden
megnézni, hogy miként alkalmazhatók a metszési képletek sok egyenes szakaszból
álló összetett vonalak metszéspont számításaikor.
Az egyszerűség kedvéért tételezzük fel, hogy két összetett
vonalunk van, az egyik n1, a másik n2 egyenes szakaszból áll. Ha mechanikusan alkalmazzuk erre az esetre a
két egyenes szakasz metszéspont meghatározására ismertetett összefüggéseinket,
úgy csak annyit kell tennünk, hogy két ciklusba foglaljuk a képleteket, a külső
ciklus pld. az első vonal szakaszai szerint változhat, míg a belső ciklus a
második vonal szakaszai szerint. Az így felépített program sorra veszi az első
vonal szakaszait, tehát először az első szakaszt, és megnézi ennek a szakasznak
a metszéseit a második vonal összes szakaszával. Az igy kialakított program műveletigénye
tehát arányos az n1*n2 szorzattal (a számítástechnikai irodalom ezt a tényt az o(n1*n2 )kifejezéssel
jelöli).
Mivel, amint már említettük, a gyakorlati feladatokban a
számítandó metszések száma igen nagy, ezért a használhatóság érdekében a térinformatikai
szoftverek különböző trükköket alkalmaznak az elvégzendő számítások
csökkentésére. Bár e trükkök alkalmazása újabb műveletek beiktatását igényli a
programba, alkalmazásukkal elérhető, hogy a műveletigény nagyságrendje
megközelítse az o(n1+n2) értéket.
E trükkök közül talán legszemléletesebb a befoglaló téglalapok
módszere. Mindkét összetett vonalat egy egy téglalappal veszünk körül, melyek
sarokponti koordinátái (x1min, y1min ), (x1min, y1max), (x1max, y1max ), (x1max, y1min), illetve (x2min, y2min), (x2min, y2max), (x2max, y2max), (x2max, y2min), és megvizsgáljuk,
hogy a két befoglaló téglalap fedi-e egymást. A vizsgálat igen egyszerűen négy
egyenlőtlenség kiértékelését igényli:
|
2.39 ábra - a
befoglaló téglalpok módszere
|
Ellenkező
esetben a két vonalnak nincs metszéspontja. Ha a két téglalap fedésben van,
úgy el kell készíteni mindkét vonal valamennyi szakaszának befoglaló
téglalapjait, és a fönti eljárással ki kell választani azokat, melyek fedik
egymást. A metszések számításába csak a kérdéses vonalszakaszokat kell
bevonni.
|
|
(a 2. téglalap az 1. téglalap fölött van)
|
|
(a 2. téglalap az 1. téglalap alatt van)
|
|
(a 2. téglalap az 1. téglalaptól jobbra
van)
|
|
(a 2. téglalap az 1. téglalaptól balra
van)
|
Ha a fenti egyenlőtlenségek közül
valamelyik nem teljesül, úgy a két téglalap fedésben van, tehát valószínű,
hogy a két összetett vonalnak van(nak) metszéspontja(i).
|
|
|
A metszéspont keresésre fordított gépidő jelentősen
csökkenthető az összetett vonalak monoton szakaszokra bontásával is.
|
2.40 ábra - a
monoton szakaszokra bontás módszere
|
Ezután már csak azt kell megkeresni, hogy a két monoton szakasz melyik
két összetevő egyenes darabja metsződik. Elvileg alkalmazhatnánk az általános
algoritmust (az első vonal minden egyes szakaszának metszését a második vonal
minden egyes szakaszával) azzal a különbséggel, hogy az első metszéspont
megtalálása után (mivel több nem lehet) leállítjuk a keresést. Tovább
csökkenthető a számítási munka, ha a megfelelő monoton szakaszokat x
szerinti intevallumokba rendezzük, és összehasonlítjuk a két görbe azonos x
intevallumaihoz tartozó átlagos y értékeket. Ahhoz az
intervallumhoz tartozó egyenesszakaszok metszés számításait kell csak
elvégezni, melynél a két görbe átlagos y értéke közel megegyezik.
|
A monotonitás azt
jelenti, hogy x monoton növekedésével az adott vonalszakaszon y
monoton növekszik vagy csökken. A monoton szakaszokat az x vagy y
tengellyel párhuzamos egyenesek csak egyszer metszik. Ha két monoton szakasz
közül az egyik y-ban növekvő, a másik peddig csökkenő, és van már egy
metszéspontjuk, úgy több metszéspontjuk már nincs.
|
Vektoros adatmodellben a vonalak hosszát a vonalszakaszok
hosszainak összegzésével nyerik. A vonalszakaszok hosszát végpontjaik
koordinátáiból a Pythagoras képlet felhasználásával
számítják. Hasonlóképpen határozható meg a poligonok kerülete is annak
figyelembevételével, hogy a kezdőpont koordinátái kétszer is szerepelnek a
számításokban, mind az első, mind az utolsó egyenes szakasz hosszának meghatározásánál.
A térinformatikai szoftverek egyik leggyakrabban alkalmazott
számítása a poligonok területének meghatározása. A számításhoz azt a
geodéziában jól ismert algoritmust használják, mely a területet trapézok
összegéből számítja.
|
2.41 ábra -
poligon területszámítása
|
Ha a töréspontok számozása az óramutató
járásával ellentétes, a területet negatív előjellel kapjuk. Mivel az y
koordinátákból a középvonalak magasságát számítjuk, az algoritmus nem működik
negatív ordináták esetén. Ebben az esetben két választásunk van: vagy az y
tengelyre végezzük a vetítést, azaz a képletben az x-eket és y-okat
felcseréljük (csak akkor alkalmazható eljárás, ha az x-ek pozitívok),
vagy megfelelően nagy számmal megnöveljük az y értékeket, hogy
eredményül pozitiv számokat kapjunk
|
Bocsájtsunk a poligon minden
töréspontjából függőlegest az X tengelyre. Minden egyenes szakasz, a két
végpontját levetítő egyenesekkel valamint az X tengely kimetszett részével
egy egy trapézt alkot. Az i.-ik trapéz területe az alábbi képletből
számítható:
|
|
Ha a poligon valamennyi oldalára
elvégezzük a számítást és az eredményt összegezzük, úgy megkapjuk a poligon
területét. Ez az egyesek számára talán váratlan eredmény abból adódik, hogy
az alsó trapézok területe levonódik az összegből, mivel az óramutató járásával
megegyező pontszámozás esetén, az (x(i+1) - x(i)) érték
negatív. A poligon (zárt sokszög) területe tehát
|
|
A képlet használatakor figyelemmel kell
lenni arra, hogy a poligon zártságából következően a kezdő és végpont
koordinátái megegyeznek: (x(n+1), y(n+1))=(x(i), y(i)).
Az algoritmus tetszőleges alakú poligonra használható egy
kivétellel: nem tudja kezelni azokat az eseteket amikor a poligon oldalak
metsződnek (nyolcas alakot vesznek fel). Ebben az esetben ki kell számítani
az oldalak metszéspontját, és ennek felhasználásával a poligont két
poligonra kell bontani.
.
|
|
A gyakorlati feladatok során a poligonok általában
folyamatosan boritják a felszínt (gondoljunk egy földmérési alaptérkép
földrészleteire), és valamennyi poligon (földrészlet) területére szükség van.
Ilyenkor célszerű az összes területet egyszerre számolni.
A program minden poligon számára létrehoz egy összegzőt és a
poligon oldalakhoz számított területet a megfelelő poligon összegzőjében
akkumulálja. A probléma azokkal az oldalakkal van, melyek egyidejűleg két
poligonhoz is tartoznak. Ezeket a területeket ugyanis mind a két poligon
összegzőjéhez hozzá kell adni, csak különböző előjellel. Ha továbbra is az
óramutató járásának megfelelő haladási értelemmel számolunk, akkor a baloldali
poligonok számára a részösszeg eredeti előjelével ellentétes, míg a jobboldali
poligonok összegzői a részösszegeket előjelhelyesen kapják.
A térinformatikában gyakran használnak a terület típusú
objektumok reprezentálására pontokat, bizonyos esetekben pld. a magyar geokód előírások figyelembevételekor a vonal típusú
objektumok is képviselhetők ponttal. Bár a magyar előírások e pontok
elhelyezésére többé kevésbé önkényesek (csak az a megkötés, hogy az objektum
határvonalán vagy azon belül helyezkedjenek el), a szakmai igény megkívánja,
hogy a képviselő pontok olyan egyértelmű és ismételhető szabálysorozat
eredményeképpen kerüljenek meghatározásra, mely elhelyezkedésileg a lehető
legjobban helyettesíti a képviselt objektumot. A terület tipusú objektumok
ilyen helyettesítő pontjait centroidoknak hívjuk. Mivel a vonalas
objektumok ponttal való helyettesítése a gyakorlatban kevéssé járható út, ezért
a centroid fogalmát nem kívánjuk ezekre az objektumokra kiterjeszteni.
Megjegyezzük ugyanakkor, hogy az azonosítást szolgáló pontok egyértelmű,
szabályokkal leírt meghatározása ezeknél az objektumoknál is indokolt.
Terület típusú objektumok pontszerű helyettesítésére
legalkalmasabb geometriai fogalom a súlypont. A súlyponti koordináták,
meghatározás szerint az alábbi kifejezésekből nyerhetők:
,
ahol (xs, ys) - a súlypont
koordinátái, T - a síkidom területe, dT - infenitezimálisan kicsiny elemi
terület, (x, y) az elemi terület sarokponti koordinátái. Az
integrál jel alatti T azt jelképezi, hogy az integrálást az egész területre végre kell
hajtani.
Poligonok esetében az általános képlet felhasználásával
levezethető, hogy a súlyponti koordináták a poligon törésponti koordinátáinak
és területének felhasználásával az alábbi kifejezésekből számíthatók:
|
|
Sajnos, amint ezt a 2.42 ábra is
illusztrálja, konkáv poligonok esetén a súlypont az objektumon kívülre is
eshet. Mivel egy objektumon kívüli pont nem játszhatja el a centroidtól
elvárt funkciókat, ilyen esetben célszerű egyértelmű szabályt alkotni a súlypont
objektumra történő visszavetítésére. A legegyszerűbb egyértelmű szabálynak
az tűnik, ha a vetítés a legrövidebb távolság mentén történik a területi
objektumra. A kérdéses centroid pont megkeresése érdekében kiszámítjuk a
súlypont és a poligon töréspontok távolságait és kiválsztjuk közülük a
legrövidebbet.
|
|
|
2.42 ábra -
konkáv síkidom súlypontja az idomon kívül helyezkedik el
|
|
A centroid három helyzetet foglalhat el: vagy a súlypontból a
kérdéses töréspontot megelőző oldalra bocsátott merőleges talppontjával lesz
azonos, vagy a követő oldalra bocsátott merőleges talppontjával, vagy magával a
törésponttal. Szimmetrikus területek esetén előfordulhat az a speciális eset,
hogy a megelőző és követő oldalra bocsátott normálisok azonos hosszúságúak.
Ebben az esetben, az egyértelműség biztosítása érdekében, a kisebb irányszögű
normálist választjuk vetítősugárnak.
Legyen ds-r=min{ds,i}; i=1,
2, . . .n, akkor az r töréspontot megelőző oldal egyenlete
,
a súlypontból a megelőző oldalra bocsájtott merőlegesé pedig
.
Ezután a metszési kifejezés felhasználásával
kiszámítjuk a talppont (xt-1, yt-1) koordinátáit, a tartalmazási egyenlőtlenséggel pedig megvizsgáljuk, hogy rajta
van-e az (r-1)-(r) egyenes szakaszon. A feltétel teljesülése
esetén a súlyponti és talpponti koordinátákból Pythagoras
képletével távolságot számolunk. Az eljárást megismételjük az (r)-(r+1)
szakaszra is. Attól függően, hogy a talppontok a szakaszon belülre vagy kívülre
esnek, maximum három, minimum egy távolságot kapunk. A legrövidebb távolsághoz
tartozó végpont (valamelyik talppont, vagy az (r) töréspont) lesz az
objektumot reprezentáló centroid.
A feladat mind egyes pontok, mind pontcsoportok vonatkozásában
igen gyakran előfordul. Ha egyszerű példát akarunk mutatni erre a két esetre
elég ha csak arra gondolunk, hogy minden pontszerű objektum valamilyen terület típusú
objektumon belül helyezkedik el. Ha például arra vagyunk kíváncsiak, hogy egy
forrás milyen földrészleten található, úgy ezt az algoritmust kell
alkalmaznunk. De ezt az algoritmust igényli annak a kérdésnek a megválaszolása
is, hogy hány centroiddal reprezentált épület található pld. a VI. kerületben.
Az algoritmus alapgondolatát
már ismertettük, konverzió céljaira történő
felhasználásával is foglalkoztunk. Most csak néhány olyan momentumra hívjuk
fel a figyelmet, mely elősegíti az algoritmus gyakorlati realizálását. Az
implementálás során annyiban módosítottuk a korrekten megfogalmazott
algoritmust, hogy mivel a zérust nem tekintjük páratlan számnak, akkor van a
pont a poligonban, ha a belőle kiinduló félegyenesnek páratlan számú metszéspontja
van a poligont alkotó egyenes szakaszokkal, minden más esetben a pont a
poligonon kívül van (azaz eltekintettünk a metszéspontok eggyel való
megnövelésétől és az ebből fakadó paritáscserétől).
Húzzunk egy függőleges egyenest a pontból, keressük meg a
metszéspontját a poligont alkotó egyenes szakaszokkal. Azért, hogy ne kelljen
minden egyenessel kiszámítani a metszéspontot majd utána megnézni, hogy az a
szakaszon belül vagy kívül van-e, már a metszéspont keresése előtt kirostáljuk
a metszésre esélytelen vonalszakasz jelölteket az alábbiak szerint:
Legyenek a vizsgált pont koordinátái (u,v), az egyenes szakaszok kezdő
és végponti koordinátáinak indexei pedig (i) és (i+1), a
függőleges egyenesen x=u. Mivel a függőleges vonalszakaszok nem
metsződnek a végesben a függőleges egyenesekkel, a vizsgálatot csak azokra a
szakaszokra végezzük el melyekre igaz, hogy
x(i+1)<>x(i). A perspektív vonalszakaszok
kiválasztását a [x(i+1)-u]*[u-x(i)]>=0 feltétel érvényesítése teszi lehetővé,
ez ugyanis azt fejezi ki, hogy a vizsgált szakasz két végpontja a pont
függőlegesétől jobbra illetve balra (esetleg az egyik végpont magán a
függőlegesen) helyezkedik el.
Abban az esetben, ha a metszéspont x koordinátája
egybeesik a vonalszakasz kezdő vagy végpontjával (a kezdő vagy végpont a
vizsgált pont függőlegesében van) a metszéspont számlálás hibázhat. Ezt
elkerülendő, két olyan feltételt iktatunk a programba, melyek azt biztosítják,
hogy ha a metszéspont x(i)-el esik egybe, úgy a program csak
akkor számol metszéspontot, ha az (i+1)-es pont a függőlegestől jobbra
esik, ha pedig x(i+1) esik a pont függőlegesére, úgy a számlálás feltétele, hogy az (i).-ik
pont a függőlegestől balra helyezkedjen el.
A metszéspont y koordinátáját megkapjuk, ha a
kiválasztott egyenes szakasz egyenletébe behelyettesítjük az x=u
értéket. Ha a metszéspont y koordinátája nagyobb mint v (a
vizsgált pont y koordinátája), úgy a metszéspont a vizsgált pont fölött
van, a számláló tartalmához hozzáadódik az egység és a vizsgálat mindaddig
folytatódik, amíg a poligon összes oldala sorra nem kerül (legalább annak
eldöntésére, hogy perspektív-e vagy sem).
A fentiekben vázolt program nem intézkedik külön arra az
esetre, ha a vizsgált pont rajta van a poligon kerületén. Ez az eset egyszerűen
figyelembe vehető azzal, hogy a számlálót akkor is beindítjuk, ha a metszéspont
y koordinátája egyenlő v-el.
A gyakorlati esetekben több pont több poligonon belüli
elhelyezkedését kell vizsgálni. A poligonok ezekben az esetekben, a topológiai
adatmodell szerint, ívekben kerülnek tárolásra (két csomópont közötti egyenes szakaszok
sorozata alkotja az ívet). Minden ív egyidejűleg két poligonhoz is tartozik.
Mivel az ívek irányítottak, az érintett poligonokra baloldali és jobboldali
jelzővel szokás hivatkozni.
Minden pontból kiindulva függőlegeseket húzunk és
meghatározzuk a metszéspontok y koordinátáit. A kapott y értékeket
együtt tároljuk a kérdéses ív alatti poligon nevével (Nyugatról-Keletre
irányított poligonok esetén a jobboldali poligonéval). Valamennyi ív vizsgálata
után meg kell keresni a legalsó metszéspontot és a hozzátartozó poligon nevét.
Ez lesz az a poligon, amely a pontot tartalmazza. Az eljárást minden pontra
elvégezve, megkapjuk minden pont tartalmazó poligonját. Az algoritmus igényli,
hogy minden pontról minden ív vizsgálatra kerüljön. A vizsgálatok száma
csökkenthető, ha az íveket előzetesen maximális és minimális x
koordinátáiknak megfelelő csoportokba rendezzük, és az egyes pontokból csak
azokat az íveket vizsgáljuk, melyek x szerinti intervalluma tartalmazza
a figyelembe vett pont x értékét. Ezeken kívüli, y szerinti
rendezésekkel tovább csökkenthető a megvizsgálandó ívek száma.
Megjegyzéseit
E-mail-en várja a szerző: Dr Sárközy Ferenc