3D Matematik - Sadece belirli bir miktardaki pozisyonlarda pozisyonları koruyun

Question

Listemi büyük ölçüde nasıl daraltacağımı büyük bir konum kümesinden belirlemeye çalışıyorum.

Şu anda yaklaşık 3000 konumum var (x, y, z) ve temel olarak birbirlerinden en uzaktaki konumları tutmak istiyorum (2 yarda içinde 100 pozisyon tutmam gerekmiyor birbirinden yarıçap).

Kesin bir güç yöntemi yapmanın yanı sıra 3000^2 karşılaştırması yapmanın yanında, bu listeyi nasıl daha daraltabileceğime dair herhangi bir fikrim var mı?

Buna matematik perspektifinden nasıl yaklaşmalıyım konusunda biraz kafam karıştı.

Answer 1

Eh, bu algoritmanın adını hatırlayamıyorum, ancak bunu işlemek için size eğlenceli bir teknik anlatacağım. 3B ortamda yarı-rastgele bir puan dağılımı olduğunu varsayacağım.

Basit Versiyon: Böl ve Yönet

1. Divide küp 3D ızgara içine alan. Her küp, her iki tarafta X metre olacaktır.
2. Çok amaçlı bir dizi [x, y, z], kılavuzunuzdaki her küp için bir öğeye sahip olduğunu belirtin. Dizinin
3. her eleman bir tepe (x, y, z) yapıya bir köşe ya da referans ya da olmalıdır, ve her biri için veri kümesindeki her köşe ile
4. Yineleyin NULL varsayılan tespit hangi küp köşe falls
   • Nasıl? Eh, (5.5, 8.2, 9.1) vertex'in MyCubes [5,8,9] 'a ait olduğunu varsayabiliriz, X (küp-boy-uzunluk) 1 boyutundadır. Not: Sadece ondalık/şamandıraları kestirdim. hangi küpü belirleyin.
5. İlgili küpün zaten bir tepe noktası tarafından alınmış olup olmadığını kontrol edin. Kontrol: Eğer MyCubes [5,8,9] == NULL sonra (hiçbir şey, alınan dostum dışarı atmak nokta!)

Biraz belleğini

kurtaralım başka (benim köşe enjekte) Bu size tek geçişte güzel basitleştirilmiş bir veri kümesi, ancak potansiyel olarak büyük miktarda bellek maliyeti verecektir.

Peki, çok fazla bellek kullanmadan nasıl yapıyorsunuz?

Yukarıdaki örnekte anahtarımın Grid-Cube koordinatını (5,8,9) olması için bir hashtable kullanıyorum. Şimdi

If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...) 

, sen az bellek kullanımı (boş küp potansiyel sayıda hayır dev dizisi ile bir tek geçişli bir çözüm olacaktır. Maliyetidir Ne? Eh, kurulum sizin yapı/sınıf programlama süresini bir HashTable .Contains eylemi gerçekleştirmek, böylece (veya sizin dile eşdeğeri)

Hey, sonuç tıknaz vardır! doğru

, biz ilk sonucu aldı çünkü herhangi küp sığacak o .Ortalama olarak, köşeler arasındaki X-ayrımını elde etmiş olacağız, ama şimdi anlayacağınız gibi, bazı köşeler hala birbirine yakın olacak (küplerin kenarlarında).

Peki, bunu nasıl ele alıyoruz? Peki, tepedeki dizi yöntemine geri dönelim (bellek yoğun!). Bunun yerine SADECE köşe küp-in-Söz konusu zaten ise de bu diğer kontrolü gerçekleştirmek, olacağını kontrol etme

: Ben muhtemelen bu güzelliğini görebilirsiniz düşünüyorum

If Not ThisCubeIsTaken() 
    For each SurroundingCube 
     If not Is_Your_Vertex_Sufficiently_Far_Away_From_Me() 
     exit_loop_and_outer_if_statement() 
     end if 
    Next 
    //Ok, we got here, we can add the vertex to the current cube because the cube is not only available, but the neighbors are far enough away from me 
End If 

, olduğu gibi 3D diziniz varsa komşu küpleri almak gerçekten çok kolay.

Böyle bir düzeltme yaparsanız, muhtemelen '0.25X ile ekleyip eklemeyin' ilkesini uygulayabilirsiniz. Fark edilebilir bir yumuşatma etkisi elde etmek için çok sıkı olmanız gerekmeyecektir. Yine

çok tıknaz

, ben bu varyasyonda

pürüzsüz istiyoruz, bir köşe küp ikamet almaya izin verilip verilmediğini için eleme işlemini değiştirir.

If TheCube is empty OR if ThisVertex is closer to the center of TheCube than the Cube's current vertex 
    InsertVertex (overwrite any existing vertex in the cube 
End If 

Not, bunun için komşu tespiti yapmak zorunda değiliz. Sadece her küpün merkezine doğru optimize ediyoruz.

İsterseniz, bu varyasyonu bir önceki varyasyonla birleştirebilirsiniz. Hile Modu

bu durumda bazı insanlar için, basitçe veri kümesi% 10 rastgele seçim hakkını al ve bu yeterince iyi sadeleştirme olacaktır. Bununla birlikte, birbirine çok yakın olan bazı noktalarda çok tıknaz olacak. Parlak tarafta, birkaç dakika alır. Prototip yapmadıkça bunu önermem.