凸包计算
一个图形的凸包,就是包含这个图形的一个凸的区域。例如,一个平面图形的凸包可以是一个凸多边形,一个三维物体的凸包可以是一个凸多面体。一个图形的凸包不是唯一的。
在进行图形求交计算时,为了减小计算量,经常要在求交之前先进行凸包计算。如果两个图形的凸包不相交,那么显然它们不可能相交,就不必再对它们进行求交了。否则这两个图形有可能相交,需要进一步计算。
包围盒是一种特殊而又十分常用的凸包。二维的包围盒是二维平面上的一个矩形,它的两条边分别与两条坐标轴x,y平行,可以表示为两个不等式:xmin≤x≤xmax,ymin≤y≤ymax;三维空间中的包围盒是一个长方体,其长、宽、高分别与三条坐标轴平行,表示为三个不等式:xmin≤x≤xmax,ymin≤y≤ymax,zmin≤z≤zmax。两个包围盒相交的充要条件是它们在每一个坐标轴方向上都相交。由于判定两个包围盒的相交情况比较容易,所以包围盒成为最常用的一种凸包。
求多边形或多面体的包围盒是相当简便的。只要遍历其所有顶点,就可以找出多边形或多面体在各个坐标轴方向上的最大、最小坐标值,从而确定包围盒。对于已近似化为多边形或多面体的含有曲线曲面的几何体,也可以用同样的方法求出包围盒。对于一般的几何形体,则要根据其具体性质来求取其包围盒。
在进行含有曲线、曲面的几何体的求交时,常常先求取它们的一个凸多边形或凸多面体的凸包,由于凸多边形和凸多面体间的求交相对简单,可以节省一定的计算量。例如,Bezier、B样条和NURBS曲线曲面具有凸包性质,其控制多边形或控制网格是其本身的凸包。在进行此类曲线曲面的求交计算时,就常先用其控制多边形或控制网格求交。
一般的凸包的求法因具体情况而异,下面举一个求圆弧凸包的例子。设圆弧段的圆方程为 (x-x0)2+(y-y0)2=r2,圆弧起始角为a1,终止角为a2。对圆弧计算凸包如图2.5.5所示。先根据起始角a1与终止角a2求出相应的弧端点坐标P1,P2,进而求出弧的弦中点Pm=(P1+P2)/2。再用(q 1+q 2)/2的正、余弦或下式计算弧中点Pc:
则该弧的包围盒顶点为P1,P1+(Pc-Pm),P2+(Pc-Pm), P2。
相关阅读:
下一篇文章:没有了
网友评论:
- 最新试题
- 考试大纲
加载中...


返回顶部


