Dynamic Programming as a Method of Spline Approximation in the CAD Systems of Linear Constructions

Under study is a problem of the line structure routing of roads, railways and other linear constructions. Designing a trace plan and longitudinal profile are considered as non-linear programming tasks. Since the number of elements of the plan and the longitudinal profile is not known, the problem is solved in three stages. First, a search is performed for a polyline consisting of short elements. On the second stage it is used to determine the initial approximation of the desired line, which is optimized at the last stage. The required line consists of a given type elements and it is a spline with a number of features: - In contrast to the polynomial elements considered in the theory of splines, when designing roads unknown spline is a sequence of elements: straight, clothoid, circle, clothoid, straight and so on. - In this task, the spline does not have to be a single-valued function. - The parameters of the elements of the desired spline must satisfy the constraints in the form of inequalities. These features of the task do not allow the use of non-linear programming methods to solve it. Converting a broken line to a spline is carried out using dynamic programming. For this purpose a special formalization of this task is proposed. A new algorithm of dynamic programming is given. The result is used as an initial approximation to optimize the parameters of the spline using a previously developed non-linear programming program.