Fast union of geometries in JavaScript using Turf.JS and RBush

fastUnion.js

// Turf union can be very slow 
// The part that is slowing down turf.union() is, that the union function has to compare all the coordinates with each other, in order to avoid duplicate coordinates
// We can speed up this process in two ways
// 1) Only compare the coordinates of the polygons that intersect (idea of ChatGPT)
// 2) Pairwise combine the polygons recursively The cost of computing the union of two polygons scales with the number of points in each. So you can reduce the runtime by reducing the number of operations that involve large polygons. (idea of https://stackoverflow.com/a/70010562/3935035) 

const findIntersectingPolygons = (geojson) => {
  const allPolygons = turf.getCoords(geojson);
  const bboxes = allPolygons.map((coords, index) => {
    const polygon = turf.polygon(coords);
    return { bbox: turf.bbox(polygon), index };
  });
  const tree = rbush.load(bboxes);
  const queryBbox = turf.bbox(geojson);
  const intersectingIndexes = [];
  const nonIntersectingIndexes = [];
  const overlaps = tree.search({
    minX: queryBbox[0],
    minY: queryBbox[1],
    maxX: queryBbox[2],
    maxY: queryBbox[3]
  });
  for (let i = 0; i < overlaps.length; i++) {
    const index = overlaps[i].index;
    const polygon = turf.polygon(allPolygons[index]);
    const intersection = turf.intersect(geojson, polygon);
    if (intersection) {
      intersectingIndexes.push(index);
    } else {
      nonIntersectingIndexes.push(index);
    }
  }
  const intersections = intersectingIndexes.map(index => turf.polygon(allPolygons[index]));
  const nonIntersections = nonIntersectingIndexes.map(index => turf.polygon(allPolygons[index]));
  return { intersections, nonIntersections };
};


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;
}

// findIntersectingPolygons() takes a valid GeoJSON Multipolygon as input and returns intersections and nonIntersections
// intersections we use as input for fasterUnion(), because there potential intersections in these geometries (thus we need to eliminate duplicate coord entries)
// in the end, we only need to put together the result of fasterUnion() and nonIntersections, which is a metter of 
// array comprehensions, because GeoJSON geometries are nothign more than fancy arrays
// Most of this code was written by ChatGPT