Konvexní obálka množiny bodů

Konvexní obálka množiny bodu. ˚ Graham Scan. Jarvis Scan. Quick Hull. Inkrementální metoda. Divide and Conquer. Rotating Calipers.

Tomáš Bayer | [email protected] ˇ Katedra aplikované geoinformatiky a kartografie. Pˇrírodovedecká fakulta UK.

ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

1 / 39

Obsah pˇrednášky

1

Úvod do problému

2

Formulace problému

3

Metody konstrukce konvexní obálky

4

Minimum Area Enclosing Rectangle

5

ˇ u˚ budov Detekce hlavních smer


2 / 39

Úvod do problému

1. Detekce obrysu budovy z klasifikovaných dat


3 / 39

Formulace problému

2. Formulace problému Dáno:

Množina n bodu˚ S = {p1, , p2 , ..., pn } v R2 ,

Hledáme:

Nejmenší konvexní množinu C, ∀pi ∈ C. (Convex Hull Problem)

kde

pi = [xi , yi ].

Definice 1: Konvexní obálka množiny H koneˇcné množiny S v E2 pˇredstavuje nejmenší konvexní ˇ mnohoúhelník P obsahující S (tj. neexistuje P 0 ⊂ P splnující definici). Definice 2: Konvexní obálka H množiny koneˇcné množiny S pˇredstavuje konvexní mnohoúhelník P s nejmenší plochou. Definice 3: Konvexní obálka H množiny koneˇcné množiny S pˇredstavuje pruseˇ ˚ cnici všech polorovin obsahujících S. Definice 4: Konvexní obálka H množiny koneˇcné množiny S pˇredstavuje sjednocení všech trojúhelníku, ˚ jejichž vrcholy tvoˇrí body v S. Množinu S oznaˇcíme jako konvexní, pokud spojnice libovolných dvou prvku˚ leží zcela uvnitˇr této množiny. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

4 / 39

Formulace problému

3. Ukázka konvexní obálky H množiny S


5 / 39

Formulace problému

4. Využití konvexní obálky ˇ Jedna z nejpoužívanejších geometrických struktur, pomocná struktura pro ˇradu algoritmu. ˚ ˇ Casto používána jako první odhad tvaru prostorového jevu Pˇríklady použití: Detekce kolizí: plánování pohybu robotu. ˚ Konstrukce MBR: využití v kartografii pro detekci tvaru a natoˇcení budov. Analýza tvaru˚ (Shape Analysis): analýza tvaru˚ objektu. ˚ Statistická analýza: analýza rozptylu, ˚ odhady, napˇr. metoda Onion Peeling. Analýza shluku˚ (Cluster Analysis): vlastnosti clusterovaných dat. Poznámka: Konvexní obálka H existuje v Rd ., budeme se zabývat pouze R2 . variantou. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

6 / 39

Formulace problému

5. Odhad centroidu metodou Onion Peeling


7 / 39


6. Metody konstrukce konvexní obálky

ˇ používaných metod pro konstrukci konvexní obálky: Pˇrehled nejˇcasteji Jarvis Scan (Gift Wrapping) Graham Scan Quick Hull Inkrementální kontrukce Divide and Conquer ˇ Nekteré z metod použitelné pouze pro R2 , jiné pˇreveditelné do vyšší dimenze.


8 / 39


7. Jarvis Scan Pˇripomíná postup balení dárku do papíru (tzv. Gift Wrapping Algorithm), autorem Jarvis 1973. Jednoduchá implementace, lze rozšíˇrit i do R3 . Pˇredpoklad: v S nejsou tˇri kolineární body. Nutnost pˇredzpracování O (n): nalezení pivotu q, qy = min(yi ). Princip algoritmu: Necht’ pj −1 , pj pˇredstavují dva poslední body H a bod pj +1 aktuálneˇ nalezený bod pˇridávaný do H. ˇ Bod pj +1 musí splnovat kritérium minimálního úhlu θ mezi stranou pj +1 pj a prodloužením strany pj −1 pj . Bod pj +1 hledáme ze všech pi , které dosud nejsou souˇcástí H.


9 / 39


