计算两凸多边形交集面积的计算机算法

吴新丽，蒋立恒，叶明全

（皖南医学院 医学信息学院，安徽 芜湖 241002）

两凸多边形交集面积可以理解为在一个给定的平面上有两个凸多边形，如果两个凸多边形之间存在交集，那么两个凸多边形的交集也必定是一个凸多边形.如果这两个凸多边形之间不存在交集，其含义是两个凸多边形之间相离或者说边界点与边之间相交，则相交面积为0当然本文对这种情况不做讨论.目前情况下主要分为两个方案对其进行计算和分析，首先流体力学方面在很多学术研讨以及技术类领域中都存在各种研究难点.尤其是针对如何对两个存在交集的多边形重叠部分，对其面积进行计算时遇到的问题更为严重.就目前的二维流体力学方面的lagrang网格的重分程序中计算方式中，不论是运用何种方式，在针对性解决该问题时，计算方面都需耗费较长时间，花费大量人力物力.就技术上而言实现此程序是非常复杂的,在运行时候会花费大量的时间.如果说是两个存在交集的多边形均是凸的,那么他的算法以及设计计算机的程序是相对而言简单的,本文将会说出一个新的程序算法关于计算两凸存在交集的多边形面积.这种算法思路相对简单,逻辑比较清晰,程序实现起来相对容易,有数学常识可知不论是哪一个类型的多边形在计算中可能都会出现有限凸多边形的集合或者合集内容，因此在计算方案的确定时，首先应该将非凸出的多边形进行处理或者计算，然后再使用固定计算方案对其进行分析和判定[1].

1 基本理论

关于面定义以及定理给出了些事实，是以理论分析算法以及对算法计算机进行实现的理论为基础

1.1 定义1

多边形一般是指由n个不同平面坐标的点p1p2交集pnpn+1首尾相连形成闭折线和所围的平面区域，记为G.设该闭折的线为多边形G的边界，记为Γ.称P(i=1,2,A,n)为多边形G的顶点;相邻的顶点连线PiPi+1.为多边形G的边;当多边形G的顶点按一定的序号沿边界Γ按一定顺序顺时针的方向排列时,称G是正向的，如果不是称为反向的.

1.2 定义1.1

如果多边形G是凸多边形，如果它全部顶点均位于它任意条边所在的直线的一侧.现两凸多边形G1和G2的并集的多边形定义为G1并G2;交集的多边形定义为G1交G2.

1.3 定理I

任意一个凸多边形G均可表示其所有的边所在的直线所划分的、并包含G的各个半平面的交集.

1.4 定理推论

如果平面上随机一点P在凸多边形G内，则当沿着G的边界行动时，P总在行动边的一侧;相反，若P在G外，则会沿着G的边界行动时，P有时于左侧，有时候在右侧.

1.5 定理1.1

若多边形G(其边界为I=P1P2^Pn)为凸多边形，则一点P在G内(包含边界上情况)的充要条件为:面积{PP2P2YPP2P3Y交集 YPPk-1PkYPPkP1}= 面积{G}，其中 PPi,Pi+1，(1≤i≤n,Pn+1=P1)为三角形.

1.6 定理1.1.1

如果两凸多边形G1和G3相交，则交集的多边形仍为凸多边形.

2 算法

在笛卡儿平面(x,y)设有两个凸多边形A，B.A=a1a2a3…ak,B=b1b2b3…bk其中ai=(xi,yi)(i=1,2,3,4,5……k),bj=(xj,yj)(i=1,2,……1)分别为A和B的顶点.本文的目的是计算两多边形相交部分的面积.

假定A和B此时均是凸多边形,计算方案依照如下步骤进行计算：

第一步计算过程中首先应该计算在B中A全部顶点,以及在B的边界上顶点,然后以集合G1,表示,G1={g1,g2,g3….gm1},m1＞=0.

然后计算在A中B的所有顶点,以及在B的边界上顶点,然后以集合 G1,表示,G2={g11,g22,g33….gm2},m2＞=0.

再然后计算A每条边和B的边界全部的交点,对于A所有边来说形成一个所有交点的集合G3

G3={g111,g223,g333….gm3},m3＞=0.

紧接着设G=G1并上G2并上G3，然后舍去具有相同坐标的点，容易得出G=G={g1,g2,g3….gm},m＜=m1+m2+m3

