概述

在工作中经常会遇到将多个多边形合并成一个多边形的需求，如果多边形是相交的，可以使用turf进行合并，但是如果多边形不相交，用turf合并后的结果是一个复杂多边形，这个结果有时候不满足我们的需求，所以本文分享一个不用turf并且能合并成一个多边形的实现。

效果

image.png

实现

1. 核心思路

• 从所有多边形中提取所有顶点坐标
• 计算这些点的凸包（最小凸多边形）
• 将凸包结果转换为WKT格式输出

2. 代码

const { wktToGeoJSON } = require("@terraformer/wkt");

// 多边形的WKT
const wktArray = [];

// 辅助函数：从WKT字符串中提取坐标点
function extractPointsFromWKT(wkt) {
  const geojson = wktToGeoJSON(wkt);
  return extractPointsFromGeojson(geojson);
}

function extractPointsFromGeojson(geojson) {
  if (geojson.type === "Feature") {
    geojson = geojson.geometry;
  }
  let points = [];
  if (geojson.type === "MultiPolygon") {
    for (const polygon of geojson.coordinates) {
      points.push(
        ...extractPointsFromGeojson({ type: "Polygon", coordinates: polygon })
      );
    }
    return points;
  }
  for (const coordinates of geojson.coordinates) {
    for (const coords of coordinates) {
      points.push({ x: coords[0], y: coords[1] });
    }
  }
  return points;
}

// 计算凸包算法（Andrew's monotone chain算法）
function convexHull(points) {
  if (points.length <= 3) return points;

  points.sort((a, b) => (a.x !== b.x ? a.x - b.x : a.y - b.y));

  const lower = [];
  for (const p of points) {
    while (
      lower.length >= 2 &&
      cross(lower[lower.length - 2], lower[lower.length - 1], p) <= 0
    ) {
      lower.pop();
    }
    lower.push(p);
  }

  const upper = [];
  for (let i = points.length - 1; i >= 0; i--) {
    const p = points[i];
    while (
      upper.length >= 2 &&
      cross(upper[upper.length - 2], upper[upper.length - 1], p) <= 0
    ) {
      upper.pop();
    }
    upper.push(p);
  }

  lower.pop();
  upper.pop();

  return lower.concat(upper);
}

// 计算叉积
function cross(o, a, b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

// 将点集转换为WKT格式
function pointsToWKT(points) {
  const coords = points.map((p) => `${p.x} ${p.y}`).join(",");
  return `POLYGON ((${coords},${points[0].x} ${points[0].y}))`;
}

// 主函数：合并所有多边形
function mergePolygonsToMinArea() {
  let allPoints = [];

  // 提取所有点
  // WKT
  for (const wkt of wktArray) {
    const points = extractPointsFromWKT(wkt);
    allPoints.push(...points);
  }
  // GEOJSON
  // for (const polygon of polygons) {
  //   const points = extractPointsFromGeojson(polygon);
  //   allPoints.push(...points);
  // }

  // 计算凸包
  const hull = convexHull(allPoints);

  // 转换为WKT
  return pointsToWKT(hull);
}

// 使用示例
console.time('caculate')
const mergedPolygon = mergePolygonsToMinArea();
const json = wktToGeoJSON(mergedPolygon);
console.log(JSON.stringify(json));
console.timeEnd('caculate')