Jarvis algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 19. januar 2015; checks kræver 9 redigeringer .

Jarvis-algoritmen (eller Jarvis-traversal-algoritmen eller gaveindpakningsalgoritmen) bestemmer en sekvens af elementer i sættet , der danner et konveks skrog for dette sæt. Metoden kan forestilles som at vikle et sæt søm ind i et bræt med et reb. Algoritmen kører i tid , hvor er det samlede antal punkter på flyet, er antallet af punkter i det konvekse skrog. $O(nh)$ $n$ $h$

Beskrivelse af algoritmen

Lad et sæt point gives . Det nederste punkt længst til venstre tages som startpunktet (det kan findes bag den sædvanlige passage gennem alle punkter), det er præcis toppen af det konvekse skrog. Det næste punkt ( ) er det punkt, der har den mindste positive polære vinkel i forhold til punktet som udgangspunkt. Derefter søges et sådant punkt for hvert punkt (2<i<=|P|) mod uret ved at finde forbi blandt de resterende punkter (+ det nederste venstre), hvori den største vinkel mellem linjerne og vil være dannet . Det bliver det næste hjørne af det konvekse skrog. I dette tilfælde søges ikke selve vinklen, men kun dens cosinus søges gennem skalarproduktet mellem strålerne og , hvor er det sidste minimum fundet, er det forrige minimum, og er kandidaten til det næste minimum. Det nye minimum vil være det punkt, hvor cosinus vil have den mindste værdi (jo mindre cosinus, jo større er dens vinkel). At finde spidserne af det konvekse skrog fortsætter indtil . I det øjeblik, når det næste punkt i det konvekse skrog falder sammen med det første, stopper algoritmen - det konvekse skrog er bygget. $P=\{\,p_{1},p_{2},\ldots ,p_{n}\,\}$ $p_{1}$ $På)$ $p_{2}$ $p_{1}$ $p_{i}$ $p_{{i+1}}$ $På)$ $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}$

Pseudokode

Jarvis (P) 1) p[1] = det nederste punkt til venstre i mængden P; 2) p[2] = nabopunkt fra p[1] til højre (placeret gennem den mindste positive polære vinkel) 3) i = 2; 4) gør : (a) for hvert punkt j fra 1 til |P|, undtagen for dem, der allerede er i det konvekse skrog, men inklusive p[1] p[i+1] = point_with_min_cos(p[i-1], p[i], P[j]); //punkt, der danner minimum cosinus med linjen p[i-1]p[i], (b)i = i + 1; mens p[i] != p[1] 5) returnere p;

Analyse

Loop (4) udføres én gang, mens loop (a) udføres hver gang for . Alle andre operationer udføres i . Derfor virker algoritmen for eller i værste fald, når alle punkter falder ind i det konvekse skrog. $h$ $\Theta(n)$ $O(1)$ $\Theta (hn)$ $\Theta (n^{2})$

Se også

Grahams algoritme
Chans algoritme

Litteratur