En büyük açık alanı saptamak için etkin algoritma

Question

Aşağıda parlak bir şekilde gösterilmiş, bir alandaki en geniş çevreleri (açık alan) çalıştırmamı gerektiren bir durumum var. Aşağıdaki örnekte, siyah daireler bilinen konumlardır, siyah halkalara dokunmayan en büyük alanı (turuncu ve yeşil dairelerle temsil edilir) bulmalıyım. Aşağıdaki örnekte, turuncu daire en büyük açık alan ve bu, hesaplamak istediğim alan.

Ben bir siyah nokta ulaşıncaya kadar sonra sadece daire (açık alan) konumunu ve yarıçapı kaydetmek, zorlamak bir pozisyon almak ve bir daire genişletmek kaba olabilir ama bu kitlesel olacak tüm olası pozisyonlar arasında yinelemek için verimsiz.

Bu örnekte en büyük açık alanın nerede olacağını analiz etmenin etkili bir yolu var mı? Bu alandaki maksimum siyah nokta sayısı 15 olacak, ancak muhtemelen çok daha düşük olacaktır.

EDIT Teşekkürler Yves ve diğer tüm yorumcular. Cevap ve diğer yorumlara dayanan bir takım açıklamalar. Kara kutu bir bağdır, bu nedenle tanımlanan herhangi bir alan kara kutu içinde olmalıdır. Siyah halkaların yarıçapı bilinir ve statiktir, ancak bu amaçlar için noktalara indirgenebilir. Son olarak, dairelerin yaklaştırılması kabul edilebilir. Hangi alanın en iyisi olduğuna karar vermede hata payı olan bir AI rutininde kullanılacaktır. Yani, eğer daire yarıçap veya pozisyonda biraz dışarı çıkarsa, büyük bir sorun olmayacaktır.

Şu anda Voronoi yöntemini arıyorum ve bunu anladığımı düşünüyorum, ama şimdi uygun bir algoritma çekmeye çalışmak sorun! Test edip sana döneceğim.

DÜZENLEME 2: Yves sayesinde bir Voronoi diyagramı inceledik ve Voronoi köşe döngü için basit bir yöntem kullanılabilir (ve makas sınırlayıcı kutusunu sahasına) ve değil bu orta noktadan büyük daire bulmak "siyah daireler" in hiçbirini içermez. Nispeten küçük, sınırlı bir puan seti ile bu uygulamada yeterince mutluyum. Sonuç için, alana en iyi 3 boş daireyi gösteren aşağıya bakın.

Answer 1

Bu "büyük boş daire" sorunu olarak bilinir. Voronoi diyagramı ile verimli bir şekilde çözülebilir.

Siyah daireler sonlu bir çapa sahipse, bunları merkezlerine daraltabilir ve daha sonra bulunan çözümden yarıçapı azaltabilirsiniz.

Her neyse, dikdörtgenlere karşı dairelere izin verilirse, algoritmanın bunun hesaba katılması için değiştirilmesi gerekir. Önemsiz bir görev.

Güncelleme:

İlgili bir sorun ele alındı ​​

"konum kısıtlamaları ile TOUSSAINT Godfried T. Computing büyük boş çevreler bilgisayar & bilgi Bilimler Dergisi, 1983, 12.5. 347-358" ve " CHEW, L. Paul; DRYSDALE, Scot. Konum kısıtlamaları bulunan en büyük boş daireler. 1986. " Merkez, belirli bir dışbükey çokgenin içine girmeye zorlandığında etkili bir çözümü tanımlar. (Ama dairenin tamamen içerilmesini sanıyorum sanırım.)

---

tamamen farklı bir yaklaşım ayrı bir görüntü ile uğraşan dijital alanda (içinde, sonlu boyutta piksel) mümkündür: siyah piksele Öklit mesafesi harita hesaplayabilir. Doğrusal bir zamanda bunu sağlayan akıllıca verimli bir algoritma vardır (wrt görüntü boyutu, engellerin sayısı wrt değil); bkz. "A. Meijster, J. B.T. M. Roerdink ve W. H. Hesselink, Doğrusal zamanda mesafe dönüşümlerinin hesaplanması için genel bir algoritma".

Mesafe haritasını hesapladıktan sonra, istenen dairenin merkezi en büyük mesafe değerine sahip pikseldir. Bu yöntem herhangi bir şekildeki engellerle çalışacaktır.

---

Güncelleme: engel sayısı az olduğu için

Senin durumunda

, ayrıntılı arama kabul edilebilir olabilir. 3 noktadan geçen, 2 noktadan geçen ve bir kenara teğet veren veya 1 nokta ve teğet olarak 2 kenara geçen çevreleri denemelisiniz.

Tüm bu çevreler için, başka bir nokta içermediklerini ve en büyüklerini koruduklarını kontrol edin. Prensip olarak, bu zaman alır O (N^4). Görünüşe göre bu karmaşıklık O (N³) 'ye indirgenebilir, fakat bu problem üzerinde bulduğum her giriş, Voronoi temelli yaklaşımı ve tam kapsamlı olanı değil.