lar_cluster3d::ConvexHull Class Reference

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...
virtual	~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 25 of file ConvexHull.h.

Member Typedef Documentation

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

Definition at line 34 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 31 of file ConvexHull.h.

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

The list of the projected points.

Definition at line 32 of file ConvexHull.h.

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

Definition at line 33 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 31 of file ConvexHull.cxx.

References Area(), fConvexHull, fConvexHullArea, fPoints, and getConvexHull().

                                                                                           :
    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 ( )

virtual

Destructor.

Definition at line 45 of file ConvexHull.cxx.

{
}

Member Function Documentation

float lar_cluster3d::ConvexHull::Area ( ) const

private

Computes the area of the enclosed convext hull.

Definition at line 73 of file ConvexHull.cxx.

References crossProduct(), fConvexHull, n, x, and y.

Referenced by ConvexHull(), and getConvexHullArea().

{
    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 60 of file ConvexHull.cxx.

Referenced by Area(), getConvexHullArea(), and isLeft().

{
    // 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 394 of file ConvexHull.cxx.

References findNearestEdge().

Referenced by getConvexHullArea().

{
    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 333 of file ConvexHull.cxx.

References fConvexHull, isLeft(), and max.

Referenced by findNearestDistance(), and getConvexHullArea().

{
    // 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 56 of file ConvexHull.h.

References fConvexHull.

Referenced by lar_cluster3d::ClusterPathFinder::buildConvexHull(), lar_cluster3d::ConvexHullPathFinder::buildConvexHull(), lar_cluster3d::VoronoiPathFinder::buildConvexHull(), ConvexHull(), voronoi2d::VoronoiDiagram::getConvexHull(), and getConvexHullArea().

{return fConvexHull;}

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 109 of file ConvexHull.cxx.

References fConvexHull, fMinMaxPointPair, and isLeft().

{
    // 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 76 of file ConvexHull.h.

References Area(), crossProduct(), fConvexHullArea, findNearestDistance(), findNearestEdge(), getConvexHull(), and isLeft().

Referenced by lar_cluster3d::ClusterPathFinder::buildConvexHull(), lar_cluster3d::ConvexHullPathFinder::buildConvexHull(), and lar_cluster3d::VoronoiPathFinder::buildConvexHull().

{return fConvexHullArea;}

const ConvexHull::PointList & lar_cluster3d::ConvexHull::getExtremePoints

(

)

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

Definition at line 209 of file ConvexHull.cxx.

References fConvexHull, and fExtremePoints.

Referenced by getMinMaxPointPair().

{
    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 278 of file ConvexHull.cxx.

References fConvexHull, fKinkAngle, fKinkPoints, and fMinEdgeDistance.

Referenced by getMinMaxPointPair().

{
    // 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 61 of file ConvexHull.h.

References fMinMaxPointPair, getExtremePoints(), and getKinkPoints().

{return fMinMaxPointPair;}

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

inline

recover the list of points used to build convex hull

Definition at line 51 of file ConvexHull.h.

References fPoints.

{return fPoints;}

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 51 of file ConvexHull.cxx.

References crossProduct().

Referenced by findNearestEdge(), getConvexHull(), and getConvexHullArea().

{
    // 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 116 of file ConvexHull.h.

Referenced by Area(), ConvexHull(), findNearestEdge(), getConvexHull(), getExtremePoints(), and getKinkPoints().

float lar_cluster3d::ConvexHull::fConvexHullArea

private

Definition at line 118 of file ConvexHull.h.

Referenced by ConvexHull(), and getConvexHullArea().

PointList lar_cluster3d::ConvexHull::fExtremePoints

private

Definition at line 119 of file ConvexHull.h.

Referenced by getExtremePoints().

float lar_cluster3d::ConvexHull::fKinkAngle

private

Definition at line 112 of file ConvexHull.h.

Referenced by getKinkPoints().

reco::ConvexHullKinkTupleList lar_cluster3d::ConvexHull::fKinkPoints

private

Definition at line 120 of file ConvexHull.h.

Referenced by getKinkPoints().

float lar_cluster3d::ConvexHull::fMinEdgeDistance

private

Definition at line 113 of file ConvexHull.h.

Referenced by getKinkPoints().

MinMaxPointPair lar_cluster3d::ConvexHull::fMinMaxPointPair

private

Definition at line 117 of file ConvexHull.h.

Referenced by getConvexHull(), and getMinMaxPointPair().

const PointList& lar_cluster3d::ConvexHull::fPoints

private

Definition at line 115 of file ConvexHull.h.

Referenced by ConvexHull(), and getPointsList().

---

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

• /cvmfs/larsoft.opensciencegrid.org/products/larreco/v07_10_02/source/larreco/RecoAlg/Cluster3DAlgs/ConvexHull/ConvexHull.h
• /cvmfs/larsoft.opensciencegrid.org/products/larreco/v07_10_02/source/larreco/RecoAlg/Cluster3DAlgs/ConvexHull/ConvexHull.cxx