Design Proposal: Add 'polyline' as a supported source type

[mbalfour-amzn]

Summary

This proposal is to add 'polyline' as a first-class supported source type with MapLibre (for both GL JS and Native) so that compressed polyline data can be passed in directly as a source.

Introduction

Various map service providers - Google, Mapbox, HERE, Stadia Maps, OSRM, Valhalla, etc - have routing APIs that return geometry in a compressed polyline format. There are two general patterns that map renderers use for handling these responses:

1. Bespoke renderers provide an API that directly accepts the response and handles it internally - Mapbox, Google
2. For APIs that aren't tied to a renderer, the user calls a decode method first to turn the polyline into a LineString or GeoJSON, and then passes the result into the renderer.

Since MapLibre isn't tied to a specific service API, developers using MapLibre currently need to follow pattern 2. While this isn't terribly burdensome, it's an extremely common pattern that developers need to follow, and it requires them to spend some time learning about compressed polylines, finding the right library dependency for decoding, and adding it to their project.

Proposal

This proposal is to add 'polyline' as a first-class supported source type with MapLibre (for both GL JS and Native) so that compressed polyline data can be passed in directly as a source. All of the examples above use one of the following compressed polyline variations:

1. Polyline5 / Polyline6. This takes in a fixed number of bits of precision, which appears to always either be 5 or 6 in practice.
2. Flexible-polyline. This supports a variable number of bits of precision, encoded into the string, and also uses an improved character mapping to avoid the need for escaped characters.

Both variants come from the same underlying algorithm - Encoded Polyline Algorithm Format.

Without polyline support, users' code currently looks like this:

<script type="text/javascript" src="https://unpkg.com/@mapbox/polyline"></script>
...
    const testPolyline = "ccq~FpxzuO_GewBjMa{@br@}ZvcAgCtlAvo@~E`{@u{AppAarBzK";
    var polylineJson = polyline.toGeoJSON(testPolyline, 5);

    map.addSource("route", {
        type: "geojson",
        data: {
            type: "Feature",
            properties: {},
            geometry: polylineJson,
        },
    });

With 'polyline' as a source, the usage simplifies to the following:

        const testPolyline = "ccq~FpxzuO_GewBjMa{@br@}ZvcAgCtlAvo@~E`{@u{AppAarBzK";
        map.addSource("route", {
            type: "polyline",
            encoding: "polyline5",  // This would be "polyline5", "polyline6", or "flexible-polyline"
            data: testPolyline,
        });

With this proposal, we would support all 2 (or 3?) known variations via the encoding parameter. The choice of an encoding parameter is aligned with the current "raster-dem" source type that uses an encoding field to distinguish between Mapbox and Terrarium encodings. This also opens the door to adding more encodings over time if necessary.

Benefits

The primary benefit is to lower the developer friction of using API calls that return compressed polylines with MapLibre. Specifically:

1. The external library / import / dependency is removed
2. The data conversion call is removed
3. The need to package the converted data into a stub GeoJSON is removed

Concerns

This proposal has been informally brought up to the community to get initial feedback. These are the concerns that have been raised so far:

1. Library size. How much size will the added support cost?
2. "Slippery Slope". Will adding these formats lead to more requests for other format support across MapLibre?
3. Maintenance cost. How much maintenance burden will this add?
4. Variations. Since there isn't a single standard, do we need to support multiple variations?
5. Datatype is too low-level. Since this describes line geometry, as opposed to being a full geodata format, does the decoding support belong elsewhere?

I am raising this as a formal proposal to see if the community feels the Benefits outweigh the Concerns.

Opinions

My opinions about the concerns:

1. Library Size. I believe this will add at most 1000 - 2000 lines of code (excluding unit tests). This estimate is based on flexible-polyline which has 203 LoC for both encode and decode. We would only need decode. It is also based on geojson_source.ts in the MapLibre codebase which has 427 LoC.
2. "Slippery Slope". The formal Discussion / Approval process should be used to evaluate each request separately. The community should choose to only accept proposals on their own merits.
3. Maintenance Cost. The flexible-polyline format (the newest of the formats) hasn't been changed in 5 years, so the likelihood of ongoing maintenance costs due to format changes seems extremely low. The higher likelihood would come from any choices internal to MapLibre around the Source interface definition and how a Source is used.
4. Variations. While there are 2 (or 3?) variations listed here, they all stem from the same base algorithm, so the likelihood of more radical variations showing up over time seem low. i.e. This is more like supporting PNG, and then PNG with an additional chunk type, as opposed to supporting PNG / JPEG / GIF / BMP / etc.
5. Datatype is too low-level. The concept of "Source" doesn't seem to inherently dictate a level of data support. For example, image (a single image) could be considered a lower-level subset of raster (a TileJSON set of images). If supporting this level of data is beneficial to developers, I would encourage us to consider it.

[thehoneymad]

Love the proposal here. ❤️

The size of the library may not be a significant concern if this can be implemented as a plugin. Users have the flexibility to install and use the plugin when needed. Regarding the Polyline spec, assuming MapLibre settles on one specific version to maintain, it is unlikely that there will be extensive changes or even any notable alterations.

I personally think, if MapLibre takes this journey, it should pick 1 variant keeping the door open to support others by the MapLibre users.

[mbalfour-amzn]

There's extremely little code difference between polyline5/6 and flexible-polyline since they're the same base algorithm, which is why I'd propose supporting both from the start. If we only support one, anyone who adds support for the other one externally will effectively just cut-n-paste the one we added and then change it a bit, which seems unnecessary.

[thehoneymad]

That is a good point and makes sense to me too.

After talking internally a bit, it sounds like a pre-baked solution is the one that benefits the general population over a plugin.

[1ec5]

Consider reaching out to the developers of Turf.js to get their opinion as well. From what I’ve seen, MapLibre GL JS + Turf.js is a very popular combination, and something similar happens to a lesser extent on mobile platforms. Not every use case for Polyline geometry encoding or decoding involves an interactive map, so maybe putting this functionality in Turf would result in a more versatile overall experience for developers. Coordination between these projects would head off potential conflicts, such as differing default precision values, or other ergonomic issues.

[ianthetechie]

From what I’ve seen, MapLibre GL JS + Turf.js is a very popular combination, and something similar happens to a lesser extent on mobile platforms.

it is a popular combination, but only if you're doing certain sorts of maps. I have personally only ever needed Turf.js on a handful of occasions. I've never used Turf on mobile that I can recall 😂

Not every use case for Polyline geometry encoding or decoding involves an interactive map

Good point. If you're building a non-interactive map, then static map images are usually a better fit IMO. Every map vendor I can think of supports the fixed precision polyline for overlays in their API (and I think most allow you to choose 5 or 6 digit precision).

Coordination between these projects would head off potential conflicts, such as differing default precision values, or other ergonomic issues.

heh ;) This is a perennial source of confusion. It's a recurring support request at Stadia Maps 😂 Valhalla and valhalla-based services (like our routing API, and I think Mapbox's) default to 6. Google chose 5. Every code library I can think of defaults to 5. We defaulted our APIs to 6 (which is why we get occasional confused inquiries), but that's because our APIs return polyline6, so it makes sense.

For a general purpose library, I'd default to 5 and make a clear note in the docs that you need to check your source precision.

[1ec5]

For completeness, I’m referring to the following mobile libraries, which were originally developed by Mapbox:

• Turf for Java
• Turf for Swift (not yet forked but still open-source)

Turf for Java is part of the MapLibre-Java suite of libraries, which also includes a publicly accessible Polyline encoder and decoder. But if I’m not mistaken, these MapLibre libraries are used only by navigation libraries such as the MapLibre Navigation SDK for Android, not by any map library.

[ianthetechie]

But if I’m not mistaken, these MapLibre libraries are used only by navigation libraries such as the MapLibre Navigation SDK for Android, not by any map library.

Yeah, that's correct as far as I know. And for good reason. It's a lot to add if you don't need it (most apps don't; I'm not sure if MapLibre Navigation needs most of Turf to be honest. I think all of that belongs in a platform-independent core, not in separate platform-specific libs when talking specifically about a navigation SDK).

[1ec5]

