計(jì)算兩凸多邊形交集面積的計(jì)算機(jī)算法

吳新麗，蔣立恒，葉明全

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

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

1 基本理論

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

1.1 定義1

多邊形一般是指由n個(gè)不同平面坐標(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)按一定的序號(hào)沿邊界Γ按一定順序順時(shí)針的方向排列時(shí),稱G是正向的，如果不是稱為反向的.

1.2 定義1.1

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

1.3 定理I

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

1.4 定理推論

如果平面上隨機(jī)一點(diǎn)P在凸多邊形G內(nèi)，則當(dāng)沿著G的邊界行動(dòng)時(shí)，P總在行動(dòng)邊的一側(cè);相反，若P在G外，則會(huì)沿著G的邊界行動(dòng)時(shí)，P有時(shí)于左側(cè)，有時(shí)候在右側(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è)有兩個(gè)凸多邊形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).本文的目的是計(jì)算兩多邊形相交部分的面積.

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

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

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

再然后計(jì)算A每條邊和B的邊界全部的交點(diǎn),對(duì)于A所有邊來(lái)說(shuō)形成一個(gè)所有交點(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

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

3 算法說(shuō)明

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

3.1 命題1

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

3.3 命題1.1.1

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

3.4 計(jì)算兩線段交點(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，無(wú)交點(diǎn)；(2)當(dāng)a＜0 或 a＞1 時(shí)無(wú)交點(diǎn)；(3)當(dāng) 0≤a≤1 且 0≤B≤1 時(shí)，存在交點(diǎn)E.

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

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

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

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

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

4 具體算法

本文以C語(yǔ)言為例子具體算法實(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){//計(jì)算多邊形有向面積（剖分法）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)過(guò)程中，運(yùn)用向量?jī)?nèi)積判斷平面上點(diǎn)是不是在凸多邊形內(nèi)，用這種方法算法計(jì)算得到簡(jiǎn)化.本文還引入了通過(guò)區(qū)間分割求取兩線段交點(diǎn)的方法，并且利用相交的測(cè)試和線段的端點(diǎn)和另一線段所在位置關(guān)系等使不必要的“參數(shù)法”計(jì)算得到消除.