Proposal: Heatmap layer type

[mourner]

Motivation

Heatmap support is one of the most requested features for Mapbox GL, and an extremely common map visualization type, especially prevalent in weather, travel, fitness and social apps.

Heatmaps are typically used to visualize density of a point dataset. It's in a way similar to clustering, but with a very different look that shows areas points are crowded in very well.

Design Alternatives

Option A: Implement it as an external plugin

We could use the heatmaps use case to drive the design of custom layers API and custom sources API, both of which are not fleshed out yet, and then package it as an external plugin. The drawbacks of this approach are:

1. Heatmaps are a perfect candidate for a Mapbox Studio feature, since the process of designing them (picking the color ramp, adjusting radius, weights etc.) highly benefits from instant visual feedback. However, we can only add Studio features that seamlessly work across platforms without additional configuration and are a part of the style specification, so Studio won't be able to support heatmaps as a plugin.
2. The native plugin for heatmaps will have to be implemented independently, and we have no fleshed out plugin architecture on the native side either.
3. We want to reuse a lot of the existing Mapbox GL features such as functions, data-driven properties, clustering (very important for heatmapping big datasets), and (in near future) arbitrary expressions and property aggregations. Because of that, having to implement heatmaps as a plugin (and designing flexible enough custom layers/sources API) might be technically very difficult.
4. Heatmaps won't be available through the static maps API and the raster tile fallback.
5. It will likely be much harder to use compared to heatmaps as a core layer type.

Option B: colorize-alpha property

Prior discussion in #3182. The idea is to introduce a colorize-alpha property for existing layers like circle, then render the circles with blur as is and recolorize according to the specified color ramp that matches each pixel alpha value to a color. Drawbacks:

1. It's not a "true" heatmap as is. Mathematically, heatmap is a bivariate kernel density estimation). For a good result, you have to blend circles differently (with additive blending — ONE, ONE blend mode), and KDEs usually use a different sprite for each point — a Gaussian kernel, which may also look like a blurred circle but is still different.
2. This would mean introducing a lot of conditional code in circle drawing because of the need to render into a temporary framebuffer, then recolorizing and rendering a texture to the screen (instead of drawing circles directly).
3. It breaks down when you pitch the map, since circles in our rendering don't get the perspective distortion (they remain circles on screen, whether they scale with pitch or not).
4. Some circle properties don't make sense with colorize-alpha on — circle-stroke-*, circle- pitch-scale, circle-translate-*, and circle-blur should be always 1.0. Having these options makes heatmaps harder to use and easier to screw up.

This also feels very similar to the case of extrusion-related properties as a part of the fill type vs a separate fill-extrusion type. We chose the latter option, and I'm inclined towards the same in the choise of additional circle properties vs new heatmap layer type.

Design

Given considerations above, I propose to implement a new heatmap layer type in the core. It will have its own set of shaders and drawing code along other types. We'll be able to render either vector tile points, GeoJSON points or GeoJSON clusters as heatmaps, just like we do with circles.

The main drawback of this approach are code and specification bloat, since we are unlikely to remove a feature once we add it. I think the feature is important enough to justify being in the core, but not yet fully convinced — let's discuss.

Mock-Up

"type": "heatmap",
"paint": {
    "heatmap-radius": 30,
    "heatmap-color": {
        "colorSpace": "lab",
        "stops": [[0, "yellow"], [0.4, "green"], [1.0, "red"]]
    },
    "heatmap-weight": {
        "type": "identity",
        "property": "score"
    },
    "heatmap-max-weight": 100,
    "heatmap-opacity": 0.7,
    "heatmap-mode": "density"
}

