Z-düzeni eğrisi - Z-order curve

Z eğrisi veya Z-düzeni ile karıştırılmamalıdır .
Z-düzeni eğrisinin dört yinelemesi.
Z-düzeni eğri yinelemeleri üç boyuta genişletildi.

Gelen Matematiksel analiz ve bilgisayar biliminin , işlevleri olan Z-sırası , Lebesgue eğrisi , Morton boşluk doldurma eğrisi , Morton sırası ya da Morton kodu harita bir boyuta çok boyutlu veri veri noktalarının mevkiinde koruyarak. Adını, 1966'da dosya dizilimine ilk kez uygulayan Guy Macdonald Morton'dan almıştır. Çok boyutlu bir noktanın z değeri , koordinat değerlerinin ikili gösterimlerinin serpiştirilmesiyle basitçe hesaplanır . Veriler bu sıralamaya göre sıralandığında, ikili arama ağaçları , B ağaçları , atlama listeleri veya (düşük anlamlı bitleri kesilmiş) karma tablolar gibi herhangi bir tek boyutlu veri yapısı kullanılabilir . Ortaya çıkan sıralama, eşdeğer olarak , bir dörtlü ağaç veya oktree'nin derinlik-birinci geçişinden elde edilecek sıra olarak tanımlanabilir .

koordinat değerleri

Aşağıdaki şekil, 0 ≤ x  ≤ 7, 0 ≤  y  ≤ 7 (hem ondalık hem de ikili olarak gösterilmiştir) tamsayı koordinatlarına sahip iki boyutlu durum için Z değerlerini göstermektedir  . İkili koordinat değerlerinin serpiştirilmesi , gösterildiği gibi ikili z değerlerini verir . Bağlama z sayısal sırayla-değerlerine yinelemeli olarak Z-şekilli bir eğri oluşturur. İki boyutlu Z değerleri aynı zamanda dörtlü anahtar olarak da adlandırılır.

Z-curve.svg

x'lerin Z değerleri, Moser-de Bruijn dizisinden alınan ve yalnızca çift konumlarında sıfırdan farklı bitlere sahip olan ikili sayılar olarak tanımlanır : 

x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}

İki x'in toplamı ve farkı, bitsel işlemler kullanılarak hesaplanır : 

x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101
x[i-j] = ((x[i] & 0b01010101) - x[j]) & 0b01010101  if i >= j

Bu özellik, bir Z-değerini ofsetlemek için kullanılabilir, örneğin iki boyutta koordinatları mevcut Z-değerinden yukarı (azalan y), alt (artan y), sola (azalan x) ve sağa (artan x) koordinatlar z : 

top    = (((z & 0b10101010) - 1) & 0b10101010) | (z & 0b01010101)
bottom = (((z | 0b01010101) + 1) & 0b10101010) | (z & 0b01010101)
left   = (((z & 0b01010101) - 1) & 0b01010101) | (z & 0b10101010)
right  = (((z | 0b10101010) + 1) & 0b01010101) | (z & 0b10101010)

Ve genel olarak iki boyutlu iki Z-değeri w ve z eklemek için : 

sum = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)

Dörtlü ağaçları ve oktreeleri verimli bir şekilde oluşturma

Z sıralaması, bir dizi nokta için bir dörtlü ağaç (2D) veya sekizli ağaç (3D) oluşturmak için kullanılabilir. Temel fikir, girdi setini Z sırasına göre sıralamaktır. Sıralandıktan sonra, noktalar bir ikili arama ağacında saklanabilir ve doğrusal dörtlü ağaç adı verilen doğrudan kullanılabilir veya işaretçi tabanlı bir dörtlü ağaç oluşturmak için kullanılabilir.

Giriş noktaları genellikle, ya birim aralığı [0, 1] üzerinde sabit nokta gösterimi olarak ya da makine sözcük boyutuna karşılık gelen pozitif tamsayılar olacak şekilde her boyutta ölçeklendirilir. Her iki temsil de eşdeğerdir ve en yüksek dereceli sıfır olmayan bitin sabit zamanda bulunmasına izin verir. Dörtlü ağaçtaki her karenin iki katı olan bir kenar uzunluğu ve kenar uzunluğunun katları olan köşe koordinatları vardır. Herhangi iki nokta verildiğinde, iki nokta için elde edilen kare , her iki noktayı da kapsayan en küçük karedir. Her noktanın x ve y bileşenlerinden bitlerin serpiştirilmesine x ve y'nin karıştırılması denir ve daha yüksek boyutlara genişletilebilir.

Noktalar, bitleri açık bir şekilde serpiştirmeden karışıklıklarına göre sıralanabilir. Bunu yapmak için, her boyut için, o boyut için iki noktanın dışlayıcı veya koordinatlarının en anlamlı biti incelenir. En anlamlı bitin en büyük olduğu boyut, daha sonra karıştırma sırasını belirlemek için iki noktayı karşılaştırmak için kullanılır.

