精华内容
下载资源
问答
  • 计算几何算法和实现.pdf
  • 计算机几何算法总结

    千次阅读 2019-01-28 10:08:43
    计算几何算法概览 一、引言  计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案,比如几何问题。作为计算机...

     

    转自:http://dev.gameres.com/Program/Abstract/Geometry.htm

    计算几何算法概览


    一、引言

      计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案,比如几何问题。作为计算机科学的一个分支,计算几何主要研究解决几何问题的算法。在现代工程和数学领域,计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中,我们将对计算几何常用的基本算法做一个全面的介绍,希望对您了解并应用计算几何的知识解决问题起到帮助。

    二、目录

      本文整理的计算几何基本概念和常用算法包括如下内容:

      矢量的概念

     矢量加减法

     矢量叉积

     折线段的拐向判断

     判断点是否在线段上

     判断两线段是否相交

     判断线段和直线是否相交

     判断矩形是否包含点

     判断线段、折线、多边形是否在矩形中

     判断矩形是否在矩形中

     判断圆是否在矩形中

     判断点是否在多边形中

     判断线段是否在多边形内

     判断折线是否在多边形内

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

     判断矩形是否在多边形内

     判断圆是否在多边形内

     判断点是否在圆内

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

     判断圆是否在圆内

     计算点到线段的最近点

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

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

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

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

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

     求线段或直线与圆的交点

     凸包的概念

     凸包的求法

    三、算法介绍

      矢量的概念

      如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点,我们可以把它称为矢量(vector)p2。

     矢量加减法

     设二维矢量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和p1+p2所组成的平行四边形的带符号的面积,即:P × Q = x1*y2 - x2*y1,其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下,本文下述算法中所有的点都看作矢量,两点的加减法就是矢量相加减,而点的乘法则看作矢量叉积。

      叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:

     若 P × Q > 0 , 则P在Q的顺时针方向。
      若 P × Q < 0 , 则P在Q的逆时针方向。
      若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向。

     折线段的拐向判断

     折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2,通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向:

     若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

     若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

     若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。

     具体情况可参照下图:

        

     判断点是否在线段上

     设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内。前者保证Q点在直线P1P2上,后者是保证Q点不在线段P1P2的延长线或反向延长线上,对于这一步骤的判断可以用以下过程实现:

     ON-SEGMENT(pi,pj,pk)

     if min(xi,xj) <= xk <= max(xi,xj) and min(yi,yj) <= yk <= max(yi,yj)

     then return true;

     else return false;

     特别要注意的是,由于需要考虑水平线段和垂直线段两种特殊情况,min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)两个条件必须同时满足才能返回真值。

     判断两线段是否相交

     我们分两步确定两条线段是否相交:

     (1)快速排斥试验

       设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相交,显然两线段不会相交。

     (2)跨立试验

        如果两线段相交,则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ,则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧,即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线,但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 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。

     判断矩形是否包含点

     只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。

        
      判断线段、折线、多边形是否在矩形中

     因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。

     判断矩形是否在矩形中

     只要比较左右边界和上下边界就可以了。

     判断圆是否在矩形中

     很容易证明,圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。

     判断点是否在多边形中

     判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。

     但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中,L和多边形的顶点相交,这时候交点只能计算一个;在图(b)中,L和多边形顶点的交点不应被计算;在图(c)和(d) 中,L和多边形的一条边重合,这条边应该被忽略不计。如果L和多边形的一条边重合,这条边应该被忽略不计。

        

     为了统一起见,我们在计算射线L和多边形的交点的时候,1。对于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判断P属于多边行。由此得出算法的伪代码如下:

        count ← 0;
        以P为端点,作从右向左的射线L; 
        for 多边形的每条边s
         do if P在边s上 
              then return true;
            if s不是水平的
              then if s的一个端点在L上
                     if 该端点是s两端点中纵坐标较大的端点
                       then count ← count+1
                   else if s和L相交
                     then count ← count+1;
        if count mod 2 = 1 
          then return true;
        else return false;


      其中做射线L的方法是:设P'的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),则P和P'就确定了射线L。

     判断点是否在多边形中的这个算法的时间复杂度为O(n)。

     另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较,这种算法由于使用浮点数运算所以会带来一定误差,不推荐大家使用。

     判断线段是否在多边形内

     线段在多边形内的一个必要条件是线段的两个端点都在多边形内,但由于多边形可能为凹,所以这不能成为判断的充分条件。如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点),因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边形外(见图a)。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交。

     线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个顶点和线段相交,还必须判断两相邻交点之间的线段是否包含于多边形内部(反例见图b)。

        

     因此我们可以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序(X坐标小的排在前面,对于X坐标相同的点,Y坐标小的排在前面,这种排序准则也是为了保证水平和垂直情况的判断正确),这样相邻的两个点就是在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形内。

     证明如下:
     

     命题1:
        如果线段和多边形的两相邻交点P1 ,P2的中点P' 也在多边形内,则P1, P2之间的所有点都在多边形内。
        

     证明:
        假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P'之间,因为多边形是闭合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P'属于多边性内部,P1-Q-P'完全连续,所以P1Q和QP'一定跨越多边形的边界,因此在P1,P'之间至少还有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕。

     由命题1直接可得出推论:
      推论2:
        设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多边形内。

      在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段上就可以了。

      至此我们得出算法如下:

        if 线端PQ的端点不都在多边形内 
          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[i] , pointSet[ i+1]
          do if pointSet[i] , 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。设圆方程为:(x - 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的凸包顶点按逆时针排列的点序列。需要注意的是,我们对点按极角逆时针排序时,并不需要真正求出极角,只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。

    四、结语

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

    展开全文
  • 计算几何算法概览

    2015-03-25 19:07:20
    计算几何算法概览 超全的计算几何的算法啊。。。。真是老牛啊。。。。 http://dev.gameres.com/Program/Abstract/Geometry.htm http://dev.gameres.com/Program/Abstract/Geometry.htm ...

    计算几何算法概览
    超全的计算几何的算法啊。。。。真是老牛啊。。。。
    http://dev.gameres.com/Program/Abstract/Geometry.htm
    http://dev.gameres.com/Program/Abstract/Geometry.htm
    http://dev.gameres.com/Program/Abstract/Geometry.htm

    展开全文
  • 算法:计算机几何算法

    千次阅读 2008-03-27 20:58:00
    这里讨论计算机2D空间内的一些几何算法。讨论的主题包括:两条线段之间的方向、折线在某个顶点上的转向、点是否在线段上的判定、线段是否相交的判定、凸包、给定点组成的多边形是否构成凸多边形的判定、凸多边形面积...
            这里讨论计算机2D空间内的一些几何算法。讨论的主题包括:两条线段之间的方向、折线在某个顶点上的转向、点是否在线段上的判定、线段是否相交的判定、凸包、给定点组成的多边形是否构成凸多边形的判定、凸多边形面积的计算以及判断点是否在一个多边形(包括凹凸两种多边形) 当中的算法。
            在讨论这些主题之前,首先确定点在计算机内的表示使用一个数对(整数或者浮点数,看具体需求)<X,Y>来表示,而线段使用线段的两个端点来表示。在后面的所有主题讨论之中我们经常会用到一个几何术语:叉积,具体的几何意义表示由两个向量及其平移得到的向量围城的平行四边形的面积,而其算法是这样表示的:向量a=(x1,y1)向量b=(x2,y2),叉积a×b=x1*y2 + x2*y1;为了这些主题讨论的方便线段l我们有时也会表示成向量,表示的方法是:假设线段l上的两个端点p1(x1,y1),p2(x2,y2)那么表示出来的向量p1p2=(x2-x1,y2-y1)。
    一、两条线段的方向
            这个主题要求的就是线段l2在给定线段l1的顺时针或者逆时针方向上。正如上面所说的,我们把两条线段表示成向量的方式,这样转化而来的向量都以共同顶点原点为出发点。这样我们求得两个向量的叉积m,如果m<0说明线段l2在线段l1的逆时针方向上;m>0说明在顺时针方向上;m==0表示两条线段共线。
    二、折线在某个顶点上的转向
            假设折线上依次有点p1、p2、p3,求在顶点p2上折线是向左转或者向右转。如图:
            显然如果我们要求在P2点上的折向我们只需要把P1、P2、P3表示成第二张图上红色部分表示的两个向量P1P2和P1P3,如果向量P1P3在向量P1P2的顺时针方向那么在P2点上就是向右转,否则就是左转,而判断两个向量(或者线段)方向的算法就是第一个主题当中提到的内容。
    三、点在线段上的判断
            点是否在线段上的判断有两种方式,第一种计算出线段的方程然后判断,但是这种方式当中由于存在大量除法运算,因此不但效率较差而且存在着精度的问题。而另一种判断方式则是,设线段l上两个顶点p1p2,要求判断的点为p3,我们前面讲到过如果两个向量的叉积为0那么两个向量共线,因此我们首先判断向量p1p3和向量p1p2是否共线,这样我们可以确定点p3是否在线段l确定的直线上,接着我们判断点p3是否在点p1p2确定的矩形当中(判断方式很简单,点p3满足x1<=x3<=x2 && y1<=y3<=y2,切记不可省略两个条件中的任意一个)。
    四、判断两条线段是否相交
           这个判断我们当然也可以使用两个线段方程联立求解的方式来判断,但是同样存在性能和精度上的问题。而改进的算法是这样的思想,如果线段l1和l2相交那么线段l1的两个顶点必然在线段l2的两端,同理l2的两个端点也必然在l1的两端,如图:
    这张图中包括了两种情况相交与不相交,可以看到我们每次都是判断一条线段上的两个点(蓝色表示)是否在另一条线段(用紫色加粗)的两侧,而判断方法很简单,我们使用了两个向量(红色表示)是否在那条线段(紫色加粗)的两端,判断很简单,用叉积,如果两个叉积的积为负表示两个叉积不同号,红色向量在紫色向量的两侧,如果两次判断都满足上面的条件那么可以确定两条线段相交。下面的部分表示了不相交的情况这时求出的两个叉积的积必然为正。当然我们还要考虑下面的边界条件。还是用图来表示
    用同样方法来计算叉积的时候在处理叉积m1 = P1P3 * P1P2 与m2 = P1P4 * P1P2时由于m1 == 0 所以 m1*m2 == 0这时说明有线段的端点在另一条线段上的情况出现,通过m1==0我们可以知道P3在线段P1P2上或者在其延长线上,这时需要判断的是点P3是否在线段P1P2上,这时判断回到了第三个主题的情况下。千万要注意的是当叉积等于0的时候并不意味着两条线段相交的情况出现,因为所谓的交点可能出现在延长线上。
    五、凸包问题
            所谓凸包就是这样一个问题给定一组点,求用这组点集中的某些点组成的一个最小凸多边形能够包围点集当中所有的点。算法如下:
    1、取得一个角点,作为开始点。开始点为最左下点(即y坐标最小,如果有多个相同点则再取x坐标最小)。
    2、对所有其他的点,按照倾斜角递增的顺序排序,形成一个闭合的多边形
          这个部分需要注意的有两点,第一、在给对象排序的过程中最重要的是比较两个对象的大小问题,即compareLT(obj1,obj2)算法的实现,在这里由于是按倾斜角来排序,我们可以采用这样的一种比较方式,给定点p1、p2,从原点出发到这两个点的向量也为p1、p2,那么求这两个向量的叉积得到m,如果m<0那么说明向量p2在向量p1的逆时针方向,p2的倾斜角较大,compareLT(p1,p2)应该返回true;第二、对于倾角相同点的处理方式,即m相同的点,对于一组倾角相同的点我们只取其中离第一步当中确定的点距离最远的点,其他的点删除掉。
    3、根据第二部排序及预先处理好的一个点集我们以此对除第一步确定的点p0外其他的点做扫描,这里要用到一个堆栈,首先初始化堆栈并将p0以及排序好的点集当中的前两个点入栈,接着扫描剩余的点,每次扫描到一个点则查看堆栈顶部的两个点Pi和Pj,确定在Pi点的转向,如果是向左转则入栈当前点Pm,否则出栈Pi,然后继续查看栈顶两点,比较栈顶点到当前点的转向,知道转向为左Pm点入栈为止。
           这一步当中所说的确定转向部分的算法又回到第二个主题所描述的算法当中。
    六、判断给定点所组成的多边形是否为凸多边形
           首先假定给定的点按照某个顺序排定(或者顺时针或者逆时针),对于给定的点序列<P1,P2,P3,P4...Pm>当中的任意三个点Pi,Pj,Pk,如果满足折线在Pj处的转向都相同(或都为左或都为右),那么即可判断多边形为凸,判断折线转向的问题又回到主题2所讨论的算法。而事实上如果给定的点位逆时针序,那么转向必然为左;如果为顺时针序必然为右。
    七、凸多边形面积的计算
            根据向量叉积的意义我们知道对于三角形P1P2P3,我们求得叉积m=P1P2 * P1P3的绝对值:abs(m)就等于三角形面积的两倍,基于这样的原因我们可以根据给定凸多边形上按逆时针排列的顶点几何选定一点,依次求该点到连续两点组成三角形的面积并最终求和即得到凸多边形的面积,如图:
    八、判断点是否在多边形内
            判断点是否在多边形内的方法为将点像左做一条射线(实际只要做一条线段,线段的右端点的x值只要比所有可能点小即可y值与给定点相同),然后求这条所谓射线与多边形各个边交点的总和count,如果count为偶数则在多边形外否则在多边形内
            但是这里需要注意的是这么几种情况:1.如果多边形的某条边为水平(与X轴平行)则这条边不放入比较;2.如果边与射线的交点在顶点,那么分两种情况,如果该顶点是这条边两个顶点当中y值较大者count++否则count不变;3.如果点P直接在多边形某条边上那么直接判断点在多边形内(当然也要看程序要求)。
            因此该判断的程序流程应该是:
    0.count <- 0
    1.从多边形依次取出每条边
        Y:有边,转2
        N:无边,转6
    2.判断点是否在边上
       Y:返回true
       N:继续
    3.判断边是否水平(y1 == y2)
       Y:从1继续执行
       N:继续
    4.边的两个顶点是否在射线上
       Y:  4-1-1 判断该顶点是否是y值较大者
                  Y:count++;
        N: 判断射线与边是否相交
             Y:count++
    5.转1执行
    6.结束,输出count
    展开全文
  • [转载]计算机几何算法

    千次阅读 2011-03-09 18:30:00
    [转载]计算机几何算法原文地址:计算机几何算法作者:yuanmercu_oxxdl这里讨论计算机2D空间内的一些几何算法。讨论的主题包括:两条线段之间的方向、折线在某个顶点上的转向、点是否在线段上的判定、线段是否相交的...

    [转载]计算机几何算法

    原文地址:计算机几何算法作者:yuanmercu_oxxdl
    这里讨论计算机2D空间内的一些几何算法。讨论的主题包括:两条线段之间的方向、折线在某个顶点上的转向、点是否在线段上的判定、线段是否相交的判定、凸包、给定点组成的多边形是否构成凸多边形的判定、凸多边形面积的计算以及判断点是否在一个多边形(包括凹凸两种多边形) 当中的算法。
            在讨论这些主题之前,首先确定点在计算机内的表示使用一个数对(整数或者浮点数,看具体需求)<X,Y>来表示,而线段使用线段的两个端点来表示。在后面的所有主题讨论之中我们经常会用到一个几何术语:叉积,具体的几何意义表示由两个向量及其平移得到的向量围城的平行四边形的面积,而其算法是这样表示的:向量a=(x1,y1)向量b=(x2,y2),叉积a×b=x1*y2 + x2*y1;为了这些主题讨论的方便线段l我们有时也会表示成向量,表示的方法是:假设线段l上的两个端点p1(x1,y1),p2(x2,y2)那么表示出来的向量p1p2=(x2-x1,y2-y1)。
    一、两条线段的方向
            这个主题要求的就是线段l2在给定线段l1的顺时针或者逆时针方向上。正如上面所说的,我们把两条线段表示成向量的方式,这样转化而来的向量都以共同顶点原点为出发点。这样我们求得两个向量的叉积m,如果m<0说明线段l2在线段l1的逆时针方向上;m>0说明在顺时针方向上;m==0表示两条线段共线。
    二、折线在某个顶点上的转向
            假设折线上依次有点p1、p2、p3,求在顶点p2上折线是向左转或者向右转。如图:
            显然如果我们要求在P2点上的折向我们只需要把P1、P2、P3表示成第二张图上红色部分表示的两个向量P1P2和P1P3,如果向量P1P3在向量P1P2的顺时针方向那么在P2点上就是向右转,否则就是左转,而判断两个向量(或者线段)方向的算法就是第一个主题当中提到的内容。
    三、点在线段上的判断
            点是否在线段上的判断有两种方式,第一种计算出线段的方程然后判断,但是这种方式当中由于存在大量除法运算,因此不但效率较差而且存在着精度的问题。而另一种判断方式则是,设线段l上两个顶点p1p2,要求判断的点为p3,我们前面讲到过如果两个向量的叉积为0那么两个向量共线,因此我们首先判断向量p1p3和向量p1p2是否共线,这样我们可以确定点p3是否在线段l确定的直线上,接着我们判断点p3是否在点p1p2确定的矩形当中(判断方式很简单,点p3满足x1<=x3<=x2 && y1<=y3<=y2,切记不可省略两个条件中的任意一个)。
    四、判断两条线段是否相交
           这个判断我们当然也可以使用两个线段方程联立求解的方式来判断,但是同样存在性能和精度上的问题。而改进的算法是这样的思想,如果线段l1和l2相交那么线段l1的两个顶点必然在线段l2的两端,同理l2的两个端点也必然在l1的两端,如图:
    这张图中包括了两种情况相交与不相交,可以看到我们每次都是判断一条线段上的两个点(蓝色表示)是否在另一条线段(用紫色加粗)的两侧,而判断方法很简单,我们使用了两个向量(红色表示)是否在那条线段(紫色加粗)的两端,判断很简单,用叉积,如果两个叉积的积为负表示两个叉积不同号,红色向量在紫色向量的两侧,如果两次判断都满足上面的条件那么可以确定两条线段相交。下面的部分表示了不相交的情况这时求出的两个叉积的积必然为正。当然我们还要考虑下面的边界条件。还是用图来表示
    用同样方法来计算叉积的时候在处理叉积m1 = P1P3 * P1P2 与m2 = P1P4 * P1P2时由于m1 == 0 所以 m1*m2 == 0这时说明有线段的端点在另一条线段上的情况出现,通过m1==0我们可以知道P3在线段P1P2上或者在其延长线上,这时需要判断的是点P3是否在线段P1P2上,这时判断回到了第三个主题的情况下。千万要注意的是当叉积等于0的时候并不意味着两条线段相交的情况出现,因为所谓的交点可能出现在延长线上。
    五、凸包问题
            所谓凸包就是这样一个问题给定一组点,求用这组点集中的某些点组成的一个最小凸多边形能够包围点集当中所有的点。算法如下:
    1、取得一个角点,作为开始点。开始点为最左下点(即y坐标最小,如果有多个相同点则再取x坐标最小)。
    2、对所有其他的点,按照倾斜角递增的顺序排序,形成一个闭合的多边形
          这个部分需要注意的有两点,第一、在给对象排序的过程中最重要的是比较两个对象的大小问题,即compareLT(obj1,obj2)算法的实现,在这里由于是按倾斜角来排序,我们可以采用这样的一种比较方式,给定点p1、p2,从原点出发到这两个点的向量也为p1、p2,那么求这两个向量的叉积得到m,如果m<0那么说明向量p2在向量p1的逆时针方向,p2的倾斜角较大,compareLT(p1,p2)应该返回true;第二、对于倾角相同点的处理方式,即m相同的点,对于一组倾角相同的点我们只取其中离第一步当中确定的点距离最远的点,其他的点删除掉。
    3、根据第二部排序及预先处理好的一个点集我们以此对除第一步确定的点p0外其他的点做扫描,这里要用到一个堆栈,首先初始化堆栈并将p0以及排序好的点集当中的前两个点入栈,接着扫描剩余的点,每次扫描到一个点则查看堆栈顶部的两个点Pi和Pj,确定在Pi点的转向,如果是向左转则入栈当前点Pm,否则出栈Pi,然后继续查看栈顶两点,比较栈顶点到当前点的转向,知道转向为左Pm点入栈为止。
           这一步当中所说的确定转向部分的算法又回到第二个主题所描述的算法当中。
    六、判断给定点所组成的多边形是否为凸多边形
           首先假定给定的点按照某个顺序排定(或者顺时针或者逆时针),对于给定的点序列<P1,P2,P3,P4...Pm>当中的任意三个点Pi,Pj,Pk,如果满足折线在Pj处的转向都相同(或都为左或都为右),那么即可判断多边形为凸,判断折线转向的问题又回到主题2所讨论的算法。而事实上如果给定的点位逆时针序,那么转向必然为左;如果为顺时针序必然为右。
    七、凸多边形面积的计算
            根据向量叉积的意义我们知道对于三角形P1P2P3,我们求得叉积m=P1P2 * P1P3的绝对值:abs(m)就等于三角形面积的两倍,基于这样的原因我们可以根据给定凸多边形上按逆时针排列的顶点几何选定一点,依次求该点到连续两点组成三角形的面积并最终求和即得到凸多边形的面积,如图:
    八、判断点是否在多边形内
            判断点是否在多边形内的方法为将点像左做一条射线(实际只要做一条线段,线段的右端点的x值只要比所有可能点小即可y值与给定点相同),然后求这条所谓射线与多边形各个边交点的总和count,如果count为偶数则在多边形外否则在多边形内
            但是这里需要注意的是这么几种情况:1.如果多边形的某条边为水平(与X轴平行)则这条边不放入比较;2.如果边与射线的交点在顶点,那么分两种情况,如果该顶点是这条边两个顶点当中y值较大者count++否则count不变;3.如果点P直接在多边形某条边上那么直接判断点在多边形内(当然也要看程序要求)。
            因此该判断的程序流程应该是:
    0.count <- 0
    1.从多边形依次取出每条边
        Y:有边,转2
        N:无边,转6
    2.判断点是否在边上
       Y:返回true
       N:继续
    3.判断边是否水平(y1 == y2)
       Y:从1继续执行
       N:继续
    4.边的两个顶点是否在射线上
       Y:  4-1-1 判断该顶点是否是y值较大者
                  Y:count++;
        N: 判断射线与边是否相交
             Y:count++
    5.转1执行
    6.结束,输出count
    展开全文
  • 计算几何 算法与应用 第三版(中文版和英文版,绝不是扫描的) PDF
  • 计算几何的大部分算法都在里面可以找的到 高清版本 附带目录
  • 计算几何算法(含源代码) ㈠ 点的基本运算 1. 平面上两点之间距离 1 2. 判断两点是否重合 1 3. 矢量叉乘 1 4. 矢量点乘 2 5. 判断点是否在线段上 2 6. 求一点饶某点旋转后的坐标 2 7. 求矢量夹角 2 ...
  • 找工的过程中遇到了一些不错的几何算法面试题,这里做个总结,方面自己以后查阅,如果能帮到别人找工准备就更好了。 问题一:能否在一个边长为1的等边三角形中找到5个点,使得这5个点两两之间的距离大于0.5? 如上...
  • 给定一个四面体,通过读入四个值(1-10),分别作为其底面,正面,右面,左面所涂的颜色,如果两个四面体在旋转的意义下,四面的颜色可以一一对应,则认其为同一种四面体. 输入: 第一行为一个整数N,代表四面体个数 ...
  • 分形几何算法和实现

    万次阅读 2016-12-15 22:22:53
    曼德勃罗是想用此词来描述自然界中传统欧几里得几何学所不能描述的一大类复杂无规的几何对象。 2、分形的几何特征: 自相似性:自相似,便是局部与整体的相似。 自仿射性:自仿射性是自相似性的一种拓展。...
  • GIS开发中常用几何算法原理图解

    千次阅读 2017-08-20 22:23:51
    转自:OSGeo中国中心 ...在本文中,我们将对计算几何常用的基本算法做一个全面的介绍,希望对您了解并应用计算几何的知识解决问题起到帮助。矢量的概念如果一条线段的端点是有次序之分的,我们把这种线段成为有
  • ACM几何算法题目推荐

    千次阅读 2012-09-08 18:52:07
    一。基础题目 1.1 有固定算法的题目 A, 最近点对问题 ...最近点对问题的算法基于扫描线算法。 ZOJ   2107 Quoit Design 典型最近点对问题 POJ 3714 Raid 变种最近点对问题 B,最小包围圆
  • 比较有意思的2D几何算法

    千次阅读 2013-10-31 21:09:10
    http://www.codeproject.com/Articles/22568/Computational-Geometry-C-and-Wykobi
  • 练习泛型算法的使用。 源代码: #include<iostream> #include<vector> #include<algorithm> #include<ctime> using namespace std; vector<int> a; int main() { ...
  •  尽管人类对几何学的研究从古代起便没有中断过,但是具体到借助计算机来解决几何 问题的研究,还只是停留在一个初级阶段,无论从应用领域还是发展前景来看,计算几何 学都值得我们认真学习、加以运用,希望这篇文章...
  • c#实现的一些几何算法(一)

    千次阅读 2010-05-23 23:49:00
    算法改写于网上的一篇C++的,在此只不过是用c#实现了。这篇是关于点的一些算法,后面还有线、多边形的。 /// /// 点对象 /// public class SpatialPoint { public double x; public double y; p
  • 13.判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端  点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着  L从无穷远处开始自左向右移动,遇到和...
  • 几何学的图形计算经常应用到游戏或其它复杂的UI的开发中,下面介绍的是开发游戏中所用到的计算已知直线与圆交点的坐标。·如图,当某个物体活动范围仅限于圆o的区域范围内,可以拖动它移动,即在圆的区域内物体的...
  • c#实现的一些几何算法(三)

    千次阅读 2010-05-25 19:12:00
    续一、二//关于面的public class GeometricClass{ // 已知矩形的三个顶点(a,b,c),计算第四个顶点d的坐标. 注意:已知的三个顶点可以是无序的 public static SpatialPoint FourthPointOfRec(SpatialPoint a, ...
  • 绝版书籍。 本书对计算机图形学和其他领域的二维和三维几何学算法进行了全面的解析和合理的组织。...本书适合作为计算机图形学几何算法课程的教材,也可作为参考指南,供经验丰富的业界人士参考查阅。
  • 计算几何常用算法

    千次阅读 2007-01-12 21:05:00
    作为计算机科学的一个分支,计算几何主要研究解决几何问题的算法。在现代工程和数学领域,计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸 多领域有着十分重要的应用。在本文中,我们将对计算几何...
  • int threeValue(double d) { if (fabs(d) < eps) return 0; return d > 0 ? 1 : -1; }

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 104,505
精华内容 41,802
关键字:

几何算法