递归方法中的c ++凸包

Question

我正在尝试调试 "convex hull" jarvis 的算法。 "convex hull" 问题是，给定一个平面上 n 个点的集合 P，找到一个子集 CH(P)，它构成包含所有其他点的凸多边形的顶点。递归地编写此函数，但永远陷入循环中 return 分段错误

    int main()
{
    vector<Point> hull(20);
    int n,x,y;
    cin >> n;
    vector<Point> ps;
    Point p;
//  Point p1,p2,q1,q2;

    while(cin >> x >> y)
    {   
        p.x = x;
        p.y = y;
        ps.push_back(p);
    }
    int base = find_leftmost_point(ps, n);
    hull.push_back(ps[base]);
    vector<Point> po = convexHull(ps, base, hull);
    cout << perimeter(po) << endl;
    return 0;
}

vector<Point> convexHull(vector<Point> points, int base, vector<Point> &hull)
{

    int p, q;

    p = base;   
    q = (p+1) % points.size();
    if (points.size() <= 3) 
    {

        return hull;
    }
    if(q == base)
    {
        return hull;
    }
    else
    {   
                for (int i = 0; i < points.size(); i++)
        {   
            if (orientation(points[p], points[i], points[q]) == 2)
            {
                q = i;
            }

        }
        cout<<points[q].x<<points[q].y<<endl;
        hull.push_back(points[q]);
        return convexHull(points, q, hull);
    }
}

double perimeter(vector<Point> P)
{
    double r = 0;
    for(int i = 1;i < P.size(); i++)
        r += sqrt(pow(P[i].x - P[i-1].x, 2) + pow(P[i].y - P[i-1].y, 2));
    return r;
}
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

    if (val == 0) 
        return 0;
    return (val > 0) ? 1 : 2;
}

int find_leftmost_point(vector<Point> points, int n)
{
    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;
    return l;

}

Answer 1

您当然可以 return 矢量。这本身不会导致段错误。可能导致此类错误的原因是：

hull.push_back(points[p]); 因为没有什么能保证向量中有 p+1 个点
orientation(points[p], points[i], points[q]) 因为没有任何东西可以保证向量中有 p+1 或 n 或 q 点
你最终陷入无限递归。这应该使用您使用的输入数据进行分析。但是如果 n>base，你最终会递归地调用函数而没有可以阻止它减少的整数。

编辑&解决方案：

根据您提供的附加信息，可以确保 n==points.size() 和 base<n。从那里可以清楚地看出 p、i 和 q 将始终小于 n。这消除了前两个可能的错误。

但是运行你的代码有一个小样本，表明你在无休止地循环：一旦你将最后一个点添加到船体，你再次开始添加第一个。它缺少什么，因此请确保您添加的点不在船体中。

您可以通过在 for 循环之后添加以下代码来执行此操作：

    auto srch=find(hull.begin(), hull.end(), points[q]); 
    if (srch!=hull.end()) {
        cout << "ALREADY IN"<<endl; 
        return hull;
    }

这里是 online demo。

递归方法中的c ++凸包

c++ convex hull in recursion method

c++

recursion

vector

convex-hull