第八章 数论算法及计算几何算法 241
{
s= P[min].x*P[max].y+P[i].x*P[min].y+P[max].x*P[i].y
-P[i].x*P[max].y-P[max].x*P[min].y-P[min].x*P[i].y; if(s<smin) {smin=s;b=i;} } if(b!=0) {
printf("(%d,%d)\n",P[b].x,P[b].y); DC2(P,min,b); DC2(P,b,max); } }
8.6最接近点对问题
在计算机应用中,常用诸如点、圆等简单的几何对象描述现实世界的实体,在涉及这些几何对象的问题中,常需要了解其邻域中其它几何对象的信息。例如,一个控制空中或海上交通的系统就需要了解两个最近的交通工具,以预测可能产生的相撞事故。实质上,这就是要找出空间中最接近的一对点问题。因此,研究该问题有很大的实用价值。
最接近点对问题要求给定平面上n个点组成的集合S,找出其中n个点组成的点对中距离最近的一对点。
2
显然,n个点的集合S中共有Cn个点对。很容易想到的算法是通过计算所有这些点对
的距离来找出最近点对。算法的效率直接依赖于n值,n越大,运行时间越长。这种方法实质上是一种穷举搜索策略。
8.6.1最接近点对的穷举搜索法
1.算法思想
假设n个点以直角坐标的形式给出,则点集中的任意两个点Pi(xi,yi)和Pj(xj,yj)的距离为:
dij (xi xj)2 (yi yj)2。分别计算点集中每一对点的距离,从中找出值最小的那对
点。为了避免点对的重复计算,算法只考虑i<j的情况。
2.算法描述
double shortest_dis(POINT p[], int n, POINT & p1, POINT & p2) {
double tempd= ,d=0; for(int i=0;i<n-1; i++) for(int j=i+1; j<n; j++) {
d=sqrt( pow( (p[i].x-p[j].x) ,2 )+pow( (p[i].y-p[j].y) ,2) )
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...
第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...
数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...
第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...
离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...
第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...
[编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...
三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...
224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......
热门文档