8

Sorry if this is a late interference. This is an awesome discussion. I’ve read that with great curiosity.
I’d like to point out a couple of potential problems I see with lanelet2. I’m speaking from personal experience as we are using in-house made mapping system very similar to lanelet.
Lanelet is a geo-points based solution, meaning that map lines (road sides, road marking lines, stop lines e.t.c.) represented by a set of points (https://github.com/fzi-forschungszentrum-informatik/Lanelet2/blob/master/lanelet2_core/doc/LaneletPrimitives.md).
With this kind of representation performance of some basic map operations will not be satisfactory.
Let me give examples:

  1. One of basic operations: Defining if a geo-point is within specific lanelet. This task boils down to the checking if the point is inside the polygon defined by points of linestrings forming lanelet. This is a standard algorithm and it requires O(N) operations where N is a number of points in polygon. So checking single point is O(N) and in typical driving situation such check happens hundreds of times per second which loads CPU badly. We certainly do some precomuptation/caching to mitigate the load but problem is still there.
  2. Another basic operation: For a geo-point, find closest point on the linestring. In general case it requires iterating all the points inside the linestring, meaning O(N) and again this operation is executed very often while driving.

If I have task to redesign the system from scratch now. I’d seriously consider using vector(polynomial) representation of linestring instead of approximated breadcrumb points. It’s more complicated math for sure, but if done right, I believe it can give you O(1) for those cases I described.

Hope it make sense and can help on final solution.

1 Like