Minkowského operace a jejich aplikace

Minkowského operace a jejich aplikace Svˇetlana Tomiczková ˇ Plzeˇn KMA FAV ZCU

1. února 2012

Svˇetlana Tomiczková

Minkowského operace a jejich aplikace

Obsah

Aplikace Minkowského suma Minkowského rozdíl Minkowského souˇcin v E2 Minkowského souˇcin kvaternion˚u Akce 22. 6. 1864 - 12. 1. 1909



Úvod

Použití Rozmist’ování (packing, nesting, containment problem) Plánování pohybu robota mezi pˇrekážkami Hledání offsetu (ekvidistantní plochy) Využití v optice Další zp˚usoby popisu kˇrivek a ploch



Rozmist’ování

Containment problem Packing problem Nesting problem Cutting plan Compaction Pálící programy Pokrývání rovinné oblasti kruhy (sférami)



Robot Motion Planning - ˇrešíme úlohu v E2 m˚užeme tuto úlohu rozdˇelit podle tvaru robota a pˇrekážek (konvexní, nekonvexní, aproximace polygonem apod.) podle zp˚usobu pohybu (jestli bude pohyb realizován pouze pomocí posunutí, nebo je možné pˇridat i otoˇcení) pracovní prostor (angl. work space) poˇcet parametr˚u, který koresponduje s poˇctem stupˇnu˚ volnosti robota v rovinˇe, realizovaný pouze pomocí posunutí, jsou to dva stupnˇe volnosti, pokud pˇridáme otoˇcení, jsou to tˇri stupnˇe volnosti Parametrický prostor robota nazýváme konfiguraˇcní prostor (angl. configuration space) ˇ Cást kofiguraˇcního prostoru, kam robot nesmí, se nazývá zakázaný prostor (forbidden space), zbytek kofiguraˇcního prostoru je volný prostor (free space). Svˇetlana Tomiczková


Offset Definice Rovnobˇežné, neboli Bertrandovy kˇrivky, jsou takové kˇrivky, které mají spoleˇcné hlavní normály. Je-li c(t) jedna kˇrivka tohoto páru, pak druhá má rovnici cd (t) = c(t) + d n(t), kde d je konstanta a n(t) jednotkový vektor hlavní normály. Necht’ s(u, v) je plocha v E3 , pak její offset sd (u, v) ve vzdálenosti d definujeme pˇredpisem sd (u, v) = s(u, v) + d n(u, v), kde n(u, v) je jednotkový normálový vektor plochy s(u, v). Offset m˚užeme také definovat jako obálku soustavy kružnic s polomˇerem d, jejichž stˇred se pohybuje po kˇrivce c(t). Svˇetlana Tomiczková


Caustica a anticaustika

V rovinˇe bychom anticaustiku mohli popsat jako kˇrivku, která je evolventou caustiky, což je kˇrivka, kterou dostaneme jako obálku odražených paprsk˚u w. Svˇetlana Tomiczková


Minkowského suma

