第八章 数论算法及计算几何算法 235
P1' P2'
x1 x0x2 x0
y1 y0y2 y0
(x1 x0) (y2 y0) (x2 x0) (y1 y0)
如果该叉积为正,则P0P1在P0P2的顺时针方向;如果为负,则P0P1在P0P2的逆时针方向;如果为零,则01和02共线。
计算01和02叉积的算法描述如下;
double multiply(POINT P1,POINT P2,POINT P0) {
return ( (P1.x-P0.x)*(P2.y-P0.y)-(P2.x-P0.x)*(P1.y-P0.y) ); }
3.确定两条线段是否相交
针对两条线段是否相交的问题,人们习惯使用平面解析几何的方法来求解。但由于计算过程中使用了三角函数和除法,使得运算代价比较昂贵并且容易产生舍入误差。本节介绍的计算几何算法仅限于加、减、乘和比较运算,因此不可能产生计算误差且算法简洁高效。
算法分两步确定两条线段P1P2和P3P4是否相交。第一步:通过快速排斥实验来确定两条线段是否不相交;第二步:在快速排斥实验判断有可能相交的前提下进行跨立实验,来确定两条线段是否相互跨立。
(1)快速排斥实验——确定两条线段是否不相交。
将包含某线段且四条边分别平行于X轴和Y轴的最小矩形称为界限框。快速排斥实验就是先求出两条线段的界限框,然后判断该界限框有没有可能相交,如果不可能相交,则两条线段肯定不相交;如果两个界限框有可能相交,则两条线段也有可能相交,此时才进行第二步的操作。
线段P1P2的界限框1为:左下角坐标为(min(x1,x2),min(y1,y2)),右上角坐标为(max(x1,x2),max(y1,y2))。
线段P3P4的界限框2为:左下角坐标为(min(x3,x4),min(y3,y4)),右上角坐标为(max(x3,x4),max(y3,y4))。
如果界限框2完全在界限框1的上面,或者完全在界限框1的下面,或者完全在界限框1的左面,或者完全在界限框1的右面均可判定两个界限框不相交。否则,不能确定两个界限框是否相交。
快速排斥实验算法描述:
bool intersect1(LINESEG u,LINESEG v)
{ //max、min分别用于求两者的最大值和最小值
return ((max(u.s.x,u.e.x)<min(v.s.x,v.e.x))|| (max(v.s.x,v.e.x)<min(u.s.x,u.e.x))||
(max(u.s.y,u.e.y)< min(v.s.y,v.e.y))|| (max(v.s.y,v.e.y)<min(u.s.y,u.e.y)));
}
(2)跨立实验——确定两条线段是否相互跨立
快速排斥实验算法intersect1返回true,则认为两条线段不相交;否则,认为有可能相交,则进行跨立实验。所谓跨立是指某线段的两个端点是否分别处于另一线段所在直线的两旁,或者是否有其中一个端点处于另—线段所在的直线上。可以运用叉积方法来确定,其设计思想是从线段u的一个端点向另一条线段v的两个端点引出两条辅助线段,然后分别计算
第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 最大公约数......
热门文档