8. Algoritmus Jarvis Scan Nevýhodou složitost O (n2 ), nehodí se pro velké S. Algoritmus 1: Gift Wrapping (S, H) 1: Nalezení pivota q , q = min(yi ), 2: Pˇridej q → H. 3: Inicializuj: pj −1 =lib. bod ležící na ose x, pj = q, pi = pj −1 . 4: Opakuj, dokud pi 6= q: 5: Opakuj pro ∀pi ∈ / H a body pj −1 , pj : 6: Nalezni pi takové, že θ = min(θi ); 7: Pˇridej pi → H. 8: pj −1 = pj ; pj = pi .


10 / 39


9. Ukázka Jarvis Scan


11 / 39


10. Graham Scan Algoritmus není možné rošíˇrit do R3 (Graham 1972). Výrazneˇ nižší cˇ asová složitost O (n · log(n)), lze použít i na rozsáhlé datasety S. Princip: ˇ Každá uspoˇrádaná trojice bodu˚ pj −1 , pj , pj +1 ∈ H musí splnovat kritérium levotoˇcivosti. Pokud pro libovolnou trojici bodu˚ pj −1 , pj , pj +1 platí kritérium levotoˇcivosti: Body zˇrejmeˇ leží na H (avšak nemusí!). Pak testování následující trojice pj , pj +1 , pj +2 ... neplatí kritérium levotoˇcivosti: Odstraníme vrchol pj z H, tj. prostˇrední bod pj nemuže ˚ ležet na H. ˇ na trojici dvema ˇ Pak testování trojice pj −2 , pj −1 , pj +1 , tj. bod pj doplnen nejbližšími pˇredchudci ˚ pj −2 , pj −1 ∈ H. Jako kritérium levotoˇcivosti je používán Half Edge test. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

12 / 39


11. Ilustrace kritéria levotoˇcivosti


13 / 39


12. Algoritmus Grahamova skenování ˇ bod qy = min(yi ). Pˇrezpracování O (n): pivot q, nejpravejší ˇ datasetu S podle úhlu k ose x v bodeˇ p. Pˇrezpracování O (n · log(n)): setˇrídení Algoritmus 2: Graham Scan (S, Q) ˇ bod qy = min(yi ), q ∈ H. 1: Nalezení pivota q, nejpravejší ˇ všech bodu˚ S úhloveˇ dle q, index j odpovídá setˇrídenému ˇ 2: Setˇrídení poˇradí. 3: Pokud dva body mají stejný úhel, vymaž bod bližší q. 4: Inicializuj j = 2; Stack Q. 5: push (q , p1 ) → Q, (indexy posledních dvou prvku˚ pt , pt −1 ) 5: Opakuj pro j < n: 6: if pj vlevo od pt −1 , pt : 7: push pt do Q. 8: j = j + 1. 9:

else pop Q.


14 / 39


13. Ukázka konstrukce Graham Scan


15 / 39


14. Algoritmus Quick Hull Nazván QuickHull pro analogii s QuickSortem. Založen na pˇrístupu Divide and Conquer, složitost O (n2 ). Princip algoritmu: Konvexní obálka je konstruována ze dvou cˇ ástí, z horní cˇ ásti nazývané Upper Hull a dolní cˇ ásti nazývané Lower Hull. Upper Hull je nad spojnicí dvou bodu˚ q1 , q3 MBR s extrémními souˇradnicemi x, q1 = min(xi ), q3 = max(xi ), Lower Hull pod touto spojnicí q1 , q3 . ˇ bod c ležící vpravo od této Nad každou nalezenou stranou obálky a, b hledáme nejvzdálenejší strany, který se stává novým bodem konvexní obálky ⇒každá nalezená strana se rozpadne na dveˇ nové. ˇ výslednou konvexní obálku složíme z obou Obeˇ cˇ ásti konvexní obálky zpracovávány separátne, cˇ ástí. Duvod ˚ rychlosti algoritmu (navzdory kvadratickému odhadu nejhoršího pˇrípadu): pˇri vytváˇrení konvexní obálky se nesnažíme pracovat se všemi body vstupní množiny, ale pouze s body, které nacházejí blízko konvexní obálky. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

16 / 39


15. Algoritmus Quick Hull Algoritmus využívá dvojici rekurzivních volání procedury QuicHull nad noveˇ vzniklými stranami ac, cb z puvodní ˚ strany ab. ˇ Parametry: poˇcáteˇcní a koncový bod delené strany a jí pˇríslušející podmnožiny datasetu S, H. ˇ Nutnost pˇredzpracování, nalezení MBR, rozdelení množiny. Algoritmus 3: Quick Hull (a, b„ S, H) 1: if (a + 1 = b) S = 2: else: 3:

