📄 graham.c
字号:
<html>/*This code is described in "Computational Geometry in C" (Second Edition),Chapter 3. It is not written to be comprehensible without theexplanation in that book.Input: 2n integer coordinates of points in the plane. Output: the convex hull, cw, in PostScript; other output precedes the PS.NB: The original array storing the points is overwritten.Compile: gcc -o graham graham.c macros.hWritten by Joseph O'Rourke.Last modified: October 1997Questions to orourke@cs.smith.edu.--------------------------------------------------------------------This code is Copyright 1998 by Joseph O'Rourke. It may be freelyredistributed in its entirety provided that this copyright notice isnot removed.--------------------------------------------------------------------*/#include <stdio.h>#include <math.h>#include <stdlib.h>#include "macros.h"#define EXIT_FAILURE 1#define X 0#define Y 1typedef enum { FALSE, TRUE } bool;#define DIM 2 /* Dimension of points */typedef int tPointi[DIM]; /* Type integer point *//*----------Point(s) Structure-------------*/typedef struct tPointStructure tsPoint;typedef tsPoint *tPoint;struct tPointStructure { int vnum; tPointi v; bool delete;};/* Global variables */#define PMAX 1000 /* Max # of points */typedef tsPoint tPointArray[PMAX];static tPointArray P;int n = 0; /* Actual # of points */int ndelete = 0; /* Number deleted *//*----------Stack Structure-------------*/typedef struct tStackCell tsStack; /* Used on in NEW() */typedef tsStack *tStack;struct tStackCell { tPoint p; tStack next;};/*----------Function Prototypes-------------*/tStack Pop( tStack s );void PrintStack( tStack t );tStack Push( tPoint p, tStack top );tStack Graham( void );void Squash( void );void Copy( int i, int j );void PrintPostscript( tStack t );int Compare( const void *tp1, const void *tp2 );void FindLowest( void );void Swap( int i, int j );int AreaSign( tPointi a, tPointi b, tPointi c );bool Left( tPointi a, tPointi b, tPointi c );int ReadPoints( void );void PrintPoints( void );main(){ tStack top; n = ReadPoints(); FindLowest(); PrintPoints(); qsort( &P[1], /* pointer to 1st elem */ n-1, /* number of elems */ sizeof( tsPoint ), /* size of each elem */ Compare /* -1,0,+1 compare function */ ); printf("After sorting, ndelete = %d:\n", ndelete); PrintPoints(); if (ndelete > 0) { Squash(); printf("After squashing:\n"); } top = Graham(); printf("Hull:\n"); PrintStack( top ); PrintPostscript( top );}/*---------------------------------------------------------------------FindLowest finds the rightmost lowest point and swaps with 0-th.The lowest point has the min y-coord, and amongst those, themax x-coord: so it is rightmost among the lowest.---------------------------------------------------------------------*/void FindLowest( void ){ int i; int m = 0; /* Index of lowest so far. */ for ( i = 1; i < n; i++ ) if ( (P[i].v[Y] < P[m].v[Y]) || ((P[i].v[Y] == P[m].v[Y]) && (P[i].v[X] > P[m].v[X])) ) m = i; printf("Swapping %d with 0\n", m); Swap(0,m); /* Swap P[0] and P[m] */}void Swap( int i, int j ){ int temp; /* Uses swap macro. */ SWAP( temp, P[i].vnum, P[j].vnum ); SWAP( temp, P[i].v[X], P[j].v[X] ); SWAP( temp, P[i].v[Y], P[j].v[Y] ); SWAP( temp, P[i].delete, P[j].delete );}/*---------------------------------------------------------------------Compare: returns -1,0,+1 if p1 < p2, =, or > respectively;here "<" means smaller angle. Follows the conventions of qsort.---------------------------------------------------------------------*/int Compare( const void *tpi, const void *tpj ){ int a; /* area */ int x, y; /* projections of ri & rj in 1st quadrant */ tPoint pi, pj; pi = (tPoint)tpi; pj = (tPoint)tpj; a = AreaSign( P[0].v, pi->v, pj->v ); if (a > 0) return -1; else if (a < 0) return 1; else { /* Collinear with P[0] */ x = abs( pi->v[X] - P[0].v[X] ) - abs( pj->v[X] - P[0].v[X] ); y = abs( pi->v[Y] - P[0].v[Y] ) - abs( pj->v[Y] - P[0].v[Y] ); ndelete++; if ( (x < 0) || (y < 0) ) { pi->delete = TRUE; return -1; } else if ( (x > 0) || (y > 0) ) { pj->delete = TRUE; return 1; } else { /* points are coincident */ if (pi->vnum > pj->vnum) pj->delete = TRUE; else pi->delete = TRUE; return 0; } }}/*---------------------------------------------------------------------Pops off top elment of stack s, frees up the cell, and returns new top.---------------------------------------------------------------------*/tStack Pop( tStack s ){ tStack top; top = s->next; FREE( s ); return top;}/*---------------------------------------------------------------------Get a new cell, fill it with p, and push it onto the stack.Return pointer to new stack top.---------------------------------------------------------------------*/tStack Push( tPoint p, tStack top ){ tStack s; /* Get new cell and fill it with point. */ NEW( s, tsStack ); s->p = p; s->next = top; return s;}/*------------------------------------------------------------------------------------------------------------------------------------------*/void PrintStack( tStack t ){ if (!t) printf("Empty stack\n"); while (t) { printf("vnum=%d\tx=%d\ty=%d\n", t->p->vnum,t->p->v[X],t->p->v[Y]); t = t->next; }}/*---------------------------------------------------------------------Performs the Graham scan on an array of angularly sorted points P.---------------------------------------------------------------------*/tStack Graham(){ tStack top; int i; tPoint p1, p2; /* Top two points on stack. */ /* Initialize stack. */ top = NULL; top = Push ( &P[0], top ); top = Push ( &P[1], top ); /* Bottom two elements will never be removed. */ i = 2; while ( i < n ) { printf("Stack at top of while loop, i=%d, vnum=%d:\n", i, P[i].vnum); PrintStack( top ); if( !top->next) printf("Error\n"),exit(EXIT_FAILURE); p1 = top->next->p; p2 = top->p; if ( Left( p1->v , p2->v, P[i].v ) ) { top = Push ( &P[i], top ); i++; } else top = Pop( top ); printf("Stack at bot of while loop, i=%d, vnum=%d:\n", i, P[i].vnum); PrintStack( top ); putchar('\n'); } return top;}/*---------------------------------------------------------------------Squash removes all elements from P marked delete.---------------------------------------------------------------------*/void Squash( void ){ int i, j; i = 0; j = 0; /*printf("Squash: n=%d\n",n);*/ while ( i < n ) { /*printf("i=%d,j=%d\n",i,j);*/ if ( !P[i].delete ) { /* if not marked for deletion */ Copy( i, j ); /* Copy P[i] to P[j]. */ j++; } /* else do nothing: delete by skipping. */ i++; } n = j; printf("After Squash: n=%d\n",n); PrintPoints();}void Copy( int i, int j ){ P[j].v[X] = P[i].v[X]; P[j].v[Y] = P[i].v[Y]; P[j].vnum = P[i].vnum; P[j].delete = P[i].delete;}/*---------------------------------------------------------------------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]);}/*---------------------------------------------------------------------Returns true iff c is strictly to the left of the directedline through a to b.---------------------------------------------------------------------*/bool Left( tPointi a, tPointi b, tPointi c ){ return Area2( a, b, c ) > 0;}/*---------------------------------------------------------------------Reads in the coordinates of the points from stdin,puts them into P, and returns n, the number of vertices.Initializes other fields of point structure.---------------------------------------------------------------------*/int ReadPoints( void ){ int n = 0; while ( (n < PMAX) && (scanf("%d %d",&P[n].v[0],&P[n].v[1]) != EOF) ) { P[n].vnum = n; P[n].delete = FALSE; /*printf("vnum=%3d, x=%4d, y=%4d, delete=%d\n", P[n].vnum, P[n].v[X], P[n].v[Y], P[n].delete);*/ ++n; } if (n < PMAX) printf("n = %3d vertices read\n",n); else { printf("Error in ReadPoints: too many points; max is %d\n", PMAX); exit(EXIT_FAILURE); } return n;}void PrintPoints( void ){ int i; printf("Points:\n"); for( i = 0; i < n; i++ ) printf("vnum=%3d, x=%4d, y=%4d, delete=%d\n", P[i].vnum, P[i].v[X], P[i].v[Y], P[i].delete);}void PrintPostscript( tStack t){ int i; int xmin, ymin, xmax, ymax; xmin = xmax = P[0].v[X]; ymin = ymax = P[0].v[Y]; for (i = 1; i < n; i++) { if ( P[i].v[X] > xmax ) xmax = P[i].v[X]; else if ( P[i].v[X] < xmin ) xmin = P[i].v[X]; if ( P[i].v[Y] > ymax ) ymax = P[i].v[Y]; else if ( P[i].v[Y] < ymin ) ymin = P[i].v[Y]; } /* PostScript header */ printf("%%!PS\n"); printf("%%%%Creator: graham.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 */ /* Draw the points as little circles. */ printf("newpath\n"); printf("\n%%Points:\n"); for (i = 0; i < n; i++) printf("%d\t%d\t1 0 360\tarc\tstroke\n", P[i].v[X], P[i].v[Y]); printf("closepath\n"); /* Draw the polygon. */ printf("\n%%Hull:\n"); printf("newpath\n"); printf("%d\t%d\tmoveto\n", t->p->v[X], t->p->v[Y]); while (t) { printf("%d\t%d\tlineto\n", t->p->v[X], t->p->v[Y]); t = t->next; } printf("closepath stroke\n"); printf("showpage\n%%%%EOF\n");}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;}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -