Combined approximation algorithms for interactive design of road routes in CAD

Abstract

Objectives. The aim of the work is to create algorithms for approximating a sequence of points on a plane by arcs of clothoids and circles. Such a problem typically arises in the design of railroad and highway routes. The plan (projection onto a horizontal plane) of the road route is a curve (spline) consisting of a repeating bundle of elements “straight line + clothoid arc + circle arc + clothoid arc + ...”. Such a combination of elements provides continuity not only for the curve and its tangent, but also for the curvature. Since the number of spline elements is not known in advance, and their parameters are subject to restrictions, there is no mathematically consistent algorithm for this problem. The two-stage scheme for solving the problem is developed at RTU MIREA only for a spline with lines and circles (i.e., without clothoid elements). At the first stage, the scheme uses dynamic programming to determine the number of spline elements. At the second stage, the scheme optimizes parameters of the spline using nonlinear programming. This scheme has yet to be implemented for a spline with clothoids due to a significantly more complicated nature of this problem. Therefore, the design of route plans in existing computer aided design (CAD) systems is carried out in interactive mode using iterative selection of elements. In this regard, it makes sense to develop mathematically consistent algorithms for element-by-element approximation.Methods. The problem of element-by-element approximation by a circle and a clothoid is formalized as a lowdimensional non-linear programming problem. The objective function is the sum of squared deviations from the original points. Since a clothoid can only be represented in Cartesian coordinates by power series, there are difficulties in calculating the derivatives of the objective function with respect to the desired parameters of the spline elements. The proposed mathematically consistent algorithm for calculating these derivatives is based on the integral representation of the Cartesian coordinates of the points of the clothoid as functions of its length.Results. A mathematical model and algorithms have been developed for approximating a sequence of points on a plane by clothoids and circles using the method of nonlinear programming. A second-order algorithm is implemented with the calculation and inversion of the matrix of second derivatives (Hesse matrix).Conclusions. For approximation by circles and clothoids using nonlinear programming, it is not necessary to have an analytical expression of the objective function in terms of the required variables. The proposed algorithms make it possible to calculate not only the first, but also the second derivatives in the absence of such expressions.

Keywords

• route plan
• spline
• non-linear programming
• clothoid
• objective function
• gradient
• hessian matrix