Voronoi.h

Go to the documentation of this file.

#ifndef VoronoiDiagram_h
#define VoronoiDiagram_h

// std includes
#include <queue>

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

#include <boost/polygon/voronoi.hpp>

// Algorithm includes
#include "larreco/RecoAlg/Cluster3DAlgs/Voronoi/DCEL.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&);

    ~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&) const;

    bool computeCircleCenter3(const dcel2d::Coords&,
                              const dcel2d::Coords&,
                              const dcel2d::Coords&,
                              dcel2d::Coords&,
                              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