محاسبه convex hull - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۱۹ نفر آنلاین
۱ عضو و ۱۱۸ مهمان در سایت حاضرند

محاسبه convex hull

0 امتیاز
19 بازدید
سلام به دوستان گلم.

یک سری نقطه دارم میخام convex hull این نقاط را تو c++ بدست بیارم .فقط یک موردی که هست نمی خوام از opencv یا کتابخانه های دیگر برای اینکار استفاده کنم. .ممنون اگر راهنماییم کنید.
سوال شده دی 4, 1396  بوسیله ی sailent (امتیاز 386)   1 6 36

1 پاسخ

0 امتیاز

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

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

 

پاسخ داده شده دی 7, 1396 بوسیله ی مصطفی ساتکی (امتیاز 17,035)   17 26 66
...