What is the fastest way to create a union of many polygons in turfjs?

Question

I have something like this but with large sets it's awfully slow:

    let unionize = (triangles) => {
        if(triangles.length == 0) {
            return null
        }

        let ret = triangles[0].feature

        triangles.forEach((t, index) => {
            if(index > 0) {
                ret = turf.union(t, t)
            }
        })

        return ret
    }

Answer 1

The bottleneck is union. It must compare all coordinates from each polygon with all coordinates, in order to avoid duplicated entries. Pickung up on @Fergals idea, here is this approach implemented in JS. And it is faster

allGeometries is an array of valid GeoJSON Polygon Geometries. This function considers inner rings as well.

function fasterUnion(allGeometries) {
  const mid = Math.floor(allGeometries.length / 2);
  let group1 = allGeometries.slice(0, mid);
  let group2 = allGeometries.slice(mid);

  while (group1.length > 1) {
    group1 = unionGroup(group1);
  }
  while (group2.length > 1) {
    group2 = unionGroup(group2);
  }

  let result;
  if (group1.length === 1 && group2.length === 1) {
    result = turf.union(group1[0], group2[0]);
  } else if (group1.length === 1) {
    result = group1[0];
  } else {
    result = group2[0];
  }

  return result;
}

function unionGroup(group) {
  let newGroup = [];
  for (let i = 0; i < group.length; i += 2) {
    let a = group[i];
    let b = i + 1 < group.length ? group[i + 1] : null;
    if (b) {
      newGroup.push(turf.union(a, b));
    } else {
      newGroup.push(a);
    }
  }
  return newGroup;
}

Another potential way is to create a spatial index like an R-Tree with a library like RBush. Since the expensive part of the union is to compare all coordinates with each other and eleminate duplicates, a way to speed this up would be to exclude the comparison of coordinates, where we savely can assume, that the polygons of these coordinates do not overlap. A quick (and rough) way to find out, which polygons do overlap and which do not overlap can be done with an R-Tree. RBush provides two methods, search() and collide() which can be used for that. Once we know which polygons do not overlap, there is no need to execute the expensive union operation for them. We only must compare the coordinates of Polygons that overlap. In The end, we only need to put the result of the union (one Polygon) and the the not overlapping polygons as identified by RBush (possible many polygons) into one polygon, which is array comprehension, because the geometry in a GeoJSON is nothing more than a fancy array put together in a certain way.