Çokgenin kendi içinde kesişme noktaları var mı?

Question

2D bir çokgen olduğunu düşünün (daha doğru olması için bir 2D closed polygonal chain). Kendinden kavşaklar içerip içermediğini nasıl kontrol edersiniz? Konveks veya içbükey, saat yönünde veya saat yönünün tersine yönlendirilebilir.

Şimdi, herhangi iki parçanın çapraz olup olmadığını kontrol etmek için standart bir O(N log N) algoritması çalıştırabilirim. Ama inanıyorum ki, ek bir yapımız var - segmentlerin sırası ve her iki ardışık segmentin uç noktalarda buluşması - daha basit ve daha hızlı (belki de O(N)?) Algoritması tasarlanabilir.

Herhangi bir fikrin var mı?

Answer 1

Sadece oto-kavşaklarını kontrol etmek ya da hepsini bulmak için mi ihtiyacınız var? İkincisi, n bölümleri ile O(n^2) kesişme noktalarına sahip olabileceğiniz için O(N log N)'dan daha zordur.

Yalnızca kendi içinde kesişme olup olmadığını bulmanız veya az miktarda bulmanız gerekiyorsa, here'a bakın. Bu makale, özellikle çokgen düzlemselleştirme bölümünde ihtiyacınız olanı iddia ediyor gibi görünüyor. Makul boyutta herhangi bir problem için basit ya da yararlı olacağını açıklanan algoritmanın uygulanmasından şüphe duyuyorum. Ancak böyle bir algoritma var. Feragatname: Kağıt üzerinde çalışıp anlamadım.