Triangulation eines komplexen Polygons

[Runtime]

Hallo zusammen,

ich suche seit einiger Zeit einen Algorithmus, mit dem man ein komplexes Polygon triangulieren kann, wie
in der Java API oder mit OpenGL. Gefunden hab ich einen Delaunay Triangulationsalgorithmus, der
allerdings nur für simple Polygons funktioniert. Kann man den so verändern, dass dies auch für komplexe Polygons funktioniert, oder bin ich da total falsch?

Grüsse
Runtime

 

[Landei]

Slick2D hat ein Triangulator-Interface und diverse Implementierungen: Triangulator (Slick - The 2D Library)

 

[Runtime]

	private Vector2f[] triangulate(Vector2f[] result) {
		// Step 1: Compute all angles
		contour.computeAngles();
		for (PointBag hole = holes; hole != null; hole = hole.next) {
			hole.computeAngles();
		}

		// Step 2: Connect the holes with the contour (build bridges)
		while (holes != null) {
			Point pHole = holes.first;
			outer: do {
				if (pHole.angle <= 0) {
					Point pContour = contour.first;
					do {
						inner: if (pHole.isInfront(pContour)
								&& pContour.isInfront(pHole)) {
							if (!contour.doesIntersectSegment(pHole.pt,
									pContour.pt)) {
								PointBag hole = holes;
								do {
									if (hole.doesIntersectSegment(pHole.pt,
											pContour.pt)) {
										break inner;
									}
								} while ((hole = hole.next) != null);

								Point newPtContour = getPoint(pContour.pt);
								pContour.insertAfter(newPtContour);

								Point newPtHole = getPoint(pHole.pt);
								pHole.insertBefore(newPtHole);

								pContour.next = pHole;
								pHole.prev = pContour;

								newPtHole.next = newPtContour;
								newPtContour.prev = newPtHole;

								pContour.computeAngle();
								pHole.computeAngle();
								newPtContour.computeAngle();
								newPtHole.computeAngle();

								// detach the points from the hole
								holes.first = null;
								break outer;
							}
						}
					} while ((pContour = pContour.next) != contour.first);
				}
			} while ((pHole = pHole.next) != holes.first);

			// free the hole
			holes = freePointBag(holes);
		}

		// Step 3: Make sure we have enough space for the result
		int numTriangles = contour.countPoints() - 2;
		int neededSpace = numTriangles * 3 + 1; // for the null
		if (result.length < neededSpace) {
			result = (Vector2f[]) Array.newInstance(result.getClass()
					.getComponentType(), neededSpace);
		}

		// Step 4: Extract the triangles
		int idx = 0;
		for (;;) {
			Point pContour = contour.first;

			if (pContour == null) {
				break;
			}
			// Are there 2 or less points left ?
			if (pContour.next == pContour.prev) {
				break;
			}

			outer: do {
				if (pContour.angle > 0) {
					Point prev = pContour.prev;
					Point next = pContour.next;

					if (next.next == prev || prev.isInfront(next) && next.isInfront(prev)) {
						if (!contour.doesIntersectSegment(prev.pt, next.pt)) {
							result[idx++] = pContour.pt;
							result[idx++] = next.pt;
							result[idx++] = prev.pt;
							break outer;
						}
					}
				}
			} while ((pContour = pContour.next) != contour.first);
			
			// remove the point - we do it in every case to prevent endless loop
			Point prev = pContour.prev;
			Point next = pContour.next;

			contour.first = prev;
			pContour.unlink();
			freePoint(pContour);

			next.computeAngle();
			prev.computeAngle();
		}

		// Step 5: Append a null (see Collection.toArray)
		result[idx] = null;

		// Step 6: Free memory
		contour.clear();

		// Finished !
		return result;
	}

Wird ein wenig Zeit in anspruch nehmen. :autsch:

 

[Marco13]

Das ist auch nicht so trivial, wenn es "gut" sein soll. Wenn es NUR um Triangulieren geht, hält sich der Aufwand vielleicht in Grenzen, da gibt's dann sowas wie Ear Clipping Method (Polygon triangulation - Wikipedia, the free encyclopedia ). Das reicht auf jeden Fall, wenn man die Dreieck nur rendern will. Aber wenn die Dreiecke "gut" sein sollen (d.h. alle möglichst gleichseitig, und insbesondere keine spitzen Winkel - z.B. für irgendeine Simulation) kommt man um was Delaunay-Artiges nicht drumrum.

Der Delaunay ist erstmal eher ein "Konzept", für die praktische Anwendung (für Polygone mit Löchern usw.) braucht's dann noch mehr....

Was genau die Slick-Triangulierung macht, weiß ich nicht und grandioserweise ist API-Doku dazu ziemlich drüftig (müßte man sich mal den Source Code ansehen). Ich hatte irgendwann auch mal danach gesucht, und eine der wenigen "mächtigeren" pure Java-Lösungen war unter jtem im "numericalMethods"-Package die Klasse "Ruppert" (erbt von Delaunay). Die ist schon sehr gut - hat noch einige... glitches (die angle- und area-Constraints richtig zu setzen ist ziemlich tricky) aber sollte man sich auf jeden Fall mal ansehen.

DIE Triangulierungsbibliothek schlechthin ist Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator - aber leider erstmal nur für C. Ich hatte mal angefangen, dort ein Java/JNI-Interface drumzustricken, aber das ist noch nicht veröffentlicht. (Ursprünglich wollte ich sie mal nach Java portieren, aber... :autsch: die ist schon SEHR, SEHR C... (die C-este C-lib, die ich kenne :autsch: ))

 

[Runtime]

Ich brauche die Dreiecke nur zum Rendern, es dürfen auch neue Dreiecke generiert werden. Der Algorithmus muss einfach schnell
sein. Ear Clipping ist deshalb suboptimal, weil die Zeit quadratisch ansteigt und das Polygon sehr viele Punkte enthalten kann. Das
Polygon in monotone Polygons zu splitten wäre ein guter Weg, aber der kann nicht einfach so mit mehreren Konturen umgehen.
Eine Lösung wäre zuerst einen Bentley-Ottmann anzuwenden, aber damit wird der Algorithmus recht langsam. Gibts eine
schnellere Lösung für dieses Problem? Es dürfen auch mitten im Polygon neue Punkte für die Triangulation eingefügt werden,
solange das gerenderte Ergebnis nicht verfälscht wird.