Cities can look and feel very different depending on how they were planned and built, and this is especially apparent when you explore them from above, on a map. Some cities strictly align to a grid, others seem like they grew without any structure, and in some cases, patterns only appear when you examine a city more closely, with each neighborhood having their own distinct style. Could we visualize these patterns?

Seth Kadish and recently Geoff Boeing showed one great way to do this. They divided 360° into a set of orientation ranges, counted how many road segments belong to each range, and produced a polar histogram that gives us a profound insight into the street pattern of each particular city:

When I saw this, I was hooked instantly— what an ingenious way to look at how a city is built! But I wanted to explore more. How would such a chart look for my city, Kyiv? Or for some of my favorite but lesser known places? How would different neighbors of the same city compare? Or, on a larger scale, how would a European road network compare to the one in the US?

Extracting and processing the road data for every place of interest to generate a polar chart seemed like too much work. Could I do it on an interactive map? It turns out that this is a perfect use case for Mapbox vector maps — since the map data is there on the client, we can analyze and visualize it instantly for any place in the world. Play with the map below to see it in action!

Update: just discovered that the same idea of an interactive map was explored in 2014 by Ben Lowe. His demo no longer works unfortunately, but I’m glad I found it!

How I built it

The full app is about 80 lines of code. After initializing the map, we set it up to update the visualization every time we move it:

map.on('load', function () {
    updateOrientations();
    map.on('moveend', updateOrientations);
});

In the update routine, we can fetch all the roads on the screen with a single line of code, getting the results in GeoJSON format for easy processing:

var features = map.queryRenderedFeatures({layers: ['road']});

To make sure we only visualize road segments that we actually see, not including parts of roads that go off the view, we use a tiny library called lineclip to clip every road feature to the current bounding box:

var clippedLines = [];
for (var j = 0; j < lines.length; j++) {
  clippedLines.push.apply(clippedLines, lineclip(lines[j], bbox));
}

Calculating orientations and lengths for every road segment can be expensive if there are hundreds of thousands of them in our view. So we use cheap-ruler, a library for very fast approximations of geodesic calculations like this:

