include/deal.II/grid/grid_tools.h

00001 //---------------------------------------------------------------------------
00002 //    @f$Id: grid_tools.h 25529 2012-05-21 22:21:25Z maier @f$
00003 //
00004 //    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 by the deal.II authors
00005 //
00006 //    This file is subject to QPL and may not be  distributed
00007 //    without copyright and license information. Please refer
00008 //    to the file deal.II/doc/license.html for the  text  and
00009 //    further information on this license.
00010 //
00011 //---------------------------------------------------------------------------
00012 #ifndef __deal2__grid_tools_H
00013 #define __deal2__grid_tools_H
00014 
00015 
00016 #include <deal.II/base/config.h>
00017 #include <deal.II/fe/mapping.h>
00018 #include <deal.II/grid/tria.h>
00019 #include <deal.II/grid/tria_accessor.h>
00020 #include <deal.II/grid/tria_iterator.h>
00021 #include <deal.II/fe/mapping_q1.h>
00022 
00023 #include <list>
00024 
00025 DEAL_II_NAMESPACE_OPEN
00026 
00027 
00028 template <int, int> class DoFHandler;
00029 template <int, int> class Mapping;
00030 namespace hp
00031 {
00032   template <int, int> class DoFHandler;
00033   template <int, int> class MappingCollection;
00034 }
00035 
00036 class SparsityPattern;
00037 
00038 
00047 namespace GridTools
00048 {
00061   template <int dim, int spacedim>
00062   double diameter (const Triangulation<dim, spacedim> &tria);
00063 
00074   template <int dim, int spacedim>
00075   double volume (const Triangulation<dim,spacedim> &tria,
00076                  const Mapping<dim,spacedim> &mapping = (StaticMappingQ1<dim,spacedim>::mapping));
00077 
00094   template <int dim>
00095   double cell_measure (const std::vector<Point<dim> > &all_vertices,
00096                        const unsigned int (&vertex_indices)[GeometryInfo<dim>::vertices_per_cell]);
00097 
00130   template <int dim, int spacedim>
00131   void delete_unused_vertices (std::vector<Point<spacedim> >    &vertices,
00132                                std::vector<CellData<dim> > &cells,
00133                                SubCellData                 &subcelldata);
00134 
00158   template <int dim, int spacedim>
00159   void delete_duplicated_vertices (std::vector<Point<spacedim> >    &all_vertices,
00160                                    std::vector<CellData<dim> > &cells,
00161                                    SubCellData                 &subcelldata,
00162                                    std::vector<unsigned int>   &considered_vertices,
00163                                    const double                 tol=1e-12);
00164 
00195   template <int dim, typename Predicate, int spacedim>
00196   void transform (const Predicate    &predicate,
00197                   Triangulation<dim,spacedim> &triangulation);
00198 
00210   template <int dim, int spacedim>
00211   void shift (const Point<spacedim>   &shift_vector,
00212               Triangulation<dim,spacedim> &triangulation);
00213 
00214 
00230   void rotate (const double      angle,
00231                Triangulation<2> &triangulation);
00232 
00247   template <int dim, int spacedim>
00248   void scale (const double        scaling_factor,
00249               Triangulation<dim, spacedim> &triangulation);
00250 
00263   template <int dim, template <int, int> class Container, int spacedim>
00264   unsigned int
00265   find_closest_vertex (const Container<dim, spacedim> &container,
00266                        const Point<spacedim>     &p);
00267 
00286   template<int dim, template <int, int> class Container, int spacedim>
00287   std::vector<typename Container<dim,spacedim>::active_cell_iterator>
00288   find_cells_adjacent_to_vertex (const Container<dim,spacedim> &container,
00289                                  const unsigned int    vertex);
00290 
00291 
00320   template <int dim, template <int,int> class Container, int spacedim>
00321   typename Container<dim,spacedim>::active_cell_iterator
00322   find_active_cell_around_point (const Container<dim,spacedim>  &container,
00323                                  const Point<spacedim> &p);
00324 
00379   template <int dim, template<int, int> class Container, int spacedim>
00380   std::pair<typename Container<dim,spacedim>::active_cell_iterator, Point<dim> >
00381   find_active_cell_around_point (const Mapping<dim,spacedim>   &mapping,
00382                                  const Container<dim,spacedim> &container,
00383                                  const Point<spacedim>     &p);
00384 
00395   template <int dim, int spacedim>
00396   std::pair<typename hp::DoFHandler<dim,spacedim>::active_cell_iterator, Point<dim> >
00397   find_active_cell_around_point (const hp::MappingCollection<dim,spacedim>   &mapping,
00398                                  const hp::DoFHandler<dim,spacedim> &container,
00399                                  const Point<spacedim>     &p);
00400 
00424   template <class Container>
00425   std::vector<typename Container::active_cell_iterator>
00426   get_active_child_cells (const typename Container::cell_iterator &cell);
00427 
00433   template <class Container>
00434   void
00435   get_active_neighbors (const typename Container::active_cell_iterator        &cell,
00436                         std::vector<typename Container::active_cell_iterator> &active_neighbors);
00437 
00449   template <int dim, int spacedim>
00450   void
00451   get_face_connectivity_of_cells (const Triangulation<dim, spacedim> &triangulation,
00452                                   SparsityPattern                    &connectivity);
00453 
00474   template <int dim, int spacedim>
00475   void
00476   partition_triangulation (const unsigned int  n_partitions,
00477                            Triangulation<dim, spacedim> &triangulation);
00478 
00555   template <int dim, int spacedim>
00556   void
00557   partition_triangulation (const unsigned int     n_partitions,
00558                            const SparsityPattern &cell_connection_graph,
00559                            Triangulation<dim,spacedim>    &triangulation);
00560 
00576   template <int dim, int spacedim>
00577   void
00578   get_subdomain_association (const Triangulation<dim, spacedim>  &triangulation,
00579                              std::vector<types::subdomain_id_t> &subdomain);
00580 
00603   template <int dim, int spacedim>
00604   unsigned int
00605   count_cells_with_subdomain_association (const Triangulation<dim, spacedim> &triangulation,
00606                                           const types::subdomain_id_t         subdomain);
00607 
00664   template <typename Container>
00665   std::list<std::pair<typename Container::cell_iterator,
00666                       typename Container::cell_iterator> >
00667   get_finest_common_cells (const Container &mesh_1,
00668                            const Container &mesh_2);
00669 
00684   template <int dim, int spacedim>
00685   bool
00686   have_same_coarse_mesh (const Triangulation<dim, spacedim> &mesh_1,
00687                          const Triangulation<dim, spacedim> &mesh_2);
00688 
00702   template <typename Container>
00703   bool
00704   have_same_coarse_mesh (const Container &mesh_1,
00705                          const Container &mesh_2);
00706 
00713   template <int dim, int spacedim>
00714   double
00715   minimal_cell_diameter (const Triangulation<dim, spacedim> &triangulation);
00716 
00721   template <int dim, int spacedim>
00722   double
00723   maximal_cell_diameter (const Triangulation<dim, spacedim> &triangulation);
00724 
00774   template <int dim, int spacedim>
00775   void
00776   create_union_triangulation (const Triangulation<dim, spacedim> &triangulation_1,
00777                               const Triangulation<dim, spacedim> &triangulation_2,
00778                               Triangulation<dim, spacedim>       &result);
00779 
00805   template <int dim, int spacedim>
00806   typename Triangulation<dim,spacedim>::DistortedCellList
00807   fix_up_distorted_child_cells (const typename Triangulation<dim,spacedim>::DistortedCellList &distorted_cells,
00808                                 Triangulation<dim,spacedim> &triangulation);
00809 
00896   template <template <int,int> class Container, int dim, int spacedim>
00897   std::map<typename Container<dim-1,spacedim>::cell_iterator,
00898            typename Container<dim,spacedim>::face_iterator>
00899   extract_boundary_mesh (const Container<dim,spacedim> &volume_mesh,
00900                          Container<dim-1,spacedim>     &surface_mesh,
00901                          const std::set<types::boundary_id_t> &boundary_ids
00902                          = std::set<types::boundary_id_t>());
00903 
00904 
00945   template<typename CellIterator>
00946   std::map<CellIterator, CellIterator>
00947   collect_periodic_cell_pairs (const CellIterator                          &begin,
00948                                const typename identity<CellIterator>::type &end,
00949                                const types::boundary_id_t                  boundary_component,
00950                                int                                         direction,
00951                                const ::Tensor<1,CellIterator::AccessorType::space_dimension>
00952                                  &offset = ::Tensor<1,CellIterator::AccessorType::space_dimension>());
00953 
00954 
00963   template<typename DH>
00964   std::map<typename DH::cell_iterator, typename DH::cell_iterator>
00965   collect_periodic_cell_pairs (const DH                   &dof_handler,
00966                                const types::boundary_id_t boundary_component,
00967                                int                        direction,
00968                                const ::Tensor<1,DH::space_dimension>
00969                                  &offset = Tensor<1,DH::space_dimension>());
00970 
00971 
00975 DeclException1 (ExcInvalidNumberOfPartitions,
00976                 int,
00977                 << "The number of partitions you gave is " << arg1
00978                 << ", but must be greater than zero.");
00982 DeclException1 (ExcNonExistentSubdomain,
00983                 int,
00984                 << "The subdomain id " << arg1
00985                 << " has no cells associated with it.");
00989 DeclException0 (ExcTriangulationHasBeenRefined);
00993 DeclException1 (ExcScalingFactorNotPositive,
00994                 double,
00995                 << "The scaling factor must be positive, but is " << arg1);
00999 template <int N>
01000 DeclException1 (ExcPointNotFoundInCoarseGrid,
01001                 Point<N>,
01002                 << "The point <" << arg1
01003                 << "> could not be found inside any of the "
01004                 << "coarse grid cells.");
01008 template <int N>
01009 DeclException1 (ExcPointNotFound,
01010                 Point<N>,
01011                 << "The point <" << arg1
01012                 << "> could not be found inside any of the "
01013                 << "subcells of a coarse grid cell.");
01014 
01015 DeclException1 (ExcVertexNotUsed,
01016                 unsigned int,
01017                 << "The given vertex " << arg1
01018                 << " is not used in the given triangulation");
01019 
01020 
01021 }
01022 
01023 
01024 
01025 /* ----------------- Template function --------------- */
01026 
01027 namespace GridTools
01028 {
01029   template <int dim, typename Predicate, int spacedim>
01030   void transform (const Predicate    &predicate,
01031                   Triangulation<dim, spacedim> &triangulation)
01032   {
01033                                      // ensure that all the cells of the
01034                                      // triangulation are on the same level
01035     Assert (triangulation.n_levels() ==
01036             static_cast<unsigned int>(triangulation.begin_active()->level()+1),
01037             ExcMessage ("Not all cells of this triangulation are at the same "
01038                         "refinement level, as is required for this function."));
01039 
01040     std::vector<bool> treated_vertices (triangulation.n_vertices(),
01041                                         false);
01042 
01043                                      // loop over all active cells, and
01044                                      // transform those vertices that
01045                                      // have not yet been touched. note
01046                                      // that we get to all vertices in
01047                                      // the triangulation by only
01048                                      // visiting the active cells.
01049     typename Triangulation<dim, spacedim>::active_cell_iterator
01050       cell = triangulation.begin_active (),
01051       endc = triangulation.end ();
01052     for (; cell!=endc; ++cell)
01053       for (unsigned int v=0; v<GeometryInfo<dim>::vertices_per_cell; ++v)
01054         if (treated_vertices[cell->vertex_index(v)] == false)
01055           {
01056                                              // transform this vertex
01057             cell->vertex(v) = predicate(cell->vertex(v));
01058                                              // and mark it as treated
01059             treated_vertices[cell->vertex_index(v)] = true;
01060           };
01061   }
01062 
01063 
01064 
01065   template <class DH>
01066   std::vector<typename DH::active_cell_iterator>
01067   get_active_child_cells (const typename DH::cell_iterator& cell)
01068   {
01069     std::vector<typename DH::active_cell_iterator> child_cells;
01070 
01071     if (cell->has_children())
01072       {
01073         for (unsigned int child=0;
01074              child<cell->n_children(); ++child)
01075           if (cell->child (child)->has_children())
01076             {
01077               const std::vector<typename DH::active_cell_iterator>
01078                 children = get_active_child_cells<DH> (cell->child(child));
01079               child_cells.insert (child_cells.end(),
01080                                   children.begin(), children.end());
01081             }
01082           else
01083             child_cells.push_back (cell->child(child));
01084       }
01085 
01086     return child_cells;
01087   }
01088 
01089 
01090 
01091   template <class Container>
01092   void
01093   get_active_neighbors(const typename Container::active_cell_iterator        &cell,
01094                        std::vector<typename Container::active_cell_iterator> &active_neighbors)
01095   {
01096     active_neighbors.clear ();
01097     for (unsigned int n=0; n<GeometryInfo<Container::dimension>::faces_per_cell; ++n)
01098       if (! cell->at_boundary(n))
01099         {
01100           if (Container::dimension == 1)
01101             {
01102                                                // check children of neighbor. note
01103                                                // that in 1d children of the neighbor
01104                                                // may be further refined. In 1d the
01105                                                // case is simple since we know what
01106                                                // children bound to the present cell
01107               typename Container::cell_iterator
01108                 neighbor_child = cell->neighbor(n);
01109               if (!neighbor_child->active())
01110                 {
01111                   while (neighbor_child->has_children())
01112                     neighbor_child = neighbor_child->child (n==0 ? 1 : 0);
01113 
01114                   Assert (neighbor_child->neighbor(n==0 ? 1 : 0)==cell,
01115                           ExcInternalError());
01116                 }
01117               active_neighbors.push_back (neighbor_child);
01118             }
01119           else
01120             {
01121               if (cell->face(n)->has_children())
01122                                                  // this neighbor has children. find
01123                                                  // out which border to the present
01124                                                  // cell
01125                 for (unsigned int c=0; c<cell->face(n)->number_of_children(); ++c)
01126                   active_neighbors.push_back (cell->neighbor_child_on_subface(n,c));
01127               else
01128                 {
01129                                                    // the neighbor must be active
01130                                                    // himself
01131                   Assert(cell->neighbor(n)->active(), ExcInternalError());
01132                   active_neighbors.push_back(cell->neighbor(n));
01133                 }
01134             }
01135         }
01136   }
01137 
01138 
01139 
01140 
01141 // declaration of explicit specializations
01142 
01143   template <>
01144   double
01145   cell_measure<3>(const std::vector<Point<3> > &all_vertices,
01146                   const unsigned int (&vertex_indices) [GeometryInfo<3>::vertices_per_cell]);
01147 
01148   template <>
01149   double
01150   cell_measure<2>(const std::vector<Point<2> > &all_vertices,
01151                   const unsigned int (&vertex_indices) [GeometryInfo<2>::vertices_per_cell]);
01152 }
01153 
01154 
01155 
01156 DEAL_II_NAMESPACE_CLOSE
01157 
01158 /*----------------------------   grid_tools.h     ---------------------------*/
01159 /* end of #ifndef __deal2__grid_tools_H */
01160 #endif
01161 /*----------------------------   grid_tools.h     ---------------------------*/
01162 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

deal.II documentation generated on Tue May 22 2012 12:06:09 by doxygen 1.7.3