生成圆弧的等距线约束方法及其应用

栅格圆弧的生成算法在计算机图形学和图像处理中有着大量的应用．一条曲线一定位于该线两侧的两条到该线距离足够小的等距线之间，或认为该曲线受其两侧的两条等距线的约束．本文从真实圆弧曲线受其两侧的等距圆的约束出发，提出一种生成栅格圆弧的等距线约束算法，并分析了该算法的精度．其优点是可单方向连续生成圆弧，且生成的两个相邻栅格圆之间不会有空隙或重叠，因此可直接用于圆域有关的图形生成和栅格点扩散搜索．本文最后研究了该方法在栅格圆环、圆盘及球面、球等生成及Euclid距离变换中的应用．     

插值方法对GIS土壤养分插值结果的影响

精准农业技术的应用越来越受到大家的关注,通过对一个地块土壤养分进行详细栅格采样化验分析,利用反距离法和克里格(Kriging)两种不同计算机插值方法对土壤中各种营养元素进行了分析研究。在采样栅格大小不同的条件下,随机选择5个采样点插值,分析对比了5个采样点在不同栅格采样条件下利用两种插值方法的插值结果。通过插值计算得到土壤中全氮、速效氮和速效磷在采样栅格较小的情况下,由于反距离法考虑的周围点数较多,插值点处的插值误差要较克里格插值总体上来讲误差小,而随着采样栅格距离的加大,克里格插值的误差要小于反距离法插值的误差。     

显著性特征保持的点云模型缩放

为了对现有三维模型的尺寸进行自适应调整以满足具体应用的需求,提出一种基于能量线抽取的显著性特征保持的点云模型缩放算法.首先为输入点云模型指定上、下边界线,并采用距离演化方法在模型上计算出从上边界线到下边界线的距离场;然后依据曲面的局部显著性特征,采用动态规划算法计算出模型的能量场,根据能量场计算一条从上边界到下边界的最小能量曲线;最后将最小能量曲线上的点从模型中删除,并局部拼接完成模型的一次缩放.重复上述步骤,直至模型的尺寸符合要求.实验结果表明,该算法在达到缩放目的的同时既能较好地保护模型的显著区域,又能有效地解决现有方法在模型缩放过程中出现某些部分分辨率过高,导致产生视觉不自然甚至失真现象.     

平面NURBS曲线的等距线算法：圆弧法矢近似法

本文根据产生曲线的特征点与它的等距线的特征点的对应关系,给出了一种平面NURBS曲线的等距线表示方法——圆弧法矢近似法。这种方法的特点是:(1)等距线与产生曲线具有统一的NURBS表示;(2)计算简单、几何意义明确、近似精度高。     

基于拓扑相似性的等距参数曲面求交算法

等距曲面求交算法通常采用曲面求交算法反复迭代计算交线,没有考虑不同Offset距离等距曲面交线的相似性进行求交简化.提出了一种基于拓扑相似性的等距曲面求交优化算法.算法首先求取曲面的拓扑特征点,根据拓扑特征点分布图,确定交线环拓扑结构,在交线拓扑结构信息的指导下,确定初始点的搜索策略.采用提出的方法可以有效解决等距曲面的子环、奇点遗漏、分支跳跃、乱序跟踪和初始点求取问题,精确、鲁棒地计算出交线.     

基于虚拟高度投影线的三维重建及误差补偿

针对传统三维重建方法计算复杂度高的问题,提出一种基于虚拟高度投影线的三维重建方法。该方法将场景栅格化,在栅格中引入虚拟高度线,把虚拟高度线投影到二维图像上形成投影线,并在投影线上找到对应点得到三维场景信息,以反映场景的真实信息。分析引起误差的主要来源,针对误差来源结合摄像机内外参数提出补偿方法。通过实验验证了该方法的有效性。     

用遗传算法生成NURBS曲线的等距线

提出一种生成NURBS曲线等距线的新方法,即从原始NURBS曲线求得一组精确NURBS等距点后,采用遗传算法对参数进行优化,提高等距线的逼近精度,优化目标函数为各精确等距点至逼近曲线的距离平方和取极小值,结果表明,遗传算法具有一定的优越性。     

基于局部邻域多流形度量的人脸识别

针对人脸识别中特征的提取,提出了一种基于局部邻域多流形度量的人脸识别方法。针对人脸识别的小样本问题,用特征脸对人脸图像预处理。对预处理后的人脸数据集中每个流形内的数据点采用欧氏距离来选择各数据点的近邻点,由此得到局部权重矩阵,并计算重构数据点与原始数据点之间的误差距离;同时,采用图像集建模流形,用affine hull表示流形对应的数据集信息,计算多流形间的距离度量矩阵。通过最大化流形间距离以及最小化数据点与重构数据点误差距离来寻找投影降维矩阵。在人脸数据集上的大量比较实验,验证了该方法的准确性和有效性。     

