算法分析与复杂性理论实验报告凸包问题

1、深圳大学实验报告课程名称：算法分析与复杂性理论实验项目名称:实验三 分治法求凸包问题学院：计算机与软件学院专业：软件工程指导教师:杨恒报告人：文成 学号：2150230509班级:15级软工学术型实验时间： 2015-10-22实验报告提交时间： 2015-10-24教务部制实验目的与要求：实验目的：(1) 掌握分治法思想。(2) 学会凸包问题求解方法。实验要求1 .在blackboard提交电子版实验报告，注意实验报告的书写，整体排版。2 .实验报告的实验步骤部分需详细给出算法思想与实现代码之间的关系解释，不可直接粘贴代码(直接粘贴代码者视为该部分内容缺失)。3 .实验报告样式可从http:

2、//guide.aspx表格下载学生适用在校生管理-实践教学-实验：深圳大学学生实验报告)4 .源代码作为实验报告附件上传。5 .在实验课需要现场运行验证。实验内容:1 .对于平面上给定的 n个点，确定这个点集的凸包，即，输入是平面上的n个点，输出是凸包轮廓。2 .要求随机生成n个点的平面坐标，应用蛮力法编程计算出点集凸包。3 .要求随机生成n个点的平面坐标，应用分治法编程计算出点集凸包。4 . 分别对n=100,1000,10000,100000 ,统计算法运行时间，比较理论效率与实测效率的差异，同时对蛮力法和分治法的算法效率进行分析和比较。注意需要在不同数据量之间增加

3、测试点，例如 10000至ij 100000之间需要增力口 20000、30000ooo ,以分析效率变化 趋势。5 .利用unity 3d输出算法中间结果，直至最后算法计算结果。同时增加help按钮，详细介绍算法原理。实验过程及内容：（实验代码已作为附件提交，名为“算法实验三.cpp”）凸包问题的描述与定义：凸包的定义为：平面的一个子集 s被称为是 凸”的，当且进当对于任意两点 p,qcs, 线段都完全属于 so几何s的凸包ch（s）,就是包含s的最小凸集，更准确地说，它是 包含s的所有凸集的交。由此还可以推出凸包的很多性质，包括一条直线如果与凸包相 交（不是相切）的话，最多交于两条边或者两

4、个面。一组平面上的点，求一个包含所有点的最小凸边形，既是凸包问题。形象地说：在一平木板（平面）上钉若干钉子（点），将一橡皮筋套上去后，会把钉子圈起来，形成一个凸边形，即为该点集的凸包。convexconcave关于用分治法求凸包问题的思路：分治法是一种很基础的算法。基本思路是将问题分解为等价的几个子问题，对子问 题进行递归分解和求解，然后将子问题的解合成为所求的解。由此，可以得到一种最简单的凸包分治算法：将点集依照某种划分方法分为 n部分,对每个部分求子凸包，最后将几个子凸包合成一个更大的凸包。口包问题的分假物第一冽解定点钟的点在触标方肚掘大小排屋如下醐示柳泌定是四多郦的两个顶星第二掂在上凸包

5、殿合同中找到一个距离忸故远点p*,如下图所示。显然直线段pw*与直线段p皿时把点集组分成了三个集合.由 凸包的性质可知同三点围成的三角形中的点不可能作为凸包的顶点，所以只需考虑 直线pirmk左边的点灯以及直线2则以右边的点跄。第三步：递归求解得到凸多边形的边.第四步;合并这些边即得所求凸包,'m凸他问题的分治算法由此就可得到凸包问题的分治算法。stepl :把s中的点按x坐标进行排序step2:划分成两个子集 s1, s2.step3: p1=ch(s1w口 p2=ch(s2).step:合并p1, p2得到解集p.蛮力法解决凸包问题核心代码帅id mmi门(“极力壮弟时.凸包间拼

6、<im w 中 » n;/解认似生成吩随机数irit *x new intis0fl;int *v new lnt1s90;for (int i = 0; i < n; i*) (if ci 1 10 = 0) cout « endl;xi = rarndo - 1g vi = rand() 第 100;cuut « ,a « xi «« vi « h)> cout <c emdl <c end!;int £tart+ end b usbdl;计时器start - uetrickcdu

