В случае если неизвестная область оказывается бесконечной плоскостью, то ребро просто умирает.
Для написания алгоритма понадобится класс Edge, приводимый ниже.
О // File edge.h
#ifndef_EDGE_
#define___EDGE_
#inc!ude "vector2d,h"
class Edge {
public:
Vector2D org; Vector2D dest;
Edge ( const Vector2D& p1, const Vector2D& p2 )
8. OcHOBHbie anropuT ibi BbNucnuTenbHoii re
{
org = p1; dest = p2;
}
Edge ( const Edge& e ) {
org =e.org; dest = e.dest;
}
Edge () {}
Edge& flip (); Edge& rot ();
Vector2D point (float t) {
return org + t * (dest - org);
}
int intersect ( const Edge&, float& );
};
enum // types of edge intersection {
COLLINEAR, PARALLEL, SKEW
};
#endif
0 // File edge.cpp #include "edge.h"
Edge& Edge :: rot ()
Vector2D m = 0.5 * (org + dest);// center of the edge Vector2D n ( 0.5*(dest.y -org.y), 0.5*(org.x - dest.x));
org = m - n; dest = m + n;
return *this;
Edge& Edge :: flip ()
Vector2D tmp = org;
org = dest; dest = tmp;
return *this;
}
Mit Edge :: intersect ( const Edge& e, float& t)
Vector2D n ( e.dest.y - e.org.y, e.org.x - e.dest.x ); float denom = n & (dest - org);Компьютерная графика. Полигональные модели
..' ( denom == 0.0 ) {
int els = org.classify ( e.org, e.dest);
if ( els == LEFT || els == RIGHT ) return PARALLEL;
return COLLINEAR;
}
t = - (n & (org - e.org)) / denom; return SKEW;
}Ниже приводится программа для построения триангуляции Делоне зада набора точек.
(21 // File delaunay.cpp #include "polygon.h" #include "array.h" #include "dict.h" #include "edge.h" #include <values.h>
template <class T> void swap (T a, T b )
{
Tc;с = a; a = b; b = a;
static int edgeCmp ( Edge * a, Edge * b ) {
if ( a -> org < b -> org ) return -1;
if ( a -> org > b -> org ) return 1;
if ( a -> dest < b -> dest) return -1;
if ( a -> dest > b -> dest) return 1;
return 0;
}
static void updateFrontier ( Dictionary& frontier, Vector2D& a, Vector2D& b ) {