jarvis_algorithm.cpp

Go to the documentation of this file.

 
#include <vector>
#include <cassert>
#include <iostream>
 
namespace geometry {
    namespace jarvis {
        struct Point {
            int x, y;
        };
 
        class Convexhull {
            std::vector<Point> points;
            int size;
 
        public:
            explicit Convexhull(const std::vector<Point> &pointList) {
                points = pointList;
                size = points.size();
            }
 
            std::vector<Point> getConvexHull() const {
                // Initialize Result
                std::vector<Point> hull;
 
                // Find the leftmost point
                int leftmost_point = 0;
                for (int i = 1; i < size; i++) {
                    if (points[i].x < points[leftmost_point].x) {
                        leftmost_point = i;
                    }
                }
                // Start from leftmost point, keep moving counterclockwise
                // until reach the start point again.  This loop runs O(h)
                // times where h is number of points in result or output.
                int p = leftmost_point, q = 0;
                do {
                    // Add current point to result
                    hull.push_back(points[p]);
 
                    // Search for a point 'q' such that orientation(p, x, q)
                    // is counterclockwise for all points 'x'. The idea
                    // is to keep track of last visited most counter clock-
                    // wise point in q. If any point 'i' is more counter clock-
                    // wise than q, then update q.
                    q = (p + 1) % size;
                    for (int i = 0; i < size; i++) {
                        // If i is more counterclockwise than current q, then
                        // update q
                        if (orientation(points[p], points[i], points[q]) == 2) {
                            q = i;
                        }
                    }
 
                    // Now q is the most counterclockwise with respect to p
                    // Set p as q for next iteration, so that q is added to
                    // result 'hull'
                    p = q;
 
                } while (p != leftmost_point);        // While we don't come to first point
 
                return hull;
            }
 
            static int orientation(const Point &p, const Point &q, const Point &r) {
                int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
 
                if (val == 0) {
                    return 0;
                }
                return (val > 0) ? 1 : 2;
            }
 
        };
 
    } // namespace jarvis
} // namespace geometry
 
static void test() {
    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";
}
 
int main() {
    test();
    return 0;
}