محاسبه convex hull

Question

سلام به دوستان گلم.

یک سری نقطه دارم میخام convex hull این نقاط را تو c++ بدست بیارم .فقط یک موردی که هست نمی خوام از opencv یا کتابخانه های دیگر برای اینکار استفاده کنم. .ممنون اگر راهنماییم کنید.

Answer 1

به صورت زیر عمل کنید:

coord2_t cross(const Point &O, const Point &A, const Point &B)
{
	return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<Point> convex_hull(vector<Point> P)
{
	int n = P.size(), k = 0;
	if (n == 1) return P;
	vector<Point> H(2 * n);

	sort(P.begin(), P.end());

	for (int i = 0; i < n; ++i) {
		while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}

	for (int i = n - 2, t = k + 1; i >= 0; i--) {
		while (k >= t && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}

	H.resize(k - 1);
	return H;
}