計算幾何課件

5計算幾何

計算幾何是計算機科學中的一個分支，是專門研究有關(guān)幾何對象問題的。它在圖像分析、

模式識別、計算機圖形學等中應用甚廣。本章主要介紹幾個基本計算幾何問題的簡單并行算

法和它們的MPI編程實現(xiàn)，包括包含問題、相交問題和凸殼問題等。

1.1包含問題

包含問題(InclusionProblem)是計算幾何中最基本的問題之一。簡單的來說，包含問題就

是判斷點與多邊形的位置關(guān)系，即點在多邊形內(nèi)，點在多邊形外，和點在多邊形上。我們這

里討論的僅是點與任意多邊形之間的關(guān)系，不考慮與任意曲線封閉圖形之間的關(guān)系。

?個能夠畫在平面圖上而沒有任何相交邊的圖形稱為平面圖(PlanarGraph)。由一些相

鄰的多邊形(稱為單圖)所組成的圖形稱為平面細圖(PlanarSubvision),其中各多邊形中

除了頂點外，無兩邊相交。給定一個平面細圖和一個頂點p,確定哪個多邊形包含了p,此

即所謂的包含問題。最簡單的情況是判斷點p是否在一個多邊形。中。

1.1.1包含問題及其串行算法

判斷點在多邊形中的算法的基本思想是先求點和邊的交點個數(shù)，然后根據(jù)交點個數(shù)確定

點和邊的關(guān)系?；静襟E是：①過p點向x軸的負半軸方向做一條射線；②求此射線與多邊

型0諸邊的交點；③判斷：交點的個數(shù)若為奇數(shù)，則p位于。內(nèi)；否則p位于。外。這種

測試，對于“邊形可在。5)步內(nèi)完成。很清楚，這是最優(yōu)的串行算法，因為讀入n條邊也

至少需要。(")步。

但是需要注意幾種特殊的邊界情況：首先，過點p的射線與多邊形頂點相交，則交點只

計數(shù)一次；其次，若點p在多邊形邊上，則也認為點p在多邊形中；最后，如果射線與水平

邊重疊且點p不在該邊上，則交點不計數(shù)。

算法17.1單處理機上包含問題算法

輸入：點P坐標多邊形0的〃條邊E/.Ea,E”的兩個端點坐標集合S

輸出：點和多邊形的關(guān)系：true(p位于。內(nèi))；false(p位于。外)

Begin

(1)count=0

(2)whilei<ndo

ifpisonEjthen

returntrue

elseify=py(x〈px)intersectsEjleftqandqisnotE；low-endthen

count=count+1

endif

endif

endwhile

(3)if((countmod2)=1)then

returntrue

else

returnfalse

endif

End

算法的總運行時間為Z(n)=0(n)o

1.1.2包含問題并行算法

我們介紹兩種簡單方法來實現(xiàn)上面串行算法的并行化。一種方法是將串行算法中的步

驟2并行化。假設系統(tǒng)有p個處理器，多邊形有n條邊，將n條邊平均分配到這p個處理器

中，每個處理器最多處理［%］條邊。具體的處理方法為過p點向x的負半軸方向做一條射

線，判斷：如果點是在邊上則返回為8;線與邊無交點時返回0;如果有交點，那么就有2

種情況，如果交點是邊的下頂點，則返回為0,否則，即交點在邊上，則返回為1；把一個

處理器中的所有返回值加起來，然后將該值發(fā)送到主處理器(my_rank=0),最后主處理器根

據(jù)點的個數(shù)來判斷點與多邊形的關(guān)系。

另一種方法同樣也是將串行算法中的步驟2并行化。假設有p=2°-l個處理器，a為

正整數(shù)。p個處理器的編號從根開始自上而下，自左而右逐級向下推進。每個處理器存儲多

邊形。的一條邊，邊由其兩個端點的迪卡爾坐標表示，點p的坐標為開始時，根

讀進(X,,,匕然后傳送給樹中的其余處理器。當與接收到p的坐標時，他就確定：穿過

P的射線是否和。的邊町相交；對于特殊的情況需要利用圖形學的知識處理之。如果條件

滿足，則與產(chǎn)生“1”輸出；否則為“0”。將個處理器的輸出相加，若和為奇數(shù)，則p位于

Q內(nèi)；如果為偶數(shù)，則p位于Q外；如果和為oo,則輸出p在多邊形上。

算法17.2多處理機上包含問題算法

輸入：點p坐標9,凸)；多邊形。的〃條邊邑,，…，&的兩個端點坐標集合S

輸出：點和多邊形的位置關(guān)系：true。位于Q內(nèi))；false(/;位于Q外)

