封闭多边形去除相切部分

Question

用算法 求两个封闭的多边形去除相切部分后合成的另一个封闭多边形。
提示1：多边形由点组成，一个封闭的多边形由一个首部尾部元素相同的二维数组表示

const poly1=[
            [7637, 7172],
            [7617, 7104],
            [7604, 6975],
            [7606, 6559],
            [7596, 6423],
            [7558, 6338],
            [7437, 6372],
            [7323, 6349],
            [7197, 6380],
            [6976, 6364],
            [6899, 6336],
            [6858, 6303],
            [6831, 6318],
            [6823, 6378],
            [6800, 6398],
            [6628, 6467],
            [6529, 6451],
            [6419, 6386],
            [6387, 6335],
            [6399, 6221],
            [6300, 6263],
            [6240, 6240],
            [6180, 6274],
            [6098, 6234],
            [6073, 6237],
            [6029, 6320],
            [5949, 6387],
            [5930, 6416],
            [5808, 6411],
            [5676, 6475],
            [5629, 6445],
            [5597, 6448],
            [5551, 6498],
            [5461, 6706],
            [5482, 6746],
            [5542, 6778],
            [5623, 6866],
            [5632, 6899],
            [5442, 7109],
            [5632, 7269],
            [5706, 7362],
            [5745, 7400],
            [5807, 7403],
            [5860, 7392],
            [5940, 7343],
            [6048, 7423],
            [6120, 7548],
            [6128, 7586],
            [6097, 7644],
            [5964, 7806],
            [5928, 7940],
            [5816, 7992],
            [5818, 8044],
            [5884, 8043],
            [5919, 8112],
            [5935, 8176],
            [5982, 8307],
            [6044, 8385],
            [6085, 8414],
            [6165, 8494],
            [6286, 8445],
            [6311, 8450],
            [6394, 8334],
            [6439, 8305],
            [6523, 8204],
            [6560, 8133],
            [6713, 8192],
            [6775, 8189],
            [6811, 8170],
            [7004, 7980],
            [7108, 7890],
            [7288, 7719],
            [7404, 7579],
            [7526, 7443],
            [7546, 7408],
            [7504, 7277],
            [7577, 7245],
            [7637, 7172]
          ]

提示2：因为普通的 标识封闭图形的 这个二维数组 都是头尾相连的也就是说他的首个和末尾元素都是同一个点，那么在这种情情况下 相交的公共部分就很有可能被分割 那么被分割以后的这两个封闭图形二维数组就应该出现两种情况 第一：公共部分在数组内 那么数组就是简单的被从中间截取了一半 第二种情况：公共部分在数组边界部分，这种情况又可以分三种讨论：a：公共部分从数组0下标位置往后延申，b：公共部分从数组中间某个位置延申到数组尾部，c：是a情况和b情况的结合 公共部分从首位开始延申一定长度后结束，以及后面部分是从中间部分延申至尾部。问题在于我们必须讨论两种情况下 的数组该如何拼接
提示3： a数组b数组都是情况1的情况：我们应该需要将a或者b数组展开后重新拼接成首位两连的情况 也就是说这里需要一个辅助函数 然后因为展开拼接后的数组首个和尾部的点刚好就是另一个数组中间那部分 因为另一个数组中间被截取 所以我们将他视为两部分前半部分数组的尾部的点也就是 经过展开拼接后的数组的头 而后半部分的首个点也就是被展开拼接后的数组的尾部 所以只需要将这三部分数组按顺序依次拼接就可以满足 数组a和b都是情况1的情况

Answer 1

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：

function removeOverlap(poly1, poly2) {
  const result = [];
  let i = 0, j = 0;

  while (i < poly1.length && j < poly2.length) {
    const intersect = intersectPolygons(poly1[i], poly2[j]);
    if (intersect.length > 0) {
      result.push(intersect);
      i++;
      j++;
    } else if (poly1[i][1] < poly2[j][1]) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}

function intersectPolygons(p1, p2) {
  const intersections = [];
  for (let i = 0; i < p1.length; i++) {
    for (let j = 0; j < p2.length; j++) {
      const dotProduct = (p1[i][0] - p2[j][0]) * (p1[i + 1][1] - p1[i][1]) - (p1[i + 1][0] - p1[i][0]) * (p1[i][1] - p2[j][1]);
      const crossProduct = (p1[i + 1][0] - p1[i][0]) * (p2[j][1] - p2[j + 1][1]) - (p2[j + 1][0] - p2[j][0]) * (p1[i + 1][1] - p1[i][1]);
      const lengthSquared = Math.pow(p2[j + 1][0] - p2[j][0], 2) + Math.pow(p2[j + 1][1] - p2[j][1], 2);
      const determinant = lengthSquared * dotProduct - crossProduct * crossProduct;

      if (determinant > 0) {
        const t = ((p2[j][0] - p1[i][0]) * (p2[j + 1][1] - p2[j][1]) - (p2[j + 1][0] - p2[j][0]) * (p2[j][1] - p1[i][1])) / determinant;
        const u = -((p2[j + 1][0] - p2[j][0]) * (p1[i + 1][1] - p1[i][1]) - (p1[i + 1][0] - p1[i][0]) * (p2[j + 1][1] - p2[j][1])) / determinant;
        if (u >= 0 && u <= 1 && t >= 0 && t <= 1) {
          intersections.push([p1[i][0] + t * (p1[i + 1][0] - p1[i][0]), p1[i][1] + t * (p1[i + 1][1] - p1[i][1])]);
        }
      }
    }
  }

  return intersections;
}

function removeOverlapAndCombine(poly1, poly2) {
  const nonOverlappingPoly2 = poly2.filter((_, index) => {
    for (let i = index + 1; i < poly2.length; i++) {
      if (intersectPolygons(poly2[index], poly2[i]).length > 0) {
        return false;
      }
    }
    return true;
  });

  const combinedPolygons = removeOverlap(poly1, nonOverlappingPoly2);
  const remainingPolygons = removeOverlap(nonOverlappingPoly2, poly2);

  return combinedPolygons.concat(remainingPolygons);
}

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