• heatmap-radius: controls the radius of the kernel. The bigger the radius, the smoother the heatmap (but with less detail). Radius can be a zoom function.
• heatmap-color: the color ramp used for coloring pixels. Using stop functions for this is very convenient — you can make a smooth gradient, or a contour-like rendering using an interval function. The only weird thing about it is that the input stop values are pixel alpha values, not zoom, so this would be an outlier in the spec. Is this OK? And how would an equivalent function look in the arbitrary expressions proposal?
• heatmap-weight: for weighted heatmaps where each point has an importance score. 1.0 by default (all points are treated equally). Weight === 3.0 should be visually the same as having three 1.0-weight points in the same spot.
• heatmap-max-weight: a global layer property for scaling the heatmap intensity.
• heatmap-opacity: global heatmap layer opacity (applied to the final result).
• heatmap-mode: by default, heatmaps render according to point density (so two points in the same spot are twice as intense as one). But there are cases where we want a different behavior — imagine an air pollution map that shows measurements from spots around the country. Multiple measure points clustered close together shouldn't cause the area to appear many times more polluted compared to an area with the same pollution but only one measure spot. We could implement this behavior by introducing a property that governs the underlying blending GL equation (for the pollution case, we would use EXT_blend_minmax.MAX rather than GL_FUNC_ADD).

Implementation

The only way I've seen heatmaps implemented in the GPU is the same — draw a kernel ("blurred circle") for each point of the dataset with additive blending (storing the result in a temporary framebuffer), then colorize each pixel using a color ramp (based on alpha values). We'll have to use the same approach — I haven't found a more efficient one for the GPU.

As for performance, we have the advantage of being able to cluster points (which is already implemented), which enables us to render huge datasets as heatmaps on the client.

cc @kkaefer @anandthakker @ansis @1ec5 @ryanbaumann @peterqliu @mapbox/gl

Previous tickets: #3994 #3182

[kronick]

@mourner This sounds awesome. Your mock-up interface looks 💯

I played around with this a while back using a GLSL heatmap plugin in a canvas overlay tied to geographic points and map interactions.

I came across two ways of thinking about zoom functions and heatmaps:

• 
  The first way is the increase the radius in pixels of each point exponentially with the zoom level. This results in a constant picture regardless of zoom level, but it breaks down as you get really zoomed in and each point gets so big it's no longer part of the points loaded in the viewport. You start dropping data in a mysterious way. Performance also suffers as you draw bigger and bigger circles that need a bigger guassian blur. Drawbacks aside, this is my preferred method.

• 
  The second way is to have a fixed pixel radius for each point, regardless of zoom level. This results in a kind of lava lamp effect that's interesting, but ultimately feels more distracting than useful. Pros are that you get a sort of clustering effect for free, don't drop data that's outside the viewport as much, and performance is more predictable because the circle and blur radius is constant.

[andrewharvey]

but ultimately feels more distracting than useful

That second one sounds good. On the one map you can visualise a heat map at a continental scale, country scale, city scale, neighbourhood scale having the right amount of detail at each zoom. In the first approach you have not enough detail in the neighbourhood views and too much at the continental views.

There might be use cases for the 1st too, so ideally it would support both approaches?

[1ec5]

One use case for the first approach would be a radar map: you wouldn’t want the appearance of showers scattering as you zoom in.

[jfirebaugh]

