ConvexHull class definiton. More...

#include <ConvexHull.h>

Public Types
using	Point = std::tuple< float, float, const reco::ClusterHit3D * >
	projected x,y position and 3D hit More...

using	PointList = std::list< Point >
	The list of the projected points. More...

using	PointPair = std::pair< Point, Point >

using	MinMaxPointPair = std::pair< PointPair, PointPair >

Public Member Functions
	ConvexHull (const PointList &, float=0.85, float=0.35)
	Constructor. More...

	~ConvexHull ()
	Destructor. More...

const PointList &	getPointsList ()
	recover the list of points used to build convex hull More...

const PointList &	getConvexHull () const
	recover the list of convex hull vertices More...

const MinMaxPointPair &	getMinMaxPointPair () const
	find the ends of the convex hull (along its x axis) More...

const PointList &	getExtremePoints ()
	Find the two points on the hull which are furthest apart. More...

const reco::ConvexHullKinkTupleList &	getKinkPoints ()
	Find the points with the largest angles. More...

float	getConvexHullArea () const
	recover the area of the convex hull More...

PointPair	findNearestEdge (const Point &, float &) const
	Given an input Point, find the nearest edge. More...

float	findNearestDistance (const Point &) const
	Given an input point, find the distance to the nearest edge/point. More...

Private Member Functions
void	getConvexHull (const PointList &)
	Given an input set of 2D points build a convex hull around them. More...

float	crossProduct (const Point &p0, const Point &p1, const Point &p2) const
	Gets the cross product of line from p0 to p1 and p0 to p2. More...

float	Area () const
	Computes the area of the enclosed convext hull. More...

bool	isLeft (const Point &p0, const Point &p1, const Point &pCheck) const
	Determines whether a point is to the left, right or on line specifiec by p0 and p1. More...

Private Attributes
float	fKinkAngle

float	fMinEdgeDistance

const PointList &	fPoints

PointList	fConvexHull

MinMaxPointPair	fMinMaxPointPair

float	fConvexHullArea

PointList	fExtremePoints

reco::ConvexHullKinkTupleList	fKinkPoints

Detailed Description

ConvexHull class definiton.

Definition at line 27 of file ConvexHull.h.

Member Typedef Documentation

using lar_cluster3d::ConvexHull::MinMaxPointPair = std::pair<PointPair,PointPair>

Definition at line 36 of file ConvexHull.h.

using lar_cluster3d::ConvexHull::Point = std::tuple<float,float,const reco::ClusterHit3D*>

projected x,y position and 3D hit

Definition at line 33 of file ConvexHull.h.

using lar_cluster3d::ConvexHull::PointList = std::list<Point>

The list of the projected points.

Definition at line 34 of file ConvexHull.h.

using lar_cluster3d::ConvexHull::PointPair = std::pair<Point,Point>

Definition at line 35 of file ConvexHull.h.

Constructor & Destructor Documentation

lar_cluster3d::ConvexHull::ConvexHull	(	const PointList &	pointListIn,
		float	kinkAngle = `0.85`,
		float	minEdgeDistance = `0.35`
	)

Constructor.

Parameters

pset

Definition at line 29 of file ConvexHull.cxx.

                                                                                            :
     fKinkAngle(kinkAngle), fMinEdgeDistance(minEdgeDistance), fPoints(pointListIn), fConvexHullArea(0.)
 {
     fConvexHull.clear();
 
     // Build out the convex hull around the input points
     getConvexHull(fPoints);
 
     // And the area
     fConvexHullArea = Area();
 }

lar_cluster3d::ConvexHull::~ConvexHull ( )

Destructor.

Definition at line 43 of file ConvexHull.cxx.

44 {

45 }

Member Function Documentation

float lar_cluster3d::ConvexHull::Area ( ) const

private

Computes the area of the enclosed convext hull.

