計算幾何c語言描述

① 計算機圖形學復習

第一章
1. 計算機圖形：用數學方法描述，通過計算機生成、處理、存儲和顯示的對象。
2. 圖形和圖像的主要區別是表示方法不同：圖形是用矢量表示；圖像是用點陣表示的。圖形和圖像也可以通過光柵顯示器（或經過識別處理）可相互轉化。
3. 於計算機圖形學緊密相關的學科主要包括 圖像處理、計算幾何和計算機視覺模式識別。它們的共同點是 以圖形/圖像在計算機中的表示方法為基礎。
4. 互動式計算機圖形系統的發展可概括為以下4個階段：字元、矢量、二維光柵圖形、三維圖形。
5. 圖形學研究的主要內容有：①幾何造型技術 ②圖形生成技術 ③圖形處理技術 ④圖形信息的存儲、檢索與交換技術 ⑤人機交互技術 ⑥動畫技術 ⑦圖形輸入輸出技術 ⑧圖形標准與圖形軟體包的研發。
6. 計算機輔助設計和計算機輔助製造 是計算機圖形學最廣泛最活躍的應用領域。
7. 計算機圖形學的基本任務：一是如何利用計算機硬體來實現圖形處理功能；二是如何利用好的圖形軟體；三是如何利用數學方法及演算法解決實際應用中的圖行處理問題。
8. 計算機圖形系統是由硬體系統和軟體系統組成的。
9. 計算機圖形系統包括處理、存儲、交互、輸入和輸出五種基本功能。
10. 鍵盤和滑鼠是最常用的圖形輸入設備。滑鼠根據測量位移部件的不同，分為光電式、光機式和機械式3種。
11. 數字化儀分為電子式、超聲波式、磁伸縮式、電磁感應式等。小型的數字化儀也稱為圖形輸入板。
12. 觸摸屏是一種 定位設備，它是一種對於觸摸能產生反應的屏幕。
13. 掃描儀由3部分組成：掃描頭、控制電路和移動掃描機構。掃描頭由光源發射和光鮮接收組成。按移動機構的不同，掃描儀可分為平板式和滾筒式2種。
14. 顯示器是計算機的標准輸出設備。彩色CRT的顯示技術有2種：電子穿透法和蔭罩法。
15. 隨機掃描是指電子束的定位及偏轉具有隨意性，電子束根據需要可以在熒光屏任意方向上連續掃描，沒有固定掃描線和掃描順序限制。它具有局部修改性和動態性能。
16. 光柵掃描顯示器是畫點設備。
17. 點距是指相鄰像素點間的距離，與分辨指標相關。
18. 等離子顯示器一般有三層玻璃板組成，通常稱為等離子顯示器的三層結構。
19. 用以輸出圖形的計算機外部設備稱為硬拷貝設備。
20. 列印機是廉價的硬拷貝設備，從機械動作上常為撞擊式和非撞擊式2種。
21. 常用的噴墨頭有：壓電式、氣泡式、靜電式、固體式。
22. 繪圖儀分為靜電繪圖儀和筆式繪圖儀。
23. 圖形軟體的分層。由下到上分別是：①圖形設備指令、命令集、計算機操作系統 ②零級圖形軟體 ③一級圖形軟體 ④二級圖形軟體 ⑤三級圖形軟體。
24. 零級圖形軟體是面向系統的、最底層的軟體，主要解決圖形設備與主機的通信與介面問題，又稱設備驅動程序。
25. 一級圖形軟體即面向系統又面向用戶，又稱基本子系統。
26. 圖形應用軟體是系統的核心部分。
27. 從物理學角度，顏色以主波長、色純度和輝度來描述；從視覺角度來看，顏色以色彩、飽和度和亮度來描述。
28. 用適當比列的3種顏色混合，可以獲得白色，而且這3種顏色中的任意2種的組合都不能生成第三種顏色，稱為三原色理論。
29. RGB模型的匹配表達式是：c=rR+gG+bB。
30. 常用顏色模型
顏色模型名稱 使用范圍
RGB 圖形顯示設備（彩色CRT和光柵顯示器）
CMY 圖形列印、繪制設備
HSV 對應畫家本色原理、直觀的顏色描述
HSL 基於顏色參數的模型
用基色青、品紅、黃定義的CMY顏色模型用來描述硬拷貝設備的輸出顏色。它從白光中濾去某種顏色，故稱為減色性原色系統。

