C++ Softwarepraktikum WS 2008/2009

Algorithmus

Initialisierung: Es wird ein Dreieck T um alle Punkte der Eingabemenge L gelegt. Dadurch wird sichergestellt, dass die Dreieckslokalisierung für jeden Punkt ausgeführt werden kann. T hat durch die Delaunay-Eigenschaft keinen Einfluß auf die entstandene Triangulierung und kann deshalb am Ende entfernt werden. Das Ergebnis ist die Triangulierung von L in G.

set<point> L;    /* Eingabemenge */
Graph G;         /* initial leer */

point s = init(L);
while (!L.empty()) {
	point p = L.pop();
	triangle D_dest = find_face(s, p);
	triangulate(D_dest, p);
	s = p;
}

Der Algorithmus arbeitet inkrementell, d.h. für jeden neu eingegebenen Punkt 'dest' wird die bereits vorhandene Triangulierung entsprechend erweitert.

Erster Schritt ist die Lokalisierung des Faces 'X' in G, das das Dreieck D_dest, das 'dest' enthält, repräsentiert.

Anschließend wird 'dest' als neuer Knoten in den Graphen eingefügt und für alle Dreiecke D_a, die an D_dest mit einer Seite 'a' angrenzen, wird die Delaunay-Bedingung wieder hergestellt: Der Kreis um die drei Eckpunkte von D_a darf den neuen Punkt 'dest' nicht enthalten, ansonsten muss anders trianguliert werden.

find_face():

find_next:
e = f;

while ((e = G.cyclic_adj_succ(G.reversal(e))) != f) {
	if (intersects(G[G.source(e)], G[G.target(e)],
	               G[s], dest)) {
		f = G.reversal(e);
		goto find_next;
	}
}

return f;

Es wird die Strecke vom zuletzt eingefügten Punkt 's' zum neu eingefügten Punkt 'dest' gebildet. Mit Hilfe von zwei Orientation-Tests (Abb. 1: Pfeile in Cyan) wird das Startdreieck 'bsa' bestimmt. ‚dest’ liegt darin bzw. 'line' läuft hindurch.

Die Methode sucht nun iterativ nach dem Face in G, das 'dest' enthält. f₁ wird als die zu ab gehörige Kante in G definiert. In Iteration i wird im aktuellen Face nach einer Kante f_i+1 gesucht, die 'line' schneidet. Es wird mit dem dort angrenzenden Face fortgefahren. Da in jedem Face höchstens zwei Seiten von der Strecke geschnitten werden, ist der Weg eindeutig bestimmt.

Dies wird solange wiederholt bis bei einem Face von f_i aus kein f_i+1 mehr gefunden wird. f_end ist dann reversal(fi). Das zum Face gehörige Dreieck D_dest enthält ‚dest’. Zurückgegeben wird die Kante f_end. Der Aufbau der Suche garantiert, dass der gesuchte Punkt links der Kante liegt.

triangulate():

while (!check.empty()) {
	a = check.pop_back();
	b = G.cyclic_adj_pred(a);
	c = G.cyclic_adj_pred(G.reversal(b));
	
	bool flip;
	if (orientation(G[G.source(b)],
	                G[G.target(b)], G[n]) == -1 &&
	    orientation(G[G.source(c)],
	                G[G.target(c)], G[n]) == -1 &&
	    orientation(G[G.source(a)],
	                G[G.target(a)], G[n]) == 1) {
		flip = false;
	} else {
		flip = incircle(G[G.source(a)],
		                G[G.target(a)],
		                G[G.target(b)],
		                G[n]);
	}
	
	if (flip) {
		G.del_edge(a);
		check.push_back(c);
		check.push_back(b);
	} else {
		edge ra = G.reversal(a);
		b = G.new_edge(n, ra, false, before);
		c = G.new_edge(a, n, false, behind);
		G.set_reversal(b, c);
	}
}

Diese Methode fügt einen neuen Knoten 'n' mit Information 'dest' in den Graphen ein. Es wird ein Stack 'check' aufgebaut, der die Kanten beinhaltet, die noch auf die Delaunay-Bedingung überprüft werden müssen.

Jede Kante 'a' in 'check' steht für dasjenige Face 'X', das rechts von 'a' liegt. Dabei sei D_a das von 'X' repräsentierte Dreieck. Falls source(a) und target(a) auf der konvexen Hülle liegen, so existiert 'X' nicht. Allein mit Hilfe des Graphs kann dieser Fall nicht abgefragt werden, denn in beiden Fällen gibt es eine Kante 'b' als zyklischen Vorgänger von 'a'. Deshalb wird mit Hilfe von Orientation-Tests überprüft, ob 'dest' in D_a liegt. Existiert kein 'X', so entfällt auch die Überprüfung auf seine Delaunay-Tauglichkeit.

'check' enthält die Kanten immer entgegen des Uhrzeigersinns. Beginnend mit der zuerst eingefügten Kante 'a' wird die Delaunay-Bedingung für das jeweilige D_a überprüft.

Ergibt der Incircle-Test, dass der Punkt 'dest' innerhalb des Kreises um die drei Eckpunkte von D_a liegt, so ist die Delaunay-Bedingung verletzt. Die beiden Kanten 'c' und 'b' werden auf den Stack 'check' gelegt. Eine Kante von source(a) zu 'n' wird erst ab dem D_a eingefügt, das die Delaunay-Bedingung nicht mehr verletzt. Dadurch werden doppelte Kanten von source(a) ausgehend vermieden. Somit wird source(a) genau dann mit 'n' verbunden, wenn auch source(a) im nächsten Schleifendurchlauf wechselt. Da die Kanten um D_dest entgegen des Uhrzeigersinns durchlaufen werden, werden alle neuen Kanten zu 'n' auch entgegen des Uhrzeigersinns in seine Adjazenzliste eingefügt.

Ist 'check' leer, so wurde die Delaunay-Bedingung für alle Dreiecke wieder hergestellt. Der für 'dest' neu eingefügte Knoten 'n' wird zurückgegeben, um von dieser Stelle aus mit dem Algorithmus fortzufahren, sobald ein neuer Punkt eingeben wird.