計(jì)算幾何課件

5計(jì)算幾何

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

模式識(shí)別、計(jì)算機(jī)圖形學(xué)等中應(yīng)用甚廣。本章主要介紹幾個(gè)基本計(jì)算幾何問題的簡單并行算

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

1.1包含問題

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

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

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

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

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

除了頂點(diǎn)外，無兩邊相交。給定一個(gè)平面細(xì)圖和一個(gè)頂點(diǎn)p,確定哪個(gè)多邊形包含了p,此

即所謂的包含問題。最簡單的情況是判斷點(diǎn)p是否在一個(gè)多邊形。中。

1.1.1包含問題及其串行算法

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

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

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

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

至少需要。(")步。

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

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

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

算法17.1單處理機(jī)上包含問題算法

輸入：點(diǎn)P坐標(biāo)多邊形0的〃條邊E/.Ea,E”的兩個(gè)端點(diǎn)坐標(biāo)集合S

輸出：點(diǎn)和多邊形的關(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

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

1.1.2包含問題并行算法

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

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

中，每個(gè)處理器最多處理［%］條邊。具體的處理方法為過p點(diǎn)向x的負(fù)半軸方向做一條射

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

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

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

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

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

正整數(shù)。p個(gè)處理器的編號(hào)從根開始自上而下，自左而右逐級(jí)向下推進(jìn)。每個(gè)處理器存儲(chǔ)多

邊形。的一條邊，邊由其兩個(gè)端點(diǎn)的迪卡爾坐標(biāo)表示，點(diǎn)p的坐標(biāo)為開始時(shí)，根

讀進(jìn)(X,,,匕然后傳送給樹中的其余處理器。當(dāng)與接收到p的坐標(biāo)時(shí)，他就確定：穿過

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

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

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

算法17.2多處理機(jī)上包含問題算法

輸入：點(diǎn)p坐標(biāo)9,凸)；多邊形。的〃條邊邑,，…，&的兩個(gè)端點(diǎn)坐標(biāo)集合S

輸出：點(diǎn)和多邊形的位置關(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個(gè)處理器的情況下，上述算法的時(shí)間復(fù)雜度為。([%])。

MPI源程序請(qǐng)參見所附光盤。

1.2相交問題

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

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

的是要避免導(dǎo)線的交叉和元件的重疊；在計(jì)算機(jī)圖形學(xué)中，要求消去三維景象的二維表示中

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

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

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

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

二維問題上判斷邊的相交要麻煩，因?yàn)槿S空間上的點(diǎn)坐標(biāo)是與3個(gè)值有關(guān)的。

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

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

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

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

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

題。

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

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

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

輸入：多邊形R的N條邊即4，…,扁的兩個(gè)端點(diǎn)坐標(biāo)集合S,多邊形。的機(jī)條邊

FhF2?...,Fm的兩個(gè)端點(diǎn)坐標(biāo)集合S2

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

Begin

fori=ltondo

forj=ltomdo

if(EiintersectsF>)then

returntrue

endif

endfor

endfor

returnfalse

End

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

1.2.2相交問題的并行算法

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

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

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

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

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

輸入：多邊形尺的〃條邊?，邑,，.…扁的兩個(gè)端點(diǎn)坐標(biāo)集合S”多邊形。的機(jī)條邊

F,,F2“…,Fm的兩個(gè)端點(diǎn)坐標(biāo)集合S2

輸出：兩個(gè)多邊形是否相交：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)將各個(gè)處理器上resultk返回到主處理器，如果其中有一個(gè)為真，則兩多邊形相交，

否則兩多邊形不相交

End

MPI源程序請(qǐng)參見章末附錄。

1.3凸殼問題

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

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

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

在計(jì)算機(jī)圖形學(xué)中，使用一組點(diǎn)的凸殼可以顯示出點(diǎn)簇；在幾何問題中，集合S中最遠(yuǎn)兩

點(diǎn)就是凸殼的頂點(diǎn)，等等。

1.3.1凸殼問題及其串行算法

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

所有點(diǎn)的最小的凸多邊形。實(shí)際中，假定平面上的n個(gè)點(diǎn)，用n個(gè)釘在木板上的圖釘表示,

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

邊形。

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

參照?qǐng)D錯(cuò)誤！文檔中沒有指定樣式的文字。17.1,串行算法的基本思路如下：①識(shí)別

極點(diǎn)(ExtremePoint)：S中那些最大X坐標(biāo)(XMAX),最大Y坐標(biāo)(YMAX),最小X坐標(biāo)(XMIN),

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

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

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

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

成的正的或負(fù)的夾角是最小。這些點(diǎn)稱為凸點(diǎn)。

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

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

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

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

算法17.5單處理機(jī)上求凸殼的串行算法

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

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

Begin

(1)識(shí)別極點(diǎn)，它們都是的頂點(diǎn)

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

(3)計(jì)算頂點(diǎn)的極角，并排序：

(3.1)依次對(duì)屬于同一三角區(qū)域的點(diǎn)計(jì)算極角。然后將有最小極角點(diǎn)的序號(hào)作為自己

的Nextindex值

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

End

13.2凸殼問題并行算法

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

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

可以認(rèn)為其是直線拓?fù)浣Y(jié)構(gòu)?，F(xiàn)在將一維拓?fù)浣Y(jié)構(gòu)改變?yōu)?維的，則P(i,j)的i=l,2,3,4,而

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

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

算法17.6凸殼問題并行算法

輸入：n點(diǎn)集合S=p“}

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

Begin

(1)計(jì)算極點(diǎn)：

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

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

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

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

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

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

的點(diǎn)，存儲(chǔ)到行主處理器中本行要處理的頂點(diǎn)表列

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

(3)計(jì)算頂點(diǎn)的極角，并排序輸出：

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

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

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

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

上的點(diǎn)

End

MPI源程序請(qǐng)參見所附光盤。

1.4小結(jié)

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

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

參考文獻(xiàn)

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

[2].AkiSGParallelComputationalGeometry.Prentic-Hall,1992

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

ParallelandDistributedComputing,1986,3:492-507

[4].周培德著?計(jì)算幾何-算法設(shè)計(jì)與分析.清華大學(xué)出版社,廣西科學(xué)技術(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];/*點(diǎn)在豎直邊上，應(yīng)該對(duì)result賦個(gè)比

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

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

intgroup_size,my_rank;result=100;

}

/*判斷射線與線段是否有交點(diǎn)*/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);

/*交點(diǎn)剛好在邊上，且不為下頂

if(numbcr+i*group_size>=n)點(diǎ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];/*點(diǎn)在邊上，應(yīng)該對(duì)result賦一個(gè)

比較的大的值，這里是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;/*點(diǎn)在水平邊上，應(yīng)該對(duì)result賦

y2=temp;?個(gè)比較的大的值，這里是

)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);/*每一個(gè)處理器處理n/group_size條邊上的情

MPI_Comm_rank(MPI_COMM_WORLD,況并求和，對(duì)應(yīng)于算法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);

}

/*各處理器計(jì)數(shù)器初始化，對(duì)應(yīng)于

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

mys=O;

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

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

的坐標(biāo)*/MPI_Rcducc(&mys,&s,1,MPI_INT,MPI_SUM,

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

{

printfC請(qǐng)輸入點(diǎn)的個(gè)數(shù)/*根據(jù)s值確定輸出結(jié)果，對(duì)應(yīng)于

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

printff請(qǐng)輸入各點(diǎn)的坐標(biāo)\n")；if(my