2007年9月18日 星期二

[轉貼]Autodesk的C++筆試題,看你能答出多少

[轉貼]Autodesk的C++筆試題,看你能答出多少
 
太多了,詳細請參考www.findgs.com
一、技術題
 
1. 在類的普通成員函數中調用虛函數,情況是怎麼樣的?(對像、引用、指針)
 
2. 關於成員變量初始化順序,幾個有依賴關係的成員變量要初始化,讓寫出構造函數。
 
3. 寫一個雙鏈表。
 
4. 寫個is-a和has-a。
 
5. struct vs. class.
 
6. 稱8個小球的問題
 
7. stl 裡面vector的實現(內部空間的申請與分配)
 
8. struct /class的區別
 
9. 為什麼要用struct //成員的默認屬性不同,用struct的話,主要是作為數據的集合。
 
10. 怎樣使一個class不能被實例化 //1,構造函數私有化,2,抽像類
 
11. 私有繼承和public繼承的區別。 //is-a has-a
 
12. void *p的問題 //不能++
 
13. 引用和指針的區別與聯繫。引用是否可以更改
 
14. windows編程基礎,線程與進程的區別
 
15. com+是否熟悉
 
16. 簡述一下hash算法
 
17. 一個32位的數據,怎樣找到最左邊的一個1?// n位的2進制數據怎樣找罪左邊的1,如果是在最左位,這個數是負數,否則的話,左移一位,看是否變成負數,這是O(n)的算法,O(n/2)的算法:二分方式查找
 
18. 一個4*4的格子,填入1~15 然後給個目標狀態,怎樣去搜索。
 
19. 給你100萬個數據,數據的值在0~65535之間 用最快的速度排序
 
20. 如果我們的一個軟件產品,用戶回復說:運行速度很慢,你怎麼處理?
 
21. 八皇后問題,詳述解法
 
22. kmp快速匹配算法 ---不算輕鬆的搞定
 
23. 無向圖中兩點間最短路問題 ---偉大的迪傑克斯拉算法
 
24. 空間中任意給兩個向量,求角平分線
 
25. 什麼是平衡樹
26. 哈夫曼編碼問題
 
27. 有向圖求環
 
28. .給n個點,求凸包問題
 
29. 四則運算(給一個前綴表達式,然後求解;給一個中綴表達式)
 
30. STL中container有哪些?
 
31. map中的數據存儲方式是什麼?
 
32. map和hashmap有什麼區別?
 
33. hashmap是標準庫中的嗎?
 
34. vector中的erase方法跟algorithm的remove有什麼區別?
 
35. object是什麼?
 
36. C++中如何阻止一個類被實例化?
 
37. 一般在什麼時候構造函數被聲明成private呢?//比如要阻止編譯器生成默認的copy constructor
 
38. 什麼時候編譯器會生成默認的copy constructor呢?
 
39. 如果你已經寫了一個構造函數,編譯器還會生成copy constructor嗎?
 
40. 為什麼說如果一個類作為基類,則它的析構函數要聲明成virtual的?
 
41. inline的函數和#define有什麼區別?什麼時候會真的被inline,什麼時候不會呢?
 
42. 如果把一個類的成員函數寫在類的聲明中是什麼意思?
 
43. public繼承和private繼承有什麼架構上的區別?//public是is-a的關係,private是has-a的關係
 
44. 在多繼承的時候,如果一個類繼承同時繼承自class A和class B,而class A和B中都有一個函數叫foo(),如何明確的在子類中指出override哪個父類的foo()?
 
45. 虛擬繼承的語法是什麼?
 
46. 部分模版特例化和全部模版特例化有什麼區別?
 
47. 編一個函數,使一個單項鏈表轉置。
 
48. 拆解一個整數,比如4,可以拆解成4=3+1;4=2+2;4=2+1+1;4=1+1+1+1
 
49. 不用庫函數,實現strcpy或者memcpy等函數
 
50. 內聯函數的作用和缺點
 
51. 指針和引用的區別
 
52. 友元的意義
 
53. 虛函數的意義
 
54. Overload, Overwrite, Override 各自的特點和意義
 
55. 頭文件中的ifndef/define/endif 幹什麼用?//防止該頭文件被重複引用。
 
56. 2#i nclude <filename.h> 和#i nclude 「filename.h」 有什麼區別?
 
