`
ibadboy
  • 浏览: 83792 次
  • 性别: Icon_minigender_1
  • 来自: 江苏
社区版块
存档分类
最新评论

平面图形之几何算法研究

    博客分类:
  • java
 
阅读更多
转载自: http://blog.csdn.net/orbit/article/details/7082678

我的专业是计算机辅助设计(CAD),算是一半机械一半软件,《计算机图形学》是必修课,也是我最喜欢的课程。热衷于用代码摆平一切的我几乎将这本教科书上的每种算法都实现了一遍,这种重复劳动虽然意义不大,但是收获很多,特别是丢弃了多年的数学又重新回到了脑袋中,算是最大的收获吧。尽管已经毕业多年了,但是每次回顾这些算法的代码,都觉得内心十分澎湃,如果换成现在的我,恐怕再也不会有动力去做这些事情了。

        在学习《计算机图形学》之前,总觉得很多东西高深莫测,但实际掌握了之后,却发现其中了无神秘可言,就如同被原始人像神一样崇拜的火却被现代人叼在嘴上玩弄一样的感觉。图形学的基础之一就是计算几何,但是没有理论数学那么高深莫测,它很有实践性,有时候甚至可以简单到匪夷所思。计算几何是随着计算机和CAD的应用而诞生的一门新兴学科,在国外被称为“计算机辅助几何设计(Computer Aided Geometric Design,CAGD)”。“算法系列”接下来的几篇文章就会介绍一些图形学中常见的计算几何算法(顺便晒晒我的旧代码),都是一些图形学中的基础算法,需要一些图形学的知识和数学知识,但是都不难。不信?那就来看看到底有多难。

        本文是第一篇,主要是一些图形学常用的计算几何方法,涉及到向量、点线关系以及点与多边形关系求解等数学知识,还有一些平面几何的基本原理。事先声明一下,文中涉及的算法实现都是着眼于解释原理以及揭示算法实质的目的,在算法效率和可读性二者的考量上,更注重可读性,有时候为了提高可读性会刻意采取“效率不高”的代码形式,实际工程中使用的代码肯定更紧凑更高效,但是算法原理都是一样的,请读者们对此有正确的认识。



一、        判断点是否在矩形内



        计算机图形学和数学到底有什么关系?我们先来看几个例子,增加一些感性认识。首先是判断一个点是否在矩形内的算法,这是一个很简单的算法,但是却非常重要。比如你在一个按钮上点击鼠标,系统如何知道你要触发这个按钮对应的事件而不是另一个按钮?对了,就是一个点是否在矩形内的判断处理。Windows 的API提供了PtInRect()函数,实现方法其实就是判断点的x坐标和y坐标是否同时落在矩形的x坐标范围和y坐标范围内,算法实现也很简单:

  150 bool IsPointInRect(const Rect& rc, const Point& p)
  151 {
  152     double xr = (p.x - rc.p1.x) * (p.x - rc.p2.x);
  153     double yr = (p.y - rc.p1.y) * (p.y - rc.p2.y);
  154
  155     return ( (xr <= 0.0) && (yr <= 0.0) );
  156 }
看看IsPointInRect()函数的实现是否和你想象的不一样?有时候硬件实现乘法有困难或受限制于CPU乘法指令的效率,可以考虑用下面的函数替换,代码繁琐了一点,但是避免了乘法运算:

  120 bool IsPointInRect(const Rect& rc, const Point& p)
  121 {
  122     double xl,xr,yt,yb;
  123
  124     if(rc.p1.x < rc.p2.x)
  125     {
  126         xl = rc.p1.x;
  127         xr = rc.p2.x;
  128     }
  129     else
  130     {
  131         xl = rc.p2.x;
  132         xr = rc.p1.x;
  133     }
  134
  135     if(rc.p1.y < rc.p2.y)
  136     {
  137         yt = rc.p2.y;
  138         yb = rc.p1.y;
  139     }
  140     else
  141     {
  142         yt = rc.p1.y;
  143         yb = rc.p2.y;
  144     }
  145
  146     return ( (p.x >= xl && p.x <= xr) && (p.y >= yb && p.y <= yt) );
  147 }
由于IsPointInRect()函数并不假设矩形的两个定点是按照坐标轴升序排列的,所以算法实现时就考虑了所有可能的坐标范围。IsPointInRect()函数使用的是平面直角坐标系,如果不特别说明,本文所有的算法都是基于平面直角坐标系设计的。另外,IsPointInRect()函数没有指定特别的浮点数精度范围,默认是系统浮点数的最大精度,只在某些必须要与0比较的情况下,采用10-8次方精度,如无特别说明,本文的所有算法都这样处理。

一、        判断点是否在圆内



        现在考虑复杂一点,如果图形界面的按钮不是矩形而是圆形的怎么办呢?当然就是判断点是否在圆内部。判断算法的原理就是计算点到圆心的距离d,然后与圆半径r进行比较,若d < r则说明点在圆内,若d = r则说明点在圆上,若d > r则说明点在圆外。这就要提到计算平面上两点距离的算法。以下图为例,计算平面上任意两点之间的距离主要依据著名的勾股定理:



图1 平面两点距离计算示意图

  113 //计算欧氏几何空间内平面两点的距离
  114 double PointDistance(const Point& p1, const Point& p2)
  115 {
  116     return std::sqrt( (p1.x-p2.x)*(p1.x-p2.x)
  117                         + (p1.y-p2.y)*(p1.y-p2.y) );
  118 }


一、        判断点是否在多边形内



        现在再考虑复杂一点的,如果按钮是个不规则的多边形区域怎么办?别以为这个考虑没有意义,很多多媒体软件和游戏,通常都是用各种形状的不规则图案作为热点(Hot Spot),Windows也提供了PtInRegion() API,用于判断点是否在一个不规则区域中。我们对问题做一个简化,就判断一个点是否在多边形内?判断点P是否在多边形内是计算几何中一个非常基本的算法,最常用的方法是射线法。以P点为端点,向左方做射线L,然后沿着L从无穷远处开始向P点移动,当遇到多边形的某一条边时,记为与多边形的第一个交点,表示进入多边形内部,继续移动,当遇到另一个交点时,表示离开多边形内部。由此可知,当L与多边形的交点个数是偶数时,表示P点在多边形外,当L与多边形交点个数是奇数时,表示P点在多边形内部。

        由此可见,要实现判断点是否在多边形内的算法,需要知道直线段求交算法,而求交算法又涉及到矢量的一些基本概念,因此在实现这个算法之前,先讲一下矢量的基本概念以及线段求交算法。



3.1 矢量的基础知识

         什么是矢量?简单地讲,就是既有大小又有方向的量,数学中又常被称为向量。矢量有几何表示、代数表示和坐标表示等多种表现形式,本文讨论的是几何表示。如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段(Directed Segment),比如线段P1P2,如果起始端点P1就是坐标原点(0, 0),P2的坐标是(x, y),则线段P1P2的二维矢量坐标表示就是P= (x, y)。



3.2 矢量的加法和减法

         现在来看几个与矢量有关的重要概念,首先是矢量的加减法。假设有二维矢量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 )



图2 演示了矢量加法和减法的几何意义,由于几何中直线段的两个点不可能刚好在原点,因此线段P1P2的矢量其实就是OP2 - OP1的结果,如图2 (b)所示:



3.3 矢量的叉积(外积)

         另一个比较重要的概念是矢量的叉积(外积)。计算矢量的叉积是判断直线和线段、线段和线段以及线段和点的位置关系的核心算法。假设有二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则矢量的叉积定义为:



P × Q = x1*y2 - x2*y1



向量叉积的几何意义可以描述为由坐标原点(0,0)、P、Q和P + Q所组成的平行四边形的面积,而且是个带符号的面积,由此可知,矢量的叉积具有以下性质:



P × Q = - ( Q × P )



叉积的结果P × Q是P和Q所在平面的法矢量,它的方向是垂直与P和Q所在的平面,并且按照P、Q和P × Q的次序构成右手系,所以叉积的另一个非常重要性质是可以通过它的符号可以判断两矢量相互之间位置关系是顺时针还是逆时针关系,具体说明如下:



1) 如果 P × Q > 0 , 则Q在P的逆时针方向;

2) 如果 P × Q < 0 , 则Q在P的顺时针方向;

3) 如果 P × Q = 0 , 则Q与P共线(但可能方向是反的);



3.4 矢量的点积(内积)

         最后要介绍的概念是矢量的点积(内积)。假设有二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则矢量的点积定义为:



P·Q = x1*x2 + y1*y2



向量点积的结果是一个标量,它的代数表示是:



P·Q = |P| |Q| cos(P, Q)



(P, Q) 表示向量P和Q的夹角,如果P和Q不共线,则根据上式可以得到向量点积的一个非常重要的性质,具体说明如下:



1) 如果 P · Q > 0 , 则P和Q的夹角是钝角(大于90度);

2) 如果 P · Q < 0 , 则P和Q的夹角是锐角(小于90度);

3) 如果 P · Q = 0 , 则P和Q的夹角是90度;



        了解了矢量的概念以及矢量的各种运算的几何意义和代数意义后,就可以开始解决各种计算几何的简单问题了,回想本文开始提到的点与多边形的关系问题,首先要解决的就是判断点和直线段的位置关系问题。



3.5 用矢量的叉积判断点和直线的关系



        根据矢量叉积的几何意义,如果线段所表示的矢量和点的矢量的叉积是0,就说明点在线段所在的直线上,相对于坐标原点O来说,线段的矢量其实就是线段终点P2=[x2, y2]的矢量OP2减线段起点P1=[x1, y1]的矢量OP1的结果,因此线段P1P2的矢量可以表示为P1P2=(x2 – x1, y2 – y1)。如果要判断点P是否在线段P1P2上,就要判断矢量P1P2和矢量OP的叉积是否是0。需要注意的是,叉积为0只能说明点P与线段P1P2所在的直线共线,并不能说明点P一定会落在P1P2区间上,因此只是一个必要条件。要正确判断P在线段P1P2上,还需要做一个排斥试验,就是检查点P是否在以直线段为对角线的矩形空间内,如果以上两个条件都为真,即可判定点在线段上。有了上述原理,算法实现就比较简单了,以下就是判断点是否在线段上的算法:

  174 bool IsPointOnLineSegment(const LineSeg& ls, const Point& pt)
  175 {
  176     Rect rc;
  177
  178     GetLineSegmentRect(ls, rc);
  179     double cp = CrossProduct(ls.pe.x - ls.ps.x, ls.pe.y - ls.ps.y,
  180                              pt.x - ls.ps.x, pt.y - ls.ps.y); //计算叉积
  181
  182     return ( (IsPointInRect(rc, pt)) //排除实验
  183              && IsZeroFloatValue(cp) ); //1E-8 精度
  184 }
  185
分享到:
评论

相关推荐

    计算几何算法与应用计算几何算法与应用

    9. **几何算法分析**:复杂度理论是计算几何不可或缺的部分,需要了解和评估算法的时间复杂度和空间复杂度。 10. **应用领域**:计算几何广泛应用于图形学、GIS(地理信息系统)、CAD(计算机辅助设计)、机器人...

    计算几何算法和实现.pdf

    ### 计算几何算法与实现的关键知识点 #### 一、计算几何概述 计算几何是计算机科学的一个分支领域,主要研究如何用计算机有效地处理几何对象及其性质。这些对象通常包括点、线、多边形等基本几何元素。计算几何在...

    计算几何算法与应用(中文第三版高清目录)

    3. **平面几何算法**:这部分内容涵盖直线、射线、圆、圆弧的相交检测,点在多边形内的判断,以及凸包和凹包算法,如 Graham 扫描和 Jarvis 走步算法。 4. **几何数据结构**:包括kd树、Voronoi图、Delaunay三角...

    计算机图形学裁剪算法

    总的来说,计算机图形学中的裁剪算法是图形处理的关键技术之一,它涉及到几何学、线性代数、坐标变换等多个数学领域,是计算机图形学理论和实践的基础。理解和掌握这些算法对于从事图形相关的软件开发至关重要。

    论文研究-基于坐标变换的图形自适应排列算法.pdf

    为了解决基于网格技术的图形排列算法在处理可变尺寸图形排列问题上的局限性,基于几何变换思想,建立了有界平面上图形自适应排列的数学模型,并证明了其正确性,进而提出了基于坐标变换的图形自适应排列算法。此算法...

    论文研究-基于平面几何图形的立体浮雕建模技术.pdf

    针对具有复杂曲面的艺术类浮雕建模问题,提出一种基于平面几何图形的解决方案。首先由二维区域和截面形状定义出浮雕曲面,浮雕则采用Z-MAP栅格在计算机内离散表示;然后把多个浮雕曲面通过六种可选方式融合成具有...

    计算几何算法

    计算几何算法是计算机科学中的一个重要领域,主要研究如何用算法解决几何问题。这些算法通常涉及到二维和三维空间中的点、线、面等几何对象的操作。在这个话题中,我们看到一些核心概念和函数,它们用于处理几何对象...

    计算机图形学图象几何变换

    在“三维图形几何变换.doc”文档中,可能会详细阐述上述变换的数学原理、算法实现以及在实际应用中的案例分析。对于学习和掌握计算机图形学的读者来说,这份文档将提供宝贵的知识资源。通过深入学习,你可以理解如何...

    计算几何算法 编程 acm

    9. **图形渲染**:计算几何算法也用于图形渲染,如光线追踪、阴影计算等,这些都是现代计算机图形学的基础。 10. **算法设计技巧**:如旋转卡壳、扫线算法、桶排序等,这些技巧在解决特定几何问题时非常有效。 在...

    计算几何算法与应用(pdf)

    计算几何是计算机科学的一个分支,主要研究如何使用算法处理几何问题,这些问题在图形学、地理信息系统、机器人学以及工程设计等多个领域都有广泛应用。 书中首先会介绍基础的几何概念,如点、线、面以及它们之间的...

    2D图形学交互算法VC代码

    在计算机科学领域,2D图形学是研究如何在二维平面上表示、操作和交互图形的技术。这个主题通常涉及几何形状的构建、变换、渲染以及与用户的交互。在给定的"2D图形学交互算法VC代码"中,我们可以期待看到一系列使用...

    计算几何--算法与应用(第2版)(中文版).rar

    7. **几何算法**:包括经典的平面扫描算法(如Dijkstra最短路径算法、Flood Fill填充算法)、voronoi图的构建、 delaunay三角剖分等。这些算法在计算机图形学、地理信息系统和机器学习中都有广泛应用。 8. **应用...

    计算几何——算法分析与设计

    4. 几何查询:如最近点查询、距离计算、交点检测等,这些查询是许多几何算法的核心。 5. 几何构造:包括曲线和曲面的构造,如贝塞尔曲线、B样条曲线和NURBS(非均匀有理B样条)曲面。 6. 几何优化:如何找到最优解...

    几何算法源码(包括多边形填充算法, 多边形裁剪算法

    几何算法在计算机图形学中占有重要地位,它们广泛应用于游戏开发、图像处理、地图渲染、CAD设计等多个领域。本资源包含的源码着重于多边形填充算法和多边形裁剪算法,这些都是构建2D图形系统的基础部分。 首先,...

    我收集的电子书 计算几何--算法与应用(第2版)(中文版).pdf

    工具部分可能涉及到使用计算几何算法的软件库,如CGAL(Computational Geometry Algorithms Library)和Qhull等,这些库提供了丰富的几何算法接口,简化了开发过程。 总的来说,《计算几何--算法与应用(第2版)...

    计算机图形学 裁剪算法

    计算机图形学是信息技术领域的一个重要分支,主要研究如何在计算机中表示、生成和处理图形。在实际应用中,我们经常需要对图形进行裁剪,以便只显示感兴趣的部分或适应特定的显示区域。"裁剪算法"是计算机图形学中的...

    计算几何——算法分析与设计.rar

    计算几何是计算机科学的一个重要分支,它涉及到数学、图形学和算法等多个领域的交叉,主要研究如何用算法来解决几何问题。这个"计算几何——算法分析与设计.rar"压缩包很可能包含了一系列关于计算几何核心算法的详细...

    计算几何 (李澎煦/朱泽园)

    计算几何是计算机科学的一个重要分支,它涉及到数学和计算机图形学的交叉领域,主要研究如何用算法解决几何问题。在本资料中,我们重点关注的是半平面交算法,这是计算几何中的一个基础且实用的问题。 半平面交问题...

Global site tag (gtag.js) - Google Analytics