計算幾何演算法分析與設計

③ 演算法設計與分析的介紹

《演算法設計與分析》是2009年國防工業出版社出版的圖書，作者是張德富。書主要取材於演算法設計與分析領域的經典內容，並介紹了演算法設計的發展趨勢。內容主要包括非常經典的演算法設計技術，例如遞歸與分治、動態規劃、貪心、回溯、分支限界、圖演算法，也包括了一些高級的演算法設計主題，例如網路流和匹配、啟發式搜索、線性規劃、數論以及計算幾何。在演算法分析方面，介紹了概率分析以及最新的分攤分析和實驗分析方法。在演算法的理論方面，介紹了問題的下界、演算法的正確性證明以及NP完全理論等方面的內容。

④ 什麼是計算幾何和代數幾何,微分幾何有什麼關系

1.計算幾何是計算機理論科學的一個重要分支.自20世紀70年代末從演算法設計與分析中獨立出來起，不到30年，該學科已經有了巨大的發展，不僅產生了一系列重要的理論成果，也在眾多實際領域中得到了廣泛的應用.
計算幾何基本概念和常用演算法包括如下內容：
矢量的概念
矢量加減法
矢量叉積
折線段的拐向判斷
判斷點是否在線段上
判斷兩線段是否相交
判斷線段和直線是否相交
判斷矩形是否包含點
判斷線段、折線、多邊形是否在矩形中
判斷矩形是否在矩形中
判斷圓是否在矩形中
判斷點是否在多邊形中
判斷線段是否在多邊形內
判斷折線是否在多邊形內
判斷多邊形是否在多邊形內
判斷矩形是否在多邊形內
判斷圓是否在多邊形內
判斷點是否在圓內
判斷線段、折線、矩形、多邊形是否在圓內
判斷圓是否在圓內
計算點到線段的最近點
計算點到折線、矩形、多邊形的最近點
計算點到圓的最近距離及交點坐標
計算兩條共線的線段的交點
計算線段或直線與線段的交點
求線段或直線與折線、矩形、多邊形的交點
求線段或直線與圓的交點
凸包的概念
凸包的求法
http://www.frontfree.net/view/article_748.html
2.微分幾何是以微積分作為工具研究曲線和曲面的性質及其推廣應用的幾何學。"微分幾何學"一詞是1894年由畢安基提出的。
http://lxy.zjfc.e.cn/sxsys/ReadNews.asp?NewsID=229&BigClassName=%CA%FD%D1%A7%CC%EC%B5%D8&SmallClassName=%D1%A7%BF%C6%B7%D6%D6%A7
3.代數幾何是現代數學的一個重要分支學科。它的基本研究對象是在任意維數的空間中，由若干個代數方程的公共零點所構成的集合的幾何特徵。這樣的幾何通常叫做代數簇，而這些方程叫做這個代數簇的定義方程組。代數簇的最簡單例子就是平面中的代數曲線。當前代數幾何研究的重點是正體問題，主要是代數簇的分類以及給定的代數簇中的子簇的性質。
代數幾何與數學的許多分支學科有著廣泛的聯系。代數幾何的發展和這些學科的發展起著相互促進的作用。同時作為一門理論學科，代數幾何的應用前景也開始受到人們的注意。近年來人們在現代物理的最新超弦理論中，已廣泛應用代數幾何。
http://www.ikepu.com/datebase/briefing/maths/algebraic_geometry.htm

⑤ 計算幾何的全部演算法

1. 矢量減法

設二維矢量 P = （x1,y1） ，Q = (x2,y2)
則矢量減法定義為： P - Q = ( x1 - x2 , y1 - y2 )
顯然有性質 P - Q = - ( Q - P )
如不加說明，下面所有的點都看作矢量，兩點的減法就是矢量相減；

2.矢量叉積

設矢量P = （x1,y1） ，Q = (x2,y2)
則矢量叉積定義為： P × Q = x1*y2 - x2*y1 得到的是一個標量
顯然有性質 P × Q = - ( Q × P ) P × ( - Q ) = - ( P × Q )
如不加說明，下面所有的點都看作矢量，點的乘法看作矢量叉積；

叉乘的重要性質：

> 若 P × Q > 0 , 則P 在Q的順時針方向
> 若 P × Q < 0 , 則P 在Q的逆時針方向
> 若 P × Q = 0 , 則P 與Q共線，但可能同向也可能反向

3.判斷點在線段上