var ruler = cheapRuler(map.getCenter().lat);
...
for (var i = 0; i < line.length - 1; i++) {
  var bearing = ruler.bearing(line[i], line[i + 1]);
  var distance = ruler.distance(line[i], line[i + 1]);
  ...

For every road segment, we calculate the “bin” it belongs to (we have 64 bins that cover 360°) and accumulate segment lengths for every bin, while also counting every two-way road twice (in both directions):

var k0 = Math.round((bearing + 360) * numBins / 360) % numBins;
var k1 = Math.round((bearing + 180) * numBins / 360) % numBins;

bins[k0] += distance;
if (isTwoWay) bins[k1] += distance;

Finally, to get those pretty, uniform rainbow colors for all orientations on our chart, we use the sinebow function popularized by my coworker Charlie Loyd.

That’s it!

Now play with the interactive map — I spent hours exploring it, and hope you enjoy it as much as I do! Check out the full source code, and hit me up on Twitter if you have any questions!

Visualizing street orientations on an interactive map was originally published in maps for developers on Medium, where people are continuing the conversation by highlighting and responding to this story.

With the 0.41 release of Mapbox GL JS (and mobile SDKs to follow), we’re introducing heatmaps — a beautiful way to visualize and explore massive point datasets.

A heatmap is a data visualization where a range of colors represent the density of points in a particular area. Heatmaps help us see the “shape” of the data and highlight areas of concentration where many points are clustered closely together. The dynamic heatmap layer in Mapbox GL JS renders smoothly at 60 fps while panning and zooming. It’s fast and can handle large amounts of data (especially when combined with clustering). Let’s see what an interactive heatmap of 400,000 points looks like:

Getting started with heatmaps

If you want to get started with heatmaps right away, dive into our official example or take a look at a detailed tutorial. Want to know more? Read on for an overview.

You can start by adding a layer with type “heatmap” to your style:

map.addSource('earthquakes', {
    type: 'geojson',
    data: 'earthquakes.geojson'
});

map.addLayer({
    id: 'earthquakes',
    source: 'earthquakes',
    type: 'heatmap'
});

Heatmaps can require a lot of customization based on your use-case. Thankfully, Mapbox GL JS provides a set of powerful paint style properties for controlling every aspect of the layer’s appearance in real time.

heatmap-radius

This property affects how detailed the heatmap will be by setting the “radius of influence” of each point in pixels (an equivalent of the bandwidth parameter in kernel density estimation). Higher values make for a smoother, more generalized look. The property can also be a zoom function, allowing you to adjust the look as you zoom in.

map.addLayer({
    ...
    paint: {
        'heatmap-radius': 40
    }
});

heatmap-color

This style property controls the most important aspect of heatmap design — how the “density” value of each pixel on a map translates to color:

The value of the property is a function which maps density values ranging from 0.0 to 1.0 to colors. This example will make the most sparse areas blue while gradually transitioning through yellow to red at the most crowded spots.

"heatmap-color": {
    "stops": [
        [0.0, "blue"], 
        [0.5, "yellow"], 
        [1.0, "red"]
    ]
}

heatmap-intensity

This property allows you to adjust the intensity of the heatmap appearance globally. The higher the value, the more “weight” each point will contribute to the look. The relation is linear — e.g., setting heatmap-intensity to 10.0 is equivalent to duplicating the dataset ten times and rendering it with the default 1.0 value.

heatmap-intensity is very useful for adjusting the look of the heatmap to different zoom levels — if you leave it constant, the heatmap on lower zooms will look much heavier because points will be visually closer together.

heatmap-weight

This style property works the same as heatmap-intensity, except that it can be data-driven, adjusting intensity of individual points depending on their feature properties:

"heatmap-weight": {
    "type": "identity", 
    "property": "point_count"
}

In this example, a point with point_count value of 100 will look the same as 100 points with point_count of 1. Combined with clustering, this improves heatmap performance by drastically reducing the number of points to draw.

heatmap-opacity

This property controls the global opacity of the heatmap layer.

One useful application of heatmap-opacity is fading out the heatmap for a more detailed look when zooming in:

How heatmaps work under the hood

In mathematical terms, Mapbox GL heatmaps are a bivariate (2D) kernel density estimation with a Gaussian kernel. It means that each data point has an area of “influence” around it (called a kernel) where the numerical value of influence (which we call density) decreases as you go further from the point. If we sum density values of all points in every pixel of the screen, we get a combined density value which we then map to a heatmap color.

To implement this with OpenGL, for each data point, we draw the kernel (which looks like a blurred circle) into an offscreen half-float texture with additive blending (so that values are summed together when kernels overlap), and then we colorize this greyscale texture in a separate step.

Ideally, we need to calculate density for every screen pixel separately for each data point because this value never becomes fully zero, even when far away from the corresponding point. But that would be too expensive — even a modest amount of points to draw would require billions of operations. To speed things up, we crop each kernel to a square that’s just big enough for all values outside to be very small (under a certain threshold — we arbitrarily picked 1 / 255 / 16). This size will depend on weight and intensity of each point; heavier points will need a bigger drawing area.

Additionally, for drawing the densities, we use a downscaled texture with 4 times smaller sides than the map resolution (resulting in 16 times fewer pixels to draw for each point), and then upscale the texture back with linear interpolation during the colorization step. For heatmaps, this is visually almost indistinguishable from full resolution rendering, but it makes it considerably faster.

A different approach to heatmaps

Other platforms render heatmaps as static image tiles on the server. Our approach to heatmaps takes advantage of Mapbox GL at its core, rendering smooth transitions at 60fps and providing the ability to control every aspect of heatmap layers at scale — from picking the right color ramp to adjusting the point radius at each zoom level. Combine heatmaps with other GL JS capabilities like data-driven styling, expressions, and clustering for more unique configurations of your data.

Thank you for reading! Check out this example and tutorial for heatmaps in GL JS, and stay tuned for the launch of this feature in our mobile SDKs later this year. Reach out on Twitter (@mourner) or respond here in Medium if you have questions or comments. Let us know what you make with the tag #BuiltWithMapbox.

Vladimir Agafonkin

Introducing heatmaps in Mapbox GL JS was originally published in maps for developers on Medium, where people are continuing the conversation by highlighting and responding to this story.

Check out my WebGL-based wind power simulation demo! Let’s dive into how it works under the hood.

I have an unflattering confession to make: for the last few years working at Mapbox, I avoided direct OpenGL/WebGL programming like a plague. For one reason: the OpenGL API and terminology deeply terrified me. It always looked so complex, confusing, ugly, and verbose that I could never take the plunge and dive into it. I would get an uneasy feeling simply hearing terms like stencil masks, mipmap, depth culling, blend functions, and normal maps.

This year, I decided to finally confront my fears and build something non-trivial with WebGL on my own. 2D wind simulation looked like a perfect opportunity — it’s useful, visually stunning, and challenging, yet it still felt attainable in scope. I was surprised to discover that it was much less scary than it looked!

Wind visualization on the CPU

There are many examples of wind power visualization online, but the most popular and influential one is earth.nullschool.net, a famous project by Cameron Beccario. It’s not open source itself, but it has an old open source version which most other implementations based their code on. One notable open source derivation is Esri Wind-JS. Popular weather services that use the technique include Windy and VentuSky.

Typically, such a visualization in the browser relies on the Canvas 2D API and roughly works like this:

1. Generate an array of random particle positions on screen and draw the particles.
2. For each particle, query the wind data to get the particle speed in its current location, and move it accordingly.
3. Reset a small portion of particles to a random position. This makes sure that areas the wind blows away from never become fully empty.
4. Fade the current screen a bit and draw newly positioned particles on top.

This has subsequent performance limitations:

• The number of wind particles should be kept low (e.g. Earth uses ~5k).
• There’s a big delay every time you update the data or the view (e.g. ~2 seconds for Earth) because data processing is expensive and happens on the CPU side.

Moreover, to integrate it as a part of an interactive WebGL-based map like Mapbox is that you would have to upload the pixel contents of the Canvas element to the GPU on every frame, which would significantly reduce the performance further.

I was looking for a way to reimplement the full logic on the GPU side with WebGL, so that it would be fast, capable of drawing millions of particles, and possible to integrate into a Mapbox GL map without a big performance loss. Luckily, I stumbled upon a wonderful tutorial about particle physics in WebGL by Chris Wellons, and realized that the wind visualization can use the same approach.

OpenGL Basics

The confusing API and terminology makes OpenGL graphics programming very intimidating to learn, but under the surface, the concept is extremely simple. Here’s a practical definition:

OpenGL provides a 2D API for drawing triangles efficiently.

So basically all you do with GL is draw triangles. The difficulty, besides the scary API, comes from the various math and algorithms required to do this. It can also draw dots and basic lines (without smoothing or round joins/caps), but those are rarely used.

OpenGL provides a special C-like language — GLSL — to write programs that are directly executed by the GPU. Each program is divided into two parts, called shaders — the vertex shader and the fragment shader.

The vertex shader provides the code for converting coordinates. For example, multiplying triangle coordinates by 2 so that our triangle appears twice as big. It will run once for every coordinate we pass to OpenGL when drawing. A basic example:

attribute vec2 coord;
void main() {
    gl_Position = vec4(2.0 * coord, 0, 1);
}

The fragment shader provides the code for determining the color of each drawn pixel. You can do a lot of cool math in it, but in the end it comes down to something like “draw the current pixel of the triangle as green”. Example:

void main() {
    gl_FragColor = vec4(0, 1, 0, 1);
}

One of the cool things you can do in both vertex and fragment shaders is adding an image (called texture) as a parameter, and then looking up pixel colors in any spot of this image. We’ll rely on this heavily in the wind visualization.

The fragment shader code execution is massively parallel and heavily hardware-accelerated, so it’s usually many orders of magnitude faster than an equivalent computation on the CPU.

Getting the wind data

Every 6 hours, the US National Weather Service publishes weather data for the whole globe, known as GFS, in the form of a latitude/longitude grid with associated values (including wind velocities). It’s encoded in a special binary format called GRIB, which can be parsed into human-readable JSON with a special set of tools.

I wrote a few small scripts that download and convert the wind data into a simple PNG image with wind velocities encoded as RGB colors — horizontal velocity as red and vertical as green in each pixel. It looks like this:

There are higher resolution versions you can download (2x and 4x), but 360×180 grid is enough for a low-zoom visualization. PNG compression is quite a good fit for this kind of data, and the image above typically weights just about 80 KB.

Moving particles on the GPU

Existing wind visualizations stored particle state in JavaScript arrays. How do we store and manipulate this state on the GPU side? A new GL feature called compute shaders (in OpenGL ES 3.1 and equivalent WebGL 2.0 specifications) allows you to run shader code on arbitrary data (without any rendering). Unfortunately, support for the new specifications across browsers and mobile devices is marginal, and so we’re left with only one practical option: textures.

OpenGL allows you to draw not only to the screen, but also to a texture (through a concept called framebuffer). So we can encode particle positions as RGBA colors of an image, load it to the GPU, calculate new positions based on wind velocities in the fragment shader, encode them back into RGBA colors and draw it into a new image.

To store enough precision for both X and Y, we store each component in two bytes — RG and BA respectively, giving us a range of 65536 distinct values for each.

An example 500×500 image would then hold 250,000 particles, and we would move every particle with the fragment shader. The resulting image would look like this:

Here’s how the position is decoded and encoded from RGBA and back in the fragment shader:

// lookup particle pixel color
vec4 color = texture2D(u_particles, v_tex_pos);

// decode particle position (x, y) from pixel RGBA color
vec2 pos = vec2(
    color.r / 255.0 + color.b,
    color.g / 255.0 + color.a);

... // move the position

// encode the position back into RGBA
gl_FragColor = vec4(
    fract(pos * 255.0),
    floor(pos * 255.0) / 255.0);

On the next frame, we can take this new image as the current state and draw the new state into the other image, etc., swapping the two every frame. So, with the help of two particle state textures, we can move all the wind simulation logic to the GPU.

This approach is extremely fast — instead of updating only 5,000 particles 60 times per second on the browser, we can suddenly handle one million.

One thing to keep in mind is that near the poles, the particles should move much faster along the X axis compared to the ones on the equator, because the same number of longitude degrees represents a much smaller distance. This can be taken into account with the following shader code:

float distortion = cos(radians(pos.y * 180.0 - 90.0));
// move the particle by (velocity.x / distortion, velocity.y)

Drawing the particles

As I mentioned earlier, in addition to triangles, we can also draw basic points — rarely used, but perfect for 1-pixel particles like this.

To draw each particle, we’ll simply look up its pixel color on the particle state texture in the vertex shader to determine its position; then determine the particle color in the fragment shader by looking up its current velocity from the wind texture; and finally map it to a nice color gradient (I picked the colors from the trusty ColorBrewer2). At this point, it looks like this:

That’s something, if a little empty. But it’s hard to get a sense of wind direction from particle movement alone. We need to add particle trails.

Drawing particle trails

The first approach to drawing the trails I tried is using preserveDrawingBuffer WebGL option, which makes the screen state persist between frames, so that we can draw particles over and over on top of each other every frame as they move. However, this WebGL feature is a big performance hit, and many WebGL articles recommend against using it.

Instead, similar to how we do with particle state textures, we can draw the particles into a texture (which is in turn drawn onto a screen), then use this texture on the next frame as the background (slightly dimmed), and swap the input/target textures every frame. In addition to better performance, an advantage of this approach is that we can port it directly to native code (which has no preserveDrawingBuffer equivalent).

Interpolating wind lookups

The wind data has values for specific points on a latitude/longitude grid, e.g. (50,30),(51,30),(50,31),(51,31)geographical points. How do we get an arbitrary intermediate value, e.g. (50.123,30.744)?

OpenGL comes with free interpolation when you look up texture colors. However, it’s still leads to blocky, pixelated patterns. Here’s an example of these artifacts in the wind texture when scaled:

Luckily, we can smooth out the artifacts by looking up 4 neighbor pixels in each wind probe, and doing manual bilinear interpolation math on them on top of the native one in the fragment shader. It’s more expensive, but fixes the artifacts and leads to a more fluid wind visualization. Here’s the same area with this technique:

Pseudo-random generator on the GPU

There’s one tricky logic left to implement on the GPU — randomly resetting particle locations. Without this, even a huge number of wind particles degenerates into just a few lines on the screen, because areas the wind blows away from become empty with time:

The problem is that shaders don’t have a random number generator. How do we randomly decide if a particle needs to be reset?

I found a solution on StackOverflow — a GLSL function for pseudo-random number generation that accepts a pair of numbers as input:

float rand(const vec2 co) {
    float t = dot(vec2(12.9898, 78.233), co);
    return fract(sin(t) * (4375.85453 + t));
}

This curious function depends on sin result varying a lot with big values. Then we can do something like this:

if (rand(some_numbers) > 0.99) 
    reset_particle_position();

The challenge is picking an input for each particle that would be “random” enough so that the generated values are uniform across the screen and do not exhibit weird patterns.

Using current particle position as the seed is not perfect because the same particle positions will always generate the same random numbers, so some particles will disappear in the same area.

Using particle position in the state texture also doesn’t work because the same particles will always disappear.

What I ended up with eventually depends on both particle position and state position coupled with a random value that’s calculated on every frame and passed to the shader:

vec2 seed = (pos + v_tex_pos) * u_rand_seed;

But then we have another minor problem — areas where particles are very fast will look much more dense than areas where there’s not much wind. We can balance this out a bit by increasing the particle reset rate for faster particles:

float dropRate = u_drop_rate + speed_t * u_drop_rate_bump;

speed_t here is a relative speed value (from 0 to 1), and u_drop_rate and u_drop_rate_bump are parameters you can tweak in the final visualization. Here's an example of how it affects the result:

What’s next

The result is a fully GPU-powered wind visualization that can render a million particles at 60fps. Try playing with the sliders in the demo, and check out the final code — it’s about 250 lines total, and I tried to make it as readable as possible.

The next step is integrating this into a live map you can explore. I’ve made some progress on this but not enough to share a live demo. Here’s a little sneak peek though (sorry for the poor quality capture):

Thank you for reading and stay tuned for more updates! And check out my previous article on spatial algorithms if you missed it.

Very special, warm-hearted thank you to my Mapbox team mates @kkaefer and @ansis, who patiently answered all my silly questions about graphics programming, gave tons of valuable tips and helped me learn so much. ❤️

P.S. Want to work on cool stuff like this? Check out our job openings.

How I built a wind map with WebGL was originally published in maps for developers on Medium, where people are continuing the conversation by highlighting and responding to this story.

I’m obsessed with software performance. One of my main responsibilities at Mapbox is discovering ways to make our mapping platform faster. And when it comes to processing and displaying spatial data at scale, there’s no concept more useful and important than a spatial index.

Spatial indices are a family of algorithms that arrange geometric data for efficient search. For example, doing queries like “return all buildings in this area”, “find 1000 closest gas stations to this point”, and returning results within milliseconds even when searching millions of objects.

Spatial indices form the foundation of databases like PostGIS, which is at the core of our platform. But they’re also immensely useful in many other tasks where performance is critical. In particular, processing telemetry data — e.g. matching millions of GPS speed samples against a road network to generate live traffic data for our navigation service. On the client side, examples include placing labels on a map in real time, and looking up map objects on a mouse hover.

In the last 4 years, I’ve built a bunch of ultra-fast JavaScript libraries for spatial search: rbush, rbush-knn, kdbush, geokdbush (with a few more to come). In this post, I’ll attempt to describe how they work under the hood.

Spatial search problems

Spatial data has two fundamental query types: nearest neighbors and range queries. Both serve as a building block for many geometric and GIS problems.

K nearest neighbors

Given thousands of points, such as city locations, how do we retrieve the closest points to a given query point?

An intuitive way to do this is:

1. Calculate the distances from the query point to every other point.
2. Sort those points by distance.
3. Return the first K items.

This is fine if we have a few hundred points. But if we have millions, these queries will be too slow to use in practice.

Range and radius queries

How do we retrieve all points inside…

• a rectangle? (range query)
• a circle? (radius query)

The naive approach is to loop through all the points. But this will fail if the database is big and gets thousands of queries per second.

How spatial trees work

Solving both problems at scale requires putting the points into a spatial index. Data changes are usually much less frequent than queries, so incurring an initial cost of processing data into an index is a fair price to pay for instant searches afterwards.

Almost all spatial data structures share the same principle to enable efficient search: branch and bound. It means arranging data in a tree-like structure that allows discarding branches at once if they do not fit our search criteria.

R-tree

To see how this works, let’s start with a bunch of input points and sort them into 9 rectangular boxes with about the same number of points in each:

Now let’s take each box and sort it into 9 smaller boxes:

We’ll repeat the same process a few more times until the final boxes contain 9 points at most:

And now we’ve got an R-tree! This is arguably the most common spatial data structure. It’s used by all modern spatial databases and many game engines. R-tree is also implemented in my rbush JS library.

Besides points, R-tree can contain rectangles, which can in turn represent any kinds of geometric objects. It can also extend to 3 or more dimensions. But for simplicity, we’ll talk about 2D points in the rest of the article.

K-d tree

K-d tree is another popular spatial data structure. kdbush, my JS library for static 2D point indices, is based on it. K-d tree is similar to R-tree, but instead of sorting the points into several boxes at each tree level, we sort them into two halves (around a median point) — either left and right, or top and bottom, alternating between x and y split on each level. Like this:

Compared to R-tree, K-d tree can usually only contain points (not rectangles), and doesn’t handle adding and removing points. But it’s much easier to implement, and it’s very fast.

Both R-tree and K-d tree share the principle of partitioning data into axis-aligned tree nodes. So the search algorithms discussed below are the same for both trees.

Range queries in trees

A typical spatial tree looks like this:

Each node has a fixed number of children (in our R-tree example, 9). How deep is the resulting tree? For one million points, the tree height will equal ceil(log(1000000) / log(9)) = 7.

When performing a range search on such a tree, we can start from the top tree level and drill down, ignoring all the boxes that don’t intersect our query box. For a small query box, this means discarding all but a few boxes at each level of the tree. So getting the results won’t need much more than sixty box comparisons (7 * 9 = 63) instead of a million. Making it ~16000 times faster than a naive loop search in this case.

In academic terms, a range search in an R-tree takes O(K log(N)) time in average (where K is the number of results), compared to O(N) of a linear search. In other words, it’s extremely fast.

We chose 9 as the node size because it’s a good default, but as a rule of thumb, higher value means faster indexing and slower queries, and vice versa.

K nearest neighbors (kNN) queries

Neighbors search is slightly harder. For a particular query point, how do we know which tree nodes to search for the closest points? We could make a radius query, but we don’t know which radius to pick — the closest point could be pretty far away. And doing many radius queries with an increasing radius in hopes of getting some results is inefficient.

To search a spatial tree for nearest neighbors, we’ll take advantage of another neat data structure — a priority queue. It allows keeping an ordered list of items with a very fast way to pull out the “smallest” one. I like to write things from scratch to understand how they work, so here’s the best ever priority queue JS library: tinyqueue.

Let’s take a look at our example R-tree again:

An intuitive observation: when we search a particular set of boxes for K closest points, the boxes that are closer to the query point are more likely to have the points we look for. To use that to our advantage, we start our search at the top level by arranging the biggest boxes into a queue in the order from nearest to farthest:

Next, we “open” the nearest box, removing it from the queue and putting all its children (smaller boxes) back into the queue alongside the bigger ones:

We go on like that, opening the nearest box each time and putting its children back into the queue. When the nearest item removed from the queue is an actual point, it’s guaranteed to be the nearest point. The second point from the top of the queue will be second nearest, and so on.

This comes from the fact that all boxes we didn’t yet open only contain points that are farther than the distance to this box, so any points we pull from the queue will be nearer than points in any remaining boxes:

If our spatial tree is well balanced (meaning the branches are approximately the same size), we’ll only have to deal with a handful of boxes — leaving all the rest unopened during the search. This makes this algorithm extremely fast.

For rbush, it’s implemented in rbush-knn module. For geographic points, I recently released another kNN library — geokdbush, which gracefully handles curvature of the Earth and date line wrapping. It deserves a separate article — it was the first time I ever applied calculus at work.

Custom kNN distance metrics

This box-unpacking approach is quite flexible, and works for other distance types besides point-to-point distances. The algorithm relies on a defined lower bound of distances between the query and all objects inside a box. If we can define this lower bound for a custom metric, we can use the same algorithm for it.

This means we can, for example, change the algorithm to search K points closest to a line segment (instead of a point):

The only modification to the algorithm we need is replacing point-to-point and point-to-box distance calculations with segment-to-point and segment-to-box distances.

In particular, this came in handy when I built Concaveman, a fast 2D concave hull library in JS. It takes a bunch of points and generates an outline like this:

The algorithm starts with a convex hull (which is fast to calculate), and then flexes its segments inward by connecting them through one of the closest points:

Here’s a quote from the paper on that operation:

In our proposed concave hull algorithm, finding nearest inside points — these are candidates of target spots for digging — from boundary edges is a time-consuming process. Developing a more efficient method for this process is a future research topic.

Which I advanced, by a lucky coincidence! Indexing the points and performing “closest points to a segment” queries made the algorithm very fast.

To be continued

In future articles in the series, I’ll cover extending the kNN algorithm to geographic objects, and go into detail on tree packing algorithms (how to sort points into “boxes” optimally).

Thanks for reading! Feel free to comment and ask questions, and stay tuned for more. Play with our awesome SDKs, and if you’re fired up about hard engineering challenges and maps, check out our job openings.

A dive into spatial search algorithms was originally published in maps for developers on Medium, where people are continuing the conversation by highlighting and responding to this story.

I’m by no means an expert on talks. But, as an introvert, I overcame the fear of public speaking, gave dozens of talks at tech conferences, made lots of mistakes, and listened to hundreds of other speakers over the last years.

As a result, I learned a lot about what makes a talk engaging, inspiring and enjoyable.

A good talk is a story

Human beings go to conferences to connect to other human beings. A good talk is not a report, and not an advertisement — it’s a talk.

If all you do is commenting a bunch of slides, you will loose your listeners’ attention — they’ll probably make a better use of their time by reading a website or an article on the matter instead. People want to hear your story, to feel your enthusiasm and get inspired.

So a good talk is a story. Talk to the audience as if you’re telling it to a friend. Even complex, technical topics can be approached this way. Then it will flow naturally and engage your listeners.

And if you’re telling a story, be a human! Don’t be afraid to show through your personality. Laugh, cry, make stupid jokes, throw weird gestures, make funny faces, show funny GIFs, tell about the things you love, tell people how you screwed up. Being nervous, weird, awkward or silly is perfectly fine!

Be yourself. This will give your talk humanity and warmth. People will connect to you on a personal level, and they’ll love it.

Getting comfortable on stage

Giving your first ever public talk and feeling like you’re going to pass out? That’s normal!

Being a pretty introverted person, I gave my first talk at a crowded web development conference in 2008, talking about web accessibility. In a suit, pale like snow, with a gothic grimace on my face.

The hand holding the microphone shook intensely, with me looking as if I’m going to throw it any minute and run away. Occasionally I’d make a deep loud breath right into the mic, with the audience giving out laughs every time that happened.

Anyway, I cared about my topic, the content was useful, and people liked it.

When I’m on stage now, I often feel like I’m on a couch sitting with a bunch of friends beside a fire, even if it’s a hall with half a thousand people.

English isn’t my native language, so I often make glaring mistakes, or awkward pauses while recalling the right word. But it doesn’t bother me at all. This feeling of relaxed joy, the joy of sharing something you love with like-minded people, just comes naturally with practice.

If you’re not passionate about things you’re going to talk about, don’t bother talking at all. Otherwise, you’ll be perfectly fine! The comfort will gradually come with more talks given.

How to make great slides

The biggest problem with slides is that they have two purposes:

• to guide and complement your talk
• to be shared with others after the talk

These purposes are not compatible. Presenters tend to focus on making slides shareable, packing each slide with information. If you do this, it can ruin your talk:

1. More information distracts from your message. The audience reads your slide while you talk. And we are ridiculously bad at doing multiple things at once — especially reading and listening simultaneously.
2. Things on the slides have to be smaller (including font sizes) — many people just won’t be able to read it, as not everyone has perfect vision.
3. You can’t convey a strong message with a noisy slide. Strong messages are simple. Just a few words or a picture hit immediately; a big paragraph, a list, a table, or anything you have to stare at for a minute to understand just can’t have the same emotional impact.
4. When you pack your whole speech into slides, it sounds awkward — as if you simply read aloud instead of actually talking to people in front. It is a sure way to loose connection to your audience.

If you want to have a great live presentation, make the slides complementary to your talk, and not your talk complementary to the slides.

The slides will still do well when shared, even if they don’t have the full picture. People will crave for more — they’ll look up mentioned things, go through links, go to your website, follow you on Twitter, read the follow-up blog posts and wait patiently for the video of the talk. It’s fine.

Rules of thumb for slides

Make things simple. Remove clutter. That’s all you have to do to make your slides click. Specific tips:

1. One thing per slide: a simple phrase in a huge font size, a strong image or a video.
2. Remove anything that doesn’t serve a useful purpose: titles, frames, ornaments, logos, background patterns, distracting animations, etc.
3. Prefer many simple slides over one complex slide.
4. If you need several things on one slide, make them appear one by one.
5. It’s better to talk without slides at all than comment a bunch of complex slides.
6. Limit the variety of slide looks. In particular, limit text to a few different styles at most — e.g. a white background, a single font, with black as a primary color and one or two additional colors for emphasis.
7. Don’t assume the projector will work perfectly and under favorable lighting conditions — make sure slides have enough contrast to be readable in any case. Also, accept as a fact that colors will probably be messed up.
8. Don’t make the slides too flashy and intense — most of the time, the attention should be on you, not the slides.

Here’s a slide deck from one of my recent talks for an example.

Technical tips

Never rely on internet connection in presentations. I see fails because of this all the time. Even if you’re sure that it’ll work. Even if it always worked perfectly before. Even if slow connection should be enough. Try to prepare your presentations assuming you’ll be offline.

E.g. if your presentation is HTML/JS, turn off the WiFi and make sure each slide still works.

Use recorded video instead of doing live demos:

1. Video is infinitely more reliable — no surprises. Awkward mumbling about bad WiFi — never again!
2. Remember that people are bad at multi-tasking? You’ll have a much easier time talking strongly and connecting with your audience if you don’t stare at the screen and click something with your mouse or type on a keyboard while you talk.
3. It’ll save you some awkward time switching between slides and the right browser tab or whatever.

Also, use recorded video instead of GIFs for product demos. The most important reason is the framerate — your listeners don’t know that it’s a GIF, so they will decide that the product is slow and janky instead.

GIFs are great because they are easily shareable. But remember that performance is a feature. Engineers put so much effort into making apps fast and smooth — don’t make the audience miss this. And don’t forget that GIFs mess up colors even further.

To record a screen video on a Mac, launch QuickTime, then click “File” — “New Screen Recording”. A moment later, you have a smooth, sharp, full-colored video for your presentation.

Final notes

I was deeply scared of public performances, but decided that in order to grow, I have to do what I fear. So I started sending out talk submissions, and it went from there. Not only is the fear gone now, — I actually enjoy talking publicly a lot.

Try it yourself — at the least, you’ll learn a very useful skill. And at the most, you’ll become a great speaker and inspire thousands of people. Even if you don’t feel like it at the moment.

If you need some inspiration, I’ll state the obvious — go to TED.com. This incredible learning resource has thousands of videos with some of the best talks ever given.

Finally, feedback is very welcome! Thanks for reading and sharing.