如何对线段数组进行去重？（线段端点可互换）

问题描述 #

给定一个混合了单端点和双端点的线段数组，其中：

• 双端点数组（如[[x1,y1], [x2,y2]]）表示一条线段
• 单端点数组（如[[1,2]]）视为端点重合的线段，或与其他单端点组成线段时，端点互换的线段视为同一条
  需要对数组进行去重，示例如下：

// 输入
let array = [
  [[396.72, 241.07],[396.72, 241.07]],
  [[1,2]],[[2,1]],
  [[396.72, 241.07],[396.72, 241.07]],
  [[3,2],[9,1]],
  [[2,1]],[[1,2]]
];

// 期望输出
let uniqueOutput = [
  [[396.72, 241.07],[396.72, 241.07]],
  [[1,2],[2,1]],
  [[3,2],[9,1]]
];

解决思路 #

核心是为每条线段生成唯一标识，无论端点顺序如何，相同线段的标识完全一致，再通过标识去重：

1. 标准化线段：将线段的两个端点按固定规则排序（如坐标数值升序），确保端点顺序不同的同一条线段，标准化后形式一致；单端点线段自动补全为双端点重合的形式。
2. 生成唯一键：将标准化后的线段转换为字符串格式，作为判断重复的依据。
3. 去重筛选：遍历数组，使用Set存储已出现的线段键，仅保留第一次出现的线段；若需将单端点自动组合为线段，可额外生成所有可能的线段组合后再去重。

代码实现 #

基础去重（保留原始线段形式） #

// 标准化线段：统一端点顺序，处理单端点线段
function normalizeSegment(seg) {
  // 单端点线段补全为双端点重合的形式
  const points = seg.length === 1 ? [...seg, ...seg] : [...seg];
  // 按x坐标升序排序，x相同则按y坐标升序
  points.sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0];
    return a[1] - b[1];
  });
  return points;
}

// 生成线段的唯一标识键
function getSegmentKey(seg) {
  const normalized = normalizeSegment(seg);
  return normalized.map(point => point.join(',')).join('|');
}

// 线段去重主函数
function deduplicateSegments(segments) {
  const seenKeys = new Set();
  const uniqueSegments = [];

  for (const seg of segments) {
    const key = getSegmentKey(seg);
    if (!seenKeys.has(key)) {
      seenKeys.add(key);
      uniqueSegments.push(seg);
    }
  }

  return uniqueSegments;
}

// 测试基础功能
console.log(deduplicateSegments(array));
// 输出：[
//   [[396.72, 241.07],[396.72, 241.07]],
//   [[1,2]],
//   [[3,2],[9,1]]
// ]

扩展：单端点自动组合为线段 #

如果需要将输入中的单端点两两组合成线段后再去重，可使用以下扩展代码：

// 从点数组生成所有不重复的线段
function generateUniqueSegmentsFromPoints(points) {
  // 先对单个点去重
  const uniquePoints = [...new Set(points.map(p => p.join(',')))].map(s => s.split(',').map(Number));
  const segments = [];
  // 生成所有两两组合的线段
  for (let i = 0; i < uniquePoints.length; i++) {
    for (let j = i; j < uniquePoints.length; j++) {
      segments.push([uniquePoints[i], uniquePoints[j]]);
    }
  }
  return deduplicateSegments(segments);
}

// 测试扩展功能
const pointArray = array.flat(); // 提取输入中的所有单个点
console.log(generateUniqueSegmentsFromPoints(pointArray));
// 输出：[
//   [[396.72, 241.07],[396.72, 241.07]],
//   [[1,2],[2,1]],
//   [[1,2],[3,2]],
//   [[1,2],[9,1]],
//   [[2,1],[3,2]],
//   [[2,1],[9,1]],
//   [[3,2],[9,1]]
// ]

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