将平面图面列表转换为平面点列表的算法（C#/伪代码）

核心思路 #

基于你提供的有序节点面列表和边列表，采用增量式拓扑布局：从第一个面开始分配初始坐标，之后每个新面通过共享边与已布局区域关联，通过向量翻转/延伸生成新节点坐标，确保边无重叠。无需追求美观，后续可自行调整。

实现步骤 #

• 初始化第一个面：给第一个面的节点分配基础坐标（比如简单三角形），作为布局起点。
• 关联邻接面：遍历剩余面，找到与已布局区域共享的边，以此为基准计算新面节点的相对坐标。
• 向量生成坐标：以共享边为轴，生成垂直向量确定新节点位置，保证新面在已有区域外侧，避免边重叠。
• 修复潜在重叠：对生成的坐标做简单检查，若存在非共享边相交，微调节点坐标解决。

C# 代码实现 #

首先补充Node类的坐标属性（假设你已有节点标识）：

public class Node
{
    public string Id { get; set; } // 节点唯一标识
    public double X { get; set; } // 平面X坐标
    public double Y { get; set; } // 平面Y坐标
}

核心布局函数：

public void AssignPlanarCoordinates(List<List<Node>> faces, List<Tuple<Node, Node>> edges)
{
    // 初始化第一个面的坐标
    var firstFace = faces[0];
    if (firstFace.Count < 3) throw new ArgumentException("第一个面至少包含3个节点");
    
    firstFace[0].X = 0;
    firstFace[0].Y = 0;
    firstFace[1].X = 10;
    firstFace[1].Y = 0;
    // 计算第三个节点的垂直坐标，形成初始三角形
    var edgeDx = firstFace[1].X - firstFace[0].X;
    var edgeDy = firstFace[1].Y - firstFace[0].Y;
    firstFace[2].X = firstFace[0].X - edgeDy;
    firstFace[2].Y = firstFace[0].Y + edgeDx;

    var processedNodes = new HashSet<Node>(firstFace);
    var processedFaces = new HashSet<List<Node>> { firstFace };

    // 遍历处理剩余所有面
    while (processedFaces.Count < faces.Count)
    {
        foreach (var face in faces)
        {
            if (processedFaces.Contains(face)) continue;

            // 找到当前面与已处理区域的共享边
            var sharedEdge = edges.FirstOrDefault(e => 
                processedNodes.Contains(e.Item1) && processedNodes.Contains(e.Item2));
            
            if (sharedEdge == null) continue;

            // 定位共享边在当前面中的节点位置
            int idx1 = face.IndexOf(sharedEdge.Item1);
            int idx2 = face.IndexOf(sharedEdge.Item2);
            // 确定面的遍历顺序，找到下一个未处理节点
            int nextIdx = idx1 + 1 == face.Count ? 0 : idx1 + 1;
            if (face[nextIdx] == sharedEdge.Item2)
            {
                nextIdx = idx2 + 1 == face.Count ? 0 : idx2 + 1;
            }

            var sharedNode1 = sharedEdge.Item1;
            var sharedNode2 = sharedEdge.Item2;
            var newNode = face[nextIdx];

            // 计算共享边的向量及垂直向量（用于生成新面的外侧坐标）
            var edgeVecX = sharedNode2.X - sharedNode1.X;
            var edgeVecY = sharedNode2.Y - sharedNode1.Y;
            var perpVecX = -edgeVecY;
            var perpVecY = edgeVecX;

            // 给新节点分配坐标
            newNode.X = sharedNode1.X + perpVecX;
            newNode.Y = sharedNode1.Y + perpVecY;

            // 按面的节点顺序，延伸计算剩余节点坐标
            for (int i = nextIdx + 1; i != idx1; i = i + 1 == face.Count ? 0 : i + 1)
            {
                var prevNode = face[i == 0 ? face.Count - 1 : i - 1];
                var prevPrevNode = face[i == 0 ? face.Count - 2 : i - 2];
                var vecX = prevNode.X - prevPrevNode.X;
                var vecY = prevNode.Y - prevPrevNode.Y;
                face[i].X = prevNode.X + vecX;
                face[i].Y = prevNode.Y + vecY;
            }

            // 标记当前面和节点为已处理
            processedFaces.Add(face);
            foreach (var node in face) processedNodes.Add(node);

            // 检查并修复非共享边的重叠问题
            FixEdgeOverlaps(edges, processedNodes);
            break;
        }
    }
}

// 检查并微调重叠边
private void FixEdgeOverlaps(List<Tuple<Node, Node>> edges, HashSet<Node> processedNodes)
{
    for (int i = 0; i < edges.Count; i++)
    {
        var edge1 = edges[i];
        for (int j = i + 1; j < edges.Count; j++)
        {
            var edge2 = edges[j];
            // 跳过共享节点的边（共享边属于正常拓扑结构）
            if (edge1.Item1 == edge2.Item1 || edge1.Item1 == edge2.Item2 || 
                edge1.Item2 == edge2.Item1 || edge1.Item2 == edge2.Item2)
                continue;

            // 判断两条非共享边是否相交
            if (DoSegmentsIntersect(edge1.Item1, edge1.Item2, edge2.Item1, edge2.Item2))
            {
                // 微调其中一个节点的坐标，解决重叠
                edge1.Item1.X += 0.01;
                edge1.Item1.Y += 0.01;
                j--; // 重新检查当前边
            }
        }
    }
}

// 向量叉乘法判断两条线段是否相交
private bool DoSegmentsIntersect(Node a1, Node a2, Node b1, Node b2)
{
    double ccw1 = CrossProduct(a2.X - a1.X, a2.Y - a1.Y, b1.X - a1.X, b1.Y - a1.Y);
    double ccw2 = CrossProduct(a2.X - a1.X, a2.Y - a1.Y, b2.X - a1.X, b2.Y - a1.Y);
    double ccw3 = CrossProduct(b2.X - b1.X, b2.Y - b1.Y, a1.X - b1.X, a1.Y - b1.Y);
    double ccw4 = CrossProduct(b2.X - b1.X, b2.Y - b1.Y, a2.X - b1.X, a2.Y - b1.Y);

    return (ccw1 * ccw2 < 0) && (ccw3 * ccw4 < 0);
}

private double CrossProduct(double x1, double y1, double x2, double y2)
{
    return x1 * y2 - x2 * y1;
}

注意事项 #

• 代码中用IndexOf匹配节点，实际项目建议用节点ID做匹配，避免引用比较的问题。
• 若你的拓扑结构是严格平面图，微调步骤可能很少用到；如果存在复杂拓扑，可适当增大微调值。
• 初始坐标的大小可根据需求调整，后续可统一缩放或平移所有节点坐标。

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