Cell-neighbor-search Algorithm

Declaration

[1] template<class NBF, class CELLRANGE>
    void CalculateNeighborCells
          (NBF             &  Nb,   // out
           CELLRANGE  const&  C);   // in

[2] template<class NBF, class CELLRANGE, class FACETMAP>
    void CalculateNeighborCells
          (NBF             &  Nb,   // out
           CELLRANGE  const&  C,    // in
           FACETMAP        &  F);   // inout

[3] template<class NBF, class CELLRANGE, class FACETMAP, class CGT>
    void CalculateNeighborCells
         (NBF             &  Nb,    // out
          CELLRANGE  const&  C,     // in
          FACETMAP        &  F,     // inout
          CGT        const&);       // in (only type used) 

Description

CalculateNeighborRange (versions [2], [3]) can be used incrementally in the variable C: If C = C₁ U ... U C_n is a partition of a given cell set, then calling CalculateNeighborRange with the cell set C is equivalent to the successive calls with cell sets C₁, ..., C_n. (The remaining arguments stay identical.)

Definition

Requirements on types

• CELLRANGE, CGT:
  CELLRANGE is a model of CellGridRange.

  The following types must be published by the type CGT (version [3]) or the template grid_types<CELLSET> (versions [1], [2]):

  • Cell: a model of Grid Cell and Facet Grid Range
  • FacetOnCellIterator: a model of Facet-On-Cell Iterator.
  • Facet: a model of Grid Facet and of Vertex Grid Range
  • Vertex: a model of Grid Vertex.

  In the following, we use CGT also for grid_types<CELLSET> in versions [1], [2].

• NBF
  is a model of Mutable Mapping from CGT::FacetOnCellIterator to CGT::cell_handle.
• FACETMAP
  is a model of Mutable Mapping from vtuple<CGT::grid_type> to CGT::FacetOnCellIterator. In addition, the following expressions must be defined: (Here i is of type FACETMAP::iterator, f is of type CGT::FacetOnCellIterator, and F is of type FACETMAP. )
  • type iterator
  • i = F.end();
  • i = F.find(f);
  • F.erase(i);
  This is for example fullfilled if FACETMAP is a model of STL Pair Associative Container.

Notation

Preconditions

D n I = Ø

Postconditions

After the call, F contains exactly the boundary facets, except those that have been in it before (versions [2], [3]). In version [1], the value of Nb is set to an invalid cell handle for boundary facets (that is, facets which have been visited by only facet-on-cell iterator).

D^`= (D  \ B) U (B  \ D)

Complexity

Example

#include "Grids/Algorithms/cell-neighbor-search.h"

Triang2D t;
typedef grid_types<Triang2D> gt;
...
hash_map<gt::FacetOnCellIterator> , gt::cell_handle> Nbs;
CalculateNeighborCells(nbf,T);

for(gt::CellIterator c(t); ! c.IsDone(); ++c) 
  for(gt::FacetOnCellIterator fc(c); ! fc.IsDone(); ++fc)
    out << nbf[fc] << ' ';
  out << 'n';

Known Uses

Useqd in test file test-triang2d-construct.C for Triang2D.

Notes

See also