Hitra konveksna ovojnica

Iz MaFiRaWiki

Vsebina


Konveksna ovojnica množice točk je najmanjša konveksna množica, ki vsebuje vse točke. Konveksna ovojnica trodimenzionalne množice točk je konveksni polieder. Tu bomo predstavili računanje konveksne ovojnice v trodimenzionalnem prostoru. Najlaže si problem predstavljamo kot zavijanje darila: papir bo potegnjen čez vse; tam, kjer je v darilu prazen prostor, papir ne bo upognjen navznoter. Robovi so elementi konveksne ovojnice. Za reševanje problema bomo uporabili algoritem Quickhull.

Algoritem Quickhull

Konveksna ovojnica je najmanjši možni polieder, da so bodisi vse točke notranje bodisi so elementi konveksne ovojnice. Slikovni prikaz:

Slika:KonOv.JPG

Algoritem je naslednji:

  • najprej si izberemo neko ploskev:
    • za izhodišče si izberemo najbolj levo točko,recimo točko A (ima najmanjšo x-koordinato)
    • poiščemo najbolj desno točko, točko B (ima največjo x-koordinato)
    • točki A in B povežemo
    • izmed vseh danih točk poiščemo tisto, ki je najbolj oddaljena od daljice AB; označimo jo s C
    • povežemo točke A, B in C, da dobimo ploskev trikotne oblike;
  • pregledamo vse točke, ki so nad oz. pod ploskvijo in izberemo najbolj oddaljeno za novo oglišče:

Izberemo torej tiste točke, ki ne ležijo v tej ravnini. To preverimo z izračunom determinante:

\begin{vmatrix} x_A & x_B & x_C \\ y_A & y_B & y_C \\ z_A & z_B & z_C \\ \end{vmatrix}

kjer je A=(xA, yA, zA), B=(xB, yB, zB), C=(xC, yC, zC).
Če točke ležijo v isti ravnini, potem je determinanta enaka 0. Torej, v našem primeru mora biti determinanta različna od 0.

  • ovojnico "raztegnemo" do novega oglišča;
  • točke, ki so znotraj ovojnice, odstranimo:

To ugotovimo tako, da s pomočjo determinante izračunamo volumen poliedra P0P1P2P3, kjer je P0=(x0, y0, z0), P1=(x1, y1, z1), P2=(x2, y2, z2) in P3=(x3, y3, z3):

\begin{vmatrix} x_0 & x_1 & x_2 & x_3 \\ y_0 & y_1 & y_2 & y_3 \\  z_0 & z_1 & z_2 & z_3 \\ 1 & 1 & 1 & 1 \\ \end{vmatrix}
Izračunano vrednost moramo pomnožiti še z 1/6.

Če je volumen pozitiven, potem je trikotnik P0P1P2 pozitivno orientiran (točke ležijo v nasprotni smeri urinega kazalca), ko ga "gledamo" iz točke P3. Povedano drugače: to je normala trikotnika P0P1P2 po načelu desnega vijaka.
Če je volumen negativen, potem normala trikotnika P0P1P2 kaže v notranjost poliedra. V našem primeru želimo, da je volumen negativen, saj tako točko P3 lahko odstranimo.

  • ponavljamo, dokler ne pregledamo vseh preostalih točk.

Primer

Dano imamo množico točk v prostoru:

Slika:QH1.JPG

Za ploskev si izberemo trikotnik ABC in pogledamo ostale točke. Najbolj oddaljena je točka D, zato jo povežemo z oglišči trikotnika ABC:

Slika:QH2.JPG

Sedaj za ploskev izberemo trikotnik ACD. Pregledamo ostale točke. Najbolj oddaljena je točka E, ki jo povežemo z oglišči trikotnika ACD. Ker točka C leži v isti ravnini kot trikotnik EAB, jo odstranimo in povežemo oglišči E in B:

Slika:QH31.JPG

Tokrat za ploskev izberemo trikotnik EBD. Oglišča tega trikotnika povežemo še s preostalo točko F:

Slika:QH41.JPG

Ker točk nimamo več, je postopek končan.

Časovna zahtevnost

V najslabšem primeru je časovna zahtevnost algoritma O(n^2), v praksi pa se je pokazalo, da ni slabši od O(n log n).

Dodatni komentar

Pri v virih uporabljenem programu Quickhull je računanje konveksne ovojnice le ena izmed možnosti, ki jo ta program nudi. S tem programom lahko računamo še Delaunay-jevo triangulacijo, Voronoi-jev diagram; generira polprostore in tudi naključno množico točk, ki jo potrebujemo za določen problem. Program deluje v 2D, 3D, 4D in večdimenzionalnem prostoru.

Primeri

Vir

Glej tudi

Osebna orodja