Çokgenleri bir çizgi ile nasıl bölebilirim?

Question

olarak aşağıda gösterilen,

bir Line Çokgen bölmek mümkün mü? (iki çokgen halinde). Çizgi çokgen boyunca ilerlemezse başarısız olur.

Bu mümkün mü? Eğer öyleyse, bunu nasıl yapardım?

Answer 1

Bunu yakın zamanda yapmak zorundaydım. Sadece poligonda yürümek, diyagramınızdaki gibi içbükey çokgenler için çalışmayacaktır. Aşağıda, Greiner-Hormann çokgen kırpma algoritmasından esinlenen algoritmamın bir taslağı yer almaktadır. Bölme, poligon kırpmadan daha kolay ve daha zordur. Daha kolay, sadece bir doğrultu veya başka bir çokgen yerine bir çizgiye karşı klibi; daha zor çünkü her iki tarafı da tutmalısın.

Create an empty list of output polygons 
Create an empty list of pending crossbacks (one for each polygon) 
Find all intersections between the polygon and the line. 
Sort them by position along the line. 
Pair them up as alternating entry/exit lines. 
Append a polygon to the output list and make it current. 
Walk the polygon. For each edge: 
    Append the first point to the current polygon. 
    If there is an intersection with the split line: 
     Add the intersection point to the current polygon. 
     Find the intersection point in the intersection pairs. 
     Set its partner as the crossback point for the current polygon. 
     If there is an existing polygon with a crossback for this edge: 
      Set the current polygon to be that polygon. 
     Else 
      Append a new polygon and new crossback point to the output lists and make it current. 
     Add the intersection point to the now current polygon. 

Answer 2

Mükemmel şekilde mümkündür. Bunun için Java2d kullandığınızı kabul ediyorum. İçinde kesişenler olarak adlandırılan bir yöntem buldunuz. Bunu kullanarak bunu yapabilirsiniz.

Çokgen uygulamasının this uygulanmasını değiştirmeniz ve bir Line2D nesnesini geçen ve bir dizi çokgenleri (böylece aynı çizgi kesiminin sonsuz çokgenler oluşturabilmesi nedeniyle mümkündür) bir özelleştirici yöntemi yazmak zorunda kalabilirsiniz - zikzak çokgen varsay) veya boş.

Answer 3

Bu mümkündür, ancak çokgen dışbükey değilse ve onu bir çizgi boyunca bölmek potansiyel olarak ikiden fazla çokgene yol açar.

Çokgen kenarlarını katlayın ve her kenar için çizginin kesişip kesişmediğini belirleyin. Böyle ilk kenarı bulun. Başka bir kenar bulana kadar geçiş yapmaya devam edin, ancak yol boyunca karşılaştığınız her şeyi yeni bir çokgene ekleyin (ilk kenarın "bu taraftaki" ile aynı çizgiye bölünen kısmı ve son kenar için de dahil). Son olarak, yeni Poligona bir kapatma kenarı ekleyin. Şimdi kenarları işlemeye devam edin - hattın diğer tarafında, aynı şekilde başka bir Çokgen yaratın. Artık çizgide iki tane çokgen var. Aynı teknik, eğer dikkatliyseniz, çokgensel olmayan çokgeni çoklu katlara bölmekle işe yarayacaktır.

Çokgenin köşe çizgisini geçen çizgi ve çokgeni kesişmeyen çizgi gibi köşe durumlarına dikkat edin.

Düzenleme: Xan'ın işaret ettiği gibi, bu, tüm dışbükey olmayan durumları düzgün bir şekilde ele almayacaktır. Bu, algoritmaya küçük bir değişiklikle düzeltilebilir. Kapatma kenarını yukarıda açıklandığı gibi eklemeden önce, orijinal çokgenin başka bir kenarının bu kenarı keseceğini kontrol etmelisiniz; eğer öyleyse, sadece bu kenara kadar kapanır ve bu noktadan daha fazla kenar işlemeye devam edersiniz.

Answer 4

Tek ihtiyacınız olan bir çokgen kırpma alogrithem. Burada bir genel bakış görüyorsunuz: Polygon clipping Burada öğrenebileceğiniz penty uygulamaları var.

Answer 5

1994 yılında George Vanecek 3D'de bunun için bir çözüm çalıştı ve Grafik Taşlar V çözüm "Bir uçak ile Poligon Mekansal Bölümleme" yayınladı. Kaynak kod hala Graphic Gems Repository'da kullanılabilir. Daha yakın zamanlarda, David Geier, algoritmanın bir açıklaması ile Vanecek'in algoritmasının 2B uygulamasını yayınladı.Bkz. David's Blog: Splitting an arbitrary polygon by a line