Выпуклая оболочка - История изменений

Ctrlalt в 11:47, 9 октября 2022

2022-10-09T11:47:11Z

← Предыдущая версия		Версия от 11:47, 9 октября 2022
Строка 25:		Строка 25:

	vector<Point> convexHull(vector<Point> &points) {		vector<Point> convexHull(vector<Point> &points) {
	~~sort~~(points.begin(), points.end());		nth_element(points.begin(), points.begin(), points.end());
	sort(points.begin() + 1, points.end(), [&](Point &a, Point &b) {		sort(points.begin() + 1, points.end(), [&](Point &a, Point &b) {
	Point &o = points[0], oa(o, a), ob(o, b);		Point &o = points[0], oa(o, a), ob(o, b);
Строка 35:		Строка 35:
	while (hull.size() >= 2) {		while (hull.size() >= 2) {
	Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1];		Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1];
	Point ab(a, b), ac(a, p);		Point ab(a, b), ap(a, p);
	if (ab.crossProduct(ap) <= 0)		if (ab.crossProduct(ap) <= 0)
	hull.pop_back();		hull.pop_back();

Ctrlalt в 11:26, 9 октября 2022

2022-10-09T11:26:40Z

← Предыдущая версия		Версия от 11:26, 9 октября 2022
Строка 23:		Строка 23:
	}		}
	};		};

	~~Point o;~~
	~~bool compareByAngle(const Point &a, const Point &b) {~~
	~~Point oa(o, a), ob(o, b);~~
	~~return oa.crossProduct(ob) > 0 \|\| oa.crossProduct(ob) == 0 && oa.length() < ob.length();~~
	}

	vector<Point> convexHull(vector<Point> &points) {		vector<Point> convexHull(vector<Point> &points) {
	sort(points.begin(), points.end());		sort(points.begin(), points.end());
	~~o = points[0];~~		sort(points.begin() + 1, points.end(), [&](Point &a, Point &b) {
			Point &o = points[0], oa(o, a), ob(o, b);
	sort(points.begin() + 1, points.end(), ~~compareByAngle~~);		return oa.crossProduct(ob) > 0 \|\| oa.crossProduct(ob) == 0 && oa.length() < ob.length();
			});

	vector<Point> hull;		vector<Point> hull;
	for (~~int i = 0; i <~~ points~~.size(); i++~~) {		for (Point &p : points) {
	while (hull.size() >= 2) {		while (hull.size() >= 2) {
	Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1~~], &c = points[i~~];		Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1];
	Point ab(a, b), ac(a, c);		Point ab(a, b), ac(a, p);
	if (ab.crossProduct(ac) <= 0)		if (ab.crossProduct(ap) <= 0)
	hull.pop_back();		hull.pop_back();
	else		else
	break;		break;
	}		}
	hull.push_back(~~points[i]~~);		hull.push_back(p);
	}		}
	return hull;		return hull;

Ctrlalt в 10:05, 12 октября 2021

2021-10-12T10:05:04Z

← Предыдущая версия		Версия от 10:05, 12 октября 2021
Строка 4:		Строка 4:
	* Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.		* Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.

	{\|		struct Point {
	~~\| width="50%" \|~~		double x, y;

	struct P {		Point() {}
	double x, y;
	P(~~double X~~, ~~double Y~~) : x(X), y(Y) {}		Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}

			bool operator < (const Point &that) const {
			return y < that.y \|\| y == that.y && x < that.x;
			}

	double length() const {		double length() const {
	return ~~sqrt~~(y * y + x * x);		return hypot(x, y);
	}		}
	double ~~cross~~(const P &p) const {
	return x * p.y - y * p.x;		double crossProduct(const Point &that) const {
	}		return x * that.y - y * that.x;
			}
	};		};

	bool ~~compareByCoords~~(const P &a, const P &b) {		Point o;
	~~return~~ a~~.y &lt~~; b.y \|\| (~~a.y~~ == ~~b.y~~ && a.~~x < b~~.x);		bool compareByAngle(const Point &a, const Point &b) {
			Point oa(o, a), ob(o, b);
			return oa.crossProduct(ob) > 0 \|\| oa.crossProduct(ob) == 0 && oa.length() < ob.length();
	}		}

	~~P o~~(~~0, 0);~~		vector<Point> convexHull(vector<Point> &points) {
	~~bool compareByAngle(const P~~ &~~a, const P &b~~) {		sort(points.begin(), points.end());
	~~P va~~(a.~~x - o.x~~, a.~~y - o.y~~)~~, vb(b.x - o.x, b.y - o.y~~);		o = points[0];
	~~return va.cross(vb) > 0 \|\| (va.cross(vb) =~~= 0 ~~&& va.length() < vb.length())~~;
	}

	~~\| width="10px" \|~~
	~~\| width="50%" \|~~

	~~vector<P> convexHull(vector<P> &p) {~~		sort(points.begin() + 1, points.end(), compareByAngle);
	~~sort(p.begin(), p.end(), compareByCoords);~~
	~~o = p[0];~~
	sort(p.begin() + 1, p.end(), compareByAngle);

	vector~~<P>~~ hull;		vector<Point> hull;
	for (int i = 0; i ~~< p~~.size(); i++) {		for (int i = 0; i < points.size(); i++) {
	while (hull.size() ~~>~~= 2) {		while (hull.size() >= 2) {
	P &o = hull[hull.size() - 2], &a = hull[hull.size() - 1], &b = p[i];		Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1], &c = points[i];
	~~P oa~~(a~~.x - o.x~~, ~~a.y - o.y~~), ob(~~b.x - o.x~~, ~~b.y - o.y~~);		Point ab(a, b), ac(a, c);
	if (oa.~~cross~~(ob) ~~<~~= 0)		if (ab.crossProduct(ac) <= 0)
	hull.pop_back();		hull.pop_back();
	else		else
	break;		break;
	}		}
	hull.push_back(p[i]);		hull.push_back(points[i]);
	}		}
	return hull;		return hull;
	}		}

	\|}

	~~== Ссылки на задачи ==~~
	* [http://acmp.ru/?main=task&id_task=374 ACMP #374 — Выпуклая оболочка - 2]
	* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=290 MCCME #290 — Выпуклая оболочка (периметр и площадь)]
	* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=638 MCCME #638 — Выпуклая оболочка - периметр]

	== Ссылки ==		== Ссылки ==
	* [http://~~informatics~~.~~mccme~~.ru/~~course~~/~~view~~.~~php?id=22 informatics~~.~~mccme~~.ru ~~— Курс «Геометрия» — часть 3~~]		Теория:
			* [http://e-maxx.ru/algo/convex_hull_graham e-maxx.ru — Построение выпуклой оболочки обходом Грэхэма]
			* [https://cp-algorithms.com/geometry/grahams-scan-convex-hull.html cp-algorithms.com — Convex Hull construction using Graham's Scan]
			* algorithmica.org — Выпуклая оболочка: [https://algorithmica.org/ru/convex-hulls 1], [https://ru.algorithmica.org/cs/convex-hulls/graham/ 2]
			* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]
	* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]		* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]
	* [~~http~~://~~e-maxx~~.ru/~~bookz~~/~~files/andreeva.pdf Андреева Е. В., Егоров Ю. Е~~. ~~Вычислительная геометрия на плоскости~~]		* [https://usaco.guide/plat/convex-hull?lang=cpp usaco.guide — Convex Hull]
			Демонстрация:
	* [http://visualgo.net/en/convexhull VisuAlgo — Convex Hull]		* [http://visualgo.net/en/convexhull VisuAlgo — Convex Hull]
	* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp ~~Algos~~ — ~~Graham scan~~]		Код:
			* [https://github.com/indy256/codelibrary/blob/master/cpp/geometry/convex_hull.cpp indy256/codelibrary/cpp/geometry/convex_hull.cpp]
			* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp ADJA/algos/Geometry/convex_hull_graham_scan.cpp]
			* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/GrahamScan.java kevin-wayne/algs4/GrahamScan.java]
			Задачи:
			* [http://informatics.mccme.ru/course/view.php?id=22 informatics.mccme.ru — Курс «Геометрия» — часть 3]
			* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=290 MCCME #290 — Выпуклая оболочка (периметр и площадь)]
			* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=638 MCCME #638 — Выпуклая оболочка - периметр]
			* [http://acmp.ru/?main=task&id_task=374 ACMP #374 — Выпуклая оболочка - 2]

	[[Категория:Геометрия]]		[[Категория:Геометрия]]

Ctrlalt: /* Ссылки */

2018-03-03T23:19:42Z

Ссылки

← Предыдущая версия		Версия от 23:19, 3 марта 2018
Строка 62:		Строка 62:
	* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]		* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]
	* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]		* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]
	* [http://visualgo.net/~~geometry.html~~ VisuAlgo — ~~(Computational) Geometry~~]		* [http://visualgo.net/en/convexhull VisuAlgo — Convex Hull]
	* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos — Graham scan]		* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos — Graham scan]

	[[Категория:Геометрия]]		[[Категория:Геометрия]]

