---
title: "Optimize Google map multi-route loading with B-spline"
description: "Optimize loading multiple routes on Google map using B-spline"
canonical_url: "https://www.bigbinary.com/blog/using-bspline-curves-to-draw-sampled-route-points-on-google-maps"
markdown_url: "https://www.bigbinary.com/blog/using-bspline-curves-to-draw-sampled-route-points-on-google-maps.md"
---

# Optimize Google map multi-route loading with B-spline

Optimize loading multiple routes on Google map using B-spline

- Author: Ashish Gaur
- Published: December 4, 2018
- Categories: JavaScript

Applications use Google maps for showing routes from point A to B. For one of
our clients we needed to show delivery routes on Google maps so that user can
select multiple deliveries and then consolidate them as one single delivery.
This meant we needed to show around 30 to 500 deliveries on a single map.

## Using Google Map polylines

We used polylines to draw individual routes on Google maps.

Polyline is composed of line segments connecting a list of points on the map.
The more points we use for drawing a polyline the more detailed the final curve
will be. Here's how we added route points to the map.

```javascript
// List of latitude and longitude
let path = points.map(point => [point.lat, point.lng]);

let route_options = {
  path: path,
  strokeColor: color,
  strokeOpacity: 1.0,
  strokeWeight: mapAttributes.strokeWeight || 3,
  map: map, // google.maps.Map
};

new google.maps.Polyline(route_options);
```

Here's an example of a polyline on a Google map. We used 422 latitude and
longitude points to draw these routes which makes it look more contiguous.

