列举多边形的顶点的时候，规则是一定要按照反时针顺序依次列举，也就是说，如果一个人沿着多边形的边界前进，依次访问多边形的各个定点，多边形的“内部”始终是在这个人的左边。
----------------------------
如果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类型然后直接用^操作符，这个细节就不展示了，它和计算几何本身无关。