1 // Copyright (C) 2007-2023 CEA/DEN, EDF R&D
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.
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.
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
17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
20 #ifndef __POLYGONALGORITHMS_HXX__
21 #define __POLYGONALGORITHMS_HXX__
27 namespace INTERP_KERNEL
33 bool operator()(const double * P_1, const double * P_2) const
35 for(int idim=0; idim<DIM; idim++)
37 if(P_1[idim] < P_2[idim] ) return true;
38 else if( P_1[idim] > P_2[idim]) return false;
45 class PolygonAlgorithms
48 PolygonAlgorithms(double epsilon, double precision);
49 std::deque<double> intersectConvexPolygons(const double* P_1,const double* P_2, int N1, int N2);
52 int convexDecomposition(const double * P, int N, std::vector< std::map< int,int > >& components,
53 std::vector< int >& components_index, const double epsilon);
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,
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);
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);
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;