第二章
31. 直線生成的3個常用演算法：數值微分法（DDA）、中點劃線法和Bresenham演算法。
32. DDA演算法的C語言實現：
DDA演算法生成直線，起點（x0,y0）,終點（x1,y1）.
Void CMy View ::OnDdaline()
{
CDC *pDC=GetDC(); //獲得設備指針
int x0=100,y0=100,x1=300,y1=200,c=RGB(250,0,0);//定義直線兩端點和直線顏色
int x,y,i;
float dx,dy,k;
dx=(float)(x1-x0);
dy=(float)(y1-y0);
k=dy/dx;
x=x0;
y=y0;
if(abs(k)<1)
{ for(;x<=x1;x++)
{pDC—>SetPixel(x,int(y+0.5),c);
y=y+k;}
}
if(abs(k)>=1)
{ for(;y<=y1;y++)
{pDC—>SetPixel(int(x+0.5),y,c);
x=x+1/k;}
}
ReleaseDC(pDC); //釋放設備指針
}
33. 任何影響圖元顯示方法的參數稱為屬性參數。圖元的基本表現是線段，其基本屬性包括線型、線寬和色彩。
34. 最常見的線型包括實線、虛線、細線和點劃線等，通常默認的線型是實線。
35. 線寬控制的實線方法：垂直線刷子、水平線刷子、方形線刷子。生成具有寬度的線條還可以採用區域填充演算法。
36. 用離散量表示連續量時引起的失真現象稱為走樣。為了提高圖形顯示質量，減少或消除走樣現象的技術稱為反走樣。
37. 反走樣技術有：提高解析度（硬體方法和軟體方法）、簡單區域取樣、加權區域取樣。
38. 區域連通情況分為四連通區域和八連通區域。四連通區域是指從區域上某一點出發，可通過上下左右4個方向移動，在不越出區域的前提下到達區域內的任意像素；八連通區域是指從區域內某一像素出發，可通過上下左右、左上左下、右上右下8個方向的移動，在不越出區域的前提下到達區域內的任意像素。
39. 字元的圖形表示可以分為點陣式和矢量式兩種形式。
40. 在圖形軟體中，除了要求能生成直線、圓等基本圖形元素外，還要求能生成其他曲線圖元、多邊形及符號等多種圖元。
41. 在掃描線填充演算法中，對水平邊忽略而不予處理的原因是實際處理時不計其交點。
42. 關於直線生成演算法的敘述中，正確的是：Bresenham演算法是對中點畫線演算法的改進。
43. 在中點畫圓演算法中敘述錯誤的是：為了減輕畫圓的工作量，中點畫圓利用了圓的四對稱性性質。
44. 多邊形填充時，下列論述錯誤的是：在判斷點是否在多邊形內時，一般通過在多變形外找一點，然後根據該線段與多邊形的交點數目為偶數即可認為在多邊形內部，若為奇數則在多邊形外部，且不考慮任何特殊情況。
第三章
1. Cohen-Sutherland演算法，也稱編碼裁剪法。其基本思想是：對於每條待裁剪的線段P1P2分三種情況處理：①若P1P2完全在窗口內，則顯示該線段，簡稱「取」之；②若P1P2完全在窗口外，則丟棄該線段，簡稱「舍」之；③若線段既不滿足「取」的條件也不滿足「舍」的條件，則求線段與窗口邊界的交點，在交點處把線段分為兩段，其中一段 完全在窗口外，可舍棄之，然後對另一段重復上述處理。
2. Sutherland-Hodgman演算法，又稱逐邊裁剪演算法。其基本思想是用窗口的四條邊所在的直線依次來裁剪多邊形。多邊形的每條邊與裁剪線的位置關系有4種情況（假設當前處理的多邊形的邊為SP）：a>端點S在外側，P在內側，則從外到內輸出P和I；b>端點S和P都在內側，則從內到內輸出P；c>端點S在內側，而P在外側，則從內到外輸出I；d>端點S和P都在外側，無輸出。
3. 按裁剪精度的不同，字元裁剪可分為三種情況：字元串裁剪、字元裁剪和筆畫裁剪。
4. 在線段AB的編碼裁剪演算法中，如A、B兩點的碼邏輯或運算全為0，則該線段位於窗口內；如AB兩點的碼邏輯與運算結果不為0，則該線段在窗口外。
5. n邊多邊形關於矩形窗口進行裁剪，結果多邊形最多有2n個頂點，最少有n個頂點。
6. 對一條等長的直線段裁剪，編碼裁剪演算法的速度和中點分割演算法的裁剪速度哪一個快，無法確定。（√）
7. 多邊形裁剪可以看做是線段裁剪的組合。（X）
8. 對於線段來說，中點分割演算法要比其他線段裁剪演算法的裁剪速度快。（X）
9. 多邊形的Weiler-Atherton裁剪演算法可以實現對任意多邊形的裁剪。（√）
第四章
1. 幾何變換是指改變幾何形狀和位置，非幾何變換是指改變圖形的顏色、線型等屬性。變換方法有對象變換（坐標系不動）和坐標變換（坐標系變化）兩種。
2. 坐標系可以分為以下幾種：世界坐標系（是對計算機圖形場景中所有圖形對象的空間定位和定義，是其他坐標系的參照）、模型坐標系（用於設計物體的局部坐標系）、用戶坐標系(為了方便交互繪圖操作，可以變換角度、方向)、設備坐標系（是繪制或輸出圖形的設備所用的坐標系，採用左手系統）。
3. 將用戶坐標系中需要進行觀察和處理的一個坐標區域稱為窗口，將窗口映射到顯示設備上的坐標區域稱為視區。從窗口到視區的變換，稱為規格化變換。（eg.4-1）
4. 所謂體素，是指可以用有限個尺寸參數定位和定形的體，如長方體、圓錐體。
5. 所謂齊次坐標表示，就是用n+1維向量表示n維的向量。
6. 二維點（x,y）的齊次坐標可以表示為：（hx hy h）,其中h≠0。當h=1時稱為規范化的齊次坐標，它能保證點集表示的唯一性。
7. 旋轉變換公式的推導、對稱變換