Ø;

return; //Hrana neobsahuje mezilehlé body

−→

−→

Najdi bod c ∈ S , d (c , a, b) = max ležící vpravo od a, b

4:

/ return; //Neexistuje bod vpravo od hrany. If c = O

5:

H ← c. //Pˇridej bod c do H.

6:

Quick Hull(a, c , S , H) //Upper Hull

7:

Quick Hull(c , b, S , H) //Lower Hull

Volání: q1 = [min(xi ), y ] q3 = [max(xi ), y ]

Split S to S1, S2; QuickHull(q1 , q3 , S 1); //Upper Hull QuickHull(q3 , q1 , S 2); //Lower Hull


17 / 39


16. Ukázka konstrukce Quick Hull


18 / 39


17. Implementace s aproximací body MBR První aproximace H pˇredstavuje konvexní cˇ tyˇrúhelník q1 , q2 , q3 , q4 .

H zpracováván postupneˇ po jednotlivých segmentech. Algoritmus využívá cˇ tveˇrici rekurzivních volání procedury QuickHull nad každou stranou (qi qi +1 ) ⇒ urychlení. Volání:

= [min(xi ), y ]; = [x , min(yi )]; = [max(xi ), y ]; = [x , max(yi )]; Split S to S1, S2, S3, S4; QuickHull(q1 , q2 , S1 , H); QuickHull(q2 , q3 , S2 , H); QuickHull(q3 , q4 , S3 , H); QuickHull(q4 , q1 , S4 , H); q1 q2 q3 q4


19 / 39


18. Ukázka konstrukce Quick Hull s aproximací body MBR


20 / 39


19. Inkrementální konstrukce Rychlá konstrukce, složitost O (n · log(n)). Lze pˇrevést do vyšší dimenze. Princip algoritmu: Body z S pˇridávány po jednom do vytvoˇrené konvexní obálky H, jejíž tvar je modifikován. Necht’ P pˇredstavuje podmnožinu datasetu S obsahující m bodu˚ a p pˇridávaný bod, pak Hm+1 = Hm ∩ p. Pˇri pˇridání bodu p do Hm mohou nastat dveˇ situace: p ∈ Hm Bod p muže ˚ být zanedbán, neovlivní tvar Hm+1 . Test polohy p vzhledem k Hm realizován prostˇrednictvím Half Edge testu. p∈ / Hm Bod p ovlivní tvar Hm+1 . Nutno najít horní a dolní teˇcny t1 , t2 procházející p kolmé k Hm . ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

21 / 39


20. Ukázka nalezení horní a dolní teˇcny


22 / 39


21. Princip nalezení horní a dolní teˇcny t1 , t2 V každém bodeˇ Hm lestujeme polohu incidujících dvou stran ej , ej +1 vzhledem k pˇridávanému bodu p. V bodech dotyku teˇcen platí: ˇ Dolní tecna t1 : Bod p vlevo od ej a vpravo od ej +1 . ˇ Horní tecna t2 : Bod p vpravo od ej a vlevo od ej +1 . Pro ostatní vrcholy pi leží bod p na stejné straneˇ od ej , ej +1 . ˇ Konvexní obálka mezi dotykovými body teˇcen odstranena a nahrazena dvojicí teˇcen. Algoritmus 4: Upper and Lower Tangent 1: for i = 0 to n − 1 2: if XOR(p vlevo od/na pi −1 pi , p vlevo od/na pi pi +1 ) 3:

pi je dotykový bod.

Poznámka: XOR (A, B ) = (A ∩ B ) ∪ (B ∩ A). ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

23 / 39


22. Konstrukce metodou Divide and Conquer Algoritmus se složitostí O (n · log(n)). Lze snadno pˇrevést do vyšší dimenze. ˇ ˇ Jeho implementace je ponekud obtížnejší. Princip algoritmu: ˇ Rozdelení problému nad množinou S na dveˇ podmnožiny S1 , S2 stejné ˇ velikosti, které zpracovávány samostatne. Obeˇ ˇrešení poté spojena s využitím horní a dolní spoleˇcné teˇcny t1 , t2 množin S1 , S2 , spojení lze realizovat v lineárním cˇ ase O (n). ˇ deleny ˇ Tyto podmnožiny mohou být opet na další podmnožiny Si poloviˇcní velikosti tak dlouho, dokud ˇrešení problému není geometricky jednoduché ⇒ konvexní obálka množiny tvoˇrené tˇrema body. Popis algoritmu bude ilustrován pro dvojici podmnožin A, B .


