geometry::jarvis::Convexhull Class Reference

Collaboration diagram for geometry::jarvis::Convexhull:

Public Member Functions
	Convexhull (const std::vector< Point > &pointList)
std::vector< Point >	getConvexHull () const

Static Public Member Functions
static int	orientation (const Point &p, const Point &q, const Point &r)

Private Attributes
std::vector< Point >	points
int	size

Detailed Description

Class which can be called from main and is globally available throughout the code

Definition at line 55 of file jarvis_algorithm.cpp.

Constructor & Destructor Documentation

Convexhull()

geometry::jarvis::Convexhull::Convexhull ( const std::vector< Point > & pointList )

inlineexplicit

Constructor of given class

Parameters

pointList	list of all points in the space
n	number of points in space

Definition at line 66 of file jarvis_algorithm.cpp.

                                                                   {
                points = pointList;
                size = points.size();
            }

Member Function Documentation

getConvexHull()

std::vector< Point > geometry::jarvis::Convexhull::getConvexHull ( ) const

inline

Creates convex hull of a set of n points. There must be 3 points at least for the convex hull to exist

Returns

an vector array containing points in space which enclose all given points thus forming a hull

Definition at line 78 of file jarvis_algorithm.cpp.

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

orientation()

static int geometry::jarvis::Convexhull::orientation ( const Point & p, const Point & q, const Point & r )

inlinestatic

This function returns the geometric orientation for the three points in a space, ie, whether they are linear ir clockwise or anti-clockwise

Parameters

p	first point selected
q	adjacent point for q
r	adjacent point for q

Returns

0 -> Linear

1 -> Clock Wise

2 -> Anti Clock Wise

Definition at line 133 of file jarvis_algorithm.cpp.

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

Member Data Documentation

points

std::vector<Point> geometry::jarvis::Convexhull::points

private

Definition at line 56 of file jarvis_algorithm.cpp.

size

int geometry::jarvis::Convexhull::size

private

Definition at line 57 of file jarvis_algorithm.cpp.

---

The documentation for this class was generated from the following file:

• geometry/jarvis_algorithm.cpp