Turf for Swift is a misnomer. It has a lot of overlap with Turf.js, but really it’s just whatever geometry functionality the iOS navigation SDK needs but doesn’t need in its core, including GeoJSON and WKT decoding that has never been part of Turf.js. Keeping this library separate from both the map and navigation SDKs has enabled its use in projects that don’t even involve interactive maps or turn-by-turn navigation, and developers get to use a simple pure Swift library instead of complicating the build system to involve C++ or Rust. Fortunately, if you use the Swift Package Manager, Turf gets statically linked, so any unused functionality gets stripped out at build time. I think something similar can happen on Android depending on the build configuration.

[1ec5]

I’m curious about the choice to define polyline as a source type rather than providing a utility function to convert between Polyline encoding and GeoJSON. This would cut out an extra step, but it would also encourage a proliferation of minimally distinct source types. For example, if someone proposes support for Well-Known Text (WKT) support, which can represent the full set of geometries that MapLibre supports, then they would have to propose it as another source type, for consistency, rather than as another utility function.

For comparison, there are existing source types for image, vídeo, and raster-dem. This makes it possible for MapLibre to support multiple image, video, and DEM formats without complicating the style spec. Unlike these source types, geojson is tied to one format; it can’t logically support KML data. But each geodata format requires such a distinct set of options that perhaps this specificity is unavoidable.

[ianthetechie]

Yeah, I think that including a utility function to decode is all that's strictly necessary in order to be useful IMO.

[mbalfour-amzn]

A utility function inside of MapLibre would solve the discoverability problem, though it still leaves the extra function call. IMO the discoverability problem is the larger problem of the two though, so I can see the value in going this route if people don't like the extra source type idea but are still supportive of adding this into MapLibre. I suppose probably somewhere like src/util/polyline.ts? Maybe polylineToGeoJSON(polyline, encodingType)?

[HarelM]

Thanks for taking the time to open this design proposal!

You have summarized the discussion on slack well and I believe you covered most of what was mentioned there, thanks again.

I have also suggested to solve this by simply documenting the solution you have suggested by highlighting the relevant libraries for decoding etc.

When I look at the concept of style spec and the fact that this compression is mostly used for routing I believe it should not be part of this library.
Routing is dynamic in most cases and defining a source that will fetch routing data for a constant url doesn't seem like a valid solution.
The linked mapbox library is actually mapbox directions, which is a routing library on top of mapbox. Maplibre has a similar fork and I definitely think this decoding should be part of that library.

My perspective is that if you already need to code the routing request, adding the conversion to geojson is not a complicated task.

To summarize my main concern: a static polyline source is cumbersome.

[ianthetechie]

The linked mapbox library is actually mapbox directions, which is a routing library on top of mapbox. Maplibre has a similar fork and I definitely think this decoding should be part of that library.

Yup. It is, as far as I can remember. Ferrostar takes a similar approach, embedding it in the core and automatically deserializing route geometries.

Side note: most open-source routing solutions have standardized on OSRM's data model (with some small extensions for banners and voice prompts by Mapbox which are now a de facto standard for all major FOSS engines), and it uses the polyline encoding (can be 5 or 6 digits of precision). The original post says that this is a bespoke rendering + API solution, but it is not with Mapbox. Mapbox Navigation just deserializes the polyline and turns it into a layer (or 2 or 3); same as you'd do with MapLibre.

[1ec5]

The Mapbox/MapLibre Navigation SDK also uses the decoded route geometry to snap the user’s location to the route line, calculate the user’s progress along the current step, detect when the user has departed from the route, and much more. It would have little reason to use a dedicated polyline source, because on the native platforms, there’s no in-memory type difference between a decoded GeoJSON LineString and a decoded Polyline.

[ianthetechie]

Exactly. All the geometry operations like snapping, off route detection, and maneuver progress (for banners and voice prompts) operate on a LineString geometry. And adding it to the map is trivial after decoding the geometry.

[ianthetechie]

Here are my 2 cents on a few points. Note that I'll try to highlight the native perspective, since all discussion so far has been about JS.

TL;DR I'd be in favor of having polyline decoding directly in MapLibre. I'm neutral on whether we need to add it as a first-class style spec thing. I think that a utility function would suffice.

Plugins

I love the idea. But MapLibre only sorta has a plugin architecture on the JS side. If there was a good plugin story, then I'd say a plugin could add a new layer type. This would make the job of the developer building a user-facing app slightly easier. But they would still have to grab a plugin ;)