Mathematically, I guess the first approach is equivalent to using a bandwidth parameter for the KDE that's independent of zoom level, while the second varies the bandwidth by zoom? Wouldn't the second be a misleading visualization? A heatmap implies that you are visualizing a sampled estimate of some continuous variable. Is there a situation where that estimate would vary depending on zoom level (other than making cool looking demos that don't ultimately have any meaning)?

[kronick]

Wouldn't the second be a misleading visualization? A heatmap implies that you are visualizing a sampled estimate of some continuous variable.

@jfirebaugh Agreed-- heatmaps already have a lot of potential to mislead depending on how you choose parameters. Keeping the visualization constant with view changes seems more "honest" to me.

On the one map you can visualise a heat map at a continental scale, country scale, city scale, neighbourhood scale having the right amount of detail at each zoom.

@andrewharvey When it comes to visualizing a dataset at a wide range of zoom levels, my conclusion from experimenting with heatmaps is that this is an area where they are not the best tool for the job. Clustering points is much better for this. Even better would be a heatmap at low zoom levels that fades into clustered or individual points after a certain threshold zoom.

This layer type could be configurable to go either way, but I would suggest we go with a constant geographic radius (option 1 above) as the default.

[ansis]

A heatmap implies that you are visualizing a sampled estimate of some continuous variable. Is there a situation where that estimate would vary depending on zoom level (other than making cool looking demos that don't ultimately have any meaning)?

Maybe: If the input is a loaded as a tiled dataset the resolution of the data will be different at different zoom levels. The higher the resolution of the input data, the smaller a kernel you can use.

Another maybe: You may want to generalize the estimate when visualizing it. A lower resolution version might be clearer than a high resolution one if it hides details that are unnecessary at that scale. Using a larger kernel to oversmooth the estimate would get you something in that direction, even if it isn't the most statistically valid way to do it.

---

questions

what would the input data for heatmaps look like?

• vector tiles? geojson?
• would it be points? clustered points with counts? a raster with counts?

how would the data be simplified/aggregated for low zoom levels?

• as a raster?
• by clustering before rasterization?

[mb12]

For point data visualizations what is really needed is the ability to
aggregate point data sets into geometries with attributes that can be analyzed. I've
included specific examples below:

1. A standard example of a point data set would be a set of elevation values.
   The best way to visualize this dataset is to transform it to a bunch of isolines
   with elevation values. One would typically create these isolines at a
   regular elevation interval. With such a representation, its very easy to visually identify places which are steep.

However this visualization does not help if you want to identify areas below a
certain elevation (e.g. below sea level). In those cases, you would want to
transfer this point data set to a bunch of polygons with elevation ranges. Once
such a polygon data set is created Mapbox GL can render polygons with
different elevation ranges using different colors.

2. Another example of a point data set would be pressure values at different locations.
   You would want to visualize this data set as a set of pressure zones, with
   high and low pressure zones highlighted with different colors.

This approach generalizes well with point data sets in other domains as well.

1. A point data set of household incomes can be transformed to zones of
   different income levels and visualized with Mapbox GL.

2. A point data set of political party affiliations can be used to create a
   set of zones that a candidate running for election could use to prioritize
   places to visit before an election!!

Most applications do this processing on the server side at the moment. It
would be really nice if this capability were built into Mapbox GL.

[mourner]

Is there a situation where that estimate would vary depending on zoom level (other than making cool looking demos that don't ultimately have any meaning)?

@jfirebaugh I don't think heatmap visualization has to be perceived solely as a geospatial analysis tool, which would mean showing mathematically correct results that depend on physical distances between points. The other purpose of a heatmap (which pretty much all mapping heatmap plugins adhere to) is being a purely visual cue to help navigate a crowded dataset, which has to adapt to zoom to remain useful. Clustering is similar in that regard — it's mathematically meaningless, but you won't be able to browse a million points without it with good performance, and it makes browsing the data much easier.

So I'd like to support both cases by allowing the user to pick either a constant value or a zoom function (exponential base-2 for constant bandwidth). It would help if the latter had some kind of an easy alias in the new expressions API, rather than having to do something unintuitive like {stops: [[10, 1],[22, 4096]], base: 2}.

@mb12 what you're describing is a different feature — not kernel density estimation (heatmap), but multivariate interpolation. It requires a very different family of algorithms (such as Inverse Distane Weighting), and is computationally much more expensive and technically more difficult to do on the client. Let's keep this thread focused on heatmaps.

[ansis]

What if at the rendering stage heatmaps were just a regular raster layer that gets colourized? (and interpolated between zooms before colorization if you want to be fancy). Heatmap creation could be handled at the source level just like marker clustering is. I haven't thought through this, but it might be worth considering. I think @mb12 was hinting at supporting different kinds of data-level transforms before reaching the rendering stage.

[mourner]

@ansis this might be a good approach for interpolation, which is static, but probably not the best fit for heatmaps because we wouldn't be able to change heatmap radius / max weight / etc. dynamically.

[anandthakker]

we wouldn't be able to change heatmap radius / max weight / etc. dynamically.

@mourner why not? GeoJSONSource has setData, and more generally I definitely envision that dynamic/updatable sources will be a requirement of the custom source API (and, therefore, of our data source architecture). Not necessarily advocating for the source-based approach, just flagging that this particular constraint probably wouldn't be a dealbreaker.

[ansis]

@ansis this might be a good approach for interpolation, which is static, but probably not the best fit for heatmaps because we wouldn't be able to change heatmap radius / max weight / etc. dynamically.

The raster tiles produced for different zoom levels could have different radiuses, max weights which means they don't have to be zoom-constant. Changing the values via the runtime api would be slower than with your proposed implementation but this isn't a common thing. It would be similar to changing the cluster radius. Rendering might be faster since with the raster approach each pixel gets shaded only once.

[mourner]

@anandthakker @ansis I mean 60-fps dynamic changes, animation — just like we can do for circle radius and color. Also, the colorizing part is not the bottleneck — drawing kernels is (it's O(n * radius^2) rather than O(pixels)), and CPU-based calculation will simply be way too slow in this case compared to GPU rendering. So I don't think your proposed approach will work.

[ansis]

mean 60-fps dynamic changes, animation — just like we can do for circle radius and color

What's the case dynamically animating kernel size? I'm not sure this is the right thing to optimize for. Or are you thinking of animating the point data underlying the heatmap?

drawing kernels is (it's O(n * radius^2)

Yep, in the proposal this is a per-frame cost. If it's moved to where tiles are loaded and updated, it becomes a less frequent cost. The webgl approach to generating a heatmap you describe could be used to create these rasters.

[mourner]

@ansis to support smooth zooming in the screen-based kernel use case (no. 2 in @kronick's comment). Otherwise user experience will be noticeably worse — equivalent to using raster map tiles compared to vector maps. Another reason is being able to animate DDS points smoothly after we introduce DDS animations (which are in the roadmap) — tying ourselves to CPU-based raster approach will make this impossible.

[bjornreppen]

I would like to see support for something ala .PNG raster tiles as a data source for the heat map. Each pixel value in the matrix containing the "count" for the "area" covered by the pixel. The .png could contain 8-bit "grayscale" (0-255) values or up to 32-bit values if required.

The vector (array of coordinates / geojson) variant might not be feasible for huge datasets, and the raster approach might work nicely in a shader program?

[mourner]

@anandthakker @ansis to address your code/spec bloat concerns: my current plan is to finish a proof of concept PR with a new core type to have something to play and experiment with; once we have this, we'll be able to see what works and what doesn't in terms of the behavior and customization, and see if we can design an extension API for a potential plugin around it instead if we decide not to pursue a core type.

[ansis]

@mourner sounds good! I agree that this seems like a good thing to have in the core mapbox gl.

[ghost]

@mourner I don’t want to interfere in your technical discussion, but from an end-user perspective I am very excited to read that you are going to make a proof a concept with a chance that this will end up in your core code or made available as a plugin. Like you said, heatmap is a very common and nice way to present clustering and we get many requests for this feature from our customers (we provide a viewer solution to the utility market via GE as reseller and we based it on the mapbox technology). So sounds very good and keep up the good work, you all make very cool stuff!

[mourner]

For anyone wondering, here's a little preview of heatmaps in Mapbox GL JS: https://www.mapbox.com/blog/heatmaps-preview/

[keyofj]

@mourner This is the last piece to our implementation of mapbox gl replacing Google maps. Is there a roadmap to a release date of adding the heatmap feature?

[stevewillard]

@mourner Is there a branch where I can try out this new layer? Thanks for your work on this, it looks great!

[mourner]

@stevewillard should be up in a few days, stay tuned for new pull requests!

[mourner]

Hey everyone, sorry for the delay! Just open a work in progress PR here: #5253. Still a lot of small things to handle (captured in the checklist), but generally it's looking good.

[stevewillard]

@mourner The heatmap layer is working great. One that that I couldn't figure out from the PR was changing the color stops - is this configurable?

[mourner]

@stevewillard yes, with heatmap-color property using stop functions:

"heatmap-color": {
    "stops": [
        [0, "blue"],
        [0.5, "yellow"],
        [1, "red"]
    ],
    "default": "rgba(0, 0, 0, 0)" // temporary hack, will not be needed when PR is ready
}

[stevewillard]

Hmm for some reason my stops aren't overriding the default colors. I'm probably doing something wrong.

I'm also noticing that when I resize the map (or browser) the heatmap layer doesn't redraw properly:

[Scarysize]

Hmm for some reason my stops aren't overriding the default colors. I'm probably doing something wrong.

I don't have this issue. The stops should range from 0 to 1 I'd imagine.

I'm also noticing that when I resize the map (or browser) the heatmap layer doesn't redraw properly

I have observed this too, just by accident though :/

[mourner]

Yeah, I'm aware of the resizing bug — on my list. Another issue you may also notice is that sometimes heatmaps will flicker.

[wangchen9074]

Why doesn't my heatmap show?My circle point can. But the type:heatmap can't.

[mourner]

@wwangchen can you make a minimal JSFiddle to demonstrate your problem? Have you looked at the official example?

[wangchen9074]

Yes. the error is : Error: layers.heat0.type: expected one of [fill, line, symbol, circle, fill-extrusion, raster, background], heatmap found
at Function.module.exports.emitErrors (webpack-internal:///652:325)

[mourner]

@wwangchen are you sure you're using the latest GL JS release (0.41.0)?

[wangchen9074]

Thank you. I am not using the latest GL JS.

[mushon]

Hi @mourner, any plans to add heatmap controls to the style editor?

[songololo]

@mourner, in your original proposal (first post above) you suggested the possibility of a heatmap-mode setting for situations where colour should not be affected by density, only by value.

I'm wondering if this was subsequently considered any further or if there are any suggested workflows for achieving this sort of behaviour with the current implementation?

Thanks.

[sanchexx]

@songololo I was looking for exactly that feature when I found that thread.

@mourner We're also wondering if there is a feature in progress to use heatmap based on value, instead of density. We tried mapping our value to the 'weight' property, but the density always take over, with no way to cancel it out.

[songololo]

@sanchexx pending the heatmap discussion: in the interim it works quite well to use a circle with blurring enabled (assuming a large radius). If pinning the radius to zoom and the colour to the magnitude, then it will give a heatmap-like effect.

[sanchexx]

Thanks @songololo . That's actually what we started playing around with, which seem to be giving results.

Started experimenting with a mix of blur & opacity, and adding varying radius according to the amount of points. The only thing I don't like is that it still seem like a bunch of circles interlacing a bit, not as smooth a as a heatmap. But better than nothing!

Can you explain what you meant by pinning the radius to the zoom? Like having a step function that define circle radius on zoom level? Any example of what worked well for you? Might be something worth considering :)

[songololo]

@sanchexx this is the pattern I'm using, hope it is helpful:

{
  'circle-radius': [
    'interpolate',
    ['exponential', 1.5],
    ['zoom'],
    13, 0,
    14, 10,
    20, 500
  ],
  'circle-color': [
    'interpolate',
    ['linear'],
    ['get', 'some_val'],
    0, 'rgba(33,102,172,0)',
    0.2, 'rgb(103,169,207)',
    0.4, 'rgb(209,229,240)',
    0.6, 'rgb(253,219,199)',
    0.8, 'rgb(239,138,98)',
    1, 'rgb(178,24,43)'
  ],
  'circle-blur': 0.75,
  'circle-opacity': 1,
  'circle-stroke-width': 0
}

PS: I'm intentionally reducing and fading-out the points below a zoom level of 14, so in most cases the zoom should probably extend lower and with less fading...!

[songyuyang0918]

Dear developers, I tried to make the data of MultiPolygon into a heatMap, but I found that the heatmapWeight doesn't work. I can be sure that the data contains the values of the relevant Settings.
Does it only support point production now?

[mourner]

@songyuyang0918 yes, only points are supported.

[songyuyang0918]

@mourner Thank you for your reply. My current data is the WFS service of geoserver, which may be of various types such as point,Polygon and line. Do you have any good ideas based on this?
For example: how to use a third-party plug-in for turning points?
I'm using the ios SDK