dune-grid  2.4.1
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::template Codim<0>::EntityPointer EntityPointer;
48 
50  typedef typename Grid::HierarchicIterator HierarchicIterator;
51 
52  static std::string formatEntityInformation ( const Entity &e ) {
53  const typename Entity::Geometry &geo = e.geometry();
54  std::ostringstream info;
55  info << "level=" << e.level() << " "
56  << "partition=" << e.partitionType() << " "
57  << "center=(" << geo.center() << ") "
58  << "corners=[(" << geo.corner(0) << ")";
59  for(int i = 1; i < geo.corners(); ++i)
60  info << " (" << e.geometry().corner(i) << ")";
61  info << "]";
62  return info.str();
63  }
64 
75  Entity hFindEntity ( const Entity &entity,
76  const FieldVector<ct,dimw>& global) const
77  {
78  // type of element geometry
79  typedef typename Entity::Geometry Geometry;
80  // type of local coordinate
81  typedef typename Geometry::LocalCoordinate LocalCoordinate;
82 
83  const int childLevel = entity.level()+1 ;
84  // loop over all child Entities
85  const HierarchicIterator end = entity.hend( childLevel );
86  for( HierarchicIterator it = entity.hbegin( childLevel ); it != end; ++it )
87  {
88  Entity child = *it;
89  const Geometry &geo = child.geometry();
90 
91  LocalCoordinate local = geo.local(global);
92  if (ReferenceElements<double, dim>::general( child.type() ).checkInside(local))
93  {
94  // return if we found the leaf, else search through the child entites
95  if( indexSet_.contains( child ) )
96  return std::move( child );
97  else
98  return hFindEntity( child, global );
99  }
100  }
101  std::ostringstream children;
102  HierarchicIterator it = entity.hbegin( childLevel );
103  if(it != end) {
104  children << "{" << formatEntityInformation(*it) << "}";
105  for( ++it; it != end; ++it )
106  children << " {" << formatEntityInformation(*it) << "}";
107  }
108  DUNE_THROW(Exception, "{" << className(*this) << "} Unexpected "
109  "internal Error: none of the children of the entity "
110  "{" << formatEntityInformation(entity) << "} contains "
111  "coordinate (" << global << "). Children are: "
112  "[" << children.str() << "].");
113  }
114 
115  public:
119  HierarchicSearch(const Grid & g, const IS & is) : grid_(g), indexSet_(is) {}
120 
128  Entity findEntity(const FieldVector<ct,dimw>& global) const
129  { return findEntity<All_Partition>(global); }
130 
138  template<PartitionIteratorType partition>
139  Entity findEntity(const FieldVector<ct,dimw>& global) const
140  {
141  typedef typename Grid::LevelGridView LevelGV;
142  const LevelGV &gv = grid_.template levelGridView(0);
143 
145  typedef typename LevelGV::template Codim<0>::template Partition<partition>::Iterator LevelIterator;
146 
147  // type of element geometry
148  typedef typename Entity::Geometry Geometry;
149  // type of local coordinate
150  typedef typename Geometry::LocalCoordinate LocalCoordinate;
151 
152  // loop over macro level
153  const LevelIterator end = gv.template end<0, partition>();
154  for (LevelIterator it = gv.template begin<0, partition>(); it != end; ++it)
155  {
156  Entity entity = *it;
157  const Geometry &geo = entity.geometry();
158 
159  LocalCoordinate local = geo.local( global );
160  if( !ReferenceElements< double, dim >::general( geo.type() ).checkInside( local ) )
161  continue;
162 
163  if( (int(dim) != int(dimw)) && ((geo.global( local ) - global).two_norm() > 1e-8) )
164  continue;
165 
166  // return if we found the leaf, else search through the child entites
167  if( indexSet_.contains( entity ) )
168  return std::move( entity );
169  else
170  return hFindEntity( entity, global );
171  }
172  DUNE_THROW( GridError, "Coordinate " << global << " is outside the grid." );
173  }
174 
175  private:
176  const Grid& grid_;
177  const IS& indexSet_;
178  };
179 
180 } // end namespace Dune
181 
182 #endif // DUNE_GRID_HIERARCHICSEARCH_HH
GridImp::template Codim< cd >::Geometry Geometry
The corresponding geometry type.
Definition: common/entity.hh:97
LocalCoordinate local(const GlobalCoordinate &global) const
Evaluate the inverse map .
Definition: common/geometry.hh:174
Base class for exceptions in Dune grid modules.
Definition: exceptions.hh:16
Wrapper class for geometries.
Definition: common/geometry.hh:65
Entity findEntity(const FieldVector< ct, dimw > &global) const
Search the IndexSet of this HierarchicSearch for an Entity containing point global.
Definition: hierarchicsearch.hh:139
FieldVector< ctype, mydim > LocalCoordinate
type of local coordinates
Definition: common/geometry.hh:101
GlobalCoordinate global(const LocalCoordinate &local) const
Evaluate the map .
Definition: common/geometry.hh:165
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:512
The dimension of the world the grid lives in.
Definition: common/grid.hh:408
Partition< All_Partition >::LevelGridView LevelGridView
View types for All_Partition.
Definition: common/grid.hh:428
static void(*)(*)(*)(*)(*)(*) move(const double *)
Definition: partitiondisplay.cc:122
GeometryType type() const
Return the name of the reference element. The type can be used to access the Dune::ReferenceElement.
Definition: common/geometry.hh:131
ct ctype
Define type used for coordinates in grid module.
Definition: common/grid.hh:548
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:388
Include standard header files.
Definition: agrid.hh:59
Definition: grapecommon.hh:49
Different resources needed by all grid implementations.
Entity findEntity(const FieldVector< ct, dimw > &global) const
Search the IndexSet of this HierarchicSearch for an Entity containing point global.
Definition: hierarchicsearch.hh:128
HierarchicSearch(const Grid &g, const IS &is)
Construct a HierarchicSearch object from a Grid and an IndexSet.
Definition: hierarchicsearch.hh:119
Search an IndexSet for an Entity containing a given point.
Definition: hierarchicsearch.hh:32
The dimension of the grid.
Definition: common/grid.hh:402