設點為Q，線段為P1P2 ，判斷點Q在該線段上的依據是：

( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2為對角頂點的矩形內

4.判斷兩線段是否相交

我們分兩步確定兩條線段是否相交：

(1)． 快速排斥試驗

設以線段 P1P2 為對角線的矩形為R， 設以線段 Q1Q2 為對角線的矩形為T，如果
R和T不相交，顯然兩線段不會相交；

(2)． 跨立試驗

如果兩線段相交，則兩線段必然相互跨立對方，如圖1所示。在圖1中，P1P2跨立
Q1Q2 ，則矢量 ( P1 - Q1 ) 和( P2 - Q1 )位於矢量( Q2 - Q1 ) 的兩側，即
( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0
上式可改寫成
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
當( P1 - Q1 ) × ( Q2 - Q1 ) = 0 時，說明( P1 - Q1 ) 和 ( Q2 - Q1 )共線，
但是因為已經通過快速排斥試驗，所以 P1 一定在線段 Q1Q2上；同理，
( Q2 - Q1 ) ×( P2 - Q1 ) = 0 說明 P2 一定在線段 Q1Q2上。

所以判斷P1P2跨立Q1Q2的依據是：

( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0

同理判斷Q1Q2跨立P1P2的依據是：

( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) ≥ 0

至此已經完全解決判斷線段是否相交的問題。

5.判斷線段和直線是否相交

如果線段 P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：

( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0

6.判斷矩形是否包含點

只要判斷該點的橫坐標和縱坐標是否夾在矩形的左右邊和上下邊之間。

6.判斷線段、折線、多邊形是否在矩形中

因為矩形是個凸集，所以只要判斷所有端點是否都在矩形中就可以了。

7.判斷矩形是否在矩形中

只要比較左右邊界和上下邊界就可以了。

8.判斷圓是否在矩形中

圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小於等於圓心到矩形四邊的距
離的最小值。

9.判斷點是否在多邊形中

以點P為端點，向左方作射線L，由於多邊形是有界的，所以射線L的左端一定在多
邊形外，考慮沿著L從無窮遠處開始自左向右移動，遇到和多邊形的第一個交點的
時候，進入到了多邊形的內部，遇到第二個交點的時候，離開了多邊形，……所
以很容易看出當L和多邊形的交點數目C是奇數的時候，P在多邊形內，是偶數的話
P在多邊形外。

但是有些特殊情況要加以考慮。如果L和多邊形的頂點相交，有些情況下交點只能
計算一個，有些情況下交點不應被計算（自己畫個圖就明白了）；如果L和多邊形
的一條邊重合，這條邊應該被忽略不計。為了統一起見，我們在計算射線L和多邊
形的交點的時候，1。對於多邊形的水平邊不作考慮；2。對於多邊形的頂點和L相
交的情況，如果該頂點是其所屬的邊上縱坐標較大的頂點，則計數，否則忽略；
3。對於P在多邊形邊上的情形，直接可判斷P屬於多邊行。由此得出演算法的偽代碼
如下：

1. count ← 0;
2. 以P為端點，作從右向左的射線L;
3. for 多邊形的每條邊s
4. do if P在邊s上
5. then return true;
6. if s不是水平的
7. then if s的一個端點在L上且該端點是s兩端點中縱坐標較大的端點
9. then count ← count+1
10. else if s和L相交
11. then count ← count+1;
12. if count mod 2 = 1
13. then return true
14. else return false;

其中做射線L的方法是：設P'的縱坐標和P相同，橫坐標為正無窮大（很大的一個正
數），則P和P'就確定了射線L。這個演算法的復雜度為O(n)。

10.判斷線段是否在多邊形內

線段在多邊形內的一個必要條件是線段的兩個端點都在多邊形內；

如果線段和多邊形的某條邊內交（兩線段內交是指兩線段相交且交點不在兩線段的
端點），因為多邊形的邊的左右兩側分屬多邊形內外不同部分，所以線段一定會有
一部分在多邊形外。於是我們得到線段在多邊形內的第二個必要條件：線段和多邊
形的所有邊都不內交；

線段和多邊形交於線段的兩端點並不會影響線段是否在多邊形內；但是如果多邊形
的某個頂點和線段相交，還必須判斷兩相鄰交點之間的線段是否包含與多邊形內部。
因此我們可以先求出所有和線段相交的多邊形的頂點，然後按照X-Y坐標排序，這樣
相鄰的兩個點就是在線段上相鄰的兩交點，如果任意相鄰兩點的中點也在多邊形內，
則該線段一定在多邊形內。證明如下：

命題1：

如果線段和多邊形的兩相鄰交點P1 ，P2的中點P' 也在多邊形內，則P1, P2之間的
所有點都在多邊形內。

證明：

假設P1,P2之間含有不在多邊形內的點，不妨設該點為Q，在P1, P'之間，因為多邊
形是閉合曲線，所以其內外部之間有界，而P1屬於多邊行內部，Q屬於多邊性外部，
P'屬於多邊性內部，P1-Q-P'完全連續，所以P1Q和QP'一定跨越多邊形的邊界，因此
在P1,P'之間至少還有兩個該線段和多邊形的交點，這和P1P2是相鄰兩交點矛盾，故
命題成立。證畢

由命題1直接可得出推論：

推論2：

設多邊形和線段PQ的交點依次為P1,P2,……Pn，其中Pi和Pi+1是相鄰兩交點，線段
PQ在多邊形內的充要條件是：P，Q在多邊形內且對於i =1, 2,……, n-1，Pi ,Pi+1
的中點也在多邊形內。

在實際編程中，沒有必要計算所有的交點，首先應判斷線段和多邊形的邊是否內交
，倘若線段和多邊形的某條邊內交則線段一定在多邊形外；如果線段和多邊形的每
一條邊都不內交，則線段和多邊形的交點一定是線段的端點或者多邊形的頂點，只
要判斷點是否在線段上就可以了。

至此我們得出演算法如下：

1. if 線端PQ的端點不都在多邊形內
2. then return false;
3. 點集pointSet初始化為空;
4. for 多邊形的每條邊s
5. do if 線段的某個端點在s上
6. then 將該端點加入pointSet;
7. else if s的某個端點在線段PQ上
8. then 將該端點加入pointSet;
9. else if s和線段PQ相交 // 這時候可以肯定是內交
10. then return false;
11. 將pointSet中的點按照X-Y坐標排序，X坐標小的排在前面，
對於X坐標相同的點，Y坐標小的排在前面；
12. for pointSet中每兩個相鄰點 pointSet[i] , pointSet[ i+1]
13. do if pointSet[i] , pointSet[ i+1] 的中點不在多邊形中
14. then return false;
15. return true;

這個演算法的復雜度也是O(n)。其中的排序因為交點數目肯定遠小於多邊形的頂點數
目n，所以最多是常數級的復雜度，幾乎可以忽略不計。

11.判斷折線在多邊形內

只要判斷折線的每條線段是否都在多邊形內即可。設折線有m條線段，多邊形有n個
頂點，則復雜度為O(m*n)。

12.判斷多邊形是否在多邊形內

只要判斷多邊形的每條邊是否都在多邊形內即可。判斷一個有m個頂點的多邊形是
否在一個有n個頂點的多邊形內復雜度為O(m*n)。

13.判斷矩形是否在多邊形內

將矩形轉化為多邊形，然後再判斷是否在多邊形內。

14.判斷圓是否在多邊形內

只要計算圓心到多邊形的每條邊的最短距離，如果該距離大於等於圓半徑則該圓在
多邊形內。計算圓心到多邊形每條邊最短距離的演算法在後文闡述。

15.判斷點是否在圓內

計算圓心到該點的距離，如果小於等於半徑則該點在圓內。

16.判斷線段、折線、矩形、多邊形是否在圓內

因為圓是凸集，所以只要判斷是否每個頂點都在圓內即可。

17.判斷圓是否在圓內

設兩圓為O1,O2，半徑分別為r1, r2，要判斷O2是否在O1內。先比較r1，r2的大小
，如果r1<r2則O2不可能在O1內；否則如果兩圓心的距離大於r1 - r2 ，則O2不在
O1內；否則O2在O1內。

18.計算點到線段的最近點

如果該線段平行於X軸（Y軸），則過點point作該線段所在直線的垂線，垂足很容
易求得，然後計算出垂足，如果垂足在線段上則返回垂足，否則返回離垂足近的端
點；

如果該線段不平行於X軸也不平行於Y軸，則斜率存在且不為0。設線段的兩端點為
pt1和pt2，斜率為：
k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );
該直線方程為：
y = k* ( x - pt1.x) + pt1.y
其垂線的斜率為 - 1 / k，
垂線方程為：
y = (-1/k) * (x - point.x) + point.y
聯立兩直線方程解得：
x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x - pt1.x) + pt1.y;

然後再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計算兩端點
到垂足的距離，選擇距離垂足較近的端點返回。

19.計算點到折線、矩形、多邊形的最近點

只要分別計算點到每條線段的最近點，記錄最近距離，取其中最近距離最小的點即
可。

20.計算點到圓的最近距離

如果該點在圓心，則返回UNDEFINED
連接點P和圓心O，如果PO平行於X軸，則根據P在O的左邊還是右邊計算出最近點的
橫坐標為centerPoint.x - radius 或 centerPoint.x + radius， 如圖4 (a)所示；
如果PO平行於Y軸，則根據P在O的上邊還是下邊計算出最近點的縱坐標為
centerPoint.y + radius 或 centerPoint.y - radius， 如圖4 (b)所示。

如果PO不平行於X軸和Y軸，則PO的斜率存在且不為0，如圖4(c)所示。這時直線PO
斜率為
k = （ P.y - O.y ）/ ( P.x - O.x )
直線PO的方程為：
y = k * ( x - P.x) + P.y
設圓方程為:
(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，
聯立兩方程組可以解出直線PO和圓的交點，取其中離P點較近的交點即可。

21.計算兩條共線的線段的交點

對於兩條共線的線段，它們之間的位置關系有圖5所示的幾種情況。
圖5(a)中兩條線段沒有交點；圖5 (b) 和 (d) 中兩條線段有無窮焦點；圖5 (c)
中兩條線段有一個交點。設line1是兩條線段中較長的一條，line2是較短的一條，
如果line1包含了line2的兩個端點，則是圖5(d)的情況，兩線段有無窮交點；如
果line1隻包含line2的一個端點，那麼如果line1的某個端點等於被line1包含的
line2的那個端點，則是圖5(c)的情況，這時兩線段只有一個交點，否則就是
圖5(c)的情況，兩線段也是有無窮的交點；如果line1不包含line2的任何端點，
則是圖5(a)的情況，這時兩線段沒有交點。

22.計算線段或直線與線段的交點

設一條線段為L0 = P1P2，另一條線段或直線為L1 = Q1Q2 ，要計算的就是L0和L1
的交點。

1.首先判斷L0和L1是否相交（方法已在前文討論過），如果不相交則沒有交點，
否則說明L0和L1一定有交點，下面就將L0和L1都看作直線來考慮。

2.如果P1和P2橫坐標相同，即L0平行於Y軸
a)若L1也平行於Y軸，
i.若P1的縱坐標和Q1的縱坐標相同，說明L0和L1共線，假如L1是直線的話他們有
無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的演算法求他們
的交點（該方法在前文已討論過）；
ii.否則說明L0和L1平行，他們沒有交點；
b)若L1不平行於Y軸，則交點橫坐標為P1的橫坐標，代入到L1的直線方程中可以計
算出交點縱坐標；
3.如果P1和P2橫坐標不同，但是Q1和Q2橫坐標相同，即L1平行於Y軸，則交點橫
坐標為Q1的橫坐標，代入到L0的直線方程中可以計算出交點縱坐標；
4.如果P1和P2縱坐標相同，即L0平行於X軸
a)若L1也平行於X軸，
i.若P1的橫坐標和Q1的橫坐標相同，說明L0和L1共線，假如L1是直線的話他們
有無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的演算法求
他們的交點（該方法在前文已討論過）；
ii.否則說明L0和L1平行，他們沒有交點；

