Search code examples
gisopenlayerspolygonnested-loopsturfjs

How to merge multiple intersecting polygons

I'm trying to merge or group polygons using turfjs.

The following illustration shows what it looks like before and how it should look like after the merge.

enter image description here

I'm working with Openlayers and Typescript and both have Polygons hence the alias TurfPolygon etc. I'm convert my OpenLayers Polygons to Turfjs Polygons first, so I can use Turf functions.

const mergedIds: number[] = [];
const t0 = performance.now();

    for (const object of arrayTurfObjects) {
        if (mergedIds.find(x => x === object.properties.mergedId)) {
            continue;
        }

        let mergeResultPolygon: TurfFeature<TurfPolygon> | null = null;

        for (let indexNested = 0; indexNested < arrayTurfObjects.length; indexNested++) {
            const nestedObject = arrayTurfObjects[indexNested];

            if(nestedObject === object){
                continue;
            }

            if(mergedIds.find(x => x === nestedObject.properties.mergedId)){
                continue;
            }

            if(mergeResultPolygon){
                if(booleanIntersects(mergeResultPolygon, nestedObject)){
                    mergeResultPolygon = TurfUnion(mergeResultPolygon, nestedObject) as TurfFeature<TurfPolygon, any>;
                    mergedIds.push(nestedObject.properties.mergedId);
                    indexNested = 0;
                }
            } else {
                if(booleanIntersects(object, nestedObject)){
                    mergeResultPolygon = TurfUnion(object, nestedObject) as TurfFeature<TurfPolygon, any>;
                    mergedIds.push(nestedObject.properties.mergedId);
                    indexNested = 0;
                }
            }
        }

        if (mergeResultPolygon) {
            const polygon = new Polygon(mergeResultPolygon.geometry.coordinates);
            const feature = new Feature(polygon);
            feature.setStyle(new Style({
                stroke: new Stroke({
                    color: ColorCode.BLACK,
                    width: 5,
                }),
                fill: new Fill({
                    color: 'rgba(255,0,0, 0.6)',
                }),
            }));
            //Here is an function to add the mergeResultPolygon to the map to check if it's correct
        }
}

const t1 = performance.now();
console.log((t1 - t0) + ' milliseconds.');

I'm iterating over the same array, which contains the polygons twice. First I check if the polygon is already merged, so I can skip, and I'm declaring my merge result polygon. Then comes the nested loop where I skip the polygon, if it's the same as the polygon in my outer loop and if its already merged.

To start my merging process I'm looking for the first polygon that intersects the current outer loop polygon, so I can set a value for my mergeResultPolygon. After that I just merge more polygons to that variable.

As you can see I have to reset the nested loop, so I can iterate again. I'm doing this, because I don't have any kind of order, so the previous polygon could intersect the merge Result Polygon.

My problem is that I'm doing this on the client side and the performance is not that great.

Is there a better solution for this problem?

Solution

  • Demonstration of getting merged polygons from a union of all polygons

    <!doctype html>
<html lang="en">
  <head>
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/openlayers/openlayers.github.io@master/en/v6.5.0/css/ol.css" type="text/css">
    <style>
      html, body, .map {
        margin: 0;
        padding: 0;
        width: 100%;
        height: 100%;
      }
    </style>
    <script src="https://cdn.jsdelivr.net/gh/openlayers/openlayers.github.io@master/en/v6.5.0/build/ol.js"></script>
    <script src="https://unpkg.com/@turf/[email protected]/turf.min.js"></script>
  </head>
  <body>
    <div id="map" class="map"></div>
    <script type="text/javascript">

      var count = 200;
      var features = new Array(count);
      var e = 4500000;
      for (var i = 0; i < count; ++i) {
        var coordinates = [2 * e * Math.random() - e, 2 * e * Math.random() - e];
        features[i] = new ol.Feature(new ol.geom.Polygon.fromExtent(ol.extent.buffer(coordinates.concat(coordinates), 200000)));
      }

      var source = new ol.source.Vector({
        features: features,
      });

      var map = new ol.Map({
        target: 'map',
        layers: [
          new ol.layer.Tile({
            source: new ol.source.OSM()
          }),
          new ol.layer.Vector({
            source: source
          })
        ],
        view: new ol.View({
          center: [0, 0],
          zoom: 2
        })
      });

      var result;
      format = new ol.format.GeoJSON();
      source.forEachFeature(function(feature) {
        var turfPolygon = format.writeFeatureObject(feature);
        if (!result) {
          result = turfPolygon;
        } else {
          result = turf.union(result, turfPolygon);
        }
      });

      var results = [];
      var olResult = format.readFeature(result);
      if (olResult.getGeometry().getType() === 'MultiPolygon') {
        olResult.getGeometry().getPolygons().forEach(function(polygon) {
          results.push(new ol.Feature(polygon));
        });
      } else {
        results.push(olResult);
      }

      map.addLayer(
        new ol.layer.Vector({
          source: new ol.source.Vector({
            features: results,
          }),
          style: new ol.style.Style({
            stroke: new ol.style.Stroke({
              color: 'red',
              width: 2
            })
          })
        })
      );

    </script>
  </body>
</html>