第五章
1. 交互繪圖技術是一種處理用戶輸入圖形數據的技術，是設計交互繪圖系統的基礎。常見的交互繪圖技術有：定位技術、橡皮筋技術、拖曳技術、定值技術、拾取技術、網格與吸附技術。
2. 常用的橡皮筋技術有：橡皮筋直線、橡皮筋矩形、橡皮筋圓。
3. 拖曳技術是將形體在空間移動的過程動態地、連續地表示出來，直到用戶滿意。
4. 定值技術有2種：一種是鍵入數值，另一種是改變電位計阻值產生要求的數量，可以用模擬的方式實現電位計功能。
5. 拾取一個基本的對象可以通過：指定名稱法、特徵點發、外界矩陣法、分類法、直接法。

第六章
1. 點、線、面是形成三維圖形的基礎，三維變換是從點開始。
2. 三維圖形變換分類：三維圖形變換包括三維幾何變換和平面幾何變換，三維幾何變換包括基本幾何變換和復合變換；平面幾何變換包括平行投影和透視投影，平行投影包括正投影和軸測投影，透視投影包括一點透視、二點透視、三點透視。
3. 投影中心與投影面之間的距離是無限的投影叫做平行投影，它包括正投影和軸測投影。
4. 正投影形成的視圖包括：主視圖、俯視圖和左視圖。軸測投影形成的視圖為軸測圖。
5. 透視投影也稱為中心投影，其投影中心與投影面之間的距離是有限的。其特點是產生近大遠小的視覺效果
6. 對於透視投影，不平行於投影面的平行線的投影會匯聚到一個點，這個點稱為滅點。透視投影的滅點有無限多個，與坐標軸平行的平行線在投影面上形成的滅點稱為主滅點。主滅點最多有3個，其對應的透視投影分別稱為一點透視、二點透視、三點透視。

