|
33. Fejezet - EGYSZERŰ ALGORITMUSOK II - POLIGONOK
Magyar változat: Sárközy Ferenc, Budapesti Műszaki Egyetem
A. BEVEZETÉS
B. POLIGON TERÜLET
Célkitűzés
Módszer
Problémák
Több poligon területének egyidejű számítása
C. PONT A POLIGONBAN ALGORITMUS
Célkitűzés
Általánosítás
Stratégia
Minta program
Különleges esetek
Bizonytalan határok
Sok pont sok poligonban
D. A CENTROID HELYZETE
Módszer
E. VÁZ
Alkalmazások
IRODALOM
ELLENŐRZŐ KÉRDÉSEK
MEGJEGYZÉSEK
33. Fejezet - EGYSZERŰ ALGORITMUSOK II - POLIGONOK
Magyar változat: Sárközy Ferenc, Budapesti Műszaki Egyetem
A. BEVEZETÉS
- az előző fejezet két vonal metszéspontjának meghatározására szolgáló egyszerű algoritmust ismertetett
- a jelen fejezet egy második egyszerű algoritmust és néhány kiterjesztést tekint át
B. POLIGON TERÜLET
Célkitűzés
- keresd meg egy töréspontjaival adott poligon (zárt sokszögvonal) területét
Módszer
- közismert módszer annak az algoritmusnak a használata, amely megadja azon szomszédos trapézok területösszegét, melyeket az alábbi vonalak határolnak:
- egy vonalszakasz
- az x tengelyig lehúzott függőleges vonalak
- az x tengely
33.1. ábra - Trapéz területszámítás
1. Bocsáss le az x tengelyig tartó függőlegeseket két szomszédos töréspontból
- számítsd ki a trapéz területét, amely a meghatározás szerint
A = (x2-x1) * (y2+y1) / 2
- azaz a terület az x-ek különbségének szorzata az y-ok átlagával
2. Folytatva a poligon minden oldalára, határozd meg valamennyi oldal által határolt trapéz területét
3. Összegezd az összes trapéz területét, hogy megkaphasd a poligon által határolt területet:
- megjegyzés: zárt sokszögről lévén szó (xn+1,yn+1) = (x1,y1)
A = S
[(xi+1-xi) * (yi+1+yi) / 2 ]
- ha xi+1 < xi , akkor a részösszeg negatív
- ennek köszönhetően az alsó trapézok kivonódnak a területösszegből és végeredményben A magának a poligonnak a területét szolgáltatja
Problémák
- az algoritmus jól működik akkor is, ha a poligonnak be-, vagy kitüremkedései vannak
- nem működik viszont, ha a poligonoldalak metszik egymást (pl. 8-as alakú)
- ha a poligon az óramutató járásával ellentétes értelemben van digitalizálva, úgy a terület negatívnak adódik
- problémát okoz, ha a poligon y értékei negatívok
- nem lehet a pontokat "le"vetíteni az x tengelyre
- megoldások:
- adj hozzá egy megfelelően nagy számot minden y-hoz
- a legalacsonyabb y alatti x-szel párhuzamos tengelyre történjen a levetítés
- olyan vetületi rendszerekben is, melyek sokszámjegyű koordináta értékeket szolgáltatnak a számítógép kerekítési hibáinak eredményeként, a pontosság csökken
- kis poligonoknál kis koordináta értékekkel érdemes dolgozni
- megoldás
- ideiglenesen el kell tolni a koordináta-rendszer kezdőpontját olymódon, hogy közel kerüljön a töréspontokhoz
- ez csökkenti a koordináta értékeket
Több poligon területének egyidejű kiszámítása
- ha a poligon oldalak egyidejűleg egy jobboldali J és egy baloldali B poligont is határolnak
- elvégezhetők valamennyi oldal számára a trapézszámítások
- minden poligonra vonatkozóan megnyitásra kerül egy folyamatos összegző
- a B poligonok számára a részösszeg negatív
- a J poligonok számára a részösszeg pozitív
- valamennyi oldal feldolgozása után megkapjuk valamennyi poligon területét
- a "külvilág" területe egyenlő lesz a poligonok összterületével, negatív előjellel véve
C. PONT A POLIGONBAN ALGORITMUS
Célkitűzés
- azt kell meghatározni, hogy egy adott pont egy adott poligonon belül vagy kívül helyezkedik-e el
Általánosítás
- keresd meg, hogy egy poligoncsoportból melyik tartalmazza egy pontcsoport valamennyi egyedét
- példák
- a megyehatárokat tartalmazó file ismerétében határozd meg, hogy melyik megyében található, a fogyasztók listáján koordinátáikkal megadottak mindegyike
- azonosítsd az attribútumait annak a földhasználati poligonnak, amelyben egy adott ház található
- jelölések
- a pont (u,v)-ben található
- a poligonnak n csúcspontja van: (xi,yi), i=1,...,n, és zárt, mivel (xn+1,yn+1) = (x1,y1)
Stratégia
1. Rajzolj egy függőleges egyenest a ponttól fölfelé a végtelenbe
2. Számold meg, hogy hányszor metszi az egyenes a poligon határát
- ha a szám páratlan, akkor a pont belül van
- ha a szám páros, akkor a pont kívül van
Mintaprogram - Egyszerű "pont a poligonban" program
ni = +1
for i=1 to n
if xi+1 <> xi then (A)
if (xi+1-u) * (u-xi) >= 0 then (B)
if xi+1 <> u or xi <= u then (C)
if xi <> u or xi+1 >= u then (D)
b = (yi+1-yi) / (xi+1-xi)
a = yi-b * xi
vi = a+b*u
if vi > v then
ni = ni*(-1)
end if
end if
end if
end if
end if
next i
- b az (xi,yi) kezdőponttól az (xi+1,yi+1) végpontba tartó egyenes meredeksége
- behelyettesítve x=u -t az y=a+b*x egyenletbe, megkapjuk a kérdéses egyenes és a ponton átmenő (x=u) függőleges metszéspontjának y koordinátáját
- ezután, ha vi > v , akkor a metszésnek a pont fölött kell lennie és a vizsgálat folytatódhat
- az ni változó váltogatva veszi fel a +1 és -1 értékeket
- ha a program metszéspontot talál, akkor vált
- a végén ni=-1, ha a pont belül van és ni=+1, ha kívül
Különleges esetek
- az A-tól D-ig terjedő programsorok a különleges eseteket kezelik a következők szerint
A. ha az (xi,yi) -ből (xi+1,yi+1)-be tartó egyenes függőleges, akkor nem lehet metszés
B. metszést mutat, ha az i. pont az u -n átmenő függőleges egyik oldalán van, míg az (i+1). pont a másikon
C. D. ha akár (xi,yi), akár (xi+1, yi+1) pontosan rajta van a ponton átmenő függőlegesen, azaz a keresett pont pontosan egy töréspont alatt van, a számlálás hibázhat:
- a probléma megoldása a következő:
- ha (xi,yi) pontosan a függőlegesen fekszik, csak akkor számolunk metszéspontot, ha (xi+1,yi+1) jobbra fekszik, vagy
- ha (xi+1,yi+1) fekszik pontosan a függőlegesen, csak akkor számolunk metszéspontot, ha (xi,yi) tőle balra fekszik
Poligon izolált szigetekkel
- jól működik
A poligonban van egy lyuk, s benne egy sziget
- jól működik
Konkáv poligonok
- jól működik
Mi van akkor, ha a pont a poligon határára esik?
- egyes "pont a poligonban" algoritmusok explicit módon tárgyalják ezt az esetet, az ismertetett algoritmus azonban nem vizsgálja külön ezt a helyzetet, ezért
- ilyen esetekben néha belül, máskor kívül fekvőnek találja a pontot
Bizonytalan határok
- Blakemore (l. Blakemore, 1984) általánosítja a pont a poligonban algoritmust ún. fuzzy-határok esetére:
- a határ elhelyezkedése bizonytalan
- azt feltételezzük, hogy a határ köré rajzolt e
szélességű sáv tartalmazza a határ ismeretlen valódi helyzetét
- ezután a pontok négy kategóriába oszthatók: "biztosan kívül fekvő", "valószínűleg kívül fekvő", "valószínűleg belül fekvő", "biztosan belül fekvő"
Sok pont sok poligonban
- a poligonokat valószínűleg ívek szerint tárolják
- vizsgáld meg valamennyi ívet azokkal a függőlegesekkel való metszés szempontjából, melyeket minden pontból fölfelé húzunk
33.2. ábra - Sok pont sok poligonban
- ha egy, az A és B poligonokhoz egyaránt tartozó ívet metsz a függőleges, akkor a metszés tényét mind az A, mind a B poligonhoz fel kell jegyezni, függetlenül attól, hogy az ív melyik oldalán fekszik
- ez minden pont/poligon kombináció számára egy számlálót igényel
- nem igazán hatékony
- egy jobb algoritmust ismertetünk az alábbiakban
- amikor egy ívet metsz egy függőleges, tárolni kell a metszéspont y koordinátáját, valamint az ív alatti poligon nevét (ha az ív irányítottsága Nyugatról Kelet felé mutat, a jobboldali poligonét, ellenkező irányítottság esetén a baloldaliét)
- minden pont számára nyilván kell tartani:
(a) a legalsó megtalált metszéspontot, és
(b) az ez alatt a metszéspont alatti poligon nevét
- miután minden ív vizsgálata megtörtént, megállapítható a legalsó metszéspont, az alatta lévő poligon a pontot tartalmazó poligon
- minden pont vonatkozásában csak két dolgot kell tárolni
- ha nem végzünk el bizonyos előzetes rendezéseket, továbbra is minden pontról minden ívet meg kell vizsgálni
D. A CENTROID HELYZETE
33.3. ábra - Példák centroid helyzetekre
- a centroid potenciális haszna abban van, hogy mint középpont képviseli a poligont
- a centroidot úgy határozhatjuk meg, hogy az az a pont, amelyben tetszőlegesen felfüggesztve a poligon egyenletes vastagságú furnér lemezből kivágott makettjét, ez utóbbi nyugalomban marad
- sajnos a centroid nem mindig a poligonon belül helyezkedik el, ez korlátozza középpont jellegű használhatóságát
- bizonyos programok a centroidot a töréspontok koordinátáinak átlagából számolják, az így kapott érték azonban nem azonos a fentiekben meghatározott centroiddal (a meghatározás szerint ugyanis a centroid a síkidom súlypontja, míg a koordináta-átlagok a ponthalmaz súlypontját szolgáltatják s a kettő nem ugyanaz)
Módszer
- a jobb algoritmus, a területszámításhoz hasonlóan, a koordináta-tengelyekre bocsájtott függőlegesekkel trapézokat hoz létre
- mivel minden trapéz egy háromszögből és egy téglalapból áll, ezek centroidjainak súlyozott átlagából a poligon centroidja meghatározható
- Centroid képlet
X = S
[(yi - yi+1) (xi2 + xixi+1 + xi+12)/6A]
Y = S
[(xi+1 - xi) (yi2 + yiyi+1 + yi+12)/6A]
- megjegyzés: mint a területszámító algoritmusnál a pontokat, itt is az óramutató járásának megfelelően kell számozni, és nem lehetnek negatív y értékek
E. VÁZ
- olyan vonalhálózat, melyet a poligonon belül azzal a feltétellel lehet megszerkeszteni, hogy minden pontja azonos távolságra van a két legközelebbi oldaltól,
- a váz elágazási helyein a csomópontokban, három oldaltól mért távolság egyenlő
- a váz marad meg a poligon "összehúzódása" után
- minden oldala konstans sebességgel mozog befelé
- úgy tekinthető, mint az övezet kialakítás ellentett művelete
33.4. ábra - Poligon váz
- a poligon konvex csúcsain a szögfelezők befelé mozgó vonalakat alkotnak
- minden konkáv csúcsnál a redukált poligont körív alkotja, a körív középpontja a csúcspontban van
- a folyamat továbbfejlődésével a szögfelezők és a körívek egybeolvadnak és fa jellegű szerkezetet alkotnak
- amint a poligon kisebbedik, széteshet egy vagy több szigetre
- végül a poligon ponttá redukálódik
- ez a pont:
- legtávolabb fekszik az eredeti határtól
- középpontja annak a legnagyobb körnek, amely belülről érinti az eredeti poligont
Alkalmazások
- megfelelő helyet nyújt a poligon címke elhelyezésére
- a címke rajzolható:
- a poligon váz-tengelye mentén
- pontra redukálás után a pontban
- utca-tömb fölbontása poligonokra, minden front számára egy poligon címke elhelyezése céljából
IRODALOM
Blakmore, M., 1984, "Generalization and error in spatial databases," Cartographica 21:131-9
Shamos, M.I., és F.P. Preparata, 1985. "Computational Geometry", Springer-Verlag, Berlin. A geometriai
algoritmusok szabványos, de komplex tárgyalása
ELLENŐRZŐ KÉRDÉSEK
1. Vitasd meg, milyen eredményekre vezet a poligon területet meghatározó és a pont a poligonban algoritmus használata, ha a poligon nem megfelelő szerkezetű (pl. nyitott, nyolcas alakú).
2. Módosítsd a pont a poligonban algoritmust olymódon, hogy szabatosan meghatározza a pont belső és külső elhelyezkedése mellett azt is, ha a pont a határvonalon van.
3. Vezess le képleteket a poligon területére és a centroid helyzetére az alapelvekből kiindulva.
4. Módosítsd a poligon területét meghatározó algoritmust olyképpen, hogy jelezze a negatív y koordinátákat és fel tudja azokat használni a területszámításhoz.
|
