Nicht konvexe Polygone und Polygonzüge

In den vorangegangenen Kapiteln wurden ausschließlich konvexe Polygone und Polygonzüge berücksichtigt. Daher sollen nun nicht konvexe Polygone und Polygonzüge betrachtet werden. Diese lassen sich durch Zerlegen in die konvexen Teilsegmente auf die konvexen Polygonzüge zurückführen. In Abbildung 23 ist ein Beispiel für einen nicht konvexen Polygonzug gegeben. Der Graph des Polygonzuges beschreibt bis zum Punkt $P5$ eine Rechtskurve. An der Kante zwischen $P4$ und $P5$ vollzieht sich ein Richtungswechsel, so dass der Graph vom Punkt $P4$ bis zum Ende eine Linkskurve vollzieht. Wenn der Polygonzug nun in zwei Polygonzüge aufgeteilt wird, so dass der Polygonzug in der Mitte der Kante zwischen $P4$ und $P5$ am Punkt $PZ$ geteilt wird, ergeben sich zwei konvexe Polygonzüge. Diese können durch das in Kapitel 3.2 erläuterte Verfahren approximiert werden.

Abbildung 23: Zerlegen eines nicht konvexen Polygonzuges am Punkt PZ.

Hier wird ein großer Vorteil aus der Tangentenwahl bei den Endpunkten der konvexen Polygonzüge deutlich. Die Bézierkurven, welche die einzelnen Teilsegmente approximieren, passen stetig aneinander. Das selbe Verfahren kann für nicht konvexe Polygone angewendet werden. Erst werden diese in die konvexen Teilsegmente zerlegt und anschließend werden die berechneten Bézierkurven wieder zusammengefügt.

Alternativ könnten Bedingungen aufgestellt werden, die ein Gleichungssystem zur Folge haben, das eine Bézierkurve beschreibt, die einen solchen Übergang von einer Rechts- in eine Linkskurve approximieren kann. Dies würde eine globale Approximation eines nicht konvexen Polygons oder Polygonzuges ermöglichen. Allerdings sollten diese Bedingungen einerseits mit zwei oder drei quadratischen Bézierkurven für eine solche Kante auskommen und gleichzeitig keine Sonderfälle erzeugen, die wiederrum durch komplexe weitere Bedingungen abgefangen werden müssen. Das Aufstellen solcher Bedingungen ist schwer möglich. Daher wird von dieser Vorgehensweise Abstand genommen.

Auf der anderen Seite stellt die Approximation durch das Aufteilen eine durchaus akzeptable Möglichkeit dar. Eine Kante, an der der Übergang stattfindet wird bei den quadratischen Bézierkurven zwar durch zwei elementare Bézierkurven approximiert, da mit einer quadratischen elementaren Bézierkurve kein Richtungswechsel dargestellt werden kann. Trotzdem wurde das Minimum an Komplexität, das bei der Approximation solcher Kanten möglich ist, erreicht.