Özel veya işlem, iki koordinatın aynı olduğu yüksek dereceli bitleri maskeler. Karıştırma, bitleri yüksek dereceden alt sıraya serpiştirdiğinden, koordinatı en anlamlı en büyük bit ile belirlemek, karıştırma sırasındaki farklılık gösteren ilk biti tanımlar ve bu koordinat iki noktayı karşılaştırmak için kullanılabilir. Bu, aşağıdaki Python kodunda gösterilir: 

def cmp_zorder(lhs, rhs) -> bool:
    """Compare z-ordering."""
    # Assume lhs and rhs array-like objects of indices.
    assert len(lhs) == len(rhs)
    # Will contain the most significant dimension.
    msd = 0
    # Loop over the other dimensions.
    for dim in range(1, len(lhs)):
        # Check if the current dimension is more significant
        # by comparing the most significant bits.
        if less_msb(lhs[msd] ^ rhs[msd], lhs[dim] ^ rhs[dim]):
            msd = dim
    return lhs[msd] < rhs[msd]

En anlamlı bitin daha küçük olup olmadığını belirlemenin bir yolu, her noktanın taban-2 logaritmasının tabanını karşılaştırmaktır. Aşağıdaki işlemin eşdeğer olduğu ve yalnızca özel veya işlemler gerektirdiği ortaya çıktı: 

def less_msb(x: int, y: int) -> bool:
    return x < y and x < (x ^ y)

Aynı tekniği kullanarak kayan noktalı sayıları karşılaştırmak da mümkündür. Less_msb fonksiyonu, birinci üs karşılaştırmak için modifiye edilir. Yalnızca eşit olduklarında, mantislerde kullanılan standart less_msb işlevi kullanılır.

Noktalar sıralandığında, iki özellik bir dörtlü ağaç oluşturmayı kolaylaştırır: Birincisi, dörtlü ağacın bir karesinde bulunan noktaların sıralı düzende bitişik bir aralık oluşturmasıdır. İkincisi, bir karenin birden fazla alt öğesi bir girdi noktası içeriyorsa, kare, sıralanmış düzende iki bitişik nokta için türetilmiş karedir .

Her bitişik nokta çifti için elde edilen kare hesaplanır ve kenar uzunluğu belirlenir. Türetilmiş her kare için, onu içeren aralık, sıralı olarak sağa ve sola doğru ilk büyük kareyle sınırlandırılır. Bu tür her bir aralık, dörtlü ağaçtaki bir kareye karşılık gelir. Bunun sonucu, yalnızca girdi noktaları veya iki veya daha fazla alt öğe içeren düğümlerin bulunduğu sıkıştırılmış bir dörtlü ağaçtır. İstenirse, eksik düğümler geri yüklenerek sıkıştırılmamış bir dörtlü ağaç oluşturulabilir.

İşaretçi tabanlı bir dörtlü ağaç oluşturmak yerine, noktalar ikili arama ağacı gibi bir veri yapısında sıralanmış düzende tutulabilir. Bu, noktaların O(log n) zamanında eklenmesine ve silinmesine izin verir. İki sıralı nokta kümesi birleştirilerek ve kopyalar kaldırılarak iki dörtlü ağaç birleştirilebilir. Nokta konumu, sorgu noktasından önceki ve sonraki noktalar sıralı olarak aranarak yapılabilir. Dörtlü ağaç sıkıştırılmışsa, bulunan öncül düğüm, sıkıştırılmış ilgili düğümün içinde rastgele bir yaprak olabilir. Bu durumda, sorgu noktasının ve bulunan yaprağın en küçük ortak atasının öncülünü bulmak gerekir.

Aralık arama için tek boyutlu veri yapılarıyla kullanın

Yerelliği iyi korusa da, verimli aralık aramaları için, veri yapısında karşılaşılan bir noktadan çok boyutlu arama aralığındaki bir sonraki Z değerini hesaplamak için bir algoritma gereklidir:

Z-düzeni eğrisinde BIGMIN araması.svg

Bu örnekte, sorgulanan aralık ( x  = 2, ..., 3, y  = 2, ..., 6) noktalı dikdörtgen ile belirtilmiştir. En yüksek Z değeri (MAX) 45'tir. Bu örnekte,  artan Z değeri yönünde bir veri yapısı aranırken F = 19 değeriyle karşılaşılır, bu nedenle F ve MAX (taralı alan) arasındaki aralıkta arama yapmamız gerekir. ). Aramayı hızlandırmak için, arama aralığında bulunan ve BIGMIN (örnekte 36) olarak adlandırılan bir sonraki Z-değeri hesaplanır ve yalnızca BIGMIN ve MAX (kalın değerler) arasındaki aralıkta arama yapılır, böylece tarananların çoğu atlanır. alan. Azalan yönde arama yapmak, F'den daha düşük sorgu aralığındaki en yüksek Z değeri olan LITMAX ile benzerdir. BIGMIN problemi ilk olarak ifade edilmiş ve çözümü Tropf ve Herzog'da gösterilmiştir. Bu çözüm, UB ağaçlarında da kullanılır ("GetNextZ-adresi"). Yaklaşım seçilen bir boyutlu veri yapısına bağlı değildir olarak, yapılanma serbest seçim bilgileri, örneğin dengeli bir ağaç olarak çok iyi bilinen yöntemler, örneğin aksine (dinamik veriler ile başa çıkmak için kullanılabilir hala R ağaçlar burada özel hususlar gereklidir). Benzer şekilde, bu bağımsızlık, yöntemin mevcut veritabanlarına dahil edilmesini kolaylaştırır.

