Jarvis algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 januari 2015; kontroller kräver 9 redigeringar .

Jarvis-algoritmen (eller Jarvis-traversalalgoritmen, eller presentinpackningsalgoritmen) bestämmer en sekvens av element i uppsättningen som bildar ett konvext skrov för denna uppsättning. Metoden kan föreställas som att linda en uppsättning spikar inslagna i en bräda med ett rep. Algoritmen körs i tiden , där är det totala antalet punkter på planet, är antalet punkter i det konvexa skrovet. $O(nh)$ $n$ $h$

Beskrivning av algoritmen

Låt en uppsättning poäng ges . Den nedersta punkten längst till vänster tas som den initiala punkten (den kan hittas bakom den vanliga passagen genom alla punkter), det är exakt toppen av det konvexa skrovet. Nästa punkt ( ) är den punkt som har den minsta positiva polära vinkeln i förhållande till punkten som origo. Därefter, för varje punkt (2<i<=|P|) moturs, söker man efter en sådan punkt genom att hitta bortom bland de återstående punkterna (+ den lägsta vänstra), där den största vinkeln mellan linjerna och kommer att vara bildas . Det blir nästa hörn av det konvexa skrovet. I det här fallet söks inte själva vinkeln, utan endast dess cosinus söks genom skalärprodukten mellan strålarna och , där är det senast hittade minimumet, är det föregående minimumet och är kandidaten för nästa minimum. Det nya minimumet kommer att vara den punkt där cosinus kommer att ta det minsta värdet (ju mindre cosinus, desto större vinkel). Att hitta hörnen på det konvexa skrovet fortsätter tills . I det ögonblicket, när nästa punkt i det konvexa skrovet sammanfaller med det första, stannar algoritmen - det konvexa skrovet byggs. $P=\{\,p_{1},p_{2},\ldots ,p_{n}\,\}$ $p_{1}$ $På)$ $p_{2}$ $p_{1}$ $pi}$ $p_{{i+1}}$ $På)$ $p_{{i-1}}p_{{i}}$ $p_{{i}}p_{{i+1}}$ $p_{{i-1}}p_{{i}}$ $p_{{i}}p'_{{i+1}}$ $pi}}$ $p_{{i-1}}$ $p'_{{i+1}}$ $p_{{i+1}}\neq p_{1}$

Pseudokod

Jarvis (P) 1) p[1] = den nedre punkten längst till vänster i mängden P; 2) p[2] = angränsande punkt från p[1] till höger (belägen genom den minsta positiva polära vinkeln) 3) i = 2; 4) gör : (a) för varje punkt j från 1 till |P|, förutom de som redan finns i det konvexa skrovet, men inklusive p[1] p[i+1] = punkt_med_min_cos(p[i-1], p[i], P[j]); //punkt som bildar den minimala cosinus med linjen p[i-1]p[i], (b)i = i + 1; medan p[i] != p[1] 5) returnera p;

Analys

Loop (4) kommer att exekveras en gång, medan loop (a) exekveras varje gång för . Alla andra operationer utförs i . Därför fungerar algoritmen för eller i värsta fall, när alla punkter faller in i det konvexa skrovet. $h$ $\Theta(n)$ $O(1)$ $\Theta (hn)$ $\Theta (n^{2})$

Se även

Grahams algoritm
Chans algoritm

Litteratur

Preparata F., Shaimos M. Computational Geometry En introduktion. — M .: Mir, 1989. — 478 sid.
Laszlo M. Beräkningsgeometri och datorgrafik i C++. - M. : BINOM, 1997. - 304 sid.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmer. Konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - "Williams", 2005. - 1296 sid.

Länkar

c++ implementering