Optimize Google map multi-route loading with B-spline

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.

// 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.

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.

  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.

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 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.

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

// 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);

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

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

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.

  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.

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.