吳新麗，蔣立恒，葉明全

（皖南醫(yī)學(xué)院 醫(yī)學(xué)信息學(xué)院，安徽 蕪湖 241002）

兩凸多邊形交集面積可以理解為在一個給定的平面上有兩個凸多邊形，如果兩個凸多邊形之間存在交集，那么兩個凸多邊形的交集也必定是一個凸多邊形.如果這兩個凸多邊形之間不存在交集，其含義是兩個凸多邊形之間相離或者說邊界點(diǎn)與邊之間相交，則相交面積為0當(dāng)然本文對這種情況不做討論.目前情況下主要分為兩個方案對其進(jìn)行計算和分析，首先流體力學(xué)方面在很多學(xué)術(shù)研討以及技術(shù)類領(lǐng)域中都存在各種研究難點(diǎn).尤其是針對如何對兩個存在交集的多邊形重疊部分，對其面積進(jìn)行計算時遇到的問題更為嚴(yán)重.就目前的二維流體力學(xué)方面的lagrang網(wǎng)格的重分程序中計算方式中，不論是運(yùn)用何種方式，在針對性解決該問題時，計算方面都需耗費(fèi)較長時間，花費(fèi)大量人力物力.就技術(shù)上而言實(shí)現(xiàn)此程序是非常復(fù)雜的,在運(yùn)行時候會花費(fèi)大量的時間.如果說是兩個存在交集的多邊形均是凸的,那么他的算法以及設(shè)計計算機(jī)的程序是相對而言簡單的,本文將會說出一個新的程序算法關(guān)于計算兩凸存在交集的多邊形面積.這種算法思路相對簡單,邏輯比較清晰,程序?qū)崿F(xiàn)起來相對容易,有數(shù)學(xué)常識可知不論是哪一個類型的多邊形在計算中可能都會出現(xiàn)有限凸多邊形的集合或者合集內(nèi)容，因此在計算方案的確定時，首先應(yīng)該將非凸出的多邊形進(jìn)行處理或者計算，然后再使用固定計算方案對其進(jìn)行分析和判定[1].

1 基本理論

關(guān)于面定義以及定理給出了些事實(shí)，是以理論分析算法以及對算法計算機(jī)進(jìn)行實(shí)現(xiàn)的理論為基礎(chǔ)

1.1 定義1

多邊形一般是指由n個不同平面坐標(biāo)的點(diǎn)p1p2交集pnpn+1首尾相連形成閉折線和所圍的平面區(qū)域，記為G.設(shè)該閉折的線為多邊形G的邊界，記為Γ.稱P(i=1,2,A,n)為多邊形G的頂點(diǎn);相鄰的頂點(diǎn)連線PiPi+1.為多邊形G的邊;當(dāng)多邊形G的頂點(diǎn)按一定的序號沿邊界Γ按一定順序順時針的方向排列時,稱G是正向的，如果不是稱為反向的.

1.2 定義1.1

如果多邊形G是凸多邊形，如果它全部頂點(diǎn)均位于它任意條邊所在的直線的一側(cè).現(xiàn)兩凸多邊形G1和G2的并集的多邊形定義為G1并G2;交集的多邊形定義為G1交G2.

1.3 定理I

任意一個凸多邊形G均可表示其所有的邊所在的直線所劃分的、并包含G的各個半平面的交集.

1.4 定理推論

如果平面上隨機(jī)一點(diǎn)P在凸多邊形G內(nèi)，則當(dāng)沿著G的邊界行動時，P總在行動邊的一側(cè);相反，若P在G外，則會沿著G的邊界行動時，P有時于左側(cè)，有時候在右側(cè).

1.5 定理1.1

若多邊形G(其邊界為I=P1P2^Pn)為凸多邊形，則一點(diǎn)P在G內(nèi)(包含邊界上情況)的充要條件為:面積{PP2P2YPP2P3Y交集 YPPk-1PkYPPkP1}= 面積{G}，其中 PPi,Pi+1，(1≤i≤n,Pn+1=P1)為三角形.

1.6 定理1.1.1

如果兩凸多邊形G1和G3相交，則交集的多邊形仍為凸多邊形.

2 算法

在笛卡兒平面(x,y)設(shè)有兩個凸多邊形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的頂點(diǎn).本文的目的是計算兩多邊形相交部分的面積.

