如何检测图中由坐标点描述的边的重叠区域及涉及边信息？

我有一批由(x, y)坐标点描述的折线图边，示例图包含两处重叠，共有4条边，定义如下：

边定义 #

A -> B #

const edgeAB = [
  { x: 375, y: 130 },
  { x: 375, y: 160 },
  { x: 165, y: 160 },
  { x: 165, y: 230 },
];

A -> C #

const edgeAC = [
  { x: 375, y: 130 },
  { x: 375, y: 160 },
  { x: 585, y: 160 },
  { x: 585, y: 230 },
];

C -> B #

const edgeCB = [
  { x: 585, y: 330 },
  { x: 585, y: 360 },
  { x: 350, y: 360 },
  { x: 350, y: 280 },
  { x: 300, y: 280 },
];

B -> C #

const edgeBC = [
  { x: 165, y: 330 },
  { x: 165, y: 360 },
  { x: 400, y: 360 },
  { x: 400, y: 280 },
  { x: 450, y: 280 },
];

以下是检测这些边的重叠区域、获取起止位置及涉及边信息的具体方案：

核心思路 #

这些边都是由连续坐标点构成的折线，重叠检测的本质是检查两条折线的单一线段是否共线且存在重叠区间，再进一步合并关联的重叠区间，最终输出完整的重叠信息。

具体步骤 #

1. 拆分折线为单线段 #

将每条折线拆分为两两相邻坐标点组成的单线段，同时记录每条单线段的：

• 所属原边名称（如A->B）
• 在原折线中的起始/结束坐标点索引
• 线段类型（水平/垂直，针对示例中的轴对齐场景）
• 线段在对应坐标轴上的范围（水平线段记录x的起止值，垂直线段记录y的起止值）

2. 检测线段间的共线与重叠 #

对每一对不同的单线段，执行两步判断：

共线判断（轴对齐场景简化）

• 水平线段：两条线段的y值完全相同
• 垂直线段：两条线段的x值完全相同
  非轴对齐线段可通过向量叉积验证共线性，此处针对示例场景简化处理。

重叠区间判断

共线后，将线段投影到对应坐标轴，计算区间交集：

• 水平线段：取两条线段x范围的交集，若交集的起始值≤结束值，则存在重叠，重叠区域的y值与线段一致
• 垂直线段：取两条线段y范围的交集，若交集的起始值≤结束值，则存在重叠，重叠区域的x值与线段一致

3. 合并重叠区间并关联原边 #

如果同一条原边的相邻单线段都与另一条边的单线段重叠，将这些连续的重叠区间合并为一个完整的重叠区域，同时记录所有涉及的原边，以及重叠区域在原边中的坐标点索引范围。

示例验证 #

针对你提供的四条边，可检测出两处重叠：

1. A->B与A->C的起始垂直段
   重叠区域：(375, 130) -> (375, 160)，涉及边：A->B、A->C
2. C->B与B->C的中间水平段
   重叠区域：(350, 360) -> (400, 360)，涉及边：C->B、B->C

代码实现（JavaScript） #

// 拆分折线为单线段，返回包含线段元数据的数组
function splitEdgeToSegments(edgeName, edgePoints) {
  const segments = [];
  for (let i = 0; i < edgePoints.length - 1; i++) {
    const p1 = edgePoints[i];
    const p2 = edgePoints[i + 1];
    const isHorizontal = p1.y === p2.y;
    segments.push({
      edgeName,
      startPointIndex: i,
      endPointIndex: i + 1,
      p1,
      p2,
      type: isHorizontal ? 'horizontal' : 'vertical',
      range: isHorizontal 
        ? [Math.min(p1.x, p2.x), Math.max(p1.x, p2.x)]
        : [Math.min(p1.y, p2.y), Math.max(p1.y, p2.y)]
    });
  }
  return segments;
}

// 检测两条共线线段的重叠区域
function findSegmentOverlap(s1, s2) {
  // 非同类线段直接排除
  if (s1.type !== s2.type) return null;
  // 轴对齐场景下的共线验证
  if (s1.type === 'horizontal' && s1.p1.y !== s2.p1.y) return null;
  if (s1.type === 'vertical' && s1.p1.x !== s2.p1.x) return null;

  // 计算区间交集
  const overlapStart = Math.max(s1.range[0], s2.range[0]);
  const overlapEnd = Math.min(s1.range[1], s2.range[1]);
  if (overlapStart > overlapEnd) return null;

  // 构造重叠区域的起止坐标
  const startPoint = s1.type === 'horizontal' 
    ? { x: overlapStart, y: s1.p1.y } 
    : { x: s1.p1.x, y: overlapStart };
  const endPoint = s1.type === 'horizontal' 
    ? { x: overlapEnd, y: s1.p1.y } 
    : { x: s1.p1.x, y: overlapEnd };

  return {
    involvedEdges: [s1.edgeName, s2.edgeName],
    startPoint,
    endPoint,
    // 记录重叠线段在原边中的位置
    edgeSegmentInfo: [
      { edgeName: s1.edgeName, segmentStartIndex: s1.startPointIndex },
      { edgeName: s2.edgeName, segmentStartIndex: s2.startPointIndex }
    ]
  };
}

// 批量检测所有边的重叠区域
function detectAllEdgeOverlaps(edges) {
  const allSegments = [];
  // 拆分所有边为单线段
  for (const [edgeName, points] of Object.entries(edges)) {
    allSegments.push(...splitEdgeToSegments(edgeName, points));
  }

  const overlaps = [];
  // 两两检测线段，避免重复检测
  for (let i = 0; i < allSegments.length; i++) {
    for (let j = i + 1; j < allSegments.length; j++) {
      const overlap = findSegmentOverlap(allSegments[i], allSegments[j]);
      if (overlap) overlaps.push(overlap);
    }
  }
  return overlaps;
}

// 测试用例
const edges = {
  'A->B': [
    { x: 375, y: 130 }, { x: 375, y: 160 }, { x: 165, y: 160 }, { x: 165, y: 230 }
  ],
  'A->C': [
    { x: 375, y: 130 }, { x: 375, y: 160 }, { x: 585, y: 160 }, { x: 585, y: 230 }
  ],
  'C->B': [
    { x: 585, y: 330 }, { x: 585, y: 360 }, { x: 350, y: 360 }, { x: 350, y: 280 }, { x: 300, y: 280 }
  ],
  'B->C': [
    { x: 165, y: 330 }, { x: 165, y: 360 }, { x: 400, y: 360 }, { x: 400, y: 280 }, { x: 450, y: 280 }
  ]
};

// 执行检测并输出结果
console.log(detectAllEdgeOverlaps(edges));

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