Jarvis algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2015. január 19-én felülvizsgált verziótól ; az ellenőrzések 9 szerkesztést igényelnek .

A Jarvis-algoritmus (vagy a Jarvis-bejárási algoritmus vagy az ajándékcsomagoló algoritmus) meghatározza a halmaz elemeinek sorozatát, amelyek konvex burkot alkotnak ehhez a halmazhoz. A módszer úgy képzelhető el, hogy egy deszkába vert szögkészletet kötéllel becsomagolunk. Az algoritmus időben fut , ahol a síkon lévő pontok teljes száma, a konvex hajótest pontjainak száma. $O(nh)$ $n$ $h$

Az algoritmus leírása

Legyen adott egy ponthalmaz . A bal szélső alsó pontot vesszük kiindulási pontnak (a szokásos áthaladás mögött minden ponton található), ez pontosan a domború hajótest teteje. A következő pont ( ) az a pont, amelynek a legkisebb pozitív poláris szöge van az origó ponthoz képest. Ezt követően minden ponthoz (2<i<=|P|) az óramutató járásával ellentétes irányban keresünk egy olyan pontot, ahol a fennmaradó pontok között (+ a legalacsonyabb balra) megkeresünk egy olyan pontot , amelyben a és az egyenesek közötti legnagyobb szög lesz . alakult . Ez lesz a konvex hajótest következő csúcsa. Ebben az esetben magát a szöget nem keresi, hanem csak a koszinuszát keresi a sugarak közötti skaláris szorzaton keresztül, és ahol az utolsó talált minimum, az előző minimum, és a következő minimum jelöltje. Az új minimum az a pont lesz, ahol a koszinusz a legkisebb értéket veszi fel (minél kisebb a koszinusz, annál nagyobb a szöge). A konvex hajótest csúcsainak megtalálása addig folytatódik, amíg . Abban a pillanatban, amikor a konvex hajótest következő pontja egybeesik az elsővel, az algoritmus leáll - a konvex hajótest megépül. $P=\{\,p_{1},p_{2},\ldots ,p_{n}\,\}$ $p_{1}$ $Tovább)$ $p_{2}$ $p_{1}$ $p_{i}$ $p_{{i+1}}$ $Tovább)$ $p_{{i-1}}p_{{i}}$ $p_{{i}}p_{{i+1}}$ $p_{{i-1}}p_{{i}}$ $p_{{i}}p'_{{i+1}}$ $p_{{i}}$ $p_{{i-1}}$ $p'_{{i+1}}$ $p_{{i+1}}\neq p_{1}$

Pszeudokód

Jarvis (P) 1) p[1] = a P halmaz bal szélső alsó pontja; 2) p[2] = p[1]-től jobbra szomszédos pont (a minimális pozitív poláris szögön keresztül) 3) i = 2; 4) tegye : (a) minden j pontra 1-től |P|-ig, kivéve azokat, amelyek már a konvex hajótestben vannak, de beleértve a p[1]-et is. p[i+1] = pont_min_cos-szal(p[i-1], p[i], P[j]); //pont, amely a minimális koszinuszot alkotja a p[i-1]p[i] egyenessel, (b)i = i + 1; míg p[i] != p[1] 5) return p;

Elemzés

A ciklus (4) egyszer, míg az (a) ciklus minden alkalommal végrehajtásra kerül . Az összes többi műveletet a . Ezért az algoritmus akkor működik, vagy a legrosszabb esetben, amikor minden pont beleesik a konvex hajótestbe. $h$ $\Theta(n)$ $O(1)$ $\Theta (hn)$ $\Theta (n^{2})$

Lásd még

Graham algoritmusa
Chan algoritmusa

Irodalom

Preparata F., Shaimos M. Számítógépes geometria Bevezetés. — M .: Mir, 1989. — 478 p.
M. László Számítógépes geometria és számítógépes grafika C++ nyelven. - M. : BINOM, 1997. - 304 p.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmusok. Konstrukció és elemzés = Bevezetés az algoritmusokba. - 2. kiadás - "Williams", 2005. - 1296 p.

Linkek

c++ megvalósítás