REŠITVE S Ugotavljanje vsebnosti točk nad posplošenimi mnogokotniki Matej Gomboši Laboratorij za geometrijsko modeliranje in algoritme multimedijev Fakulteta za elektrotehniko, računalništvo in informatiko, Univerza v Mariboru, Smetanova 17, 2000 Maribor matej. gombosi @ uni-mb .si Izvleček V članku je opisan razširjen algoritem za določanje vsebnosti točk nad posplošenimi mnogokotniki, ki poleg daljic vsebujejo tudi krožne loke. Algoritem uporablja klasično metoda sekanja Jarka. Razlika je v tem, da moramo testirati due vrsti objektov. Nalogo opravimo z enostavnimi in učinkovitimi testi, ki nam hitro odgovorijo na vprašanje. Z uporabo ustreznih podatkovnih struktur nalogo rešimo zanesljivo in enostavno, Kljub razširitvi deluje algoritem še vedno v linearni Časovni zahtevnosti. Abstract Containment Test for Generalized Polyyous The paper describes an extended algorithm for solving the point-in-polygon problem, The polygon in this case consists of straight edges and also of circular arcs. This represents a generalization of Reuleaux polygon. The algorithm uses the classical ray intersection method, The difference is that we have two types of geometric objects to test for intersections. Processing is done with simple and efficient tests, which quickly answer nur question Using the appropriate data structure, this task can be done safely and easily. Oespite the extension of the classical ray intersection method, the algorithm still runs in linear time complexity. 1 Uuod Usebnostni test je eden osnovnih in pogosto uporabljanih algoritmov v računalniški geometriji in njenih aplikacijah [9], To sb posebej uelja za računalniško grafiko, sisteme CAD/EAM in GIS aplikacije. Algoritem je odvisen od tipa mnogokotnikov, s katerimi delamo: 1. mnogokotniki z ravnimi robovi, 2. mnogokotniki, ki vsebujejo tudi krožne loke. Reševanje problemov prvega tipa jc lažje in hitrejše. Večinoma se tudi srečujemo s takšnimi mnogokotniki. Posledica tega je, da so bile dosedanje raziskave usmerjene pretežno v to smer. Tako obstaja precej dobrih algoritmov, ki rešujejo ta problem: metoda sekanja žarka [4|, [6], kodirani koordinatni sistem [2], metoda trikotnikov |3], Swathova metoda [ll)|, algoritem na osnovi uniformne delitve ravnine [14]. Vsi ti algoritmi sprejmejo le mnogokotnike z ravnimi robovi. Mi pa se želimo osrediniti na posplošene mnogokotnike, ki vsebujejo tudi krožne loke. Rešitev za ta tip mnogokotnikov še ni bila podana, zato smo se odločili, da skonstruiramo svoj algoritem. Za osnovo smo vzeli metodo sekanja žarka. Dejstvo, da operiramo s krožnimi loki, nekoliko spremeni in oteži osnovni vsebnostni lest. Naša želja je bila skonstruirati hiter in zanesljiv algoritem, ki bi poleg daljic učinkovito obravnaval tudi krožne loke. Glavno motivacijo so nam predstavljali problemi iz geodezije, kjer se večkrat srečujejo s krožnimi loki. Realen primer na sliki 1 ponazarja naš problem. To je problem onesnaženja okolice cest z izpušnimi plini, Predstavljajmo si cesto, ki je ponazorjena s povezanimi daljicami. Vedeli bi radi, kako se izpušni plini širijo v Sliki! 1 Problem širjenja upošnih plinov ponazorjen s pomočjo posplošenega mnogokolmka 90 upon*BN> INFORMATIKA 2004 -številka 2 - letnik XII Matej Gomboši; Ugotavljanje vsebnosti točk nad posplošenimi mnogokotnik! okolico ceste in kateri objekti in zgradbe ho znotraj onesnaženega področja. Za predstavitev tega problema potrebujemo krožne loke, saj se plini širijo v vse smeri enako. Na sliki 1 vidimo primer ceste in širjenja plinov. Povezane daljice v sredini predstavljajo cesto. Področje Širjenja izpušnih plinov je predstavljeno kot mnogokotnik s krožnimi loki. Imamo majhne mno-gokotnike za posamezne odseke ceste in en skupni mnogokotnik za celo področje, ki smo ga dobili z združevanjem manjših. To nam je omogočil algoritem za tvorbo očrtij [13]. Drugo poglavje podaja nekaj osnovnih definicij, uporabljenih v tem članku. Poglavje tri predstavlja glavno idejo algoritma. Četrto poglavje obravnava robne primere. Analizo algoritma podaja peto poglavje. V šestem poglavju so podani zaključki in ugotovitve. Sedmo poglavje prikazuje relevantno literaturo. 2 Definicije Posplošimo definicijo enostavnega mnogokotnika |7|: Imamo ti točk py pv ..., v ravnini. Pari točk /y»„ PiPv ■■■'P.i iP«so povezani z daljicami ali krožnimi loki. Določajo enostaven posplošen mnogokotnik Pt, če velja: • sosednje daljice ali krožni loki se dotikajo v eni sami skupni točki 0 < i < n, • nesosednje daljice nimajo skupnih točk. Daljice (označene z c, na sliki 2) in krožni laki (označeni z «,) s središči r, predstavljajo robove posplošenega mnogokotnika, točke pa robne točke. Zaporedje robov, ki deli ravnino v omejen in neomejen del, se imenuje zanka [7]. Vsak posplošen mnogokotnik ima natanko eno zanko. Prstan predstavlja a Silks 2. Posplošen mnogokotnik P luknjo znotraj mnogokotnika. Luknje so lahko tudi Vgnezdene in tvorijo hierarhijo. Zanka je protiurno usmerjena, luknja pa sourno. Poglejmo malo bliže strukturo krožnega loka n( na sliki 3. Polmer je označen z r(. Končni točki sta Vj in f, Ti dve točki določata tetivo. Ker je mnogokotnik orientiran, nam ta tetiva predstavlja vektor (f;W1+J) in nam pove tudi, na kateri strani tega vektorja leži mnogokotnik. V primeru slike 3 leži mnogokotnik na desni. 3 Algoritem Za ugotavljanje, ali je neka točka znotraj ali zunaj mnogokotnika, se uporablja metoda sekanja Žarka. Iz točke, ki jo testiram, pošljemo žarek in preverimo kolikokrat seka mnogokotnik. Za določitev vsebnosti uporabimo liho-sodo pravilo. To pravi, da če imamo liho število presečišč, je točka znotraj mnogokotnika, če jih je pa sodo število, je točka zunaj mnogokotnika. Za lažje in hitrejše računanje je naš žarek vodoraven. Tako dobimo vodoraven poltrak. Usmerjenost levo ali desno ni pomembna. Na sliki 4 vidimo primer žarka p iz točke ki je zunaj mnogokotnika P. Žarek seka eno daljico in dva krožna loka. Krožni lok it j je presekan na dveh mestih. To nam da štiri presečišča in liho-sodo pravilo pravi, da je v tem primeru točka zunaj mnogokotnika. Algoritem deluje v dveh korakih: 1. iskanje presečišč med ravnimi robovi mnogokotnika in poltrakom, 2. določanje presečišč med krožnimi loki in poltrakom. Prvi de! algoritma je lažji, saj je test presečišča med vodoravnim poltrakom in daljico dobro poznan in ni Slika 3: Definicija krožnega toka 2004 - številka 2 - letnik XII upoBABNi INFORMATIKA 91 Milici GomboSi. Ugotavljanje vsebnosti točk nad posplošenimi mnogokotniki 1/ V Slika 4: Metoda sekanja vodoravnega žarka iz točke f zahteven. Dejanskega presečišča nam ni potrebno računati, ker nas zanima samo obstoj le-tega, nt* pa njegove koordinate. Drugi del algoritma je za nas zanimiv. Tu je bilo treba sestavili ustrezne teste, ki bi hitro in enostavno določili obstoj presečišča med poltrakom in krožnim lokom. Slika 5 prikazuje krožni lok in poltrak, ki ga seka v točkah ¡i(. Ugotoviti moramo, katera presečišča Štejejo (;/,) in katera ne (d2). Pomembno je, kako je krožni lok predstavljen. Potrebovali bomo vse podatke, omenjene v definiciji. V splošnem imamo dve možni situaciji pri krožnih lokih: ■ točka je zunaj krožnice, • točka je znotraj krožni ce. V prvem primeru se lahko pojavita dve možnosti. Poltrak lahko seka ali pa ne seka tetive. Slika 5 kaže primer, ko poltrak seka tetivo. V tem primeru takoj brez nadaljnjih testov vemo, da imamo samo eno presečišče. Krožnica je seveda presekana dvakrat, vendar je eno izmed presečišč na "vidni", eno pa na "nevidni" strani. Bitka 5 Krožni lok j», je presekan v dveh mestih Tetiva je presekana, ko je žarek p znotraj vodoravnega pasu, omejenega s točkama i^in (f.y < vt.y in f.i/ > vM.y ali obratno) in je točka t na desni strani vektorja (Vi+i x v/' >o). Za ugotavljanje, na kateri strani vektorja Ježi določena točka, vedno uporabljamo vektorski produkt, ker predstavlja hitrejši test kot dejansko računanje presečišča. V primeru, da poltrak ne seka tetive, nam to sploh ne vpliva na rezultat, zato nam tega primera ni potrebno obravnavati. Poglejmo, zakaj. Poltrak lahko še vedno seka preostali del krožnega loka ali pa se ga dotika. Treba bi bilo preveriti razdaljo od središča. Če je ta večja od polmera, nimamo presečišča. Če jc ta manjša kot polmer, potem imamo dve presečišči. Če sta ti dve presečišči na "vidni" slrani (slika 6a), obe upoštevamo, če sta na "nevidni" strani {slika 6b), pa nobenega. V obeh primerih pa to ne spremeni rezultata. Nas zanima samo sod ost oz. lihost Števila presečišč. Če k rezultatu prištejemo 0 ali 2, bo ostal enak. V primeru, da je razdalja enaka polmeru, imamo dotikališče, česar pa nam ni treba upoštevati, saj dotikanje ne vpliva na rezultat. Vidimo, da smo se elegantno izognili odvečnemu testiranju in s tem pospešili algoritem. V Slika 6a. Žarek seka «vidni« del krožnega loka V * M » d d Slika Sb: Žarek seka »nevidni« del krožnega loka 92 uPodABNA INFORMATIKA 2G04 - itevitka 1 - letnik XI i Matej GomboSi: Ugotavljanje vsebnosti tožk nad posplošenimi mnogokotnikl Podobne situacije imamo tudi v primeru, da je točka I znotraj krožnice. Točka jc lahko znotraj vodoravnega pasu, ki ga določata končni točki ali izven. V primeru, da je znotraj, jc število presečišč odvisno od tega, na kateri strani se nahaja "vidni" del kroga, Če je levo od tetive, nimamo presečišč (slika 7a). To pa zato, ker je potem na desni Strani, torej tisti strani, v katero gre po h rak, "nevidni" del kroga. Torej se v tem primeru presečišče t/, ne upošteva. V nasprotnem primeru, ko je "vidni" del na desni strani, imamo seveda eno presečišče. Situacija je popolnoma enaka, le da se presečišče d, zdaj nahaja v "vidnem" delu kroga, ker sta "vidni" in "nevidni" del zamenjana (slika 7b), Če pa je točka zunaj tega pasu, so ugotovitve ravno nasprotne. Če je "vidni" del na levi, imamo eno presečišče (slika 8a), v nasprotnem primeru pa ni presečišč (slika 8b). S tem smo opisali vse možne situacije, ki lahko nastopijo pri testiranju krožnega loka. Dejanskega testiranja je zelo malo. Povzemimo zdaj vse možnosti na enem mestu (tabela 1): Situacija Št. presečišč Točka j a zunaj krožnice Poltrsk seka tetivo +1 Totka je znotraj krožnice ToCka je znotraj pasu tetive "Vidni" del na desni strani +1 Totka je zunaj pasu tetive "Vidni" del na levi strani +1 Tabeia 1: Situacije pri testiranju V primeru, da mnogo kotnik vsebuje luknje, nam to samih pravil za testiranje ne spremeni. Vse luknje se hkrati z zanko upoštevajo pri testiranju. Tako avtomatično dobimo pravilno število presečišč. 4 Robni primeri Običajen robni primer se zgodi, ko je testna iočka / na mnogokotniku. To je lahko datjica ali pa krožni !ok. Te situacije enostavno odkrijemo in nam ne spremenijo poteka algoritma. Če je točka na daljici, odkrijemo to s pomočjo vektorskega produkta (vj/, xv,v2 = 0). Če je na krožnem loku, odkrijemo s pomočjo primerjave Slika 7a »Uidni« tlel krožnega laka je na lani d P Slika Ba: Točka t je zunaj pasti, »vidni« dal je levo v V Malej ijombaši- Ugotavljanje vsebnosti točk n.id posplošenimi mnogokotniki razdalje do središča krožnega loka gre skozi točko v3, žarek q pa skozi točko v,,. V prvem primeru imamo dotik, v drugem pa presečišče. Poglejmo, zakaj. Slika 11: Žarek seka končne točke krožnega loka Odvisno od potrebe aplikacije se točka v takšnem primeru določi kot zunanja ali notranja. Bolj zanimivi so primeri, ko gre žarek skozi robno točko mnogo kotnika. To so lahko robne točke daljic ali končne točke krožnih lokov. Te primere prav tako enostavno rešimo. V primeru, da gre žarek skozi robno točko daljice, preverimo položaja sosednjih robnih točk. Slika 10 prikazuje situacijo. V primeru, da sta sosednji točki na nasprotnih straneh žarka (v3 in vs), vemo, da gre za presečišče («j. Če pa sta sosednji točki na isti strani (t>, in v3), imamo samo dotik (v2). Ta dva primera enostavno ločimo s pomočjo primerjave koordinat y sosednjih točk glede na koordinato y žarka. Zadnji robni primer je primer, ko gre žarek skozi končno točko krožnega loka. Slika 11 kaže dva prime- Chka 1D Žarek seka robni tački daljice V primeru točke v3 vidimo, da se oba sosednja dela mnogokotnika (rob in krožno lok