计算机 2D 空间内的一些几何算法这里讨论计算机 2D 空间内的一些几何算法。讨论的主题包括：两条线段之间的方向、折线在某个顶点上的转向、 点是否在线段上的判定、 线段是否相交的判定、击包、给定点组成的多边形是否构成击多边形的判定、击多边形面积的计算以及判断点是否在一个多边形(包括凹击两种多边形 ) 当中的算法。在讨论这些主题之前， 首先确定点在计算机内的表示使用一个数对(整数或者浮点数，看具体需求 )来表示，而线段使用线段的两个端点来表示。在后面的所有主题讨论之中我们经常会用到一个几何术语：叉积，具体的几何意义表示由两个向量及其平移得到的向量围城的平行四边形的面积，而其算法是这样表示的：向量 a=(x1,y1)向量 b=(x2,y2)，叉积 a×b=x1*y2 + x2*y1；为了这些主题讨论的方便线段 l 我们有时也会表示成向量，表示的方法是：假设线段l 上的两个端点p1(x1,y1),p2(x2,y2)那么表示出来的向量p1p2=(x2-x1,y2-y1)。一、两条线段的方向这个主题要求的就是线段l2 在给定线段 l1 的顺时针或者逆时针方向上。 正如上面所说的， 我们把两条线段表示成向量的方式，这样转化而来的向量都以共同顶点原点为出发点。这样我们求得两个向量的叉积m，如果 m<0说明线段 l2 在线段 l1 的逆时针方向上； m>0说明在顺时针方向上； m==0 表示两条线段共线。二、折线在某个顶点上的转向假设折线上依次有点p1、p2、p3，求在顶点 p2上折线是向左转或者向右转。如图：显然如果我们要求在P2点上的折向我们只需要把P1、P2、P3表示成第二张图上红色部分表示的两个向量P1P2和 P1P3，如果向量 P1P3在向量 P1P2的顺时针方向那么在 P2点上就是向右转，否则就是左转，而判断两个向量（或者线段）方向的算法就是第一个主题当中提到的内容。三、点在线段上的判断点是否在线段上的判断有两种方式，第一种计算出线段的方程然后判断，但是这种方式当中由于存在大量除法运算，因此不但效率较差而且存在着精度的问题。而另一种判断方式则是，设线段l 上两个顶点 p1p2，要求判断的点为p3，我们前面讲到过如果两个向量的叉积为0 那么两个向量共线， 因此我们首先判断向量 p1p3和向量 p1p2是否共线，这样我们可以确定点p3 是否在线段 l 确定的直线上，接着我们判断点 p3 是否在点 p1p2确定的矩形当中 （判断方式很简单， 点 p3满足 x1<=x3<=x2 && y1<=y3<=y2，切记不可省略两个条件中的任意一个）。四、...
