最小包圍圓課件資料

1、C程序設(shè)計課程設(shè)計報告（20142015學(xué)年第二學(xué)期）題目：最小包圍圓問題學(xué)院：電氣與電子工程學(xué)院班級：電氣1309學(xué)號：1304080009姓名：唐永亮指導(dǎo)教師：羅濤華時間：起2015.4.27止2015.4.30一、課程設(shè)計基本信息課程代碼：05190124課程名稱：計算機基礎(chǔ)課程設(shè)計課程英文名稱:Computer-basedCourseDesign課程所屬單位（院（系）、教研室）：數(shù)學(xué)與計算機學(xué)院計算機基礎(chǔ)課程群課程面向?qū)I(yè)：食品科學(xué)與工程學(xué)院、機械工程學(xué)院、電氣與電子工程學(xué)院、土建學(xué)院、動物科學(xué)與營養(yǎng)工程學(xué)院、化學(xué)與環(huán)境工程學(xué)院、工商管理類、國際經(jīng)濟與貿(mào)易、旅游管理、金融學(xué)、行政管理、

2、漢語言文學(xué)、英語、護理學(xué)、康復(fù)治療專業(yè)、生物科學(xué)類、制藥工程、制藥工程（生物制藥）、藥物制劑、物流管理課程類型：必修課先修課程：大學(xué)計算機基礎(chǔ)通識選修課程、程序設(shè)計課程學(xué)分：1總學(xué)時：1周二、課程設(shè)計目標(biāo)掌握所學(xué)語言程序設(shè)計的方法，熟悉所學(xué)語言的開發(fā)環(huán)境及調(diào)試過程，熟悉所學(xué)語言中的數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)、語句結(jié)構(gòu)、運算方法，鞏固和加深對理論課中知識的理解，提高學(xué)生對所學(xué)知識的綜合運用能力。通過綜合設(shè)計要求達到下列基本技能：1培養(yǎng)查閱參考資料、手冊的自學(xué)能力，通過獨立思考深入鉆研問題，學(xué)會自己分析、解決問題。2通過對所選題目方案分析比較，確立方案，編制與調(diào)試程序，初步掌握程序設(shè)計的方法，能熟練調(diào)試程

3、序。3系統(tǒng)設(shè)計編程簡練，可用，功能全面，并有一定的容錯能力。用戶界面良好，有較好的輸出功能。在完成課題基本要求后，具有創(chuàng)新型設(shè)計，具有一定的實用價值。4.根據(jù)個人的設(shè)計調(diào)試過程，撰寫設(shè)計報告。三、課程設(shè)計內(nèi)容熟練掌握所學(xué)語言的基本知識：數(shù)據(jù)類型（整形、實型、字符型、指針、數(shù)組、結(jié)構(gòu)等）；運算類型（算術(shù)運算、邏輯運算、自增自減運算、賦值運算等）；程序結(jié)構(gòu)（順序結(jié)構(gòu)、判斷選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)）；大程序的功能分解方法（即函數(shù)的使用）等。進一步掌握各種函數(shù)的應(yīng)用，包括時間函數(shù)、繪圖函數(shù)，以及文件的讀寫操作等。四、課程設(shè)計要求1. 要求每個同學(xué)都要認真對待，積極參與。2. 課程設(shè)計結(jié)束時，提交完成的所有源

4、程序、相關(guān)文件和可執(zhí)行文件。同時填寫并完成課程設(shè)計報告冊。3. 不符合要求的程序、設(shè)計報告、抄襲的設(shè)計報告或源程序代碼、在設(shè)計中完全未參與的將作不及格處理。五、考核方式指導(dǎo)老師負責(zé)驗收程序的運行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設(shè)計報告等進行綜合考評，百分制計算，具體考核標(biāo)準(zhǔn)主要包含以下幾個部分：1. 程序運行情況20分2. 程序功能的完善程度10分3. 程序結(jié)構(gòu)的合理性10分4. 對問題的答辯情況20分5.創(chuàng)新情況10分6. 學(xué)生的工作態(tài)度與獨立工作能力10分7. 設(shè)計報告內(nèi)容的規(guī)范性20分備注:1. 按規(guī)定時間填寫各階段文檔，學(xué)習(xí)態(tài)度加5分2. 設(shè)計報告內(nèi)容雷同扣40分，