57. 在C++ 程序中調用被C 編譯器編譯後的函數,為什麼要加extern 「C」?//C++語言支持函數重載,C 語言不支持函數重載。函數被C++編譯後在庫中的名字與C 語言的不同。C++提供了C 連接交換指定符號extern「C」來解決名字匹配問題
58. 一個類有基類、內部有一個其他類的成員對象,構造函數的執行順序是怎樣的?//先執行基類的(如果基類當中有虛基類,要先執行虛基類的,其他基類則按照聲明派生類時的順序依次執行),再執行成員對象的,最後執行自己的。
 
59. 請描述一個你熟悉的設計模式
 
60. 在UML 中,聚合(aggregation)和組合(composition)有什麼區別?
 
61. C#和C++除了語法上的差別以外,有什麼不同的地方?
 
(1) c#有垃圾自動回收機制,程序員不用擔心對象的回收。(2)c#嚴禁使用指針,只能處理對象。如果希望使用指針,則僅可在unsafe 程序塊中能使用指針。(3)c#只能單繼承。(4)必須通過類名訪問靜態成員。不能像C++中那樣,通過對像訪問靜態成員。(5)在子類中覆蓋父類的虛函數時必須用關鍵字override,覆蓋父類的方法要用關鍵字new
 
62. New delete與malloc free 的區別
 
63. #define DOUBLE(x) x+x,i = 5*DOUBLE(10);i是多少?正確的聲明是什麼?
 
64. 有哪幾種情況只能用intialization list 而不能用assignment?
 
當類中含有const、reference 成員變量;基類的構造函數都需要參數;類中含有其他類的成員對象,而該類的構造函數都需要參數。
 
65. C++是不是類型安全的?//不是。兩個不同類型的指針之間可以強制轉換。C#是類型安全的。
 
66. main 函數執行以前,還會執行什麼代碼?//全局對象的構造函數會在main 函數之前執行。
 
67. 描述內存分配方式以及它們的區別。//(1)從靜態存儲區域分配。內存在程序編譯的時候就已經分配好,這塊內存在程序的整個運行期間都存在。例如全局變量,static 變量。(2) 在棧上創建。在執行函數時,函數內局部變量的存儲單元都可以在棧上創建,函數執行結束時這些存儲單元自動被釋放。棧內存分配運算內置於處理器的指令集。(3) 從堆上分配,亦稱動態內存分配。程序在運行的時候用malloc 或new 申請任意多少的內存,程序員自己負責在何時用free 或delete 釋放內存。動態內存的生存期由我們決定,使用非常靈活,但問題也最多。
 
68. 比較一下C++中static_cast 和 dynamic_cast 的區別。
 
69. 當一個類A 中沒有生命任何成員變量與成員函數,這時sizeof(A)的值是多少,如果不是零,請解釋一下編譯器為什麼沒有讓它為零。
 
70. 已知兩個鏈表head1 和head2各自有序,請把它們合併成一個鏈表依然有序,要求用遞歸方法進行。
 
太多了,詳細請參考www.findgs.com

[轉貼]數學面積計算公式大全

[轉貼]數學面積計算公式大全
長方形=長*寬
平行四邊形=長*高
三角形=長*高/2
正方形=邊長*邊長
圓=圓周率*半徑的平方

這些是小學的,我已經挖空心思了,
我是六年級的

又找了一些:
我給的確實是初中的數學定理和公式大全,樓主看不懂問題不在這裡,建議樓主先從基礎知識抓起,光記公式而不理解是不行的,介紹
幾個初中生學習網站初中數學資源網
http://www.1230.org/
初中數學網
http://www.czsx.com.cn/
初中數學樂園
http://www.0618.org/
華師大初中數學網站
http://www.hsdczsx.com/Article_Index.asp
中學數學題庫
http://www.tiku.net/
這是初中的代數公式:
http://www.edu3g.com/math/expressions/czds/index1.html

初中數學常用公式:
http://edu.northeast.cn/system/2006/09/11/050545772.shtml

初中數學公式,這個需要下載:
http://www.hnmaths.com/Soft/czsx/200605/693.html

常用數學公式表:
http://www.wen8.net/html/307.htm

http://forum.heftyedu.com/viewthread.php?tid=740

另外關於學習方法的:(那個同學跟你的情況有點類似吧)
http://zhidao.baidu.com/question/18903134.html
希望對你有幫助,





