Google Maps polygons work fine in most cases. However, once we start dealing with a huge number of polygons (hundreds of thousands), having hundreds of coordinates each, it becomes hard to work with. If we’re dealing with boundaries of cities, wards, districts, zones, etc, we cannot even render them without optimization.

Polygons in Google Maps have a bunch of properties and event listeners attached to them. Creating and mounting a simple polygon with basic properties like paths (70 coordinates), stroke colors, and fillColor takes around 0.7 ms.

For a 1000-coordinates polygon, it’ll take 10 ms.

For 2000 polygons having 1000 coordinates each, it’ll take 2000×10 = 20,000 ms = 20 seconds.

Time is just one of the challenges we may face, a worse one would be space consumption. Without optimization, I tried running a benchmark with 8000 polygons having around 1000 coordinates each in development mode (using Vue.js). The RAM usage of the browser tab went up to 7GB. I’m using a Ryzen 3600X processor with 32GB RAM.

Of course, the processing power of the CPU plays a major role here. Given, that Google Maps highly depends on CPU processing and can’t leverage the GPU power, there’s nothing much we can do here.

One way is to use Data Layers to create Polygons instead of native Google Maps Polygons. However, it’ll still not be enough.

We can use Douglas Peucker’s polygon simplification algorithm to simplify/optimize our polygons. This is not a loss-less algorithm. This algorithm simply reduces the number of coordinates our polygons may have with minimal change in visual appearance. We can mention what should be the intensity of change by using what we call a kink value or epsilon for the function.

The first polygon has 70 coordinates while the second one has just 7 coordinates. This heavily reduces the drawing and rendering time.

It’s worth mentioning that if the value of epsilon is too high (it usually varies between 0 and 1000), there’ll be higher chances of polygons overlapping each other. This is because, with an increased amount of kink, we’re asking to merge more and more coordinates into one another.

Other two algorithms serving the same purpose are the Visvalingam-Whyatt algorithm and the Lang algorithm. You can find their performance difference here.

Now, let’s have a code implementation of the above algorithm in JavaScript / Vue.js.

Implementation

Here’s our polygon-coordinates.js file (containing 70 coordinates):

export const polygonCoordinates = [
  {
    lat: 54.288944244384766,
    lng: -0.8960511684417725
  },
  {
    lat: 54.2889404296875,
    lng: -0.895641028881073
  },
// 68 more coordinates
]
Code language: JavaScript (javascript)

And here’s our douglas-peucker.js file containing the simplification algorithm:

export const RDouglasPeucker = (source, kink) => {
  //Ramer Douglas Peucker
  let n_source = 0,
    n_stack,
    n_dest,
    start,
    end,
    i,
    sig;
  let dev_sqr, max_dev_sqr, band_sqr;
  let x12, y12, d12, x13, y13, d13, x23, y23, d23;
  const F = (Math.PI / 180.0) * 0.5;
  const index = [];
  const sig_start = [];
  const sig_end = [];

  if (source.length < 3) return source;

  n_source = source.length;
  band_sqr = (kink * 360.0) / (2.0 * Math.PI * 6378137.0);
  band_sqr *= band_sqr;
  n_dest = 0;
  sig_start[0] = 0;
  sig_end[0] = n_source - 1;
  n_stack = 1;

  while (n_stack > 0) {
    start = sig_start[n_stack - 1];
    end = sig_end[n_stack - 1];
    n_stack--;

    if (end - start > 1) {
      x12 = source[end].lng - source[start].lng;
      y12 = source[end].lat - source[start].lat;
      if (Math.abs(x12) > 180.0) x12 = 360.0 - Math.abs(x12);
      x12 *= Math.cos(F * (source[end].lat + source[start].lat));
      d12 = x12 * x12 + y12 * y12;

      for (i = start + 1, sig = start, max_dev_sqr = -1.0; i < end; i++) {
        x13 = source[i].lng - source[start].lng;
        y13 = source[i].lat - source[start].lat;
        if (Math.abs(x13) > 180.0) x13 = 360.0 - Math.abs(x13);
        x13 *= Math.cos(F * (source[i].lat + source[start].lat));
        d13 = x13 * x13 + y13 * y13;

        x23 = source[i].lng - source[end].lng;
        y23 = source[i].lat - source[end].lat;
        if (Math.abs(x23) > 180.0) x23 = 360.0 - Math.abs(x23);
        x23 *= Math.cos(F * (source[i].lat + source[end].lat));
        d23 = x23 * x23 + y23 * y23;

        if (d13 >= d12 + d23) dev_sqr = d23;
        else if (d23 >= d12 + d13) dev_sqr = d13;
        else
          dev_sqr = ((x13 * y12 - y13 * x12) * (x13 * y12 - y13 * x12)) / d12;

        if (dev_sqr > max_dev_sqr) {
          sig = i;
          max_dev_sqr = dev_sqr;
        }
      }

      if (max_dev_sqr < band_sqr) {
        index[n_dest] = start;
        n_dest++;
      } else {
        n_stack++;
        sig_start[n_stack - 1] = sig;
        sig_end[n_stack - 1] = end;
        n_stack++;
        sig_start[n_stack - 1] = start;
        sig_end[n_stack - 1] = sig;
      }
    } else {
      index[n_dest] = start;
      n_dest++;
    }
  }

  index[n_dest] = n_source - 1;
  n_dest++;

  const r = [];
  for (let i = 0; i < n_dest; i++) r.push(source[index[i]]);
  return r;
};

Code language: JavaScript (javascript)

