Polygon Convex-Concave Test

/*

 * THIS IS A C PROGRAM THAT CHECKS WHETHER A GIVEN POLYGON IS CONVEX OR CONCAVE

 */

#include<stdio.h>

 #include<stdlib.h>

 #include<conio.h>

 #include<graphics.h>

 #include<dos.h>

 #include<math.h>

#define CONVEX 1

 #define CONCAVE -1

 int unitx = 20,unity = 20;

 /*Function to create a grid */

 void createGraph()    {

            int midx,midy,x,y;

            midx = getmaxx()/2;   /* the origin */

            midy = getmaxy()/2;

            setbkcolor(WHITE);

            setcolor(DARKGRAY);

            setlinestyle(SOLID_LINE,1,1);

            for(x=unitx;x<=getmaxx();x=x+unitx)

                        line(x,unity,x,getmaxy()-unity);

            for(y=unity;y<=getmaxy();y=y+unity)

                        line(unitx,y,getmaxx()-unitx,y);

            setcolor(DARKGRAY);

            setlinestyle(SOLID_LINE,1,2);

            /* draw the axes lines */

            line(midx,0,midx,getmaxy());

            line(0,midy,getmaxx(),midy);

   }

 typedef struct point{

  int x;

  int y;

  }point;

 int polyTest(point *,int);

 void main()    {

            int gdrive=DETECT,gmode,gerror;

            point vertex[50];          //polygon with maximum 50 vertices allowed

            int n,midx,midy,i;

            int startx,starty,endx,endy;

            char buffer[25];

            initgraph(&gdrive,&gmode,"C:\\TC\\BGI");

            printf("\nHow many vertices? ");

            scanf("%d",&n);

            for(i=0;i<n;i++){

                        printf("\nEnter \"x y\" values for vertex(%d) ",i+1);

                        scanf("%d%d",&vertex[i].x,&vertex[i].y);

            }

            midx = getmaxx()/2;

            midy = getmaxy()/2;

            cleardevice();

            createGraph();            /* render the grid on screen*/

            setlinestyle(SOLID_LINE,0,2);

            setcolor(DARKGRAY);

            for(i=0;i<n;i++)             {           /*draw the polygon on screen */

                        delay(500);

                        startx = vertex[i%n].x;

                        starty = vertex[i%n].y;

                        endx = vertex[(i+1)%n].x;

                        endy = vertex[(i+1)%n].y;

             line(midx+startx*unitx,midy-starty*unity,midx+endx*unitx,midy-endy*unity);

             sprintf(buffer,"(%d,%d)",startx,starty);

            outtextxy(midx+startx*unitx,midy-starty*unity,buffer);

             }

             delay(1000);

    switch(polyTest(vertex,n))    {               /* check the polygon & give result */

            case 0: sprintf(buffer,"Not a closed Polygon!!");

                        break;

            case 1: sprintf(buffer,"The Polygon is CONVEX");

                        break;

            case -1:sprintf(buffer,"The Polygon is CONCAVE");      

            }

    outtextxy(30,getmaxy()-50,buffer);

    getch();

 }

           

int polyTest(point *p,int n)       {

   int i,j,k;

   int flag = 0;

   double z;

   if (n < 3)        /*not a closed figure*/

      return(0);

   for (i=0;i<n;i++) {

      j = (i + 1) % n;

      k = (i + 2) % n;

      z  = (p[j].x - p[i].x) * (p[k].y - p[j].y);

      z -= (p[j].y - p[i].y) * (p[k].x - p[j].x);

      if (z < 0)

         flag |= 1;

      else if (z > 0)

         flag |= 2;

      if (flag == 3)

         return(CONCAVE);

   }

   if (flag != 0)

      return(CONVEX);

   else

      return(0);

}