Ctrlalt в 23:18, 17 ноября 2014

2014-11-17T23:18:41Z

← Предыдущая версия		Версия от 23:18, 17 ноября 2014
Строка 1:		Строка 1:
	* Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку O.		* Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку O.
	* Сортируем остальные почки по полярному углу от O. Точка A должна идти раньше точки B, если поворот от вектора OA к вектору OB происходит по часовой ~~стрелке~~ (косое произведение положительно). Если OA и OB коллинеарны, то раньше идёт точка, ближайшая к O.		* Сортируем остальные почки по полярному углу от O. Точка A должна идти раньше точки B, если поворот от вектора OA к вектору OB происходит против часовой стрелки (косое произведение положительно). Если OA и OB коллинеарны, то раньше идёт точка, ближайшая к O.
	* Добавляем точку O в оболочку.		* Добавляем точку O в оболочку.
	* Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.		* Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.

Ctrlalt: /* Ссылки */

2014-09-29T20:14:32Z

Ссылки

← Предыдущая версия		Версия от 20:14, 29 сентября 2014
Строка 62:		Строка 62:
	* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]		* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]
	* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]		* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]
			* [http://visualgo.net/geometry.html VisuAlgo — (Computational) Geometry]
	* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos — Graham scan]		* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos — Graham scan]

	[[Категория:Геометрия]]		[[Категория:Геометрия]]