Definice Necht’ A a B jsou množiny bod˚u v En . Minkowského sumou A ⊕ B množin A a B rozumíme [ A⊕B = Ab , b∈B

kde množina Ab = {a + b| a ∈ A} = A + b je množina A posunutá o vektor b. Necht’ A a B jsou množiny bod˚u v En . Pak A ⊕ B = {a + b| a ∈ A ∧ b ∈ B}.



Vlastnosti Minkowského sumy

A⊕B =B⊕A (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) (A ∪ B) ⊕ (C ∪ D) = (A ⊕ C) ∪ (A ⊕ D) ∪ (B ⊕ C) ∪ (B ⊕ D) As ⊕ B t = (A ⊕ B)s+t Svˇetlana Tomiczková


Minkowského suma dvou krychlí



Vˇeta Necht’ A a B jsou dvˇe množiny v En a x je libovolný bod. Pak A ∩ B x 6= ∅ ⇔ x ∈ A ⊕ (−B), kde −B = {−b|b ∈ B}.

D˚usledek 1

As ∩ B t 6= ∅ ⇔ t − s ∈ A ⊕ (−B).

2

A∩B = 6 ∅ (mají spoleˇcný bod), právˇe když (0, 0) ∈ A ⊕ (−B).



Algoritmy pro výpoˇcet Minkowského sumy

Algoritmus naivní pˇrímý výpoˇcet naivní geometricko-grafový grafový založený na orientovaném grafu

prostor E2 E2 E3 E3 E3 E3

výpoˇcetní složitost O(mn log mn) O(m + n) O(mn log mn) O(eP + eQ + k)

Tabulka: Tabulka algoritm˚u pro výpoˇcet Minkowského sumy



Pˇríklad

Minkowského suma C = A ⊕ B konvexních množin A, B je konvexní množina, jak ale vypadá Minkowského suma množin, které nejsou konvexní?



Pˇríklad

Minkowského suma C = A ⊕ B konvexních množin A, B je konvexní množina, jak ale vypadá Minkowského suma množin, které nejsou konvexní?



Minkowského rozdíl

R. Farouki, H. P. Moon a B. Ravani {a − b| a ∈ A ∧ b ∈ B}


Zhenyu Li \

Ab

b∈B


Minkowského rozdíl

Definice Necht’ A a B jsou množiny bod˚u v En . Minkowského rozdílem A B množin A a B rozumíme množinu \ A B = A−b , b∈B

kde množina A−b = {a − b| a ∈ A} = A − b je množina, která vznikne posunutím množiny A o vektor −b.



Vlastnosti Minkowského rozdílu

As B t = (A B)s−t , A B = (A0 ⊕ (−B))0 , A ⊕ B = (A0 (−B))0 ,



Vlastnosti Minkowského rozdílu

Vˇeta Necht’ A a B jsou dvˇe konvexní, uzavˇrené a omezené množiny v En , pak platí (A ⊕ B) B = A, tedy operace A B je pro konvexní, uzavˇrené a omezené množiny vratná (zprava inverzní) k operaci A ⊕ B. Svˇetlana Tomiczková


Proˇc pˇredpokládáme ve vˇetˇe množiny konvexní, uzavˇrené a omezené? Uved’me si nˇekolik pˇríklad˚u. Konvexní množinu jsme mohli získat jako Minkowského sumu dvou konvexních stejnˇe jako dvou nekonvexních množin, nebo dokonce jedné konvexní a jedné nekonvexní množiny Minkowského rozdílem dvou konvexních množin je ale vždy množina konvexní (je to pr˚unik konvexních množin). Minkowského suma dvou opaˇcných polorovin je celá rovina. Minkowského rozdíl bude ale poˇcítán jako pr˚unik shodných rovin, tedy výsledkem bude celá rovina. Minkowského suma uzavˇrených a omezených množin je uzavˇrená množina, ale Minkowského suma dvou otevˇrených nebo otevˇrené a uzavˇrené množiny je množina otevˇrená. Minkowského rozdíl dvou otevˇrených množin je množina otevˇrená, tj. uzavˇrenou množinu nem˚užeme získat. Svˇetlana Tomiczková


Pˇríklad Minkowského rozdíl ale m˚uže být zprava inverzní operací i v nˇekterých pˇrípadech, kdy pˇredpoklady vˇety splnˇeny nejsou. Necht’ množinou A je kruh a množina B = {b1 , b2 } obsahuje dva body.

Minkowského rozdílem C 0 = C B je pr˚unik dvou množin, z nichž každá obsahuje dva kruhy, tj. výsledkem je p˚uvodní množina A. Svˇetlana Tomiczková


Vlastnosti Minkowského rozdílu Vˇeta Necht’ C a B jsou dvˇe konvexní, uzavˇrené a omezené množiny v En , pak platí (C B) ⊕ B ⊂ C.

Minkowského rozdíl A = C B Svˇetlana Tomiczková


Vlastnosti Minkowského rozdílu Vˇeta Necht’ C a B jsou dvˇe konvexní, uzavˇrené a omezené množiny v En , pak platí (C B) ⊕ B ⊂ C.



Podmínky pro nepˇrekrývání dvou množin m˚užeme modifikovat pro problém umístˇení jedné množiny do jiné to je tzv. containment problem. Definice Množina B leží v množinˇe A, právˇe když B ⊂ A.

Vˇeta Necht’ B x ⊆ A, pak x ∈ A B. Minkowského rozdíl tedy urˇcuje všechna posunutí, kterými m˚užeme pˇremístit množinu B, tak aby ležela uvnitˇr množiny A. Pokud je A B prázdná množina, pak B do A pomocí posunutí umístit nelze. Jestliže bod [0, 0] ∈ A B, pak B ⊂ A.



Podmínky pro nepˇrekrývání dvou množin m˚užeme modifikovat pro problém umístˇení jedné množiny do jiné to je tzv. containment problem.



Minkowského souˇcin Definice Necht’ A a B jsou bodové množiny v E2 . Minkowského souˇcinem A ⊗ B množin A a B rozumíme A ⊗ B = {a × b | a ∈ A, b ∈ B}, kde a × b je souˇcin komplexních cˇ ísel.

Vlastnosti Minkowského souˇcinu A ⊗ B = B ⊗ A, (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C), (A ⊕ B) ⊗ C ⊂ (A ⊗ C) ⊕ (B ⊗ C).



Násobení bodem

Vynásobením množiny B jednobodovou množinou A = {z} provedeme otoˇcení komplexní množiny B okolo poˇcátku o úhel ϕ a stejnolehlost (scaling) se stˇredem v poˇcátku a koeficientem |z|.

Je-li A kˇrivka v E2 , m˚užeme A ⊗ B považovat za sjednocení jednoparametrické soustavy S množin, které dostaneme rotací a stejnolehlostí aB. množiny B, tj. A ⊗ B = a∈A



Násobení dvou pˇrímek Necht’ A, B jsou pˇrímky v E2 . Pak jestliže žádná z pˇrímek neprochází poˇcátkem, pak A ⊗ B je vnˇejšek paraboly , jestliže jedna z pˇrímek prochází poˇcátkem, pak A ⊗ B je sjednocením poˇcátku a dvou otevˇrených polorovin oddˇelených pˇrímkou, která prochází poˇcátkem , jestliže obˇe pˇrímky prochází poˇcátkem, pak A ⊗ B je pˇrímka procházející poˇcátkem.



Násobení kˇrivky a pˇrímky Necht’ A je hladká kˇrivka c v komplexní rovinˇe a B svislá pˇrímka procházející bodem [1, 0]. Pak hranice ∂(A ⊗ B) množiny A ⊗ B je podmnožinou inverzní úpatnice kˇrivky c vzhledem k poˇcátku O.

Úpatnice a inverzní úpatnice mají speciální význam v optice. Pól P reprezentuje zdroj svˇetla a kˇrivka c pˇredstavuje zrcadlo. Svˇetlana Tomiczková


Násobení kružnice a pˇrímky-pˇrímka prochází poˇcátkem



Násobení kružnice a pˇrímky-pˇrímka neprochází poˇcátkem



Umístˇení množiny B do množiny A pˇri použití rotace Necht’ A a B jsou dvˇe množiny v E2 a K = {cos t + i sin t | t ∈ h0, 2π)} je jednotková kružnice se stˇredem v poˇcátku. Pak množinu B m˚užeme umístit do množiny A, tj. existuje x tak, že B x ⊂ A, právˇe když [ A ({z} ⊗ B) 6= ∅. z∈K



Minkowského souˇcin množin kvaternion˚u

Definice Necht’ A a B jsou množiny kvaternion˚u (A, B ⊂ H). Minkowského souˇcinem A ⊗ B množin A a B rozumíme A ⊗ B = {ab | a ∈ A, b ∈ B}, kde ab je souˇcin kvaternion˚u. Necht’ A a B jsou množiny kvaternion˚u. Pak [ A⊗B = aB. a∈A



Zobecnˇení Minkowského souˇcinu množin kvaternion˚u

Definice Necht’ A ⊂ R × H3 a X ⊂ H. Akcí A X množiny A na množinu X rozumíme A X = {as al x ar + at | (as , al , ar , at ) ∈ A, x ∈ X }. Takto definovaná akce je zobecnˇením Minkowského souˇcinu množin kvaternion˚u. Jestliže A ⊂ H a A = {(1, a, 1, 0)| a ∈ A}, pak A X = {a x | a ∈ A, x ∈ X }, tj. A X = A ⊗ X . Pro X ⊗ A bychom volili A = {(1, 1, a, 0) | a ∈ A} a A X = {x a| a ∈ A, x ∈ X } = X ⊗ A.



Geometrická interpretace akce Anuloid A X , kde A = {(as , cos u2 + k sin 2u , cos u2 + k sin u2 , a(i cos u + j sin u)) | u ∈ h0, 2π)} a X = {i cos v + k sin v | v ∈ h0, 2π)}. as = sin u2