Definition at line 71 of file ConvexHull.cxx.

 {
     float area(0.);
 
     // Compute the area by taking advantage of
     // 1) the ability to decompose a convex hull into triangles,
     // 2) the ability to use the cross product to calculate the area
     // So, the technique is to pick a point which we take as the center of the polygon
     // and then sum the signed area of triangles formed from this point to two adjecent
     // vertices on the convex hull.
     float x = 0.;
     float y = 0.;
     float n = float(fConvexHull.size());
 
     for(const auto& point : fConvexHull)
     {
         x += std::get<0>(point);
         y += std::get<1>(point);
     }
 
     Point center(x/n,y/n,0);
 
     Point lastPoint = fConvexHull.front();
 
     for(const auto& point : fConvexHull)
     {
         if (point != lastPoint) area += 0.5 * crossProduct(center,lastPoint,point);
 
         lastPoint = point;
     }
 
     return area;
 }

float lar_cluster3d::ConvexHull::crossProduct	(	const Point &	p0,
		const Point &	p1,
		const Point &	p2
	)		const

private

Gets the cross product of line from p0 to p1 and p0 to p2.

Definition at line 58 of file ConvexHull.cxx.

 {
     // Define a quick 2D cross product here since it will used quite a bit!
     float deltaX  = std::get<0>(p1) - std::get<0>(p0);
     float deltaY  = std::get<1>(p1) - std::get<1>(p0);
     float dCheckX = std::get<0>(p2) - std::get<0>(p0);
     float dCheckY = std::get<1>(p2) - std::get<1>(p0);
 
     return ((deltaX * dCheckY) - (deltaY * dCheckX));
 }

float lar_cluster3d::ConvexHull::findNearestDistance ( const Point & point ) const

Given an input point, find the distance to the nearest edge/point.

Definition at line 392 of file ConvexHull.cxx.

 {
     float     closestDistance;
 
     findNearestEdge(point,closestDistance);
 
     return closestDistance;
 }

ConvexHull::PointPair lar_cluster3d::ConvexHull::findNearestEdge	(	const Point &	point,
		float &	closestDistance
	)		const

Given an input Point, find the nearest edge.

Definition at line 331 of file ConvexHull.cxx.

 {
     // The idea is to find the nearest edge of the convex hull, defined by
     // two adjacent vertices of the hull, to the input point.
     // As near as I can tell, the best way to do this is to apply brute force...
     // Idea will be to iterate over pairs of points
     PointList::const_iterator curPointItr = fConvexHull.begin();
     Point                     prevPoint   = *curPointItr++;
     Point                     curPoint    = *curPointItr;
 
     // Set up the winner
     PointPair closestEdge(prevPoint,curPoint);
 
     closestDistance = std::numeric_limits<float>::max();
 
     // curPointItr is meant to point to the second point
     while(curPointItr != fConvexHull.end())
     {
         if (curPoint != prevPoint)
         {
             // Dereference some stuff
             float xPrevToPoint = (std::get<0>(point)    - std::get<0>(prevPoint));
             float yPrevToPoint = (std::get<1>(point)    - std::get<1>(prevPoint));
             float xPrevToCur   = (std::get<0>(curPoint) - std::get<0>(prevPoint));
             float yPrevToCur   = (std::get<1>(curPoint) - std::get<1>(prevPoint));
             float edgeLength   = std::sqrt(xPrevToCur * xPrevToCur + yPrevToCur * yPrevToCur);
 
             // Find projection onto convex hull edge
             float projection = ((xPrevToPoint * xPrevToCur) + (yPrevToPoint * yPrevToCur)) / edgeLength;
 
             // DOCA point
             Point docaPoint(std::get<0>(prevPoint) + projection * xPrevToCur / edgeLength,
                             std::get<1>(prevPoint) + projection * yPrevToCur / edgeLength, 0);
 
             if (projection > edgeLength) docaPoint = curPoint;
             if (projection < 0)          docaPoint = prevPoint;
 
             float xDocaDist = std::get<0>(point) - std::get<0>(docaPoint);
             float yDocaDist = std::get<1>(point) - std::get<1>(docaPoint);
             float docaDist  = xDocaDist * xDocaDist + yDocaDist * yDocaDist;
 
             if (docaDist < closestDistance)
             {
                 closestEdge     = PointPair(prevPoint,curPoint);
                 closestDistance = docaDist;
             }
         }
 
         prevPoint = curPoint;
         curPoint  = *curPointItr++;
     }
 
     closestDistance = std::sqrt(closestDistance);
 
     // Convention is convex hull vertices sorted in counter clockwise fashion so if the point
     // lays to the left of the nearest edge then it must be an interior point
     if (isLeft(closestEdge.first,closestEdge.second,point)) closestDistance = -closestDistance;
 
     return closestEdge;
 }

