home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapter41 / l41-1.c next >
C/C++ Source or Header  |  1997-06-18  |  2KB  |  49 lines
  1. /* Returns 1 if polygon described by passed-in vertex list is monotone with
  2. respect to a vertical line, 0 otherwise. Doesn't matter if polygon is simple 
  3. (non-self-intersecting) or not.
  4.   Tested with Borland C++ 4.02 in small model by Jim Mischel 12/16/94.
  5.   Requires: L24-2.C L24-3.ASM L24-4.C L22-4.ASM L23-4.C L23-5.ASM
  6.   Compile command line:
  7.     bcc -ms l24-1.c l24-2.c l24-3.asm l24-4.c l22-4.asm l23-4.c l23-5.asm
  8. */
  9.  
  10. #include "polygon.h"
  11.  
  12. #define SIGNUM(a) ((a>0)?1:((a<0)?-1:0))
  13.  
  14. int PolygonIsMonotoneVertical(struct PointListHeader * VertexList)
  15. {
  16.    int i, Length, DeltaYSign, PreviousDeltaYSign;
  17.    int NumYReversals = 0;
  18.    struct Point *VertexPtr = VertexList->PointPtr;
  19.  
  20.    /* Three or fewer points can't make a non-vertical-monotone polygon */
  21.    if ((Length=VertexList->Length) < 4) return(1);
  22.  
  23.    /* Scan to the first non-horizontal edge */
  24.    PreviousDeltaYSign = SIGNUM(VertexPtr[Length-1].Y - VertexPtr[0].Y);
  25.    i = 0;
  26.    while ((PreviousDeltaYSign == 0) && (i < (Length-1))) {
  27.       PreviousDeltaYSign = SIGNUM(VertexPtr[i].Y - VertexPtr[i+1].Y);
  28.       i++;
  29.    }
  30.  
  31.    if (i == (Length-1)) return(1);  /* polygon is a flat line */
  32.  
  33.    /* Now count Y reversals. Might miss one reversal, at the last vertex, but 
  34.       because reversal counts must be even, being off by one isn't a problem */
  35.    do {
  36.       if ((DeltaYSign = SIGNUM(VertexPtr[i].Y - VertexPtr[i+1].Y))
  37.             != 0) {
  38.          if (DeltaYSign != PreviousDeltaYSign) {
  39.             /* Switched Y direction; not vertical-monotone if
  40.                reversed Y direction as many as three times */
  41.             if (++NumYReversals > 2) return(0);
  42.             PreviousDeltaYSign = DeltaYSign;
  43.          }
  44.       }
  45.    } while (i++ < (Length-1));
  46.    return(1);  /* it's a vertical-monotone polygon */
  47. }
  48.  
  49.