Otoczka wypukła

O tym kalkulatorze

Kalkulator otoczki wypukłej znajduje najmniejszy wielokąt wypukły zawierający zbiór punktów 2D, korzystając z algorytmu łańcucha monotonicznego Andrew. Wypisuje wierzchołki otoczki w kolejności przeciwnej do ruchu wskazówek zegara, liczy, ile punktów leży na otoczce, a ile wewnątrz, i podaje dokładne pole i obwód wraz z wykresem punktowym, na którym obrysowano wynik. Punkty zduplikowane i współliniowe są obsługiwane poprawnie.

Jak wyznaczyć otoczkę wypukłą

1. Wpisz punkty jako pary x,y rozdzielone przecinkami — kolejność nie ma znaczenia.
2. Kalkulator scala duplikaty i sortuje punkty od lewej do prawej.
3. Przechodzi po posortowanych punktach, budując dolną i górną granicę i zachowując tylko wierzchołki, w których obrys skręca w lewo.
4. Odczytaj wierzchołki otoczki, pole i obwód oraz zobacz obrys narysowany na Twoich punktach.

Typowe przykłady

• Wierzchołki kwadratu 0,0 6,0 6,4 0,4 z punktami wewnętrznymi 3,2 i 2,1 → 4 wierzchołki otoczki, pole 24, obwód 20
• Trójkąt 0,0 4,0 0,3 → 3 wierzchołki otoczki, pole 6, obwód 12
• Punkty współliniowe 0,0 1,1 2,2 3,3 → otoczka zdegenerowana (odcinek), pole 0
• Kwadrat 0,0 4,0 4,4 0,4 i wierzchołek 2,5 → 5 wierzchołków otoczki, bo szczyt wysuwa górną krawędź