My opinion is that the Google encoded polyline format is so ubiquitous that it's probably worth keeping in the core, and it should be quite light. This is actually the first time I've heard of the HERE flexible polyline, but if it's not much to add, then that's also fine.

Maintenance and size

Both specs are stable and have been for a very long time. There will not be any changes to it; only perhaps "superseding" specs (like flexible polyline) off the same principle.

The implementation probably shouldn't need to depend on a GeoJSON generator library, so size should be very small. All you need is a list of coordinates to draw the polyline in MapLibre, at least on mobile. Maybe there is some reason I'm missing to convert to GeoJSON specifically, but this would be like... idk only one line of actual code? It's so simple and mechanical; you just need the boilerplate structure, and the geometry is just the list of coordinates (the output of the decode function) mapped into an array, ensuring the correct coordinate order.

[HarelM]

Not sure what you mean by "sorta" plugin architecture, but I believe writing a plugin that uses addProtocol or import script to workers should be a fairly easy task.
If this plugin is widely used we should consider adding it as a first class.
If the answer to the above is that this plugin would have only like 10 lines of code (which I believe should be about right) then as I said, an example would also be sufficient.

[mbalfour-amzn]

FWIW, I've given this a try with addProtocol. The usability feels a little weird to me personally vs having a source type, but it's certainly an option. I tried looking at addSourceType as well to see about using it instead but couldn't figure out how to get that one to work.

For reference, here's the PoC code and usage. Production-level code would have error handling, etc.

    // Setup - create the flexpolyline custom protocol.
    maplibregl.addProtocol('flexpolyline', async (params, abortController) => {
        function flipped(coords) {
            var flipped = [];
            for (var i = 0; i < coords.length; i++) {
                var coord = coords[i].slice();
                flipped.push([coord[1], coord[0]]);
            }
            return flipped;
        }

        const polyline = params.url.split("://")[1];
        var coords = decode(polyline);
        var flippedLine = flipped(coords.polyline);
        var lineGeoJSON = {
            type: 'Feature',
            properties: {},
            geometry: {
                type: 'LineString',
                coordinates: flippedLine,
            }
        };

        return Promise.resolve({data : lineGeoJSON});
    });

    // Example usage. The compressed polyline would normally come from some API response structure.
    map.on("load", () => {
    const flexPolyline = "BFkky_Hx572QgIm4DrOi8BjzB-b3kCoE1tC3wB_Gh8B28CxxCizD7M";
    map.addSource("route", {
        type: "geojson",
        data: "flexpolyline://" + flexPolyline
    });

[wipfli]

Thanks for the proposal @mbalfour-amzn. To me it looks like the effect you would like to have for your users could be done with a more convenient polyline wrapper outside of MapLibre GL JS:

We could do...

const testPolyline = "ccq~FpxzuO_GewBjMa{@br@}ZvcAgCtlAvo@~E`{@u{AppAarBzK";

myPolylineWrapper.addSourceToMap(map, "route", testPolyline, 5);

...where myPolylineWrapper.addSourceToMap() just executes the code you have in your first example:

function addSourceToMap(map, source, data, encoding) {
    var polylineJson = polyline.toGeoJSON(data, encoding);

    map.addSource(source, {
        type: "geojson",
        data: {
            type: "Feature",
            properties: {},
            geometry: polylineJson,
        },
    });
}

What do you think?

[mbalfour-amzn]

Yeah, this could definitely be implemented as a helper outside of MapLibre. That's the path I would likely take if we don't add this directly to MapLibre. I wanted to pursue this proposal first though to see if the community thought it was a worthwhile addition, and because it improves the problem of helper/plugin/package discoverability. As @HarelM has pointed out, this is where additional documentation would help no matter what route we go.

[karussell]

If this plugin is widely used we should consider adding it as a first class.

As one of the GraphHopper maintainers I would recommend to not put this into maplibre and just stick to geojson.

E.g. Google uses precision=5 but often this is not sufficient and some services like ours support also a higher precision (as mentioned above valhalla does so too). Also the lat,lon could be expanded by another third dimension (elevation) like we do if explicitly requested, so I would keep this and the associated hassle out of the core library :)