![Polyline example](https://www.bigbinary.com/blog/images/images_used_in_blog/2018/using-bspline-curves-to-draw-sampled-route-points-on-google-maps/polyline_example.png)

We needed to show 200 deliveries in that map. On an average a delivery contains
around 500 route points. This means we need to load 1,00,000 route points. Let's
measure and see how much time the whole process takes.

## Loading multiple routes on a map

Plotting a single route on a map can be done in less than a second. However as
we increase the number of routes to plot, the payload size increases which
affects the load time. This is because we've around 500 route points per
delivery. If we want to show 500 deliveries on the map then we need to load
500 \* 500 = 2,50,000 routes points. Let's benchmark the load time it takes to
show deliveries on a map.

No. of deliveries | Load Time | Payload Size | 500 | 8.77s | 12.3MB | 400 |
7.76s | 10.4MB | 300 | 6.68s | 7.9MB | 200 | 5.88s | 5.3MB | 100 | 5.47s | 3.5MB
|

The load time is more than 5 seconds which is high. What if we could decrease
the payload size and still be able to plot the routes.

## Sampling route points for decreased payload size

For each delivery we've around 500 route points. If we drop a few route points
in between on a regular interval then we'll be able to decrease the payload
size. Latitude and longitude have at least 5 decimal points. We rounded them off
to 1 decimal point and then we picked unique values.

```ruby
  def route_lat_lng_points
    return '' unless delivery.route_lat_lng_points

    delivery.route_lat_lng_points.
        chunk{ |point| [point.first.round(1), point.second.round(1)] }.
        map(&:first).join(',')
  end
```

Now let's check the payload size and the load time.

No. of deliveries | Load Time | Payload Size | 500 | 6.52s | 6.7MB | 400 | 5.97s
| 5.5MB | 300 | 5.68s | 4.2MB | 200 | 4.88s | 2.9MB | 100 | 4.07s | 2.0MB |

The payload size decreased by 50 percent. However since we sampled the data the
routes are not contiguous anymore. Here's how it looks now.

![Sampled routes](https://www.bigbinary.com/blog/images/images_used_in_blog/2018/using-bspline-curves-to-draw-sampled-route-points-on-google-maps/sampled_routes.png)
![Contiguous routes](https://www.bigbinary.com/blog/images/images_used_in_blog/2018/using-bspline-curves-to-draw-sampled-route-points-on-google-maps/contiguous_routes.png)

Note that we sampled route points till single decimal point. Notice that the
routes in which we did sampling appears to be jagged instead of contiguous. We
can solve this by using a curve fitting method to create a curve from the
discrete points we have.

## Curve fitting using B-spline function

[B-spline](https://en.wikipedia.org/wiki/B-spline) or basis spline is a spline
function which can be used for creating smooth curves best fitted to a set of
control points. Here's an example of a B-spline curve created from a set of
control points.

![Bspline example](https://www.bigbinary.com/blog/images/images_used_in_blog/2018/using-bspline-curves-to-draw-sampled-route-points-on-google-maps/bspline_example.png)

We changed our previous example to use B-spline function to generate latitude
and longitude points.

```javascript
// List of latitude and longitude
let lats = points.map(point => point.lat);
let lngs = points.map(point => point.lng);
let path = bspline(lats, lngs);

let route_options = {
  path: path,
  strokeColor: color,
  strokeOpacity: 1.0,
  strokeWeight: mapAttributes.strokeWeight || 3,
  map: map, // instance of google.maps.Map
};

new google.maps.Polyline(route_options);
```

```javascript
function bspline(lats, lngs) {
  let i, t, ax, ay, bx, by, cx, cy, dx, dy, lat, lng, points;
  points = [];

  for (i = 2; i < lats.length - 2; i++) {
    for (t = 0; t < 1; t += 0.2) {
      ax = (-lats[i - 2] + 3 * lats[i - 1] - 3 * lats[i] + lats[i + 1]) / 6;
      ay = (-lngs[i - 2] + 3 * lngs[i - 1] - 3 * lngs[i] + lngs[i + 1]) / 6;

      bx = (lats[i - 2] - 2 * lats[i - 1] + lats[i]) / 2;
      by = (lngs[i - 2] - 2 * lngs[i - 1] + lngs[i]) / 2;

      cx = (-lats[i - 2] + lats[i]) / 2;
      cy = (-lngs[i - 2] + lngs[i]) / 2;

      dx = (lats[i - 2] + 4 * lats[i - 1] + lats[i]) / 6;
      dy = (lngs[i - 2] + 4 * lngs[i - 1] + lngs[i]) / 6;

      lat =
        ax * Math.pow(t + 0.1, 3) +
        bx * Math.pow(t + 0.1, 2) +
        cx * (t + 0.1) +
        dx;

      lng =
        ay * Math.pow(t + 0.1, 3) +
        by * Math.pow(t + 0.1, 2) +
        cy * (t + 0.1) +
        dy;

      points.push(new google.maps.LatLng(lat, lng));
    }
  }
  return points;
}
```

Source:
[https://johan.karlsteen.com/2011/07/30/improving-google-maps-polygons-with-b-splines](https://johan.karlsteen.com/2011/07/30/improving-google-maps-polygons-with-b-splines/)

After the change the plotted routes are much better. Here's how it looks now.

![Bspline routes](https://www.bigbinary.com/blog/images/images_used_in_blog/2018/using-bspline-curves-to-draw-sampled-route-points-on-google-maps/bspline_routes.png)
![Contiguous routes](https://www.bigbinary.com/blog/images/images_used_in_blog/2018/using-bspline-curves-to-draw-sampled-route-points-on-google-maps/contiguous_routes.png)

The only downside here is that if we zoom in the map we'll notice that the
routes are not exactly overlapping the Google map paths. Otherwise we're able to
plot almost same routes with sampled route points. However we still need 6.5
seconds to load 500 deliveries. How do we fix that ?

## Loading deliveries in batches

Sometimes users have up to 500 deliveries but they want to change only a few
deliveries and then use the application. Right now the way application is setup
users have no choice but to wait until all 500 deliveries are loaded and then
only they would be able to change a few deliveries. This is not ideal.

We want to show deliveries as soon as they're loaded. We added a polling
mechanism that would load batches of 20 deliveries and as soon as a batch is
loaded we would plot them on the map. This way user could interact with the
loaded deliveries while the remaining deliveries are still being loaded.

```javascript
  loadDeliveriesWindow(updatedState = {}, lastPage = 0, currentWindow = 1) {
    // windowSize: Size of the batch to be loaded
    // perPage: No of deliveries per page
    const { perPage, windowSize } = this.state;

    if (currentWindow > perPage / windowSize) {
      // Streaming deliveries ended
      this.setState($.extend(updatedState, { windowStreaming: false }));
      return;
    }

    if (currentWindow === 1) {
      // Streaming deliveries started
      this.setState({ windowStreaming: true });
    }

    // Gets delivery data from backend
    this.fetchDeliveries(currentWindow + (lastPage * windowSize), queryParams).complete(() => {
      // Plots deliveries on map
      this.loadDeliveries();

      // Load the next batch of deliveries
      setTimeout((() => {
        this.loadDeliveriesWindow(updatedState, lastPage, currentWindow + 1);
      }).bind(this, currentWindow, updatedState, lastPage), 100);
    });
  }
```

Here's a comparison of how the user experience changed.

![Streaming deliveries](https://www.bigbinary.com/blog/images/images_used_in_blog/2018/using-bspline-curves-to-draw-sampled-route-points-on-google-maps/streaming_deliveries.gif)
![Normal loading](https://www.bigbinary.com/blog/images/images_used_in_blog/2018/using-bspline-curves-to-draw-sampled-route-points-on-google-maps/normal_loading.gif)

Notice that loaded deliveries are instantly plotted and user can start
interacting with them. While if we load all the deliveries before plotting them
the user has to wait for all of them to be loaded. This made the user experience
much better if the user loaded more than 100 deliveries.

## Serializing route points list without brackets

One more optimization we did was to change how route points are being
serialized.

The route points after serialization contained opening and closing square
brackets. So let's say the route points are

`[[25.57167, -80.421271], [25.676544, -80.388611], [25.820025, -80.386488],...]`.

After serialization they looked like

`[[25.57167,-80.421271], [25.676544,-80.388611], [25.820025,-80.386488],...]`.

For each route point we've an extra opening and closing square bracket which can
be avoided.

We could get rid of the brackets by concatenating the route points array and
converting it to a string. After conversion it looked like this.

`"25.57167,-80.421271|25.676544,-80.388611|25.820025,-80.386488|..."`

At the client side we converted it back to an array. This reduced the payload
size by 0.2MB for dense routes.

Note this is a trade off between client side processing and network bandwidth.
In modern computers the client side processing will be negligible. For our
clients, network bandwidth was a crucial resource so we optimized it for network
bandwidth.

## Links

- [Human page](https://www.bigbinary.com/blog/using-bspline-curves-to-draw-sampled-route-points-on-google-maps)