En Yakın Dışbükey Çokgenleri Birleştir

Question

Bir dizi nokta bulutum var (kendi bölgelerinde olduğu belirlenen noktalardan oluşan bir küme).

gol ya

i olan bu bireysel kümeleri birleştirmektir.

ii. Birbirinden en az

kontrolünden itibaren, kontrol ii bunu daha zor hale getirir. Bu pointcloud'larla çabucak ilgilenmek için AABB (X ekseni boyunca hizalanan eksen hizalanmış sınırlayıcı kutular) yaratıyorum.

Benim geçerli yöntem Ayırma Eksen teoreminin bazı özelliklerini kullanmaktır:

1. daha sonra rasgele bir eksen ve üzerine bu çıkıntı ile örtüşen kontrol, her PointCloud her AABB için
2. için AABB oluşturma bu lineer projeksiyonları bu hatta düştükleri yere göre ayırmak (nlog (n)). Daha sonra SAT kullanarak O (N) kesişimlerini kontrol etmek için bu listeden geçiyorum. Çoğu AABB'nin lineer projeksiyonları örtüşmeyecek ve bu nedenle kesişmeyecek ve ben elimden gelenleri manuel olarak kontrol edebiliyorum (çünkü 1D'de hiçbir çakışma kesişimi garanti etmiyor, fakat tersi doğru değil).

Son kısım, takılı olduğum yer. Yukarıdaki 1D projeksiyonu, kavşaklar için O (n^2) ikili kontrollerden kaçınmak için yapıldı. Ancak, belirli bir eşikte olan ancak Kesişen DEĞİL olmayan dışbükey çokgenleri birleştirmek için, bir O (N^2) çift yönlü kontrolün etrafında bir yol göremiyorum.

Belirli bir mesafe içinde bulunan tüm dışbükey poligonları, her bir çift kombinasyonunu kontrol etmeksizin birleştirmek için bir ağaç veya grafik oluşturmanın bir yolu var mı?

Kullanım adımlarını 1 & 2'den kullanırsanız, kalan pointclouds/AABB'nin Kesişen DEĞİLDİ olmadığını varsayabilirsiniz.

DÜZENLEME

olası bir çözüm threshold/2AABB genişliği ve yüksekliği, ekleme ve kesişme kontrol etmek için olacaktır. Eğer kesişirse, fiili kavşakları (AABB için hızlı olan) ve ikisi arasındaki minimum mesafeyi kontrol edebilirim.

Answer 1

Rastgele eksenimin normalini kullanarak sona erdim ve her iki yönde de her iki yöndeki çakışmaları kontrol ettim; bu da algoritmamı önemli ölçüde hızlandırdı (bir eksen boyunca kümelenme varsa yavaşlatma kaldırıldı).

Mesafe eşiği için, kesişimi garantilemek için gerekli olan en az AABB mesafe dolgusu gerekliydi A/2. Bu, AABB'un yalnızca x veya y yönünde ayrıldığı tüm durumları yakalar (çapraz durum A * sqrt (2)/4 gerektirir)

Answer 2

Belirli bir kesişen kutular kümesinin kesişen kutuları bulma problemi olduğunu düşünüyorum 'mekansal birleşme' denir. TOUCH gibi özel algoritmalar vardır. Ancak, bir mekansal dizin kullanıyorsanız, kutuların arasında yinelemenin ve çakışmayı kontrol etmenin oldukça verimli olduğunu buldum. Bu, her kutu için kesişen kutular için uzamsal indeksi sorgulamanız anlamına gelir. Klasik olarak bunun için bir R-Tree veya X-Tree kullanabilirsiniz.

PH-Tree (kendi Java uygulamam) ile çok iyi sonuçlar elde ettim, örneğin yaklaşık 1.200.000 3D kutucuk (6000 kesişen kutu) veri kümeleriyle, dizinin yüklenmesi ve sorguların gerçekleştirilmesi yaklaşık 6 saniye sürüyor. masaüstü bilgisayar

DÜZENLEME

Ben karmaşıklığı hakkında emin değilim, ama (n * n günlük) O altında gibi görünüyor.