GetFEM  5.4.2
bgeot_mesh_structure.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 1999-2020 Yves Renard
5 
6  This file is a part of GetFEM
7 
8  GetFEM is free software; you can redistribute it and/or modify it
9  under the terms of the GNU Lesser General Public License as published
10  by the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version along with the GCC Runtime Library
12  Exception either version 3.1 or (at your option) any later version.
13  This program is distributed in the hope that it will be useful, but
14  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16  License and GCC Runtime Library Exception for more details.
17  You should have received a copy of the GNU Lesser General Public License
18  along with this program; if not, write to the Free Software Foundation,
19  Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
20 
21  As a special exception, you may use this file as it is a part of a free
22  software library without restriction. Specifically, if other files
23  instantiate templates or use macros or inline functions from this file,
24  or you compile this file and link it with other files to produce an
25  executable, this file does not by itself cause the resulting executable
26  to be covered by the GNU Lesser General Public License. This exception
27  does not however invalidate any other reasons why the executable file
28  might be covered by the GNU Lesser General Public License.
29 
30 ===========================================================================*/
31 
32 /**@file bgeot_mesh_structure.h
33  @author Yves Renard <[email protected]>
34  @date November 5, 1999.
35  @brief Mesh structure definition
36 */
37 
38 #ifndef BGEOT_MESH_STRUCTURE_H__
39 #define BGEOT_MESH_STRUCTURE_H__
40 
41 #include <set>
42 #include "bgeot_convex_structure.h"
43 #include "dal_tree_sorted.h"
44 
45 namespace bgeot {
46 
47  struct APIDECL mesh_convex_structure {
48  typedef std::vector<size_type> ind_pt_ct;
49 
50  pconvex_structure cstruct; /* type of convex. */
51  ind_pt_ct pts; /* point list indices. */
52 
53  pconvex_structure structure() const { return cstruct; }
54  pconvex_structure &structure() { return cstruct; }
55  mesh_convex_structure() : cstruct(0) {}
56  };
57 
58  struct convex_face
59  {
60  convex_face(size_type element, short_type face) : cv(element), f(face) {}
61  size_type cv = -1;
62  short_type f = -1;
63  bool valid() const {return (cv != size_type(-1)) && (f != short_type(-1));}
64  static convex_face invalid_face() {return {size_type(-1), short_type(-1)};}
65  };
66 
67  /**@addtogroup mesh */
68  ///@{
69  /** Mesh structure definition.
70  * At this point, the mesh is just a graph: the points have no
71  * associated coordinates
72  */
73  class APIDECL mesh_structure {
74 
75  public :
76 
77  typedef std::vector<size_type> ind_cv_ct;
78  typedef std::vector<size_type> ind_set;
79  typedef gmm::tab_ref_index_ref<ind_cv_ct::const_iterator,
80  convex_ind_ct::const_iterator> ind_pt_face_ct;
81  typedef dal::dynamic_array<ind_cv_ct, 8> point_ct;
82 
83  protected :
84 
85  dal::dynamic_tas<mesh_convex_structure, 8> convex_tab;
86  point_ct points_tab;
87 
88  public :
89 
90  /// Return the list of valid convex IDs
91  const dal::bit_vector &convex_index() const
92  { return convex_tab.index(); }
93  /// Return the list of valid convex IDs of a given dimension
94  dal::bit_vector convex_index(dim_type) const;
95  /// The total number of convexes in the mesh
96  size_type nb_convex() const { return convex_tab.card(); }
97  /// The number of convex indexes from 0 to the index of the last convex
98  size_type nb_allocated_convex() const
99  { return convex_tab.index().last_true()+1; }
100  /// Return true if i is in convex_index()
101  bool is_convex_valid(size_type i) { return (convex_tab.index())[i]; }
102  size_type nb_max_points() const { return points_tab.size(); }
103  /// Return true if the point i is used by at least one convex
104  bool is_point_valid(size_type i) const { return !(points_tab[i].empty()); }
105  /** Return a container to the list of points attached to convex ic.
106  They are ordered according to structure_of_convex(ic) */
107  const ind_set &ind_points_of_convex(size_type ic) const
108  { return convex_tab[ic].pts; }
109  /// Return the "local" index for point ip of the mesh
110  size_type local_ind_of_convex_point(size_type ic, size_type ip) const;
111  /// Return the pconvex_structure of the convex ic.
112  pconvex_structure structure_of_convex(size_type ic) const
113  { return convex_tab[ic].cstruct; }
114  /// Return the number of points of convex ic.
115  short_type nb_points_of_convex(size_type ic) const
116  { return convex_tab[ic].cstruct->nb_points(); }
117  /// Return the number of faces of convex ic.
118  short_type nb_faces_of_convex(size_type ic) const
119  { return short_type(convex_tab[ic].cstruct->nb_faces()); }
120  /// Exchange two point IDs
121  void swap_points(size_type i, size_type j);
122  /// Exchange two convex IDs
123  void swap_convex(size_type cv1, size_type cv2);
124 
125  template<class ITER>
126  size_type add_convex_noverif(pconvex_structure cs, ITER ipts,
127  size_type to_index = size_type(-1));
128  /** Insert a new convex in the mesh_structure.
129  @param cs the structure of the new convex.
130  @param ipts an iterator over a sequence of integers (point IDs of the convex nodes).
131  @param present an optional argument, contains true on return if the convex already exists in the mesh_structure.
132  @return the convex ID
133  */
134  template<class ITER>
135  size_type add_convex(pconvex_structure cs,
136  ITER ipts, bool *present = 0);
137  template<class ITER> size_type add_simplex(dim_type dim, ITER ipts)
138  { return add_convex(simplex_structure(dim), ipts); }
139  size_type add_segment(size_type a, size_type b);
140  /** Remove the convex ic */
141  void sup_convex(size_type ic);
142  /** Remove a convex given its points
143  @param nb the number of points for the convex
144  @param ipts an iterator over the list of point IDs of the convex
145  */
146  template<class ITER>
147  void sup_convex_with_points(ITER ipts, short_type nb);
148  void sup_segment(size_type a, size_type b)
149  { size_type t[2]; t[0] = a; t[1] = b; sup_convex_with_points(&t[0], 2); }
150  /** Insert a new convex corresponding to face f of the convex ic */
151  size_type add_face_of_convex(size_type ic, short_type f);
152  /** Insert new convexes corresponding to the faces of the convex ic */
153  void add_faces_of_convex(size_type ic);
154  /** build a new mesh, such that its convexes are the faces of the
155  convexes of the previous one */
156  void to_faces(dim_type n);
157  /** build a new mesh, such that its convexes are the edges of the
158  convexes of the previous one */
159  void to_edges();
160 
161  size_type nb_convex_with_edge(size_type i1, size_type i2);
162  void convex_with_edge(size_type i1, size_type i2,
163  std::vector<size_type> &ipt) const;
164 
165  /** Return a container of the convexes attached to point ip */
166  const ind_cv_ct &convex_to_point(size_type ip) const
167  { return points_tab[ip]; }
168  /** Return a container of the points attached (via an edge) to point ip */
169  void ind_points_to_point(size_type, ind_set &) const;
170 
171  /** Return true if the convex contains the listed points.
172  @param ic the convex ID.
173  @param nb the number of points which are searched in ic.
174  @param pit an iterator to the list of points searched.
175  */
176  template<class ITER>
177  bool is_convex_having_points(size_type ic,short_type nb, ITER pit) const;
178 
179  /** Return true if the face of the convex contains the given list of points */
180  template<class ITER>
181  bool is_convex_face_having_points(size_type ic, short_type face_num,
182  short_type nb, ITER pit) const;
183 
184  /** Return a container of the (global) point number for face f or convex ic */
185  ind_pt_face_ct ind_points_of_face_of_convex(size_type ic,
186  short_type f) const;
187 
188  size_type memsize() const;
189  /** Reorder the convex IDs and point IDs, such that there is no
190  hole in their numbering. */
191  void optimize_structure();
192  /// erase the mesh
193  void clear();
194  void stat();
195 
196  /** Return in s a list of neighbors of a given convex face.
197  @param ic the convex id.
198  @param f the face number of the convex.
199  @param s the resulting ind_set.
200  */
201  void neighbors_of_convex(size_type ic, short_type f, ind_set &s) const;
202  void neighbours_of_convex(size_type ic, short_type f, ind_set &s) const
203  IS_DEPRECATED { neighbors_of_convex(ic, f, s); }
204 
205  /** Return in s a list of neighbors of a given convex sharing the
206  intersection of a given list of faces
207  @param ic the convex id.
208  @param f the face number of the convex.
209  @param s the resulting ind_set.
210  */
211  void neighbors_of_convex(size_type ic,
212  const std::vector<short_type> &ftab,
213  ind_set &s) const;
214  void neighbours_of_convex(size_type ic,
215  const std::vector<short_type> &ftab,
216  ind_set &s) const IS_DEPRECATED
217  { neighbors_of_convex(ic, ftab, s); }
218 
219  /** Return a list of neighbors of a given convex.
220  @param ic the convex id.
221  @param s the resulting ind_set.
222  */
223  void neighbors_of_convex(size_type ic, ind_set &s) const;
224  void neighbours_of_convex(size_type ic, ind_set &s) const
225  IS_DEPRECATED { neighbors_of_convex(ic, s); }
226 
227  /** Return a neighbor convex of a given convex face.
228  @param ic the convex id.
229  @param f the face number of the convex.
230  @return size_type(-1) if there is no neighbor to this convex and
231  the index of the first neighbor found otherwise.
232  */
233  size_type neighbor_of_convex(size_type ic, short_type f) const;
234  size_type neighbour_of_convex(size_type ic, short_type f) const
235  IS_DEPRECATED { return neighbor_of_convex(ic, f); }
236 
237  /**Return a face of the neighbouring element that is adjacent to the
238  given face
239  @param ic the convex id.
240  @param f the face number of the convex.
241  @return convex_face that contains the neighbors convex id and the
242  adjacent face number, or convex_face::invalid_face() otherwise.
243  */
244  convex_face adjacent_face(size_type ic, short_type f) const;
245 
246  bool is_convex_having_neighbor(size_type ic, short_type f) const
247  { return (neighbor_of_convex(ic, f) != size_type(-1)); }
248  bool is_convex_having_neighbour(size_type ic, short_type f) const
249  IS_DEPRECATED { return (neighbor_of_convex(ic, f) != size_type(-1)); }
250 
251  /** Convex ID of the first convex attached to the point ip. */
252  size_type first_convex_of_point(size_type ip) const
253  { return points_tab[ip].empty() ? size_type(-1) : points_tab[ip][0]; }
254  /** Find the local index of the point of global index ip with respect to
255  * the convex cv.
256  * @return local index (a number smaller than
257  * nb_points_of_convex(first_convex_of_point(ip))) or size_type(-1) if
258  * the point is not found.
259  */
260  size_type ind_in_convex_of_point(size_type ic, size_type ip) const;
261  };
262  ///@}
263 
264 
265 
266 
267  /** Return the cuthill_mc_kee ordering on the convexes */
268  void APIDECL cuthill_mckee_on_convexes(const bgeot::mesh_structure &ms,
269  std::vector<size_type> &cmk);
270 
271  template<class ITER>
272  bool mesh_structure::is_convex_having_points(size_type ic,
273  short_type nb, ITER pit) const {
274  const ind_set &pt = ind_points_of_convex(ic);
275  for (short_type i = 0; i < nb; ++i, ++pit)
276  if (std::find(pt.begin(), pt.end(), *pit) == pt.end())
277  return false;
278  return true;
279  }
280 
281  template<class ITER> bool
282  mesh_structure::is_convex_face_having_points(size_type ic, short_type face_num,
283  short_type nb, ITER pit) const {
284  ind_pt_face_ct pt = ind_points_of_face_of_convex(ic, face_num);
285  for (short_type i = 0; i < nb; ++i, ++pit)
286  if (std::find(pt.begin(), pt.end(), *pit) == pt.end()) return false;
287  return true;
288  }
289 
290  template<class ITER>
291  size_type mesh_structure::add_convex_noverif(pconvex_structure cs,
292  ITER ipts, size_type is) {
293  mesh_convex_structure s; s.cstruct = cs;
294  size_type nb = cs->nb_points();
295 
296  if (is != size_type(-1)) { sup_convex(is); convex_tab.add_to_index(is,s); }
297  else is = convex_tab.add(s);
298 
299  convex_tab[is].pts.resize(nb);
300  for (size_type i = 0; i < nb; ++i, ++ipts)
301  { convex_tab[is].pts[i] = *ipts; points_tab[*ipts].push_back(is); }
302  return is;
303  }
304 
305  template<class ITER>
306  size_type mesh_structure::add_convex(pconvex_structure cs,
307  ITER ipts, bool *present) {
308  if (present) *present = false;
309  for (size_type i = 0; i < points_tab[*ipts].size(); ++i)
310  if (structure_of_convex(points_tab[*ipts][i]) == cs &&
311  is_convex_having_points(points_tab[*ipts][i], cs->nb_points(), ipts))
312  { if (present) *present = true; return points_tab[*ipts][i]; }
313  return add_convex_noverif(cs, ipts);
314  }
315 
316  template<class ITER>
317  void mesh_structure::sup_convex_with_points(ITER ipts, short_type nb) {
318  if (nb) {
319  for (size_type i = 0; i < points_tab[*ipts].size(); ++i)
320  if (is_convex_having_points(points_tab[*ipts][i], nb, ipts))
321  sup_convex(points_tab[*ipts][i]);
322  }
323  }
324 
325 
326  /* ********************************************************************* */
327  /* */
328  /* Gives the list of edges of a mesh. */
329  /* */
330  /* ********************************************************************* */
331 
332  /* maybe this should be removed from the matlab interface and obsoleted */
333  struct APIDECL edge_list_elt {
334  size_type i, j;
335  size_type cv;
336  inline bool operator < (const edge_list_elt &e) const {
337  if (i < e.i) return true;
338  if (i > e.i) return false;
339  if (j < e.j) return true; else if (j > e.j) return false;
340  if (cv < e.cv) return true;
341  return false;
342  }
343  edge_list_elt(size_type ii, size_type jj, size_type ic = 0) : cv(ic)
344  { i = std::min(ii, jj); j = std::max(ii, jj); }
345  edge_list_elt() {}
346  };
347 
348  typedef dal::dynamic_tree_sorted<edge_list_elt> edge_list;
349 
350  /* do not use that */
351  void APIDECL mesh_edge_list_convex(pconvex_structure cvs,
352  std::vector<size_type> points_of_convex,
353  size_type cv_id, edge_list &el,
354  bool merge_convex);
355  void APIDECL mesh_edge_list(const mesh_structure &m, edge_list &el,
356  bool merge_convex = true);
357 
358 
359 
360 } /* end of namespace bgeot. */
361 
362 
363 #endif /* BGEOT_MESH_STRUCTURE_H__ */
bgeot::mesh_structure::first_convex_of_point
size_type first_convex_of_point(size_type ip) const
Convex ID of the first convex attached to the point ip.
Definition: bgeot_mesh_structure.h:252
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
bgeot::mesh_structure::is_point_valid
bool is_point_valid(size_type i) const
Return true if the point i is used by at least one convex.
Definition: bgeot_mesh_structure.h:104
bgeot::mesh_structure::ind_points_of_convex
const ind_set & ind_points_of_convex(size_type ic) const
Return a container to the list of points attached to convex ic.
Definition: bgeot_mesh_structure.h:107
bgeot::mesh_structure::is_convex_having_points
bool is_convex_having_points(size_type ic, short_type nb, ITER pit) const
Return true if the convex contains the listed points.
Definition: bgeot_mesh_structure.h:272
bgeot::short_type
gmm::uint16_type short_type
used as the common short type integer in the library
Definition: bgeot_config.h:72
bgeot::simplex_structure
pconvex_structure simplex_structure(dim_type nc)
Give a pointer on the structures of a simplex of dimension d.
Definition: bgeot_convex_structure.cc:148
dal_tree_sorted.h
a balanced tree stored in a dal::dynamic_array
bgeot::mesh_structure::is_convex_valid
bool is_convex_valid(size_type i)
Return true if i is in convex_index()
Definition: bgeot_mesh_structure.h:101
bgeot::mesh_structure::convex_index
const dal::bit_vector & convex_index() const
Return the list of valid convex IDs.
Definition: bgeot_mesh_structure.h:91
bgeot::mesh_structure::is_convex_face_having_points
bool is_convex_face_having_points(size_type ic, short_type face_num, short_type nb, ITER pit) const
Return true if the face of the convex contains the given list of points.
Definition: bgeot_mesh_structure.h:282
dal::dynamic_array< ind_cv_ct, 8 >
bgeot::mesh_structure::ind_points_of_face_of_convex
ind_pt_face_ct ind_points_of_face_of_convex(size_type ic, short_type f) const
Return a container of the (global) point number for face f or convex ic.
Definition: bgeot_mesh_structure.cc:173
dal::dynamic_array::empty
bool empty(void) const
True if no space is allocated.
Definition: dal_basic.h:223
bgeot::mesh_structure::nb_convex
size_type nb_convex() const
The total number of convexes in the mesh.
Definition: bgeot_mesh_structure.h:96
bgeot::mesh_structure::convex_to_point
const ind_cv_ct & convex_to_point(size_type ip) const
Return a container of the convexes attached to point ip.
Definition: bgeot_mesh_structure.h:166
bgeot_convex_structure.h
Definition of convex structures.
bgeot::mesh_structure
Mesh structure definition.
Definition: bgeot_mesh_structure.h:73
bgeot
Basic Geometric Tools.
Definition: bgeot_convex_ref.cc:27
bgeot::pconvex_structure
std::shared_ptr< const convex_structure > pconvex_structure
Pointer on a convex structure description.
Definition: bgeot_convex_structure.h:54
bgeot::mesh_structure::nb_allocated_convex
size_type nb_allocated_convex() const
The number of convex indexes from 0 to the index of the last convex.
Definition: bgeot_mesh_structure.h:98
dal::dynamic_array::size
size_type size(void) const
Number of allocated elements.
Definition: dal_basic.h:219
bgeot::mesh_structure::sup_convex
void sup_convex(size_type ic)
Remove the convex ic.
Definition: bgeot_mesh_structure.cc:100
bgeot::mesh_structure::add_convex
size_type add_convex(pconvex_structure cs, ITER ipts, bool *present=0)
Insert a new convex in the mesh_structure.
Definition: bgeot_mesh_structure.h:306
bgeot::mesh_structure::sup_convex_with_points
void sup_convex_with_points(ITER ipts, short_type nb)
Remove a convex given its points.
Definition: bgeot_mesh_structure.h:317
gmm::tab_ref_index_ref
indexed array reference (given a container X, and a set of indexes I, this class provides a pseudo-co...
Definition: gmm_ref.h:289
bgeot::mesh_structure::nb_points_of_convex
short_type nb_points_of_convex(size_type ic) const
Return the number of points of convex ic.
Definition: bgeot_mesh_structure.h:115
bgeot::mesh_structure::structure_of_convex
pconvex_structure structure_of_convex(size_type ic) const
Return the pconvex_structure of the convex ic.
Definition: bgeot_mesh_structure.h:112
bgeot::mesh_structure::nb_faces_of_convex
short_type nb_faces_of_convex(size_type ic) const
Return the number of faces of convex ic.
Definition: bgeot_mesh_structure.h:118
bgeot::cuthill_mckee_on_convexes
void cuthill_mckee_on_convexes(const bgeot::mesh_structure &ms, std::vector< size_type > &cmk)
Return the cuthill_mc_kee ordering on the convexes.
Definition: bgeot_mesh_structure.cc:438