b)若L1不平行於X軸，則交點縱坐標為P1的縱坐標，代入到L1的直線方程中可以計
算出交點橫坐標；
5.如果P1和P2縱坐標不同，但是Q1和Q2縱坐標相同，即L1平行於X軸，則交點縱坐標
為Q1的縱坐標，代入到L0的直線方程中可以計算出交點橫坐標；
6.剩下的情況就是L1和L0的斜率均存在且不為0的情況
a)計算出L0的斜率K0，L1的斜率K1 ；
b)如果K1 = K2
i.如果Q1在L0上，則說明L0和L1共線，假如L1是直線的話有無窮交點，假如L1
是線段的話可用"計算兩條共線線段的交點"的演算法求他們的交點（該方法在
前文已討論過）；
ii.如果Q1不在L0上，則說明L0和L1平行，他們沒有交點。
c)聯立兩直線的方程組可以解出交點來

說明：這個演算法並不復雜，但是要分情況討論清楚，尤其是當兩條線段共線的情況
需要單獨考慮，所以在前文將求兩條共線線段的演算法單獨寫出來。另外，一開始就
先利用矢量叉乘判斷線段與線段（或直線）是否相交，如果結果是相交，那麼在後
面就可以將線段全部看作直線來考慮。

23.求線段或直線與折線、矩形、多邊形的交點

