Voronoi.h

Go to the documentation of this file.

// ----------------------------------------------------------------------------
//
// $Id$
//
// Copyright 2008, 2009, 2010, 2011, 2012  Antonio Franchi and Paolo Stegagno    
//
// This file is part of MIP.
//
// MIP is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// MIP is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with MIP. If not, see <http://www.gnu.org/licenses/>.
//
// Contact info: antonio.franchi@tuebingen.mpg.de stegagno@diag.uniroma1.it
//
// ----------------------------------------------------------------------------





/* @{ */


#ifndef __VORONOI_H__
#define __VORONOI_H__

#include <Scan.h>
#include <DraWin.h>

#include <CGAL/basic.h>

#include <CGAL/Simple_cartesian.h>
// #include <CGAL/Filtered_kernel.h>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Voronoi_diagram_2.h>
#include <CGAL/Delaunay_triangulation_adaptation_traits_2.h>
#include <CGAL/Delaunay_triangulation_adaptation_policies_2.h>

#include <CGAL/IO/Geomview_stream.h>
#include <CGAL/IO/Triangulation_geomview_ostream_2.h>

#include <CGAL/intersections.h>
#include <CGAL/centroid.h>
#include <CGAL/Polygon_2.h>

#include <CGAL/Min_circle_2.h>
#include <CGAL/Min_circle_2_traits_2.h>

#include <CGAL/convex_hull_2.h>

using namespace MipResources;

typedef CGAL::Exact_predicates_inexact_constructions_kernel    K;
typedef CGAL::Delaunay_triangulation_2<K>  Triangulation;
typedef Triangulation::Edge_iterator  Edge_iterator;
typedef Triangulation::Point          Point;

typedef K::Line_2                   Line_2;
typedef K::Ray_2          Ray_2;
typedef K::Segment_2                Segment_2;

// typedefs for defining the adaptor
//typedef CGAL::Exact_predicates_inexact_constructions_kernel                  K;
typedef CGAL::Delaunay_triangulation_2<K>                                    DT;
typedef CGAL::Delaunay_triangulation_adaptation_traits_2<DT>                 AT;
typedef CGAL::Delaunay_triangulation_caching_degeneracy_removal_policy_2<DT> AP;
typedef CGAL::Voronoi_diagram_2<DT,AT,AP>                                    VD;

// typedef for the result type of the point location
typedef AT::Site_2                    Site_2;
typedef AT::Point_2                   Point_2;

typedef VD::Locate_result             Locate_result;
typedef VD::Vertex_handle             Vertex_handle;
typedef VD::Face_handle               Face_handle;
typedef VD::Halfedge_handle           Halfedge_handle;
typedef VD::Halfedge_iterator         Halfedge_iterator;
typedef VD::Ccb_halfedge_circulator   Ccb_halfedge_circulator;
typedef VD::Site_iterator             Site_iterator;

typedef CGAL::Polygon_2<K> Polygon_2;
typedef Polygon_2::Vertex_circulator Vertex_circulator;
typedef K::Vector_2 Vector_2;
typedef K::Direction_2 Direction_2;

typedef  CGAL::Min_circle_2_traits_2<K>  Traits;
typedef  CGAL::Min_circle_2<Traits>      Min_circle;

using CGAL::ORIGIN;


using namespace std;


class VoronoiEdgeSector {

 private:
  
  Angle _angMin;
  Angle _angMax; 
  Halfedge_handle _edge;
  bool _valid;
  Color _dwColor;
  
 public:
  
  VoronoiEdgeSector() { 
   _valid = false;
  }
  
  VoronoiEdgeSector(Angle angMin, Angle angMax, Halfedge_handle edge, Color dwColor) {
   _angMin = angMin;
   _angMax = angMax; 
   _edge = edge;
   _valid = true;
   _dwColor = dwColor;
  }
  
  ~VoronoiEdgeSector(){
  }
  
  Angle angMin() { return _angMin; }
  
  Angle angMax() { return _angMax; }
  
  Halfedge_handle edge() { return _edge; }
  
