Gradient algorithms for polygonal approximation of convex contours

The subjects of this paper are descent algorithms to optimally approximate a strictly convex contour with a polygon. This classic geometric problem is relevant in interpolation theory and data compression, and has potential applications in robotic sensor networks. We design gradient descent laws for intuitive performance metrics such as the area of the inner, outer, and “outer minus inner” approximating polygons. The algorithms position the polygon vertices based on simple feedback ideas and on limited nearest-neighbor interaction.     

An algorithm for polygonal approximation of a digital object

A fast and simple heuristic algorithm for polygonal approximation is presented. The algorithm is based on a mark and sweep technique. Results of computer implementation with various images are reported.     

Fast polygonal approximation of digitized curves

We describe a new technique for fast “scan-along” computation of piecewise linear approximations of digital curves in 2-space. Our method is derived from earlier work on the theory of minimum-perimeter polygonal approximations of digitized closed curves.We demonstrate the specialization of this technique to the case where the error is measured as the largest Hausdorff-Euclidean distance between the approximation and the given digitized curve. We illustrate the application of this procedure to the boundaries of the images of a lung and a rib in chest radiographs.     

Ant colony search algorithms for optimal polygonal approximation of plane curves

This paper presents a new polygonal approximation method using ant colony search algorithm. The problem is represented by a directed graph such that the objective of the original problem becomes to find the shortest closed circuit on the graph under the problem-specific constraints. A number of artificial ants are distributed on the graph and communicate with one another through the pheromone trails which are a form of the long-term memory guiding the future exploration of the graph. The important properties of the proposed method are thoroughly investigated. The performance of the proposed method as compared to those of the genetic-based and the tabu search-based approaches is very promising.     

Optimal polygonal approximation of digitized curves using the sum of square deviations criterion

We address the problem of finding an optimal polygonal approximation of digitized curves. Several optimal algorithms have already been proposed to determine the minimum number of points that define a polygonal approximation of the curve, with respect to a criterion error. We present a new algorithm with reasonable complexity to determine the optimal polygonal approximation using the mean square error norm. The idea is to estimate the remaining number of segments and to integrate the cost in the A^* algorithm. The solution is optimal in the minimum number of segments.     

Moment-based methods for polygonal approximation of digitized curves

Object shape representation plays an important role in the area of image processing, pattern recognition and computer vision. In the past two decades, many algorithms have been suggested for creating approximated polygons. In this study, two new polygonal approximation methods based on the geometric moments and the orthogonal moments defined in terms of Legendre polynomials are proposed. The difference between the moments defined by the initial contour and those of the approximated polygon is taken as the objective function. Each algorithm provides various polygonal approximation results with different number of line segments for different application situations. For a given error bound, we can determine the optimal polygon with a minimum number of line segments. The procedures are applied to some digital curves and better results are obtained in comparison with some known methods.     

An efficient evolutionary algorithm for accurate polygonal approximation

An optimization problem for polygonal approximation of 2-D shapes is investigated in this paper. The optimization problem for a digital contour of N points with the approximating polygon of K vertices has a search space of C(N, K) instances, i.e., the number of ways of choosing K vertices out of N points. A genetic-algorithm-based method has been proposed for determining the optimal polygons of digital curves, and its performance is better than that of several existing methods for the polygonal approximation problems. This paper proposes an efficient evolutionary algorithm (EEA) with a novel orthogonal array crossover for obtaining the optimal solution to the polygonal approximation problem. It is shown empirically that the proposed EEA outperforms the existing genetic-algorithm-based method under the same cost conditions in terms of the quality of the best solution, average solution, variance of solutions, and the convergence speed, especially in solving large polygonal approximation problems.     

An O(N) algorithm for polygonal approximation

A new, sequential algorithm for polygonal approximation of plane, closed curves is presented. It runs in O(N) time and is based on a tolerance independent of the scale factor.     

Polygonal approximation of closed discrete curves