24 / 39


23. Algoritmus Divide and Conquer Pˇredpoklad: žádná trojice bodu˚ není kolineární a žádné dva body v datasetu nemají stejné souˇradnice x. ˇ Delení S na dveˇ podmnožiny A, B a jejich následné spojení s nalezením horní a dolní teˇcny t1 , t2 . Algoritmus 5: Divide and Conquer. ˇ S podle x. 1: Setˇrídení ˇ 2: Rozdelení S na dveˇ podmnožiny A, B obsahující n/2 bodu. ˚ 3: Konstrukce konvexních obálek H(A) a H(B ). 4: Spojení konvexních obálek H = H(A) ∪ H(B ). 5: Nalezení dolní teˇcny t1 . 6: Nalezení horní teˇcny t2 . ˇ 7: Nahrazení úseku˚ konvexních obálek A, B mezi obema teˇcnami. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

25 / 39


24. Algoritmus nalezení dolní teˇcny t1 Existence ˇrady algoritmu˚ pro spojení dvojice konvexních obálek. Ukázka spojení nalezení dolní teˇcny t1 “procházkou”, Walking Algorithm (Preprata & Hong, 1977). Z extrémních bodu˚ a, b množin A, B nalezneme k bodu a bod b takový, že jejich spojnice je dolní teˇcnou B. Z bodu b hledáme bod a takový, aby jejich spojnice byla dolní teˇcnou A. Postup opakujeme, dokud a, b není dolní teˇcnou A i B. Algoritmus 6: Lower Tangent t1 , Walk ˇ bod A. 1: Najdi bod a: nejpravejší ˇ bod B. 2: Najdi bod b: nejpravejší 3: Opakuj, dokud t1 = ab není dolní teˇcnou A a B. 4: Opakuj, dokud t1 není dolní teˇcnou A: 5: a = a − 1. 6: Opakuj, dokud t1 není dolní teˇcnou B: 7:

b =b+1


26 / 39


25. Princip nalezení dolní teˇcny


27 / 39


26. Využití konvexní obálky pro konstrukci obdélníka s minimální plochou Dáno: Hledáme:

Množina n bodu˚ S v R2 . Obdélník R s nejmenší plochou opsaný S. (Minimum Area Enclosing Box)

Naivní algoritmy problém ˇreší v kvadratickém cˇ ase O (n2 ). Definice: Nejméneˇ jedna strana obdélníka s minimální plochou R opsaného množineˇ S je kolineární se stranou H. Algoritmy pro konstrukci obdélníka s minimální plochou R opsaného množineˇ S pracují s konvexní obálkou H ⇒ pˇredzpracování. Složitost konstrukce konvexní obálky H : O (n · log(n)). Složitost konstrukce obdélníku R nad H: pouze O (n) ! Algoritmus ˇreší problém v cˇ ase O (n · log(n)). Využití v kartografii pro detekci tvaru a natoˇcení budov. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

28 / 39


27. Ukázka obdélníku s minimální plochou opsaného množineˇ S


29 / 39


28. Rotating Calipers Algoritmus Rotating Calipers pro nalezení R nad datasetem S v lineárním cˇ ase (Toussaint, 1983). V prvním kroku nalezen MBR, který se dotýká H v bodech s extrémními souˇradnicemi pi , pj , pk , pl . Úhly stran pˇríslušející 4 extrémním bodum ˚ sevˇrené se stranami MBTR oznaˇcme θi , θj , θk , θl .


30 / 39


29. Princip metody Rotating Calipers Pro délky hran l1 , l2 MBR a plochu A platí: l1

= dik cos ϕk

l2

= djl cos ϕj

A

= l1 l2

Otoˇcení obdélníku o úhel ±δ , nové délky hran l10 , l20 a plocha A0 l10

= dik cos(ϕk ± δ)

0

= djl cos(ϕj ± δ)

