美文网首页
算法 & 数据结构——最大凸包生成

算法 & 数据结构——最大凸包生成

作者: 落单的毛毛虫 | 来源:发表于2017-11-15 14:45 被阅读0次

    记录一个最大凸多边形生成算法:通过随机顶点,生成一个包含所有顶点的凸多边形。

    多边形生成算法

    通过随机顶点,生成一个连接所有顶点的多边形

    算法思路:

    找到出于平面坐标最下面的顶点,以这个顶点为中心,对其他顶点依据角度进行排序。排序完成后,多边形就已经生成了。

    C++实现:

    void PolygonHull(std::vector<POINT> & points)
    {
        auto val = *std::min_element(points.begin(), points.end(), [](const POINT & p1, const POINT & p2) 
            { 
                return p1.y < p2.y || p1.x < p2.x;
            });
    
        std::sort(points.begin(), points.end(), [&val](const POINT & p1, const POINT & p2)
            {
                auto a1 = GetAngle(val, p1), l1 = GetLengthSqr(p1 - val);
                auto a2 = GetAngle(val, p2), l2 = GetLengthSqr(p2 - val);
                return a1 < a2 || a1 == a2 && l1 < l2;
            });
    }
    

    最大凸包生成算法

    算法思路:

    在多边形算法的基础上,进行以下操作:

    • 1 将集合第一个顶点 p0 和第二个顶点 p1 压栈,将 p2 指向第三个顶点
    • 2 如果集合没有遍历完,则跳到步骤3,否则跳到步骤6
    • 3 判断 p2 处于 p0p1 的左边则跳到步骤4,否则跳到步骤5
    • 4 将 p2 压栈,p0,p1,p2各前进1步,跳到步骤2
    • 5 将 p1 出栈,跳到步骤2
    • 6 算法结束

    C++实现:

    std::vector<POINT> ConvexHull(std::vector<POINT> & points)
    {
        auto val = *std::min_element(points.begin(), points.end(), [](const POINT & p1, const POINT & p2) 
            { 
                return p1.y < p2.y || p1.x < p2.x;
            });
    
        std::sort(points.begin(), points.end(), [&val](const POINT & p1, const POINT & p2)
            {   
                auto a1 = GetAngle(val, p1), l1 = GetLengthSqr(p1 - val);
                auto a2 = GetAngle(val, p2), l2 = GetLengthSqr(p2 - val);
                return a1 < a2 || a1 == a2 && l1 < l2;
            });
    
        std::vector<POINT> set;
        auto iter = points.cbegin();
        set.push_back(*iter++);
        set.push_back(*iter++);
        while (iter != points.cend())
        {
            auto & p0 = *(set.cend() - 2),
                 & p1 = *(set.cend() - 1),
                 & p2 = *iter;
            if (0 > Corss(p1 - p0, p2 - p1))
                set.pop_back();
            else 
                set.push_back(*iter++);
        }
        return set;
    }
    

    相关文章

      网友评论

          本文标题:算法 & 数据结构——最大凸包生成

          本文链接:https://www.haomeiwen.com/subject/rtncvxtx.html