【算法】求两个凸多边形的交集的面积

admin1

解法分析：
     显然凸多边形的交集仍然是凸多边形，本解法的关键是首先求出交集凸多边
的全部顶点，然后利用凸多边的面积算法求解。
     首先明确交集多边形的顶点组成。在本问题中，容易证明交集的顶点应该出自
下面的两类点 ：
    〔一〕已知的两个多边形 的顶点
    〔二〕两个多边形的边的交点
     第一类点的求法：显然如果一个多边形的某个顶点在另一个多边形内〔包括在边上〕则
该顶点是交集的一个顶点，因此我们只需依次对两个多边形的顶点进行判断，检验其是否包含
在另一个多边形中，即可求出第一类点。本程序中的子函数 inarea( )利用待判断点与另一
个多边形的全部边按顺序组成的三角形的面积总和与此多边形的面积进行大小比较，来判断该
点的归属，若大则在凸多边形的外部，不属于第一类点；否则，是交集的顶点。
     第二类点的求法：两个多边形相交可能有两条边重合〔包括部分重合〕的情况，显然重
合的部分必是交集的一条边，这条边的顶点是已知两个多边形的顶点，即应属于第一类点，在
第一类点的求法中显然已包括了这种顶点，因此我们在求两个多边形的边的交点时，
可以不计算两条边重合时的交点，而只计算两条边相交〔不平行〕时的交点。在本程序的算
法中为了求两条边的交点，我们采用线段的参数方程表示法，即
          ｘ＝ａ*ｔ＋ｂ
          ｙ＝ｃ*ｔ＋ｄ        其中0<=ｔ<=1 ；
设线段的两个端点坐标分别是〔ｘ0，ｙ0〕和〔ｘ1，ｙ1〕，则线段的参数方程可写成：   
ｘ＝〔ｘ1–ｘ0〕*ｔ＋ｘ0         
ｙ＝〔ｙ1–ｙ0〕*ｔ＋ｙ0   其中 0<=ｔ<=1；
据此可以求两条边的交点，详细的计算公式请见后面的源程序。
     如果某个多边形的顶点在另一个多边形的边上，由上面的算法可知它将被分别计入两类
点当中，因此我们最后求得的交集多边形的顶点可能有部分是重复的，但由多边形的面积算法
可知这不会影响面积的大小，因此在确定两类点时，不需要做精细的划分。
     在求三角形的面积时，用到了下面的公式：
                     ┃ 1  x0  y0  ┃     
         S3 = (1/2)* ┃ 1  x1  y1  ┃
                     ┃ 1  x2  y2  ┃
     其中〔x0,y0〕〔x1,y1〕〔x2,y2〕为三角形的三个顶点坐标；并且 S3为三角形的有
向面积，之所以用有向面积是因为在确定交集多边形顶点的顺序时，要利用三角形的有向面积
进行方向判断。
源程序：
//VC调试通过，