基于MapReduce的加权Voronoi图并行算法设计及应用

针对大规模数据的加权Voronoi图实现的复杂性和计算精度低问题, 采用欧氏距离法, 设计和实现了一种基于MapReduce编程模型的并行栅格加权Voronoi图的生成算法, 并将其成功应用于石家庄桥东区超市的推荐服务。该算法计算精度高, 同时可适用于任意点、线、面及复合发生元的加权Voronoi图的计算。实验结果表明, 算法在处理大规模栅格数据时能明显提高栅格Voronoi图的生成速度, 并能为用户推荐综合因素优选的超市。     

基于一元对称幂基的等距曲面有理逼近算法

给出了基于一元对称幂基的等距曲面蒙面逼近新算法。利用一元对称幂基逼近张量积Bézier曲面u向曲线的等距曲线,得到一组等距逼近曲线,取固定的v值,得到一组数据点,用反算控制顶点的方法得到过这组数据点的v向曲线。对这两组曲线用蒙面算法得到逼近的有理等距曲面。该算法计算简单,将二元等距曲面有理逼近转化为一元曲线有理逼近,同时方便地解决了整体误差问题,随着对称幂基阶数的升高,可以得到较理想的逼近效果。     

Design and implementation of maple packages for processing offsets and conchoids

In this paper we present two packages, implemented in the computer algebra system Maple, for dealing with offsets and conchoids to algebraic curves, respectively. Help pages and procedures are described. Also in an annex, we provide a brief atlas, created with these packages, and where the offset and the conchoid of several algebraic plane curves are obtained, their rationality is analyzed, and parametrizations are computed. Practical performance of the implemented algorithms shows that the packages execute in reasonable time; we include time cost tables of the computation of the offset and conchoid curves of two rational families of curves using the implemented packages.     

An interpolator forN-TH-order curves

A method is presented that allows to generate curves of any order; it can be implemented with a very simple interpolator circuit—making use of counters and adders only—or can be used for writing a computer program. The interpolation is fast and accurate, the error (i.e. the distance of the approximated curve from the ideal) being limited and depending solely on the interpolation step. In particular, an interpolator for cubic curves is described.     

A grid generator for 3-D explosion simulations using the staircase boundary approach in Cartesian coordinates based on STL models

In this paper, an automatic grid generator based on STL models is proposed. The staircase boundary treatment is implemented to handle irregular geometries and the computation domain is discretized using a regular Cartesian grid. Using the grid generator, staircase grids that are suitable for fast and accurate finite difference analysis could be generated. Employing the slicing algorithm in RP technologies [1], the STL models are sliced with a set of parallel planes to generate 2D slices after the STL files obtained from a CAD system undergo topology reconstruction. To decrease the staircase error (increase accuracy) and enhance working efficiency, the cross-section at the middle of the layer is taken to represent the cross-section of whole layer. The scan line filling technique of computer graphics [2] is used to achieve grid generation after slicing. Finally, we demonstrate an application of the introduced method to generate staircase grids, which allows successful FDM simulation in the field of explosion. The example shows that the automatic grid generator based on STL models is fast and gives simulation results that are in agreement with practical observations.     

Offset of curves on tessellated surfaces

Geodesic offset of curves on surfaces is an important and useful tool of computer aided design for applications such as generation of tool paths for NC machining and simulation of fibre path on tool surfaces in composites manufacturing. For many industrial and graphic applications, tessellation representation is used for curves and surfaces because of its simplicity in representation and for simpler and faster geometric operations. The paper presents an algorithm for computing offset of curves on tessellated surfaces. A curve on tessellation (COT) is represented as a sequence of 3D points, with each line segment of every two consecutive points lying exactly on the tessellation. With an incremental approach of the algorithm to compute offset COT, the final offset curve position is obtained through several intermediate offset curve positions. Each offset curve position is obtained by offsetting all the points of COT along the tessellation in such a way that all the line segments gets offset exactly along the faces of tessellation in which the line segments are contained. The algorithm, based entirely on tessellation representation, completely eliminates the formation of local self-intersections. Global self-intersections if any, are detected and corrected explicitly. Offset of both open and closed tessellated curves, either in a plane or on a tessellated surface, can be generated using the proposed approach. The computation of offset COT is very accurate within the tessellation tolerance.     

Polyline approach for approximating Hausdorff distance between planar free-form curves

