algorithm to detect the type of a polygon

[30baz]

i take points as input from a .txt file and i draw with these points a polygon then here comes the problem .. i need an algorithm to detect the type of the polygon .. concave or convex .. and here is my code ..
------------------------------------------------------------------
#include<stdafx.h>
#include <iostream>
#include <iomanip>
#include <fstream>
#include<conio.h>
#include<stdio.h>
#include<glut.h>
#include<gl.h>
using namespace std;

int counter=0;
int xsave[100];
int ysave[100];
int i=0;
int c=0;
int x1=0;
int y1=0;
int calc1=0;
int calc2=0;
void detect_polygon_type()
{


}

void draw_polygon(int x,int y)
{
c++;
glBegin(GL_POINTS);
glVertex2i(x,y);
glEnd();
if(c>1)
{
glBegin(GL_LINE_STRIP);
glVertex2i(x1,y1);
glVertex2i(x,y);
glEnd();
glFlush();
}
else
{
glFlush();
} }



int main1() {
glClear(GL_COLOR_BUFFER_BIT); // clear the screen

int x;
int y;
ifstream inFile;
inFile.open("test.txt");
if (!inFile) {
printf("file cannot be opened !!");
getch();
exit(1); // terminate with error
}

while(inFile >> x >> y )
{
counter++;
draw_polygon(x,y);
x1=x;
y1=y;

}
inFile.close();

}
void myInit(void)
{
glClearColor(1.0,1.0,1.0,0.0); // set white background color
glColor3f(0.0f, 0.0f, 0.0f); // set the drawing color
glPointSize(4.0); // a ‘dot’ is 4 by 4 pixels
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0, 640.0, 0.0, 480.0);
}
//<<<<<<<<<<<<<<<<<<<<<<<< myDisplay >>>>>>>>>>>>>>>>>
void myDisplay(void)
{
//glClear(GL_COLOR_BUFFER_BIT);
glBegin(GL_POINTS);
glEnd();
glFlush(); // send all output to display

}


//<<<<<<<<<<<<<<<<<<<<<<<< main >>>>>>>>>>>>>>>>>>>>>>
void main(int argc, char** argv)
{
glutInit(&argc, argv); // initialize the toolkit
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); // set display mode
glutInitWindowSize(640,480); // set window size
glutInitWindowPosition(100, 150); // set window position on
glutCreateWindow("Assignment 1 , Question # 2 "); // open the screen window
glutDisplayFunc(myDisplay); // register redraw function
myInit();
main1();
//detect_polygon_type();
glutMainLoop(); // go into a perpetual loop
getch();

}
--------------------------------------------------------------
thanks in advance

[trinitrotoluene]

To find if a set of points give a convex or a concave polygon you can calculate the convex hull of the points. If all the points are on the convex hull then it is obvious that the polygon is convex. If the number of points on the convex hull is smaller of the total numbers of points then the polygon is concave. To calculate the convex hull you can use the gift wrapping algorithm. This is the simplest convex hull algorithm to implements but it is not the most efficient.For your case (100 points max) this should be enough. In the algorithm, computing the real polar angles can be not easy. A clever way to compute it is to take the determinant of two points (a 2x2 matrix) and sort these values. I have implemented this algorithm and it work very well.

[trinitrotoluene]

Hah... another solution (much much simpler) is when you have a convex polygon you turn always in the same direction. When you have a concave polygon sometime you will turn left, sometime you will turn right. So the algorithm essentially is:

Take the determinant between the first point on the polygon with the next and save the result.For all points in the list.Take the next point as current point.Take the determinant between the current point and the next point and compare the sign of the result with the previous one (multiply both and if the result is negative the polygon is concave and you can terminate the loop now).If you pass through all the points then the polygon is convex.

Hope that help.

Edit: In fact you need to compute the determinant of the matrix between vectors not points. So v1 = current point - previous point , v2 = next point - current point and the matrix is:

 | v1.x v1.y |
 | v2.x v2.y |

You have all the base now to make your algorithm work.

[30baz]

thank u so much .. this really helped

[trinitrotoluene]

Here is the algorithm,very easy to implements:

 
#include <stdio.h>
#include <stdlib.h>
 
 
typedef struct 
{
  double x,y;
}Point;
 
