Kübik hacminin iki yüzünü bağlayan bir çizgi bulun

Question

Voksellerle dolu N³ çözünürlüğünün hacimsel bir küpünü hayal edin. Küp tamamen doldurulabilir veya kıvrımlı "tüneller" veya duvarlar içerebilir - ya da sadece birkaç kaçak voksel; Şimdi, sınırlayıcı küpün altı yüzünden herhangi birini seçiyoruz ve bu iki yüzünü, içine herhangi bir voksel basmadan bağlayan bir çizgi bulmaya çalışıyoruz. Böyle bir çizgi varsa, yüzler birbirini görebilir, aksi halde tamamen tıkanırlar.

Soruma şudur: böyle bir satır çizilebiliyorsa hızlıca ayırt etmek için bir O (n) (veya daha iyi) algoritması var mı? Çizginin kesin parametreleri önemli değil.

Answer 1

A Voxel küp Rubik Cube, voksel yapısı gibi görünecektir böylece, her ilgili blokta bağlayan hat içinde çizmek gerekiyor bir taraftan diğer tarafa bir çizgi çizmek için, blokların bir 3D matristir bir sonraki aşamada, çizgiler, küp boyunca bir sürekli çizgi oluşturur.

Aşağıdaki algoritma iyi uygulandığında iyi çalışır, çünkü küp içinde yerel koordinatlarda çalışacağınız için, küpün kendi dönüştürmeleri, dünya koordinatlarına çevrildiğinde 3D motor tarafından otomatik olarak uygulanacaktır.

Zaman Karmaşıklık

MATRIX.MAX_Z * (
        Time(MATRIX.GET_VOXEL(x,y,z)) 
       + Time(VOXEL.DRAW-LINE(0,0,0, 0,0,VOXEL_DEPTH)) 
       ) 

Algoritma

FUNCTION DRAW (INTEGER X, INTEGER Y) 

    INTEGER VOXEL_X = X/MATRIX.VOXEL_WIDTH 
    INTEGER VOXEL_Y = Y/MATRIX.VOXEL_HEIGHT 

    FOR i = 0 .. (MATRIX.MAX_Z-1) 

     VOXEL V = MATRIX.GET_VOXEL(VOXEL_X, VOXEL_Y, i) 

     INTEGER X_0 = X % MATRIX.VOXEL_WIDTH 
     INTEGER Y_0 = Y % MATRIX.VOXEL_HEIGHT 
     INTEGER Z_0 = 0 

     INTEGER X_1 = X_0 
     INTEGER Y_1 = Y_0 
     INTEGER Z_1 = (MATRIX.VOXEL_DEPTH-1) 

     V.DRAW-LINE(X_0,Y_0,Z_0, X_1,Y_1,Z_1) 

    END-FOR 

END-FUNCTION 

Answer 2

Yani bu testi yapmanın bir kolay yolu keyfi de hedef küp kaynaktan görünümü (ortografik) kılmaktır çözüm. Herhangi bir arka plan pikseli varsa, iki dikdörtgen arasında bir çizgi vardır. Yani karmaşıklık iki hep var:

• Eğer
• Ne kadar hızlı bir ortografik işleyebilen hale geldiği çözünürlük, ikili görünümü ihtiyacınız olan tek şey render o ikili için Şimdi

bilmek kaplıdır/kapsam dışıdır. Bu, iki asalet, en az bir tane ve en fazla bir tane olmak üzere ikiye ayrılır. Minimum ağaç izleri var mı? Açık çocuk düğümü var mı (veya) "en büyük izler" var kapalı çocuk düğümü (ve) ". Bu ağaçların inşa edilmesi n log (n), ancak sorgu sadece log'tur (n).

Hedef çözünürlük için m, yalnızca günlük olmalıdır (m). Kayan boyutu için m = 2^23'e çıksanız bile.

+-+-+-+   +-+-+-+-+-+ 
    | |#| |   |#| | | | | 
    +-+-+-+   +-+-+-+-+-+ 
    | |#| |   |#| | |#| | 
    +-+-+-+   +-+-+-+-+-+ 
    | |#| |   |#| | |#| | 
    +-+-+-+   +-+-+-+-+-+ 
        |#| | |#| | 
        +-+-+-+-+-+ 
        | | | |#| | 
        +-+-+-+-+-+ 

... ama bu nasıl bağlı aşılmaz olmayabilir: aşağı iki boyuta sorunu Breaking

Answer 3

, bazı voksel yapılandırmaları soldan sağa, belli ki diyelim ki, gelen delinmez olduğu açıktır köşelerinizi işlemek için:

...ve bu kesinlikle mümkündür: Eğer en azından bazı imkansız piksel/voksel yapılandırmaları ortadan kaldırabilir alt birinden üst 2D-küpleri söyleyebilir herhangi bir hile, aklınıza gelebilecek eğer, Şimdi

+-+-+-+-+-+ 
    |#| | | | | 
    +-+-+-+-+-+ 
    |#| | | | | 
    +-+-+-+-+-+ 
    |#| | | | | 
    +-+-+-+-+-+ 
    | | | |#| | 
    +-+-+-+-+-+ 
    | | | |#| | 
    +-+-+-+-+-+ 

- ama Şüphesiz, kaynak noktanızdan gelen herhangi bir açıdan, n-kare problemi (2D) veya 3D'de n^4 gibi görünen sesler için, her pikselin hedef tarafınızda test edilmesi gerekir.

2B'de, sol tarafın üstünden başlayıp voksel merkezimi sağ üst tarafa bağlayan hattın tıkalı bir piksele çarpıp vurmadığını kontrol edeyim: eğer yapmıyorsak, işimiz bitti; eğer yaparsa, açınızı ilerlersiniz, böylece ışın oklüzyonun sol alt köşesini geçer ve bir geçit veya sağ tarafın sonuna ulaşıncaya kadar kontrol etmeye devam edin.

Tamamen bitene kadar, kaynak tarafındaki her piksele devam edin.

Ama bu kaba kuvvet ve belki de daha zarif bir çözüm görmek isterdim, belki de G. Bach ...?