MedialAxis2D.h

Go to the documentation of this file.

#ifndef MEDIAL_AXIS_2D_H_
#define MEDIAL_AXIS_2D_H_
 
#include <memory>
#include <map>
#include <limits>
#include <algorithm>
#include <unordered_map>
#include <tuple>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
#include <CGAL/Segment_Delaunay_graph_2.h>
#include <CGAL/Triangulation_2.h>
#include <containers/sequential/graph/graph.h>
#include <containers/sequential/graph/algorithms/graph_algo_util.h>
#include <boost/functional/hash.hpp>
 
using namespace std;
 
#include "Vector.h"
using namespace mathtool;
#include "IOUtils.h"
 
#include "Geometry/GMSPolyhedron.h"
#include "Geometry/Boundaries/Boundary.h"
#include "SegmentTrees.h"
#include "Workspace/WorkspaceSkeleton.h"
 
 
 
class MedialAxis2D {
 
  public:
    typedef CGAL::Simple_cartesian<double> CK;
    typedef CGAL::Segment_Delaunay_graph_filtered_traits_2<CK,
            CGAL::Field_with_sqrt_tag>  Gt;
    typedef CGAL::Segment_Delaunay_graph_2<Gt>   SDG2;
    typedef typename SDG2::Site_2 Site2;
    typedef typename SDG2::Point_2 Point2;
    typedef typename SDG2::Edge Edge2;
    typedef typename SDG2::Data_structure DS;
    typedef typename Gt::Segment_2 Segment2;
    typedef CGAL::Parabola_segment_2<Gt> Parabola2;
    // Type for clearance info - first: clearance value, second: witness
    typedef pair<double,Point3d> ClearanceType;
    // Types for skeleton and its annotations
    typedef WorkspaceSkeleton       SkeletonGraphType;
    typedef unordered_map<WorkspaceSkeleton::VD, ClearanceType>
      VertexClearanceMapType;
 
    struct MedialEdge {
      MedialEdge(Segment2& _s, Site2& _s1, Site2& _s2, double _ss = 0);
      MedialEdge(Parabola2& _p, Point2& _s, Point2& _t, Site2& _s1,
          Site2& _s2);
      MedialEdge(Point2& _s, Point2& _t, Site2& _s1, Site2& _s2);
 
      const Point2& GetSource() { return m_interpolated.front();  }
      const Point2& GetTarget() { return m_interpolated.back(); }
      bool IsSegment() { return m_isLine; }
 
      void InterpolateSegment(double _step);
 
      vector<Point2> m_interpolated;  
      Site2 m_site1, m_site2;   
      bool m_isLine{true};      
      bool m_isFree{false}; 
      friend class MedialAxis2D;
    };
 
    typedef stapl::sequential::graph<stapl::UNDIRECTED,stapl::MULTIEDGES,
            Point2, MedialEdge>  MedialAxisGraph;
 
    struct PolygonSegment {
      // Constructor function
      PolygonSegment(Point2& _s, Point2& _t);
      // Check the point lies on the segment
      bool OnLine(const Point2& _p);
      Point2 Source() { return m_end[0]; }
      Point2 Target() { return m_end[1]; }
      double GetConstant() { return m_constant; }
      double GetMultiple() { return m_multiple; }
      Point2 m_end[2];  
      double m_constant;  
      double m_multiple;    
    };
    typedef vector<PolygonSegment> PolygonSegments;
 
    struct edgeHash {
      size_t operator()(const WorkspaceSkeleton::ED& _ed) const {
        size_t seed = 0;
        boost::hash_combine(seed,_ed.id());
        boost::hash_combine(seed,boost::hash_value(make_pair(_ed.source(),
                _ed.target())));
        return seed;
        //return hash<typename ED::edge_id_type>()(_ed.id());
      }
    };
    // Clearance map type for skeleton edges
    typedef unordered_map<WorkspaceSkeleton::ED,vector<ClearanceType>,
            edgeHash> EdgeClearanceMapType;
 
    MedialAxis2D() : m_segTree(2){}
    MedialAxis2D(vector<GMSPolyhedron>& _polys, const Boundary* _b,
        vector<Boundary*> _bndrys=vector<Boundary*>());
 
 
    void AddSegments(vector<pair<Point3d,Point3d>>& _s);
 
    void AddSegments(vector<Point3d>& _p, vector<pair<size_t,size_t>>& _s);
 
    void AddPoints(vector<Point3d>& _p);
 
    void BuildMedialAxis();
 
 
    tuple<WorkspaceSkeleton,VertexClearanceMapType,EdgeClearanceMapType>
      GetSkeleton(size_t _t=0);
 
    vector<ClearanceType> AnnotateSegment(MedialEdge& _e);
 
    double GetVertexClearance(size_t _i);
    Point3d GetVertexClearanceWitness(size_t _i);
 
 
  private:
 
    void AddPolygon(const GMSPolyhedron& _p,
        vector<pair<Point3d,Point3d>>& _s, Boundary* _b = nullptr);
 
    bool IsSkeletonEdge(Edge2& _e);
 
    bool IsMedialAxisEdge(Edge2& _e, bool k=false);
    bool IsReflexBisector(const Point2& _p1, const Point2& _p2,
        Site2& _s1, Site2& _s2);
 
    ClearanceType GetMinDistance(const Point2& _p, Site2& _s1, Site2& _s2);
 
    ClearanceType DistanceToSite(const Point2& _p, Site2& _s);
 
    double GetMinDistance(MedialEdge& _e);
 
    double GetMaxDistance(MedialEdge& _e);
 
    void CalculateClearance();
    bool IsFree(const Point2& _p);
    bool IsOutside(const Point2& _p);
 
    void ValidateEdge(MedialEdge& _e);
 
    Point2 MidPoint(Site2& _o, Site2& _p, Site2& _q, Point2& _fp);
 
 
    SDG2 sdg; 
    MedialAxisGraph m_graph;    
    vector<PolygonSegments> m_polygons; 
 
    SegmentTrees<> m_segTree; 
 
    unordered_map<size_t, ClearanceType> m_vertexClearance; 
 
    bool m_debug{false};   
    Point3d m_boundary[2]; 
 
};
 
#endif