Ctrlalt: /* Ссылки */

2014-08-28T23:10:37Z

Ссылки

← Предыдущая версия		Версия от 23:10, 28 августа 2014
Строка 61:		Строка 61:
	* [http://informatics.mccme.ru/course/view.php?id=22 informatics.mccme.ru — Курс «Геометрия» — часть 3]		* [http://informatics.mccme.ru/course/view.php?id=22 informatics.mccme.ru — Курс «Геометрия» — часть 3]
	* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]		* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]
			* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]
	* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos — Graham scan]		* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos — Graham scan]

	[[Категория:Геометрия]]		[[Категория:Геометрия]]

Ctrlalt: Новая страница: «* Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит вы…»

2014-08-28T16:59:52Z

Новая страница: «* Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит вы…»

Новая страница

* Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку O.
* Сортируем остальные почки по полярному углу от O. Точка A должна идти раньше точки B, если поворот от вектора OA к вектору OB происходит по часовой стрелке (косое произведение положительно). Если OA и OB коллинеарны, то раньше идёт точка, ближайшая к O.
* Добавляем точку O в оболочку.
* Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.

{|
| width="50%" |

struct P {
double x, y;
P(double X, double Y) : x(X), y(Y) {}
double length() const {
return sqrt(y * y + x * x);
}
double cross(const P &p) const {
return x * p.y - y * p.x;
}
};

bool compareByCoords(const P &a, const P &b) {
return a.y < b.y || (a.y == b.y && a.x < b.x);
}

P o(0, 0);
bool compareByAngle(const P &a, const P &b) {
P va(a.x - o.x, a.y - o.y), vb(b.x - o.x, b.y - o.y);
return va.cross(vb) > 0 || (va.cross(vb) == 0 && va.length() < vb.length());
}

| width="10px" |
| width="50%" |

vector<P> convexHull(vector<P> &p) {
sort(p.begin(), p.end(), compareByCoords);
o = p[0];
sort(p.begin() + 1, p.end(), compareByAngle);

vector<P> hull;
for (int i = 0; i < p.size(); i++) {
while (hull.size() >= 2) {
P &o = hull[hull.size() - 2], &a = hull[hull.size() - 1], &b = p[i];
P oa(a.x - o.x, a.y - o.y), ob(b.x - o.x, b.y - o.y);
if (oa.cross(ob) <= 0)
hull.pop_back();
else
break;
}
hull.push_back(p[i]);
}
return hull;
}

|}

== Ссылки на задачи ==
* [http://acmp.ru/?main=task&id_task=374 ACMP #374 — Выпуклая оболочка - 2]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=290 MCCME #290 — Выпуклая оболочка (периметр и площадь)]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=638 MCCME #638 — Выпуклая оболочка - периметр]

== Ссылки ==
* [http://informatics.mccme.ru/course/view.php?id=22 informatics.mccme.ru — Курс «Геометрия» — часть 3]
* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts]
* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos — Graham scan]

[[Категория:Геометрия]]