const PointList& lar_cluster3d::ConvexHull::getConvexHull ( ) const

inline

recover the list of convex hull vertices

Definition at line 58 of file ConvexHull.h.

58 {return fConvexHull;}

lar_cluster3d::ConvexHull::fConvexHull

PointList fConvexHull

Definition: ConvexHull.h:118

void lar_cluster3d::ConvexHull::getConvexHull ( const PointList & pointList )

private

Given an input set of 2D points build a convex hull around them.

Parameters

PointList The input list of 2D points to build hull around

Definition at line 107 of file ConvexHull.cxx.

 {
     // Start by identifying the min/max points
     Point pMinMin = pointList.front();
 
     // Find the point with maximum y sharing the same x value...
     PointList::const_iterator pMinMaxItr = std::find_if(pointList.begin(),pointList.end(),[pMinMin](const auto& elem){return std::get<0>(elem) != std::get<0>(pMinMin);});
 
     Point pMinMax = *(--pMinMaxItr);  // This could be / probably is the same point
 
     fMinMaxPointPair.first.first  = pMinMin;
     fMinMaxPointPair.first.second = pMinMax;
 
     Point pMaxMax = pointList.back();  // get the last point
 
     // Find the point with minimum y sharing the same x value...
     PointList::const_reverse_iterator pMaxMinItr = std::find_if(pointList.rbegin(),pointList.rend(),[pMaxMax](const auto& elem){return std::get<0>(elem) != std::get<0>(pMaxMax);});
 
     Point pMaxMin = *(--pMaxMinItr);  // This could be / probably is the same point
 
     fMinMaxPointPair.second.first  = pMaxMin;
     fMinMaxPointPair.second.second = pMaxMax;
 
     // Get the lower convex hull
     PointList lowerHullList;
 
     lowerHullList.push_back(pMinMin);
 
     // loop over points in the set
     for(auto curPoint : pointList)
     {
         // First check that we even want to consider this point
         if (isLeft(pMinMin,pMaxMin,curPoint)) continue;
 
         // In words: treat "lowerHullVec" as a stack. If there is only one entry then
         // push the current point onto the stack. If more than one entry then check if
         // the current point is to the left of the line from the last two points in the
         // stack. If it is then add the current point to the stack, if it is not then
         // pop the last point off the stack and try again.
         while(lowerHullList.size() > 1)
         {
             Point lastPoint = lowerHullList.back();
 
             lowerHullList.pop_back();
 
             Point nextToLastPoint = lowerHullList.back();
 
             if (isLeft(nextToLastPoint,lastPoint,curPoint))
             {
                 lowerHullList.push_back(lastPoint);
                 break;
             }
         }
 
         lowerHullList.push_back(curPoint);
     }
 
     // Now get the upper hull
     PointList upperHullList;
 
     upperHullList.push_back(pMaxMax);
 
     for(auto curPoint : boost::adaptors::reverse(pointList))
     {
         // First check that we even want to consider this point
         // Remember that we are going "backwards" so still want
         // curPoint to lie to the "left"
         if (isLeft(pMaxMax,pMinMax,curPoint)) continue;
 
         // Replicate the above but going the other direction...
         while(upperHullList.size() > 1)
         {
             Point lastPoint = upperHullList.back();
 
             upperHullList.pop_back();
 
             Point nextToLastPoint = upperHullList.back();
 
             if (isLeft(nextToLastPoint,lastPoint,curPoint))
             {
                 upperHullList.push_back(lastPoint);
                 break;
             }
         }
 
         upperHullList.push_back(curPoint);
     }
 
     // Now we merge the two lists into the output list
     std::copy(lowerHullList.begin(),lowerHullList.end(),std::back_inserter(fConvexHull));
 
     if (pMaxMin == pMaxMax) upperHullList.pop_front();
 
     std::copy(upperHullList.begin(),upperHullList.end(),std::back_inserter(fConvexHull));
 
     if (pMinMin != pMinMax) fConvexHull.push_back(pMinMin);
 
     return;
 }

