fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. struct Point {
  6. 	float x;
  7. 	float y;
  8. };
  9.  
  10. // returns cross product p0p1 x p0p2
  11. float direction(Point p0, Point p1, Point p2) {
  12. 	return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
  13. }
  14.  
  15. // returns squared distance between given points
  16. float distSquared(Point a, Point b) {
  17. 	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  18. }
  19.  
  20. std::vector<Point> FindConvexHull(std::vector<Point> &points) {
  21. 	// find minimum point
  22. 	auto minimumIterator = std::min_element(points.begin(), points.end(), [](Point a, Point b) {
  23. 		return a.y < b.y || (a.y == b.y && a.x < b.x);
  24. 	});
  25. 	// and swap it with the beginning of points vector
  26. 	std::iter_swap(points.begin(), minimumIterator);
  27.  
  28. 	// sort the rest of the points based on orientation to minimum point (and on distance for same orientations)
  29. 	std::sort(points.begin() + 1, points.end(), [=](Point a, Point b) {
  30. 		float d = direction(points[0], a, b);
  31. 		return d ? d > 0 : distSquared(points[0], a) < distSquared(points[0], b);
  32. 	});
  33.  
  34. 	// add first 3 points to convex hull
  35. 	std::vector<Point> convexHull;
  36. 	convexHull.push_back(points[0]);
  37. 	convexHull.push_back(points[1]);
  38. 	convexHull.push_back(points[2]);
  39. 	for (int i = 3; i < points.size(); ++i) {
  40. 		// while going through points:
  41. 		//  convexHull[last-1], convexHull[last], points[i]
  42. 		// there is no left turn
  43. 		while (direction(convexHull[convexHull.size() - 2], convexHull.back(), points[i]) <= 0) {
  44. 			// remove last point from convex hull
  45. 			convexHull.pop_back();
  46. 		}
  47. 		// now there is left turn so add current point to convex hull
  48. 		convexHull.push_back(points[i]);
  49. 	}
  50. 	return convexHull;
  51. }
  52.  
  53. int main(int argc, char *argv[]) {
  54. 	std::vector<Point> points = {
  55. 		{ 1,4 },{ 2,1 },{ 2,5 },{ 3,3 },{ 4,2 },{ 4,7 },{ 5,4 },{ 5,6 },
  56. 		{ 6,5 },{ 6,7 },{ 7,3 },{ 8,2 },{ 8,5 }
  57. 	};
  58. 	std::vector<Point> convexHull = FindConvexHull(points);
  59. 	for (auto p : convexHull) {
  60. 		std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
  61. 	}
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(2, 1)
(8, 2)
(8, 5)
(6, 7)
(4, 7)
(1, 4)
https://ideone.com/HENzFB
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!