C# 实现连续水平/垂直线段序列的相交判断

现有N段固定单位长度的连续水平、垂直线段，以移动方向序列形式存储，可选方向为右、左、下、上四类。需要实现判断逻辑：若序列对应的折线路径存在自相交，则返回true，否则返回false。

• 测试用例：当N=6，方向序列为{"up", "left", "down", "down", "right", "up"}时，预期返回true
• 现有代码存在两处明显问题：一是坐标计算方法每次循环都重置坐标原点，无法正确累计路径；二是仅返回终点坐标，未存储全量线段信息，无法支撑相交判断。

• 第一步：修正坐标遍历逻辑，从原点(0,0)出发，按方向序列逐段移动，记录每一段线段的两个端点坐标，生成完整的线段列表。
• 第二步：由于所有线段只有水平、垂直两种，相交判定可以简化，不需要使用复杂的通用线段相交算法：
  • 水平线段Y坐标固定，X值落在两个端点的X区间内
  • 垂直线段X坐标固定，Y值落在两个端点的Y区间内
  • 若两条线段同为水平/垂直：共线且坐标区间存在重叠即为相交
  • 若两条线段一水平一垂直：垂直线段的X落在水平线段的X区间内，同时水平线段的Y落在垂直线段的Y区间内即为相交
  • 注意：直接相邻的线段本身就是端点连接，属于路径正常结构，不需要判定，遍历线段对时跳过索引差小于2的组合即可。
• 第三步：遍历所有非相邻线段对，只要有一对满足相交条件，直接返回true；所有线段对遍历完无相交则返回false。

// 线段结构，存储两个端点坐标
readonly record struct LineSegment(int X1, int Y1, int X2, int Y2)
{
    public bool IsHorizontal => Y1 == Y2;
    public int XMin => Math.Min(X1, X2);
    public int XMax => Math.Max(X1, X2);
    public int YMin => Math.Min(Y1, Y2);
    public int YMax => Math.Max(Y1, Y2);
}

static (int, int) GetCoordinates(string[] sectionDirection, int numberOfSections)
{
    (int X, int Y) pos = (0, 0);
    foreach (string move in sectionDirection)
    {
        switch (move)
        {
            case "left":
                pos.X--;
                break;
            case "right":
                pos.X++;
                break;
            case "down":
                pos.Y--;
                break;
            case "up":
                pos.Y++;
                break;
        }
    }
    return (pos.X, pos.Y);
}

static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
{
    List<LineSegment> segments = new List<LineSegment>();
    (int X, int Y) current = (0, 0);
    
    // 生成所有线段
    foreach (string move in sectionDirection)
    {
        (int X, int Y) next = current;
        switch (move)
        {
            case "left":
                next.X--;
                break;
            case "right":
                next.X++;
                break;
            case "down":
                next.Y--;
                break;
            case "up":
                next.Y++;
                break;
        }
        segments.Add(new LineSegment(current.X, current.Y, next.X, next.Y));
        current = next;
    }

    // 遍历所有非相邻线段对判断相交
    for (int i = 0; i < segments.Count; i++)
    {
        for (int j = i + 2; j < segments.Count; j++)
        {
            if (IsIntersect(segments[i], segments[j]))
            {
                return true;
            }
        }
    }
    return false;
}

// 水平/垂直线段相交判定
static bool IsIntersect(LineSegment a, LineSegment b)
{
    if (a.IsHorizontal && b.IsHorizontal)
    {
        // 两条都是水平，Y相同且X区间重叠
        if (a.Y1 != b.Y1) return false;
        return a.XMin <= b.XMax && b.XMin <= a.XMax;
    }
    else if (!a.IsHorizontal && !b.IsHorizontal)
    {
        // 两条都是垂直，X相同且Y区间重叠
        if (a.X1 != b.X1) return false;
        return a.YMin <= b.YMax && b.YMin <= a.YMax;
    }
    else
    {
        // 一水平一垂直，先区分哪个是水平哪个是垂直
        LineSegment horizontal = a.IsHorizontal ? a : b;
        LineSegment vertical = a.IsHorizontal ? b : a;
        
        // 垂直线的X在水平线段X区间内，水平线的Y在垂直线段Y区间内即为相交
        return vertical.X1 >= horizontal.XMin 
               && vertical.X1 <= horizontal.XMax 
               && horizontal.Y1 >= vertical.YMin 
               && horizontal.Y1 <= vertical.YMax;
    }
}

针对给出的测试用例，路径最终会回到起点(0,0)，最后一段线段和第一段线段在(0,0)处相交，函数会正确返回true，符合预期。

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