5、無調(diào)試過程問題分析扣10分，無參考文獻扣10分3. 源程序無注釋則在程序結(jié)構(gòu)合理性扣10分六、課程設(shè)計主要參考資料1. 譚浩強著.C程序設(shè)計（第3版）.北京：清華大學(xué)出版社，2005.72. 劉光蓉、汪靖、陸登波主編.C程序設(shè)計實驗與實踐教程.北京：清華大學(xué)出版社，2011.23. 游洪躍主編.C語言程序設(shè)計實驗與課程設(shè)計教程.北京：清華大學(xué)出版社，2011.54. （美）PerterVanDerLinden著，徐波譯.C專家編程（C編程語言經(jīng)典之作）.北京：人民郵電出版社，2008.25. 凱尼格著，高巍譯.C陷阱與缺陷.北京：人民郵電出版社，2008.26. MarkdeBerg等著，鄧俊

6、輝譯，計算幾何-算法與應(yīng)用（第3版），清華大學(xué)出版社，2009年8月7. 楊克昌編著，計算機程序設(shè)計典型例題精解，國防科技大學(xué)大學(xué)出版社，1999年3月七、課程設(shè)計計劃安排時間任務(wù)課程設(shè)計前一周選擇課程設(shè)計題目，分析課題的要求，確定設(shè)計方案，完成報告冊中“課程設(shè)計概述”課程設(shè)計第1天按功能模塊編寫詳細設(shè)計說明，完成報告冊中“總體設(shè)計”課程設(shè)計第2天編寫程序、調(diào)試程序課程設(shè)計第3天編寫程序、調(diào)試程序，完成報告冊中“詳細設(shè)計”課程設(shè)計第4天調(diào)試程序，完成報告冊中“調(diào)試分析過程”課程設(shè)計第5天完成報告冊中“總結(jié)”、“參考文獻”、“課程設(shè)計評審表”部分內(nèi)容，提交課程設(shè)計報告、源程序、面試或答辯11一、

7、課程設(shè)計概述最小包圍圓問題是計算幾何中的一個很經(jīng)典的問題：輸入平面上n個點的坐標(biāo)，輸出一個圓的圓心和半徑，這個圓剛好包圍了給出的n個點，即這個圓是包圍了給出所有點的最小的圓，求最小包圍圓的圓心位置和半徑。題描述設(shè)計要求1.2.3.4.定義一個結(jié)構(gòu)體類型表示平面上點的位置坐標(biāo)。編寫一個函數(shù)求兩點之間的距離。編寫一個函數(shù)確定三點是否在同一條直線上。編寫一個函數(shù)求n個點集的最小包圍圓。5.編寫一個函數(shù)求通過點q,包含了n個點集中所有點的最小包圍圓。6.編寫一個函數(shù)求通過點q1和q2,包含了n個點集中所有點的最小包圍圓。7.主函數(shù)中實現(xiàn)平面坐標(biāo)點個數(shù)及坐標(biāo)的輸入，調(diào)用以上函數(shù)，求出最小包圍圓的坐標(biāo)位置

8、及半徑。設(shè)掌握所學(xué)語言程序設(shè)計的方法，熟悉所學(xué)語言的開發(fā)環(huán)境及計調(diào)試過程，熟悉所學(xué)語言中的數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)、語句結(jié)構(gòu)、目運算方法，鞏固和加深對理論課中知識的理解，提高學(xué)生對所的學(xué)知識的綜合運用能力。開1.Visualc+60發(fā)2.電腦環(huán)3Win7操作系統(tǒng)境二、總體設(shè)計(1)最小包圍圓問題是輸入平面上n個點的坐標(biāo)，輸出一個圓的圓心和半徑。因此，這程序設(shè)計需要運用到最小包的求解方法。1.定義一個結(jié)構(gòu)體類型來表示平面上的點的坐標(biāo)位置。定義結(jié)構(gòu)體數(shù)組存放n座摩天大樓的坐標(biāo)位置。2編寫一個函數(shù)求兩點之間的距離。求平面上兩點之間的距離公式為d=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y

