2012《計算幾何》實驗任務(wù)

2012《計算幾何》實驗任務(wù)基本要求：最低完成100分值的題目。三維房子的顯示(40分)目的：熟悉形體線框模型(或半實體模型)的描述方法，熟悉觀察變換的實現(xiàn)及其效果。要求：已知一個房子，其在用戶坐標(biāo)系下的坐標(biāo)如圖所示。實現(xiàn)一個程序，可以用對話框任意輸入視點坐標(biāo)，把該房子的平行投影效果顯示出來。房子的坐標(biāo)如下：P0(-80,0,0)，P](80,0,0)，P2(80,0,200)，P3(0,0,260)，P4(-80,220,200)，P5(-80,220,0)，P6(80,220,0)，P7(80,220,200),P8(0,220,260),P9(-80,220,200)。鼓勵：如果你能夠用虛線顯示出隱藏線，本題成績加20分。判斷隱藏線采用如下原則：凸多面體的一條邊是不可見的，當(dāng)且僅當(dāng)它的兩個面是不可見的。凸多面體的一個面是不可見的，當(dāng)且僅當(dāng)它的法向與視線的夾角小于90度。參考程序：目錄下有可執(zhí)行的演示程序。多邊形的基本計算(30分)目的：熟悉多邊形的交互繪制，熟悉多邊形的表示，熟悉多邊形的基本計算。要求：用戶在交互輸入一個多邊形之后，可以選擇菜單，完成下列計算：多邊形的面積；多邊形的方向；交互輸入一點，判斷該點在多邊形的內(nèi)外。計算結(jié)果以對話框的形式反饋。鼓勵：本題沒有額外獎勵。參考程序：本題沒有可執(zhí)行的演示程序。在實現(xiàn)上，你可利用交互繪制多邊形的源程序多邊形的三角剖分（30分）目的：熟悉多邊形的表示，熟悉多邊形三角剖分的切耳算法。要求：用戶在交互輸入一個多邊形之后，通過選擇菜單，完成并顯示它的三角剖分。鼓勵：本題沒有額外獎勵。參考程序：目錄下有可執(zhí)行的演示程序。在實現(xiàn)上，你可利用交互繪制多邊形的源程序平面點集的凸包（30分）目的：熟悉平面點集凸包的生成算法。要求：用戶在交互輸入若干個點之后，通過選擇菜單，生成并顯示它的凸包。鼓勵：本題沒有額外獎勵。參考程序：目錄下有可執(zhí)行的演示程序。在實現(xiàn)上，你可以自己編寫程序，卷包裹算法也可，也可以利用目錄中的Graham掃描算法的控制臺源程序。平面點集的Delaunay三角剖分（20分）目的：熟悉平面點集的Delaunay三角剖分及其生成算法。要求：用戶在交互輸入若干個點之后，通過選擇菜單，生成并顯示它的Delaunay三角剖分。鼓勵：如果你采用的是O（n2）時間算法，額外獎勵30分。如果你能夠以四種顏色顯示每個三角形的內(nèi)部，并且使得相鄰的三角形具有不同的顏色，你也將額外被獎勵30分。參考程序：目錄下有可執(zhí)行的演示程序。在實現(xiàn)上，你可以利用O（n4）時間的控制臺源程序，也可以利用O（n2）時間的控制臺源程序。如果你想著色，需要重構(gòu)出三角剖分的數(shù)據(jù)結(jié)構(gòu)。多邊形的布爾集合運算（60分）

目的：熟悉多邊形的布爾集合運算算法。要求：用戶在交互輸入兩個多邊形之后，通過選擇菜單，生成并顯示它的并集、交集或差集。鼓勵：本題只完成并運算即可。如果你能夠完成交運算或差運算，額外獎勵40分參考程序：目錄下有可執(zhí)行的演示程序。在實現(xiàn)上，你應(yīng)該自己編寫程序。三維點集的凸包（50分）目的：多面體的表示方法，熟悉三維平面點集凸包的生成算法。要求：提供菜單來隨機地生成三維點集，通過選擇菜單，生成并顯示它的凸包。并且可以如房子一樣，在任意視點下觀察。鼓勵：同房子一樣，如果你能夠以虛線的形式顯示隱藏線，額外獎勵30分參考程序：目錄下有可執(zhí)行的演示程序（隨后提供）。在實現(xiàn)上，你應(yīng)該利用目錄下的增量式算法的控制臺源程序。B樣條曲面的顯示（40分）目的：認識B樣條曲面及其離散化方法。要求：已知存在于文件中的B樣條曲面的控制頂點網(wǎng)格數(shù)據(jù)（bs_surf_1.txt是一個例子文件），要求讀入該文件并將其真實地顯示出來，并且可以在任意視點下觀察?？刂祈旤c網(wǎng)格數(shù)據(jù)文件的格式如下：u方向控制頂點mv方向控制頂點個數(shù)nP00的坐標(biāo)值P01的坐標(biāo)值Pm-1,n-1Pm-1,n-1的坐標(biāo)值參考程序：目錄下有可執(zhí)行的演示程序。在實現(xiàn)上，你應(yīng)該你應(yīng)該自己編寫程序。多面體的平移掃描生成（80分）目的：進一步熟悉多面體的表示方法，熟悉掃描法生成多面體的方法。要求：用戶在交互輸入一個多邊形之后，可以選擇菜單，輸入