面向高速加工的等残余螺旋轨迹生成方法

针对现有轨迹生成方法难以满足高速加工的要求的问题,提出一种等残余高度螺旋轨迹直接生成方法.首先根据首末2条边界曲线的不同连接方式进行分类,对存在的3种连接方式分别设计了不同的初始螺旋轨迹生成方式;然后采用等残余轨迹生成方法偏置初始螺旋轨迹.这种直接生成的螺旋轨迹与传统通过求环形轨迹问的对角曲线生成的螺旋轨迹相比,可更好...     

基于成长型神经网络以线段为基元的曲线重建

在逆向工程中,对基于散乱数据点的曲线重建研究有着重要的意义。曲线可用线段基元逼近。提出使用成长型神经网络以线段为基元的曲线重建新算法。给定某一曲线的散乱点集和一初始折线,新算法优化折线上的顶点位置,使折线更好地逼近散乱点;持续分裂折线上活动性强的顶点和删除活动性最弱的顶点,使折线上顶点的分布更符合散乱点数据的概率分布。实验结果表明,新算法能够取得良好的曲线重建效果。     

平面散乱点线集三角剖分的算法

利用平面扫描的思想，即利用从右到左移动的y-轴扫描点线集．当扫描线达到某个给定点或给定线段端点时，将该点或端点与其上下相邻线段端点连接．新连线与已三角剖分的边只能在其端点处相交．该算法的时间复杂性为O(N log N)，其中N是点线集中点的数目与线段端点数之和．     

VBA编程应用实例

以减少多线段的顶点为例,通过编程对多线段的相邻顶点距离进行计算,根据距离对多线段的某一顶点进行取舍,从而实现减少多线段顶点的目标.     

基于MapReduce框架的分布式软K段主曲线算法

传统的主曲线算法在小规模数据集上能获得良好的效果,但单节点的计算和存储能力都不能满足海量数据主曲线的提取要求,而算法分布式并行化是目前解决该类问题最有效的途径之一。本文提出基于MapReduce框架的分布式软K段主曲线算法 (Distributed soft ｋ-segments principal curve,DisSKPC)。首先,基于分布式K-Means算法,采用递归粒化方法对数据集进行粒化,以确定粒的大小并保证粒中数据的关联性。然后调用软K段主曲线算法计算每个粒数据的局部主成分线段,并提出用噪声方差来消除在高密集、高曲率的数据区域可能产生的过拟合线段。最后借助哈密顿路径和贪婪算法连接这些局部主成分线段,形成一条通过数据云中间的最佳曲线。实验结果表明,本文所提出的DisSKPC算法具有良好的可行性和扩展性。     

二次均匀B样条曲线的双圆弧逼近方法*

提出了一种用双圆弧对二次均匀B样条曲线的分段逼近方法。首先,对一条具有n 1个控制顶点的二次均匀B样条曲线按照相邻两节点界定的区间分成n-1段只有三个控制顶点的二次均匀B样条曲线段;然后对每一曲线段构造一条双圆弧进行逼近。所构造的双圆弧满足端点及端点切向量条件,即双圆弧的两个端点分别是所逼近的曲线段的端点,而且双圆弧在两个端点处的切向量是所逼近的曲线段在端点处的单位切向量。同时,双圆弧的连接点是双圆弧连接点轨迹圆与其所逼近的曲线段的交点。这些新构造出来的双圆弧连接在一起构成了一条圆弧样条曲线,即二次均匀B样条曲线的逼近曲线。另外给出了逼近误差分析和实例说明。     

二维点与曲线位置关系判断的最邻近线段法

为解决三维地质建模中模型切割时遇到的分边问题,提出一种二维点与曲线的位置关系判断算法,即最邻近线段法.该算法在曲线上寻找与点最邻近的线段,判断其与点的位置关系,从而确定点与曲线的位置关系.在三维地质建模中,先将待判断的模型点和切割曲线都转换到二维(暂不考虑Z坐标),然后使用该算法判断点与曲线的位置关系,最后再转换回三维,即完成三维点与曲线的位置关系判断,进而解决模型点相对切割曲线分边的问题.     

三角网格模型的特征线提取

在反求工程中，散乱数据点云的曲面重构常采用三角网格模型，若将其转换成曲面实体模型则有更广泛的应用，从三角网格模型中提取特征线是转换过程中的重要步骤．在讨论反求工程中数据点云分块方法的基础上，采取“基于边”的方法来提取特征线：先提取特征点，再连接成特征线．根据相邻三角片的法矢夹角和各点主曲率是否为极值，分两次提取特征点，利用三角顶点加权和均匀化等方法减少狭长三角片对特征点提取的计算误差影响，再将特征点分组连接成B样条曲线．文中算法的结果可为B样条曲面分片拟合和建立B-rep曲面实体模型提供依据。     

基于复杂形态数据的主曲线提取算法及其在图像骨架提取中的应用

针对目前存在的主曲线算法对提取分散度大、高度弯曲及自相交等复杂形态数据效果不好的情况,提出从复杂数据集中找到主曲线的新方法.算法首先用细化算法初始化顶点集得到初步骨架图,并合并邻近顶点;然后采用Kégl主曲线算法的拟合光滑步思想并加以改进来平滑顶点位置,通过迭代构建出主图;最后采用Kégl主曲线算法的重构步进一步修正主图.算法在模拟数据集上进行试验而且还被运用于图像骨架提取,实验结果表明它对提取复杂数据的主曲线是非常有效的.     

