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.

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.