截面线数据点排序算法研究与应用

提出一种截面线数据点排序算法,该算法计算截面线数据点的最小包围多边形,将截面线数据点依据边长差最小原则插入到最小包围多边形中,形成包含所有数据点的多边形,顺序连接该多边形各顶点,实现对截面线数据点的排序.实例证明,该算法稳定、准确,可有效提高截面线数据点的排序效率.     

判断点与封闭多边形相对关系的改进算法

针对以前判断点与封闭多边形关系的转角法只考虑封闭多边形边界全部直线组成而忽略了圆弧的缺陷,分析以圆弧为边界判断点与封闭多边形关系的原理,提出了改进算法,并举例说明了判断点与封闭多这形关系改进算法的原理和应用。     

点在平面多边形内外的判断方法

在诸多研究领域中,判断点是否在多边形内是一个非常基本的问题。首先分析了解决这一问题的传统方法, 然后提出一种边界代数跟踪法对多边形进行栅格化,在此基础上设计出Flooding操作和轮廓腐蚀算法进行多边形内外点的判断。试验结果表明该方法具有健壮性好、适用于任意复杂多边形而无需对奇异情况进行单独处理等优点。     

基于法线方向的点包容检测

过待定点作一射线,此射线可能与多边形的某几条边有交点,从待定点向这条边的两端点作两个向量,求这两向量的法线方向,对法线方向进行计数。若法线方向为正向,将计数器加1;若法线方向为反向,将计数器减1。求待定点与每条相交边的两向量的法线方向并计数,当法线方向的正反次数相同时,待定点在多边形外,否则在多边形内。此算法避免了某些其他算法的错误,计算量很小,简单易行。通过编写程序计算验证表明,算法简单有效、稳定可靠,对简单多边形、自相交多边形及带孔多边形等多类情况同样适用。     

一个多边形快速等距偏移方法

多边形的等距偏移是CAD/CAM领域中的一个基础性问题 ,是型腔环切加工刀具轨迹生成的关键。根据无效环在原始多边形上的对应连续线段必有一凸或凹点 ,从多边形的凸点和干涉凹点出发 ,利用干涉边的连贯性逐步确定无效环 ,最后对多边形中的非干涉区域作等距偏移 ,实现多边形的等距偏移。该方法利用干涉区域的连贯性避免了大量不必要的求交计算 ,同时支持带有孤岛的多边形等距偏移。其算法复杂度接近于O(n) ,其中n为多边形顶点个数。     

基于零件形心的数控火焰切割路径的规划

研究了数控火焰切割中多边形零件切割路径规划、打孔点的位置选择、带有内轮廓的零件打孔点位置选择和内轮廓的切割路径规划等关键问题,提出了一种基于零件外轮廓多边形形心的规划算法。首先根据零件外轮廓多边形计算零件的形心,然后把各个零件的形心作为TSP问题中的城市,采用蚁群算法对零件的切割路径进行分析。在此基础上,应用改进的局部优化算法研究了多边形零件切割打孔点的位置和内外轮廓的切割路径规划。     

一种快速的多边形的线裁剪算法

裁剪算法是计算机图形学的一个基本算法 ,但大多数算法都是针对矩形窗口或多边形窗口的 ,已有的凹多边形裁剪主要将其分解为凸多边形处理。此外提出一个任意多边形的快速交点排序线裁剪算法 ,并将其用于工程图装配的二维消隐     

一种快速的多边形的线裁剪算法

裁剪算法是计算机图形学的一个基本算法，但大多数算法都是针对矩形窗口或多边形窗口的，已有的凹多边形裁剪主要将其分解为凸多边形处理。此外提出一个任意多边形的快速交点排序线裁剪算法，并将其用于工程图装配的二维消隐。     

一种基于分裂合并的多边形逼近算法

断层医学图象目标组织经图象分割、轮廓跟踪后得到的轮廓像素点数据量较大,不宜直接用于几何建模。多边形逼近是提取曲线特征点和简化数据、加快图形运算的一个重要方法,提出一种基于分裂合并的多边形逼近算法,将轮廓像素点集合分段进行线段逼近,逐次递增进行共线检查,反复执行分裂、合并操作,直到所有逼近误差在指定范围内,逼近多边形不再改变为止。该算法能够在保持原始轮廓形状特征的前提下,有效减少数据量,提高了计算效率。     

基于自适应八叉树的三维点云快速拾取方法研究

针对逆向工程中大规模点云数据快速拾取问题,对当前三维图形拾取基本方法进行了研究,对点云拾取的基本流程和点云快速拾取的关键问题进行了分析,提出了一种基于自适应八叉树的三维点云快速拾取方法。当用户在计算机屏幕上给出拾取多边形后,首先基于点云分布密度,对点云数据进行了自适应八叉树划分;然后对八叉树节点进行了投影,在屏幕上形成了八叉树节点的投影多边形,并对拾取多边形建立了矩形包围盒;接着对八叉树投影多边形和拾取多边形的矩形包围盒进行了相交检测,将不与矩形包围盒相交的八叉树节点包含的点云去除,从而缩小了点云拾取所需判断的范围,提升了拾取效率。最后对不同分布密度点云进行了定面积的拾取实验。实验结果表明,该点云拾取方法的点云分布密度越大,拾取时间相对越短,算法具有较高的拾取速度和准确度。