求二维线段集紧围界有序点序列生成的编程算法

你这个场景有个非常关键的约束可以大幅简化算法：每条线段必有一个端点y=0，另一个端点属于围界点，因此不需要额外生成候选点，所有围界点都来自输入线段的非y=0端点。

算法步骤（改进卷包裹法） #

预处理阶段 #

• 遍历所有输入线段，提取所有y≠0的端点存入候选点集S，每个点同步绑定其所属的输入线段用于后续相交校验
• 确定起始点：若已预先指定起点a直接使用，否则取S中x坐标最小的点作为a；若已指定终点i直接使用，否则取S中x坐标最大的点作为i。如果需要生成完整闭合围界，把终点设置为起点即可，迭代到回到起点就得到闭合凹包。

迭代生成围界序列 #

// 初始化
List<Point> 围界序列 = new List<Point> { 起点a };
HashSet<Point> 已选点 = new HashSet<Point> { 起点a };
Point 当前点 = 起点a;

// 迭代直到到达终点
while (当前点 != 终点i)
{
    Point 最优下一点 = null;
    double 最小极角 = double.MaxValue;
    
    // 遍历所有未选的候选点
    foreach (Point p in S.Except(已选点))
    {
        // 校验1：所有候选点都在当前点到p的线段同侧（保证所有线段在围界同一侧）
        bool 合法 = true;
        foreach (Point q in S)
        {
            if (q == 当前点 || q == p) continue;
            // 二维叉积计算：(p.x - 当前点.x)*(q.y - 当前点.y) - (p.y - 当前点.y)*(q.x - 当前点.x)
            double 叉积 = (p.X - 当前点.X) * (q.Y - 当前点.Y) - (p.Y - 当前点.Y) * (q.X - 当前点.X);
            // 阈值1e-6处理浮点数精度问题，若生成围界方向不对，把判断条件改为叉积 > 1e-6即可
            if (叉积 < -1e-6)
            {
                合法 = false;
                break;
            }
        }
        if (!合法) continue;
        
        // 校验2：当前点到p的线段不与任何输入线段相交
        foreach (Line seg in 所有输入线段)
        {
            if (线段相交(当前点, p, seg.端点1, seg.端点2))
            {
                合法 = false;
                break;
            }
        }
        if (!合法) continue;
        
        // 计算当前点到p的极角，选最小的（最顺时针方向）作为最优下一点
        double 极角 = Math.Atan2(p.Y - 当前点.Y, p.X - 当前点.X);
        if (极角 < 最小极角)
        {
            最小极角 = 极角;
            最优下一点 = p;
        }
    }
    
    // 加入序列，更新当前点
    围界序列.Add(最优下一点);
    已选点.Add(最优下一点);
    当前点 = 最优下一点;
}

C#实现注意事项 #

1. 点和线段的结构体需要重写Equals和GetHashCode方法，保证HashSet的判重逻辑正确
2. 线段相交判断可以用标准的跨立实验实现，同样需要加入1e-6左右的浮点数精度阈值
3. 如果候选点数量超过千级，可以提前对候选点按极角排序优化遍历效率

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