Classes | Public Member Functions | Static Public Member Functions | Friends | List of all members
indexedOctree< Type > Class Template Reference

Non-pointer based hierarchical recursive searching. More...

Inheritance diagram for indexedOctree< Type >:
Inheritance graph
[legend]
Collaboration diagram for indexedOctree< Type >:
Collaboration graph
[legend]

Classes

class  node
 Tree node. Has up pointer and down pointers. More...
 

Public Member Functions

 indexedOctree (const Type &shapes)
 Construct null. More...
 
 indexedOctree (const Type &shapes, const List< node > &nodes, const labelListList &contents)
 Construct from components. More...
 
 indexedOctree (const Type &shapes, const treeBoundBox &bb, const label maxLevels, const scalar maxLeafRatio, const scalar maxDuplicity)
 Construct from shapes. More...
 
 indexedOctree (const Type &shapes, Istream &is)
 Construct from Istream. More...
 
autoPtr< indexedOctree< Type > > clone () const
 Clone. More...
 
const Type & shapes () const
 Reference to shape. More...
 
const List< node > & nodes () const
 List of all nodes. More...
 
const labelListList & contents () const
 List of all contents (referenced by those nodes that are. More...
 
const treeBoundBox & bb () const
 Top bounding box. More...
 
pointIndexHit findNearest (const point &sample, const scalar nearestDistSqr) const
 
template<class FindNearestOp >
pointIndexHit findNearest (const point &sample, const scalar nearestDistSqr, const FindNearestOp &fnOp) const
 Calculate nearest point on nearest shape. More...
 
template<class FindNearestOp >
void findNearest (const label nodeI, const point &, scalar &nearestDistSqr, label &nearestShapeI, point &nearestPoint, const FindNearestOp &fnOp) const
 Low level: calculate nearest starting from subnode. More...
 
pointIndexHit findNearest (const linePointRef &ln, treeBoundBox &tightest, point &linePoint) const
 Find nearest to line. More...
 
template<class FindNearestOp >
pointIndexHit findNearest (const linePointRef &ln, treeBoundBox &tightest, point &linePoint, const FindNearestOp &fnOp) const
 
pointIndexHit findLine (const point &start, const point &end) const
 Find nearest intersection of line between start and end. More...
 
pointIndexHit findLineAny (const point &start, const point &end) const
 Find any intersection of line between start and end. More...
 
template<class FindIntersectOp >
pointIndexHit findLine (const point &start, const point &end, const FindIntersectOp &fiOp) const
 Find nearest intersection of line between start and end. More...
 
template<class FindIntersectOp >
pointIndexHit findLineAny (const point &start, const point &end, const FindIntersectOp &fiOp) const
 Find any intersection of line between start and end. More...
 
labelList findBox (const treeBoundBox &bb) const
 Find (in no particular order) indices of all shapes inside or. More...
 
labelList findSphere (const point &centre, const scalar radiusSqr) const
 Find (in no particular order) indices of all shapes inside or. More...
 
labelBits findNode (const label nodeI, const point &) const
 Find deepest node (as parent+octant) containing point. Starts. More...
 
label findInside (const point &) const
 Find shape containing point. Only implemented for certain. More...
 
const labelList & findIndices (const point &) const
 Find the shape indices that occupy the result of findNode. More...
 
volumeType getVolumeType (const point &) const
 Determine type (inside/outside/mixed) for point. unknown if. More...
 
template<class CompareOp >
void findNear (const scalar nearDist, const indexedOctree< Type > &tree2, CompareOp &cop) const
 Find near pairs and apply CompareOp to them. More...
 
void print (prefixOSstream &, const bool printContents, const label) const
 Print tree. Either print all indices (printContent = true) or. More...
 
bool write (Ostream &os) const
 
template<class FindIntersectOp >
Foam::pointIndexHit findLine (const bool findAny, const point &treeStart, const point &treeEnd, const label startNodeI, const direction startOctant, const FindIntersectOp &fiOp, const bool verbose) const
 
template<class FindIntersectOp >
Foam::pointIndexHit findLine (const bool findAny, const point &start, const point &end, const FindIntersectOp &fiOp) const
 
template<class FindNearestOp >
Foam::pointIndexHit findNearest (const point &sample, const scalar startDistSqr, const FindNearestOp &fnOp) const
 
template<class FindNearestOp >
Foam::pointIndexHit findNearest (const linePointRef &ln, treeBoundBox &tightest, point &linePoint, const FindNearestOp &fnOp) const
 
template<class FindIntersectOp >
Foam::pointIndexHit findLine (const point &start, const point &end, const FindIntersectOp &fiOp) const
 
template<class FindIntersectOp >
Foam::pointIndexHit findLineAny (const point &start, const point &end, const FindIntersectOp &fiOp) const
 

Static Public Member Functions

static scalar & perturbTol ()
 Get the perturbation tolerance. More...
 
static bool isContent (const labelBits i)
 
static bool isEmpty (const labelBits i)
 
static bool isNode (const labelBits i)
 
static label getContent (const labelBits i)
 
static label getNode (const labelBits i)
 
static direction getOctant (const labelBits i)
 
static volumeType getSide (const vector &outsideNormal, const vector &vec)
 Helper function to return the side. Returns outside if. More...
 
static bool overlaps (const point &bbMin, const point &bbMax, const scalar nearestDistSqr, const point &sample)
 Helper: does bb intersect a sphere around sample? Or is any. More...
 

Friends

Ostream & operator (Ostream &, const indexedOctree< Type > &)
 

Detailed Description

template<class Type>
class Foam::indexedOctree< Type >

Non-pointer based hierarchical recursive searching.

Source files

Definition at line 47 of file treeDataEdge.H.

Constructor & Destructor Documentation

indexedOctree ( const Type &  shapes)

Construct null.

Definition at line 2114 of file indexedOctree.C.

Referenced by indexedOctree< Type >::indexedOctree().

Here is the caller graph for this function:

indexedOctree ( const Type &  shapes,
const List< node > &  nodes,
const labelListList &  contents 
)

Construct from components.

Definition at line 2125 of file indexedOctree.C.

References indexedOctree< Type >::indexedOctree().

Here is the call graph for this function:

indexedOctree ( const Type &  shapes,
const treeBoundBox &  bb,
const label  maxLevels,
const scalar  maxLeafRatio,
const scalar  maxDuplicity 
)

Construct from shapes.

Definition at line 2140 of file indexedOctree.C.

References DynamicList< T, SizeInc, SizeMult, SizeDiv >::append(), indexedOctree< Type >::bb(), DynamicList< T, SizeInc, SizeMult, SizeDiv >::clear(), indexedOctree< Type >::contents(), Foam::endl(), forAll, Foam::identity(), indexedOctree< Type >::indexedOctree(), Foam::nl, indexedOctree< Type >::nodes(), Foam::Pout, List< T >::setSize(), DynamicList< T, SizeInc, SizeMult, SizeDiv >::shrink(), List< T >::size(), and memInfo::size().

Here is the call graph for this function:

indexedOctree ( const Type &  shapes,
Istream &  is 
)

Construct from Istream.

Definition at line 2304 of file indexedOctree.C.

Member Function Documentation

Foam::scalar & perturbTol ( )
static

Get the perturbation tolerance.

Definition at line 2319 of file indexedOctree.C.

Referenced by triSurfaceMesh::edgeTree(), triSurfaceSearch::findLine(), triSurfaceSearch::findLineAll(), triSurfaceSearch::findLineAny(), triSurfaceRegionSearch::findNearest(), triSurfaceSearch::findNearest(), triSurfaceMesh::getVolumeType(), triSurfaceSearch::tree(), and triSurfaceRegionSearch::treeByRegion().

Here is the caller graph for this function:

autoPtr<indexedOctree<Type> > clone ( ) const
inline

Clone.

Definition at line 432 of file indexedOctree.H.

const Type& shapes ( ) const
inline

Reference to shape.

Definition at line 445 of file indexedOctree.H.

Referenced by polyMesh::findCellFacePt(), patchProbes::findElements(), indexedOctree< Type >::findLine(), meshSearch::findNearestBoundaryFace(), refinementFeatures::findNearestEdge(), refinementFeatures::findNearestPoint(), refinementFeatures::findNearestRegionEdge(), surfaceFeatures::nearestEdges(), listPlusEqOp< T >::operator()(), and nearestEqOp::operator()().

Here is the caller graph for this function:

const List<node>& nodes ( ) const
inline

List of all nodes.

Definition at line 451 of file indexedOctree.H.

Referenced by indexedOctree< Type >::findLine(), and indexedOctree< Type >::indexedOctree().

Here is the caller graph for this function:

const labelListList& contents ( ) const
inline

List of all contents (referenced by those nodes that are.

contents)

Definition at line 458 of file indexedOctree.H.

Referenced by indexedOctree< Type >::findLine(), indexedOctree< Type >::indexedOctree(), and indexedOctree< Foam::treeDataFace >::nodes().

Here is the caller graph for this function:

const treeBoundBox& bb ( ) const
inline

Top bounding box.

Definition at line 464 of file indexedOctree.H.

Referenced by patchProbes::findElements(), indexedOctree< Type >::findNear(), meshSearch::findNearestBoundaryFace(), indexedOctree< Type >::getVolumeType(), indexedOctree< Type >::indexedOctree(), surfaceFeatures::nearestSamples(), and nearestEqOp::operator()().

Here is the caller graph for this function:

static bool isContent ( const labelBits  i)
inlinestatic

Definition at line 477 of file indexedOctree.H.

Referenced by indexedOctree< Type >::findIndices(), indexedOctree< Type >::findInside(), indexedOctree< Type >::findLine(), indexedOctree< Type >::findNode(), indexedOctree< Foam::treeDataFace >::getContent(), and indexedOctree< Type >::print().

Here is the caller graph for this function:

static bool isEmpty ( const labelBits  i)
inlinestatic

Definition at line 482 of file indexedOctree.H.

static bool isNode ( const labelBits  i)
inlinestatic

Definition at line 487 of file indexedOctree.H.

Referenced by indexedOctree< Type >::findLine(), indexedOctree< Type >::findNode(), indexedOctree< Foam::treeDataFace >::getNode(), and indexedOctree< Type >::print().

Here is the caller graph for this function:

static label getContent ( const labelBits  i)
inlinestatic

Definition at line 492 of file indexedOctree.H.

Referenced by indexedOctree< Type >::findIndices(), indexedOctree< Type >::findInside(), indexedOctree< Type >::findLine(), and indexedOctree< Type >::print().

Here is the caller graph for this function:

static label getNode ( const labelBits  i)
inlinestatic

Definition at line 502 of file indexedOctree.H.

Referenced by indexedOctree< Type >::findIndices(), indexedOctree< Type >::findInside(), indexedOctree< Type >::findLine(), indexedOctree< Type >::findNode(), and indexedOctree< Type >::print().

Here is the caller graph for this function:

static direction getOctant ( const labelBits  i)
inlinestatic

Definition at line 512 of file indexedOctree.H.

Referenced by indexedOctree< Type >::findIndices(), and indexedOctree< Type >::findInside().

Here is the caller graph for this function:

Foam::pointIndexHit findNearest ( const point &  sample,
const scalar  nearestDistSqr 
) const

Definition at line 2327 of file indexedOctree.C.

pointIndexHit findNearest ( const point &  sample,
const scalar  nearestDistSqr,
const FindNearestOp &  fnOp 
) const

Calculate nearest point on nearest shape.

Returns

  • bool : any point found nearer than nearestDistSqr
  • label: index in shapes
  • point: actual nearest point found
void findNearest ( const label  nodeI,
const point &  sample,
scalar &  nearestDistSqr,
label &  nearestShapeI,
point &  nearestPoint,
const FindNearestOp &  fnOp 
) const

Low level: calculate nearest starting from subnode.

Definition at line 490 of file indexedOctree.C.

References Foam::abort(), indexedOctree< Type >::node::bb_, line< Point, PointRef >::centre(), treeBoundBox::contains(), Foam::endl(), treeBoundBox::faceBits(), Foam::facePoint(), Foam::FatalError, FatalErrorInFunction, forAll, PointIndexHit< Point >::hit(), treeBoundBox::intersects(), Foam::ln(), Foam::mag(), boundBox::max(), boundBox::min(), boundBox::overlaps(), treeBoundBox::posBits(), s(), treeBoundBox::searchOrder(), PointIndexHit< Point >::setHit(), PointIndexHit< Point >::setIndex(), PointIndexHit< Point >::setPoint(), List< T >::size(), boundBox::span(), treeBoundBox::subBbox(), indexedOctree< Type >::node::subNodes_, Vector< Cmpt >::x(), Y, Vector< Cmpt >::y(), and Vector< Cmpt >::z().

Here is the call graph for this function:

Foam::pointIndexHit findNearest ( const linePointRef &  ln,
treeBoundBox &  tightest,
point &  linePoint 
) const

Find nearest to line.

Returns

  • bool : any point found?
  • label: index in shapes
  • point: actual nearest point found sets:
  • linePoint : corresponding nearest point on line

Definition at line 2376 of file indexedOctree.C.

pointIndexHit findNearest ( const linePointRef &  ln,
treeBoundBox &  tightest,
point &  linePoint,
const FindNearestOp &  fnOp 
) const
Foam::pointIndexHit findLine ( const point &  start,
const point &  end 
) const

Find nearest intersection of line between start and end.

Definition at line 2428 of file indexedOctree.C.

References indexedOctree< Type >::findLineAny().

Here is the call graph for this function:

Foam::pointIndexHit findLineAny ( const point &  start,
const point &  end 
) const

Find any intersection of line between start and end.

Definition at line 2445 of file indexedOctree.C.

Referenced by indexedOctree< Type >::findLine(), triSurfaceSearch::findLineAny(), indexedOctree< Foam::treeDataFace >::getOctant(), and NamedEnum< Enum, nEnum >::names().

Here is the caller graph for this function:

pointIndexHit findLine ( const point &  start,
const point &  end,
const FindIntersectOp &  fiOp 
) const

Find nearest intersection of line between start and end.

pointIndexHit findLineAny ( const point &  start,
const point &  end,
const FindIntersectOp &  fiOp 
) const

Find any intersection of line between start and end.

Foam::labelList findBox ( const treeBoundBox &  bb) const

Find (in no particular order) indices of all shapes inside or.

overlapping bounding box (i.e. all shapes not outside box)

Definition at line 2488 of file indexedOctree.C.

References HashTable< T, Key, Hash >::toc().

Here is the call graph for this function:

Foam::labelList findSphere ( const point &  centre,
const scalar  radiusSqr 
) const

Find (in no particular order) indices of all shapes inside or.

overlapping a bounding sphere (i.e. all shapes not outside sphere)

Definition at line 2506 of file indexedOctree.C.

References indexedOctree< Type >::findNode(), and HashTable< T, Key, Hash >::toc().

Here is the call graph for this function:

Foam::labelBits findNode ( const label  nodeI,
const point &  sample 
) const

Find deepest node (as parent+octant) containing point. Starts.

off from starting index in nodes_ (use 0 to start from top) Use getNode and getOctant to extract info, or call findIndices.

Definition at line 2525 of file indexedOctree.C.

References Foam::abort(), indexedOctree< Type >::node::bb_, treeBoundBox::contains(), Foam::FatalError, FatalErrorInFunction, indexedOctree< Type >::getNode(), indexedOctree< Type >::isContent(), indexedOctree< Type >::isNode(), indexedOctree< Type >::node::subNodes_, and treeBoundBox::subOctant().

Referenced by indexedOctree< Type >::findIndices(), indexedOctree< Type >::findInside(), indexedOctree< Type >::findSphere(), and indexedOctree< Foam::treeDataFace >::getOctant().

Here is the call graph for this function:

Here is the caller graph for this function:

Foam::label findInside ( const point &  sample) const

Find shape containing point. Only implemented for certain.

shapes.

Definition at line 2571 of file indexedOctree.C.

References indexedOctree< Type >::findIndices(), indexedOctree< Type >::findNode(), forAll, indexedOctree< Type >::getContent(), indexedOctree< Type >::getNode(), indexedOctree< Type >::getOctant(), indexedOctree< Type >::isContent(), and indexedOctree< Type >::node::subNodes_.

Referenced by mappedPatchBase::findSamples(), indexedOctree< Foam::treeDataFace >::getOctant(), and nearestEqOp::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

const Foam::labelList & findIndices ( const point &  sample) const

Find the shape indices that occupy the result of findNode.

Definition at line 2601 of file indexedOctree.C.

References indexedOctree< Type >::findNode(), indexedOctree< Type >::getContent(), indexedOctree< Type >::getNode(), indexedOctree< Type >::getOctant(), indexedOctree< Type >::isContent(), and indexedOctree< Type >::node::subNodes_.

Referenced by polyMesh::findCellFacePt(), indexedOctree< Type >::findInside(), and indexedOctree< Foam::treeDataFace >::getOctant().

Here is the call graph for this function:

Here is the caller graph for this function:

Foam::volumeType getVolumeType ( const point &  sample) const

Determine type (inside/outside/mixed) for point. unknown if.

cannot be determined (e.g. non-manifold surface)

Definition at line 2625 of file indexedOctree.C.

References Foam::abort(), indexedOctree< Type >::bb(), Foam::endl(), Foam::FatalError, FatalErrorInFunction, forAll, PackedList< nBits >::get(), volumeType::INSIDE, volumeType::MIXED, volumeType::OUTSIDE, Foam::Pout, PackedList< nBits >::setSize(), PackedList< nBits >::size(), Foam::type(), and volumeType::UNKNOWN.

Here is the call graph for this function:

Foam::volumeType getSide ( const vector &  outsideNormal,
const vector &  vec 
)
static

Helper function to return the side. Returns outside if.

outsideNormal&vec >= 0, inside otherwise

Definition at line 471 of file indexedOctree.C.

Referenced by indexedOctree< Foam::treeDataFace >::getOctant(), treeDataFace::getVolumeType(), and indexedOctree< Type >::overlaps().

Here is the caller graph for this function:

bool overlaps ( const point &  bbMin,
const point &  bbMax,
const scalar  nearestDistSqr,
const point &  sample 
)
static

Helper: does bb intersect a sphere around sample? Or is any.

corner point of bb closer than nearestDistSqr to sample.

Definition at line 42 of file indexedOctree.C.

References Foam::abort(), List< T >::append(), DynamicList< T, SizeInc, SizeMult, SizeDiv >::append(), indexedOctree< Type >::node::bb_, Foam::divide(), Foam::FatalError, FatalErrorInFunction, forAll, indexedOctree< Type >::getSide(), boundBox::max(), Foam::max(), boundBox::midpoint(), boundBox::min(), Foam::min(), Foam::nl, boundBox::overlaps(), indexedOctree< Type >::node::parent_, List< T >::setSize(), List< T >::size(), FixedList< T, Size >::size(), treeBoundBox::subBbox(), indexedOctree< Type >::node::subNodes_, treeBoundBox::subOctant(), DynamicList< T, SizeInc, SizeMult, SizeDiv >::transfer(), List< T >::transfer(), Foam::type(), Vector< Cmpt >::x(), Vector< Cmpt >::y(), and Vector< Cmpt >::z().

Here is the call graph for this function:

void findNear ( const scalar  nearDist,
const indexedOctree< Type > &  tree2,
CompareOp &  cop 
) const

Find near pairs and apply CompareOp to them.

tree2 can be *this or different tree.

Definition at line 2695 of file indexedOctree.C.

References indexedOctree< Type >::bb(), and indexedOctree< Type >::print().

Here is the call graph for this function:

void print ( prefixOSstream &  os,
const bool  printContents,
const label  nodeI 
) const

Print tree. Either print all indices (printContent = true) or.

just size of contents nodes.

Definition at line 2718 of file indexedOctree.C.

References indexedOctree< Type >::node::bb_, Foam::endl(), forAll, indexedOctree< Type >::getContent(), indexedOctree< Type >::getNode(), indexedOctree< Type >::isContent(), indexedOctree< Type >::isNode(), Foam::nl, indexedOctree< Type >::node::parent_, prefixOSstream::prefix(), List< T >::size(), treeBoundBox::subBbox(), and indexedOctree< Type >::node::subNodes_.

Referenced by indexedOctree< Type >::findNear(), and indexedOctree< Foam::treeDataFace >::getOctant().

Here is the call graph for this function:

Here is the caller graph for this function:

bool write ( Ostream &  os) const

Definition at line 2790 of file indexedOctree.C.

References IOstream::good(), and token::SPACE.

Referenced by indexedOctree< Foam::treeDataFace >::getOctant().

Here is the call graph for this function:

Here is the caller graph for this function:

Foam::pointIndexHit findLine ( const bool  findAny,
const point &  treeStart,
const point &  treeEnd,
const label  startNodeI,
const direction  startOctant,
const FindIntersectOp &  fiOp,
const bool  verbose 
) const

Definition at line 1499 of file indexedOctree.C.

References Foam::abort(), Foam::endl(), treeBoundBox::faceBits(), Foam::FatalError, FatalErrorInFunction, PointIndexHit< Point >::hit(), Foam::nl, Foam::Pout, PointIndexHit< Point >::rawPoint(), and WarningInFunction.

Here is the call graph for this function:

Foam::pointIndexHit findLine ( const bool  findAny,
const point &  start,
const point &  end,
const FindIntersectOp &  fiOp 
) const

Definition at line 1691 of file indexedOctree.C.

References indexedOctree< Type >::node::bb_, indexedOctree< Type >::contents(), Foam::constant::electromagnetic::e, Foam::endl(), forAll, indexedOctree< Type >::getContent(), indexedOctree< Type >::getNode(), HashSet< Key, Hash >::insert(), treeBoundBox::intersects(), indexedOctree< Type >::isContent(), indexedOctree< Type >::isNode(), boundBox::max(), boundBox::min(), OFstream::name(), Foam::name(), Foam::nl, indexedOctree< Type >::nodes(), boundBox::overlaps(), treeBoundBox::points(), treeBoundBox::posBits(), Foam::Pout, indexedOctree< Type >::shapes(), treeBoundBox::subBbox(), indexedOctree< Type >::node::subNodes_, Vector< Cmpt >::x(), Vector< Cmpt >::y(), Vector< Cmpt >::z(), and Foam::Zero.

Here is the call graph for this function:

Foam::pointIndexHit findNearest ( const point &  sample,
const scalar  startDistSqr,
const FindNearestOp &  fnOp 
) const

Definition at line 2344 of file indexedOctree.C.

References Foam::Zero.

Foam::pointIndexHit findNearest ( const linePointRef &  ln,
treeBoundBox &  tightest,
point &  linePoint,
const FindNearestOp &  fnOp 
) const

Definition at line 2395 of file indexedOctree.C.

References Foam::Zero.

Foam::pointIndexHit findLine ( const point &  start,
const point &  end,
const FindIntersectOp &  fiOp 
) const

Definition at line 2463 of file indexedOctree.C.

References indexedOctree< Type >::findLineAny().

Here is the call graph for this function:

Foam::pointIndexHit findLineAny ( const point &  start,
const point &  end,
const FindIntersectOp &  fiOp 
) const

Definition at line 2476 of file indexedOctree.C.

Friends And Related Function Documentation

Ostream& operator ( Ostream &  ,
const indexedOctree< Type > &   
)
friend
The documentation for this class was generated from the following files:
Generated by   doxygen 1.8.11