凸多边形最小面积四边形包围盒算法

针对凸多边形的最小面积四边形包围盒问题进行研究,通过数学推导证明,得出了凸多边形的最小面积四边形包围盒的四边都是多共点边,或三边是多共点边而另一边(单共点边)中点与凸多边形的一顶点重合等一系列结论.依据此结论设计了时间复杂度为O(n4)的算法,依据本算法可以构造出凸多边形面积最小的凸四边形包围盒,而且其算法的复杂度仅与凸多边形的边数n相关,是多项式级的复杂度.运算实例表明了算法的正确性和有效性.     

基于凸包的最小体积有向包围盒生成算法

针对复杂物体三维点集的建模问题,提出一种基于凸包的最小体积的封闭有向包围盒生成算法.对凸包和其最小体积有向包围盒的关系进行分析,总结了其4种边面接触类型.通过枚举凸包中边的所有可能的组合,唯一确定包围盒的最优方向.实验证明,该算法可以快速生成符合模型体积特征的最小有向包围盒,且拟合效果良好.     

基于布尔搜索的空间目标分布最小包围盒规划

为了降低对平面内无源目标进行定位产生的搜索代价,研究了确定覆盖所有随机部署的无线传感器网络节点的最小包围盒问题.首先提出基于布尔搜索的无线传感器网络节点最小包围盒规划方法,运用深度优先策略,使锚节点不断逼近目标节点的实际位置;然后根据前述算法完成时的锚节点坐标,设计了坐标最大-最小值规划算法以构造最小覆盖面积包围盒.最后通过仿真和算法分析得出,所提策略计算复杂度低于遍历方式的最小包围圆、包围盒算法,且能更准确地估计出覆盖面积最小的包围盒.     

基于区域的光纤环绕制缺陷实时检测算法

针对光纤陀螺敏感线圈(光纤环)制备过程中,光纤的绕制张力变化和光纤环承载主轴跳动度变化等因素导致的"爬丝"和"间隙"绕制缺陷,提出基于区域的光纤环绕制缺陷检测算法,将原始光纤凹凸特征的处理转换成矩形大小及数量特征的处理。该算法在对光纤环绕制轮廓精确提取的基础上,通过对光纤环初始表面进行拟合,确定绕制光纤覆盖的最小有效区域,并实时提取区域内已绕制光纤轮廓的最小包围矩形;然后根据阈值的合理选取,计算最小有效区域内已绕制轮廓的最小包围矩形的区域大小及区域个数,以此判断绕制缺陷的种类,并标记缺陷位置。实验结果表明,在光纤环绕制轮廓精确提取的基础上,该算法可以有效识别并标记缺陷位置,对于不易受环境因素影响的"间隙"缺陷可以完全正确检出,且执行速度快,可满足缺陷实时检测的要求。     

最小距离分裂算法在NURBS曲面间的改进

基于分裂算法中最小距离在NURBS曲面间的应用研究,提出了以包围体来代替包围盒(AABB)的思想,在求凸包间距离时选取了GJK算法,并对分裂算法进行了改进,从而在算法精度以及算法速度方面实现了极大地提高.     

基于改进OBB包围盒的碰撞检测算法

针对车铣复合数控加工仿真碰撞检测精确度低的问题,提出了一种基于改进OBB包围盒的快速碰撞检测算法.该算法基于改进的OBB包围盒算法,利用车铣复合加工仿真碰撞检测的结果,创建碰撞单元组的包围盒及层次包围盒树;通过粗检阶段计算出包围盒树的相交节点集合,计算得到发生碰撞的三角形面片集合;应用回退技术,解得初始碰撞时间及位置.实例验证结果表明,该算法有效提高了车铣复合数控加工碰撞检测的精确度.     

八叉树空间结构投影的射线物体求交方法

为了提高光线投射算法中射线与物体求交速度,提出一种利用八叉树空间结构在视平面上投影的射线快速求交方法。算法构造平行于视平面的八叉树空间结构,将每个八叉树叶子包围盒沿视点方向投影在视平面上,将视平面划分成若干投影区域。在射线与包围盒求交时,根据射线落在视平面上的位置,确定其所属投影区域,求出与该射线相交的包围盒。实验表明该算法对传统的光线投射算法效率有较大提升。     

