c# - 识别段链的算法

我有一系列片段：

ISegment[] segments

由接口定义：

public interface ISegment
{
    Point3D A { get; } // Segment start point
    Point3D B { get; } // Segment end point
}

可包含以下实例：

public class Line : ISegment
{
    public Point3D A { get; } // Line start point
    public Point3D B { get; } // Line end point
    /* ... Other line properties & methods ... */
}

或实例：

public class Arc : ISegment
{
    public Point3D A { get; } // Arc start point
    public Point3D B { get; } // Arc end point
    /* ... Other arc properties & methods ... */
}

可以用这个图像来表示：

我正在搜索一个优雅的算法，将它们识别为段链：

ISegment[][] segmentChains

结果是：

[[s1, s2, s3, s4], [s5, s6], [s7], [s8, s9, s10], [s11, s12]]

没有任何秩序考虑。
注：
输入1D数组segments可以有任何顺序
输出2D数组可以有任何顺序
弧段可以具有相同的起点和终点
欢迎大家帮忙！

最佳答案

我有一个迭代的方法应该可以工作。不过，也不知道它有多优雅。我更喜欢使用Lists而不是Arrays，因为它们可以动态扩展（初始化时不需要大小）。
方法签名如下：

public static List<List<ISegment>>GetSegmentChains(List<ISegment> segments)

其中segments是段列表，返回值是“链”列表，其中每个链是段列表。
该方法的基本思想是：
从段（候选）列表中删除候选段，并将其存储在临时列表中。
把A点和B点储存在另一个列表中
对于具有与列表中的一个点匹配的端点的每个剩余线段：
将该段的其他（不匹配）点放入列表中
将段与第一个段一起存储
从我们的候选人中去掉这部分
当没有更多的候选者时，将我们的临时列表添加到返回值列表，如果：
列表中有多个项（有效链）-或-
列表中有一个项，但其端点相同（一个单段圆）
有一种方法可以做到：

public static List<List<ISegment>>GetSegmentChains(List<ISegment> segments)
{
    // Some quick 'fail fast' validation
    var segmentChains = new List<List<ISegment>>();
    if (segments == null) return segmentChains;
    if (segments.Count == 0) return segmentChains;
    if (segments.Count == 1)
    {
        if (IsSingleSegmentChain(segments[0])) segmentChains.Add(segments);
        return segmentChains;
    }

    // Get a copy of our segments
    var candidateSegments = segments.ToList();

    // Process each one
    while (candidateSegments.Any())
    {
        // Remove the first one from the candidate list and add it to a temporary chain
        // list, and add it's endPoints to a list for comparision with other candidates
        var candidateSegment = candidateSegments.First();
        candidateSegments.Remove(candidateSegment);
        var candidateChain = new List<ISegment> { candidateSegment };
        var endPoints = new List<Point3D> {candidateSegment.A, candidateSegment.B};

        // Go through the points list, finding any candidates with a match
        while (endPoints.Any())
        {
            foreach (var endPoint in endPoints.ToList())
            {
                // Add the 'other' point to our points list from each
                // candidate that has a match with this point
                foreach (var candidate in candidateSegments
                    .Where(c => ContainsPoint(c, endPoint)).ToList())
                {
                    endPoints.Add(GetNonMatchingPoint(candidate, endPoint));
                    candidateSegments.Remove(candidate);
                    candidateChain.Add(candidate);
                }

                // Remove this point since it's been fully processed
                endPoints.Remove(endPoint);
            }
        }

        // See if we have a chain, and if so, add it to our return list
        if (candidateChain.Count == 1 && IsSingleSegmentChain(candidateChain[0]) ||
            candidateChain.Count > 1)
        {
            segmentChains.Add(candidateChain);
        }
    }

    return segmentChains;
}

类修改以包含构造函数并覆盖

public interface ISegment
{
    string Name { get; }
    Point3D A { get; }
    Point3D B { get; }
}

public class Line : ISegment
{
    public string Name { get; }
    public Point3D A { get; }
    public Point3D B { get; }

    public Line(string name, Point3D a, Point3D b)
    {
        Name = name;
        A = a;
        B = b;
    }

    public override string ToString()
    {
        return Name;
    }
}

public class Arc : ISegment
{
    public string Name { get; }
    public Point3D A { get; }
    public Point3D B { get; }

    public Arc(string name, Point3D singlePoint) : this(name, singlePoint, singlePoint)
    {
    }

    public Arc(string name, Point3D a, Point3D b)
    {
        Name = name;
        A = a;
        B = b;
    }

    public override string ToString()
    {
        return Name;
    }
}

在示例中生成段列表、确定段是否为单段链、确定段是否包含点以及从段获取不匹配点的辅助方法：

public static List<ISegment> GenerateSegmentList()
{
    // Generate the points in the diagram
    var A = new Point3D(0, 0, 0);
    var B = new Point3D(0, 0, 1);
    var C = new Point3D(0, 0, 2);
    var D = new Point3D(0, 0, 3);
    var E = new Point3D(0, 0, 4);
    var F = new Point3D(0, 0, 5);
    var G = new Point3D(0, 0, 6);
    var H = new Point3D(0, 0, 7);
    var I = new Point3D(0, 0, 8);
    var J = new Point3D(0, 0, 9);
    var K = new Point3D(0, 1, 0);
    var L = new Point3D(0, 1, 1);
    var M = new Point3D(0, 1, 2);
    var N = new Point3D(0, 1, 3);

    // Generate the segments in the diagram
    return new List<ISegment>
    {
        new Line("s1", A, B),
        new Line("s2", B, C),
        new Line("s3", C, D),
        new Line("s4", D, E),
        new Line("s5", F, G),
        new Line("s6", G, H),
        new Arc("s7", I),
        new Line("s8", J, K),
        new Line("s9", K, L),
        new Line("s10", L, J),
        new Line("s11", M, N),
        new Arc("s12", N, M)
    };
}

public static bool IsSingleSegmentChain(ISegment segment)
{
    return segment != null && segment.A == segment.B;
}

public static bool ContainsPoint(ISegment segment, Point3D pointToMatch)
{
    return segment != null && (segment.A == pointToMatch || segment.B == pointToMatch);
}

public static Point3D GetNonMatchingPoint(ISegment segment, Point3D pointToMatch)
{
    return segment == null
        ? default(Point3D)
        : (segment.A == pointToMatch)
            ? segment.B
            : segment.A;
}

示例用法

private static void Main()
{
    List<ISegment> segments = GenerateSegmentList();
    List<List<ISegment>> segmentChains = GetSegmentChains(segments);

    for(int i = 0; i < segmentChains.Count; i++)
    {
        Console.WriteLine($"Segment Chain #{i + 1}: {string.Join(" => ", segmentChains[i])}");
    }

    Console.WriteLine("\nDone!\nPress any key to exit...");
    Console.ReadKey();
}

输出

关于c# - 识别段链的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44075461/