Polyline Smoothing with Compound Bezier Splines

Vladimir A. Romakin

Abstract


The paper considers a new iterative method for constructing a smooth spline on a plane, consisting of cubic Bezier curves and repeating the shape of a given polyline with the required accuracy. At each iteration of the method, the following operations are performed: choosing the number of spline interpolation nodes, placing them on a given polyline according to certain rule, constructing a smooth compound Bezier spline passing through these nodes, and estimating the approximation accuracy, that is, the proximity of the constructed spline to a given polyline. The choice of the position of the spline interpolation nodes on a given polyline is performed by comparing the proximity measures of adjacent Bezier curves that make up the spline and the segments of the polyline that approximate these curves. The examples of smoothing polylines of varying complexity, including polylines with self-intersections, are given, confirming the effectiveness of the proposed method. The results of the work can be used in various applications, for example, when constructing the trajectory of automatic vehicles and mobile robots, when designing technical objects in computer-aided design systems, when performing cartographic generalization of linear cartographic objects, when designing fonts, etc.

Keywords


polyline smoothing; compound splines; Bezier curves; measure of proximity; interpolation; approximation

References


Hwang J.H., Arkin R., Kwon D. Mobile robots at your fingertip: Bezier curve on-line trajectory generation for supervisory control. Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003). Vol. 2. IEEE, 2003. P. 1444–1449. DOI: 10.1109/IROS.2003.1248847.

Ravankar A., Ravankar A.A., Kobayashi Y., et al. Path Smoothing Techniques in Robot Navigation: State-of-the-Art, Current and Future Challenges. Sensors. 2018. Vol. 18, no. 9. Article number 3170. DOI: 10.3390/s18093170.

Zhou F., Song B., Tian G. Bezier curve based smooth path planning for mobile robot. Journal of Information and Computational Science. 2011. Vol. 8, no. 12. P. 2441–2450.

Romakin V.A. Routing of fluidic circuits using skeletons of polygonal figures and compound splines. International Conference on Modern Trends in Manufacturing Technologies and Equipment (ICMTMTE 2021). Vol. 346. 2021. Article number 03060. DOI: 10.1051/matecconf/202134603060.

Berlyant A.M., Musin O.R., Sobchuk T.V. Cartographic generalization and fractal theory. Moscow, 1998. 136 p. (in Russian).

Musin O.R., Ukhalov A.Y., Edelsbrunner G., Yakimova O.P. Application of fractal and computational geometry methods for cartographic generalization of linear objects. Modeling and analysis of information systems. 2012. Vol. 19, no. 6. P. 152–160. (in Russian).

Sarfraz M., Khan M.A. Automatic Outline capture of Arabic fonts. Information Sciences. 2002. Vol. 140. P. 269–281. DOI: 10.1016/S0020-0255(01)00176-1.

Sohel F.A., Karmakar G.C., Dooley L.S. A generic shape descriptor using Bezier curves. International Conference on Information Technology: Coding and Computing (ITCC’05). Vol. 2. IEEE, 2005. P. 95–100. DOI: 10.1109/ITCC.2005.11.

Kodnyanko V.A. Directional Splines and Their Use for Smoothing Ejections and Fractures of Interpolant. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 1. P. 5–19. (in Russian) DOI: 10.14529/cmse210101.

Ho Y.J., Liu J.S. Collision-free curvature-bounded smooth path planning using composite Bezier curve based on Voronoi diagram. Proceedings of IEEE International Symposium on Computational Intelligence in Robotics and Automation. IEEE, 2009. P. 463–468. DOI: 10.1109/CIRA.2009.5423161.

Borisenko V.V. Construction of Optimal Bézier Splines. Journal of Mathematical Sciences. 2019. Vol. 237, no. 3. P. 375–386. DOI: 10.1007/s10958-019-04164-6.




DOI: http://dx.doi.org/10.14529/cmse220403