238 8.5.1 凸包问题的穷举搜索法
1.算法思想
根据凸多边形的定义可以知道,对于一个由n个点组成的集合S中的任意两个点Pi和Pj,当且仅当该集合中的其它点要么位于穿过Pi和Pj直线的同侧,要么位于线段PiPj上。则线段PiPj是该集合凸多边形边界的一部分。对每一个点都做一遍检验之后,满足条件的线段就构成了该凸包的边界。
2.算法求解步骤
步骤1:对于集合中的任意两点Pi和Pj,定义穿过它们直线方程为:
x xiy yi (8-13)
xj xiyj yi
将式(8-13)整理得到式(8-14)
(yj-yi)x+(xi-xj)y=xiyj-yixj (8-14)
步骤2:这样一根直线把平面分成了两个半平面,一个半平面的点都满足(yj-yi)x+(xi-xj)y-xiyj+yixj>0;另一个半平面的点都满足(yj-yi)x+(xi-xj)y-xiyj+yixj<0;对于线上的点,(yj-yi)x+(xi-xj)y-xiyj+yixj=0。将点集S中的其余点代入(yj-yi)x+(xi-xj)y-xiyj+yixj,然后检查是否异号,如果异号,说明线段PiPj不是点集S的凸多边形的边界。否则,PiPj是凸多边形的边界。
步骤3:对点集中的每个点,重复步骤1和步骤2,直到找出全部多边形的边界。 3.算法描述
void QJ(POINT P[])//数组P用来存放点集 {
int count1=0,count2=0, i=0,j=0;a=0,b=0,c=0,int Y; for( i=0;i<N-1;i++) for(int j=i+1;j<N;j++) {
a=P[j].y-P[i].y;//计算方程中自变量x的系数 }
b=P[i].x-P[j].x; //计算方程中自变量y的系数 for(k=0;k<N;k++) } {
if( (k==j)||(k==i) ) continue; Y=a*P[k].x+b*P[k].y-c;
if(Y>0) count1++;//统计在其中一个半平面的点的个数 if(Y<0) count2++;//统计在另一个半平面的点的个数 }
printf("(%d,%d),(%d,%d)\n",x[i],y[i],x[j],y[j]); count1=0; count2=0;
if(Y=0) break;//不处理,跳出循环
c=P[i].x*P[j].y-P[i].y*P[j].x; //计算方程中常数项的值
if((count1==(N-2))||(count2==(N-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 最大公约数......
热门文档