as = b



Geometrická interpretace akce Šroubové plochy Kˇrivka at je šroubovicí, A = {(as , cos u2 + k sin 2u , cos u2 + k sin u2 , a(i cos u + j sin u) + k v0 u) | u ∈ h0, 2π)}. X = {i v | v ∈ h−1, 1i}


X = {i cos v + k sin v | v ∈ h0, 2π)}


Literatura de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried: Computational geometry. Algorithms and applications. Berlin: Springer Verlag 1997. Brechner, Eric, L.: General offset Curves and Surfaces. In Geometry Processing for Design and Manufacturing, ed. Barnhill, R.E., SIAM,Philadelphia, pp. 101-121, 1992. Farouki, Rida T.; Moon, H. P.; Ravani, B.: Minkowski geometric algebra of complex sets. Geometriae Dedicata 85: 283-315, 2001. Farouki, Rida T.; Chastang, Jean-Claude A.: Curves and surfaces in Geometrical Optics. Mathematical Methods in Computer Aided Geometric Design II. Academic Press 1992. Pottmann, Helmut: General offset surfaces. Neural, Parallel & Scientific Computations 5, 55-80, 1997. Smukler, Micah: Geometry, Topology and aplications of the Minkowski Product and Action. Harvey Mudd College. Senior thesis, 2003. ˇ v Plzni, disertaˇcní práce, 2006. Tomiczková, Svˇetlana: Minkowského operace a jejich aplikace. ZCU Wallner, J., Sakkalis, T., Maekawa, T., Pottmann, H., Yu, G.: Self-Intersection of Offset Curves and Surfaces. March 30, 2001. Weiner, Ian; Gu, Weiqing: Minkowski geometric algebra of quaternion sets. International Journal of Pure and Applied Mathematics, Vol. 3, No.4: 385-411, 2002. Zhenyu Li: Compaction Algorithms for Non-Convex Polygons and Their Applications. Massachusetts: Harvard University. PhD. thesis, 1994. Svˇetlana Tomiczková


Závˇer

Dˇekuji za pozornost



Minkowského operace a jejich aplikace

Recommend Documents