第七章
1. 型值點是曲面或曲線上的點，而控制點不一定在曲線曲面上，控制點的主要目的是用來控制曲線曲面的形狀。
2. 插值和逼近是曲線曲面設計中的兩種不同方法。插值—生成的曲線曲面經過每一個型值點，逼近—生成的曲線曲面靠近每一個控制點。
3. 曲線曲面的表示要求：唯一性、統一性、幾何不變性、幾何直觀、易於界定、易於光滑連接。
4. 曲線曲面有參數和非參數表示，但參數表示較好。非參數表示又分為顯式和隱式兩種。
5. 對於一個平面曲線，顯式表示的一般形式是：y=f(x)。一個x與一個y對應，因此顯式方程不能表示封閉或多值曲線。例不能用顯式方程表示一個圓。
6. 如果一個曲線方程表示為f(x,y)=0的形式，我們稱之為隱式表示。其優點是易於判斷函數f(x,y)是否大於、小於或等於零，即易於判斷是落在所表示曲線上還是在曲線的哪一側。
7. 參數連續與幾何連續的區別：參數連續性是傳統意義上的、嚴格的連續，而幾何連續性只需限定兩個曲線段在交點處的參數導數成比例，不必完全相等，是一種更直觀、易於交互控制的連續性。
8. 在曲線曲面造型中，一般只用到C1（1階參數連續）、C2（2階參數連續）、G1（1階幾何連續）、G2（2階幾何連續）。切矢量（一階導數）反映了曲線對參數t的變化速遞，曲率（二階導數）反映了曲線對參數t變化的加速度。
9. 通常C1連續必能保證G1的連續，但G1的連續並不能保證C1連續。
10. 對於三次Hermite曲線，用於描述曲線的可供選擇的條件有：端點坐標、切矢量和曲率。
11. 三次Hermite曲線特點：①可局部調整，因為每個曲線段僅依賴於端點約束；②基於Hermite樣條的變化形式有Cardinal樣條和Kochanek-Bartels樣條；③具有幾何不變性。
12. Bezier曲線的性質：①端點性質②端點切矢量③端點的曲率④對稱性⑤幾何不變性⑥凸包性⑦變差縮減性。
13. 一次Bezier曲線是連接起點P0和終點P1的直線段，二次Bezier曲線對應一條起點P0終點在P2處的拋物線。
14. B樣條曲線的性質：①局部性②連續性或可微性③幾何不變性④嚴格凸包性⑤近似性⑥變差縮減性。
15. NURRS曲線具有以下性質：①局部性②可微性③仿射不變性④嚴格保凸性⑤一般性⑥變差縮減性⑦端點性質。

第八章
1. 要把三維物體的信息顯示在二維顯示設備中，必須通過投影變換。由於投影變換失去了深度信息，往往會導致二義性，要消除二義性，就必須在繪制時消除實際不可見的線和面，稱作消除隱藏線和隱藏面，簡稱消隱。
2. 面消隱常用演算法有：深度緩沖區（Z-buffer）演算法和深度排序演算法（畫家演算法）。
3. 深度緩沖區演算法和深度排序演算法的區別：

② 編程與數學的關系