Begin

(1)count=0

(2)forallP-where1WjWppar-do

resultj=O

endfor

(3)forallP.where1Wj〈ppar-do

fori=ltodo

ifpisonEjxp+jthen

returnresultj=oo

else

ify=Py(xWpx)intersectsEjxp+jleftqandqisnotEjxp+jlow-endthen

resultj=resultj+1

endif

endif

endfor

endfor

(4)forj=ltoppar-doPi

sendsresult)toPo

endfor

(5)forj=ltopdo

count=count+result)

endfor

(6)if((countmod2)=1)or(count=oo)then

returntrue

elsereturnfalse

endif

End

在有p個處理器的情況下，上述算法的時間復雜度為。([%])。

MPI源程序請參見所附光盤。

1.2相交問題

在很多實際應用中，要求確定一組幾何物體(目標)是否相交。例如，在模式分類中，必

須確定代表不同類別的空間中的不同區(qū)域是否具有共同的子區(qū)域；在集成電路設計中，重要

的是要避免導線的交叉和元件的重疊；在計算機圖形學中，要求消去三維景象的二維表示中

的隱線和隱面等等。像如上的這些問題都可歸結(jié)為物體的相交問題(IntersectionProblem)o

設有平面上的兩個多邊形(允許有邊相交)及和。，如果多邊形R的一條邊和。的一條邊相

交，則稱7?和。是相交的。所以兩個多邊形的相交問題可以轉(zhuǎn)化為線段與多邊形的相交問題。

三維空間的相交問題與二維平面上的相交問題并沒有實質(zhì)的區(qū)別，只是在判斷邊的相交時比

二維問題上判斷邊的相交要麻煩，因為三維空間上的點坐標是與3個值有關(guān)的。

下面描述的算法都是針對二維平面上的多邊形相交而言的。

1.2.1兩多邊形相交問題及其串行算法

最基本的相交問題是判斷兩條線段是否相交。而邊與多邊形相交就是判斷一條邊和多條

邊中的某條邊是否相交的算法。要是一個多邊形的某條邊與另一個多邊形的一條邊相交，則

就稱兩個多邊形相交。這樣兩個多邊形相交的問題就轉(zhuǎn)化為多條邊與一個多邊形相交的問

題。

判斷線段是否相交的關(guān)鍵是求兩條直線的交點，即判斷此交點是否在線段上。這和包含

問題有些相似，需要判斷點與邊的關(guān)系。不同點是只須判斷點是否在邊上。

算法17.3單處理機上的兩多邊形相交問題算法

輸入：多邊形R的N條邊即4，…,扁的兩個端點坐標集合S,多邊形。的機條邊

FhF2?...,Fm的兩個端點坐標集合S2

輸出：兩個多邊形是否相交：true(兩多邊形相交)：false(兩多邊形不相交)

Begin

fori=ltondo

forj=ltomdo

if(EiintersectsF>)then

returntrue

endif

endfor

endfor

returnfalse

End

顯然上述算法所需時間為O(mn)。

1.2.2相交問題的并行算法

下面我們給出兩多邊形相交問題的樸素并行算法：對于多邊形R的每一條邊，要確定

其是否與多邊形。相交；如果夫的邊中有一條邊與。相交，那么就可以斷定多邊形R與。

是相交的。假設R有"條邊，。有w條邊，總共有p個處理器Pi,Pz,…,Pp。對于R中的每

條邊依次判斷是否與。相交。

算法17.4兩多邊形相交問題的并行算法

輸入：多邊形尺的〃條邊?，邑,，.…扁的兩個端點坐標集合S”多邊形。的機條邊

F,,F2“…,Fm的兩個端點坐標集合S2

輸出：兩個多邊形是否相交：true(兩多邊形相交)；false(兩多邊形不相交)

Begin

(1)fori=ltomdo

將E,廣播到所有處理器上

endfor

(2)forj=ltomdo

將可廣播到所有處理器上

endfor

(3)forallPkwhere1WkWppar-do

fori=ltodo

forj=ltomdo

if(Eixp^intersectsF>)then

resultk=true

endif

endfor

endfor

endfor

(4)將各個處理器上resultk返回到主處理器，如果其中有一個為真，則兩多邊形相交，

否則兩多邊形不相交

End

MPI源程序請參見章末附錄。

1.3凸殼問題

凸殼(ConvexHull)問題是計算幾何中一個重要問題，它的應用很廣泛。例如，在圖

