Ear Clipping Triangulierung - Versionsgeschichte

DGLBot: Der Ausdruck ''(.*?)'' wurde ersetzt mit ''$1''.

2009-03-10T18:04:08Z

Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.

Igel457: /* Grundidee */

2008-04-03T19:22:56Z

‎Grundidee

Flash: /* Vor- und Nachteile, Alternativen */

2008-04-02T21:22:58Z

‎Vor- und Nachteile, Alternativen

Flash: /* Grundidee */

2008-04-02T21:21:37Z

‎Grundidee

Flash: /* Vor- und Nachteile, Alternativen */

2008-04-02T21:19:51Z

‎Vor- und Nachteile, Alternativen

Flash: /* Vor- und Nachteile, Alternativen */

2008-04-02T21:19:25Z

‎Vor- und Nachteile, Alternativen

Igel457: /* Beispielimplementierung */

2008-03-30T12:35:53Z

‎Beispielimplementierung

Igel457: /* Allgemeines */

2008-03-30T12:33:52Z

‎Allgemeines

I0n0s: Rechtschreibung

2008-03-30T00:02:10Z

Rechtschreibung

Igel457: /* Vor- und Nachteile, Alternativen */

2008-03-29T20:15:27Z

‎Vor- und Nachteile, Alternativen

@@ Zeile 24: / Zeile 24: @@
 Im Nachfolgenden findet sich eine einfache Beispielimplementierung des Ear Clipping Algorithmus. Bitte beachtet, dass die Punkte des Polygon im Uhrzeigersinn angeordnet sein müssen und das Polygon keine Überschneidungen haben darf.
-<pascal>
+<source lang="pascal">
 uses
    Classes, Types;
@@ Zeile 157: / Zeile 157: @@
    lst.Free;
 end;
-</pascal>
+</source>
 ==Weblinks==

@@ Zeile 5: / Zeile 5: @@
 ===Grundidee===
-Nimmt aus einem Polygon die beiden benachbarten Punkte eines Punktes, so erhält man ein Dreieck. Ein Polygon beinhaltet immer ein solches Dreieck, in dem keine anderen Punkte des Polygons liegen. Dieses Dreieck wird "Ohr" genannt. Schneidet man dieses Dreieck ab, so erhält man ein neues Polygon, für das die Regel wieder angewandt werden kann. Die nachfolgende Grafik veranschaulicht das Prinzip:
+Nimmt man aus einem Polygon die beiden benachbarten Punkte eines Punktes, so erhält man ein Dreieck. Ein Polygon beinhaltet immer ein solches Dreieck, in dem keine anderen Punkte des Polygons liegen. Dieses Dreieck wird "Ohr" genannt. Schneidet man dieses Dreieck ab, so erhält man ein neues Polygon, für das die Regel wieder angewandt werden kann. Die nachfolgende Grafik veranschaulicht das Prinzip:
 [[Bild:Earclipping.png|framed|center|Ablauf des Ear Clipping Verfahrens]]

@@ Zeile 12: / Zeile 12: @@
 ===Vor- und Nachteile, Alternativen===
 Der wahre Vorteil dieses Algorithmus ist, dass er einfach zu implementieren und nachvollziehen ist.
 Jedoch hat er bei guter Implementierung eine quadratische Laufzeit. Das bedeutet, dass er gerade bei größeren Datenmengen in zeitkritischen Anwendungen nicht zu gebrauchen ist. Zudem können gerade bei Polygonen mit unregelmäßiger Punktverteilung Dreiecke von sehr unterschiedlicher Größe entstehen. Hierbei ist es besonders problematisch, dass immer wieder sehr kleine Dreiecke entstehen (siehe letztes Dreieck im Beispiel oben). Auf manchen Grafikkarten kann dies zu Bildfehlern bei der Füllung/Texturierung führen.
@@ Zeile 19: / Zeile 18: @@
 Die [[Delaunay-Triangulation]] und das [[Voronoi-Diagramm]] sind hier als Alternativen hervorzuheben. Diese Algorithmen erstellen deutlich ausgewogenere Dreiecksnetze.
-Die Earclipping Triangulierung lässt sich zwar von Natur aus bei [[Konvex|konkaven]] Polygonzügen anwenden, hat jedoch Probleme mit Überschneidungen oder so genannten "Inseln" im Polygon (siehe Bild rechts). Dieses Problem lässt sich dadurch lösen, dass das Polygon zuvor in mehrere Polygone ohne Überschneidungen und Inseln unterteilt wird.
+Die Earclipping Triangulierung lässt sich zwar von Natur aus bei [[Konvex|konkaven]] Polygonzügen anwenden, hat jedoch Probleme mit Überschneidungen oder so genannten "Inseln" im Polygon (siehe nachfolgendes Bild). Dieses Problem lässt sich dadurch lösen, dass das Polygon zuvor in mehrere Polygone ohne Überschneidungen und Inseln unterteilt wird.
 ===Beispielimplementierung===

