c++ convex hull in recursion method

Question

I'm trying to debug the "convex hull" jarvis's algorithm. The "convex hull" problem is, given a collection P of n points in a plane, to find a subset CH(P) that forms the vertices of a convex polygon containing all the other points. write this function recursively but stick in a loop for ever and return segmentation fault

    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

You can of course return vectors. This doesn't by itself cause a segfault. What could cause such errors is:

• hull.push_back(points[p]); because nothing guarantees that there are p+1 points in the vector
• orientation(points[p], points[i], points[q]) because nothing guarantees that there are p+1 or n or q points in your vector
• you end up in an infinite recursion. This should be analyzed with the input data that you use. But for if n>base, you end up calling recursively the function without the integers that could stop it decrease.

Edit & solution:

With the additional information that you've provided, it is ensured that n==points.size() and that base<n. From there it is clear that p, i and q will always be smaller than n. This eliminates the two first possible errors.

But running your code with a small sample, shows that you are cycling endlessly: once you have added the last point to the hull, you start again adding the first one. What is missing it so make sure that the point you add is not already in the hull.

You can do this by adding the following code just after your for-loop:

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

And here the online demo.