Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
jarvis_algorithm.cpp File Reference

Implementation of Jarvis’s algorithm. More...

#include <vector>
#include <cassert>
#include <iostream>
Include dependency graph for jarvis_algorithm.cpp:

Classes

struct  geometry::jarvis::Point
 
class  geometry::jarvis::Convexhull
 

Namespaces

 geometry
 Geometry algorithms.
 
 jarvis
 Functions for Jarvis’s algorithm.
 

Functions

static void test ()
 
int main ()
 

Detailed Description

Implementation of Jarvis’s algorithm.

Given a set of points in the plane. the convex hull of the set is the smallest convex polygon that contains all the points of it.

Algorithm

The idea of Jarvis’s Algorithm is simple, we start from the leftmost point (or point with minimum x coordinate value) and we keep wrapping points in counterclockwise direction.

The idea is to use orientation() here. Next point is selected as the point that beats all other points at counterclockwise orientation, i.e., next point is q if for any other point r, we have “orientation(p, q, r) = counterclockwise”.

For Example, If points = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};

then the convex hull is (0, 3), (0, 0), (3, 0), (3, 3)

Author
Rishabh Agarwal

Function Documentation

◆ main()

int main ( void  )

Driver Code

176  {
177  test();
178  return 0;
179 }
Here is the call graph for this function:

◆ test()

static void test ( )
static

Test function

Returns
void
151  {
152  std::vector<geometry::jarvis::Point> points = {{0, 3},
153  {2, 2},
154  {1, 1},
155  {2, 1},
156  {3, 0},
157  {0, 0},
158  {3, 3}
159  };
160  geometry::jarvis::Convexhull hull(points);
162  actualPoint = hull.getConvexHull();
163 
164  std::vector<geometry::jarvis::Point> expectedPoint = {{0, 3},
165  {0, 0},
166  {3, 0},
167  {3, 3}};
168  for (int i = 0; i < expectedPoint.size(); i++) {
169  assert(actualPoint[i].x == expectedPoint[i].x);
170  assert(actualPoint[i].y == expectedPoint[i].y);
171  }
172  std::cout << "Test implementations passed!\n";
173 }
Here is the call graph for this function:
test
static void test()
Definition: jarvis_algorithm.cpp:151
std::vector< geometry::jarvis::Point >
std::vector::size
T size(T... args)
std::cout
geometry::jarvis::Convexhull
Definition: jarvis_algorithm.cpp:55