Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Implementation of Jarvis’s algorithm. More...
#include <vector>
#include <cassert>
#include <iostream>
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 () |
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.
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)
int main | ( | void | ) |
|
static |
Test function