And finally, here’s our component file where we import these two files and optimize our polygon:

<template>
  <div>
    <div class="np-margins">
      <h4>
        Optimize Google Maps Polygon Using Ramer Douglas Peucker Algorithm
      </h4>
      <input type="number" v-model="kinkValue" placeholder="Kink value" />
      <button @click="optimizePolygon">Optimize polygon</button>
      <button @click="resetPolygon">Reset optimization</button>
      <p>Total coordinates: {{ this.drawablePolygonCoords.length }}</p>
    </div>
    <div id="polygon-label-map" class="map-margins"></div>
    <div class="np-credits">www.nightprogrammer.com</div>
  </div>
</template>

<script>
import loadGoogleMapsApi from "load-google-maps-api";
import { gMapsApiKey } from "./../constants";
import { RDouglasPeucker } from "./douglas-peucker";
import { polygonCoordinates } from "./polygon-coordinates";

export default {
  name: "PolygonMap",
  data() {
    return {
      map: null,
      googleInstance: null,
      kinkValue: 10,
      polygonCoords: polygonCoordinates,
      drawablePolygonCoords: [],
      polygonShape: null,
    };
  },
  methods: {
    optimizePolygon() {
      this.polygonShape.setMap(null);

      this.drawablePolygonCoords = RDouglasPeucker(
        this.polygonCoords,
        this.kinkValue
      );
      this.setPolygonOnMap(this.googleInstance, this.drawablePolygonCoords);
    },
    resetPolygon() {
      this.polygonShape.setMap(null);

      this.drawablePolygonCoords = this.polygonCoords;
      this.setPolygonOnMap(this.googleInstance, this.drawablePolygonCoords);
    },
    setPolygonOnMap(google, polygonCoordinates) {
      const tempBounds = new google.maps.LatLngBounds();

      for (let j = 0; j < polygonCoordinates.length; j++) {
        const x = {
          lat: polygonCoordinates[j].lat,
          lng: polygonCoordinates[j].lng,
        };
        const BoundLatLng = new google.maps.LatLng({
          lat: parseFloat(x.lat),
          lng: parseFloat(x.lng),
        });
        tempBounds.extend(BoundLatLng);
      }
      const centroid = tempBounds.getCenter();

      this.polygonShape = new google.maps.Polygon({
        paths: polygonCoordinates,
        strokeColor: "#ffffff",
        map: this.map,
        strokeWeight: 2,
        fillColor: "#7b00ff",
        fillOpacity: 0.6,
        zIndex: 99999,
        draggable: true,
      });

      this.polygonShape.setMap(this.map);

      this.map.setCenter(centroid);
      this.map.setZoom(16);
    },
  },
  mounted() {
    loadGoogleMapsApi({
      key: gMapsApiKey,
      libraries: ["places", "drawing", "geometry"],
    }).then(async () => {
      const mapZoom = 12;
      const { google } = window;
      const mapOptions = {
        zoom: mapZoom,
        mapTypeId: google.maps.MapTypeId.HYBRID,
        center: new google.maps.LatLng({ lat: 23, lng: 57 }),
        mapTypeControl: true,
        streetViewControl: false,
        mapTypeControlOptions: {
          position: google.maps.ControlPosition.BOTTOM_LEFT,
        },
      };
      this.map = new google.maps.Map(
        document.getElementById("polygon-label-map"),
        mapOptions
      );
      this.googleInstance = google;
      this.drawablePolygonCoords = this.polygonCoords;
      this.setPolygonOnMap(this.googleInstance, this.polygonCoords);
    });
  },
};
</script>

<style scoped>
.header-margins {
  margin-left: 30px;
  margin-top: 20px;
}
.np-margins {
  margin: 20px 30px;
}
.map-margins {
  height: 300px;
  width: 500px;
  margin: 20px 30px;
}
.np-credits {
  margin-left: 30px;
  margin-top: 4px;
  font-size: 12px;
}
button {
  background: rgb(0, 89, 255);
  color: #fff;
  border: 1px solid #fff;
  padding: 4px 10px;
  border-radius: 4px;
}
</style>
Code language: HTML, XML (xml)

In the above file, we’ve first imported the coordinates and RDouglasPeucker algorithmic function on line 20 and 21. We’ve taken two reactive states named polygonCoords and drawablePolygonCoords on line 30 and 31. polygonCoords will be used to keep the original coordinates set (so that we can reset back to it if needed).

drawablePolygonCoords will contain the coordinates which we’d render the polygon with. This can either be the original set of coordinates or a simplified version made by Douglas Peucker’s algorithm.

We’ve defined two methods named optimizePolygon() and resetPolygon(). The first method will use Perucker’s algorithm to simplify the coordinates. resetPolygon() will copy the original coordinates set to the drawablePolygonCoords and draw the polygon again.

This is the benchmark results for 6 runs (with disabled cache) for each type of polygon with kink value 10 on my system:

Run#	Optimized (ms)	Original (ms)
1	0.40000009536743164	0.8345006363456634
2	0.39999985694885254	1.2000000476837158
3	0.29999995231624842	1.12634999234000000
4	0.47837273927498237	0.98454409234333333
5	0.29999995231624434	1.48230925620394920
6	0.10000014305114746	0.856239482399999238

The optimized version averages at 0.32972878987915116 ms while the original version averages at 1.0806572512194437 ms.

This makes the optimized version 3.27 times faster.

Demonstration

Here’s what the above code should look like in action:

You can find a working version of the above code from my repository links below:

Codesandbox / Demo | Github