Sharp error bounds for piecewise linear interpolation of planar curves

Curves are commonly drawn by piecewise linear interpolation, but to worry about the error is rather seldom. In the present paper we give a strong mathematical error analysis for curve segments with bounded curvature and length. Though the result seems very clear, the proof turned out to be unexpectedly hard, comparable to that of the famous four vertex theorem.     

Error-bounded biarc approximation of planar curves

Presented in this paper is an error-bounded method for approximating a planar parametric curve with a G¹ arc spline made of biarcs. The approximated curve is not restricted in specially bounded shapes of confined degrees, and it does not have to be compatible with non-uniform rational B-splines (NURBS). The main idea of the method is to divide the curve of interest into smaller segments so that each segment can be approximated with a biarc within a specified tolerance. The biarc is obtained by polygonal approximation to the curve segment and single biarc fitting to the polygon. In this process, the Hausdorff distance is used as a criterion for approximation quality. An iterative approach is proposed for fitting an optimized biarc to a given polygon and its two end tangents. The approach is robust and acceptable in computation since the Hausdorff distance between a polygon and its fitted biarc can be computed directly and precisely. The method is simple in concept, provides reasonable accuracy control, and produces the smaller number of biarcs in the resulting arc spline. Some experimental results demonstrate its usefulness and quality.     

Qualitative analysis by piecewise linear approximation

This paper describes a computer program called PLR that derives the qualitative behavior of ordinary differential equations. Current qualitative reasoning programs derive the abstract behaviour of a system by simulating hand-crafted ‘qualitative’ versions of the differential equations that characterize the system and summarizing the results. PLR infers more detailed information by constructing and analysing piecewise linear approximations of the original equations. The analysis employs the phase space representation of dynamic systems theory. PLR constructs a phase diagram for a system of piecewise linear equations by partitioning phase space into regions in which the system is linear, analysing the linear systems, and combining the results. It pastes together the local analyses into a global phase diagram by determining which sequences of regions the trajectories can traverse. The current implementation of PLR only handles second-order systems, but the method extends to higher-order systems. As an example of PLR's performance, I present its analyses of the Lienard and van der Pol equations.     

Knot placement for piecewise polynomial approximation of curves

For piecewise polynomial representation of curves, an algorithm to create knots is presented. The aim is to minimize the interpolation error for a given number of knots or, conversely, the number of knots needed to interpolate within a tolerance. The method used is a modification of de Boor's knot placement scheme. The algorithm described in this paper has been realized in the CADCAM system SYRKO, a Daimler-Benz development for car body design and manufacturing.     

Null controllability of planar bimodal piecewise linear systems

This article investigates the null controllability of planar bimodal piecewise linear systems, which consist of two second order LTI systems separated by a line crossing through the origin. It is interesting to note that even when both subsystems are controllable in the classical sense, the whole piecewise linear system may be not null controllable. On the other hand, a piecewise linear system could be null controllable even when it has uncontrollable subsystems. First, the evolution directions from any non-origin state are studied from the geometric point of view, and it turns out that the directions usually span an open half space. Then, we derive an explicit and easily verifiable necessary and sufficient condition for a planar bimodal piecewise linear system to be null controllable. Finally, the article concludes with several numerical examples and discussions on the results and future work.     

改进的超越函数分段线性逼近方法

针对超越函数计算中所采用的分段线性逼近算法存在的无法提前确定精度及部分区间资源浪费的问题,提出一种改进的分段线性逼近超越函数算法。该算法由预定义的逼近区间端点计算出用于逼近的线性函数,根据被逼近函数的凹凸性对所计算线性函数进行调整,在此基础上计算出预定义逼近区间内调整后函数与被逼近函数之间的最大误差;按照所需精度的要求,自动调整逼近区间,通过该过程的迭代,获得了较少分段次数。算法结果在Matlab上进行仿真,仿真结果表明,所提算法的分段数相比等分法减少了60%。所提算法在保证精度的前提下,降低了查找表（LUT）的资源消耗。     

A piecewise linear approximation based on a statistical model

A statistical model is introduced and then, based on it, a piecewise linear approximation algorithm of linear computational complexity is presented. The advantages of the algorithm are proved experimentally in small sample cases and theoretically in the large sample case. The paper is closed with a discussion on some possible extensions.     

Statistical monitoring of nonlinear profiles by using piecewise linear approximation

In many practical situations, the quality of a process, or product, is better characterized and summarized by the relationship between a response variable and one or more explanatory variables. Such a relationship between the response variable and explanatory variables is called a profile. Recently, profile monitoring has become a fertile research field in statistical process control (SPC). To handle the nonlinear profile data, the proposal considered in this paper is that the entire curve is broken into several segments of data points that exhibit a statistical fit to the linear model, and therefore each of them can be monitored separately by using existing linear profile SPC methods. A new method that determines the locations of change points based on the slop change is proposed. Two goodness-of-fit criteria are utilized for determining the best number of change points to avoid over-fitting. Two nonlinear profile examples taken from the literature are used to illustrate the proposed change-point model. Monitoring performances using the existing T² and EWMA-based approaches are presented when the nonlinear profile data is fitted by using the proposed change-point model.     

Polygonal approximation of digital planar curves through break point suppression

This paper presents a new algorithm that detects a set of dominant points on the boundary of an eight-connected shape to obtain a polygonal approximation of the shape itself. The set of dominant points is obtained from the original break points of the initial boundary, where the integral square is zero. For this goal, most of the original break points are deleted by suppressing those whose perpendicular distance to an approximating straight line is lower than a variable threshold value. The proposed algorithm iteratively deletes redundant break points until the required approximation, which relies on a decrease in the length of the contour and the highest error, is achieved. A comparative experiment with another commonly used algorithm showed that the proposed method produced efficient and effective polygonal approximations for digital planar curves with features of several sizes.     