float lar_cluster3d::ConvexHull::getConvexHullArea ( ) const

inline

recover the area of the convex hull

Definition at line 78 of file ConvexHull.h.

78 {return fConvexHullArea;}

lar_cluster3d::ConvexHull::fConvexHullArea

float fConvexHullArea

Definition: ConvexHull.h:120

const ConvexHull::PointList & lar_cluster3d::ConvexHull::getExtremePoints ( )

Find the two points on the hull which are furthest apart.

Definition at line 207 of file ConvexHull.cxx.

 {
     PointList::const_iterator nextPointItr  = fConvexHull.begin();
     PointList::const_iterator firstPointItr = nextPointItr++;
 
     float  maxSeparation(0.);
 
     // Make sure the current list has been cleared
     fExtremePoints.clear();
 
     // For finding the two farthest points
     PointPair extremePoints(Point(0,0,NULL),Point(0,0,NULL));
 
     while(nextPointItr != fConvexHull.end())
     {
         // Get a vector representing the edge from the first to the current next point
         Point           firstPoint  = *firstPointItr++;
         Point           nextPoint   = *nextPointItr;
         Eigen::Vector2f firstEdge(std::get<0>(*firstPointItr) - std::get<0>(firstPoint), std::get<1>(*firstPointItr) - std::get<1>(firstPoint));
 
         // normalize it
         firstEdge.normalize();
 
         PointList::const_iterator endPointItr = nextPointItr;
 
         while(++endPointItr != fConvexHull.end())
         {
             Point           endPoint = *endPointItr;
             Eigen::Vector2f nextEdge(std::get<0>(endPoint) - std::get<0>(nextPoint), std::get<1>(endPoint) - std::get<1>(nextPoint));
 
             // normalize it
             nextEdge.normalize();
 
             // Have we found the turnaround point?
             if (firstEdge.dot(nextEdge) < 0.)
             {
                 Eigen::Vector2f separation(std::get<0>(nextPoint) - std::get<0>(firstPoint), std::get<1>(nextPoint) - std::get<1>(firstPoint));
                 float           separationDistance = separation.norm();
 
                 if (separationDistance > maxSeparation)
                 {
                     extremePoints.first  = firstPoint;
                     extremePoints.second = nextPoint;
                     maxSeparation        = separationDistance;
                 }
 
                 // Regardless of thise being the maximum distance we have hit a turnaround point so
                 // we need to break out of this loop
                 break;
             }
 
             nextPointItr = endPointItr;
             nextPoint    = endPoint;
         }
 
         // If we have hit the end of the convex hull without finding a turnaround point then we are not
         // going to find one so break out of the main loop
         if (endPointItr == fConvexHull.end()) break;
 
         // Need to make sure we don't overrun the next point
         if (firstPointItr == nextPointItr) nextPointItr++;
     }
 
     fExtremePoints.push_back(extremePoints.first);
     fExtremePoints.push_back(extremePoints.second);
 
     return fExtremePoints;
 }

const reco::ConvexHullKinkTupleList & lar_cluster3d::ConvexHull::getKinkPoints ( )

Find the points with the largest angles.