象處理中可以通過構(gòu)造凸殼找到數(shù)字圖象中的凹面；在模式識別中，可視模式的凸殼能夠作

為描述模式外形的重要特征；在分類中，一組物體的凸殼就可勾畫出這些物體的所屬的類；

在計算機圖形學中，使用一組點的凸殼可以顯示出點簇；在幾何問題中，集合S中最遠兩

點就是凸殼的頂點，等等。

1.3.1凸殼問題及其串行算法

給定平面中的點的集合5={0”02，“”夕“}，所謂S之凸殼簡記為就是包含S

所有點的最小的凸多邊形。實際中，假定平面上的n個點，用n個釘在木板上的圖釘表示,

用一條橡皮帶纏繞著這些圖釘，然后放松橡皮帶，在撐緊橡皮帶所構(gòu)成的平面圖形就是凸多

邊形。

圖錯誤！文檔中沒有指定樣式的文字。17.1圖示求凸殼的方法

參照圖錯誤！文檔中沒有指定樣式的文字。17.1,串行算法的基本思路如下：①識別

極點(ExtremePoint)：S中那些最大X坐標(XMAX),最大Y坐標(YMAX),最小X坐標(XMIN),

最小Y坐標(YMIN)的那些頂點稱為極點；②識別凸邊(HullEdge)：線段(p,,pQ是CH(S)

的一條凸邊，當且僅當S的其余n-2個頂點均位于穿過Pj和的(無限長的)直線的同側(cè)。

由此定義可知,p,和p,一定是CH(S)的頂點;③識別凸點(HullPoint)：令p,和p,是CH(S)

上的兩連續(xù)頂點。假定取p,為坐標原點，那么在所有S中的點，Pj和p,相對于X軸所形

成的正的或負的夾角是最小。這些點稱為凸點。

很明顯，極點都是C7"型的頂點，任何位于由極點所圍成的多邊形內(nèi)的點都不是C"⑸

的頂點，那些在多邊形外的點可以歸入由XMAX、XMIN、YMAX、YMIN所圍成的四邊形

與由極點所圍成的多邊形所形成的四個三角區(qū)中。這樣問題就歸結(jié)成為求找這四個三角區(qū)中

頂點的凸邊，再把這些凸邊連接起來就可求得C”

算法17.5單處理機上求凸殼的串行算法

輸入：n點集合S={p”“,?”}

輸出：返回包含S的凸殼的頂點表列CH(S)

Begin

(1)識別極點，它們都是的頂點

(2)將頂點歸入有極點確定的四個三角區(qū)中，不在四個三角區(qū)中的頂點不需要處理

(3)計算頂點的極角，并排序：

(3.1)依次對屬于同一三角區(qū)域的點計算極角。然后將有最小極角點的序號作為自己

的Nextindex值

(3.2)然后處理器按照點的Nextindex索引輸出點

End

13.2凸殼問題并行算法

假定n個處理器排成網(wǎng)孔形狀，處于第i行和第/列的處理器用戶(力)表示。點i的坐標

用(巧，匕)表示。首先來介紹兩個基本概念和術(shù)語：①拓撲結(jié)構(gòu)的轉(zhuǎn)化：給定的n個處理器,

可以認為其是直線拓撲結(jié)構(gòu)。現(xiàn)在將一維拓撲結(jié)構(gòu)改變?yōu)?維的，則P(i,j)的i=l,2,3,4,而

j=l,2,-,n/4o②行主處理器：行主處理器是一個人為設定的處理器，純粹是為了處理上的方

便。在本算法中取p(i,l)為行主處理器。

算法17.6凸殼問題并行算法

輸入：n點集合S=p“}

輸出：返回凸殼頂點表列CH(S)

Begin

(1)計算極點：

(1.1)第1行的行主處理器向第2,3,4行的行主處理器發(fā)送頂點坐標

(1.2)第1、2、3、4行的行主處理器分別計算XMAX、YMIN、YMAX、XMIN；

并把它們的坐標分別存儲在4個行主處理器P(l,l)、P(2,l)、P(3,l)、P(4,l)中

(L3)確定極點后，將四條由極點組成的邊存儲到每一行的行主處理器上

(2)確定S中的頂點是否在四個三角區(qū)中：

(2.1)四個行主處理器同時判斷頂點是否處于自身所在的區(qū)域，其中屬于自己區(qū)域內(nèi)

的點，存儲到行主處理器中本行要處理的頂點表列

