www.pudn.com > 2D.rar > tri.c
/*
This code is described in "Computational Geometry in C" (Second Edition),
Chapter 1. It is not written to be comprehensible without the
explanation in that book.
Input: 2n integer coordinates for vertices of a simple polygon,
in counterclockwise order. NB: the code will not work
for points in clockwise order!
Output: the diagonals of a triangulation, in PostScript.
Compile: gcc -o tri tri.c (or simply: make)
Written by Joseph O'Rourke, with contributions by Min Xu.
Last modified: October 1997
Questions to orourke@cs.smith.edu.
--------------------------------------------------------------------
This code is Copyright 1998 by Joseph O'Rourke. It may be freely
redistributed in its entirety provided that this copyright notice is
not removed.
--------------------------------------------------------------------
*/
#include
#include
#define EXIT_FAILURE 1
#define X 0
#define Y 1
typedef enum { FALSE, TRUE } bool;
#define DIM 2 /* Dimension of points */
typedef int tPointi[DIM]; /* Type integer point */
typedef struct tVertexStructure tsVertex; /* Used only in NEW(). */
typedef tsVertex *tVertex;
struct tVertexStructure {
int vnum; /* Index */
tPointi v; /* Coordinates */
bool ear; /* TRUE iff an ear */
tVertex next,prev;
};
/* Global variable definitions */
tVertex vertices = NULL; /* "Head" of circular list. */
int nvertices = 0; /* Total number of polygon vertices. */
#include "macros.h" /* NEW, ADD */
/*---------------------------------------------------------------------
Function prototypes.
---------------------------------------------------------------------*/
int AreaPoly2( void );
void Triangulate( void );
void EarInit( void );
bool Diagonal( tVertex a, tVertex b );
bool Diagonalie( tVertex a, tVertex b );
bool InCone( tVertex a, tVertex b );
int Area2( tPointi a, tPointi b, tPointi c );
int AreaSign( tPointi a, tPointi b, tPointi c );
bool Xor( bool x, bool y );
bool Left( tPointi a, tPointi b, tPointi c );
bool LeftOn( tPointi a, tPointi b, tPointi c );
bool Collinear( tPointi a, tPointi b, tPointi c );
bool Between( tPointi a, tPointi b, tPointi c );
bool Intersect( tPointi a, tPointi b, tPointi c, tPointi d );
bool IntersectProp( tPointi a, tPointi b, tPointi c, tPointi d );
tVertex MakeNullVertex( void );
void ReadVertices( void );
void PrintVertices( void );
void PrintDiagonal( tVertex a, tVertex b );
void PrintPoly( void );
/*-------------------------------------------------------------------*/
main()
{
ReadVertices();
PrintVertices();
printf("%%Area of polygon = %g\n", 0.5 * AreaPoly2() );
Triangulate();
printf("showpage\n%%%%EOF\n");
}
/*---------------------------------------------------------------------
Returns twice the signed area of the triangle determined by a,b,c.
The area is positive if a,b,c are oriented ccw, negative if cw,
and zero if the points are collinear.
---------------------------------------------------------------------*/
int Area2( tPointi a, tPointi b, tPointi c )
{
return
(b[X] - a[X]) * (c[Y] - a[Y]) -
(c[X] - a[X]) * (b[Y] - a[Y]);
}
/*---------------------------------------------------------------------
Exclusive or: TRUE iff exactly one argument is true.
---------------------------------------------------------------------*/
bool Xor( bool x, bool y )
{
/* The arguments are negated to ensure that they are 0/1 values. */
/* (Idea due to Michael Baldwin.) */
return !x ^ !y;
}
/*---------------------------------------------------------------------
Returns true iff ab properly intersects cd: they share
a point interior to both segments. The properness of the
intersection is ensured by using strict leftness.
---------------------------------------------------------------------*/
bool IntersectProp( tPointi a, tPointi b, tPointi c, tPointi d )
{
/* Eliminate improper cases. */
if (
Collinear(a,b,c) ||
Collinear(a,b,d) ||
Collinear(c,d,a) ||
Collinear(c,d,b)
)
return FALSE;
return
Xor( Left(a,b,c), Left(a,b,d) )
&& Xor( Left(c,d,a), Left(c,d,b) );
}
/*---------------------------------------------------------------------
Returns true iff c is strictly to the left of the directed
line through a to b.
---------------------------------------------------------------------*/
bool Left( tPointi a, tPointi b, tPointi c )
{
return AreaSign( a, b, c ) > 0;
}
bool LeftOn( tPointi a, tPointi b, tPointi c )
{
return AreaSign( a, b, c ) >= 0;
}
bool Collinear( tPointi a, tPointi b, tPointi c )
{
return AreaSign( a, b, c ) == 0;
}
/*---------------------------------------------------------------------
Returns TRUE iff point c lies on the closed segement ab.
First checks that c is collinear with a and b.
---------------------------------------------------------------------*/
bool Between( tPointi a, tPointi b, tPointi c )
{
tPointi ba, ca;
if ( ! Collinear( a, b, c ) )
return FALSE;
/* If ab not vertical, check betweenness on x; else on y. */
if ( a[X] != b[X] )
return ((a[X] <= c[X]) && (c[X] <= b[X])) ||
((a[X] >= c[X]) && (c[X] >= b[X]));
else
return ((a[Y] <= c[Y]) && (c[Y] <= b[Y])) ||
((a[Y] >= c[Y]) && (c[Y] >= b[Y]));
}
/*---------------------------------------------------------------------
Returns TRUE iff segments ab and cd intersect, properly or improperly.
---------------------------------------------------------------------*/
bool Intersect( tPointi a, tPointi b, tPointi c, tPointi d )
{
if ( IntersectProp( a, b, c, d ) )
return TRUE;
else if ( Between( a, b, c )
|| Between( a, b, d )
|| Between( c, d, a )
|| Between( c, d, b )
)
return TRUE;
else return FALSE;
}
/*---------------------------------------------------------------------
Returns TRUE iff (a,b) is a proper internal *or* external
diagonal of P, *ignoring edges incident to a and b*.
---------------------------------------------------------------------*/
bool Diagonalie( tVertex a, tVertex b )
{
tVertex c, c1;
/* For each edge (c,c1) of P */
c = vertices;
do {
c1 = c->next;
/* Skip edges incident to a or b */
if ( ( c != a ) && ( c1 != a )
&& ( c != b ) && ( c1 != b )
&& Intersect( a->v, b->v, c->v, c1->v )
)
return FALSE;
c = c->next;
} while ( c != vertices );
return TRUE;
}
/*---------------------------------------------------------------------
This function initializes the data structures, and calls
Triangulate2 to clip off the ears one by one.
---------------------------------------------------------------------*/
void EarInit( void )
{
tVertex v0, v1, v2; /* three consecutive vertices */
/* Initialize v1->ear for all vertices. */
v1 = vertices;
printf("newpath\n");
do {
v2 = v1->next;
v0 = v1->prev;
v1->ear = Diagonal( v0, v2 );
v1 = v1->next;
} while ( v1 != vertices );
printf("closepath stroke\n\n");
}
/*---------------------------------------------------------------------
Prints out n-3 diagonals (as pairs of integer indices)
which form a triangulation of P.
---------------------------------------------------------------------*/
void Triangulate( void )
{
tVertex v0, v1, v2, v3, v4; /* five consecutive vertices */
int n = nvertices; /* number of vertices; shrinks to 3. */
bool earfound; /* for debugging and error detection only. */
EarInit();
printf("\nnewpath\n");
/* Each step of outer loop removes one ear. */
while ( n > 3 ) {
/* Inner loop searches for an ear. */
v2 = vertices;
earfound = FALSE;
do {
if (v2->ear) {
earfound = TRUE;
/* Ear found. Fill variables. */
v3 = v2->next; v4 = v3->next;
v1 = v2->prev; v0 = v1->prev;
/* (v1,v3) is a diagonal */
PrintDiagonal( v1, v3 );
/* Update earity of diagonal endpoints */
v1->ear = Diagonal( v0, v3 );
v3->ear = Diagonal( v1, v4 );
/* Cut off the ear v2 */
v1->next = v3;
v3->prev = v1;
vertices = v3; /* In case the head was v2. */
n--;
break; /* out of inner loop; resume outer loop */
} /* end if ear found */
v2 = v2->next;
} while ( v2 != vertices );
if ( !earfound ) {
printf("%%Error in Triangulate: No ear found.\n");
PrintPoly();
printf("showpage\n%%%%EOF\n");
exit(EXIT_FAILURE);
}
} /* end outer while loop */
printf("closepath stroke\n\n");
}
/*---------------------------------------------------------------------
Returns TRUE iff the diagonal (a,b) is strictly internal to the
polygon in the neighborhood of the a endpoint.
---------------------------------------------------------------------*/
bool InCone( tVertex a, tVertex b )
{
tVertex a0,a1; /* a0,a,a1 are consecutive vertices. */
a1 = a->next;
a0 = a->prev;
/* If a is a convex vertex ... */
if( LeftOn( a->v, a1->v, a0->v ) )
return Left( a->v, b->v, a0->v )
&& Left( b->v, a->v, a1->v );
/* Else a is reflex: */
return !( LeftOn( a->v, b->v, a1->v )
&& LeftOn( b->v, a->v, a0->v ) );
}
/*---------------------------------------------------------------------
Returns TRUE iff (a,b) is a proper internal diagonal.
---------------------------------------------------------------------*/
bool Diagonal( tVertex a, tVertex b )
{
return InCone( a, b ) && InCone( b, a ) && Diagonalie( a, b );
}
/*---------------------------------------------------------------------
ReadVertices: Reads in the vertices, and links them into a circular
list with MakeNullVertex. There is no need for the # of vertices to be
the first line: the function looks for EOF instead.
---------------------------------------------------------------------*/
void ReadVertices( void )
{
tVertex v;
int x, y;
int vnum = 0;
while ( scanf ("%d %d", &x, &y ) != EOF ) {
v = MakeNullVertex();
v->v[X] = x;
v->v[Y] = y;
v->vnum = vnum++;
}
nvertices = vnum;
if (nvertices < 3)
printf("%%Error in ReadVertices: nvertices=%d<3\n", nvertices),
exit(EXIT_FAILURE);
}
/*---------------------------------------------------------------------
MakeNullVertex: Makes a vertex.
---------------------------------------------------------------------*/
tVertex MakeNullVertex( void )
{
tVertex v;
NEW( v, tsVertex );
ADD( vertices, v );
return v;
}
/*---------------------------------------------------------------------
For debugging; not currently invoked.
---------------------------------------------------------------------*/
void PrintPoly( void )
{
tVertex v;
printf("%%Polygon circular list:\n");
v = vertices;
do {
printf( "%% vnum=%5d:\tear=%d\n", v->vnum, v->ear );
v = v->next;
} while ( v != vertices );
}
/*---------------------------------------------------------------------
Print: Prints out the vertices. Uses the vnum indices
corresponding to the order in which the vertices were input.
Output is in PostScript format.
---------------------------------------------------------------------*/
void PrintVertices( void )
{
/* Pointers to vertices, edges, faces. */
tVertex v;
int xmin, ymin, xmax, ymax;
/* Compute bounding box for Encapsulated PostScript. */
v = vertices;
xmin = xmax = v->v[X];
ymin = ymax = v->v[Y];
do {
if ( v->v[X] > xmax ) xmax = v->v[X];
else if ( v->v[X] < xmin ) xmin = v->v[X];
if ( v->v[Y] > ymax ) ymax = v->v[Y];
else if ( v->v[Y] < ymin ) ymin = v->v[Y];
v = v->next;
} while ( v != vertices );
/* PostScript header */
printf("%%!PS\n");
printf("%%%%Creator: tri.c (Joseph O'Rourke)\n");
printf("%%%%BoundingBox: %d %d %d %d\n", xmin, ymin, xmax, ymax);
printf("%%%%EndComments\n");
printf(".00 .00 setlinewidth\n");
printf("%d %d translate\n", -xmin+72, -ymin+72 );
/* The +72 shifts the figure one inch from the lower left corner */
/* Output vertex info as a PostScript comment. */
printf("\n%% number of vertices = %d\n", nvertices);
v = vertices;
do {
printf( "%% vnum=%5d:\tx=%5d\ty=%5d\n", v->vnum, v->v[X], v->v[Y] );
v = v->next;
} while ( v != vertices );
/* Draw the polygon. */
printf("\n%%Polygon:\n");
printf("newpath\n");
v = vertices;
printf("%d\t%d\tmoveto\n", v->v[X], v->v[Y] );
v = v->next;
do {
printf("%d\t%d\tlineto\n", v->v[X], v->v[Y] );
v = v->next;
} while ( v != vertices );
printf("closepath stroke\n");
}
void PrintDiagonal( tVertex a, tVertex b )
{
printf("%%Diagonal: (%d,%d)\n", a->vnum, b->vnum );
printf("%d\t%d\tmoveto\n", a->v[X], a->v[Y] );
printf("%d\t%d\tlineto\n", b->v[X], b->v[Y] );
}
int AreaPoly2( void )
{
int sum = 0;
tVertex p, a;
p = vertices; /* Fixed. */
a = p->next; /* Moving. */
do {
sum += Area2( p->v, a->v, a->next->v );
a = a->next;
} while ( a->next != vertices );
return sum;
}
int AreaSign( tPointi a, tPointi b, tPointi c )
{
double area2;
area2 = ( b[0] - a[0] ) * (double)( c[1] - a[1] ) -
( c[0] - a[0] ) * (double)( b[1] - a[1] );
/* The area should be an integer. */
if ( area2 > 0.5 ) return 1;
else if ( area2 < -0.5 ) return -1;
else return 0;
}