jarvis_algorithm.cpp File Reference

Implementation of Jarvis’s algorithm. More...

#include <vector>
#include <cassert>
#include <iostream>

Include dependency graph for jarvis_algorithm.cpp:

Go to the source code of this file.

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

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

Definition in file jarvis_algorithm.cpp.

Function Documentation

main()

int main

(

void

)

Driver Code

Definition at line 176 of file jarvis_algorithm.cpp.

           {
    test();
    return 0;
}

test()

static void test ( )

static

Test function

Returns

void

Definition at line 151 of file jarvis_algorithm.cpp.

                   {
    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";
}