快速成型中基于直骨架原理的轮廓偏置算法

为了降低光固化快速成型中成型件的表面粗糙度,解决现有偏置算法中效率低、轮廓自相交和互相交等问题,提出一种基于直骨架的偏置算法.该算法采用多边形单调链分解的方法来提高直骨架计算速度,适用于二维多连通区域;求取偏置多边形前,通过标记偏置分裂及退化的偏置点,用栈的数据组织形式提取偏置多边形顶点,提高了算法稳定性.实验结果表明,在快速成型中,采用该算法的多重轮廓扫描方式能有效降低成型件的表面粗糙度并提高制作效率.     

Computing offsets of B-spline curves

This paper presents a general offset technique valid for non-uniform rational B-spline curves. The offset curve is defined by a new control polygon where each new control point is the offset of a control point of the original curve in a direction given by the normal at the closest point of the curve. The offset factor is related to both the curvature and the distance between the control point and its closest point. Straight lines and inflection points are considered as well as the offset in a direction other than the normal one. One of the main advantages of this technique is to provide a good approximation when the offset cannot be described by a B-spline and an exact result otherwise (for circles, for example).     

Incremental Labelling of Voronoi Vertices for Shape Reconstruction

We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece‐wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non‐uniformly (ε‐sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non‐uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm.     

寻求简单多边形凸壳的线性时间算法

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选，使剩余顶点的角的大小排成递增序，然后用Graham扫描方法删去非凸壳顶点，最后得到多边形凸壳的顶点序列.第二个算法不断删去多边形的凹点及新产生的 凹点，最后得到凸壳顶点序列。这两种算法简单，易于实现，时间复杂性都是O（n)。     

遗传算法在曲线多边形近似中的应用

在平面数字曲线的多边形近似中,为克服顶点的检测只依靠部区域,缺 乏全局信息的弱点,文中把多边形近似问题作了寻找在满足一定的近似误差下使顶点数最少,或者使顶点数和近似误差都尽可能少的最优化问题来处理。     

带法向约束的圆平均非线性细分曲线设计

目的 对采样设备获取的测量数据进行拟合,可实现原模型的重建及功能恢复。但有些情况下,获取的数据点不仅包含位置信息,还包含法向量信息。针对这一问题,本文提出了基于圆平均的双参数4点binary非线性细分法与单参数3点ternary插值非线性细分法。方法 首先将线性细分法改写为点的重复binary线性平均,然后用圆平均代替相应的线性平均,最后用加权测地线平均计算的法向量作为新插入顶点的法向量。基于圆平均的双参数4点binary细分法的每一次细分过程可分为偏移步与张力步。基于圆平均的单参数3点ternary细分法的每一次细分过程可分为左插步、插值步与右插步。结果 对于本文方法的收敛性与C¹连续性条件给出了理论证明;数值实验表明,与相应的线性细分相比,本文方法生成的曲线更光滑且具有圆的再生力,可以较好地实现3个封闭曲线重建。结论 本文方法可以在带法向量的初始控制顶点较少的情况下,较好地实现带法向约束的离散点集的曲线重建问题。     

平面点集凸壳的快速算法

提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算（除最坏情况外）,从而节省计算时间。     

带有给定切线多边形的C~2连续的C-B样条曲线

描述了一种与给定切线多边形相切的 C- B样条曲线的算法 .在算法中 ,所有的 C- B样条曲线的控制点可以通过对切线多边形的顶点简单计算产生 .所构造的曲线对切线多边形具有保形性 ,曲线可以局部修改 .最后给出了三个算例 .     

带有给定切线多边形的C-Bézier闭曲线和B-型样条闭曲线

§1.引 言 Bézier曲线和B样条曲线已广泛应用到汽车、航空、造船等许多领域中.Hering讨论了与凸多边形每边相切的分段三(四)次 Bézier闭曲线和三(四)次B样条闭曲线.它的所有Bézier点必须通过求解大型方程组得到,计算量大,且曲线易出现拐点,而B样条闭曲线的控制点要通过反算得到[1].方逵改进了Hering的方法,构造了G2连续的分段三次曲线[2],基本上克服了Hering方法的两个缺点,但局部修改仍然是比较复杂的.方逵等再次研究了与任意多边形相切的分段四次和五次Bézier曲线[3],但五次Béier曲线不能作局部修改.本文的第二节研究了与任意多边形相切的分段C-Bézier曲线,该曲线C1连续的,且对切线多边形具有保形性,每段C-Bézier曲线上的控制点由切线多边形的顶点计算     

A fast algorithm for parametric curve plotting

In parametric curve plotting by means of line segments, a curve r = r(t), t[t₀, t_u] is given, and a set of ordered points r(t_i, iN, t_ie[t₀, t_u] is specified as the vertices of an inscribed polygon of the curve. There are several, analytical, numerical or intuitive ways to derive these vertices obtaining a smooth polygonal approximation. The methods, which can be found in the literature, either belong to some special curves or involve a considerable waste of computing time.

In this paper, we consider an algorithm that appears as a subroutine in the whole program. The subroutine allows the main program to space points as a function of a distance interval for any parametric curve. The design of the routine for performing this spacing is outlined and two examples are shown.     

Guarding galleries and terrains

Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.