This paper presents a practical polyline approach for approximating the Hausdorff distance between planar free-form curves. After the input curves are approximated with polylines using the recursively splitting method, the precise Hausdorff distance between polylines is computed as the approximation of the Hausdorff distance between free-form curves, and the error of the approximation is controllable. The computation of the Hausdorff distance between polylines is based on an incremental algorithm that computes the directed Hausdorff distance from a line segment to a polyline. Furthermore, not every segment on polylines contributes to the final Hausdorff distance. Based on the bound properties of the Hausdorff distance and the continuity of polylines, two pruning strategies are applied in order to prune useless segments. The R-Tree structure is employed as well to accelerate the pruning process. We experimented on Bezier curves, B-Spline curves and NURBS curves respectively with our algorithm, and there are 95% segments pruned on approximating polylines in average. Two comparisons are also presented: One is with an algorithm computing the directed Hausdorff distance on polylines by building Voronoi diagram of segments. The other comparison is with equation solving and pruning methods for computing the Hausdorff distance between free-form curves.     

Offsetting operations on non-manifold topological models

This paper describes non-manifold offsetting operations that add or remove a uniform thickness from a given non-manifold topological model. The mathematical definitions and properties of the non-manifold offsetting operations are investigated first, and then an offset algorithm based on the definitions is proposed and implemented using the non-manifold Euler operators proposed in this paper. In this algorithm, the offset elements of minimal size for the vertices, edges and faces of a given non-manifold model are generated first. Then, they are united into a single body using the non-manifold Boolean operations. In order to reduce computation time and numerical errors, the intersections between the offset elements are calculated considering the origins of the topological entities during union. Finally, all topological entities that are within the offset distance are detected and removed in turn. In addition to the original offset algorithm based on mathematical definitions, some variant offset algorithms, called sheet thickening and solid shelling, are proposed and implemented for more practical and efficient solid modeling of thin-walled plastic or sheet metal parts. In virtue of the proposed non-manifold offset operation and its variations, different offsetting operations for wireframes, sheets and solids can be integrated into one and applied to a wide range of applications with a great potential usefulness.     

基于三步逼近的BD2高精度快速捕获算法研究

针对BeiDou-2（BD2）卫星导航软件接收机捕获模块中捕获精度低和运算量大的问题,提出了一种基于三步逼近的高精度快速捕获算法。算法采用变步长的三步逼近方法逐步缩小多普勒频移搜索范围,快速得到了精确的初始码相位和多普勒频偏;利用频率圆周移位方法,在第一步搜索以一次乘法代替FFT操作,较大地减少了捕获模块的运算负担。实验结果证明,该算法捕获的伪码偏移精确、载频偏移误差在100 Hz以内,且最优情况下的运算量比传统的并行码相位捕获算法平均减少了70.56%,运算效率高。     

Numerical solution of reactive-diffusive systems

Four time linearization techniques and two operator-splitting algorithms have been employed to study the propagation of a one-dimensional wave governed by a reaction-diffusion equation. Comparisons amongst the methods are shown in terms of the L ²-norm error and computed wave speeds. The calculations have been performed with different numerical grids in order to determine the effects of the temporal and spatial step sizes on the accuracy. It is shown that a time linearization procedure with a second-order accurate temporal approximation and a fourth-order accurate spatial discretization yields the most accurate results. The numerical calculations are compared with those reported in Parts 1 and 2. It is concluded that the most accurate time linearization method described in this paper offers a great promise for the computation of multi-dimensional reaction-diffusion equations.     

Hierarchical line integration

This paper presents an acceleration scheme for the numerical computation of sets of trajectories in vector fields or iterated solutions in maps, possibly with simultaneous evaluation of quantities along the curves such as integrals or extrema. It addresses cases with a dense evaluation on the domain, where straightforward approaches are subject to redundant calculations. These are avoided by first calculating short solutions for the whole domain. From these, longer solutions are then constructed in a hierarchical manner until the designated length is achieved. While the computational complexity of the straightforward approach depends linearly on the length of the solutions, the computational cost with the proposed scheme grows only logarithmically with increasing length. Due to independence of subtasks and memory locality, our algorithm is suitable for parallel execution on many-core architectures like GPUs. The trade-offs of the method--lower accuracy and increased memory consumption--are analyzed, including error order as well as numerical error for discrete computation grids. The usefulness and flexibility of the scheme are demonstrated with two example applications: line integral convolution and the computation of the finite-time Lyapunov exponent. Finally, results and performance measurements of our GPU implementation are presented for both synthetic and simulated vector fields from computational fluid dynamics.     

An offset algorithm for polyline curves

Polyline curves which are composed of line segments and arcs are widely used in engineering applications. In this paper, a novel offset algorithm for polyline curves is proposed. The offset algorithm comprises three steps. Firstly, the offsets of all the segments of polyline curves are calculated. Then all the offsets are trimmed or joined to build polyline curves that are called untrimmed offset curves. Finally, a clipping algorithm is applied to the untrimmed offset curves to yield the final results. The offset algorithm can deal with polyline curves that are self-intersection, overlapping or containing small arcs. The new algorithm has been implemented in a commercial system TiOpenCAD 8.0 and its reliability is verified by a great number of examples.