Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
geometry::jarvis::Convexhull Class Reference
Collaboration diagram for geometry::jarvis::Convexhull:
[legend]

Public Member Functions

 Convexhull (const std::vector< Point > &pointList)
 
std::vector< PointgetConvexHull () const
 

Static Public Member Functions

static int orientation (const Point &p, const Point &q, const Point &r)
 

Private Attributes

std::vector< Pointpoints
 
int size
 

Detailed Description

Class which can be called from main and is globally available throughout the code

Constructor & Destructor Documentation

◆ Convexhull()

geometry::jarvis::Convexhull::Convexhull ( const std::vector< Point > &  pointList)
inlineexplicit

Constructor of given class

Parameters
pointListlist of all points in the space
nnumber of points in space
66  {
67  points = pointList;
68  size = points.size();
69  }
Here is the call graph for this function:

Member Function Documentation

◆ getConvexHull()

std::vector<Point> geometry::jarvis::Convexhull::getConvexHull ( ) const
inline

Creates convex hull of a set of n points. There must be 3 points at least for the convex hull to exist

Returns
an vector array containing points in space which enclose all given points thus forming a hull
78  {
79  // Initialize Result
80  std::vector<Point> hull;
81 
82  // Find the leftmost point
83  int leftmost_point = 0;
84  for (int i = 1; i < size; i++) {
85  if (points[i].x < points[leftmost_point].x) {
86  leftmost_point = i;
87  }
88  }
89  // Start from leftmost point, keep moving counterclockwise
90  // until reach the start point again. This loop runs O(h)
91  // times where h is number of points in result or output.
92  int p = leftmost_point, q = 0;
93  do {
94  // Add current point to result
95  hull.push_back(points[p]);
96 
97  // Search for a point 'q' such that orientation(p, x, q)
98  // is counterclockwise for all points 'x'. The idea
99  // is to keep track of last visited most counter clock-
100  // wise point in q. If any point 'i' is more counter clock-
101  // wise than q, then update q.
102  q = (p + 1) % size;
103  for (int i = 0; i < size; i++) {
104  // If i is more counterclockwise than current q, then
105  // update q
106  if (orientation(points[p], points[i], points[q]) == 2) {
107  q = i;
108  }
109  }
110 
111  // Now q is the most counterclockwise with respect to p
112  // Set p as q for next iteration, so that q is added to
113  // result 'hull'
114  p = q;
115 
116  } while (p != leftmost_point); // While we don't come to first point
117 
118  return hull;
119  }
Here is the call graph for this function:

◆ orientation()

static int geometry::jarvis::Convexhull::orientation ( const Point p,
const Point q,
const Point r 
)
inlinestatic

This function returns the geometric orientation for the three points in a space, ie, whether they are linear ir clockwise or anti-clockwise

Parameters
pfirst point selected
qadjacent point for q
radjacent point for q
Returns
0 -> Linear
1 -> Clock Wise
2 -> Anti Clock Wise
133  {
134  int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
135 
136  if (val == 0) {
137  return 0;
138  }
139  return (val > 0) ? 1 : 2;
140  }

The documentation for this class was generated from the following file:
std::vector
STL class.
std::vector::push_back
T push_back(T... args)
Point::y
int y
Point respect to x coordinate.
Definition: line_segment_intersection.cpp:14
geometry::jarvis::Convexhull::orientation
static int orientation(const Point &p, const Point &q, const Point &r)
Definition: jarvis_algorithm.cpp:133