drawing-board-service/src/utils/polygon.ts

/**
 * 高效提取连通段（包括闭合多边形和开放折线）
 */
export function extractConnectedSegments(
  segments: { a: number; b: number }[]
): number[][] {
  if (segments.length === 0) return [];

  // 1. 构建邻接表
  const adj: Map<number, Set<number>> = new Map();
  for (const { a, b } of segments) {
    if (a === b) continue; // 忽略自环
    if (!adj.has(a)) adj.set(a, new Set());
    if (!adj.has(b)) adj.set(b, new Set());
    adj.get(a)!.add(b);
    adj.get(b)!.add(a);
  }

  const result: number[][] = [];

  // 2. 首先提取所有“开放路径” (从度数为 1 的点开始)
  // 这样做可以消除干扰，剩下的一定是纯粹的环结构
  for (const [node, neighbors] of adj.entries()) {
    if (neighbors.size === 1) {
      const path: number[] = [node];
      let curr = node;
      
      while (adj.has(curr) && adj.get(curr)!.size > 0) {
        const next = adj.get(curr)!.values().next().value!;
        path.push(next);
        
        // 删除已经处理的边
        adj.get(curr)!.delete(next);
        adj.get(next)!.delete(curr);
        
        // 如果 next 点没边了，从图中移除
        if (adj.get(curr)!.size === 0) adj.delete(curr);
        curr = next;
        
        // 如果遇到了分叉点（度数大于1）或终点，停止
        if (!adj.has(curr) || adj.get(curr)!.size !== 1) break;
      }
      if (path.length > 1) result.push(path);
    }
  }

  // 3. 处理剩下的部分（此时图中只剩下闭合环）
  // 采用简单的深度优先遍历提取环
  const nodes = Array.from(adj.keys());
  for (const startNode of nodes) {
    if (!adj.has(startNode)) continue;

    const path: number[] = [startNode];
    let curr = startNode;

    while (adj.has(curr) && adj.get(curr)!.size > 0) {
      const next = adj.get(curr)!.values().next().value!;
      path.push(next);

      adj.get(curr)!.delete(next);
      adj.get(next)!.delete(curr);
      
      if (adj.get(curr)!.size === 0) adj.delete(curr);
      
      curr = next;
      if (curr === startNode) break; // 环闭合
    }
    
    if (path.length > 1) {
      result.push(path);
    }
  }

  return result;
}


/**
 * 从无向线段中提取所有闭合环（多边形）和开放路径
 * @param segments 线段数组，每条线段由两个点组成（无方向性）
 * @returns 返回所有闭合环和开放路径，每个路径用点数组表示
 */
export function extractConnectedNoDirectionSegments(
  segments: { a: number; b: number }[]
): number[][] {
  // 1. 构建无向图邻接表
  const graph: Record<number, number[]> = {};
  for (const { a, b } of segments) {
    if (!graph[a]) graph[a] = [];
    if (!graph[b]) graph[b] = [];
    graph[a].push(b);
    graph[b].push(a);
  }

  // 2. 边访问记录（确保 (a,b) 和 (b,a) 被视为同一条边）
  const edgeKey = (a: number, b: number) => (a < b ? `${a},${b}` : `${b},${a}`);

  // 3. 结果收集
  const result: number[][] = [];
  const polygonSet = new Set<string>(); // 用于去重

  // 4. 标准化多边形（按点集排序去重）
  const normalizePolygon = (polygon: number[]) => {
    const points = [...new Set(polygon.slice(0, -1))].sort((a, b) => a - b);
    return JSON.stringify(points);
  };

  // 5. DFS 查找闭合环（无向图）
  function findPolygons(start: number) {
    const stack: {
      current: number;
      path: number[];
      visitedEdges: Set<string>;
    }[] = [{ current: start, path: [start], visitedEdges: new Set() }];

    while (stack.length > 0) {
      const { current, path, visitedEdges } = stack.pop()!;

      for (const neighbor of graph[current]) {
        const edge = edgeKey(current, neighbor);

        // 跳过已访问的边
        if (visitedEdges.has(edge)) continue;

        // 发现闭合环（路径长度 > 2 且回到起点）
        if (neighbor === start && path.length > 2) {
          const closedPath = [...path, start];
          const polyKey = normalizePolygon(closedPath);

          if (!polygonSet.has(polyKey)) {
            polygonSet.add(polyKey);
            result.push(closedPath);
          }
          continue;
        }

        // 避免重复访问点（起点除外）
        if (neighbor !== start && path.includes(neighbor)) continue;

        const newVisitedEdges = new Set(visitedEdges);
        newVisitedEdges.add(edge);
        stack.push({
          current: neighbor,
          path: [...path, neighbor],
          visitedEdges: newVisitedEdges,
        });
      }
    }
  }

  // 6. 查找所有闭合环
  for (const node in graph) {
    const nodeId = Number(node);
    if (graph[nodeId].length >= 2) {
      findPolygons(nodeId);
    }
  }

  // 7. 查找开放路径（度数为1的点）
  const visitedNodes = new Set<number>();
  for (const node in graph) {
    const nodeId = Number(node);
    if (visitedNodes.has(nodeId)) continue;

    // 开放路径必须从端点开始（度数为1的点）
    if (graph[nodeId].length === 1) {
      const path: number[] = [];
      let current: number | null = nodeId;
      let prev: number | null = null;

      while (current !== null) {
        visitedNodes.add(current);
        path.push(current);

        // 找到下一个未访问的相邻点
        let next: number | null = null;
        for (const neighbor of graph[current]) {
          if (neighbor !== prev && !visitedNodes.has(neighbor)) {
            next = neighbor;
            break;
          }
        }

        prev = current;
        current = next;
      }

      if (path.length >= 2) {
        result.push(path);
      }
    }
  }

  return result;
}