Algoritem zavijanje darila

Iz MaFiRaWiki

(Preusmerjeno iz Gift wrapping algoritem)

Algoritem Zavijanje darila (Gift wrapping algorithm) je enostaven algoritem za računanje konveksne ovojnice dane množice točk.
V dvodimenzionalnem prostoru je ta algoritem znan kot Jarvisov obhod.

Vsebina

Opis

  • Začnemo v točki p0, za katero vemo, da je element konveksne ovojnice - izberemo najbolj levo točko. Hkrati števec i postavimo na 0.
  • Točko pi+1 izberemo tako, da so vse ostale točke na desni strani daljice pipi+1.
  • Števec i povečamo za 1.
  • Postopek ponavljamo, dokler ne pridemo spet do začetne točke.

Slika:jarvis.JPG

Primer

Radi bi določili konveksno ovojnico na tej množici:

Slika:jarvis1.JPG

Postopek

  • Za izhodiščno točko izberemo najbolj levo točko (točka A) in poiščemo naslednjo tako, da so vse ostale na desni strani ter ju povežemo (točka B):

Slika:jarvis2.JPG

  • Sedaj postane točka B začetna točka in ponovimo postopek. Naslednja ustrezna točka je točka C:

Slika:jarvis3.JPG

  • Začetna točka postane točka C. Ponovimo postopek in ustrezna točka je točka D:

Slika:jarvis4.JPG

  • Začetna točka je sedaj točka D. Ponovimo isti postopek, naslednja ustrezna točka je točka E:

Slika:jarvis5.JPG

  • Začetna točka je tokrat točka E. Spet isti postopek:

Slika:jarvis6.JPG

Ker je končna točka enaka izhodiščni točki, smo postopek zaključili. Dobili smo konveksno ovojnico.

Časovna zahtevnost

Časovna zahtevnost algoritma je O(nh), kjer je n število vseh točk, h pa število točk, ki so elementi konveksne ovojnice.

Glej tudi

  • Animacija algoritma zavijanja darila je tukaj.

Javanska koda je dostopna na isti strani kot animacija, le da je treba v razdelku Algorithms klikniti na Gift Wrap.

Vir

http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

Osebna orodja