2025年大學(xué)《數(shù)學(xué)與應(yīng)用數(shù)學(xué)》專業(yè)題庫(kù)——計(jì)算幾何與計(jì)算機(jī)輔助設(shè)計(jì)考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題1.在二維空間中，判斷三個(gè)點(diǎn)A(x1,y1),B(x2,y2),C(x3,y3)是否按順時(shí)針?lè)较蚺帕?，下列哪個(gè)判斷條件是正確的？A.(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)>0B.(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)<0C.(x2-x1)*(y3-y1)+(y2-y1)*(x3-x1)>0D.(x2-x1)*(y3-y1)+(y2-y1)*(x3-x1)<02.給定一個(gè)點(diǎn)集P，構(gòu)建Voronoi圖的過(guò)程主要依賴于什么數(shù)據(jù)結(jié)構(gòu)？A.K-d樹(shù)B.B樹(shù)C.哈希表D.樹(shù)狀體（Octree/Quadtree）3.在Bezier曲線設(shè)計(jì)中，控制點(diǎn)P0,P1,...,Pn對(duì)曲線形狀的影響是？A.P0決定起點(diǎn)，Pn決定終點(diǎn)，其他點(diǎn)僅影響切線方向B.所有控制點(diǎn)都等量影響曲線形狀C.僅P0和Pn影響曲線的大致走向D.控制點(diǎn)僅決定曲線的局部細(xì)節(jié)4.B樣條曲線與Bezier曲線相比，其主要優(yōu)點(diǎn)之一是？A.計(jì)算更為簡(jiǎn)單，易于實(shí)現(xiàn)B.能精確通過(guò)所有控制點(diǎn)C.具有局部修改性，修改一個(gè)控制點(diǎn)只影響局部曲線段D.形狀變化更為豐富，易于設(shè)計(jì)復(fù)雜曲線5.在計(jì)算機(jī)輔助幾何設(shè)計(jì)（CAD）中，邊界表示（B-Rep）方法主要用于？A.表示和處理點(diǎn)集B.表示和處理自由曲面C.表示和分析實(shí)體幾何形狀，通常使用多邊形網(wǎng)格或構(gòu)造實(shí)體幾何（CSG）作為基礎(chǔ)D.表示曲線的參數(shù)方程二、填空題1.計(jì)算幾何中，凸包是包含點(diǎn)集P的最小凸多邊形（或凸多面體），其計(jì)算常用_________算法或_________算法。2.對(duì)于一個(gè)n次貝塞爾曲線，它共有_________個(gè)控制點(diǎn)，其定義域?yàn)閇0,1]。3.在二維空間中，判斷點(diǎn)q是否在簡(jiǎn)單多邊形p的內(nèi)部，常用的方法是_________和_________算法。4.NURBS（非均勻有理B樣條）曲線/曲面能夠精確表示_________和_________，具有廣泛的幾何表示能力。5.幾何布爾運(yùn)算（并、交、差）是CAD造型中的基本操作，對(duì)于多邊形網(wǎng)格模型，這些運(yùn)算通常通過(guò)_________（如D-布爾運(yùn)算）或基于體素的方法實(shí)現(xiàn)。三、計(jì)算題1.給定點(diǎn)A(1,2)，B(4,6)，C(5,3)。計(jì)算向量AB和向量AC的叉積，并據(jù)此判斷點(diǎn)C相對(duì)于向量AB是在哪個(gè)象限（順時(shí)針、逆時(shí)針或共線）。2.已知一個(gè)三次貝塞爾曲線的控制點(diǎn)分別為P0(0,0),P1(1,2),P2(3,3),P3(4,0)。求該曲線在參數(shù)t=1/2處的切線方向向量。3.設(shè)有兩個(gè)不相交的簡(jiǎn)單凸多邊形P1和P2（用頂點(diǎn)序列表示），描述如何使用掃描線算法計(jì)算P1∪P2（并集）的邊界多邊形。四、簡(jiǎn)答題1.簡(jiǎn)述Delaunay三角剖分的特性，并列舉至少三個(gè)其在計(jì)算幾何或相關(guān)應(yīng)用中（如地形建模、點(diǎn)云處理）的重要優(yōu)勢(shì)。2.解釋NURBS曲面與Bezier曲面在表示能力和局部修改性方面的主要區(qū)別。五、證明與設(shè)計(jì)題1.證明：對(duì)于二維空間中的兩個(gè)線段L1(P0,P1)和L2(P2,P3)，如果它們相交，那么向量(P1-P0)×(P3-P2)和向量(P3-P2)×(P1-P0)的符號(hào)相反。六、編程實(shí)踐題（注：此處按要求不寫答案，但實(shí)際考試中應(yīng)有編程題目）設(shè)計(jì)一個(gè)函數(shù)，輸入為一個(gè)簡(jiǎn)單多邊形的頂點(diǎn)序列（按順序給出），輸出該多邊形的凸包頂點(diǎn)序列。要求采用Graham掃描算法或Jaumann算法進(jìn)行實(shí)現(xiàn)。請(qǐng)描述算法的主要步驟，并給出相應(yīng)的偽代碼或代碼框架。試卷答案一、選擇題1.B2.A3.A4.C5.C二、填空題1.Graham掃描；Jarvis步進(jìn)（或GiftWrapping）2.n+13.跨邊判斷；射線法4.圓錐曲線；自由曲面5.D-布爾運(yùn)算三、計(jì)算題1.解析思路：計(jì)算向量AB=(Bx-Ax,By-Ay)=(4-1,6-2)=(3,4)。計(jì)算向量AC=(Cx-Ax,Cy-Ay)=(5-1,3-2)=(4,1)。向量AB和AC的叉積為AB×AC=(3*1)-(4*4)=3-16=-13。由于叉積結(jié)果為負(fù)，且向量AC在向量AB的逆時(shí)針?lè)较蛐D(zhuǎn)，因此點(diǎn)C相對(duì)于向量AB是逆時(shí)針?lè)较虻?。答案：叉積-13，點(diǎn)C相對(duì)于向量AB是逆時(shí)針?lè)较虻摹?.解析思路：三次貝塞爾曲線的切線方向向量在任意參數(shù)t處為P'(t)=n*(P1-P0)+2n*(P2-P1)+n*(P3-P2)，其中n=t^(n-1)*(1-t)^(m-n)*m!。對(duì)于三次曲線n=m=3，所以n(t)=3*(1-t)^2*t。P'(t)=3*(1-t)^2*t*(P1-P0)+6*(1-t)*t*(P2-P1)+3*t^2*(P3-P2)。將P0,P1,P2,P3的坐標(biāo)代入，并計(jì)算t=1/2時(shí)的值。答案：切線方向向量為(-1,1)。3.解析思路：掃描線算法計(jì)算并集的基本思想是：按y坐標(biāo)排序所有多邊形的頂點(diǎn)；使用掃描線從下往上掃描，維護(hù)當(dāng)前活躍多邊形列表；當(dāng)掃描線進(jìn)入多邊形時(shí)，將其加入活躍列表，并根據(jù)其邊與列表中其他邊的關(guān)系（交叉點(diǎn)、頂點(diǎn)）更新列表；當(dāng)掃描線離開(kāi)多邊形時(shí)，將其移出活躍列表；在掃描過(guò)程中，根據(jù)邊的進(jìn)入和離開(kāi)順序以及交叉點(diǎn)，構(gòu)建并集的邊界多邊形。答案：使用掃描線自下而上遍歷，維護(hù)活躍邊表，根據(jù)邊的進(jìn)入、離開(kāi)和交叉點(diǎn)信息，按順序連接邊點(diǎn)，構(gòu)建并集的邊界多邊形。四、簡(jiǎn)答題1.解析思路：Delaunay三角剖分的特性包括：最鄰近點(diǎn)三角剖分（每個(gè)三角形頂點(diǎn)都是其內(nèi)部最近點(diǎn)的鄰點(diǎn)）、空外接圓特性（每個(gè)三角形的外接圓不包含任何其他點(diǎn)）、最大最小角特性（相對(duì)其他可能三角形，Delaunay三角形具有最大的最小角）。優(yōu)勢(shì)：生成的網(wǎng)格具有良好的流形性，角度變化較為尖銳，能有效避免狹長(zhǎng)三角形；在點(diǎn)云數(shù)據(jù)中能更好地反映局部細(xì)節(jié)；與Voronoi圖對(duì)偶，可用于區(qū)域劃分和聚類分析；在參數(shù)化造型和地形建模中能產(chǎn)生更平滑、自然的曲面。2.解析思路：NURBS能夠精確表示任何類型的Bézier曲面（通過(guò)設(shè)置權(quán)值為1），而B(niǎo)ézier曲面僅能精確表示由其控制點(diǎn)張成的凸包區(qū)域。NURBS具有局部修改性，改變一個(gè)控制點(diǎn)或權(quán)值只影響該控制點(diǎn)附近的曲面區(qū)域（由權(quán)值衰減函數(shù)控制），而B(niǎo)ézier曲面控制點(diǎn)的修改會(huì)影響整個(gè)曲面。NURBS的設(shè)計(jì)更靈活，可以通過(guò)調(diào)整控制點(diǎn)和權(quán)值來(lái)實(shí)現(xiàn)更復(fù)雜的幾何形狀和更精細(xì)的控制。五、證明與設(shè)計(jì)題1.證明思路：使用向量叉積判斷兩線段是否相交以及它們相對(duì)方向。設(shè)兩線段L1(P0,P1)和L2(P2,P3)。向量AP0=P0-P2，向量AP1=P1-P2。向量方向D1=P1-P0，D2=P3-P2。向量叉積D1×D2和D2×D1的符號(hào)相反。如果L1和L2相交，則點(diǎn)P0在L2上或其延長(zhǎng)線上，點(diǎn)P1在L2的另一側(cè)或其延長(zhǎng)線上，反之亦然。這意味著向量AP0和AP1關(guān)于D2的方向相反，即(AP0×D2)和(AP1×D2)的符號(hào)相反。同樣，向量AP0和AP1關(guān)于D1的方向也相反，即(AP0×D1)和(AP1×D1)的符號(hào)相反。由于D1×D2和D2×D1符號(hào)相反，因此(AP0×D2)和(AP1×D2)的符號(hào)相反等價(jià)于(AP0×D1)和(AP1×D1)的符號(hào)相反。答案：見(jiàn)證明思路。六、編程實(shí)踐題解析思路：Graham掃描算法步驟：1.找到所有點(diǎn)中y坐標(biāo)最小的點(diǎn)，如果有多個(gè)，則取x坐標(biāo)最小的一個(gè)作為基準(zhǔn)點(diǎn)P0。2.將其余點(diǎn)按相對(duì)于P0的極角（與P0連接向量的橫縱坐標(biāo)的反正切值，注意處理水平方向）進(jìn)行排序，如果極角相同，則距離P0近的點(diǎn)排前面。3.初始化凸包棧，將P0,P1,P2壓入棧。4.從P3開(kāi)始，對(duì)于棧頂?shù)拿總€(gè)點(diǎn)H，比較當(dāng)前點(diǎn)P與H及H的前一個(gè)點(diǎn)H'構(gòu)成的向量（即P,H,H'）。如果向量(H'->H)到(H->P)依次是逆時(shí)針?lè)较颍床娣e小于0），則將H彈出棧。重復(fù)此過(guò)程，直到向量(H'->H)到(H->P)是順時(shí)針?lè)较颍ú娣e大于0）或P在棧頂點(diǎn)H的線上（叉積等于0）。5.將點(diǎn)P壓入棧。6.棧中剩下的點(diǎn)即為凸包頂點(diǎn)，按出棧順序（或入棧順序）輸出。偽代碼框架：SelectP0asthepointwithminimumy(andminimumxiftiesexist).SortpointsP1,...,PnbypolaranglewithrespecttoP0.InitializestackwithP0,P1,P2.ForeachpointPifromP3toPn:Whilestacksize>=