9、1-y2)3編寫一個函數(shù)確定三點是否共線。先求叉積，若叉積為0即三點共線；反之，三點不共線。4.編寫一個函數(shù)求n個點集的最小包圍。任意取兩個點，以這兩個點的連線為直徑作圓，再以此判斷剩余的點是否都在圓上或圓內(nèi)。5.編寫一個函數(shù)求通過點q，包含了n個點集中所有點的最小包圍圓。先用p1和pi作圓，再從2到i-1判斷是否有點不在圓上。6.編寫一個函數(shù)求通過點q1和q2,包含了n個點集中所有點的最小包圍圓。7.主函數(shù)實現(xiàn)平面坐標(biāo)點個數(shù)及坐標(biāo)輸入，調(diào)用以上函數(shù)，求出最小包圍圓的坐標(biāo)位置和半徑。二、總體設(shè)計系統(tǒng)總體設(shè)計框架三、詳細設(shè)計1.利用結(jié)構(gòu)體類型定義平面上點的坐標(biāo)typedefstructpoint

10、intx;inty;POINT;2.定義結(jié)構(gòu)體數(shù)組存放n座摩天大樓的位置坐標(biāo)#defineN100POINTaN;結(jié)構(gòu)體數(shù)組元素的引用：aix，aiy,結(jié)構(gòu)體數(shù)組元素的使用等同于同類型的普通變量。3求最小包圍圓的求解方法可以轉(zhuǎn)換為3個子問題進行求解。由于三個點確定一個圓，因此可以從沒有確定點，到有一個確定點，再到兩個確定點，再到三個確定點來求的問題。(1) 通過三個點求判斷三點是否共線，找到距離最遠的一對點，以其連線為直徑作圓，若不共線轉(zhuǎn)換為三角形的外接圓問題。利用doublemultiply(Pointp1,Pointp2,Pointp0)return(p1x-pOx)*(p2y-p0y)-

11、(p2x-p0.x)*(p1y-p0y)判斷三點是否共線(2) 求三角形外接假設(shè)三個點(x1,y1),(x2,y2),(x3,y3)設(shè)過(x1,y1),(x2,y2)的直線L1方程為Ax+By二C,它的中點為(x1+x2)/2,(y1+y2)/2),L1中垂線方程為A1x+B1y=C1;則它的中垂線方程中A1=-B=x2-x1,B1=A=y2-y1,C1=-B*(x1+x2)/2+A*(y1+y2)/2同理可得過(x1,y1),(x3,y3)的直線的中垂線方程。這兩條中垂線的交點就是圓心。(3) 求兩條直線交點設(shè)兩條直線為A1x+B1y=C1和A2x+B2y=C2.設(shè)一個變量det二A1*B2

12、-A2*B1;如果det=0,兩直線平行；反之，則交點x=(B2*C1-B1*C2)/det,y=(A1*C2-A2*C1)/det4通過點Pi,包含n個點集中所有點的最小包圍圓，利用for(j=2;j<=n;j+)if(distance(d,aj)<=r)continue;elseMiniDiscWith2Point(pi,aj,j-1);從第一點開始查找。三、詳細設(shè)計(1)主要功能模塊源程序#include<stdio.h>#include<math.h>structPointdoublex,y;；Pointa1000,d;doubler;doubled

13、istance(Pointp1,Pointp2)return(sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);doublemultiply(Pointp1,Pointp2,Pointp0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);voidMiniDiscWith2Point(Pointp,Pointq,intn)d.x=(p.x+q.x)/2.0;d.y=(p.y+q.y)/2.0;r=distance(p,q)/2;intk;doublec1,c2,t1,t2,t3;fo

