EaBIM一直以来积极响应国家“十二五”推进建筑业信息化的号召,对建筑领域的信息技术开展深入技术交流和探讨!致力于打造“BIM-建筑师-生态技术”三位一体综合资源交流共享平台,希望为BIM与可持续设计理念及技术的普及做出微小的贡献!!!

EaBIM

 找回密码
 注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
查看: 840|回复: 0
打印 上一主题 下一主题

[计算机图形学] 计算几何算法概论

[复制链接]

1514

主题

7465

帖子

1万

积分

admin

Rank: 10Rank: 10Rank: 10Rank: 10Rank: 10Rank: 10Rank: 10Rank: 10Rank: 10Rank: 10

积分
12408

社区QQ达人

跳转到指定楼层
楼主
发表于 2014-1-9 13:33:21 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式


      then return false;
    点集pointSet初始化为空;
    for 多边形的每条边s
      do if 线段的某个端点在s上
           then 将该端点加入pointSet;
         else if s的某个端点在线段PQ上
           then 将该端点加入pointSet;
         else if s和线段PQ相交 // 这时候已经可以肯定是内交了
           then return false;
    将pointSet中的点按照X-Y坐标排序;
    for pointSet中每两个相邻点 pointSet , pointSet[ i+1]
      do if pointSet , pointSet[ i+1] 的中点不在多边形中
           then return false;
    return true;


  这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n,所以最多是常数级的复杂度,几乎可以忽略不计。因此算法的时间复杂度也是O(n)。

  判断折线是否在多边形内:

  只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段,多边形有n个顶点,则该算法的时间复杂度为O(m*n)。

  判断多边形是否在多边形内:

  只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m*n)。

  判断矩形是否在多边形内:

  将矩形转化为多边形,然后再判断是否在多边形内。

  判断圆是否在多边形内:

  只要计算圆心到多边形的每条边的最短距离,如果该距离大于等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。

  判断点是否在圆内:

  计算圆心到该点的距离,如果小于等于半径则该点在圆内。

  判断线段、折线、矩形、多边形是否在圆内:

  因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。

  判断圆是否在圆内:

  设两圆为O1,O2,半径分别为r1, r2,要判断O2是否在O1内。先比较r1,r2的大小,如果r1<r2则O2不可能在O1内;否则如果两圆心的距离大于r1 - r2 ,则O2不在O1内;否则O2在O1内。

  计算点到线段的最近点:

  如果该线段平行于X轴(Y轴),则过点point作该线段所在直线的垂线,垂足很容易求得,然后计算出垂足,如果垂足在线段上则返回垂足,否则返回离垂足近的端点;如果该线段不平行于X轴也不平行于Y轴,则斜率存在且不为0。设线段的两端点为pt1和pt2,斜率为:k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );该直线方程为:y = k* ( x - pt1.x) + pt1.y。其垂线的斜率为 - 1 / k,垂线方程为:y = (-1/k) * (x - point.x) + point.y 。

  联立两直线方程解得:x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1) ,y = k * ( x - pt1.x) + pt1.y;然后再判断垂足是否在线段上,如果在线段上则返回垂足;如果不在则计算两端点到垂足的距离,选择距离垂足较近的端点返回。

  计算点到折线、矩形、多边形的最近点:

  只要分别计算点到每条线段的最近点,记录最近距离,取其中最近距离最小的点即可。

  计算点到圆的最近距离及交点坐标:

  如果该点在圆心,因为圆心到圆周任一点的距离相等,返回UNDEFINED。

  连接点P和圆心O,如果PO平行于X轴,则根据P在O的左边还是右边计算出最近点的横坐标为centerPoint.x - radius 或 centerPoint.x + radius。如果PO平行于Y轴,则根据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius或 centerPoint.y - radius。如果PO不平行于X轴和Y轴,则PO的斜率存在且不为0,这时直线PO斜率为k = ( P.y - O.y )/ ( P.x - O.x )。直线PO的方程为:y = k * ( x - P.x) + P.y。设圆方程为undefinedx - O.x ) ^2 + ( y - O.y ) ^2 = r ^2,联立两方程组可以解出直线PO和圆的交点,取其中离P点较近的交点即可。

  计算两条共线的线段的交点:

  对于两条共线的线段,它们之间的位置关系有下图所示的几种情况。图(a)中两条线段没有交点;图 (b) 和 (d) 中两条线段有无穷焦点;图 (c) 中两条线段有一个交点。设line1是两条线段中较长的一条,line2是较短的一条,如果line1包含了line2的两个端点,则是图(d)的情况,两线段有无穷交点;如果line1只包含line2的一个端点,那么如果line1的某个端点等于被line1包含的line2的那个端点,则是图(c)的情况,这时两线段只有一个交点,否则就是图(b)的情况,两线段也是有无穷的交点;如果line1不包含line2的任何端点,则是图(a)的情况,这时两线段没有交点。


                               