基于空间分解和混合包围盒的碰撞检测算法

针对如何提高碰撞检测的实时性,提出了一种碰撞检测算法.该算法首先利用空间分解确定相邻物体,然后对相邻物体利用层次包围盒方法进行碰撞检测,在包围盒碰撞检测方面,提出了一种新的包围盒混合结构,这种混合结构结合了AABB包围盒相交测试的简单性和k-DOPs包围盒的紧密性.实验结果表明,该算法有效地提高了碰撞检测的实时性.     

几何对象统一表示的R~*-tree结点分裂算法

针对R*-tree应用到逆向工程领域时遇到的适用性差等问题,提出一种新的R*-tree点分裂算法.该算法将R*-tree索引结点表示为最小包围盒,依据最小包围盒外接球间的重叠度衡量结点间的相似值,结合k-means算法,随机提取两个结点作为初始分簇中心,依据结点间的相似值计算新的分簇中心并迭代分簇,直到分簇中心不再变化,实现R*-tree的结点分裂.实例表明,该算法可处理各种复杂几何对象的R*-tree结点分裂问题,并可优化R*-tree结构,显著提高结点的分裂效率.     

一种新的基于混合层次包围盒的并行碰撞检测算法

提出了一种基于混合层次包围盒（HBVs）的快速并行碰撞检测算法。利用AABB包围盒较好的紧密性和包围球计算简单的优点及并行技术中的分治策略来构建物体的混合包围盒层次（S—AABB）,通过遍历混合包围盒层次组成任务树,采用OpenMP并行模型并行遍历任务树来加速碰撞检测算法。实验结果表明,该算法在效率、精确性方面具有明显优势。     

平面代数曲线的交点隔离算法

判断两条平面代数曲线在给定区域内是否相交是几何设计的一个基本问题.针对代数曲线的正规交点,本文建立了一个隔离算法.首先使用结式计算和单变元多项式的实根隔离算法,获得一系列初始矩形Box.这些Box中要么没有交点,要么只有唯一交点.通过引入伴随多项式,建立了判定给定Box中无交点和有唯一正规交点的方法 .利用Maple平台实现了隔离代数曲线正规交点的算法Real Intersection.经过随机方程组实验,该方法在高次数的情况明显优于Maple中基于有理单变元表示的交点隔离方法 Isolate.     

基于碰撞检测算法的动态服装仿真研究

针对传统服装仿真方法中的动力学模型生成策略和碰撞检测算法提出了改进。首先采用三角网格代替传统的四方网格,并给出了三角网格的生成算法;然后分别测试出待测点与AABB包围盒和图元的碰撞检测时间;再计算出整个碰撞检测时间开销最小时叶子包围盒中的图元数目;最后以该图元数目来构造AABB碰撞检测树,实现了最优情况计算叶子包围盒图元数量的方法。仿真结果表明,该改进生成算法能够有效地减少了碰撞检测时间。     

基于分形盒维数检测QRS波群定位方法

应用分形盒维数检测理论，对心电信号的分形特征进行了研究，结果显示不同格子尺度下检测到的覆盖信号盒子数与格子尺寸之间存在密切的对数线性关系，这表明心电信号也具有分形特性。同时，研究过程中还发现当采用一个时间窗来对信号进行检测时，在心电信号中QRS波群位置检测到的分维较大。而且这种差异很显著。在这个发现的基础上，提出了基于分形盒维数检测的心电信号QRS波群定位方法，经实际应用表明该算法速度较快，并能有效去除干扰，可用于心电信号特征点的实时检测中。     

求解圆柱形物品装载问题的递归启发式算法

研究同尺寸圆柱形物品的装载问题.先将同尺寸圆柱形物品装入容量相同的长方体小箱,然后将小箱装入集装箱中,使集装箱所装物品数最多.对于各种可能的小箱尺寸,用启发式算法确定物品在小箱内的布局,使体积利用率尽可能高;用递归算法确定小箱在集装箱内的布局,使体积利用率最高.实验结果表明本文算法能够简化小箱布局方案,同时简化装箱过程,具有较好的应用价值.     