14、r(k=1;k<=n;k+)if(distance(d,ak)<=r)continue;if(multiply(p,q,ak)!=0.0)c1=(p.x*p.x+p.y*p.y_q.x*q.x_q.y*q.y)/2.0;c2=(p.x*p.x+p.y*p.y-ak.x*ak.x-ak.y*ak.y)/2.0;d.x=(c1*(p.y_ak.y)_c2*(p.y_q.y)/(p.x_q.x)*(p.y_ak.y)_(p.x_ak.x)*(p.y_q.y);d.y=(c1*(p.x_ak.x)_c2*(p.x_q.x)/(p.y_q.y)*(p.x_ak.x)_(p.y_ak.y)*(

15、p.x_q.x);r=distance(d,ak);elset1=distance(p,q);t2=distance(q,ak);13=distance(p,ak);if(t1>=t2&&t1>=t3)d.x=(p.x+q.x)/2.0;d.y=(p.y+q.y)/2.0;r=distance(p,q)/2.0;elseif(t2>=tl&&t2>=t3)d.x=(ak.x+q.x)/2.0;d.y=(ak.y+q.y)/2.0;r=distance(ak,q)/2.0;elsed.x=(ak.x+p.x)/2.0;d.y=(ak.y+p

16、.y)/2.0;r=distance(ak,p)/2.0;voidMiniDiscWithPoint(TPointpi,intn)d.x=(pi.x+al.x)/2.0;d.y=(pi.y+al.y)/2.0;r=distance(pi,al)/2.0;intj;for(j=2;j<=n;j+)if(distance(d,aj)<=r)continue;elseMiniDiscWith2Point(pi,aj,j-l);voidMinDisc(intn)d.x=(al.x+a2.x)/2.0;d.y=(al.y+a2.y)/2.0;r=distance(al,a2)/2.0;int

17、j;for(j=3;j<=n;j+)if(distance(d,aj)<=r)continue;elseMiniDiscWith2Point(al,aj,j-l);intmain()三、詳細設(shè)計主要功能模塊的算法設(shè)計5通過點p,q,包含n個點集中所有點的最小包圍圓，利用for(k=1;k<=n;k+)if(distance(d,ak)<=r)continue;if(multiply(p,q,ak)!=O.O)else通過判斷是否共線，求出最小包圍圓。6.主函數(shù)利用while語句和循環(huán)語句實現(xiàn)n個點的輸入，輸出最小包圍圓的圓心和半徑+三、詳細設(shè)計主要功能模塊源程序whil

18、e(scanf("%d",&n)&&n)for(i=l;i<=n;i+)scanf("%lf%lf",&ai.x,&ai.y);辻(n=l)printf("%.21f%.2lf0.00n",al.x,al.y);continue;r=distance(al,a2)/2.0;d.x=(al.x+a2.x)/2.0;d.y=(al.y+a2.y)/2.0;for(i=3;i<=n;i+)if(distance(d,ai)<=r)continue;elseMiniDiscWithPo

19、int(ai,iT);printf("%.2lf%.2lf%.2lfn",d.x,d.y,r);return0；24四、調(diào)試分析過程1.在定義變量時出現(xiàn)錯誤,得到的數(shù)據(jù)出現(xiàn)錯誤.重新定2.義變量的數(shù)據(jù)類型。使用循環(huán)語句while時，沒有確定循環(huán)結(jié)束的條件，出現(xiàn)死循環(huán)。重新檢查，修正循環(huán)終止條件。3.忘記對所調(diào)用的函數(shù)進行聲明，在編譯時有出錯信息。在main函數(shù)中增加一個對所調(diào)用函數(shù)的聲明。4.在使用scanf函數(shù)時，忘記用變量的地址符。重新書寫?，F(xiàn)的問題5.6.使用一維數(shù)組時，數(shù)組的下標(biāo)出現(xiàn)錯誤，導(dǎo)致輸出的結(jié)果有誤。修正數(shù)組下標(biāo)。輸入數(shù)據(jù)的形式與要求不符合，導(dǎo)致運行程序時沒有得到相應(yīng)的輸出結(jié)果。對照scanf函數(shù)中的輸入形及解決方法式重新輸入數(shù)據(jù)。四、調(diào)試分析