Edge * e = new Edge ( a, b );
if (frontier.find ( e )) frontier.del ( e );
else {8. Основные алгоритмы вычислительной геометр
e -> flip (); frontier.insert (e );
}
}
static Edge * hullEdge (Vector2D s Q, int n ) {
int m = 0;
for (int i = 1; i < n; i++ ) if(s[i]<s[m]) m = i;
swap ( s [0], s [m]);
for ( m = 1, i = 2; i < n; i++ ) {
int els = s [i].classify ( s [0], s [m]);
if ( els == LEFT || els == BETWEEN ) m = i;
}
return new Edge ( s [0], s [m]);
}
static Polygon * traingle ( const Vector2D& a, const Vector2D& b,
const Vector2D& c)
{
Polygon * t = new Polygon;
t -> addVertex ( a ); t -> addVertex ( b ); t -> addVertex ( c );
return t;
static int mate ( Edge& e, Vector2D s Q, int n, Vector2D& p ) {
float t;
float bestT = MAXFLOAT; Edge f ( e );
f.rot ();
for (int U= 0; i < n; i++ )
{ (
if ( s [i].classify ( e.org, e.dest) == RIGHT ) {
Edge g (e.dest, s [i]); g.rot ();
if (f.intersect ( g, t) == SKEW && t < bestT ) {
bestT = t; P = s [i];
}
}Компьютерная графика. Полигональные модели
}
return t < MAXFLOAT;
}
Array * delaunayTriangulate ( Vector2D s 0, int n ) {
Array * traingles = new Array; Dictionary frontier ( edgeCmp ); Vector2D p;
Edge * e = hulIEdge ( s, n );
* fronier.insert ( e );
while (Ifrontier.isEmpty ()) {
e = fronier.femoveAt ( 0 );
if ( mate (*e, s, n, p )) {
updateFrontier (frontier, p, e -> org ); updateFrontier (frontier, e -> dest, p ); traingles -> insert (
triangle ( e -> org, e -> dest, p ));
}
delete e;
}
return triangles;
}Треугольники, образуемые в процессе триангуляции, хранятся в массиве traingles. Все живые ребра хранятся в словаре frontier. Причем каждое ребро направлено так, что неизвестная для него область лежит справа.
Рассмотрим, каким образом функция updateFrontier изменяет словарь живых ребер. При добавлении к массиву triangles нового треугольника / изменяется состояние всех трех ребер треугольника. Ребро треугольника, примыкающее к границе, из живого становится мертвым. Каждое из двух оставшихся ребер изменяет свое состояние из спящего в живое, если оно ранее не было записано в словарь, или из живого в мертвое, если оно в словаре уже было.