dune-grid  2.5.0
hierarchicsearch.hh
Go to the documentation of this file.
1 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 // vi: set et ts=4 sw=2 sts=2:
3 
4 #ifndef DUNE_GRID_HIERARCHICSEARCH_HH
5 #define DUNE_GRID_HIERARCHICSEARCH_HH
6 
13 #include <cstddef>
14 #include <sstream>
15 #include <string>
16 #include <utility>
17 
18 #include <dune/common/classname.hh>
19 #include <dune/common/exceptions.hh>
20 #include <dune/common/fvector.hh>
21 
22 #include <dune/grid/common/grid.hh>
24 
25 namespace Dune
26 {
27 
31  template<class Grid, class IS>
33  {
35  enum {dim=Grid::dimension};
36 
38  enum {dimw=Grid::dimensionworld};
39 
41  typedef typename Grid::ctype ct;
42 
44  typedef typename Grid::template Codim<0>::Entity Entity;
45 
47  typedef typename Grid::HierarchicIterator HierarchicIterator;
48 
49  static std::string formatEntityInformation ( const Entity &e ) {
50  const typename Entity::Geometry &geo = e.geometry();
51  std::ostringstream info;
52  info << "level=" << e.level() << " "
53  << "partition=" << e.partitionType() << " "
54  << "center=(" << geo.center() << ") "
55  << "corners=[(" << geo.corner(0) << ")";
56  for(int i = 1; i < geo.corners(); ++i)
57  info << " (" << e.geometry().corner(i) << ")";
58  info << "]";
59  return info.str();
60  }
61 
72  Entity hFindEntity ( const Entity &entity,
73  const FieldVector<ct,dimw>& global) const
74  {
75  // type of element geometry
76  typedef typename Entity::Geometry Geometry;
77  // type of local coordinate
78  typedef typename Geometry::LocalCoordinate LocalCoordinate;
79 
80  const int childLevel = entity.level()+1 ;
81  // loop over all child Entities
82  const HierarchicIterator end = entity.hend( childLevel );
83  for( HierarchicIterator it = entity.hbegin( childLevel ); it != end; ++it )
84  {
85  Entity child = *it;
86  const Geometry &geo = child.geometry();
87 
88  LocalCoordinate local = geo.local(global);
89  if (ReferenceElements<double, dim>::general( child.type() ).checkInside(local))
90  {
91  // return if we found the leaf, else search through the child entites
92  if( indexSet_.contains( child ) )
93  return std::move( child );
94  else
95  return hFindEntity( child, global );
96  }
97  }
98  std::ostringstream children;
99  HierarchicIterator it = entity.hbegin( childLevel );
100  if(it != end) {
101  children << "{" << formatEntityInformation(*it) << "}";
102  for( ++it; it != end; ++it )
103  children << " {" << formatEntityInformation(*it) << "}";
104  }
105  DUNE_THROW(Exception, "{" << className(*this) << "} Unexpected "
106  "internal Error: none of the children of the entity "
107  "{" << formatEntityInformation(entity) << "} contains "
108  "coordinate (" << global << "). Children are: "
109  "[" << children.str() << "].");
110  }
111 
112  public:
116  HierarchicSearch(const Grid & g, const IS & is) : grid_(g), indexSet_(is) {}
117 
125  Entity findEntity(const FieldVector<ct,dimw>& global) const
126  { return findEntity<All_Partition>(global); }
127 
135  template<PartitionIteratorType partition>
136  Entity findEntity(const FieldVector<ct,dimw>& global) const
137  {
138  typedef typename Grid::LevelGridView LevelGV;
139  const LevelGV &gv = grid_.levelGridView(0);
140 
142  typedef typename LevelGV::template Codim<0>::template Partition<partition>::Iterator LevelIterator;
143 
144  // type of element geometry
145  typedef typename Entity::Geometry Geometry;
146  // type of local coordinate
147  typedef typename Geometry::LocalCoordinate LocalCoordinate;
148 
149  // loop over macro level
150  const LevelIterator end = gv.template end<0, partition>();
151  for (LevelIterator it = gv.template begin<0, partition>(); it != end; ++it)
152  {
153  Entity entity = *it;
154  const Geometry &geo = entity.geometry();
155 
156  LocalCoordinate local = geo.local( global );
157  if( !ReferenceElements< double, dim >::general( geo.type() ).checkInside( local ) )
158  continue;
159 
160  if( (int(dim) != int(dimw)) && ((geo.global( local ) - global).two_norm() > 1e-8) )
161  continue;
162 
163  // return if we found the leaf, else search through the child entites
164  if( indexSet_.contains( entity ) )
165  return std::move( entity );
166  else
167  return hFindEntity( entity, global );
168  }
169  DUNE_THROW( GridError, "Coordinate " << global << " is outside the grid." );
170  }
171 
172  private:
173  const Grid& grid_;
174  const IS& indexSet_;
175  };
176 
177 } // end namespace Dune
178 
179 #endif // DUNE_GRID_HIERARCHICSEARCH_HH
ct ctype
Define type used for coordinates in grid module.
Definition: common/grid.hh:522
Base class for exceptions in Dune grid modules.
Definition: exceptions.hh:16
Entity findEntity(const FieldVector< ct, dimw > &global) const
Search the IndexSet of this HierarchicSearch for an Entity containing point global.
Definition: hierarchicsearch.hh:125
HierarchicSearch(const Grid &g, const IS &is)
Construct a HierarchicSearch object from a Grid and an IndexSet.
Definition: hierarchicsearch.hh:116
GeometryType type() const
Return the type of the reference element. The type can be used to access the Dune::ReferenceElement.
Definition: common/geometry.hh:123
GridFamily::Traits::LevelGridView LevelGridView
type of view for level grid
Definition: common/grid.hh:406
LocalCoordinate local(const GlobalCoordinate &global) const
Evaluate the inverse map .
Definition: common/geometry.hh:166
LevelGridView levelGridView(int level) const
View for a grid level for All_Partition.
Definition: common/grid.hh:588
Include standard header files.
Definition: agrid.hh:59
GlobalCoordinate global(const LocalCoordinate &local) const
Evaluate the map .
Definition: common/geometry.hh:157
Wrapper class for geometries.
Definition: common/geometry.hh:65
GridFamily::Traits::HierarchicIterator HierarchicIterator
A type that is a model of Dune::HierarchicIterator A type of iterator that allows to examine...
Definition: common/grid.hh:486
Search an IndexSet for an Entity containing a given point.
Definition: hierarchicsearch.hh:32
Entity findEntity(const FieldVector< ct, dimw > &global) const
Search the IndexSet of this HierarchicSearch for an Entity containing point global.
Definition: hierarchicsearch.hh:136
FieldVector< ctype, mydim > LocalCoordinate
type of local coordinates
Definition: common/geometry.hh:93
GridImp::template Codim< cd >::Geometry Geometry
The corresponding geometry type.
Definition: common/entity.hh:100
Different resources needed by all grid implementations.
The dimension of the grid.
Definition: common/grid.hh:387
Grid abstract base classThis class is the base class for all grid implementations. Although no virtual functions are used we call it abstract since its methods do not contain an implementation but forward to the methods of the derived class via the Barton-Nackman trick.
Definition: common/grid.hh:373
The dimension of the world the grid lives in.
Definition: common/grid.hh:393