Za dano množico točk poišči KONVEKSNO OGRINJAČO s pomočjo JARVISOVEGA OBHODA.

KONVEKSNA MNOŽICA

KONVEKSNA OGRINJAČA

Imamo npr. spodnjo množico točk:

Predstavljamo si, da okoli točk napnemo elastiko (moder kvadrat):

Spustimo elastiko:

• Z modro je označena KONVEKSNA OGRINJAČA naše množice.

Algoritmi za iskanje konveksne ogrinjače se uporabljajo v praksi v naslednjih primerih:

• Računalniški vid - npr. za zajem območja gibanja,
• GIS (zemljepisni informacijski sistem) - določanje območij (npr. določanje poplavnih območij),
• iskanje vzorcev - prepoznavanje oblik,
• iskanje največje razdalje med pari točk v podani množici točk - vedno bo največjo razdaljo tvoril nek par točk iz konveksne ogrinjače,
• statistika,
• ...

Izberemo si začetno točko T₀:

• Za začetno točko vzamemo točko iz množice D, za katero zagotovo vemo, da je del konveksne ogrinjače.

  • Vemo, da je točka z najmanjšo koordinato y zagotovo del konveksne ogrinjače. Če je takih točk več (so seveda vse del konveksne ogrinjače), vzamemo za začetno točko npr. najbolj levo.
  • Slika
• Naslednje točke, ki so del konveksne ogrinjače, iščemo v nasprotni smeri urinega kazalca.

Poiščemo naslednjo točko, ki je del konveksne ogrinjače

• Skozi točko T₀ naredimo vzporednico z x-osjo, premico poimenujemo p₀.
• Predstavljamo si, da iz točke T₀ povlečemo premice skozi vse preostale točke.
• Izberemo tisto točko (poimenujemo jo T₁), katere premica (poimenujemo jo p₁) oklepa najmanjši kot s premico p₀.

• Slika

  • Za lažjo predstavo: Izberemo tisto premico (posledično točko), da so vse točke na eni strani premice (bodisi nad premico, bodisi pod premico).

Poiščemo naslednjo točko konveksne ogrinjače (T₂)

S pomočjo točke T₁ poiščemo naslednjo točko, ki je del konveksne ogrinjače.

• Izberemo tisto točko (T₂), katere premica s premico p₂ oklepa najmanjši kot.

  • Izpustimo računanje kotov za tiste točke, ki so že del konveksne ogrinjače. Ne izpustimo le začetne točke, ker se na koncu vrnemo v le-to.
  • Izračunati moramo vse kote in poiskati najmanjši kot.
• Slika

Podobno poiščemo točko T₃ in vse naslednje točke, ki so del konveksne ogrinjače.

Splošni korak:

• Iščemo i-to točko (T_i) konveksne ogrinjače.

  • i je različen od 0 in 1.
• Predstavljamo si, da skozi točko T_i-1 povlečemo premice skozi vse ostale točke, ki še niso del konveksne ogrinjače. Premico iz T_i-1 povlečemo tudi skozi točko T₀.

• Za naslednjo točko (T_i) konveksne ogrinjače vzamemo tisto točko, katere premica oklepa najmanjši kot s premico p_i-1.

  • Če na izbrani premici leži več točk, izberemo tisto, ki je najbližja prejšnji točki konveksne ogrinjače (T_i-1).

Postopek ponavljamo toliko časa, dokler ne pridemo nazaj v točko T₀.

• Slika

Časovna zahtevnost algoritma je O(nh).

• n je moč množice (število vseh točk).
• h je moč konveksne ogrinjače (število točk, ki sestavljajo konveksno ogrinjačo).

Razlaga:

Za vsako točko, ki je del konveksne ogrinjače porabimo:

• O(1) za primerjanje izračunanih kotov,
• O(n) za iskanje najmanjšega kota,
• O(n) skupni čas.

Če je h število točk, ki sestavljajo konveksno ogrinjačo, potem je celotna časovna zahtevnost O(nh).

• V najslabšem primeru so vse točke množice del konveksne ogrinjače. Takrat je časovna zahtevnost O(n²).

  • Npr., ko so vse točke množice razporejene na isti krožnici.

• Algoritem je izredno hiter (O(n)), kadar je moč konveksne množice v primerjavi z močjo celotne množice zelo majhna.

Kaj narediti, ko tekom izvajanja algoritma naletimo na spodnji primer?

Na premici, ki s premico p_i (v spodnjem primeru premico p₂) oklepa najmanjši kot, leži več točk.

V našem primeru tako za naslednjo točko (točko T₃) izberemo točko, ki leži na premici, ki s premico p₂ oklepa najmanjši kot in je najbližnja točki T₂.

Sedaj lahko postopek nadalaljujemo.

Ali spodnja slika predstavlja konveksno množico?

Katere točke sestavljajo konveskno ogrinjačo?

Kakšne časovne zahtevnosti je algoritem Jarvisov obhod?

• n -> moč celotne množice
• h -> moč konveksne ogrinjače

• Definicije konveksne ogrinjače in konveksne množice:

  • http://www.fmf.uni-lj.si/~juvan/Racunalnistvo3/gradivo/konveksnost_mnoz.tex

• Uporaba konveksne ogrinjače v praksi:

  • http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/Chen_hull/applications.htm

• Algoritem:

  • http://www.chrisharrison.net/projects/convexHull/index.htm
  • http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
  • http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/jarvisMarch.htm
  • http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_cs_07w/Webprojects/Zhaobo_hull/index.html