1 過兩點有且只有一條直線
2 兩點之間線段最短
3 同角或等角的補角相等
4 同角或等角的余角相等
5 過一點有且只有一條直線和已知直線垂直
6 直線外一點與直線上各點連接的所有線段中,垂線段最短
7 平行公理 經過直線外一點,有且只有一條直線與這條直線平行
8 如果兩條直線都和第三條直線平行,這兩條直線也互相平行
9 同位角相等,兩直線平行
10 內錯角相等,兩直線平行
11 同旁內角互補,兩直線平行
12兩直線平行,同位角相等
13 兩直線平行,內錯角相等
14 兩直線平行,同旁內角互補
15 定理 三角形兩邊的和大於第三邊
16 推論 三角形兩邊的差小於第三邊
17 三角形內角和定理 三角形三個內角的和等於180°
18 推論1 直角三角形的兩個銳角互余
19 推論2 三角形的一個外角等於和它不相鄰的兩個內角的和
20 推論3 三角形的一個外角大於任何一個和它不相鄰的內角
21 全等三角形的對應邊、對應角相等
22邊角邊公理(SAS) 有兩邊和它們的夾角對應相等的兩個三角形全等
23 角邊角公理( ASA)有兩角和它們的夾邊對應相等的兩個三角形全等
24 推論(AAS) 有兩角和其中一角的對邊對應相等的兩個三角形全等
25 邊邊邊公理(SSS) 有三邊對應相等的兩個三角形全等
26 斜邊、直角邊公理(HL) 有斜邊和一條直角邊對應相等的兩個直角三角形全等
27 定理1 在角的平分線上的點到這個角的兩邊的距離相等
28 定理2 到一個角的兩邊的距離相同的點,在這個角的平分線上
29 角的平分線是到角的兩邊距離相等的所有點的集合
30 等腰三角形的性質定理 等腰三角形的兩個底角相等 (即等邊對等角)
31 推論1 等腰三角形頂角的平分線平分底邊並且垂直於底邊
32 等腰三角形的頂角平分線、底邊上的中線和底邊上的高互相重合
33 推論3 等邊三角形的各角都相等,並且每一個角都等於60°
34 等腰三角形的判定定理 如果一個三角形有兩個角相等,那麼這兩個角所對的邊也相等(等角對等邊)
35 推論1 三個角都相等的三角形是等邊三角形
36 推論 2 有一個角等於60°的等腰三角形是等邊三角形
37 在直角三角形中,如果一個銳角等於30°那麼它所對的直角邊等於斜邊的一半
38 直角三角形斜邊上的中線等於斜邊上的一半
39 定理 線段垂直平分線上的點和這條線段兩個端點的距離相等
40 逆定理 和一條線段兩個端點距離相等的點,在這條線段的垂直平分線上
41 線段的垂直平分線可看作和線段兩端點距離相等的所有點的集合
42 定理1 關於某條直線對稱的兩個圖形是全等形
43 定理 2 如果兩個圖形關於某直線對稱,那麼對稱軸是對應點連線的垂直平分線
44定理3 兩個圖形關於某直線對稱,如果它們的對應線段或延長線相交,那麼交點在對稱軸上
45逆定理 如果兩個圖形的對應點連線被同一條直線垂直平分,那麼這兩個圖形關於這條直線對稱
46勾股定理 直角三角形兩直角邊a、b的平方和、等於斜邊c的平方,即a^2+b^2=c^2
47勾股定理的逆定理 如果三角形的三邊長a、b、c有關係a^2+b^2=c^2 ,那麼這個三角形是直角三角形
48定理 四邊形的內角和等於360°
49四邊形的外角和等於360°
50多邊形內角和定理 n邊形的內角的和等於(n-2)×180°
51推論 任意多邊的外角和等於360°
52平行四邊形性質定理1 平行四邊形的對角相等
53平行四邊形性質定理2 平行四邊形的對邊相等
54推論 夾在兩條平行線間的平行線段相等
55平行四邊形性質定理3 平行四邊形的對角線互相平分
56平行四邊形判定定理1 兩組對角分別相等的四邊形是平行四邊形
57平行四邊形判定定理2 兩組對邊分別相等的四邊形是平行四邊形
58平行四邊形判定定理3 對角線互相平分的四邊形是平行四邊形
59平行四邊形判定定理4 一組對邊平行相等的四邊形是平行四邊形
60矩形性質定理1 矩形的四個角都是直角
61矩形性質定理2 矩形的對角線相等
62矩形判定定理1 有三個角是直角的四邊形是矩形
63矩形判定定理2 對角線相等的平行四邊形是矩形
64菱形性質定理1 菱形的四條邊都相等
65菱形性質定理2 菱形的對角線互相垂直,並且每一條對角線平分一組對角
66菱形面積=對角線乘積的一半,即S=(a×b)÷2
67菱形判定定理1 四邊都相等的四邊形是菱形
68菱形判定定理2 對角線互相垂直的平行四邊形是菱形
69正方形性質定理1 正方形的四個角都是直角,四條邊都相等
70正方形性質定理2正方形的兩條對角線相等,並且互相垂直平分,每條對角線平分一組對角
71定理1 關於中心對稱的兩個圖形是全等的
72定理2 關於中心對稱的兩個圖形,對稱點連線都經過對稱中心,並且被對稱中心平分
73逆定理 如果兩個圖形的對應點連線都經過某一點,並且被這一
點平分,那麼這兩個圖形關於這一點對稱
74等腰梯形性質定理 等腰梯形在同一底上的兩個角相等
75等腰梯形的兩條對角線相等
76等腰梯形判定定理 在同一底上的兩個角相等的梯形是等腰梯形
77對角線相等的梯形是等腰梯形
78平行線等分線段定理 如果一組平行線在一條直線上截得的線段
相等,那麼在其他直線上截得的線段也相等
79 推論1 經過梯形一腰的中點與底平行的直線,必平分另一腰
80 推論2 經過三角形一邊的中點與另一邊平行的直線,必平分第
三邊
81 三角形中位線定理 三角形的中位線平行於第三邊,並且等於它
的一半
82 梯形中位線定理 梯形的中位線平行於兩底,並且等於兩底和的
一半 L=(a+b)÷2 S=L×h
83 (1)比例的基本性質 如果a:b=c:d,那麼ad=bc
如果ad=bc,那麼a:b=c:d
84 (2)合比性質 如果a/b=c/d,那麼(a±b)/b=(c±d)/d
85 (3)等比性質 如果a/b=c/d=…=m/n(b+d+…+n≠0),那麼
(a+c+…+m)/(b+d+…+n)=a/b
86 平行線分線段成比例定理 三條平行線截兩條直線,所得的對應
線段成比例
87 推論 平行於三角形一邊的直線截其他兩邊(或兩邊的延長線),所得的對應線段成比例
88 定理 如果一條直線截三角形的兩邊(或兩邊的延長線)所得的對應線段成比例,那麼這條直線平行於三角形的第三邊
89 平行於三角形的一邊,並且和其他兩邊相交的直線,所截得的三角形的三邊與原三角形三邊對應成比例
90 定理 平行於三角形一邊的直線和其他兩邊(或兩邊的延長線)相交,所構成的三角形與原三角形相似
91 相似三角形判定定理1 兩角對應相等,兩三角形相似(ASA)
92 直角三角形被斜邊上的高分成的兩個直角三角形和原三角形相似
93 判定定理2 兩邊對應成比例且夾角相等,兩三角形相似(SAS)
94 判定定理3 三邊對應成比例,兩三角形相似(SSS)
95 定理 如果一個直角三角形的斜邊和一條直角邊與另一個直角三
角形的斜邊和一條直角邊對應成比例,那麼這兩個直角三角形相似
96 性質定理1 相似三角形對應高的比,對應中線的比與對應角平
分線的比都等於相似比
97 性質定理2 相似三角形周長的比等於相似比
98 性質定理3 相似三角形面積的比等於相似比的平方
99 任意銳角的正弦值等於它的余角的餘弦值,任意銳角的餘弦值等
於它的余角的正弦值
100任意銳角的正切值等於它的余角的余切值,任意銳角的余切值等
於它的余角的正切值
101圓是定點的距離等於定長的點的集合
102圓的內部可以看作是圓心的距離小於半徑的點的集合
103圓的外部可以看作是圓心的距離大於半徑的點的集合
104同圓或等圓的半徑相等
105到定點的距離等於定長的點的軌跡,是以定點為圓心,定長為半
徑的圓
106和已知線段兩個端點的距離相等的點的軌跡,是著條線段的垂直
平分線
107到已知角的兩邊距離相等的點的軌跡,是這個角的平分線
108到兩條平行線距離相等的點的軌跡,是和這兩條平行線平行且距
離相等的一條直線
109定理 不在同一直線上的三點確定一個圓。
110垂徑定理 垂直於弦的直徑平分這條弦並且平分弦所對的兩條弧
111推論1 ①平分弦(不是直徑)的直徑垂直於弦,並且平分弦所對的兩條弧
②弦的垂直平分線經過圓心,並且平分弦所對的兩條弧
③平分弦所對的一條弧的直徑,垂直平分弦,並且平分弦所對的另一條弧
112推論2 圓的兩條平行弦所夾的弧相等
113圓是以圓心為對稱中心的中心對稱圖形
114定理 在同圓或等圓中,相等的圓心角所對的弧相等,所對的弦
相等,所對的弦的弦心距相等
115推論 在同圓或等圓中,如果兩個圓心角、兩條弧、兩條弦或兩
弦的弦心距中有一組量相等那麼它們所對應的其餘各組量都相等
116定理 一條弧所對的圓周角等於它所對的圓心角的一半
117推論1 同弧或等弧所對的圓周角相等;同圓或等圓中,相等的圓周角所對的弧也相等
118推論2 半圓(或直徑)所對的圓周角是直角;90°的圓周角所
對的弦是直徑
119推論3 如果三角形一邊上的中線等於這邊的一半,那麼這個三角形是直角三角形
120定理 圓的內接四邊形的對角互補,並且任何一個外角都等於它
的內對角
121①直線L和⊙O相交 d<r
②直線L和⊙O相切 d=r
③直線L和⊙O相離 d>r
122切線的判定定理 經過半徑的外端並且垂直於這條半徑的直線是圓的切線
123切線的性質定理 圓的切線垂直於經過切點的半徑
124推論1 經過圓心且垂直於切線的直線必經過切點
125推論2 經過切點且垂直於切線的直線必經過圓心
126切線長定理 從圓外一點引圓的兩條切線,它們的切線長相等,
圓心和這一點的連線平分兩條切線的夾角
127圓的外切四邊形的兩組對邊的和相等
128弦切角定理 弦切角等於它所夾的弧對的圓周角
129推論 如果兩個弦切角所夾的弧相等,那麼這兩個弦切角也相等
130相交弦定理 圓內的兩條相交弦,被交點分成的兩條線段長的積
相等
131推論 如果弦與直徑垂直相交,那麼弦的一半是它分直徑所成的
兩條線段的比例中項
132切割線定理 從圓外一點引圓的切線和割線,切線長是這點到割
線與圓交點的兩條線段長的比例中項
133推論 從圓外一點引圓的兩條割線,這一點到每條割線與圓的交點的兩條線段長的積相等
134如果兩個圓相切,那麼切點一定在連心線上
135①兩圓外離 d>R+r ②兩圓外切 d=R+r
③兩圓相交 R-r<d<R+r(R>r)
④兩圓內切 d=R-r(R>r) ⑤兩圓內含d<R-r(R>r)
136定理 相交兩圓的連心線垂直平分兩圓的公共弦
137定理 把圓分成n(n3):
⑴依次連結各分點所得的多邊形是這個圓的內接正n邊形
⑵經過各分點作圓的切線,以相鄰切線的交點為頂點的多邊形是這個圓的外切正n邊形
138定理 任何正多邊形都有一個外接圓和一個內切圓,這兩個圓是同心圓
139正n邊形的每個內角都等於(n-2)×180°/n
140定理 正n邊形的半徑和邊心距把正n邊形分成2n個全等的直角三角形
141正n邊形的面積Sn=pnrn/2 p表示正n邊形的周長
142正三角形面積√3a/4 a表示邊長
143如果在一個頂點周圍有k個正n邊形的角,由於這些角的和應為
360°,因此k×(n-2)180°/n=360°化為(n-2)(k-2)=4
144弧長計算公式:L=n兀R/180
145扇形面積公式:S扇形=n兀R^2/360=LR/2
146內公切線長= d-(R-r) 外公切線長= d-(R+r)
(還有一些,大家幫補充吧)

