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
namespace	geometry
	for std::vector
namespace	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

           {
    test();
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Test function

Returns

void

                   {
    std::vector<geometry::jarvis::Point> points = {{0, 3},
                                                   {2, 2},
                                                   {1, 1},
                                                   {2, 1},
                                                   {3, 0},
                                                   {0, 0},
                                                   {3, 3}
    };
    geometry::jarvis::Convexhull hull(points);
    std::vector<geometry::jarvis::Point> actualPoint;
    actualPoint = hull.getConvexHull();
 
    std::vector<geometry::jarvis::Point> expectedPoint = {{0, 3},
                                                          {0, 0},
                                                          {3, 0},
                                                          {3, 3}};
    for (int i = 0; i < expectedPoint.size(); i++) {
        assert(actualPoint[i].x == expectedPoint[i].x);
        assert(actualPoint[i].y == expectedPoint[i].y);
    }
    std::cout << "Test implementations passed!\n";
}

Here is the call graph for this function: