Approximation Figures of Complex Geometric Shapes Using the Docking

V. D. Avvakumov, Associate Professor, e-mail: awwam@mail.ru, Novouralsk Technological Institute of the National Research Nuclear University MEPhI

We consider the problem of constructing approximate figures (simple shapes and the convex hull) for figures of complex geometric shapes. Simple shapes are convex n-gon and the circle; both convex hull and complex shapes can be composed of line segments and circular arcs.

The need for approximation arises in solving problems with geometric shapes figures organize complex shape figures (nesting problem): for simple shapes it is much faster to check the conditions of their non intersection. Constructing convex hulls is a very important procedure in many applications not only in itself, it can be part of other algorithms using this procedure as a component.

The first section contains the definitions used in this article: the well-known and introduced by the author. The basic concept is introduced among the arrays of discrete-continuous representation of the sidebar containing the coordinates of the connection points of contour elements and, if the contour has the arcs of their centers.

The second section describes the methodological basis for solutions of approximation algorithms and the method of forming the source data. Methodological basis for the proposed algorithms is a method of docking developed by the author. This method allows to find data for the algorithms constructing desired shapes: a discrete representation of the supporting function for the construction of simple shapes and a plurality of contact points of the of supporting line with the figure for finding the convex hull.

The third section is devoted to the construction of simple approximate figures. In general, for finding an approximating n-gon two procedures (primary and secondary) are used. The first (coarse) approximation of the n-gon is determined by the initial procedure. The application of secondary procedure allows an exact solution.

A plurality of contact points, obtained by joining is a discrete representation of the convex hull because all contact points got in accordance with the algorithm are those of the contour. However, this set contains a significant amount of redundant information. The fourth section describes an algorithm for obtaining arrays of discrete-continuous contour representation of the convex hull based on a plurality of contact points.

Method of dimensional tolerances application of the original figure with its approximation is presented in the fifth section. The substantiation of the need to consider the tolerances in solving problems of placing objects on the plane is given. Calculations show that the inclusion of tolerance can increase the area of approximating figures by up to 30 %.

The results of algorithms work for obtaining approximating figures are arrays of discrete-continuous representation of the contour. Such representation of the contour allows to build simple and universal algorithms for flat figures in solving location problems.

There is an example in which the figures are given for some approximate figures.

The results presented in this article may be used in applications where it is required to solve the problem of locating geometric objects: computer graphics, pattern recognition and image processing, computer-aided design and manufacturing processes.

Keywords: approximation, the figure of complex geometric shapes, simple figures, convex hull, contour, algorithms, continuous-discrete representation of the contour, nesting, supporting line, tolerance on size

pp. 39–48