分別求與每條邊的交點即可。

24.求線段或直線與圓的交點

設圓心為O，圓半徑為r，直線（或線段）L上的兩點為P1,P2。
1.如果L是線段且P1，P2都包含在圓O內，則沒有交點；否則進行下一步
2.如果L平行於Y軸，
a)計算圓心到L的距離dis
b)如果dis > r 則L和圓沒有交點；
c)利用勾股定理，可以求出兩交點坐標，如圖6(a)所示；但要注意考慮L和圓的相
切情況
3.如果L平行於X軸，做法與L平行於Y軸的情況類似；
4.如果L既不平行X軸也不平行Y軸，可以求出L的斜率K，然後列出L的點斜式方程
，和圓方程聯立即可求解出L和圓的兩個交點；
5.如果L是線段，對於2，3，4中求出的交點還要分別判斷是否屬於該線段的范圍內。

⑥ 計算幾何 演算法設計與分析 怎麼樣

但是可以分類。以下是我查到的資料演算法可大致分為基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法。演算法可以宏泛的分為三類：有限的，確定

⑦ 《演算法設計技巧與分析》pdf下載在線閱讀，求百度網盤雲資源

《演算法設計技巧與分析》（[沙特]M. H. Alsuwaiyel）電子書網盤下載免費在線閱讀

