Test for convex or concave polygon

helloktk의 블로그 | ㅇ
http://blog.naver.com/helloktk/80025637242 주어진 단순폴리곤이 convex인지 concave 인지는 이웃하는 변끼리의 cross 가 모두 같은 부호를 갖는지를 체크하면 된다.
중간에 부호가 바뀌면 해당 폴리곤의 concave이다.
이웃하는 세꼭지점이 일직선상에 놓인 경우는 제외해야 한다.
폴리곤이 simple인지 아닌지는 어떻게 판별할까?

/*주어진 심플한 다각형이 convex인지 concave인지를 판별한다. 점들이 일직선상에 놓인 상황에 있으면 0을 리턴한다. */
int is_convex_polygon(POINT p[], int N)
{
    int i;
    int flag = 0;    
    if (N < 3) return(0);

    for (i=0; i<N; i++) {
        int j = (i + 1) % N;
        int k = (i + 2) % N;
        double 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);
}