Algoritem zavijanja darila (konveksna ovojnica)

Algoritem zavijanja darila (konveksna ovojnica)

Avtor: Maja Kapitler

Problem

Želimo poiskati konveksno ovojnico za podano množico točk v dveh dimenzijah s pomočjo algoritma Algoritem zavijanja darila oziroma Jarvisov obhod.


Zgled:

(http://www2.nauk.si/files/640/Zgled.png)


Konveksna in konkavna množica

Konveksna množica je v geometriji množica točk, za katero velja, da pri poljubni izbiri točk in iz te množice, daljica v celoti leži v tej množici.


Zgled:

(http://www2.nauk.si/files/640/KonveksnaMnožica.png)


Konveksna in konkavna množica

Če lahko v dani množici izberemo taki točki in , da daljica ne leži v celoti v dani množici, potem ta množica ni konveksna. Nekonveksno množico imenujemo konkavna.


Zgled:

(http://www2.nauk.si/files/640/KonkavnaMnožica.png)


Konveksna ovojnica

Definicija konveksne ovojnice: Konveksna ogrinjača ali ovojnica ali lupina je najkrajša možna povezava točk tako, da so vse točke na notranji strani ali pa elementi konveksne ovojnice.

Opomba: V nadaljevanju bo na prosojnicah le uporaba izraza konveksna ovojnica.




Problem iskanja konveksne ovojnice si lahko predstavljamo na sledeči način, in sicer:

Imamo nekaj žebljičkov zapičenih v desko - to so točke iz . Okoli njih napnemo elastiko tako, da so vsi žebljički v njej, nato pa jo spustimo, da se napne okoli žebljičkov. Žebljički, ki se jih elastika dotika, so elementi konveksne ovojnice.

Zgled z žebljički

Zgled:

  • Imamo neko množico točk:

    (http://www2.nauk.si/files/640/MnožicaTočk2.png)

Zgled z žebljički

  • Okoli njih napnemo elastiko tako, da so vse točke v njej:

    (http://www2.nauk.si/files/640/Elastika2.png)

Zgled z žebljički

  • Elastiko spustimo:

    (http://www2.nauk.si/files/640/ElastikaSpustimo2.png)
  • Z zeleno barvo je označena konveksna ovojnica te množice točk. Točke, ki se jih elastika dotika, so elementi konveksne ovojnice.

Primeri uporabe

S problemom iskanja konveksne ovojnice se v praksi najpogosteje srečujemo na področjih računalniškega vida in geometrije (npr. za zajem območja gibanja).

Še nekaj primerov, kjer se uporabljajo algoritmi za iskanje konveksne ovojnice:

  • iskanje vzorcev (za prepoznavanje oblik),
  • iskanje največje razdalje med pari točk v podani množici točk (največjo razdaljo bo vedno tvoril nek par točk iz konveksne ovojnice),
  • statistika ...

Algoritmi

Za reševanje poznamo več možnih algoritmov:

  • groba sila,
  • Jarvisov obhod,
  • Grahamov pregled,
  • inkrementalna metoda,
  • algoritem tvorbe konveksne lupine s strategijo "deli in vladaj",
  • aproksimacijski algoritem.


    Osredotočimo se na Jarvisov obhod.

Jarvisov obhod - Algoritem zavijanja darila

  • angl. Jarvis March, Gift wrapping algorithm

  • Dani množici točk poiščemo konveksno ovojnico v dveh ali več dimenzijah. Osredotočimo se na dve dimenziji.

  • Algoritem se imenuje po R. A. Jarvis-u (objavil leta 1973).

  • Časovna zahtevnost:

    • število vseh točk,
    • število točk, ki ležijo na konveksni ovojnici.

  • V najslabšem primeru so vse podane točke tudi elementi konveksne ovojnice (). Časovna zahtevnost: .

    • Primer: vse točke ležijo na krožnici ...

      (http://www2.nauk.si/files/640/Krožnica.png)


Jarvisov obhod - Algoritem zavijanja darila

  • Časovna zahtevnost je torej odvisna od števila točk konveksne ovojnice.

  • V primerjavi z ostalimi algoritmi se Jarvisov obhod splača uporabiti, ko je majhen ali pa je v primerjavi z zelo majhen. Časovna zahtevnost: , ko je moč konveksne množice v primerjavi z močjo cele množice zelo majhna.

Algoritem

  • Podano imamo neko množico točk .

  • Za začetno/izhodiščno točko izberemo točko z najmanjšo koordinato (lahko tudi točko z najmanjšo koordinato). Vemo, da ta točka zagotovo leži na konveksni ovojnici (to bi lahko dokazali s protislovjem). Označimo jo s .

    (http://www2.nauk.si/files/640/Algoritem1.png)
    Začetna množica točk


Algoritem

  • Poiščemo še vse preostale točke, ki pripadajo konveksni ovojnici. Točke iščemo v nasprotni smeri urinega kazalca.

    Postopek:

    • Skozi točko naredimo vzporednico z osjo ().

    • Iz točke povlečemo še premice skozi vse preostale točke (to so kandidati za točke na konveksni ovojnici).

    • Izračunamo vse kote in hkrati poiščemo najmanjši kot.

    • Naslednja točka bo tista točka, katere premica () oklepa najmanjši kot s premico . Označimo jo s .

Algoritem


(http://www2.nauk.si/files/640/Algoritem2.png)
1. korak


Algoritem

  • Podobno poiščemo naslednjo točko - označimo s .

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

    (http://www2.nauk.si/files/640/Algoritem3.png)
    2. korak


Algoritem

  • Podobno poiščemo še vse preostale točke konveksne ovojnice.

  • i-ti korak:

    • Iščemo -to točko (označimo s ).

    • Iz točke povlečemo premice skozi vse preostale točke, ki še niso elementi konveksne ovojnice (opomba: tudi skozi točko ).

    • Naslednja točka konveksne ovojnice - , bo tista točka, katere premica () oklepa najmanjši kot s premico .


  • Opomba:

    • Če bi na izbrani premici ležalo več točk (točke so kolinearne), je naslednja točka tista, ki je najbližja prejšnji točki.


  • Postopek ponavljamo toliko časa, dokler ne pridemo nazaj v začetno točko .

Algoritem


(http://www2.nauk.si/files/640/Algoritem4.png)
3. korak


Algoritem


(http://www2.nauk.si/files/640/Algoritem5.png)
4. korak


Algoritem


(http://www2.nauk.si/files/640/Algoritem6.png)
5. korak


Algoritem


(http://www2.nauk.si/files/640/Algoritem7.png)
6. korak


Algoritem - rezultat

  • Rezultat:

    (http://www2.nauk.si/files/640/Algoritem8.png)


Implementacija v Python-u

Spodaj je na voljo povezava do algoritma napisanega v programskem jeziku Python.

Program v Pythonu

Uporaba in razlaga algoritma

Spodaj je na voljo povezava do filmčka s prikazom delovanja algoritma na 15 naključno zgeneriranih točkah (majhen problem).

Povezava na filmček 1


Spodaj je na voljo povezava do filmčka s prikazom delovanja algoritma na 50 naključno zgeneriranih točkah (velik problem).

Povezava na filmček 2


Spodaj je na voljo povezava do filmčka s prikazom delovanja algoritma v GeoGebri.

Povezava na filmček 3

Zgled delovanja algoritma



Zgled delovanja algoritma



Zgled delovanja algoritma

"Zavijanje darila"

Zakaj se algoritem imenuje algoritem "Zavijanja darila"?

  • V "darilo" (nek skupek) moramo spraviti te točke, katere dobimo podane na začetku. Predstavljamo si, kot da bi s trakcem obkrožili vse te točke.

    (http://www2.nauk.si/files/640/AlgoritemZavijanjaDarila_1.png)
  • Načeloma gre za problem v treh dimenzijah, kjer bi morali točke "obkrožiti" z ravnino. V našem primeru pa se ukvarjamo s problemom v dveh dimenzijah.
  • Vzamemo najbolj izpostavljeno točko, torej točko z najmanjšo koordinato ter v tej točki fiksiramo (pritrdimo) dolgo vrvico (trakec).

    (http://www2.nauk.si/files/640/AlgoritemZavijanjaDarila2.png)

"Zavijanje darila"

  • Vrvico iz začetne točke (v nadaljevanju bo to trenutna točka) potegnemo gor. Točka, na kateri se bo ujela, bo naslednja točka (tista točka, katere premica oklepa najmanjši kot s prejšnjo premico).

    (http://www2.nauk.si/files/640/AlgoritemZavijanjaDarila3.png)
  • Nato nadaljujemo. Vrvico potegnemo gor, dokler se ne ujame na naslednji točki.

    (http://www2.nauk.si/files/640/AlgoritemZavijanjaDarila4.png)

"Zavijanje darila"

  • To ponavljamo, dokler ne pridemo nazaj v začetno točko oziroma, dokler ne obkrožimo celega darila (ki tako vsebuje vse točke).

    (http://www2.nauk.si/files/640/AlgoritemZavijanjaDarila5.png)

Kviz - 1. vprašanje

Ali je naslednja množica konveksna ali konkavna?


(http://www2.nauk.si/files/640/KonveksnaMnožica.png)



konkavna
konveksna


Pravilno

Čestitam! Odgovor je pravilen.

Naprej

Napačno

Še enkrat si oglej definicijo konveksne in konkavne množice.

Ponovi

Kviz - 2. vprašanje

Definicija konveksne ovojnice:
Konveksna ovojnica je

možna povezava točk tako, da so vse točke na

strani ali pa elementi konveksne ovojnice.

Preveri

Pravilno

Čestitam! Odgovor je pravilen.

Naprej

Napačno

Še enkrat si oglej definicijo konveksne ovojnice.

Ponovi

Pravilno

Čestitam! Odgovor je pravilen.

Naprej

Napačno

Še enkrat si oglej definicijo konveksne ovojnice.

Ponovi

Kviz - 3. vprašanje

Poveži:

Pričakovana časovna zahtevnost
Minimalna časovna zahtevnost
Maksimalna časovna zahtevnost

Opomba:
število vseh točk,
število točk, ki ležijo na konveksni ovojnici.


Preveri

Pravilno

Čestitam! Odgovor je pravilen.

Naprej

Napačno

Še enkrat si preberi o časovni zahtevnosti.

Ponovi

Kviz - 4. vprašanje

V algoritmu lahko kot začetno točko izberemo točko:
(pravilnih je več odgovorov)



Preveri

Pravilno

Čestitam! Odgovor je pravilen.

Naprej

Napačno

Še enkrat si oglej algoritem.

Ponovi

Kviz - 5. vprašanje

V algoritmu na vsakem koraku poračunamo kote.

(http://www2.nauk.si/files/640/Algoritem2.png)
1. korak


Naslednja točka bo tista točka, katere premica s prejšnjo premico oklepa:

največji kot
topi kot
ostri kot
najmanjši kot




Pravilno

Čestitam! Odgovor je pravilen.

Naprej

Napačno

Še enkrat si oglej algoritem.

Ponovi

Kviz - 6. vprašanje

Algoritem traja dokler ne pridemo nazaj v:

prejšnjo točko
začetno točko



Pravilno

Čestitam! Odgovor je pravilen.

Naprej

Napačno

Še enkrat si oglej algoritem.

Ponovi

Kviz - 7. vprašanje

(http://www2.nauk.si/files/640/Algoritem8.png)
Rezultat


Katere točke so elementi konveksne ovojnice?



Preveri

Pravilno

Čestitam! Odgovor je pravilen.

Naprej

Napačno

Še enkrat si oglej algoritem.

Ponovi

Viri

0%
0%