如何在JavaScript/D3中移除多边形边上的冗余共线点

问题说明 #

给定一个多边形的点集，部分点位于多边形某条边的两个端点之间且与端点共线，需要编写函数剔除这些冗余点，得到仅保留顶点的精简多边形点集。

实现思路 #

核心是判断每个点是否为非顶点的共线中间点：

• 对每个点（首尾点按闭合多边形逻辑循环处理），取其前一个点和后一个点，计算三点叉乘：叉乘为0则说明三点共线
• 验证当前点是否落在前后两点构成的线段范围内：通过坐标极值范围或点积方向判断
• 仅保留不满足上述共线中间点条件的点（即多边形顶点）

代码实现 #

多边形点集精简函数 #

function cleanPolygonPoints(points) {
  if (points.length < 3) return [...points]; // 少于3个点直接返回

  const cleaned = [];
  const len = points.length;

  for (let i = 0; i < len; i++) {
    const prevPoint = points[(i - 1 + len) % len]; // 前一个点，闭合循环处理
    const currPoint = points[i];
    const nextPoint = points[(i + 1) % len]; // 后一个点，闭合循环处理

    // 计算叉乘，判断三点是否共线
    const crossProduct = (nextPoint[0] - prevPoint[0]) * (currPoint[1] - prevPoint[1]) - 
                         (nextPoint[1] - prevPoint[1]) * (currPoint[0] - prevPoint[0]);

    // 叉乘不为0，说明不是共线中间点，保留
    if (crossProduct !== 0) {
      cleaned.push(currPoint);
      continue;
    }

    // 叉乘为0时，验证是否在前后点的线段范围内
    const isBetweenX = (currPoint[0] - prevPoint[0]) * (currPoint[0] - nextPoint[0]) <= 0;
    const isBetweenY = (currPoint[1] - prevPoint[1]) * (currPoint[1] - nextPoint[1]) <= 0;
    // 不在线段中间（比如是端点重合）则保留
    if (!isBetweenX || !isBetweenY) {
      cleaned.push(currPoint);
    }
    // 否则跳过该共线中间点
  }

  // 处理重复的首尾闭合点
  if (cleaned.length > 1 && JSON.stringify(cleaned[0]) === JSON.stringify(cleaned[cleaned.length - 1])) {
    cleaned.pop();
  }
  // 确保多边形闭合，添加首尾一致的点
  cleaned.push(cleaned[0]);
  return cleaned;
}

D3.js 可视化示例 #

<!DOCTYPE html>
<html>
<head>
  <script src="https://d3js.org/d3.v7.min.js"></script>
  <style>
    .container { display: flex; gap: 20px; margin: 20px; }
    svg { border: 1px solid #ddd; }
    .raw-path { fill: rgba(255, 99, 71, 0.2); stroke: #ff6347; stroke-width: 2; }
    .cleaned-path { fill: rgba(32, 178, 170, 0.2); stroke: #20b2aa; stroke-width: 2; }
    .point { r: 3; fill: #333; }
  </style>
</head>
<body>
  <div class="container">
    <div>
      <h3>原始多边形</h3>
      <svg id="rawSvg" width="400" height="400"></svg>
    </div>
    <div>
      <h3>精简后多边形</h3>
      <svg id="cleanedSvg" width="400" height="400"></svg>
    </div>
  </div>

  <script>
    // 示例原始点集
    const rawData = [
      [50, 50], [100, 100], [150, 150], [200, 50], [150, 0], [100, -50], [50, 0], [0, 50], [50, 50]
    ];
    // 获取精简后的点集
    const cleanedData = cleanPolygonPoints(rawData);

    // 通用绘图函数
    function drawPolygon(svgId, data, pathClass) {
      const svg = d3.select(`#${svgId}`);
      const scaleX = d3.scaleLinear().domain([-100, 300]).range([50, 350]);
      const scaleY = d3.scaleLinear().domain([-100, 200]).range([350, 50]);

      // 生成路径
      const lineGenerator = d3.line()
        .x(d => scaleX(d[0]))
        .y(d => scaleY(d[1]));

      svg.append("path")
        .attr("class", pathClass)
        .attr("d", lineGenerator(data));

      // 绘制点
      svg.selectAll(".point")
        .data(data)
        .enter()
        .append("circle")
        .attr("class", "point")
        .attr("cx", d => scaleX(d[0]))
        .attr("cy", d => scaleY(d[1]));
    }

    // 绘制原始和精简后的多边形
    drawPolygon("rawSvg", rawData, "raw-path");
    drawPolygon("cleanedSvg", cleanedData, "cleaned-path");
  </script>
</body>
</html>

示例效果 #

• 原始点集包含多个共线中间点（比如[50,50]→[100,100]→[150,150]这三个共线点）
• 精简后仅保留线段的两个端点[50,50]和[150,150]，其余共线中间点被剔除，多边形形状不变但点集更简洁

内容的提问来源于stack exchange，提问作者toowren