Special Spline Approximation in CAD Systems of Linear Structure Routing

摘要

This article deals with the problem of approximation of plane curves defined by a sequence of points by a spline of a given type. This task arises when developing methods for computer-aided design of linear structures: railways and roads, trenches for laying pipelines, canals, etc. Its fundamental differences from the problems are considered in the theory of splines and its applications are as follows: spline elements are of various types (straight line segments and circles joined by clothoids), the boundaries of the elements and even their number is unknown; also there are restrictions - inequalities on the parameters of the elements. Continuity of the curve, the tangent, and the curvature is provided. Clothoids are missing if curvature continuity is not required, for example, when designing pipelines. The above mentioned features of the task do not allow using the achievements of the theory of splines and nonlinear programming. We cannot recognize the individual elements of the desired spline by a given sequence of points. Therefore, it is not possible to implement their selection separately. We must search for the spline as a whole. The article presents a mathematical model and a new algorithm for solving the problem using dynamic programming.