0

= l10 l20 .

l2 A

Rotace dle ±δ lze sˇcítat, jak urˇcit plochu obdélníku po i-tém otoˇcení z plochy pˇredchozího? ˇ Pro vztah mezi Ai +1 a Ai platí po úprave: Ai +1 = Ai (cos2 δ + (tan ϕk − tan ϕj ) cos δ sin δ − tan ϕk tan ϕj sin2 δ) ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

31 / 39


30. Algoritmus metody Rotating Calipers Algoritmus 7: Rotating Calipers 1: Inicializuj Amin = ∞, rot = 0, θsum = 0. 2: Nalezení MBR nad S. 3: Výpoˇcet úhlu˚ ϕj , ϕk a plochy A(R). 4: Amin = A. 5: Opakuj, dokud θsum < π4 : 6: 7: 8: 9: 10: 11:

Výpoˇcet úhlu˚ θi , θj , θk , θl a stran l1 , l2 θ = min(θi , θj , θk , θl ). Otoˇcení R o úhel θ Urˇcení A(R) z pˇredchozí A. if (A < Amin ) Amin = A;rot = rot + θ; L1 = l1 ; L2 = l2 .

12:

θsum = θsum + θ.

Možné problémy: numerická nepˇresnost vlivem rekurentního výpoˇctu formule mezi Ai +1 , Ai . ˇ Tomáš Bayer | [email protected] (Katedra aplikované Konvexní geoinformatiky obálkaamnožiny kartografie. bodPˇ u. ˚ rírodovedecká fakulta UK.)

32 / 39


ˇ metody Rotating Calipers 31. Znázornení


33 / 39


32. Detekce úhlu natoˇcení budovy ˇ Castý problém pˇri kartografické generalizaci budov cˇ i jejich automatickém rozpoznávání. Budova pˇred generalizací a po generalizaci musí mít uchovánu orientaci vzhledem k ostatním obsahovým prvkum ˚ mapy (napˇr. zachování uliˇcní cˇ áry). ˇ budovy (jsou na sebe kolmé). Nutnost detekovat tzv. hlavní smery Popisují orientaci (tj. natoˇcení) budovy vzhledem k ostatním prvkum ˚ mapy. Metody detekce natoˇcení budov: Longest Edge. Weighted Bisektor Minimum Area Enclosing Rectangle. Wall Average.


34 / 39


ˇ u˚ budov 33. Metody detekce hlavních smer Longest Edge ˇ budovy pˇredstavován nejdelší stranou v budove, ˇ druhý hlavní smer ˇ na ní kolmý. První hlavní smer Nedosahuje pˇríliš dobrých výsledku˚ Wieghted Bisector: ˇ ϕ1 , ϕ2 a s délkami s1 , s2 . První hlavní smer ˇ je dán V budoveˇ hledány dveˇ nejdelší úhlopˇríˇcky se smery ˇ váženým prum ˚ erem. Dává velmi dobré výsledky.

ϕ=

s1 ϕ1 + s2 ϕ2 s1 + s2

.

Minimum Area Enclosing Rectangle ˇ pˇredstavuje delší ze stran R, druhý kratší strana. Dává dobré výsledky, problémy s První hlavní smer budovami tvaru L a Z. Wall Average ˇ Na každou stranu budovy aplikována operace mod ( π2 ). Zbytky po delení leží v intervalu < 0, π2 ). Z hodnot ˇ váhou je délka strany. spoˇcten vážený prum ˚ er,

ϕ=

n X si · ϕi mod ( π2 ) i =1

si

.


35 / 39


ˇ u˚ budovy 34. Detekce hlavních smer Metody Longest Edge a Wall Average (Duchene et al, 2003).


36 / 39


ˇ u˚ budovy 35. Detekce hlavních smer Metody Smallest Area Enclosing Rectangle a Weigted Bisector (Duchene et al, 2003).


37 / 39


ˇ u˚ 36. Problémy pˇri detekci hlavních smer ˇ u˚ u budov tvaru˚ L, Z. Problémy s detekcí hlavních smer


38 / 39


ˇ na kartografickou 37. Vliv chybného urˇcení hlavního smeru generalizaci Algoritmus Divide and Conquer (Bayer, 2009).


39 / 39

Konvexní obálka množiny bodů

Recommend Documents