你好，我是計算機專業大三的學生，我來說說在我的印象中數學的關系：
第一，編寫程序體現的是一個人的邏輯思維，既然涉及到邏輯，必然會與數學有些關系。但是與數學關系的深淺要與你所涉及的方面有關。
第二，編程中必須要學的數學：
1.最基本的數字與運算知識：二進制的概念（在哈夫曼樹，哈弗曼編碼等方面有直接的應用），取余的概念（在循環鏈表，隨機數方面有應用），基礎平面幾何（在繪制窗口，繪制曲線，自定義按鈕等圖形化的地方會用到），還有些很基礎的數學知識絕對不超出初中的范疇。
2.計算機中的數學知識：主要的一門叫做離散數學，講的是邏輯代數的相關知識，其實在真正的編程中不會直接體現這門課的重要性，對於初學者只要知道：與或非是怎麼回事，什麼是集合就可以了。離散數學還涉及到一些圖與樹的概念，我現在先把這些劃歸到數據結構中。
3.我前面說了，編程與你的需求有直接的關系，有些編程領域與數學的知識密不可分：
1）搞底層：舉個例子，如果你想設計一套你自己的windows字體，那麼肯定涉及到字體平滑，字體平滑就涉及到一個很難的數學知識：插值。這個知識在數值分析中講解，而且沒有高等數學的基礎，這門課想學會的可能性幾乎是零。。。這門課主要解決的是高等數學中的問題如何用計算機解決，比如：泰勒插值，拉格朗日插值，求解一般方程或微分方程的解，還有的我忘了，反正都是很難的知識。而底層的很多編程都是以這些為基礎的。
2）搞圖形學：CG技術由於在游戲中的如日中天，使得很多初高中生對圖形學神往已久，但卻不知計算機圖形學的知識是建立在很多大學數學課程的基礎上的。尤其是圖形學理論的學習，沒有線性代數的基礎是根本看不懂的。而在三維視圖方面又要涉及到高等數學中極坐標的知識。很多演算法，比如梁-Baskey演算法對於平面幾何分析水平的要求是非常高的！如果你想搞游戲設計，動畫電影（這個是要寫腳本程序的，否則畫面哪能那麼好），我勸你還是到了大學再深入學習吧。
3）搞演算法：學習演算法與其說數學要好，還不如說成是智力要好。。。比如分治法，動態規劃演算法，回溯法等對於問題的前期分析要求很高，尤其是列出遞歸方程，這些我覺得是在考智力。還有一些，比如圖演算法，樹的應用，排序，查找，這些知識涉及到計算機專業的另一門課程：數據結構，這門課是計算機專業的核心課程之一，也是專業與非專業的最大區別。這門課對數學要求不高，但對於一個人的思維要求比較高。還有像計算幾何的問題，那就是純數學問題了。。。
4）搞密碼學：我不搞這方面，而且也沒研究過，但聽說這方面對數學要求極高！由於我的數學比較好，別人還推薦過我去搞這方面，但是我一想到面對的都是數字，我就退縮了。。。
以上就是我所知道的與數學有關的計算機分支，每個方面都夠人學一輩子，而且學好了，前途與錢途都是大大的！
第三，這么多方面都跟數學有關，那編程豈不沒法學了？還有些方面對於數學要求相對較低，我說的相對較低是由於不管哪方面都會涉及到一些基礎的數學演算法。總的來說，越往高層，對數學的要求越低，比如MFC，那些網路編程，系統編程都是封裝好的，但對於一個系統來說整體的規劃和設計更關鍵，就是說前期的需求分析、邏輯結構設計和物理結構設計比編碼更重要，當然工資也更高。。。
最後，我想給你提些學習編程的建議：
1）由於你的年齡還小，中國的教育體質問題，希望你不要把太多的精力放在這上面。。。我想你懂的。雖然聽說過哪個孩子做了個游戲之後成了百萬富翁，但這么多年了，似乎只有他一個，不要懷疑自己的實力，但更不要幻想你有這個運氣。。。
2）編程注重邏輯思維，你才是初中生，大腦的發育不知是否成熟（絕不是說你智力低，你應該知道大腦發育是有階段的吧），所以要以語言的基礎為主，這個對數學要求不高。
3）請選一門語言去練習，編程注重實踐，沒有實踐只有理論那就等於沒學，所以一定多練練。至於語言，我推薦學習C或C++，至於C與C++是怎麼回事，怎麼學習，這是另一個比較難的話題。。。注意別上來就學VC++（MFC），否則你會一事無成！
4）編程很枯燥，所以要耐得住性子，不要一見到難題就退縮，一見到不會的概念就把書扔了，不會的時候請多看看基礎，八成是語言基礎不到位。
就寫這么多吧，希望我的回答對你有幫助。你若有什麼問題還可以繼續問，若是編程過程中遇到什麼問題也可以問我，很歡迎的！

③ 在線等，急求一道C語言的編程題！！！正確答案直接發20元微信紅包

凸包問題。計算幾何。

#include<stdio.h>
#include<string.h>
structnode
{
longlongx,y;
}a[100005],b[100005];
longlongmul(nodep1,nodep2,nodep3)
{
return(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
intmain()
{
intn,m,i,low,high,mid,flag;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y);
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%lld%lld",&b[i].x,&b[i].y);
flag=0;
for(i=0;i<m;i++)
{
if(mul(a[0],a[1],b[i])>=0||mul(a[0],a[n-1],b[i])<=0)
{
flag=1;
gotoloop;
}
low=2;high=n-1;
while(low<high)
{
mid=(low+high)>>1;
if(mul(a[0],a[mid],b[i])>0)
high=mid;
elselow=mid+1;
}
if(mul(a[low],a[low-1],b[i])<=0)
{
flag=1;
gotoloop;
}
}
loop:if(flag)
printf("NO
");
elseprintf("YES
");
}
return0;
}

轉自http://www.cnblogs.com/dream-wind/archive/2012/05/23/2514694.html

演算法描述裡面也有。

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

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