7、iito;for (i - gw i<n; i*jfor (int j - i + 1s j < n; j* + j <int numl - 0, raura2 - is：for (int k - q; k < n; k*) (判断a秋*恒叫=伫的值if £ft»lb vul mil vj, vfcd < b) rwm"； if (fw1b vi« 肛jl vj, xk, vk)> d) nmk2*«if (i(vl, vj) o)&a i(xte<mn(xip xji)|肛xj)n (nunl

8、*; nwm?4*;)ifkj) - 0)腼(vk<hlncyib vj) (| (vk>hak(fitnubi*; null?*;)if c(f(xl, vll, xjx vj1b xk. vk 0)时 kkk<hln(xir xj» ii <kk>mx(kl, xj») nnn2*;>)内输出满足条件的边if (numl ss 0) 11| (num? =s 9)>cout <y « ki « h.w « yi « 4s).r « kj « ibi" &

9、#171; vj «« endl;end - setlickcduntf);used = end - start;cout « used«enill;，/输出操作时间分治法解决凸包问题核心代码如下:uold dlaiixu(fuint p rinl n)前已经输一斤存同x坐标3 .扫描最后端点元素 相同x坐3.4 .返回。点，点,的点的点都都则加则目uuit) kudihrti pbinl p ,int 1 tinl r)«"p 口 :存放点的捌fl. 1 ,画帧喳台豆搀止坐标/«t mida mux用来干7科即文即'

10、;<fflt1hfloatpoint pnax;int lnun-0;iht ll；ihl hiiiw 肛门ii底瓦l121rl 暂打用下面方式其现prlnttc' 120 n.frt.ff(1 .fbvf)"9*«aiiclfl.xapl.fbpir.i9pr«j) l(l<r)t l：r;inax-(j>r>? j,；r;for(i-i*i;iciba»c;i)xkp .x*pj1 .p .x*pij .y ./p-)q-pirj .xkpij .ji-pl.k«pi.f；lnu唏曜为r；iltmdx = t

11、 ; pndx-pi i 羊圻i正负.lniin*；/lfta tifadk)lnum*;ll-i ：pnhk-pi;if (liiuh>o> printrcan")；dimqdan【。环9dnum*，-pll;"将pll】收入巾点隼kuaiba口fp;klialbaufp ,1 l ,r)；>ns/t=明：,将叩 1、如图所示，分治法实现后的运行程序如下 做一个6个点的测试，"e：k>+p roj ecr®法声韩=gbu g国法妄缝三百"场人点的卞4b 80 10 01 17199-5 -5点中i-5 -5j(-1 1

12、)(0 0)(0 1)(1 d(9 9) 画过祗序；1(一居 h5) (9,9) 边一 z (-5t -5) (-1,1) 边一3 (-1,1)(9, 9) 边一 4 (9t9) (-5,-5)所有功如下二(-5*-5) 一1,1)(-l, 1) 9)(9(9)(-5>-5)所有顶点如1 -m一与19.9)(lt 1)耗时为10毫秒press any key to contimiq理向拼刍理人法学：最终求出3个顶点(-5, -5) (9,9) (-1,1)为正确答案将程序改成随机产生点，只需输入点的个数。输入30个点。最终得到凸包的表边与点。w，十projectx翔=ddxj孙份法安蛉三

13、30an*pwmrri(2 53)(3 11)(5 45)(18 95)(21 16)(22 33)(23 41)(27 36)(29 78)(34 0)(35 94)(37 59)(41 11)(41 67)(47 26)(47 44)(53 68)(61 91)(62 57)(62 64)(67 99)(69 24)(69 12)(71 38)(73 64)搜狗拼音输入法全：数据处理分析：关于蛮力法求凸包问题选择不同的两个点有 c2 = n(n2 丁种选择,对这不同的两个点都要对其他的n-2个点求出a*x+b*y-c的值，即时间效率属于o(n3),输入不同的n观察输出结果的时间，并填入如下

14、表中:n100150200250300350400450500time(s)0.2810.9202.2474.3997.50412.02817.84725.13234.399n550600650700750800850900950time(s)47.56560.95076.42593.928115.41144.00169.63203.81236.65根据上表通过 matlab描点画图可得下图:10d2c0300400500 g0g 700 soo9 口口1000关于分治法求凸包问题本人程序暂有些问题，当点数增大到1000, 10000,后并没有做出来目前只能解决小规模的问题。未采集分治法的时间数据。实验结论：分治法的思想就是将一个规模为 n的问题分解为k个规模较小的子问题， 这些子问 题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问 题的解。蛮力法求凸包问题随着规模的增大，效率会越来越低