Çıkarmadan Sonra Kalan Polonu Hesaplamak için Algoritma

Question

Büyük bir çokgenim var (Pa). görüldüğü gibi çokgen içinde küçük "delik" bir yeri vardır:

1. delik birbirlerine
2. çakışamaz: Burada

   delikleri için bir kaç şartı vardır delikler, numaralı dış poligonun dış poligonun dışına çıkamaz. Ancak, delikleri dış poligon kenarına

Kalan çokgen (veya çokgen listesi) verimli bir şekilde nasıl elde edilir? En kolay yol (kaba kuvvet yolu) Pa'u almak ve delikleri çıkararak aşamalı olarak kalan çokgeni hesaplamaktır. Bu fikir mümkün olsa da, daha verimli bir algoritma olduğundan şüpheleniyorum.

Düzenleme: Çokgen kırpma (veya çıkarma) algoritmasının nasıl gerçekleştirileceğini sormuyorum! Aslında bu kaba kuvvetle yapacağım bir şey. Ben poligon kırpma yöntemine ek olarak (ana çokgen al ve sonra yavaş yavaş delikler dışarı klip) soruyorum, başka daha verimli yolu var mı?

Answer 1

Genel olarak yapılması çok zor. Burada çözüm için kaynak kodunu bulabilirsiniz:

General Polygon Clipper (GPC)

Answer 2

Böyle yapabilirsiniz.

1. Ana çokgen bir bit eşlemdeki bir renkle çizin.
2. Delikleri aynı bitmap'e başka bir renkle çizin. Daha sonra eşik olarak ana çokgenler rengiyle yürüyen kare algoritması çalıştırarak çokgeni ayıklayın.
3. Çıktı, bu çokgene ait tüm noktaları içerecektir.
4. Sürekli kapalı çokgen olarak isterseniz noktaları sıralayabilirsiniz.

Answer 3

Çokgeniniz için doğru gösterimi kullanırsanız, bir şey yapmanıza gerek yoktur. Sadece deliklerin kenarlarını Pa kenarlarına yapıştırın.

Sahip olmanız gereken tek şey, eğer bir delik köşesi veya kenarı Pa kenarına dokunabiliyorsa, orada bir miktar basitleştirme yapmanız gerekecektir.

Farklı bir sorun, poligonu bir bitmap haline getiriyor!

Answer 4

Salva ile aynı fikirdeyim ancak yazımım çizim kısmına yönelecek. Temel olarak, ana ve delikli poligonların tüm çizgilerini bir araya getirebilir ve böylece tek bir karmaşık çokgen elde edebilirsiniz.

Algoritmanın kendisi çok karmaşık değildir ve güzel bir şekilde Polygon Fill Teaching Tool'da açıklanmıştır.