  bool valid() { return _valid; }
  
  Color dwColor() { return _dwColor; }
  
  bool isInside(Angle angle) {
   
   if (!_valid) return false;
   
   if (_angMax.dCast2Pi() >= _angMin.dCast2Pi()) {
    if (angle.dCast2Pi() >=  _angMin.dCast2Pi() && angle.dCast2Pi() <= _angMax.dCast2Pi()) return true;
   }
   else { //angMin > angMax if AngMax > 360°
    if (angle.dCast2Pi() >=  _angMin.dCast2Pi() || angle.dCast2Pi() <= _angMax.dCast2Pi()) return true;
   }
   
   return false;
  }
  
  string print(){
   stringstream s;
   s.precision(3);
   s.setf(ios::fixed,ios::floatfield);
   s << "(angMin: " << _angMin.dCastDeg() << " Deg, angMax: " << _angMax.dCastDeg() << " Deg)" ;
   return s.str();
  }
  
};


class Voronoi{
 private:
  Triangulation T;
  VD vd;
  
  vector <Segment_2> scanRays, limitedScanRays, voronoiScanRays;
  vector <Point_2> voronoiScanPoints;
  vector <Point_2> voronoiSites;
  vector <VoronoiEdgeSector> voronoiRegionSectors;
  
  
  CGAL::Geomview_stream* gv;
  bool gvSet;
  
  DraWin* dw;
  unsigned int dwList;
  bool dwSet;
  Pose dwPose;
  Decimal dwPointSize;
  Decimal dwDiskSize;
  Color dwColor;
  
  Face_handle findRegion(Position p);
  
  bool intersectionRayEdge(Segment_2 r, Halfedge_handle e, Point_2 & iPoint);
  
  bool findEdgeSector(Angle bearing, VoronoiEdgeSector & edgeSector);
  
  void findRegionSectors(Position p);
  
  void drawEdge(Halfedge_handle e);

  void drawScanRays(vector <Segment_2>& rays, int sampling=1);
  
  Point_2 polygonCentroid(Polygon_2 polyg);
  
 public:
  
  Voronoi(){
   gv = 0;
   gvSet = false;
   
   dw = 0;
   dwList = 0;
   dwSet = false;
  }

  ~Voronoi(){
  }
  
  void insert(Position p);

  bool valid();
    
  
  bool scanToFill(Scan& scan, Angle angRangeMin, Angle angRangeMax, Angle angRes);
  
  void fillScan(Scan& scan, Decimal linRangeMax, Angle angRes);
  
  vector <Position> intersectScan(Scan& scan, Position p, Decimal limitedRange, bool limitedRangeOn=true, bool useSectors=true);
  
  Position centroid();
  
  Position weightedNormal(Decimal limitedRange, Decimal limitedRangeEps, Angle angRes, bool limitTarget = true);
  
  Position circumCenter(Decimal &radius);
  
  void clear();
  
  void setGV(CGAL::Geomview_stream* gvs);
  
  void setDW(DraWin* dwp, unsigned int dwpList);
  
  void setDWPose(Pose dwpPose);
  
  void setDWPointSize(Decimal s);
  
  void setDWDiskSize(Decimal s);
  
  void setDWColor(Color c);
  
  void drawDiagram();
  
  void drawSites();
  
  void drawDisk(Position p);
  
  void drawSegment(Position source, Position target);
  
  void drawCircle(Position center, Decimal radius, int sampling=1);
  
  void drawScan(int sampling=1);
  
  void drawLimitedScan(int sampling=1);
  
  void drawVoronoiScan(int sampling=1);
  
  void drawVoronoiScanPoints(int sampling=1);
//   void drawVoronoiScanPointsFar(int sampling=1);
//   void drawVoronoiScanPointsNear(int sampling=1);
  
  
  void drawRegionEdges(Position p);
  
  void drawRegionSectors(Position center, Decimal radius, int sampling=1);
  
  bool clearPlot();
  
  Position pointToPosition(Point_2 point);
  
  Point_2 positionToPoint(Position point);
};


#endif


/* @} */