C ++ выпуклая оболочка в методе рекурсии

Question

C ++ выпуклая оболочка в методе рекурсии

Я пытаюсь отладить алгоритм Джарвиса с «выпуклой оболочкой». Задача «выпуклой оболочки» состоит в том, чтобы при заданном наборе P из n точек на плоскости найти подмножество CH (P), которое образует вершины выпуклого многоугольника, содержащего все остальные точки.
написать эту функцию рекурсивно, но зациклить на себе и вернуть ошибку сегментации

    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;

}

1

c++convex-hull recursion vector

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы можете, конечно, вернуть векторы. Это само по себе не является причиной ошибки. Что может вызвать такие ошибки:

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;
}

И здесь онлайн демо.

0