(2.2)將行主處理器上的表列傳遞到本行中其余的處理器上

(3)計算頂點的極角，并排序輸出：

(3.1)每一行上的第i個處理器計算表列中第j個點極角，其中j是mod行處理器數(shù)

等于i的數(shù)。然后將有最小極角點的序號作為自己的Nextindex值

(3.2)處理器將計算的Nextindex值傳遞到每行中的主處理器

(3.3)然后每個行主處理器按照從極點開始按Nextindex索引依次輸出所得到的極點

上的點

End

MPI源程序請參見所附光盤。

1.4小結(jié)

本章主要介紹了計算幾何中包含問題、相交問題和凸殼等三個基本問題的并行算法及其

MPI編程及其實現(xiàn)。這些算法可參見文獻川。讀者如欲進一步學習可參考文獻⑵、[3]和[4]。

參考文獻

[1].陳國良編著.并行算法的設計與分析(修訂版).高等教育出版社,2002.11

[2].AkiSGParallelComputationalGeometry.Prentic-Hall,1992

[3].Atal1ahMJ.GoodrichMT.EfficientParallelSolutionstoSomeGeometricProblems.J.of

ParallelandDistributedComputing,1986,3:492-507

[4].周培德著?計算幾何-算法設計與分析.清華大學出版社,廣西科學技術(shù)出版社,2000.5

附錄包含問題并行算法的MPI源程序

1.源程序including.c

#include<mpi.h>if((x>x1)&&(y<=y2)&&(y>y1))

#include<stdio.h>result=l;

else

intn;result=0;

doublextemp[20],ytemp[20];/*點在豎直邊上，應該對result賦個比

doublex,y;較的大的值，這里是100*/

ints,mys;if((x==xl)&&((y-yl)*(y2-y)>=0))

intgroup_size,my_rank;result=100;

}

/*判斷射線與線段是否有交點*/else

intcal_intcr(intnumber,inti,doublex,doubley){

(/*非豎直邊，非水平邊*/

doublexl,yl,x2,y2,temp;if(yi!=y2)

intresult;(

result=0;temp=x2+(y-y2)*(x2-xl)/(y2-y1);

/*交點剛好在邊上，且不為下頂

if(numbcr+i*group_size>=n)點*/

returnresult;if((tcmp<x)&&(y<=y2)&&(y>y1))

result=l;

xl=xtemp[number+i*group_size];else

y1=ytemp[number+i*group_size];result=0;

x2=xtemp[(number+l+i*group_size)%n];

y2=ytcmp[(numbcr+l+i*group_sizc)%n];/*點在邊上，應該對result賦一個

比較的大的值，這里是100*/

if(yi>y2)if((temp==x)&&((y-y2)*

{(yl-y)>=0))

temp=x1;result=100;

xl=x2;}

x2=temp;else

temp=yl;(

yl=y2;/*點在水平邊上，應該對result賦

y2=temp;?個比較的大的值，這里是

)100*/

if((y=y1)&&((Xl-x)*(x-x2)>=0))

/*判斷豎直邊的情況*/result=100;

if(xl==x2)}

returnresult;MPI_Bcast(xtcmp,n,MPI_DOUBLE,0,

)MPI_COMM_WORLD);

MPI_Bcast(ytcmp,n,MPI_DOUBLE,0,

main(intargc,char*argv[])MPI_COMM_WORLD);

(

inti;MPl_Barrier(MPl_COMM_WORLD);

MPI_Init(&argc,&argv);/*每一個處理器處理n/group_size條邊上的情

MPI_Comm_rank(MPI_COMM_WORLD,況并求和，對應于算法17.2步驟(3)*/

&my_rank);fbr(i=O;i<n/group_size+1;i-H-)

MPI_Comm_size(MPI_COMM_WORLD,{

&group_size);mys+=cal_inter(my_rank,i,x,y);

}

/*各處理器計數(shù)器初始化，對應于

算法17.2步驟(2)*/MPI_Barrier(MPI_COMM_WORLD);

mys=O;

/*把mys的值規(guī)約到s,對應于

/*主處理器讀入多邊形頂點和要判斷的點算法17.2步驟(4)和(5)*/

的坐標*/MPI_Rcducc(&mys,&s,1,MPI_INT,MPI_SUM,

if(my_rank==O)0,MPI_COMM_WORLD);

{

printfC請輸入點的個數(shù)/*根據(jù)s值確定輸出結(jié)果，對應于

scanff%d”,&n);算法17.2步驟(6)*/

printff請輸入各點的坐標\n")；if(my