Polygonal approximation of planar curves in the L 1 norm

An algorithm for obtaining a polygonal approximation in the L ₁, norm of a plane curve of arbitrary shape is presented. The L ₁ error norm in any segment is not to exceed a pre-assigned value. The given curve is first digitized and the algorithm is then applied to the discrete points. The algorithm uses linear programming techniques which makes it efficient and fast. Numerical results and comments are given.     

Synthesis of 2D curves by blending piecewise linear curvature profiles

A new algorithm for fitting a smooth curve through two datapoints, to meet specified tangent direction and curvature requirements at these datapoints, is described. The algorithm produces a piecewise linear curvature profile, thus the resultant curve consists of parts of Cornu spirals. It does this by blending some basic forms defined in the paper. A FORTRAN program based on this algorithm can provide many substantially different solutions to any given problem. It can either be incorporated in a linear curvature spline package or used in an interactive system for designing spans or splines.     

Piecewise linear approximation of plane curves by perimeter optimization

A method for the piecewise linear approximation of a plane curve is described. An approximate curve is obtained by choosing a certain number of points from a set of sampled points of the original curve. A “point choice function” that represents the relation between the original points and the chosen points is formulated. The approximation is performed by the dynamic programming principle searching for the optimal point choice function that attains the minimal error about arc length of the curve. Evaluation of the global approximate error provides efficient curve approximations, irrespective of shape complexity, number of sampled points, and irregularity of sampling interval.     

A piecewise linear approximation method preserving visual feature points of original figures

We present a method for piecewise linear approximation of digitized planar curves which can compress the amount of data, without loss of perceptual information for human approximation. This method consists of two stages, the uniform process and the recovering process. The method has the following four major merits: (1) Because this method approximates according to the intricacy, it can efficiently approximate figures in which portions of both large and small curvatures coexist. (2) Spikes and corners can be retained. (3) Smooth connecting points are retained. (4) Straight lines in the original figure are directly adopted as approximating line segments. Because of the above merits, our method is applicable to both natural and artificial figures.     

A new subdivision based approach for piecewise smooth approximation of 3D polygonal curves

This paper presents an algorithm dealing with the data reduction and the approximation of 3D polygonal curves. Our method is able to approximate efficiently a set of straight 3D segments or points with a piecewise smooth subdivision curve, in a near optimal way in terms of control point number. Our algorithm is a generalization for subdivision rules, including sharp vertex processing, of the Active B-Spline Curve developed by Pottmann et al. We have also developed a theoretically demonstrated approach, analysing curvature properties of B-Splines, which computes a near optimal evaluation of the initial number and positions of control points. Moreover, our original Active Footpoint Parameterization method prevents wrong matching problems occurring particularly for self-intersecting curves. Thus, the stability of the algorithm is highly increased. Our method was tested on different sets of curves and gives satisfying results regarding to approximation error, convergence speed and compression rate. This method is in line with a larger 3D CAD object compression scheme by piecewise subdivision surface approximation. The objective is to fit a subdivision surface on a target patch by first fitting its boundary with a subdivision curve whose control polygon will represent the boundary of the surface control polyhedron.     

Planar piecewise algebraic curves

An approach is described for piecing together segments of planar algebraic curves with derivative continuity. The application of piecewise algebraic curves to area modelling (the two-dimensional analogue of solid modelling) is discussed. A technique is presented for expressing a planar rational parametric curve as an algebraic curve segment. An upper bound is derived for the farthest distance between two algebraic curves (one of which may also be a parametric curve) within a specified region.     

Sketching piecewise clothoid curves

We present a novel approach to sketching 2D curves with minimally varying curvature as piecewise clothoids. A stable and efficient algorithm fits a sketched piecewise linear curve using a number of clothoid segments with G² continuity based on a specified error tolerance. Further, adjacent clothoid segments can be locally blended to result in a G³ curve with curvature that predominantly varies linearly with arc length. We also handle intended sharp corners or G¹ discontinuities, as independent rotations of clothoid pieces. Our formulation is ideally suited to conceptual design applications where aesthetic fairness of the sketched curve takes precedence over the precise interpolation of geometric constraints. We show the effectiveness of our results within a system for sketch-based road and robot-vehicle path design, where clothoids are already widely used.     

Energy-based multi-view piecewise planar stereo

The piecewise planar model (PPM) is an effective means of approximating a complex scene by using planar patches to give a complete interpretation of the spatial points reconstructed from projected 2D images. The traditional piecewise planar stereo methods suffer from either a very restricted number of directions for plane detection or heavy reliance on the segmentation accuracy of superpixels. To address these issues, we propose a new multi-view piecewise planar stereo method in this paper. Our method formulates the problem of complete scene reconstruction as a multi-level energy minimization problem. To detect planes along principal directions, a novel energy formulation with pair-wise potentials is used to assign an optimal plane for each superpixel in an iterative manner, where reliable scene priors and geometric constraints are incorporated to enhance the modeling efficacy and inference efficiency. To detect non-principal-direction planes, we adopt a multi-direction plane sweeping with a restricted search space method to generate reliable candidate planes. To handle the multi-surface straddling problem of a single superpixel, a superpixel sub-segmenting scheme is proposed and a robust Pⁿ Potts model-like higher-order potential is introduced to refine the resulting depth map. Our method is a natural integration of pixel- and superpixel-level multi-view stereos under a unified energy minimization framework. Experimental results for standard data sets and our own data sets show that our proposed method can satisfactorily handle many challenging factors (e.g., slanted surfaces and poorly textured regions) and can obtain accurate piecewise planar depth maps.