資源鏈接：

鏈接：

書名：演算法設計技巧與分析

作者：[沙特]M. H. Alsuwaiyel

譯者：吳偉昶

豆瓣評分：7.5

出版社：電子工業出版社

出版年份：2004-8

頁數：318

內容簡介：

本書是國際著名演算法專家李德財教授主編的系列叢書「Lecture Notes Series on Computing」中的一本。本書涵蓋了絕大多數演算法設計中的一般技術，在表達每一種技術時，闡述它的應用背景，注意用與其他技術比較的方法說明它的特徵，並提供大量相應實際問題的例子。本書同時也強調了對每一種演算法的詳細的復雜性分析。全書分七部分19章，從演算法設計和演算法分析的基本概念和方法入手，先後介紹了遞歸技術、分治、動態規劃、貪心演算法、圖的遍歷等技術，對NP完全問題進行了基本但清楚的討論。對概率演算法、近似演算法和計算幾何這些近年來發展迅猛的領域也用一定的篇幅講述了基本內容。書中每章後都附有大量的練習題，有利於讀者對書中內容的理解和應用。

本書結構簡明，內容豐富，適合於作為計算機學科以及相關學科演算法課程的教材和參考書，尤其適宜於學過數據結構和離散數學課程之後的演算法課教材。同時也可作為從事演算法研究的一本好的入門書。

⑧ 求 計算幾何 演算法與應用 第三版（清華大學出版社） 的習題答案

你到網上搜《演算法設計與實驗題解》找個電子版下就行了。同一個作者所著，包含你要的主教材習題解答。

⑨ acm計算幾何演算法

計算幾何？這不是很多嘛。我這手裡還有一本黑的書，就是講計算幾何的，不過我現在專業問題不會再研究ACM了……另外網上也有很多東西的。實在不行你就弄本《計算機圖形學》，也有許多的問題啊。

⑩ 計算幾何中計算2個向量的交點坐標如何求的

不管是平面向量還是空間向量，都是自由向量；交點問題都不涉及的，沒有提交點，更不需要計算坐標。求交點坐標解方程法是正確的。即便沒有交點也可以用這種方法，只不過此時求出的方程無解而已。

向量P=A+tB=（1，2）+t（3，0）=（1+3t，2），

向量Q=C+sD=（1，-1）+s（3，2）=（1+3s，-1+2s）。

令1+3t=1+3s且2=-1+2s，解得s=t=3/2，代入得交點坐標：（11/2，2）。

解析：

由於零向量與任一向量都共線，所以A不正確；由於數學中研究的向量是自由向量，所以兩個相等的非零向量可以在同一直線上，而此時就構不成四邊形，根本不可能是一個平行四邊形的四個頂點，所以B不正確；向量的平行只要方向相同或相反即可，與起點是否相同無關，所以D不正確；對於C，其條件以否定形式給出，所以可從其逆否命題來入手考慮。