判断多边形点串存放序列

目标：给定一个任意点串序列的多边形（可能出现自相交的情况），判断其形点的存放序列方向。

注：输入的多边形点串的尾点与首点相同，即多存一个点，将首点存两遍。

算法思想：

（1）判断多边形形点个数，若少于4，则表明该点串无法构成多多边形。【return -2】

（2）计算多边形外包围盒的宽度和高度，若其中一个为0，则表明该多边形退化成了一条线或一个点。【return -1】

（3）计算多边形落在其外包围盒四条边上的顶点的索引号（left, bottom,right,up）

（4）比较得到索引号中最小的索引值：hit = min{left, bottom,right,up}

（5）判断从hit开始之后，（left, bottom,right,up）索引值的单调性情况

若：单调递增，则点串序列为逆时针。【return 1】

若：单调递减，则点串序列为顺时针。【return 2】

若：没有单调性，则点窜为自相交情况。【return 0】

多边形自相交

代码实现：

 1 int pts_sequence(const MxCutPolygon& cut_poly)
 2 {
 3     int pt_num = cut_poly.length();
 4     if (pt_num<4) return -2;
 5 
 6     int i;
 7     int lbrt[4]={0,0,0,0};
 8     MxVertex vmin = cut_poly[0];
 9     MxVertex vmax = cut_poly[0];
10     for (i=1; i<(pt_num-1); i++)
11     {
12         const MxVertex& v=cut_poly[i];
13 
14         if (v[0]<vmin[0]) {vmin[0]=v[0];lbrt[0]=i;}
15         if (v[0]>vmax[0]) {vmax[0]=v[0];lbrt[2]=i;}
16         if (v[1]<vmin[1]) {vmin[1]=v[1];lbrt[1]=i;}
17         if (v[1]>vmax[1]) {vmax[1]=v[1];lbrt[3]=i;}
18     }
19 
20     if (vmax[0]-vmin[0]<1e-6) return -1;
21     if (vmax[1]-vmin[1]<1e-6) return -1;
22 
23     int hit_idx;
24     int midx=pt_num;
25     for (i=0; i<4; i++)
26     {
27         if (midx>lbrt[i])
28         {
29             midx=lbrt[i];
30             hit_idx = i;
31         }
32     }
33 
34     int ccw_counter=0;
35     int cw_counter=0;
36     for (i=0; i<4; i++)
37     {
38         int curIdx=(hit_idx+i)%4;
39         int nextIdx=(hit_idx+i+1)%4;
40         if (lbrt[nextIdx]>=lbrt[curIdx])
41             ccw_counter++;
42         if (lbrt[nextIdx]<=lbrt[curIdx])
43             cw_counter++;
44     }
45 
46     if (ccw_counter==4) return 1;
47     if (cw_counter==4)  return 2;
48 
49     return 0;
50 }