search

motis-project / motis

Intermodal Mobility Information System
https://motis-project.de
MIT License
194 stars 47 forks source link

compressed polylines #455

Open GerdC opened 5 months ago

GerdC commented 5 months ago

RE issue #452 Motis potential

There are multiple ways to compress polylines.

Often Googles compressed polyline format is used. It is efficient, proven, and there are libraries in many languages supporting it.

There are reasons to extend this format, like HERE did with flexible-polyline: https://github.com/heremaps/flexible-polyline (MIT license). Standard application of this format is to compress elevation for each coordinate in the polyline.

(When ORS is told to return a polyline with elevation, it uses this format, which to my knowledge is undocumented apart from these decoder implementations: https://giscience.github.io/openrouteservice/api-reference/endpoints/directions/geometry-decoding I wouldn't seriously consider this format)

Also, routers like GraphHopper and OpenRouteService have an additional way to add properties to a polyline (more properties than would fit into HEREs flexible-polyline)

Their idea is the following. Let's take steepness as an example: They return a structure that says: from polyline index 7 to index 13, the steepness id is 1, meaning a steepness between 4% and 7%.

Different modes have different properties that are interesting for them. While for walking and bike, the steepness is interesting, for cars it is interesting if it is a toll road. Examples for such properties are in this ORS documentation: https://giscience.github.io/openrouteservice/api-reference/endpoints/directions/extra-info/

GraphHoppers/ORSs idea can be combined with polyline and with flexible-polyline.

These are the options I came across using real world routing APIs.

felixguendling commented 5 months ago

This depends on software that is not really part of MOTIS (only linked as a library or in the future used as third-party API). Since we might evolve the MOTIS API protocol, we can still keep this issue here.

mlundblad commented 5 months ago

RE issue #452 Motis potential

There are multiple ways to compress polylines.

Often Googles compressed polyline format is used. It is efficient, proven, and there are libraries in many languages supporting it.

Is this the same as EPAF, right? This is what we currently support in GNOME Maps (the format used in GraphHopper and OpenTripPlanner).

GerdC commented 5 months ago

Never heard of EPAF before, but this Gnome code implements EPAF and a few lines later links to Googles polyline documentation: https://mail.gnome.org/archives/commits-list/2022-August/msg02657.html So yes, EPAF should be identical with Googles polyline format.

mlundblad commented 5 months ago

Never heard of EPAF before, but this Gnome code implements EPAF and a few lines later links to Googles polyline documentation: https://mail.gnome.org/archives/commits-list/2022-August/msg02657.html So yes, EPAF should be identical with Googles polyline format.

Yeah, I don't remember exactly where this code came from originally, I think it might be borrowed from another project, so not actually sure what EPAF stood for, but yeah the link suggest Google.