typedef struct
{
float x, y;
} Point2D;
typedef struct
{
Point2D p1, p2, p3;
} Triangle2D;
Triangle2D* Terrain::Process( int nb_points, Point2D *points, int& nb_triangles )
{
/* allocate and initialize list of Vertices in polygon */
Triangle2D *triangles = new Triangle2D[nb_points-2];
nb_triangles = 0;
int n = nb_points;
if ( n < 3 ) return false;
int *V = new int[n];
/* we want a counter-clockwise polygon in V */
if ( 0.0f < Area(nb_points, points) )
for (int v=0; v<n; v++) V[v] = v;
else
for(int v=0; v<n; v++) V[v] = (n-1)-v;
int nv = n;
/* remove nv-2 Vertices, creating 1 triangle every time */
int count = 2*nv; /* error detection */
for(int m=0, v=nv-1; nv>2; )
{
/* if we loop, it is probably a non-simple polygon */
if (0 >= (count--))
{
//** Triangulate: ERROR - probable bad polygon!
// delete[] triangles;
printf( "Degenerate polygon\n" );
return triangles;
}
/* three consecutive vertices in current polygon, <u,v,w> */
int u = v ; if (nv <= u) u = 0; /* previous */
v = u+1; if (nv <= v) v = 0; /* new v */
int w = v+1; if (nv <= w) w = 0; /* next */
if ( Snip(nb_points, points,u,v,w,nv,V) )
{
int a,b,c,s,t;
/* true names of the vertices */
a = V[u]; b = V[v]; c = V[w];
/* output Triangle */
/* result.push_back( points[a] );
result.push_back( points[b] );
result.push_back( points[c] );*/
triangles[nb_triangles].p1 = points[a];
triangles[nb_triangles].p2 = points[b];
triangles[nb_triangles].p3 = points[c];
nb_triangles++;
m++;
/* remove v from remaining polygon */
for(s=v,t=v+1;t<nv;s++,t++) V[s] = V[t]; nv--;
/* resest error detection counter */
count = 2*nv;
}
}
delete V;
return triangles;
}
float Terrain::Area( int nb_points, Point2D *points )
{
int n = nb_points;
float A=0.0f;
for(int p=n-1,q=0; q<n; p=q++)
{
A+= points[p].x*points[q].y - points[q].x*points[p].y;
}
return A*0.5f;
}
bool Terrain::Snip( int nb_points, Point2D *points,int u,int v,int w,int n,int *V )
{
int p;
float Ax, Ay, Bx, By, Cx, Cy, Px, Py;
Ax = points[V[u]].x;
Ay = points[V[u]].y;
Bx = points[V[v]].x;
By = points[V[v]].y;
Cx = points[V[w]].x;
Cy = points[V[w]].y;
if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return false;
for (p=0;p<n;p++)
{
if( (p == u) || (p == v) || (p == w) ) continue;
Px = points[V[p]].x;
Py = points[V[p]].y;
if (InsideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false;
}
return true;
}
bool Terrain::InsideTriangle(float Ax, float Ay,
float Bx, float By,
float Cx, float Cy,
float Px, float Py)
{
float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
float cCROSSap, bCROSScp, aCROSSbp;
ax = Cx - Bx; ay = Cy - By;
bx = Ax - Cx; by = Ay - Cy;
cx = Bx - Ax; cy = By - Ay;
apx= Px - Ax; apy= Py - Ay;
bpx= Px - Bx; bpy= Py - By;
cpx= Px - Cx; cpy= Py - Cy;
aCROSSbp = ax*bpy - ay*bpx;
cCROSSap = cx*apy - cy*apx;
bCROSScp = bx*cpy - by*cpx;
return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
}
976130.4 6449595.49999999976127.2 6449598.09999999976124.7 6449601.79999999976122.4 6449605.79999999976120.3 6449610.09999999976117.2 6449615.39999999976115.7 6449619.29999999976114.9 6449623.59999999976115.7 6449627.49999999976119.4 6449630.69999999976121.7 6449634.89999999976120.6 6449639.49999999