Einfaches Polygon - Simple polygon
In Geometrie , ein einfaches Polygon / p ɒ l ɪ ɡ ɒ n / ist ein Polygon , das nicht der Fall ist intersect selbst und hat keine Löcher. Das heißt, es ist eine flache Form, die aus geraden, sich nicht schneidenden Liniensegmenten oder "Seiten" besteht, die paarweise verbunden sind, um einen einzelnen geschlossenen Pfad zu bilden . Wenn sich die Seiten schneiden, ist das Polygon nicht einfach. Der Qualifier "einfach" wird häufig weggelassen, wobei die obige Definition dann allgemein als Definition eines Polygons verstanden wird.
Die obige Definition gewährleistet die folgenden Eigenschaften:
- Ein Polygon umschließt eine Region (das Innere genannt), die immer eine messbare Fläche hat .
- Die Liniensegmente, die ein Polygon bilden (Seiten oder Kanten genannt), treffen sich nur an ihren Endpunkten, den sogenannten Scheitelpunkten (Singular: Scheitelpunkt) oder weniger formal "Ecken".
- An jedem Scheitelpunkt treffen sich genau zwei Kanten.
- Die Anzahl der Kanten entspricht immer der Anzahl der Ecken.
Zwei Kanten, die sich an einer Ecke treffen, sind normalerweise erforderlich, um einen Winkel zu bilden , der nicht gerade ist (180°); andernfalls werden die kollinearen Liniensegmente als Teile einer einzelnen Seite betrachtet.
Mathematiker verwenden normalerweise "Polygon", um sich nur auf die Form zu beziehen, die aus den Liniensegmenten besteht, nicht auf den eingeschlossenen Bereich. Einige verwenden jedoch "Polygon", um sich auf eine ebene Figur zu beziehen, die von einem geschlossenen Pfad begrenzt ist, der aus einer endlichen Folge besteht von geraden Liniensegmenten (dh durch eine geschlossene polygonale Kette ). Gemäß der verwendeten Definition kann diese Grenze Teil des Polygons selbst sein oder nicht.
Einfache Polygone werden auch Jordan-Polygone genannt , weil man mit dem Jordan-Kurvensatz beweisen kann, dass ein solches Polygon die Ebene in zwei Bereiche teilt, den Bereich innerhalb und den Bereich außerhalb. Ein Polygon in der Ebene ist genau dann einfach, wenn es topologisch einem Kreis entspricht . Sein Inneres entspricht topologisch einer Scheibe .
Schwach einfaches Polygon
Bildet eine Ansammlung von sich nicht kreuzenden Liniensegmenten die Grenze eines Gebiets der Ebene, das topologisch einer Scheibe entspricht, dann wird diese Grenze als schwach einfaches Polygon bezeichnet . Im Bild links ist ABCDEFGHJKLM nach dieser Definition ein schwach einfaches Polygon, wobei die Farbe Blau die Region markiert, deren Grenze es ist. Diese Art von schwach einfachen Polygonen kann in Computergrafik und CAD als Computerdarstellung von polygonalen Bereichen mit Löchern auftreten: Für jedes Loch wird ein "Schnitt" erstellt, um es mit einer äußeren Begrenzung zu verbinden. Unter Bezugnahme auf das obige Bild ist ABCM eine äußere Grenze einer ebenen Region mit einem Loch FGHJ. Der Schnitt ED verbindet das Loch mit dem Äußeren und wird in der resultierenden schwach einfachen polygonalen Darstellung zweimal durchlaufen.
In einer alternativen und allgemeineren Definition von schwach einfachen Polygonen sind sie die Grenzen von Folgen einfacher Polygone desselben kombinatorischen Typs mit der Konvergenz unter der Fréchet-Distanz . Dies formalisiert die Vorstellung, dass ein solches Polygon es Segmenten ermöglicht, sich zu berühren, aber nicht zu kreuzen. Diese Art von schwach einfachen Polygonen muss jedoch nicht die Grenze einer Region bilden, da ihr "Innere" leer sein kann. Unter Bezugnahme auf das obige Bild ist die Polygonkette ABCBA beispielsweise gemäß dieser Definition ein schwach einfaches Polygon: Sie kann als die Grenze des "Zusammendrückens" des Polygons ABCFGHA angesehen werden.
Rechenprobleme
In der Computergeometrie beinhalten mehrere wichtige Rechenaufgaben Eingaben in Form eines einfachen Polygons; Bei jedem dieser Probleme ist die Unterscheidung zwischen Innen und Außen entscheidend bei der Problemdefinition.
- Punkt-in-Polygon- Testen beinhaltet die Bestimmung für ein einfaches Polygon P und einen Abfragepunkt q , ob q innerhalb von P liegt .
- Zur Berechnung der Polygonfläche sind einfache Formeln bekannt ; das heißt, die Fläche des Inneren des Polygons.
-
Polygonpartition ist eine Menge primitiver Einheiten (zB Quadrate), die sich nicht überlappen und deren Vereinigung dem Polygon entspricht. Ein Polygonpartitionsproblem ist ein Problem, eine Partition zu finden, die in gewissem Sinne minimal ist, zum Beispiel: eine Partition mit einer kleinsten Anzahl von Einheiten oder mit Einheiten der kleinsten Gesamtseitenlänge.
- Ein Spezialfall der Polygon Partition Polygon Triangulation : ein einfaches Polygon in Dreiecke geteilt wird . Obwohl konvexe Polygone leicht zu triangulieren sind, ist das Triangulieren eines allgemeinen einfachen Polygons schwieriger, da wir vermeiden müssen, Kanten hinzuzufügen, die sich außerhalb des Polygons kreuzen. Dennoch zeigte Bernard Chazelle 1991, dass jedes einfache Polygon mit n Ecken in Θ ( n ) Zeit trianguliert werden kann , was optimal ist. Derselbe Algorithmus kann auch verwendet werden, um zu bestimmen, ob eine geschlossene Polygonkette ein einfaches Polygon bildet.
- Ein weiterer Sonderfall ist das Kunstgalerieproblem , das sich äquivalent als Partition in eine minimale Anzahl sternförmiger Polygone umformulieren lässt .
- Boolesche Operationen an Polygonen : Verschiedene Boolesche Operationen an den durch polygonale Bereiche definierten Punktmengen.
- Die konvexe Hülle eines einfachen Polygons kann effizienter berechnet werden als die konvexe Hülle anderer Eingabetypen, wie beispielsweise die konvexe Hülle einer Punktmenge.
- Voronoi-Diagramm eines einfachen Polygons
- Mediale Achse / topologisches Skelett / gerades Skelett eines einfachen Polygons
- Offsetkurve eines einfachen Polygons
- Minkowski-Summe für einfache Polygone