Optimal polygonal approximation of closed curves differs from the case of open curve in the sense that the location of the starting point must also be determined. Straightforward exhaustive search would take N times more time than the corresponding optimal algorithm for an open curve, because there are N possible points to be considered as the starting point. Faster sub-optimal solution can be found by iterating the search and heuristically selecting different starting point at each iteration. In this paper, we propose to find the optimal approximation of a cyclically extended closed curve of double size, and to select the best possible starting point by search in the extended search space for the curve. The proposed approach provides solution very close to the optimal one using at most twice as much time as required by the optimal algorithm for the corresponding open curve.     

Point placement algorithms for Delaunay triangulation of polygonal domains

In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.     

On stop conditions about methods to obtain polygonal approximations relied on break point suppression

In this work, we propose a new unsupervised stop condition for heuristic methods that employ break point suppression to obtain polygonal approximations. Using a stop condition, these heuristic methods delete redundant break points until a required level of approximation is satisfied. The new stop condition is based on the optimisation of the F₂ measure. Comparisons with original stop conditions of several methods show that the new stop condition yields a measurable improvement in the approximation. The polygonal approximations obtained with the new stop condition are more efficient and better adjusted to the original contours. The new stop condition can be combined with supervised optimal methods to obtain a reference approximation of the original contour with a minimum number of points. In this case, the resulting methods are unsupervised methods.     

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.     

Robust adaptive polygonal approximation of implicit curves

We present an algorithm for computing a robust adaptive polygonal approximation of an implicit curve in the plane. The approximation is adapted to the geometry of the curve because the length of the edges varies with the curvature of the curve. Robustness is achieved by combining interval arithmetic and automatic differentiation.     

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.     

A new measurement for assessing polygonal approximation of curves

This paper presents a novel method for assessing the accuracy of unsupervised polygonal approximation algorithms. This measurement relies on a polygonal approximation called the “reference approximation”. The reference approximation is obtained using the method of Perez and Vidal [11] by an iterative method that optimizes an objective function. Then, the proposed measurement is calculated by comparing the reference approximation with the approximation to be evaluated, taking into account the similarity between the polygonal approximation and the original contour, and penalizing polygonal approximations with an excessive number of points. A comparative experiment by using polygonal approximations obtained with commonly used algorithms showed that the proposed measurement is more efficient than other proposed measurements at comparing polygonal approximations with different number of points.     

Circle approximation using integral B-splines

A method to approximate a circular arc of any sweep angle with integral B-spline curves of any degree is presented. The idea is to interpolate end derivatives as well as some internal points with integral B-splines of given degree and continuity. The critical element is the choice of the right end derivative directions and magnitudes. The points and the derivatives at these locations are sampled uniformly using the trigonometric equation of the circle. The method is very general in that any degree and any level of parametric continuity can be specified.     

Simultaneous inner and outer approximation of shapes

For compact Euclidean bodiesP, Q, we define (P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy . HeresQ denotes a scaling ofQ by the factors, andQ,Q are some translates ofQ. This function gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.)For integerk 3, define (k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with (P, Q) (k). Among other results, we prove that 2.118 ... <-(3) 2.25 and (k) = 1 + (k ^–2). We give anO(n ² log² n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes (T, P) among triangles. However, in linear time we can find a trianglet with (t, P)<-2.25.Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.Work of all authors was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). Rudolf Fleischer and Kurt Mehlhorn acknowledge also DFG (Grant SPP Me 620/6). Chee Yap acknowledges also DFG (Grant Be 142/46-1) and NSF (Grants DCR-84-01898 and CCR-87-03458). This research was performed when Günter Rote and Chee Yap were at the Freie Universität Berlin.     

Biarc approximation of NURBS curves

An algorithm for approximating arbitrary NURBS curves with biarcs is presented. The main idea is to approximate the NURBS curve with a polygon, and then to approximate the polygon with biarcs to within the required tolerance. The method uses a parametric formulation of biarcs appropriate in geometric design using parametric curves. The method is most useful in numerical control to drive the cutter along straight line or circular paths.