實用工具:常用數學公式


公式分類 公式表達式

乘法與因式分 a2-b2=(a+b)(a-b) a3+b3=(a+b)(a2-ab+b2) a3-b3=(a-b(a2+ab+b2)

三角不等式 |a+b||a|+|b| |a-b||a|+|b| |a|b<=>-bab

|a-b||a|-|b| -|a|a|a|

一元二次方程的解 -b+√(b2-4ac)/2a -b-√(b2-4ac)/2a

根與係數的關係 X1+X2=-b/a X1*X2=c/a 註:韋達定理

判別式
b2-4ac=0 註:方程有兩個相等的實根
b2-4ac>0 註:方程有兩個不等的實根
b2-4ac<0 註:方程沒有實根,有共軛複數根

三角函數公式

兩角和公式
sin(A+B)=sinAcosB+cosAsinB sin(A-B)=sinAcosB-sinBcosA
cos(A+B)=cosAcosB-sinAsinB cos(A-B)=cosAcosB+sinAsinB
tan(A+B)=(tanA+tanB)/(1-tanAtanB) tan(A-B)=(tanA-tanB)/(1+tanAtanB)
ctg(A+B)=(ctgActgB-1)/(ctgB+ctgA) ctg(A-B)=(ctgActgB+1)/(ctgB-ctgA)

倍角公式
tan2A=2tanA/(1-tan2A) ctg2A=(ctg2A-1)/2ctga
cos2a=cos2a-sin2a=2cos2a-1=1-2sin2a

半角公式
sin(A/2)=√((1-cosA)/2) sin(A/2)=-√((1-cosA)/2)
cos(A/2)=√((1+cosA)/2) cos(A/2)=-√((1+cosA)/2)
tan(A/2)=√((1-cosA)/((1+cosA)) tan(A/2)=-√((1-cosA)/((1+cosA))
ctg(A/2)=√((1+cosA)/((1-cosA)) ctg(A/2)=-√((1+cosA)/((1-cosA))

和差化積
2sinAcosB=sin(A+B)+sin(A-B) 2cosAsinB=sin(A+B)-sin(A-B)
2cosAcosB=cos(A+B)-sin(A-B) -2sinAsinB=cos(A+B)-cos(A-B)
sinA+sinB=2sin((A+B)/2)cos((A-B)/2 cosA+cosB=2cos((A+B)/2)sin((A-B)/2)
tanA+tanB=sin(A+B)/cosAcosB tanA-tanB=sin(A-B)/cosAcosB
ctgA+ctgBsin(A+B)/sinAsinB -ctgA+ctgBsin(A+B)/sinAsinB

某些數列前n項和
1+2+3+4+5+6+7+8+9+…+n=n(n+1)/2 1+3+5+7+9+11+13+15+…+(2n-1)=n2
2+4+6+8+10+12+14+…+(2n)=n(n+1) 12+22+32+42+52+62+72+82+…+n2=n(n+1)(2n+1)/6
13+23+33+43+53+63+…n3=n2(n+1)2/4 1*2+2*3+3*4+4*5+5*6+6*7+…+n(n+1)=n(n+1)(n+2)/3

正弦定理 a/sinA=b/sinB=c/sinC=2R 註: 其中 R 表示三角形的外接圓半徑

餘弦定理 b2=a2+c2-2accosB 註:角B是邊a和邊c的夾角

圓的標準方程 (x-a)2+(y-b)2=r2 註:(a,b)是圓心坐標
圓的一般方程 x2+y2+Dx+Ey+F=0 註:D2+E2-4F>0
拋物線標準方程 y2=2px y2=-2px x2=2py x2=-2py

直稜柱側面積 S=c*h 斜稜柱側面積 S=c'*h
正稜錐側面積 S=1/2c*h' 正稜台側面積 S=1/2(c+c')h'
圓台側面積 S=1/2(c+c')l=pi(R+r)l 球的表面積 S=4pi*r2
圓柱側面積 S=c*h=2pi*h 圓錐側面積 S=1/2*c*l=pi*r*l

弧長公式 l=a*r a是圓心角的弧度數r >0 扇形面積公式 s=1/2*l*r

錐體體積公式 V=1/3*S*H 圓錐體體積公式 V=1/3*pi*r2h
斜稜柱體積 V=S'L 註:其中,S'是直截面面積, L是側稜長
柱體體積公式 V=s*h 圓柱體 V=pi*r2h

[轉貼]計算幾何常用算法介紹

[轉貼]計算幾何常用算法介紹
http://www.blogjava.net/sishuiweilan/archive/2007/09/07/143474.html

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