假定A和B此時均是凸多邊形,計算方案依照如下步驟進(jìn)行計算：

第一步計算過程中首先應(yīng)該計算在B中A全部頂點(diǎn),以及在B的邊界上頂點(diǎn),然后以集合G1,表示,G1={g1,g2,g3….gm1},m1＞=0.

然后計算在A中B的所有頂點(diǎn),以及在B的邊界上頂點(diǎn),然后以集合 G1,表示,G2={g11,g22,g33….gm2},m2＞=0.

再然后計算A每條邊和B的邊界全部的交點(diǎn),對于A所有邊來說形成一個所有交點(diǎn)的集合G3

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

緊接著設(shè)G=G1并上G2并上G3，然后舍去具有相同坐標(biāo)的點(diǎn)，容易得出G=G={g1,g2,g3….gm},m＜=m1+m2+m3

然后對g1,g2,g3….gm重新編序使G成為凸多邊形.最后計算G的面積.

3 算法說明

列出算法1及程序設(shè)計實(shí)現(xiàn)，它們可以有助于我們的理解,容易把算法設(shè)計成為計算程序.

3.1 命題1

如果將A以及B作為兩凸多邊形,的兩條邊，那么G=A交B也是呈現(xiàn)凸出的,上述推理以及結(jié)論均是關(guān)于凸集的一個更廣泛命題的推論,凸多邊形位于其任意一條邊及延長線的一側(cè).

3.2 命題1.1

若A=a1,a2...為凸多邊形，一點(diǎn)P在A外的充要條件是:

面積 {pa1a2并pa2a3并…并pak-1Rk并paka1}＞面積{A},其中 paiai+1(ai+1≥a1,1≤i≤k)為三角形,此命題可用算法1中第一步和第二步程序設(shè)計.

3.3 命題1.1.1

直線px+qy+r=0把整平面劃分為兩個部分，得知點(diǎn)M和N在半平面內(nèi)（同一個）的充要條件是f(M)與f(N)是同號,其中f(x,y)=px+qy+r,M=(x,y).算法的程序設(shè)計還需要如下兩個計算公式.

3.4 計算兩線段交點(diǎn)的公式

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

求解關(guān)于未知數(shù) a，B的方程組 x1+a(x2-x1)=x3+B(x4-x3)y1+a(y2-y1)=y3+B(y4-y3)

得a與b 值易知(1)若△=0，則AB∥CD，無交點(diǎn)；(2)當(dāng)a＜0 或 a＞1 時無交點(diǎn)；(3)當(dāng) 0≤a≤1 且 0≤B≤1 時，存在交點(diǎn)E.

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

(4)計算多邊形面積的公式:

設(shè)M=M1 M2 … Mk為多邊形,Mi=(x1,yi),i=1,2,3…k,設(shè)為 S

(5)其中S為多邊形M的面積，用于算法的最后一步.

本文例舉的上述算法中，主要的計算量在前幾步.還有在算法l、2的程序設(shè)計中，首先解決判定點(diǎn)是不是在凸多邊形內(nèi)部的問題.均提出有效判定點(diǎn)集中點(diǎn)是不是在任意平面多邊形G內(nèi)部的算法，然而這些方法更多考慮的是一般的情況，在應(yīng)用于是使問題復(fù)雜化[2]；則簡單地利用定理1.1.1可作為判斷一點(diǎn)是不是在凸多邊形G內(nèi)的依據(jù):若G有N條邊，那么做出一次的判斷最少需要求n又l/n個三角形的面積[3].利用定義1.1和推論1可作為判別一點(diǎn)P是不是在凸多邊形G內(nèi)的依據(jù):若P在凸多邊形G內(nèi)，則在沿著G的邊行動時，P會總在行動者的一側(cè);若P在G外，則在沿著G的邊行動時，P點(diǎn)會從行動者的一側(cè)變到另一側(cè)，在PP.上行動時，P點(diǎn)在行動的左側(cè);而當(dāng)行動到PP上時，P點(diǎn)變到行動者的右側(cè)，反之亦然.還需注意，沿多邊形G行動時，無論G是正向的，還是反向，上述結(jié)論都成立.

4 具體算法

本文以C語言為例子具體算法實(shí)現(xiàn)

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){//三點(diǎn)的平行四邊形有向面積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;}

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