蚂蚁文库
换一换
首页 蚂蚁文库 > 资源分类 > PDF文档下载
 

计算几何常用算法概览

  • 资源ID:55710355       资源大小:477.63KB        全文页数:22页
  • 资源格式: PDF        下载权限:游客/注册会员    下载费用:10积分 【人民币10元】
快捷注册下载 游客一键下载
会员登录下载
三方登录下载: 微信快捷登录 QQ登录  
下载资源需要10积分 【人民币10元】
邮箱/手机:
温馨提示:
支付成功后,系统会自动生成账号(用户名和密码都是您填写的邮箱或者手机号),方便下次登录下载和查询订单;
支付方式: 微信支付    支付宝   
验证码:   换一换

 
友情提示
2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

计算几何常用算法概览

计算几何常用算法概览计算几何常用算法概览 本站原创怒火之袍 一、引言一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化, 但是也有 一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方 案,比如几何问题。作为计算机科学的一个分支,计算几何主要研究解决 几何问题的算法。在现代工程和数学领域,计算几何在图形学、机器人技 术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本 文中,我们将对计算几何常用的基本算法做一个全面的介绍,希望对您了 解并应用计算几何的知识解决问题起到帮助。 二、目录二、目录 本文整理的计算几何基本概念和常用算法包括如下内容 矢量的概念 三、算法介绍三、算法介绍 矢量的概念矢量的概念 1 / 22 如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段 directed segment。如果有向线段 p1p2 的起点 p1 在坐标原点,我们可以把 它称为矢量vectorp2。 矢量加减法矢量加减法 设二维矢量 P x1,y1 ,Q x2 , y2 ,则矢量加法定义为 P Q x1 x2 , y1 y2 , 同样的, 矢量减法定义为P - Q x1 - x2 , y1 - y2 。 显然有性质 P Q Q P , P - Q - Q - P 。 矢量叉积矢量叉积 计算矢量叉积是与直线和线段相关算法的核心部分。设矢量 P (x1,y1) ,Q x2,y2,则矢量叉积定义为由0,0、p1、p2 和 p1p2 所 组成的平行四边形的带符号的面积,即P Q x1*y2 - x2*y1,其结果 是一个标量。显然有性质 P Q - Q P 和 P - Q - P Q 。一般在不加说明的情况下,本文下述算法中所有的点都看作矢量,两 点的加减法就是矢量相加减,而点的乘法则看作矢量叉积。 叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的 顺逆时针关系 若 P Q 0 , 则 P 在 Q 的顺时针方向。 若 P Q 0,则 p0p1 在 p1 点拐向右侧后得到 p1p2。 若p2 - p0 p1 - p0 0。同理判断 Q1Q2 跨立 P1P2 的 依据是 Q1 - P1 P2 - P1 * P2 - P1 Q2 - P1 0。具体情 况如下图所示 在相同的原理下,对此算法的具体的实现细节可能会与此有所不同,除 了这种过程外,大家也可以参考算法导论上的实现。 判断线段和直线是否相交判断线段和直线是否相交 有了上面的基础,这个算法就很容易了。如果线段 P1P2 和直线 Q1Q2 相交,则 P1P2 跨立 Q1Q2,即 P1 - Q1 Q2 - Q1 * Q2 - Q1 P2 - Q1 0。 判断矩形是否包含点判断矩形是否包含点 6 / 22 只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。 判断线段、折线、多边形是否在矩形中判断线段、折线、多边形是否在矩形中 因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。 判断矩形是否在矩形中判断矩形是否在矩形中 只要比较左右边界和上下边界就可以了。 判断圆是否在矩形中判断圆是否在矩形中 很容易证明,圆在矩形中的充要条件是圆心在矩形中且圆的半径小于 等于圆心到矩形四边的距离的最小值。 判断点是否在多边形中判断点是否在多边形中 判断点 P 是否在多边形中是计算几何中一个非常基本但是十分重要的 算法。以点 P 为端点,向左方作射线 L,由于多边形是有界的,所以射线 L 的左端一定在多边形外,考虑沿着 L 从无穷远处开始自左向右移动,遇 到和多边形的第一个交点的时候,进入到了多边形的内部,遇到第二个交 点的时候,离开了多边形,所以很容易看出当 L 和多边形的交点数目 C 是奇数的时候,P 在多边形内,是偶数的话 P 在多边形外。 但是有些特殊情况要加以考虑。如图下图abcd所示。在图a中, L 和多边形的顶点相交,这时候交点只能计算一个;在图b中,L 和多边 7 / 22 形顶点的交点不应被计算;在图c和d 中,L 和多边形的一条边重合, 这条边应该被忽略不计。如果 L 和多边形的一条边重合,这条边应该被忽 略不计。 为了统一起见,我们在计算射线 L 和多边形的交点的时候,1。对于多 边形的水平边不作考虑;2。对于多边形的顶点和 L 相交的情况,如果该顶 点是其所属的边上纵坐标较大的顶点,则计数,否则忽略; 3。对于P 在多 边形边上的情形, 直接可判断 P 属于多边行。 由此得出算法的伪代码如下 8 / 22 count ← 0; 以 P 为端点,作从右向左的射线 L; for 多边形的每条边 s do if P 在边 s 上 then return true; if s 不是水平的 then if s 的一个端点在 L 上 if 该端点是 s 两端点中纵坐标较大的端点 then count ← count1 else if s 和 L 相交 then count ← count1; if count mod 2 1 then return true; else return false; 其中做射线 L 的方法是设 P的纵坐标和 P 相同,横坐标为正无穷大 (很大的一个正数),则 P 和 P就确定了射线 L。 判断点是否在多边形中的这个算法的时间复杂度为 On。 9 / 22 另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比 较,这种算法由于使用浮点数运算所以会带来一定误差,不推荐大家使用。 判断线段是否在多边形内 线段在多边形内的一个必要条件是线段的两个端点都在多边形内, 但由 于多边形可能为凹,所以这不能成为判断的充分条件。如果线段和多边形 的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点), 因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有 一部分在多边形外见图 a。 于是我们得到线段在多边形内的第二个必要条 件线段和多边形的所有边都不内交。 线段和多边形交于线段的两端点并不会影响线段是否在多边形内; 但是 如果多边形的某个顶点和线段相交,还必须判断两相邻交点之间的线段是 否包含于多边形内部(反例见图 b。 10 / 22 因此我们可以先求出所有和线段相交的多边形的顶点,然后按照 X-Y 坐标排序X 坐标小的排在前面,对于 X 坐标相同的点,Y 坐标小的排在前 面,这种排序准则也是为了保证水平和垂直情况的判断正确,这样相邻的 两个点就是在线段上相邻的两交点,如果任意相邻两点的中点也在多边形 内,则该线段一定在多边形内。 证明如下 命题 1 如果线段和多边形的两相邻交点 P1 ,P2 的中点 P 也在多边形内,则 P1, P2 之间的所有点都在

注意事项

本文(计算几何常用算法概览)为本站会员(sunhongz120)主动上传,蚂蚁文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知蚂蚁文库(发送邮件至2303240369@qq.com或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们


网站客服QQ:2303240369

copyright@ 2017-2027 mayiwenku.com 

网站版权所有  智慧蚂蚁网络

经营许可证号:ICP备2024020385号



收起
展开