Up Next
Go up to Grid algorithms
Go forward to Count boundary components Algorithm

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 takes a range of cells C and determines the neighbor relation on its cells. (Two cells are neighbors if they share a facet.) The output is stored in nb.

CalculateNeighborRange (versions [2], [3]) can be used incrementally in the variable C: If C = C1 U ... U Cn 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 C1, ..., Cn. (The remaining arguments stay identical.)

Definition
CalculateNeighborRange is defined in cell-neighbor-search.h
Requirements on types
Notation
F is the set of facets of C.
I the set of interior facets of C.
B the boundary facets of C (such that I U B = F).
D is the domain of the map F before the call.
D` is the domain of the map F after the call.
Preconditions
The grid underlying C is a subgrid of a manifold-with-boundary complex.
For versions [2] and [3], the domain of the map F may already contain facets, but these must be boundary facets:
D n I = Ø
Postconditions
All pairs of cells sharing an interior facets in I have been found, as well as all cells having a Facet such that the corresponding vertex set has been in D.

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)
It follows that D` n I = Ø.
Complexity
Expected time O(F).
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';

The mapping from gt::FacetOnCellIterator to gt::cell_handle can of course be done much more efficiently than with a hash table, see the example in test-triang2d-construct.C.
Known Uses

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

Notes
See also

Guntram Berti

Up Next