src/INTERP_KERNEL/PolygonAlgorithms.hxx

   1 // Copyright (C) 2007-2016  CEA/DEN, EDF R&D
   2 //
   3 // This library is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU Lesser General Public
   5 // License as published by the Free Software Foundation; either
   6 // version 2.1 of the License, or (at your option) any later version.
   7 //
   8 // This library is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // Lesser General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU Lesser General Public
  14 // License along with this library; if not, write to the Free Software
  15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19
  20 #ifndef __POLYGONALGORITHMS_HXX__
  21 #define __POLYGONALGORITHMS_HXX__
  22
  23 #include <vector>
  24 #include <deque>
  25 #include <map>
  26
  27 namespace INTERP_KERNEL
  28 {
  29   template<int DIM>
  30   class VertexLess
  31   {
  32   public:
  33     bool operator()(const double * P_1, const double * P_2) const
  34     {
  35       for(int idim=0; idim<DIM; idim++)
  36         {
  37           if(P_1[idim] < P_2[idim] )  return true;
  38           else if( P_1[idim] > P_2[idim]) return false;
  39         }
  40       return false;
  41     }
  42   };
  43
  44   template<int DIM>
  45   class PolygonAlgorithms
  46   {
  47   public:
  48     PolygonAlgorithms(double epsilon, double precision);
  49     std::deque<double> intersectConvexPolygons(const double* P_1,const double* P_2, int N1, int N2);
  50
  51     //Not yet tested
  52     int convexDecomposition(const double * P, int N, std::vector< std::map< int,int > >& components,
  53                             std::vector< int >& components_index, const double epsilon);
  54   private:
  55     void defineIndices(int& i_loc, int& i_next, int& i_prev,
  56                        const double *& Poly1, const double *& Poly2,
  57                        int& j1, int& j1_glob, int& j2, int& j2_glob,
  58                        int& j3, int& j3_glob, int& j4, int& j4_glob,
  59                        int& i_glob, int& i_next_glob, int& i_prev_glob,
  60                        const double * P_1, const double * P_2,
  61                        int N1, int N2, int sign);
  62     void addCrossings( const double * A, const double * B, int i , int i_next,
  63                        const double * C, const double * D, int j1, int j2,
  64                        const double * E, const double * F, int j3, int j4,
  65                        const double * G);
  66     void addCrossing0(const double * A, const double * B, int i, int i_next,
  67                       const double * C, const double * D, int j, int j_next);
  68     void addCrossing( double * ABCD, std::pair< int,int > i_i_next, std::pair< int,int > j_j_next);
  69     void addNewVertex( int i, int i_glob, int i_next_glob, int i_prev_glob, const double * P);
  70     bool intersectSegmentSegment(const double * A,  const double * B, const double * C,
  71                                  const double * D,  const double * E, double * V);
  72
  73
  74     //Not yet tested
  75     void convexDecomposition(const double* P, int N, double* n,  std::vector< int > subP, int NsubP,
  76                              std::vector< std::map< int,int > >& components, std::vector< int >& components_index,
  77                              int& Ncomp, int sign, const double epsilon);
  78     void convHull(const double *P, int N, double * n,  std::map< int,int >& subP,
  79                   std::map< int,int >& not_in_hull, int& NsubP, const double epsilon);
  80   private:
  81     std::deque< double > _Inter;/* vertices of the intersection  P1^P2 */
  82     std::vector< std::pair< int,int > > _End_segments; /* segments containing inter final edges */
  83     /* status list of segments (ending point, starting point) intersected by the sweeping line */
  84     /* and a boolean true if the ending point is in the intersection */
  85     std::multimap< int, std::pair< int,bool> > _Status;
  86     bool _is_in_intersection;
  87     bool _terminus;
  88     double _vdouble[DIM];
  89     double _epsilon;
  90     double _precision;
  91   };
  92 }
  93
  94 #endif