计算几何（一）

列举多边形的顶点的时候，规则是一定要按照反时针顺序依次列举，也就是说，如果一个人沿着多边形的边界前进，依次访问多边形的各个定点，多边形的“内部”始终是在这个人的左边。

----------------------------

如果abc（注意顺序）是一个三角形的三个顶点，令向量A=b-a，B=c-a，三角形的面积数值上是向量AB叉积的一半。即
2A(T) = (b0-a0)(c1-a1) - (c0-a0)(b1-a1)
定义
#define    X 0
#define    Y 1
#define    DIM 2               /* Dimension of points */
typedef    int tPointi[DIM];   /* Type integer point */
则计算三角形面积的代码可以写成
int     Area2( tPointi a, tPointi b, tPointi c ) {
   return (b[X] - a[X]) * (c[Y] - a[Y]) -
          (c[X] - a[X]) * (b[Y] - a[Y]);
}

----------------------------

平面上有任意简单多边形（不相邻的两个边没有交点），它的顶点是v0,v1,v2...vn。在平面上任取一点p，多边形的面积可以通过计算n个三角形的面积再求和得出：
A=A(p,v0,v1)+A(p,v1,v2)+A(p,v2,v3)+...+A(p,v[n-2],v[n-1])+A(p,v[n-1],v0)
定义
typedef    struct tVertexStructure tsVertex;    /* Used only in NEW(). */
typedef    tsVertex *tVertex;
struct    tVertexStructure {
   int        vnum;        /* Index */
   tPointi    v;        /* Coordinates */
   bool     ear;        /* TRUE iff an ear */
   tVertex     next,prev;
};
tVertex    vertices  = NULL;    /* "Head" of circular list. */
int    nvertices = 0;        /* Total number of polygon vertices. */
规定：存储一个多边形各顶点的数据结构是一个双向循环链表。
求多边形面积的的代码是：
int    AreaPoly2( void ) {
   int     sum = 0;
   tVertex p, a;

   p = vertices;   /* Fixed. */
   a = p->next;    /* Moving. */
   do {
      sum += Area2( p->v, a->v, a->next->v );
      a = a->next;
   } while ( a->next != vertices );
   return sum;
}

------------------------------

注意到有向线段ab可以确定一条直线，如果点c在直线ab左侧，那么三角形abc的面积就是正值（因为此时abc是按反时针顺序排列的），如果c在直线ab上，三角形abc的面积就是0，如果c在直线ab右边，三角形abc的面积就是负值（此时abc是按顺时针顺序出现的）。
定义
int     AreaSign( tPointi a, tPointi b, tPointi c )
{
    double area2;

    area2 = ( b[0] - a[0] ) * (double)( c[1] - a[1] ) -
            ( c[0] - a[0] ) * (double)( b[1] - a[1] );

    /* The area should be an integer. */
    if      ( area2 >  0.5 ) return  1;
    else if ( area2 < -0.5 ) return -1;
    else                     return  0;
}
（这个函数为什么这样定义，以后会说到。）
由此得到判断一个点c是否在一个直线ab左侧的方法：
bool    Left( tPointi a, tPointi b, tPointi c ) {
   return  AreaSign( a, b, c ) > 0;
}
判断一个点c是否在直线ab左侧或其上：
bool    LeftOn( tPointi a, tPointi b, tPointi c ) {
   return  AreaSign( a, b, c ) >= 0;
}
判断点abc是否共线：
bool    Collinear( tPointi a, tPointi b, tPointi c ) {
   return  AreaSign( a, b, c ) == 0;
}

------------------------------

判断线段相交时，如果用斜截式联立方程组求根的方式，一者斜截式有斜率90度、两直线平行等特殊情况；二者方程组的解很可能不是整数，出现浮点计算误差影响结果。因此换用别的方式。
如果两条线段ab和cd内相交，那么cd就被ab所确定的直线切割为两部分。所以对直线ab来说，点c和d一个在左，一个在右。类似地，对直线cd来说，点a和b也是一个在左，一个在右。如果这两个条件都满足，就可以判定两条线段相交。即：
bool    IntersectProp( tPointi a, tPointi b, tPointi c, tPointi d )
{
   if (Collinear(a,b,c) || Collinear(a,b,d) ||
       Collinear(c,d,a) || Collinear(c,d,b))
      return FALSE;

   return Xor( Left(a,b,c), Left(a,b,d) )
      && Xor( Left(c,d,a), Left(c,d,b) );
}
这里Xor要单独写成一个函数，是因为纯C不支持bool类型，C++完全可以定义成bool类型然后直接用^操作符，这个细节就不展示了，它和计算几何本身无关。