BoundingBoxTree.h

// Copyright (C) 2013 Anders Logg
//
// This file is part of DOLFIN.
//
// DOLFIN is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// DOLFIN is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with DOLFIN. If not, see <http://www.gnu.org/licenses/>.
//
// First added:  2013-04-09
// Last changed: 2014-05-12

#ifndef __BOUNDING_BOX_TREE_H
#define __BOUNDING_BOX_TREE_H

#include <limits>
#include <vector>
#include <memory>

namespace dolfin
{

  // Forward declarations
  class Point;
  class GenericBoundingBoxTree;
  class Mesh;


  class BoundingBoxTree
  {
  public:

    BoundingBoxTree();

    ~BoundingBoxTree();

    void build(const Mesh& mesh);

    void build(const Mesh& mesh, std::size_t tdim);

    void build(const std::vector<Point>& points, std::size_t gdim);

    std::vector<unsigned int>
    compute_collisions(const Point& point) const;

    std::pair<std::vector<unsigned int>, std::vector<unsigned int> >
    compute_collisions(const BoundingBoxTree& tree) const;

    std::vector<unsigned int>
    compute_entity_collisions(const Point& point) const;

    std::vector<unsigned int>
    compute_process_collisions(const Point& point) const;

    std::pair<std::vector<unsigned int>, std::vector<unsigned int> >
    compute_entity_collisions(const BoundingBoxTree& tree) const;

    unsigned int
    compute_first_collision(const Point& point) const;

    unsigned int
    compute_first_entity_collision(const Point& point) const;

    std::pair<unsigned int, double>
    compute_closest_entity(const Point& point) const;

    std::pair<unsigned int, double>
    compute_closest_point(const Point& point) const;

    bool collides(const Point& point) const;

    bool collides_entity(const Point& point) const;

  private:

    // Check that tree has been built
    void _check_built() const;

    // Dimension-dependent implementation
    std::shared_ptr<GenericBoundingBoxTree> _tree;

    // Pointer to the mesh. We all know that we don't really want
    // to store a pointer to the mesh here, but without it we will
    // be forced to make calls like
    // tree_A.compute_entity_intersections(tree_B, mesh_A, mesh_B).
    const Mesh* _mesh;

  };

}

#endif