A technique for the intersection of two splines of clothoid curves is herein presented. The study is motivated by the motion planning problem for a nonholonomic automated robotic vehicle, where a clothoid spline represents the path of the robot and the presence of an intersection with the path of another robot or with some obstacles boundaries means a possible collision. The algorithm works by segmenting each spline into small tangent triangles and then by organising the resulting, possibly large, number of triangles in a tree structure to exploit an efficient hierarchical check for intersections. Among various possible tree structures, the AABB tree is selected, which is a balanced choice between the complexity of the construction and the cost of evaluation, and avoids the need for extensive comparisons between each pair of clothoid segments that compose the splines. Indeed, only on pairs of intersecting triangles the collision is checked at curve level. This reduction of the computational cost yields an algorithm that can be effectively applied to real time applications.

Efficient intersection between splines of clothoids / Bertolazzi, E.; Bevilacqua, P.; Frego, M.. - In: MATHEMATICS AND COMPUTERS IN SIMULATION. - ISSN 0378-4754. - STAMPA. - 176:(2020), pp. 57-72. [10.1016/j.matcom.2019.10.001]

Efficient intersection between splines of clothoids

Bertolazzi E.;Bevilacqua P.;Frego M.
2020

Abstract

A technique for the intersection of two splines of clothoid curves is herein presented. The study is motivated by the motion planning problem for a nonholonomic automated robotic vehicle, where a clothoid spline represents the path of the robot and the presence of an intersection with the path of another robot or with some obstacles boundaries means a possible collision. The algorithm works by segmenting each spline into small tangent triangles and then by organising the resulting, possibly large, number of triangles in a tree structure to exploit an efficient hierarchical check for intersections. Among various possible tree structures, the AABB tree is selected, which is a balanced choice between the complexity of the construction and the cost of evaluation, and avoids the need for extensive comparisons between each pair of clothoid segments that compose the splines. Indeed, only on pairs of intersecting triangles the collision is checked at curve level. This reduction of the computational cost yields an algorithm that can be effectively applied to real time applications.
Bertolazzi, E.; Bevilacqua, P.; Frego, M.
Efficient intersection between splines of clothoids / Bertolazzi, E.; Bevilacqua, P.; Frego, M.. - In: MATHEMATICS AND COMPUTERS IN SIMULATION. - ISSN 0378-4754. - STAMPA. - 176:(2020), pp. 57-72. [10.1016/j.matcom.2019.10.001]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11572/266151
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact