Dışbükey Örtü
Bir nokta kümesinin dışbükey örtüsü
Bu hesaplayıcı hakkında
Dışbükey Örtü, Andrew'un monoton zincir algoritmasını kullanarak bir 2B nokta kümesini çevreleyen en küçük dışbükey çokgeni bulur. Örtünün köşe noktalarını saat yönünün tersine sırayla listeler, kaç noktanın örtü üzerinde ve kaçının içinde olduğunu sayar ve kesin alanla çevreyi, sonucun sınırını çizen bir saçılım grafiğiyle birlikte verir. Yinelenen ve doğrusal noktalar doğru biçimde ele alınır.
Dışbükey örtü nasıl bulunur
- Noktalarınızı virgülle ayrılmış x,y çiftleri olarak girin; sıra önemli değildir.
- Hesaplayıcı yinelenenleri birleştirir ve noktaları soldan sağa sıralar.
- Sıralanmış noktaları tarayarak alt ve üst sınırı oluşturur ve yalnızca sınırın sola döndüğü köşe noktalarını tutar.
- Örtü köşelerini, alanı ve çevreyi okuyun ve noktalarınızın üzerine çizilen sınırı görün.
Yaygın örnekler
- Kare köşeleri 0,0 6,0 6,4 0,4 ve iç noktalar 3,2 ile 2,1 → 4 örtü köşesi, alan 24, çevre 20
- Üçgen 0,0 4,0 0,3 → 3 örtü köşesi, alan 6, çevre 12
- Doğrusal noktalar 0,0 1,1 2,2 3,3 → dejenere örtü (bir doğru parçası), alan 0
- Kare 0,0 4,0 4,4 0,4 ve tepe noktası 2,5 → tepe üst kenarı dışarı taşıdığı için 5 örtü köşesi
Sıkça sorulan sorular
Dışbükey örtü nedir?
Bir nokta kümesinin dışbükey örtüsü, noktaların tamamını içeren en küçük dışbükey çokgendir; en dıştaki noktaların çevresine bir lastik bant gerip bırakınca bandın aldığı şekil gibi.
Hangi noktalar örtü köşesi olur?
Yalnızca uçtaki köşe noktaları örtü üzerinde yer alır. Şeklin tamamen içindeki noktalar ve tam olarak bir örtü kenarının üzerine düşen noktalar köşe olarak listelenmez.
Yinelenen veya doğrusal noktalar nasıl ele alınır?
Aynı noktalar önce birleştirilir. Tüm noktalar tek bir doğru üzerindeyse örtü sıfır alanlı bir doğru parçasına indirgenir; hesaplayıcı bunu dejenere örtü olarak bildirir.
Kaç noktaya ihtiyacım var?
Pozitif alanlı bir örtü oluşturmak için doğrusal olmayan en az üç farklı nokta gerekir.