Voronoi.h

Go to the documentation of this file.

#ifndef VoronoiDiagram_h
#define VoronoiDiagram_h

// std includes
#include <list>
#include <algorithm>
#include <queue>

// LArSoft includes
#include "larreco/RecoAlg/Cluster3DAlgs/Voronoi/SweepEvent.h"
#include "larreco/RecoAlg/Cluster3DAlgs/Voronoi/BeachLine.h"
#include "larreco/RecoAlg/Cluster3DAlgs/Voronoi/EventUtilities.h"

#include <boost/polygon/voronoi.hpp>

// Algorithm includes
#include "larreco/RecoAlg/Cluster3DAlgs/Cluster3D.h"
//------------------------------------------------------------------------------------------------------------------------------------------

namespace voronoi2d
{
class VoronoiDiagram
{
public:
    using PointPair       = std::pair<dcel2d::Point,dcel2d::Point>;
    using MinMaxPointPair = std::pair<PointPair,PointPair>;
    
    VoronoiDiagram(dcel2d::HalfEdgeList&, dcel2d::VertexList&, dcel2d::FaceList&);

    virtual ~VoronoiDiagram();
    
    void buildVoronoiDiagram(const dcel2d::PointList&);
    
    void buildVoronoiDiagramBoost(const dcel2d::PointList&);
    
    const dcel2d::FaceList& getFaceList() const {return fFaceList;}
    
    const dcel2d::VertexList& getVertexList() const {return fVertexList;}

    double getVoronoiDiagramArea() const {return fVoronoiDiagramArea;}
    
    const dcel2d::PointList& getConvexHull() const {return fConvexHullList;}
    
    PointPair getExtremePoints() const;

    PointPair findNearestEdge(const dcel2d::Point&, double&) const;
    
    double findNearestDistance(const dcel2d::Point&) const;

private:
    
    using EventQueue = std::priority_queue<IEvent*, std::vector<IEvent*>, bool(*)(const IEvent*,const IEvent*)>;
    
    void handleSiteEvents(BeachLine&, EventQueue&, IEvent*);
    
    void handleCircleEvents(BeachLine&, EventQueue&, IEvent*);
    
    void makeLeftCircleEvent(EventQueue&, BSTNode*, double);
    void makeRightCircleEvent(EventQueue&, BSTNode*, double);

    IEvent* makeCircleEvent(BSTNode*, BSTNode*, BSTNode*, double);
    
    bool computeCircleCenter(const dcel2d::Coords&, const dcel2d::Coords&, const dcel2d::Coords&, dcel2d::Coords&, double&, double&) const;

    bool computeCircleCenter2(const dcel2d::Coords&, const dcel2d::Coords&, const dcel2d::Coords&, dcel2d::Coords&, double&, double&) const;
    
    bool computeCircleCenter3(const dcel2d::Coords&, const dcel2d::Coords&, const dcel2d::Coords&, dcel2d::Coords&, double&, double&) const;
    
    void getConvexHull(const BSTNode*);
    
    void terminateInfiniteEdges(BeachLine&, double);
    
    bool isInsideConvexHull(const dcel2d::Vertex&) const;
    
    bool isOutsideConvexHull(const dcel2d::Vertex&, dcel2d::PointList::const_iterator, dcel2d::Coords&, double&) const;

    void findBoundingBox(const dcel2d::VertexList&);
    
    using BoostEdgeToEdgeMap     = std::map<const boost::polygon::voronoi_edge<double>*,   dcel2d::HalfEdge*>;
    using BoostVertexToVertexMap = std::map<const boost::polygon::voronoi_vertex<double>*, dcel2d::Vertex*>;
    using BoostCellToFaceMap     = std::map<const boost::polygon::voronoi_cell<double>*,   dcel2d::Face*>;

    void boostTranslation(const dcel2d::PointList&,
                          const boost::polygon::voronoi_edge<double>*,
                          const boost::polygon::voronoi_edge<double>*,
                          BoostEdgeToEdgeMap&,
                          BoostVertexToVertexMap&,
                          BoostCellToFaceMap&);

    void mergeDegenerateVertices();
    
    double ComputeFaceArea();
    
    double crossProduct(const dcel2d::Point& p0, const dcel2d::Point& p1, const dcel2d::Point& p2) const;

    double Area() const;

    bool isLeft(const dcel2d::Point& p0, const dcel2d::Point& p1, const dcel2d::Point& pCheck) const;
    
    dcel2d::HalfEdgeList& fHalfEdgeList;
    dcel2d::VertexList&   fVertexList;
    dcel2d::FaceList&     fFaceList;

    dcel2d::PointList     fPointList;
    SiteEventList         fSiteEventList;       //< Container for site events
    CircleEventList       fCircleEventList;     //< Container for circle events
    BSTNodeList           fCircleNodeList;      //< Container for the circle "nodes"
    
    dcel2d::PointList     fConvexHullList;      //< Points representing the convex hull
    dcel2d::Coords        fConvexHullCenter;    //< Center of the convex hull
    
    double                fXMin;                //< Bounding box min value x
    double                fXMax;                //< Bounding box max value x
    double                fYMin;                //< Bounding box min value y
    double                fYMax;                //< Bounding box max value y
    mutable int           fNumBadCircles;       //< Number bad circles
    double                fVoronoiDiagramArea;
    
    EventUtilities        fUtilities;           //< Handy functions to operate on arcs

};
    
} // namespace lar_cluster3d
#endif