In maliput_sparse we describe line string as a collection of points. These line strings are used in order to define the boundaries of the lane (left line, centerline and right line).
The use of brute force algorithm for retrieving the closest point or interpolating a given segment of the linestring has a negative impact in the performance, mainly, when the line string is defined with a dense number of points
Queries
Typically, for a given p value in the centerline, it is needed to be found the equivalent ps in the laterals.
For getting this information we should resolve the following geometrical queries:
From P to XYZ
Given a linestring, we often need to find the interpolated xyz value for a given p value.
Get the closest interpolated point for a given xyz
From an inertial position XYZ we might want to find:
Closest interpolated point - in Inertial frame.
Closest p coordinate
Bounding points, in this example C and D that contains the equivalent p of XYZ
Summary
https://github.com/maliput/maliput_sparse/issues/47 and https://github.com/maliput/lanelets_eval/pull/43 have evidenced that the query time could be improved.
Context
In
maliput_sparsewe describe line string as a collection of points. These line strings are used in order to define the boundaries of the lane (left line, centerline and right line).The use of brute force algorithm for retrieving the closest point or interpolating a given segment of the linestring has a negative impact in the performance, mainly, when the line string is defined with a dense number of points
Queries
Typically, for a given
pvalue in the centerline, it is needed to be found the equivalentps in the laterals.For getting this information we should resolve the following geometrical queries:
From P to XYZ
Given a linestring, we often need to find the interpolated
xyzvalue for a givenpvalue.Get the closest interpolated point for a given xyz
From an inertial position
XYZwe might want to find:pcoordinatepofXYZAlternatives to brute force algorithm