Ocular Engine
Ocular::Math::ConvexHull2D Class Reference

#include <ConvexHull2D.hpp>

Public Member Functions

 ConvexHull2D (std::vector< Point2f > const &points)
 ConvexHull2D (Point2f const *, uint32_t numPoints)
void sort ()
uint32_t getNumPoints () const
std::vector< Point2f > const & getHull () const

Protected Member Functions

void createHull ()
void splitCollection (LineSegment2Df const &segment, std::vector< Point2f > &leftGroup, std::vector< Point2f > &rightGroup)
void findHull (LineSegment2Df const &segment, std::vector< Point2f > &points)

Detailed Description

A convex hull is the minimum set of points that envelope an arbitrary collection of points.

By default, the points comprising the hull are stored as they are discovered and no type of order is guaranteed.

The sort method may be called to order them in a counterclockwise fashion.

Constructor & Destructor Documentation

Ocular::Math::ConvexHull2D::ConvexHull2D ( std::vector< Point2f > const &  points)
[in]pointsArbitrary collection of points to calculate a convex hull for.
Ocular::Math::ConvexHull2D::ConvexHull2D ( Point2f const *  points,
uint32_t  numPoints 
[in]pointsArbitrary array of points to calculate a convex hull for.
[in]numPointsNumber of points in the array.

Member Function Documentation

void Ocular::Math::ConvexHull2D::findHull ( LineSegment2Df const &  segment,
std::vector< Point2f > &  points 

Find the most distant point from the segment.

This point (C) creates a triangle ACB with the two endpoints (AB) and is part of the hull. Any points inside ACB are not part of the hull, while any points outside of it may be part of the hull.

Check the points to the left of the segment AC. The most distant one (D) will create a a triangle ADC. Any inside this triangle are not part of the hull, and so on and so forth.

Once all points left of AC have been accounted for, then do the same for all points to the left of the line segment CB.

std::vector< Point2f > const & Ocular::Math::ConvexHull2D::getHull ( ) const

Returns a container with all of the points in the convex hull. The vertices compose a polygon and are stored in a counterclockwise order.

uint32_t Ocular::Math::ConvexHull2D::getNumPoints ( ) const

Returns the number of points that make up the convex hull.

void Ocular::Math::ConvexHull2D::sort ( )

Sorts the points comprising the convex hull into an ordered counterclockwise polygon.

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