加载中...
QQ群:3790902 | 设为首页 | 加入收藏 | sitemap |
 
初级 程序员 网管员 信处技 电商技 中级 数工 软测 监理师 多媒体设计师 软设 信息系统管理 嵌入式 电商设 网工 系统集成 高级 系统分析 网络规划 项目管理 系统架构
数据库 操作系统 数据结构 软件工程 计算机系统 语言 网络 多媒体 标准化 计算机图形学 电子商务 数据挖掘 编译原理 信号处理
VB C\C++ Java ASP PHP JSP Access MSSQL Mysql Oracle DB2 Sybase Delphi 片上系统
Ajax .net Perl Pascal ODS XML 云计算 P2P 工作流 快速工具 设计模式 异构数据 统一过程 软件架构
供应链 ERP CRM UML CMM J2EE 中间件 EAI 产品线 商业智能 极限编程 多核技术 外包ASP SOA
PB WEB Service WSDL UDDI SOAP TSP 虚拟化 AOP SaaS 论文 网格计算 普适计算 敏捷方法 RIA

凸包计算

2008-8-13 21:22:48 本站原创 佚名 【字体:

核心提示:凸包计算 一个图形的凸包,就是包含这个图形的一个凸的区域。例如,一个平面图形的凸包可以是一个凸多边形,一个三维物体的凸包可以是一个凸多面体。一个图形的凸包不是唯一的。 在进行图形求交计算时,为了减小计
凸包计算

一个图形的凸包,就是包含这个图形的一个凸的区域。例如,一个平面图形的凸包可以是一个凸多边形,一个三维物体的凸包可以是一个凸多面体。一个图形的凸包不是唯一的。

在进行图形求交计算时,为了减小计算量,经常要在求交之前先进行凸包计算。如果两个图形的凸包不相交,那么显然它们不可能相交,就不必再对它们进行求交了。否则这两个图形有可能相交,需要进一步计算。

包围盒是一种特殊而又十分常用的凸包。二维的包围盒是二维平面上的一个矩形,它的两条边分别与两条坐标轴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

点击浏览下一页

相关阅读:

上一篇文章:重叠判定算法
下一篇文章:没有了

网友评论:


图文信息
实战JBOSS――教你写第一个EJB 2001年度网络设计师级下午试卷
CSAI高程模拟试题三 ASP.NET服务器控件之RenderContents