@@ Zeile 7: / Zeile 7: @@
 Nimmt aus einem Polygon die beiden benachbarten Punkte eines Punktes, so erhält man ein Dreieck. Ein Polygon beinhaltet immer ein solches Dreieck, in dem keine anderen Punkte des Polygons liegen. Dieses Dreieck wird "Ohr" genannt. Schneidet man dieses Dreieck ab, so erhält man ein neues Polygon, für das die Regel wieder angewandt werden kann. Die nachfolgende Grafik veranschaulicht das Prinzip:
-[[Bild:Earclipping.png]]
+[[Bild:Earclipping.png|framed|center|Ablauf des Ear Clipping Verfahrens]]
 Der Algorithmus lässt sich noch verbessern, indem man bestimmt, ob der aktuell ausgewählte Punkt an einer konvexen oder konkaven Ecke des Polygons liegt. Handelt es sich um eine konkave Ecke, so kann man direkt zum nächsten Punkt springen und dort seine Überprüfungen anstellen.

@@ Zeile 12: / Zeile 12: @@
 ===Vor- und Nachteile, Alternativen===
 Der wahre Vorteil dieses Algorithmus ist, dass er einfach zu implementieren und nachvollziehen ist.
 Jedoch hat er bei guter Implementierung eine quadratische Laufzeit. Das bedeutet, dass er gerade bei größeren Datenmengen in zeitkritischen Anwendungen nicht zu gebrauchen ist. Zudem können gerade bei Polygonen mit unregelmäßiger Punktverteilung Dreiecke von sehr unterschiedlicher Größe entstehen. Hierbei ist es besonders problematisch, dass immer wieder sehr kleine Dreiecke entstehen (siehe letztes Dreieck im Beispiel oben). Auf manchen Grafikkarten kann dies zu Bildfehlern bei der Füllung/Texturierung führen.
@@ Zeile 17: / Zeile 18: @@
 Beim zuletzt genannten Problem schneiden andere Algorithmen deutlich besser ab. Jedoch sind diese um einiges komplizierter.
 Die [[Delaunay-Triangulation]] und das [[Voronoi-Diagramm]] sind hier als Alternativen hervorzuheben. Diese Algorithmen erstellen deutlich ausgewogenere Dreiecksnetze.
-[[Bild:NonSimplePolygon.png|framed|right|Spezielle Polygone die anders zu behandeln sind.]]
 Die Earclipping Triangulierung lässt sich zwar von Natur aus bei [[Konvex|konkaven]] Polygonzügen anwenden, hat jedoch Probleme mit Überschneidungen oder so genannten "Inseln" im Polygon (siehe Bild rechts). Dieses Problem lässt sich dadurch lösen, dass das Polygon zuvor in mehrere Polygone ohne Überschneidungen und Inseln unterteilt wird.

@@ Zeile 1: / Zeile 1: @@
 ==Allgemeines==
-Bei dem "Ear Clipping"-Algorithmus, handelt es sich um ein einfaches Verfahren, nach der beliebige, sich nicht überschneidende Polygone in Dreiecke unterteilt ([[Triangulierung|trianguliert]]) werden können. Dies wird notwendig, da moderne Grafikkarten auf das Darstellen von Dreiecken optimiert sind und vor allem mit konkaven Polygonen nicht zurecht kommen.
+Bei dem "Ear Clipping"-Algorithmus, handelt es sich um ein einfaches Verfahren, nach dem beliebige, sich nicht überschneidende Polygone in Dreiecke unterteilt ([[Triangulierung|trianguliert]]) werden können. Dies wird notwendig, da moderne Grafikkarten auf das Darstellen von Dreiecken optimiert sind und vor allem mit konkaven Polygonen nicht zurecht kommen.
 ==Theorie==

@@ Zeile 17: / Zeile 17: @@
 Die [[Delaunay-Triangulation]] und das [[Voronoi-Diagramm]] sind hier als Alternativen hervorzuheben. Diese Algorithmen erstellen deutlich ausgewogenere Dreiecksnetze.
-Die Earclipping Triangulierung lässt sich zwar von Natur aus bei [[konkav|konkaven]] Polygonzügen anwenden, hat jedoch Probleme mit Überschneidungen oder so genannten "Inseln" im Polygon. Dieses Problem lässt sich dadurch lösen, dass das Polygon zuvor in mehrere Polygone ohne Überschneidungen und Inseln unterteilt wird.
+Die Earclipping Triangulierung lässt sich zwar von Natur aus bei [[Konvex|konkaven]] Polygonzügen anwenden, hat jedoch Probleme mit Überschneidungen oder so genannten "Inseln" im Polygon. Dieses Problem lässt sich dadurch lösen, dass das Polygon zuvor in mehrere Polygone ohne Überschneidungen und Inseln unterteilt wird.
 [[Bild:NonSimplePolygon.png]]