How to apply the Four Colour theorem on GeoJSON feature collection with Leaflet

Question

Imagine you have a GeoJSON feature collection of adjacent colored polygons presented in a Leaflet map; in the present case the parishes of the city of Lisbon

Run the snippet to see the map

fetch('https://geoapi.pt/municipio/lisboa/freguesias?json=1').then(r => r.json()).then(data => {
  const geojsons = data.geojsons
  
  var map = L.map('map')

  const bbox = geojsons.municipio.bbox
  const corner1 = L.latLng(bbox[1], bbox[0])
  const corner2 = L.latLng(bbox[3], bbox[2])
  const bounds = L.latLngBounds(corner1, corner2)
  map.fitBounds(bounds)
  
  L.tileLayer('https://tile.openstreetmap.org/{z}/{x}/{y}.png', {
    maxZoom: 19,
    attribution: '&copy; <a href="http://www.openstreetmap.org/copyright">OpenStreetMap</a>'
  }).addTo(map)

  // feature collection
  const parishesGeoJsonFeatureCollection = {
    type: 'FeatureCollection',
    features: geojsons.freguesias
  }

  // need this for color pallete
  const numberOfParishes = parishesGeoJsonFeatureCollection.features.length
  parishesGeoJsonFeatureCollection.features.forEach((parish, index) => {
    parish.properties.index = index
  })

  L.geoJson(parishesGeoJsonFeatureCollection, {
    style
  }).addTo(map)

  function style (feature) {
    return {
      weight: 2,
      opacity: 1,
      color: 'white',
      dashArray: '3',
      fillOpacity: 0.7,
      fillColor: getColor(feature.properties.index, numberOfParishes)
    }
  }

})

// get random color
function getColor (index, size) {
  const colors = {
    3: ['#8dd3c7', '#ffffb3', '#bebada'],
    4: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072'],
    5: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3'],
    6: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462'],
    7: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462', '#b3de69'],
    8: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462', '#b3de69', '#fccde5'],
    9: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462', '#b3de69', '#fccde5', '#d9d9d9'],
    10: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462', '#b3de69', '#fccde5', '#d9d9d9', '#bc80bd'],
    11: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462', '#b3de69', '#fccde5', '#d9d9d9', '#bc80bd', '#ccebc5'],
    12: ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462', '#b3de69', '#fccde5', '#d9d9d9', '#bc80bd', '#ccebc5', '#ffed6f']
  }

  if (size < 3) {
    return colors[3][index]
  } else if (size <= 12) {
    return colors[size][index]
  } else {
    return colors[12][index % 12]
  }
}

#map { height: 220px; }

<link rel="stylesheet" href="https://unpkg.com/[email protected]/dist/leaflet.css"
     integrity="sha256-kLaT2GOSpHechhsozzB+flnD+zUyjE2LlfWPgU04xyI="
     crossorigin=""/>
 <script src="https://unpkg.com/[email protected]/dist/leaflet.js"
     integrity="sha256-WBkoXOwTeyKclOHuWtc+i2uENFpDZ9YPdf5Hf+D7ewM="
     crossorigin=""></script>

<div id="map"></div>

How would you apply the Four Colour theorem or any suitable algorithm to avoid adjacent polygons to have the same color?

Answer 1

Thanks to @TomazicM from other stack exchange site, I could implement it. Please upvote him accordingly, not me, I just post here for users that just arrive here to know and since SO allows snippet insertion, thus you can see it working live.

It makes use of another library, named TopoJSON

const colors = ['#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462', '#b3de69', '#fccde5', '#d9d9d9', '#bc80bd', '#ccebc5', '#ffed6f']

function style (feature) {
  return {
    weight: 2,
    opacity: 1,
    color: 'white',
    dashArray: '3',
    fillOpacity: 0.7,
    fillColor: colors[feature.properties.colorIndex]
  }
} 

fetch('https://geoapi.pt/municipio/lisboa/freguesias?json=1').then(r => r.json()).then(data => {
  const geojsons = data.geojsons
  
  var map = L.map('map')

  const bbox = geojsons.municipio.bbox
  const corner1 = L.latLng(bbox[1], bbox[0])
  const corner2 = L.latLng(bbox[3], bbox[2])
  const bounds = L.latLngBounds(corner1, corner2)
  map.fitBounds(bounds)
    L.tileLayer('https://tile.openstreetmap.org/{z}/{x}/{y}.png', {
    maxZoom: 19,
    attribution: '&copy; <a href="http://www.openstreetmap.org/copyright">OpenStreetMap</a>'
  }).addTo(map)

  // feature collection
  const parishesGeoJsonFeatureCollection = {
    type: 'FeatureCollection',
    features: geojsons.freguesias
  }

var topoJSON = topojson.topology([parishesGeoJsonFeatureCollection], 1e4);

  var neighbors = topojson.neighbors(topoJSON.objects[0].geometries);
  
  var featureColors = [];
  parishesGeoJsonFeatureCollection.features.forEach((parish, index) => {
    for (var i = 0; i < colors.length; i++) {
      var found = false;
      for (var j = 0; j < neighbors[index].length; j++) {
        if (featureColors[neighbors[index][j]] == i) {
          found = true;
          break;
        }
      }
      if (!found) break;
    }
    featureColors[index] = i;
    parish.properties.colorIndex = i;
  });

  L.geoJson(parishesGeoJsonFeatureCollection, {
    style
  }).addTo(map)
})

#map { height: 220px; }

<link rel="stylesheet" href="https://unpkg.com/[email protected]/dist/leaflet.css"
     integrity="sha256-kLaT2GOSpHechhsozzB+flnD+zUyjE2LlfWPgU04xyI="
     crossorigin=""/>
 <script src="https://unpkg.com/[email protected]/dist/leaflet.js"
     integrity="sha256-WBkoXOwTeyKclOHuWtc+i2uENFpDZ9YPdf5Hf+D7ewM="
     crossorigin=""></script>
<script src="https://unpkg.com/topojson@3"></script>

<div id="map"></div>