计算几何（二）

昨天最后说到的函数IntersectProp，并不包含线段ab的一个断点在线段cd上的情况。也就是说交点对两个线段来说都不是端点的情况。
判别这种情况，条件有两个：
1- ab的端点（以a为例）和cd共线；
2- a的横/纵坐标在c和d的横/纵坐标之间。
一般情况都判断横坐标，只在acd共线而且cd垂直于y轴（横坐标都是0）时，判断纵坐标。
代码
bool    Between( tPointi a, tPointi b, tPointi c ) {
   tPointi    ba, ca;

   if ( ! Collinear( a, b, c ) )
      return  FALSE;

   /* If ab not vertical, check betweenness on x; else on y. */
   if ( a[X] != b[X] )
      return ((a[X] <= c[X]) && (c[X] <= b[X])) ||
             ((a[X] >= c[X]) && (c[X] >= b[X]));
   else
      return ((a[Y] <= c[Y]) && (c[Y] <= b[Y])) ||
             ((a[Y] >= c[Y]) && (c[Y] >= b[Y]));
}

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

所以包括了所有情况的线段相交判断函数逻辑是满足下面两个条件之一：
1- 交点对两条线段来说都不是端点；或者
2- 交点是其中一条线段的端点之一。
代码：
bool    Intersect( tPointi a, tPointi b, tPointi c, tPointi d ) {
   if      ( IntersectProp( a, b, c, d ) )
      return  TRUE;
   else if (   Between( a, b, c )
            || Between( a, b, d )
            || Between( c, d, a )
            || Between( c, d, b )
           )
      return  TRUE;
   else    
      return  FALSE;
}

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

接下来的问题是判断线段ab是不是一个多边形的对角线。
对角线要满足以下条件：
1- 端点是多边形的顶点；
2- 除了端点之外，不与多边形的任何一条边有交集；
3- 在多边形内部。
第一步，先不考虑条件（3），条件1、2实现起来不难。
基本的思路就是针对给定的线段ab，遍历多边形的所有边：
如果边的顶点分别是c、d，且c、d和a、b都不重合，并且ab与cd相交，
那么按照定义ab就一定不是多边形的顶点。
bool   Diagonalie( tVertex a, tVertex b ) {
   tVertex c, c1;

   /* For each edge (c,c1) of P */
   c = vertices;
   do {
      c1 = c->next;
      /* Skip edges incident to a or b */
      if (    ( c != a ) && ( c1 != a )
           && ( c != b ) && ( c1 != b )
           && Intersect( a->v, b->v, c->v, c1->v )
         )
         return FALSE;
      c = c->next;
   } while ( c != vertices );
   return TRUE;
}

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

再看上面提到的条件（3），如何判断一个对角线ab是否在多边形内部？
假设要检查的对角线是线段ab，a是多边形的一个顶点。和a相邻的两个顶点是a0和a1。
按照反时针的顺序，三个顶点的次序是a0,a,a1。
分成两种情况讨论：
一，角a小于等于180度（这时候a称为一个“凸顶点”）
二，角a大于180度（这时候a称为一个“凹顶点”）
如果是凸顶点，ab在多边形内部可以等价为“a0在有向线段ab左边，a1在有向线段ba左边”。

如果是凹顶点，上面的判断条件就不对了，可能a0,a1在ab的同一侧而ab仍然在多边形内。
对凹顶点a，将多边形的“内部”和“外部”互换，a就成了一个凸顶点。
此时，“ab在多边形内”等价为“以下命题不成立：ab在新多边形内，或与角a的任何一边共线”。
即“以下命题不成立：a1在ab左侧或在ab上，且a0在ba左侧或在ba上”。
注意这里的条件都包含了“在直线上”的情形，因为按定义，
对角线和多边形边界的交集，只能是对角线的两个端点。

区分一个顶点a是凸顶点还是凹顶点，是通过判断a0,a,a1的关系。
a是凸顶点，当且仅当a0在aa1左边或在aa1上。注意如果a0,a,a1共线，a的内角是180度。
按定义这种情况a被当作一个凸顶点。

bool   InCone( tVertex a, tVertex b ) {
   tVertex a0,a1;    /* a0,a,a1 are consecutive vertices. */

   a1 = a->next;
   a0 = a->prev;

   /* If a is a convex vertex ... */
   if( LeftOn( a->v, a1->v, a0->v ) )
       return    Left( a->v, b->v, a0->v )
              && Left( b->v, a->v, a1->v );

   /* Else a is reflex: */
       return !(    LeftOn( a->v, b->v, a1->v )
                 && LeftOn( b->v, a->v, a0->v ) );
}

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

有了上面两段讨论的内容作为基础，判断真正的对角线就容易了。
bool    Diagonal( tVertex a, tVertex b ) {
   return InCone( a, b ) && InCone( b, a ) && Diagonalie( a, b );
}
注意InCone被调用了两次，原因不仅是要保证ab在多边形内。
Diagonalie跳过了所有端点包括a或b的边，InCone的两次调用还用来保证，
ab和多边形以a、b之一为顶点的所有边的交集，只有ab两点。