首页 / 算法 / 关于算法--蛮力法--最近对和凸包问题
关于算法--蛮力法--最近对和凸包问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了关于算法--蛮力法--最近对和凸包问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1536字，纯文字阅读大概需要3分钟。
内容图文
一、最近对问题：即从一个二维或多位的空间中找出距离最近的两个点
1、步骤
a、分别计算每一对点之间的距离
b、找出距离最近的那一对
（为了避免重复计算，只考虑i<j的那些对）
2、JavaScript实现
1 <!DOCTYPE html>
2 <html lang="en">
3 <head>
4 <meta charset="UTF-8">
5 <title>最近对问题</title>
6 </head>
7 <body>
8 9 </body>
10 <script type="text/javascript">
11var point = function(x, y) {
12var _arr = new Array();
13 _arr = [x, y];
14 _arr.x = x;
15 _arr.y = y;
16return _arr;
17 }
1819var caculate = function(p1, p2) {
20return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
21 }
2223function search(arr) {
24var dis = Number.POSITIVE_INFINITY;
25var indexX = null;
26var indexY = null;
27for(var i = 0; i < arr.length - 1; i++){
28for(var j = i+1; j < arr.length; j++){
29var d = caculate(arr[i], arr[j]);
30if(d < dis){
31 dis = d;
32 indexX = i;
33 indexY = j;
34 }
35 }
36 }
37return "第 "+indexX+" 个点和第 "+indexY+" 个点之间的距离最近";
38 }
3940//实验阶段41//创建四个点坐标分别为(0,0),(2,0),(0,3),(2,1)42var p1 = new point(0,0);
43var p2 = new point(2,0);
44var p3 = new point(0,3);
45var p4 = new point(2,1);
46 console.log(search([p1, p2, p3, p4]))
47 </script>
48 </html>
3、算法分析
可使用(Xi - Xj)2 +(Yi - Yj)2代替sqrt((Xi - Xj)2 +(Yi - Yj)2)，尽量避免开方；所以本算法的基本操作是求平方，执行次数C(n) = Σ[i=1 to n-1]Σ[j=i+1 to n] 2 = n(n - 1)，属于Θ(n2)
一、凸包问题
1、凸集合概念：对于平面上一个点集合，如果以集合中任意两点P和Q未断电的线段，均属于该集合，则集合是凸的
2、凸包：凸包是包含所有点的最小凸集合
3、一般判断方法：判断是否所有其他点都在连接P1和P2的直线同一侧
4、一般时间效率：它属于Θ(n3)；对于不同的点的每一个n(n-1)/2，都要比较其它n-2个点的符号
原文：http://www.cnblogs.com/likaopu/p/5679297.html
内容总结
以上是互联网集市为您收集整理的关于算法--蛮力法--最近对和凸包问题全部内容，希望文章能够帮你解决关于算法--蛮力法--最近对和凸包问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。