計算兩凸多邊形交集面積的計算機算法

吳新麗，蔣立恒，葉明全

（皖南醫學院 醫學信息學院，安徽 蕪湖 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;}

本文給出求兩凸多邊形并集多邊形及面積的算法還有實現方法.實現過程中，運用向量內積判斷平面上點是不是在凸多邊形內，用這種方法算法計算得到簡化.本文還引入了通過區間分割求取兩線段交點的方法，并且利用相交的測試和線段的端點和另一線段所在位置關系等使不必要的“參數法”計算得到消除.