Yöntemi hiyerarşik olarak (eldeki veri yapısına göre), isteğe bağlı olarak hem artan hem de azalan yönde uygulamak, örneğin en yakın komşu aramalarının altında yatan bir prosedür olarak, hem ticari hem de teknik uygulamalarda önemli olan yüksek verimli çok boyutlu menzil araması sağlar. Z-order, ticari veritabanı sistemlerine giren birkaç çok boyutlu erişim yönteminden biridir ( Oracle veritabanı 1995, Transbase 2000).

1966 gibi uzun bir süre önce, GMMorton, statik iki boyutlu bir coğrafi veritabanının dosya dizilimi için Z-sırasını önerdi. Alansal veri birimleri, boyutları ve sağ alt köşedeki Z değerleri ile temsil edilen bir veya birkaç ikinci dereceden çerçeve içinde bulunur, boyutlar köşe konumunda Z-sıralı hiyerarşisine uygundur. Yüksek olasılıkla, bitişik bir çerçeveye geçiş, bir veya birkaç nispeten küçük tarama adımıyla yapılır.

İlgili yapılar

Alternatif olarak Hilbert eğrisi daha iyi bir düzen koruma davranışına sahip olduğu ve aslında optimize edilmiş bir indeks olan S2 geometrisinde kullanıldığı için önerilmiştir.

Uygulamalar

Moser-de Bruijn dizisine nerede ve her ikisinin de ait olduğu için toplama tablosu ve toplamları sayısal sırayla birleştiren Z-sıralı eğri

Lineer Cebir

Strassen algoritması bloklar tek elemanlarının (ya da daha çok pratik kadar matris çoğalması için, dört blok ve dört küçük blokta bu blokların her biri daha sonra ardışık olarak bölme içinde matrisler bölme dayanır: matrisleri ulaşıncaya kadar küçük olduğu Moser-de Bruijn dizisi önemsiz algoritması daha hızlıdır). Matris elemanlarının Z-sırasında düzenlenmesi daha sonra yerelliği iyileştirir ve (satır veya sütun ana sıralamasına kıyasla) ek bir avantaja sahiptir, iki bloğu çarpmak için alt rutinin matrisin toplam boyutunu bilmesine gerek yoktur, sadece blokların boyutu ve bellekteki konumu. Z-mertebesiyle Strassen çarpmasının etkili kullanımı gösterilmiştir, bkz. Valsalam ve Skjellum'un 2002 tarihli makalesi.

Buluç et al. Bir mevcut eksik matris Z emir de sıfır olmayan elemanları sağlamak için bu veri yapısını paralel matris vektör çarpımı.

Doku eşleme

Bazı GPU'lar , doku eşlemeli rasterleştirme sırasında referansın uzamsal konumunu artırmak için doku eşlemelerini Z-sırasında saklar . Bu, önbellek satırlarının dikdörtgen döşemeleri temsil etmesine izin vererek yakındaki erişimlerin önbellekte olma olasılığını artırır. Daha büyük bir ölçekte, SDRAM/DDRAM'de maliyetli, sözde "sayfa sonları" (yani satır değiştirme maliyeti ) olasılığını da azaltır . Bu önemlidir, çünkü 3B oluşturma keyfi dönüşümleri (döndürmeler, ölçekleme, perspektif ve animasyonlu yüzeyler tarafından bozulma) içerir.

Bu formatlara genellikle swizzled dokular veya twiddled dokular denir . Diğer döşeme biçimleri de kullanılabilir.

N-vücut sorunu

Barnes-Hut algoritma, bir okt-ağacının inşa edilmesini gerektirir. Verileri işaretçi tabanlı bir ağaç olarak depolamak, okt ağacı üzerinde derinlemesine birinci düzende yineleme yapmak için birçok sıralı işaretçi referansı gerektirir (dağıtılmış bellekli bir makinede pahalıdır). Bunun yerine, eğer veriler bir hashtable içinde , oct-tree hashing kullanılarak depolanırsa , Z-düzeni eğrisi, oct-tree'yi derinlik-birinci düzende doğal olarak yineler.

Ayrıca bakınız

Referanslar

Dış bağlantılar