Prosty wielokąt — Simple polygon
W geometrii , A wielokąt prosty / s ɒ l ɪ ɡ ɒ n / jest wielokąta , że nie przecinają się samo i nie ma otworów. Oznacza to, że jest to płaski kształt składający się z prostych, nieprzecinających się segmentów linii lub „boków”, które są połączone parami, tworząc pojedynczą zamkniętą ścieżkę. Jeśli boki się przecinają, wielokąt nie jest prosty. Kwalifikator „prosty” jest często pomijany, a powyższą definicję należy rozumieć jako ogólną definicję wielokąta.
Podana powyżej definicja zapewnia następujące właściwości:
- Wielokąt otacza obszar (zwany jego wnętrzem), który zawsze ma mierzalną powierzchnię .
- Segmenty linii tworzące wielokąt (zwane bokami lub krawędziami) spotykają się tylko w ich punktach końcowych, zwanych wierzchołkami (liczba pojedyncza: wierzchołek) lub mniej formalnie „rogami”.
- Dokładnie dwie krawędzie spotykają się na każdym wierzchołku.
- Liczba krawędzi zawsze jest równa liczbie wierzchołków.
Dwie krawędzie stykające się w rogu są zwykle wymagane, aby utworzyć kąt, który nie jest prosty (180°); w przeciwnym razie współliniowe segmenty linii będą uważane za części jednego boku.
Matematycy zwykle używają terminu „wielokąt” w odniesieniu tylko do kształtu utworzonego przez segmenty linii, a nie do obszaru zamkniętego, jednak niektórzy mogą używać terminu „wielokąt” w odniesieniu do figury płaskiej ograniczonej zamkniętą ścieżką, złożonej ze skończonej sekwencji segmentów linii prostych (tj. przez zamknięty łańcuch wielokątny ). Zgodnie z używaną definicją granica ta może, ale nie musi, stanowić część samego wielokąta.
Proste wielokąty są również nazywane wielokątami Jordana , ponieważ twierdzenie o krzywej Jordana może być użyte do udowodnienia, że taki wielokąt dzieli płaszczyznę na dwa obszary, obszar wewnątrz niej i obszar na zewnątrz. Wielokąt w samolocie jest proste tylko wtedy, gdy jest topologicznie równoważne do kręgu . Jego wnętrze jest topologicznie równoważne z dyskiem .
Słabo prosty wielokąt
Jeśli zbiór nieprzecinających się odcinków linii tworzy granicę obszaru płaszczyzny, który jest topologicznie równoważny dyskowi, to granica ta nazywana jest słabo prostym wielokątem . Na rysunku po lewej ABCDEFGHJKLM jest słabo prostym wielokątem zgodnie z tą definicją, z niebieskim kolorem oznaczającym region, dla którego jest granicą. Ten typ słabo prostego wielokąta może powstać w grafice komputerowej i CAD jako komputerowa reprezentacja obszarów wielokątów z otworami: dla każdego otworu tworzone jest „wycięcie”, aby połączyć go z zewnętrzną granicą. Odnosząc się do powyższego obrazu, ABCM jest zewnętrzną granicą płaskiego obszaru z otworem FGHJ. Wycięty ED łączy otwór z zewnętrzem i jest przecinany dwukrotnie w wynikowej słabo prostej reprezentacji wielokąta.
W alternatywnej i bardziej ogólnej definicji słabo prostych wielokątów są to granice ciągów prostych wielokątów tego samego typu kombinatorycznego o zbieżności pod odległością Frécheta . Formalizuje to pogląd, że taki wielokąt pozwala segmentom stykać się, ale nie krzyżować. Jednak ten typ słabo prostego wielokąta nie musi stanowić granicy regionu, ponieważ jego „wnętrze” może być puste. Na przykład, odnosząc się do powyższego obrazu, wielokątny łańcuch ABCBA jest według tej definicji słabo prostym wielokątem: może być postrzegany jako granica „ściskania” wielokąta ABCFGHA.
Problemy obliczeniowe
W geometrii obliczeniowej kilka ważnych zadań obliczeniowych obejmuje dane wejściowe w postaci prostego wielokąta; w każdym z tych problemów rozróżnienie między wnętrzem a zewnętrzem jest kluczowe w definicji problemu.
- Testowanie punktu w wieloboku polega na określeniu, dla prostego wielokąta P i punktu zapytania q , czy q leży wewnątrz P .
- Znane są proste formuły do obliczania powierzchni wielokąta ; czyli obszar wnętrza wielokąta.
-
Podział wielokąta to zbiór jednostek pierwotnych (np. kwadratów), które się nie nakładają i których suma jest równa wielokątowi. Problem podziału wielokąta to problem ze znalezieniem podziału, który jest w pewnym sensie minimalny, na przykład: podział z najmniejszą liczbą jednostek lub z jednostkami o najmniejszej całkowitej długości boku.
- Specjalnym przypadkiem podziału wielokątów jest triangulacja wielokątów : dzielenie prostego wielokąta na trójkąty. Chociaż wielokąty wypukłe są łatwe do triangulacji, triangulacja ogólnego wielokąta prostego jest trudniejsza, ponieważ musimy unikać dodawania krawędzi, które przecinają się poza wielokątem. Niemniej jednak Bernard Chazelle wykazał w 1991 roku, że każdy prosty wielokąt o n wierzchołkach może być triangulowany w czasie Θ ( n ), który jest optymalny. Ten sam algorytm może być również użyty do określenia, czy zamknięty łańcuch wielokąta tworzy wielokąt prosty.
- Innym szczególnym przypadkiem jest problem galerii sztuki , który można równoważnie przeformułować jako podział na minimalną liczbę wielokątów w kształcie gwiazdy .
- Operacje Boole'a na wielokątach : Różne operacje Boole'a na zbiorach punktów zdefiniowanych przez regiony wielokątów.
- Wypukłe kadłuba prosty wielokąta mogą być obliczane bardziej efektywnie niż wypukłej innych rodzajów wejść, takich jak na wypukłej zbioru punktów.
- Diagram Woronoja prostego wielokąta
- Oś środkowa / szkielet topologiczny / prosty szkielet prostego wielokąta
- Krzywa przesunięcia prostego wielokąta
- Suma Minkowskiego dla prostych wielokątów