Voronoi kolay algoritma uygulamak için diyagram?

SORU

10 HAZİRAN 2009, ÇARŞAMBA

Voronoi kolay algoritma uygulamak için diyagram?

Voronoi diyagramı uygulaması kolay algoritmaları nelerdir?

Herhangi bir algoritma pseudo şeklinde özel olarak bulamadım. Voronoi diyagramı algoritmanın bazı bağlantılar, öğretici vs. paylaşın lütfen.

Şimdiden teşekkürler.

CEVAP

10 HAZİRAN 2009, ÇARŞAMBA

Bir nokta kümesinin Delaunay nirengi hesaplamak için kolay bir algoritma flipping edges. Delaunay nirengi Voronoi diyagramı çift grafik olduğundan, doğrusal zaman çevrimine diyagram oluşturabilirsiniz.

Ne yazık ki, saygısız yaklaşımın en kötü durum koşma süresi O(n^2) ' dir. İyi şanslar hattı süpürme gibi algoritmalar(n log n) O zaman alan var. Bu biraz zor olsa da uygulamaktır. Eğer tembel benim gibi) iseniz, Delaunay nirengi varolan bir uygulama arıyorum öneririm, kullanımı ve çift grafik bilgi işlem yapardım.

Genel olarak, bu konu hakkında iyi bir kitap de Berg ve ark tarafından Computational Geometry.

Bunu Paylaş: