Geometrické vyhledávání
‡
‡
mnohoúhelníky a jejich vlastnosti
lokalizace bodu vůči konvexnímu mnohoúhelníku
„
‡
lokalizace bodu vůči nekonvexnímu mnohoúhelníku
„
‡
rozhodnutí, zda je bod vnitřní či vnější
rozhodnutí, zda je bod vnitřní či vnější
lokalizace bodu v rovinném grafu
„
rozhodnutí, ve které stěně grafu daný bod leží
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Definice
P je část roviny ohraničená uzavřenou lomenou čarou
tvořenou konečným počtem n vrcholů pi.
Nechť ei = pi pi +1 je strana mnohoúhelníka (úsečka spojující
Mnohoúhelník
sousední vrcholy).
„
počet vrcholů, stran a vnitřních úhlů je v jednom mnohoúhelníku stejný
(= n )
„
(každé dvě sousední strany mají společný právě jeden krajní bod a neleží
v téže přímce)
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Mnohoúhelníky a jejich vlastnosti
‡
Konvexní mnohoúhelník
vnitřní úhly jsou konvexní.
‡
V konvexním mnohoúhelníku P neleží žádný bod spojnice dvou
libovolných vrcholů pi , p j , i ≠ j vně P.
‡
Všechny úhlopříčky konvexního mnohoúhelníku
‡
Přímka q, která není rovnoběžná se žádnou hranou konvexního
mnohoúhelníku P, protíná P nejvýše ve dvou bodech.
Počítačová geometrie
P je takový mnohoúhelník, jehož všechny
P leží uvnitř P.
Petra Surynková
Geometrické vyhledávání
konvexní
mnohoúhelník
žádný bod spojnice
libovolných vrcholů
neleží vně
mnohoúhelníka
pj
pi +1
pi
nejvýše 2 průsečíky
q
Počítačová geometrie
pi
všechny
úhlopříčky leží
uvnitř
mnohoúhelníka
Petra Surynková
Geometrické vyhledávání
‡
Mnohoúhelníky a jejich vlastnosti
‡
Konvexní mnohoúhelník
kteroukoli stranou.
‡
Pokud je alespoň jeden z vnitřních úhlů mnohoúhelníku
mnohoúhelník P je nekonvexní.
‡
V nekonvexním mnohoúhelníku P existuje alespoň jedna spojnice
dvou vrcholů pi , p j , i ≠ j, jejíž body leží vně mnohoúhelníku P.
Počítačová geometrie
P leží vždy v jedné z polorovin určených
P vetší než π ,
Petra Surynková
Geometrické vyhledávání
konvexní
mnohoúhelník
nekonvexní
mnohoúhelník
pi +1
pi
existuje spojnice
vrcholů vně
mnohoúhelníka
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Mnohoúhelníky a jejich vlastnosti
‡
Jednoduchý mnohoúhelník je takový mnohoúhelník, pro jehož
strany platí
„
průsečíkem sousedních stran
tj.
„
strany, které spolu nesousedí, nemají žádný průsečík
tj.
pi
ei = pi pi +1 , ei +1 = pi +1 pi + 2
ei , ei +1 je bod pi +1
ei ∩ ei +1 = pi +1
ei ∩ e j = ∅ , pro každé j ≠ i + 1
ei
pi
pi +1
Počítačová geometrie
jednoduchý
mnohoúhelník
ei
pi +1
Petra Surynková
Geometrické vyhledávání
‡
Mnohoúhelníky a jejich vlastnosti
‡
Každý konvexní mnohoúhelník je jednoduchý.
‡
Každý mnohoúhelník s
‡
‡
n ≥ 4 vrcholy má úhlopříčku, počet úhlopříček
1
v mnohoúhelníku s n ≥ 4 vrcholy je n( n − 3) .
2
Každý mnohoúhelník s n ≥ 4 vrcholy může být přidáním úhlopříček
dekomponován na množinu trojúhelníků – triangulace.
Každá triangulace mnohoúhelníku s
úhlopříček a n − 2 trojúhelníků.
Počítačová geometrie
n ≥ 4 vrcholy používá n − 3
Petra Surynková
Geometrické vyhledávání
triangulace
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
triangulace
n = 14
počet úhlopříček v
triangulaci
14 − 3 = 11
počet trojúhelníků
14 − 2 = 12
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Mnohoúhelníky a jejich vlastnosti
‡
Hvězdicový mnohoúhelník je takový mnohoúhelník, pro který platí
„
existuje vnitřní bod polygonu z (nesplývá s žádným vrcholem
mnohoúhelníku a neleží na žádné straně mnohoúhelníku)
„
každá úsečka zpi (
mnohoúhelníka
„
množina bodů
pi - vrchol mnohoúhelníka) leží celá uvnitř
z se nazývá jádro hvězdicového mnohoúhelníka
z
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu
„
„
určení polohy bodu
vstup
‡
‡
„
mnohoúhelník
bod M
M vzhledem k mnohoúhelníku
P
výstup
‡
‡
‡
bod
bod
bod
M leží uvnitř mnohoúhelníku P
M leží vně mnohoúhelníku P
M leží na straně mnohoúhelníka P (případně splývá s vrcholem)
M1
Počítačová geometrie
M2
M3
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
„ zvolíme bod A uvnitř konvexního mnohoúhelníka (lin. kombinace
vrcholů mnohoúhelníka s koeficienty ∈ ( 0,1) )
‡
např. těžiště libovolných třech vrcholů
p6
p5
p7
M
A
p4
p1
Počítačová geometrie
p2
p3
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
„ bod A spojíme s lib. dvěma vrcholy (rozdělíme na dva úhly, bod A
je vrchol)
p6
p5
p7
M
A
p4
p1
p2
Počítačová geometrie
p3
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
„ zjistíme, ve kterém úhlu leží bod M - jak?
‡
p6
ƒ
ƒ
p5
p7
pokud bod
M leží na rameni např. Ap2
,,za bodem‘‘ p2 - bod M je vně mnohoúhelníka
,,před bodem‘‘ p2 - bod M je uvnitř
mnohoúhelníka
M
A
p4
p1
p2
Počítačová geometrie
p3
„
znovu dělíme úhel, ve kterém leží bod
zjistíme, ve kterém úhlu leží bod M
„
celé opakujeme
„
M
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
p6
p6
p5
p7
M
A
p4
p1
p2
Počítačová geometrie
p3
p5
p7
M
A
p4
p1
p2
p3
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
p6
p6
p5
p7
M
A
p4
p1
p2
Počítačová geometrie
p3
p5
p7
M
A
p4
p1
p2
p3
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
p6
p6
p5
p7
M
A
p4
p1
p2
Počítačová geometrie
p3
p5
p7
M
A
p4
p1
p2
p3
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
p6
p6
p5
p7
M
A
p4
p1
p2
Počítačová geometrie
p3
p5
p7
M
A
p4
p1
p2
p3
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
p6
p5
p7
M
A
p4
p1
p2
Počítačová geometrie
‡
poslední krok – ramena úhlů
procházejí sousedními vrcholy
‡
zjistíme, zda úsečka AM protíná
stranu mnohoúhelníka p4 p5
ƒ ano – bod M je vně
ƒ ne – bod
M je uvnitř
p3
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
‡
p6
ƒ proti směru hodinových ručiček pravotočivá
p5
p7
‡
p4
p1
p2
p3
určení orientace mnohoúhelníku
pi +1 = [ xi +1 , yi +1 ], pi + 2
xi
xi +1
xi +2
Počítačová geometrie
pi = [ xi , yi ],
= [ xi+ 2 , yi +2 ]
tři po sobě jdoucí vrcholy
yi
1
yi +1 1 > 0
yi + 2 1
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - konvexní mnohoúhelníky
‡
vrcholy konvexního mnohoúhelníku
orientovány pravotočivě
‡
bod
p6
p5
p7
ƒ
M
p4
p1
p2
p3
‡
Počítačová geometrie
M [m1 , m2 ] - uvnitř
pro každou stranu pi , pi +1
pi = [ xi , yi ], pi +1 = [ xi +1 , yi +1 ]
xi
yi
1
xi +1
m1
yi +1 1 > 0
m2 1
bod vně – existuje strana, pro kterou
je determinant záporný
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - nekonvexní mnohoúhelníky
„ bodem M vedeme libovolnou polopřímku q
„
= tzv. paprskový algoritmus (Ray Crossing algorithm)
p8
q
p7
p9
p10
p6
p5
M
p1
p3
p2
Počítačová geometrie
p4
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - nekonvexní mnohoúhelníky
„ počet průsečíků přímky q a mnohoúhelníku
‡ lichý – bod M je uvnitř mnohoúhelníka
‡ sudý – bod M je vně mnohoúhelníka
p8
q
p7
p9
p10
p6
p5
M
p1
p3
p2
Počítačová geometrie
p4
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - nekonvexní mnohoúhelníky
„
co musíme ošetřit?
‡
q
polopřímka prochází vrcholem
pi
M
q
počítáme jeden průsečík
Počítačová geometrie
pi
M
počítáme dva průsečíky
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - nekonvexní mnohoúhelníky
„
co musíme ošetřit?
‡
polopřímka stranou
q
pi
q
pi
pi +1
M
počítáme jeden průsečík navazující strany v různých
polorovinách určených přímkou q
Počítačová geometrie
M
pi +1
počítáme dva průsečíky navazující strany ve stejné
polorovině
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu
„
„
určení polohy bodu
vstup
‡
rovinný graf
ƒ
ƒ
ƒ
ƒ
‡
„
M vzhledem k množině mnohoúhelníků
bod
množina vrcholů, hran a stěn
víme, které vrcholy jsou incidentní s hranou
víme, které stěny jsou incidentní s hranou
hrany orientované, dohoda – stěny incidentní s hranou (1. levá, 2. pravá)
M
výstup
‡
stěna grafu, ve které leží bod
Počítačová geometrie
M
Petra Surynková
Geometrické vyhledávání
M1
M2
M3
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu
„ bodem M vedeme libovolnou polopřímku q
M
q
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu
„ bodem M vedeme libovolnou polopřímku q
„
M
„
q
Počítačová geometrie
zjistíme všechny průsečíky této
polopřímky s hranami grafu
z těchto průsečíků vybereme ten, který
je bodu M nejblíže
‡
určíme hranu, na které leží
„
určíme, zda bod M leží vlevo nebo
vpravo od zjištěné hrany
„
tím je určena stěna, ve které bod
M leží
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - předzpracování
„
„
„
rozdělíme graf do svislých pásů
každým vrcholem vedeme rovnoběžku s osou
dvě sousední rovnoběžky vymezují jeden pás
y
y
M
x
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - předzpracování
„
„
uvnitř pásu se nenachází žádný jiný počáteční nebo koncový
bod žádné z hran
uvnitř pásu se žádné dva segmenty neprotínají
y
„
„
M
průnikem oblasti a pásu je
lichoběžník (případně
trojúhelník)
každý lichoběžník uvnitř
pásu (s výjimkou
okrajového) má horního a
dolního souseda
x
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu - předzpracování
„
princip nalezení stěny, ve které leží bod
‡
‡
M
nalezení pásu, ve kterém leží bod M
pro tento pás nalezení lichoběžníku, uvnitř kterého bod
M leží
y
M
M′
x
Počítačová geometrie
Petra Surynková
Geometrické vyhledávání
‡
Lokalizace bodu – předzpracování – popis algoritmu
„
„
„
„
setřídíme x-ové souřadnice vrcholů grafu (vrcholy očíslujeme
dle tohoto uspořádání)
v každém pásu si pamatujeme uspořádaný seznam hran
procházející pásem, uspořádáno podle y-ové souřadnice
vyhledáme pás, ve kterém leží bod M (dle x-ové souřadnice)
v pásu hledáme takovou úsečku, nad nebo pod kterou bod M
leží (půlením)
M
„
určíme stěnu grafu, ve které leží bod
Počítačová geometrie
M
Petra Surynková
Download

Geometrické vyhledávání