double calc_determinant(Point p1,Point p2);
Point calc_vector(Point p0,Point p1);
 
// return a number : number < 0 concave,  number > 0 convex, number = 0 if num_vertices < 3 
int detect_polygon_type(const Point *p,const int num_vertices);
 
 
int main(int argc,char **argv)
{
  int val;
  Point poly1[4];//convex
  Point poly2[4];//concave
 
  poly1[0].x = -5.0; poly1[0].y = -5.0;
  poly1[1].x = 5.0; poly1[1].y = -5.0;
  poly1[2].x = 5.0; poly1[2].y = 5.0;
  poly1[3].x = -5.0; poly1[3].y = 5.0;
 
  poly2[0].x = -5.0; poly2[0].y = -5.0;
  poly2[1].x = 5.0; poly2[1].y = -5.0;
  poly2[2].x = 5.0; poly2[2].y = 5.0;
  poly2[3].x = 1.0; poly2[3].y = 0.0;
 
  val = detect_polygon_type(poly1,4);
  printf("%i\n",val);
 
  val = detect_polygon_type(poly2,4);
  printf("%i\n",val);
 
 return(EXIT_SUCCESS); 
}
 
int detect_polygon_type(const Point *p,const int num_vertices)
{
  Point v1,v2;
  double det_value;
  double cur_det_value;
  int i;
 
  if(num_vertices < 3)
  {
    return(0);
  }
 
 
  v1 = calc_vector(p[0],p[num_vertices-1]);
  v2 = calc_vector(p[1],p[0]);
  det_value = calc_determinant(v1,v2);
 
  for(i = 1 ; i < num_vertices-1 ; i++)
  {
    v1 = v2;
    v2 = calc_vector(p[i+1],p[i]);
    cur_det_value = calc_determinant(v1,v2);
 
    if( (cur_det_value * det_value) < 0.0 )
    {
      return(-1);
    }
 
  }
 
  v1 = v2;
  v2 = calc_vector(p[0],p[num_vertices-1]);
  cur_det_value = calc_determinant(v1,v2);
 
  if( (cur_det_value * det_value) < 0.0)
  {
    return(-1);
  }
  else
  {
    return(1);
  }
 
}
 
 
double calc_determinant(Point p1,Point p2)
{
  return (p1.x * p2.y - p1.y * p2.x);
}
 
 
Point calc_vector(Point p0,Point p1)
{
  Point p;
  p.x = p0.x - p1.x;
  p.y = p0.y - p1.y;
  return(p); 
}

[30baz]

First of all , thnks for ur support for the 2nd time but i think there would be a problem in that algorithm that entering the points of the polygon in different order will give different results since the determent is (a*d)-(b*c) so if u enter the points of a polygon in a specific order then calculate the determinant between each 2 points and then multiply all together u can get the wrong answer although there is an order at which u can get the correct answer .. do u get my point ??

thnks again for ur time ...
Best Regards,
30baz

[30baz]

First of all , thnks for ur support for the 2nd time but i think there would be a problem in that algorithm that entering the points of the polygon in different order will give different results since the determent is (a*d)-(b*c) so if u enter the points of a polygon in a specific order then calculate the determinant between each 2 points and then multiply all together u can get the wrong answer although there is an order at which u can get the correct answer .. do u get my point ??

thnks again for ur time ...
Best Regards,
30baz

[trinitrotoluene]

First of all , thnks for ur support for the 2nd time but i think there would be a problem in that algorithm that entering the points of the polygon in different order will give different results since the determent is (a*d)-(b*c) so if u enter the points of a polygon in a specific order then calculate the determinant between each 2 points and then multiply all together u can get the wrong answer although there is an order at which u can get the correct answer .. do u get my point ??

For sure, to be able to function properly, the algorithm need that the vertex in your file describe the contour in order (clockwise or counterclockwise) of your polygon. More specifically, if you take a vertex in your file, the previous vertex and the next vertex are neighbor on the contour of the polygon.
If the vertex in your file are in random order, then you will have no choice but to use an algorithm in the same "family" that I described in my first post.

Edit: After thinking about that, the vertex in your file cannot be in random order. If it is that, then for a concave polygon more than one contour can be described with your set of point(multiple solution). Can you post a sample file (one for convex, one for concave) so I be able to check my algorithm on a larger set of vertex.