然后对g1,g2,g3….gm重新编序使G成为凸多边形.最后计算G的面积.

3 算法说明

列出算法1及程序设计实现，它们可以有助于我们的理解,容易把算法设计成为计算程序.

3.1 命题1

如果将A以及B作为两凸多边形,的两条边，那么G=A交B也是呈现凸出的,上述推理以及结论均是关于凸集的一个更广泛命题的推论,凸多边形位于其任意一条边及延长线的一侧.

3.2 命题1.1

若A=a1,a2...为凸多边形，一点P在A外的充要条件是:

面积 {pa1a2并pa2a3并…并pak-1Rk并paka1}＞面积{A},其中 paiai+1(ai+1≥a1,1≤i≤k)为三角形,此命题可用算法1中第一步和第二步程序设计.

3.3 命题1.1.1

直线px+qy+r=0把整平面划分为两个部分，得知点M和N在半平面内（同一个）的充要条件是f(M)与f(N)是同号,其中f(x,y)=px+qy+r,M=(x,y).算法的程序设计还需要如下两个计算公式.

3.4 计算两线段交点的公式

令A=(x1,y1),B=(x2,y2),C=(x3,y3),D=(x4,y4),利用参数a,β线段AB和CD可表示如下:AB={MM=A+a(B-A),0≤a≤1},CD=NN=C+B(D-C),0≤B≤1}.

求解关于未知数 a，B的方程组 x1+a(x2-x1)=x3+B(x4-x3)y1+a(y2-y1)=y3+B(y4-y3)

得a与b 值易知(1)若△=0，则AB∥CD，无交点；(2)当a＜0 或 a＞1 时无交点；(3)当 0≤a≤1 且 0≤B≤1 时，存在交点E.

E=(x1,+a(x2-x1;),y1+a(y2-y1)

(4)计算多边形面积的公式:

设M=M1 M2 … Mk为多边形,Mi=(x1,yi),i=1,2,3…k,设为 S

(5)其中S为多边形M的面积，用于算法的最后一步.

本文例举的上述算法中，主要的计算量在前几步.还有在算法l、2的程序设计中，首先解决判定点是不是在凸多边形内部的问题.均提出有效判定点集中点是不是在任意平面多边形G内部的算法，然而这些方法更多考虑的是一般的情况，在应用于是使问题复杂化[2]；则简单地利用定理1.1.1可作为判断一点是不是在凸多边形G内的依据:若G有N条边，那么做出一次的判断最少需要求n又l/n个三角形的面积[3].利用定义1.1和推论1可作为判别一点P是不是在凸多边形G内的依据:若P在凸多边形G内，则在沿着G的边行动时，P会总在行动者的一侧;若P在G外，则在沿着G的边行动时，P点会从行动者的一侧变到另一侧，在PP.上行动时，P点在行动的左侧;而当行动到PP上时，P点变到行动者的右侧，反之亦然.还需注意，沿多边形G行动时，无论G是正向的，还是反向，上述结论都成立.

4 具体算法

本文以C语言为例子具体算法实现

inline const int Get_Int(){int num=0,bj=1;char x=getchar();while(x＜'0'||x＞'9'){if(x=='-')bj=-1;x=getchar();}

while(x＞='0'&&x＜='9'){num=num*10+x-'0';x=getchar();}return num*bj}

const double eps=1e-10;

struct Point{double x,y;Point(double_x,double_y):x(_x),y(_y){}

Point(){}Point operator+(const Point&a)const{return Point(x+a.x,y+a.y);}

Point operator-(const Point&a)const{return Point(a.x-x,a.y-y);}

double Area(Point a,Point b,Point c){//三点的平行四边形有向面积Vector u=b-a;Vector v=c-a;return Cross(u,v);}

double Area(int n,Point*P){//计算多边形有向面积（剖分法）double ans=0;

for(int i=2;i＜n;i++)ans+=Area(P[1],P[i],P[i+1]);return ans/2;}

本文给出求两凸多边形并集多边形及面积的算法还有实现方法.实现过程中，运用向量内积判断平面上点是不是在凸多边形内，用这种方法算法计算得到简化.本文还引入了通过区间分割求取两线段交点的方法，并且利用相交的测试和线段的端点和另一线段所在位置关系等使不必要的“参数法”计算得到消除.