Definition at line 276 of file ConvexHull.cxx.

 {
     // Goal here is to isolate the points where we see a large deviation in the contour defined by the
     // convex hull. The complications are numerous, chief is that some deviations can be artificially
     // "rounded" by a series of very small steps around a large corner. So we need to protect against that.
 
     // Make sure the current list has been cleared
     fKinkPoints.clear();
 
     // Need a mininum number of points/edges
     if (fConvexHull.size() > 3)
     {
         // Idea will be to traverse the convex hull and keep track of all points where there is a
         // "kink" which will be defined as a "large" angle between adjacent edges.
         // Recall that construxtion of the convex hull results in the same point at the start and
         // end of the list
         // Getting the initial point requires some contortions because the convex hull point list will
         // contain the same point at both ends of the list (why?)
         PointList::iterator pointItr = fConvexHull.begin();
 
         // Advance to the second to last element
         std::advance(pointItr, fConvexHull.size() - 2);
 
         Point lastPoint = *pointItr++;
 
         // Reset pointer to the first element
         pointItr = fConvexHull.begin();
 
         Point           curPoint  = *pointItr++;
         Eigen::Vector2f lastEdge(std::get<0>(curPoint) - std::get<0>(lastPoint), std::get<1>(curPoint) - std::get<1>(lastPoint));
 
         lastEdge.normalize();
 
         while(pointItr != fConvexHull.end())
         {
             Point& nextPoint = *pointItr++;
 
             Eigen::Vector2f nextEdge(std::get<0>(nextPoint) - std::get<0>(curPoint), std::get<1>(nextPoint) - std::get<1>(curPoint));
 
             if (nextEdge.norm() > fMinEdgeDistance)
             {
                 nextEdge.normalize();
 
                 if (lastEdge.dot(nextEdge) < fKinkAngle) fKinkPoints.emplace_back(curPoint,lastEdge,nextEdge);
 
                 lastEdge = nextEdge;
             }
 
             curPoint = nextPoint;
         }
     }
 
     return fKinkPoints;
 }

const MinMaxPointPair& lar_cluster3d::ConvexHull::getMinMaxPointPair ( ) const

inline

find the ends of the convex hull (along its x axis)

Definition at line 63 of file ConvexHull.h.

63 {return fMinMaxPointPair;}

lar_cluster3d::ConvexHull::fMinMaxPointPair

MinMaxPointPair fMinMaxPointPair

Definition: ConvexHull.h:119

const PointList& lar_cluster3d::ConvexHull::getPointsList ( )

inline

recover the list of points used to build convex hull

Definition at line 53 of file ConvexHull.h.

53 {return fPoints;}

lar_cluster3d::ConvexHull::fPoints

const PointList & fPoints

Definition: ConvexHull.h:117

bool lar_cluster3d::ConvexHull::isLeft	(	const Point &	p0,
		const Point &	p1,
		const Point &	pCheck
	)		const

private

Determines whether a point is to the left, right or on line specifiec by p0 and p1.

Definition at line 49 of file ConvexHull.cxx.

 {
     // Use the cross product to determine if the check point lies to the left, on or right
     // of the line defined by points p0 and p1
     return crossProduct(p0, p1, pCheck) > 0;
 }

Member Data Documentation

PointList lar_cluster3d::ConvexHull::fConvexHull

private

Definition at line 118 of file ConvexHull.h.

float lar_cluster3d::ConvexHull::fConvexHullArea

private

Definition at line 120 of file ConvexHull.h.

PointList lar_cluster3d::ConvexHull::fExtremePoints

private

Definition at line 121 of file ConvexHull.h.

float lar_cluster3d::ConvexHull::fKinkAngle

private

Definition at line 114 of file ConvexHull.h.

reco::ConvexHullKinkTupleList lar_cluster3d::ConvexHull::fKinkPoints

private

Definition at line 122 of file ConvexHull.h.

float lar_cluster3d::ConvexHull::fMinEdgeDistance

private

Definition at line 115 of file ConvexHull.h.

MinMaxPointPair lar_cluster3d::ConvexHull::fMinMaxPointPair

private

Definition at line 119 of file ConvexHull.h.

const PointList& lar_cluster3d::ConvexHull::fPoints

private

Definition at line 117 of file ConvexHull.h.

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

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation