Jarvis-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. tammikuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 9 muokkausta .

Jarvis-algoritmi (tai Jarvis-läpikulkualgoritmi tai lahjapakkausalgoritmi) määrittää joukon elementtejä, jotka muodostavat kuperan rungon tälle joukolle. Menetelmä voidaan kuvitella käärimällä laudalle lyöty naulasarja köydellä. Algoritmi ajaa ajassa , missä on pisteiden kokonaismäärä tasossa, on kuperan rungon pisteiden lukumäärä. $O(nh)$ $n$ $h$

Algoritmin kuvaus

Olkoon joukko pisteitä annettu . Vasemmanpuoleisin alapiste otetaan alkupisteeksi (se löytyy tavanomaisen kaikkien pisteiden läpiviennin takaa), se on täsmälleen kuperan rungon yläosa. Seuraava piste ( ) on piste, jolla on pienin positiivinen napakulma suhteessa origopisteeseen. Tämän jälkeen jokaiselle pisteelle (2<i<=|P|) vastapäivään etsitään sellainen piste etsimällä jäljellä olevien pisteiden joukosta (+ alin vasen), jossa suurin viivojen ja välinen kulma on muodostunut . Se on kuperan rungon seuraava kärki. Tässä tapauksessa itse kulmaa ei haeta, vaan vain sen kosini etsitään säteiden välisen skalaaritulon kautta ja , jossa on viimeinen löydetty minimi, on edellinen minimi ja on seuraavan minimin ehdokas. Uusi minimi on piste, jossa kosini saa pienimmän arvon (mitä pienempi kosini, sitä suurempi sen kulma). Kuperan rungon kärkien etsiminen jatkuu, kunnes . Sillä hetkellä, kun kuperan rungon seuraava piste osuu yhteen ensimmäisen kanssa, algoritmi pysähtyy - kupera runko rakennetaan. $P=\{\,p_{1},p_{2},\ldots ,p_{n}\,\}$ $p_{1}$ $Päällä)$ $p_{2}$ $p_{1}$ $p_{i}$ $p_{{i+1}}$ $Päällä)$ $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}$

Pseudokoodi

Jarvis (P) 1) p[1] = joukon P vasen alin piste; 2) p[2] = naapuripiste kohdasta p[1] oikealle (sijaitsee pienimmän positiivisen napakulman kautta) 3) i = 2; 4) tee : (a) jokaiselle pisteelle j 1:stä |P|:iin, lukuun ottamatta niitä, jotka ovat jo kuperassa rungossa, mutta mukaan lukien p[1] p[i+1] = piste_min_cos(p[i-1], p[i], P[j]); //piste, joka muodostaa minimikosinin viivan p[i-1]p[i] kanssa, (b)i = i + 1; kun taas p[i] != p[1] 5) paluu p;

Analyysi

Silmukka (4) suoritetaan kerran, kun taas silmukka (a) suoritetaan joka kerta . Kaikki muut toiminnot suoritetaan . Siksi algoritmi toimii tai pahimmassa tapauksessa, kun kaikki pisteet putoavat kuperaan runkoon. $h$ $\Theta(n)$ $O(1)$ $\Theta (hn)$ $\Theta (n^{2})$

Katso myös

Grahamin algoritmi
Chanin algoritmi

Kirjallisuus

Preparata F., Shaimos M. Laskennallinen geometria Johdanto. - M .: Mir, 1989. - 478 s.
Laszlo M. Laskennallinen geometria ja tietokonegrafiikka C++:ssa. - M .: BINOM, 1997. - 304 s.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmit. Rakentaminen ja analyysi = Johdatus algoritmeihin. - 2. painos - "Williams", 2005. - 1296 s.

Linkit

c++ toteutus