lar_cluster3d::ConvexHull Class Reference

ConvexHull class definiton. More...

#include "ConvexHull.h"

Public Types
using	Point = std::tuple< float, float, const reco::ClusterHit3D * >
	Definitions used by the ConvexHull algorithm. More...
using	PointList = std::list< Point >
using	PointPair = std::pair< Point, Point >
using	MinMaxPointPair = std::pair< PointPair, PointPair >

Public Member Functions
	ConvexHull (const PointList &)
	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...
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
const PointList &	fPoints
PointList	fConvexHull
MinMaxPointPair	fMinMaxPointPair
float	fConvexHullArea

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*>

Definitions used by the ConvexHull algorithm.

Definition at line 31 of file ConvexHull.h.

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

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

)

Constructor.

Parameters

pset

Definition at line 28 of file ConvexHull.cxx.

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

                                                   : 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 41 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 69 of file ConvexHull.cxx.

References crossProduct(), and fConvexHull.

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 (for technical reasons we use 0,0)
    // and then sum the signed area of triangles formed from this point to two adjecent
    // vertices on the convex hull.
    Point center(0.,0.,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 56 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 255 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 194 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::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 94 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 66 of file ConvexHull.h.

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

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

{return fConvexHullArea;}

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.

{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 47 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 103 of file ConvexHull.h.

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

float lar_cluster3d::ConvexHull::fConvexHullArea

private

Definition at line 105 of file ConvexHull.h.

Referenced by ConvexHull(), and getConvexHullArea().

MinMaxPointPair lar_cluster3d::ConvexHull::fMinMaxPointPair

private

Definition at line 104 of file ConvexHull.h.

Referenced by getConvexHull(), and getMinMaxPointPair().

const PointList& lar_cluster3d::ConvexHull::fPoints

private

Definition at line 102 of file ConvexHull.h.

Referenced by ConvexHull(), and getPointsList().

---

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

• larreco/v06_64_02/source/larreco/RecoAlg/Cluster3DAlgs/ConvexHull/ConvexHull.h
• larreco/v06_64_02/source/larreco/RecoAlg/Cluster3DAlgs/ConvexHull/ConvexHull.cxx