c演算法幾何

① 計算幾何的全部演算法

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中求出的交點還要分別判斷是否屬於該線段的范圍內。

② 關於C語言演算法

從易到難有：
排序：例如冒泡、快排、分治等。http://ke..com/view/58783.htm
搜索：如深搜、廣搜等。http://ke..com/view/3688332.htm
動態規劃，
貪心，
組合數學：http://ke..com/view/44868.htm
二叉樹，
圖論，
數論，
計算幾何。
《演算法導論》博大精深，不適合初學者或者適合肯下苦功夫的初學者。

③ C語言算斜率小問題（純數學幾何運算問題）

其實這個很簡單的問題
斜率為小數的可能最大吧，呵呵
但是小數的存儲是有誤差的，所以比較起來是不準確的，這個能理解吧
還有一個問題就是分母可能為零，也就是豎線，那麼斜率就是無窮大了，這樣在計算上是一個分母為零的異常吧
所以不能用小數來表示斜率，並且判斷不能出現小數
所以就要同分，

你考慮的變號問題，同分時需要變號（如果是負數）在代數中是不存在的
這個你可以詢問一下老師或者同學，並查一下代數課本，初中的知識吧，呵呵

④ c語言演算法有哪些

這里整理c語言常用演算法，主要有：
交換演算法
查找最小值演算法
冒泡排序
選擇排序
插入排序
shell排序 (希爾排序)
歸並排序
快速排序
二分查找演算法
查找重復演算法

⑤ c語言演算法

離散數學離散數學作為計算機學科的基礎是競賽中涉及最多的數學分支，重中之重又在於圖論和組合數學，尤其是圖論。圖論之所以運用最多是因為它的變化最多，而且可以輕易地結合基本數據結構和許多演算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關節點和關鍵路徑、歐拉迴路、最小生成樹、最短路徑、二部圖匹配和網路流等等。雖然這部分的比重很大，但是往往也是競賽中的難題所在，如果有初學者對於這部分的某些具體內容暫時感到力不從心，也不必著急，可以慢慢積累。組合數學競賽中設計的組合計數問題大都需要用組合數學來解決，組合數學中的知識相比於圖論要簡單一些，很多知識對於小學上過奧校的同學來說已經十分熟悉，但是也有一些部分需要先對代數結構中的群論有初步了解才能進行學習。組合數學在競賽中很少以難題的形式出現，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。數論以素數判斷和同餘為模型構造出來的題目往往需要較多的數論知識來解決，這部分在競賽中的比重並不大，但只要來上一道，也足以使知識不足的人冥思苦想上一陣時間。素數判斷和同餘最常見的是在以密碼學為背景的題目中出現，在運用密碼學常識確定大概的過程之後，核心演算法往往要涉及數論的內容。計算幾何計算幾何相比於其它部分來說是比較獨立的，就是說它和其它的知識點很少有過多的結合，較常用到的部分包括—線段相交的判斷、多邊形面積的計算、內點外點的判斷、凸包等等。計算幾何的題目難度不會很大，但也永遠不會成為最弱的題。線性代數對線性代數的應用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以藉助於矩陣來找到更好的演算法。 ~

⑥ 設計計算幾何演算法的編程語言是什麼，也是c、c++之類嗎

你問的這個很片面啊，如果是C語言中的 sqrt()函數，就是開方，當然是用C語言編的，C++也有很多同樣的啊，像VB JAVA都有演算法啊，windows就是用多種語言實現不同的功能的。。每種語言都有他自己的演算法，也有自己的區別 ，就像C是面向過程，而C++是面向對象，C++有繼承和多態等性質什麼的，

⑦ C語言中 什麼是演算法 演算法的表示有哪幾種方式

演算法（Algorithm）是一系列解決問題的清晰指令。
演算法也可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列，並且這樣的步驟和序列可以解決一類問題。
一個演算法應該具有以下五個重要的特徵：
有窮性，確切性，輸入，輸出，可行性。
演算法可以使用自然語言、偽代碼、流程圖，或者程序語言（比如C，C++）等多種不同的方法來描述。

⑧ C語言求圓周長和面積

一、數學公式：

圓周長=2*π*半徑

面積=π*半徑²

二、演算法分析：

周長和面積都依賴半徑，所以要先輸入半徑值，然後套用公式，計算周長和面積。 最終輸出結果即可。

三、參考代碼：

代碼如下

#include"stdio.h"

#definePi3.14

voidmain()

{

floatr,c,area;

printf("請輸入圓的半徑：");

scanf("%f",&r);

c=2*Pi*r;

area=Pi*r*r;

printf("該圓的周長是%.2f，面積是%.2f ",c,area);

}

⑨ 詳解C語言演算法

完整的程序如下：
typedef int status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 10
#include<stdarg.h>
#include<iostream.h>
#include<stdlib.h>
typedef int ElemType;
#define MAXDIM 8
typedef struct{
ElemType * base;
int dim;
int *bounds;
int *constants;
}Array;

status InitArray(Array &A,int dim,...)
{va_list ap;
if(dim<1||dim>MAXDIM) return ERROR;
A.dim=dim;
int i;
int total=1;
A.bounds=(int *)malloc(dim*sizeof(int));
if(!A.bounds) return ERROR;
va_start(ap,dim);
for(i=0;i<dim;i++)
{A.bounds[i]=va_arg(ap,int);
if(A.bounds[i]<0) return ERROR;
total*=A.bounds[i];
}
va_end(ap);
A.base=(ElemType*)malloc(total*sizeof(ElemType));
if(!A.base) return ERROR;
A.constants=(int *)malloc(dim*sizeof(int));
if(!A.constants) return ERROR;
A.constants[dim-1]=1;
for(i=dim-2;i>=0;i--)
A.constants[i]=A.constants[i+1]*A.bounds[i+1];
return OK;
}

status DestoryArray(Array &A)
{if(!A.base) return ERROR;
free(A.base);
if(!A.bounds) return ERROR;
free(A.bounds);
if(!A.constants) return ERROR;
free(A.constants);
A.dim=0;
return OK;
}

status Locate(Array A,int & off,...)
{va_list ap;
va_start(ap,off);
off=0;
int ind;
int i;
for(i=0;i<A.dim;i++)
{ind=va_arg(ap,int);
if(ind>A.bounds[i]||ind<0) return ERROR;
off+=ind*A.constants[i];
}
va_end(ap);
return OK;
}

status Value(Array A,ElemType & e,...)
{int off;
va_list ap;
va_start(ap,e);
Locate(A,off,ap);
e=A.base[off];
va_end(ap);
return OK;
}

status Assign(Array A,ElemType e,...)
{int off;
va_list ap;
va_start(ap,e);
Locate(A,off,ap);
A.base[off]=e;
va_end(ap);
return OK;
}
int main()
{Array A;
InitArray(A,2,2,5);
int i;
for(i=0;i<10;i++)
{ cout<<"請輸入數據"<<endl;
cin>>A.base[i];
}

ElemType e;
int off;
Locate(A,off,2,3);
cout<<"偏移是"<<off<<endl;
Value(A,e,2,4);
cout<<"第二行第四列是"<<e<<endl;
cin>>e;
Assign(A,e,2,2);
Value(A,e,2,2);
cout<<"第二行第二列是"<<e<<endl;
DestoryArray(A);
return 0;
}

執行InitArray(A,2,2,5)後
A.bounds[0]=2, A.bounds[1]=5
A.constants[1]=1, A.constants[0]=5
並且為A.base分配了10個ElemType型的元素空間

PS:關鍵是搞懂省略號參數列表的用法