考虑倒箱操作的AutoStore魔方型仓储系统自动引导车双层路径规划

新兴魔方型仓储系统AutoStore中,用于存放货物的料箱垂直堆放在相互拼接但独立的货格内,AGV除了要搬运目标料箱外,还需负责目标料箱上部阻碍箱的倒箱操作,且活动范围从二维平面扩大到三维空间,均增加了路径规划的复杂性。为了降低路径规划的复杂性,在分解作业流程的基础上,通过建立AGV双层路径规划模型的方法：内层模型以阻碍箱落箱位为决策变量,最小化单个目标箱的倒箱时间;外层模型将内层模型所得倒箱时间为输入参数,优化目标为最小化AGV完成任务时间。通过提出嵌套式启发式算法,将倒箱路径寻优嵌入多AGV多任务路径分配中。研究了不同规模算例,证明了本文所给方法的有效率和适用性;且仓储规模增大后,目标箱分散度增加, AGV作业时间大幅度增加;AGV数量和作业时间负相关;仓储率提高会增加倒箱几率,增加作业时间;目标箱数目变化与AGV作业时间正相关。结果证明在求解效率方面,主要受目标箱随机生成位置和仓储率影响,但绝对值也仅在10秒左右。     

截面形式对R UHPC梁抗弯承载力的影响

为明确截面形式对UHPC抗拉强度在钢筋超高性能混凝土(R-UHPC)梁抗弯承载力贡献的影响,考虑实测得到的7种不同钢纤维掺量UHPC的抗拉和抗压性能,对矩形、箱形和T形R-UHPC梁进行抗弯承载力计算,构建并分析抗拉强度贡献率、抗压强度利用率等指标.结果表明:UHPC根据其硬化段长短和其极限应变与钢筋屈服应变的关系,可划分为U0、 U1和U2类材料. UHPC抗拉强度的贡献率与截面形式有关:矩形梁箱形梁T形梁,对U1和U2类UHPC的矩形梁或箱形梁,宜考虑其抗拉强度对梁抗弯承载力的贡献.材料设计时,若考虑UHPC抗拉强度的作用,宜采用U2类材料.截面设计时, UHPC抗拉强度的贡献,矩形梁应考虑,箱形梁可考虑, T形梁可不考虑,宜采用箱形、 I形或工形梁截面以提高抗拉强度贡献. UHPC抗压强度利用率,随纤维掺量的增大而下降,利用率在45.5%～60.2%范围.工程应用时,可应用UHPC-NC叠合梁或预应力UHPC梁以提高抗压强度利用率.     

矩形拉深件毛坯尺寸的求解

求解矩形拉深件的毛坯形状有许多理论及计算方法,但目前各种理论及计算方法都存在一定的局限性和误差,相比之下滑移场理论可较完善地反映矩形拉深件的特点。     

一种用于MEMS动态测量的最优盒计数分形维数算法

在微机电系统（micro electromechanical system,MEMS）的动态测量中,利用分形插值法可以提高MEMS器件面内位移测量的精度,利用图像边缘的分形特征,还可以实现离面位移和旋转角度的测试。而分形维数（fractal dimension）的计算又是这些方法的关键。在研究目前最常用的分形维数计算方法差分盒计数法（difference box counting, DBC）的基础上,提出了一种对“空盒子”不予计数的最优盒计数分形维数算法,克服了差分盒计数法存在“空盒子”被计数的缺陷。理论分析和实验结果表明,该算法获得的分形维数更接近于理论维数。     

CAD数据修复中寻找相邻曲面的空间包围盒算法

提出了基于ACIS平台寻找相邻曲面的算法,首先对读入的模型的所有曲面求出其空间包围盒,然后对每个曲面的每条边求出曲线的空间包围盒,利用空间包围盒是否相交确定是否可能相邻,最后运用边界匹配算法确定曲面的相邻关系.该算法思想简单,易实现.     

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.