登录/注册后可看大图

  计算线段或直线与线段的交点:

  设一条线段为L0 = P1P2,另一条线段或直线为L1 = Q1Q2 ,要计算的就是L0和L1的交点。

 1. 首先判断L0和L1是否相交(方法已在前文讨论过),如果不相交则没有交点,否则说明L0和L1一定有交点,下面就将L0和L1都看作直线来考虑。

 2. 如果P1和P2横坐标相同,即L0平行于Y轴

  a) 若L1也平行于Y轴,

    i. 若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
    ii. 否则说明L0和L1平行,他们没有交点;

  b) 若L1不平行于Y轴,则交点横坐标为P1的横坐标,代入到L1的直线方程中可以计算出交点纵坐标;

 3. 如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点横坐标为Q1的横坐标,代入到L0的直线方程中可以计算出交点纵坐标;

 4. 如果P1和P2纵坐标相同,即L0平行于X轴

  a) 若L1也平行于X轴,

    i. 若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
    ii. 否则说明L0和L1平行,他们没有交点;

  b) 若L1不平行于X轴,则交点纵坐标为P1的纵坐标,代入到L1的直线方程中可以计算出交点横坐标;

 5. 如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点纵坐标为Q1的纵坐标,代入到L0的直线方程中可以计算出交点横坐标;

 6. 剩下的情况就是L1和L0的斜率均存在且不为0的情况

  a) 计算出L0的斜率K0,L1的斜率K1 ;

  b) 如果K1 = K2

    i. 如果Q1在L0上,则说明L0和L1共线,假如L1是直线的话有无穷交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
    ii. 如果Q1不在L0上,则说明L0和L1平行,他们没有交点。

  c) 联立两直线的方程组可以解出交点来

  这个算法并不复杂,但是要分情况讨论清楚,尤其是当两条线段共线的情况需要单独考虑,所以在前文将求两条共线线段的算法单独写出来。另外,一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交,如果结果是相交,那么在后面就可以将线段全部看作直线来考虑。需要注意的是,我们可以将直线或线段方程改写为ax+by+c=0的形式,这样一来上述过程的部分步骤可以合并,缩短了代码长度,但是由于先要求出参数,这种算法将花费更多的时间。

  求线段或直线与折线、矩形、多边形的交点:

  分别求与每条边的交点即可。

  求线段或直线与圆的交点:

  设圆心为O,圆半径为r,直线(或线段)L上的两点为P1,P2。

  1. 如果L是线段且P1,P2都包含在圆O内,则没有交点;否则进行下一步。

  2. 如果L平行于Y轴,

   a) 计算圆心到L的距离dis;
   b) 如果dis > r 则L和圆没有交点;
   c) 利用勾股定理,可以求出两交点坐标,但要注意考虑L和圆的相切情况。

  3. 如果L平行于X轴,做法与L平行于Y轴的情况类似;

  4. 如果L既不平行X轴也不平行Y轴,可以求出L的斜率K,然后列出L的点斜式方程,和圆方程联立即可求解出L和圆的两个交点;

  5. 如果L是线段,对于2,3,4中求出的交点还要分别判断是否属于该线段的范围内。

  凸包的概念:

  点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。


                               
登录/注册后可看大图

   
 

  凸包的求法:

  现在已经证明了凸包算法的时间复杂度下界是O(n*logn),但是当凸包的顶点数h也被考虑进去的话,Krikpatrick和Seidel的剪枝搜索算法可以达到O(n*logh),在渐进意义下达到最优。最常用的凸包算法是Graham扫描法和Jarvis步进法。本文只简单介绍一下Graham扫描法,其正确性的证明和Jarvis步进法的过程大家可以参考《算法导论》。

  对于一个有三个或以上点的点集Q,Graham扫描法的过程如下:

  令p0为Q中Y-X坐标排序下最小的点
  设<p1,p2,...pm>为对其余点按以p0为中心的极角逆时针排序所得的点集(如果有多个点有相同的极角,除了距p0最远的点外全部移除
  压p0进栈S
  压p1进栈S
  压p2进栈S
    for i ← 3 to m
      do while 由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧
        对S弹栈
      压pi进栈S
    return S;

 

  此过程执行后,栈S由底至顶的元素就是Q的凸包顶点按逆时针排列的点序列。需要注意的是,我们对点按极角逆时针排序时,并不需要真正求出极角,只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。

四、结语

  尽管人类对几何学的研究从古代起便没有中断过,但是具体到借助计算机来解决几何问题的研究,还只是停留在一个初级阶段,无论从应用领域还是发展前景来看,计算几何学都值得我们认真学习、加以运用,希望这篇文章能带你走进这个丰富多彩的世界。


分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
收藏收藏 转播转播 分享分享 分享淘帖 支持支持 反对反对
工作时间:工作日的9:00-12:00/13:30-18:00,节假日不在线,请勿留言
*滑块验证:
您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|EaBIM网 ( 苏ICP备2020058923号-1  苏公网安备32011502011255号

GMT+8, 2024-11-30 12:13

Powered by Discuz! X3.2 Licensed

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表