tree.h

Go to the documentation of this file.

//    |  /           |
//    ' /   __| _` | __|  _ \   __|
//    . \  |   (   | |   (   |\__ `
//   _|\_\_|  \__,_|\__|\___/ ____/
//                   Multi-Physics
//
//  License:         BSD License
//                   Kratos default license: kratos/license.txt
//
//  Main authors:    klabra
//
 
#pragma once
 
// System includes
#include <string>
#include <iostream>
#include <cmath>
#include <type_traits>
 
// External includes
 
// Project includes
#include "search_structure.h"
#include "geometries/bounding_box.h"
#include "utilities/parallel_utilities.h"
 
namespace Kratos
{
 
 
 
 
 
 
template<
std::size_t TDimension,
    class TPointType,
    class TPointerType,
    class TIteratorType,
    class TDistanceIteratorType,
    class TIteratorIteratorType = typename std::vector<TIteratorType>::iterator
    >
class TreeNode
{
public:
 
 
    KRATOS_CLASS_POINTER_DEFINITION(TreeNode);
 
    using SizeType = std::size_t;
 
    using IndexType = std::size_t;
 
    using CoordinateType = double;
 
    using PointType = TPointType;
 
    using PointerType = TPointerType;
 
    using IteratorType = TIteratorType;
 
    using DistanceIteratorType = TDistanceIteratorType;
 
    using TreeNodeType = TreeNode<TDimension, TPointType, TPointerType, TIteratorType, TDistanceIteratorType>;
 
    using IteratorIteratorType = typename std::vector<IteratorType>::iterator;
 
    using SearchStructureType = SearchStructure<IndexType, SizeType, CoordinateType, TIteratorType, IteratorIteratorType, TDimension>;
 
    virtual void PrintData(std::ostream& rOStream, std::string const& Perfix = std::string()) const {}
 
    TreeNode() {}
 
    virtual ~TreeNode() {}
 
    virtual void SearchNearestPoint(PointType const& ThisPoint, PointerType& rResult, CoordinateType& rResultDistance) {}
 
    virtual void SearchNearestPoint(PointType const& ThisPoint, PointerType& rResult, CoordinateType& rResultDistance,
                                    SearchStructureType& Auxiliar) {}
 
    virtual void SearchInRadius(PointType const& ThisPoint, CoordinateType const& Radius, CoordinateType const& Radius2, IteratorType& Results,
                                DistanceIteratorType& ResultsDistances, SizeType& NumberOfResults, SizeType const& MaxNumberOfResults)
    {
        // must be implemented in derived classes.
        return;
    }
 
    virtual void SearchInRadius(PointType const& ThisPoint, CoordinateType const& Radius, CoordinateType const& Radius2, IteratorType& Results,
                                DistanceIteratorType& ResultsDistances, SizeType& NumberOfResults, SizeType const& MaxNumberOfResults, SearchStructureType& Auxiliar)
    {
        // must be implemented in derived classes.
        return;
    }
 
    virtual void SearchInRadius(PointType const& ThisPoint, CoordinateType const& Radius, CoordinateType const& Radius2, IteratorType& Results,
                                SizeType& NumberOfResults, SizeType const& MaxNumberOfResults)
    {
        // must be implemented in derived classes.
        return;
    }
 
    virtual void SearchInRadius(PointType const& ThisPoint, CoordinateType const& Radius, CoordinateType const& Radius2, IteratorType& Results,
                                SizeType& NumberOfResults, SizeType const& MaxNumberOfResults, SearchStructureType& Auxiliar)
    {
        // must be implemented in derived classes.
        return;
    }
 
    virtual void SearchInBox(PointType const& SearchMinPoint, PointType const& SearchMaxPoint, IteratorType& Results, SizeType& NumberOfResults,
                             SizeType const& MaxNumberOfResults ) // This corresponds with a AABB bounding-box
    {
        // must be implemented in derived classes.
        return;
    }
 
    // Note: Add OBB bounding-box and K-DOP bounding-box
 
    static IteratorType& NullIterator()
    {
        return msNull;
    }
 
    static PointerType& NullPointer()
    {
        return msNullPointer;
    }
 
    static TreeNode& NullLeaf()
    {
        return msNullLeaf;
    }
 
private:
    static IteratorType msNull;
    static PointerType msNullPointer;
    static TreeNode msNullLeaf;
};
 
template<std::size_t TDimension, class TPointType, class TPointerType, class TIteratorType, class TDistanceIteratorType, class TIteratorIteratorType>
typename TreeNode<TDimension, TPointType, TPointerType, TIteratorType, TDistanceIteratorType, TIteratorIteratorType>::IteratorType
TreeNode<TDimension, TPointType, TPointerType, TIteratorType, TDistanceIteratorType, TIteratorIteratorType>::msNull;
 
template<std::size_t TDimension, class TPointType, class TPointerType, class TIteratorType, class TDistanceIteratorType, class TIteratorIteratorType>
typename TreeNode<TDimension, TPointType, TPointerType, TIteratorType, TDistanceIteratorType, TIteratorIteratorType>::PointerType
TreeNode<TDimension, TPointType, TPointerType, TIteratorType, TDistanceIteratorType, TIteratorIteratorType>::msNullPointer;
 
template<std::size_t TDimension, class TPointType, class TPointerType, class TIteratorType, class TDistanceIteratorType, class TIteratorIteratorType>
TreeNode<TDimension, TPointType, TPointerType, TIteratorType, TDistanceIteratorType, TIteratorIteratorType>
TreeNode<TDimension, TPointType, TPointerType, TIteratorType, TDistanceIteratorType, TIteratorIteratorType>::msNullLeaf;
 
template< class TPartitionType >
class Tree
{
public:
 
    // Helper template to extract ObjectType or default to void
    template <typename T, typename = void>
    struct GetObjectType {
        using type = void;
    };
 
    template <typename T>
    struct GetObjectType<T, std::void_t<typename T::ObjectType>> {
        using type = typename T::ObjectType;
    };
 
    class Partitions
    {
    public:
        explicit Partitions( const std::size_t NumPartitions ) : mNumPartitions(NumPartitions) {}
        
        ~Partitions() {};
 
        std::size_t mNumPartitions;
    };
 
    KRATOS_CLASS_POINTER_DEFINITION(Tree);
 
    using PartitionType = TPartitionType;
 
    using LeafType = typename PartitionType::LeafType;
 
    using PointType = typename PartitionType::PointType;
 
    using IteratorType = typename PartitionType::IteratorType;
 
    using ObjectType = typename GetObjectType<PointType>::type;
 
    using DistanceIteratorType = typename PartitionType::DistanceIteratorType;
 
    using PointerType = typename PartitionType::PointerType;
 
    using DistanceFunction = typename PartitionType::DistanceFunction;
 
    static constexpr std::size_t Dimension = PartitionType::Dimension;
 
    using NodeType = TreeNode<Dimension,PointType,PointerType,IteratorType,DistanceIteratorType> ;
 
    using CoordinateType = typename NodeType::CoordinateType;
 
    using SizeType = typename NodeType::SizeType;
 
    using IndexType = typename NodeType::IndexType;
 
    using SearchStructureType = typename PartitionType::SearchStructureType;
 
 
    Tree(
        IteratorType itPointsBegin,
        IteratorType itPointsEnd,
        SizeType BucketSize = 1
        ) : mBucketSize(BucketSize),
            mitPointsBegin(itPointsBegin),
            mitPointsEnd(itPointsEnd)
    {
        if(mitPointsBegin == mitPointsEnd)
            return;
 
        // The BB points
        auto& r_high_point = BoundingBoxHighPoint();
        auto& r_low_point = BoundingBoxLowPoint();
 
        for(SizeType i = 0 ; i < Dimension ; i++) {
            r_high_point[i] = (**mitPointsBegin)[i];
            r_low_point[i] = (**mitPointsBegin)[i];
        }
 
        for(IteratorType point_iterator = mitPointsBegin ; point_iterator != mitPointsEnd ; point_iterator++) {
            for(SizeType i = 0 ; i < Dimension ; i++) {
                if((**point_iterator)[i] > r_high_point[i]) {
                    r_high_point[i] = (**point_iterator)[i];
                } else if((**point_iterator)[i] < r_low_point[i]) {
                   r_low_point[i]  = (**point_iterator)[i];
                }
            }
        }
 
       mRoot = TPartitionType::Construct(mitPointsBegin, mitPointsEnd, r_high_point, r_low_point, mBucketSize);
    }
 
    Tree(
        IteratorType itPointsBegin,
        IteratorType itPointsEnd,
        Partitions Parts
        ) : mitPointsBegin(itPointsBegin), 
            mitPointsEnd(itPointsEnd)
    {
        if(mitPointsBegin == mitPointsEnd)
            return;
 
        // The BB points
        auto& r_high_point = BoundingBoxHighPoint();
        auto& r_low_point = BoundingBoxLowPoint();
 
        const SizeType NumPoints = SearchUtils::PointerDistance(mitPointsBegin,mitPointsEnd);
        mBucketSize = static_cast<std::size_t>( (double) NumPoints / (double) Parts.mNumPartitions ) + 1;
 
        r_high_point = **mitPointsBegin;
        r_low_point = **mitPointsBegin;
        for(IteratorType point_iterator = mitPointsBegin ; point_iterator != mitPointsEnd ; point_iterator++) {
            for(SizeType i = 0 ; i < Dimension ; i++) {
                if((**point_iterator)[i] > r_high_point[i]) {
                    r_high_point[i] = (**point_iterator)[i];
                } else if((**point_iterator)[i] < r_low_point[i]) {
                    r_low_point[i] = (**point_iterator)[i];
                }
            }
        }
 
        mRoot = TPartitionType::Construct(mitPointsBegin, mitPointsEnd, r_high_point, r_low_point, mBucketSize);
    }
 
    virtual ~Tree()
    {
        delete mRoot;
    }
 
 
 
    PointerType ExistPoint(
        PointerType const& ThisPoint,
        CoordinateType const Tolerance = static_cast<CoordinateType>(10.0*DBL_EPSILON) 
        )
    {
        PointerType Result = *mitPointsBegin;
        CoordinateType ResultDistance = static_cast<CoordinateType>(DBL_MAX);
        // Searching the tree
        mRoot->SearchNearestPoint(*ThisPoint, Result, ResultDistance);
        if (ResultDistance<Tolerance*Tolerance)
            return Result;
        return NodeType::NullPointer();
    }
 
    PointerType SearchNearestPoint(
        PointType const& ThisPoint,
        CoordinateType& rResultDistance
        )
    {
        PointerType Result = *mitPointsBegin;
        rResultDistance = static_cast<CoordinateType>(DBL_MAX); // DistanceFunction()(ThisPoint,**mitPointsBegin);
 
        // Searching the tree
        mRoot->SearchNearestPoint(ThisPoint, Result, rResultDistance);
 
        return Result;
    }
 
    PointerType SearchNearestPoint(PointType const& ThisPoint)
    {
        PointerType Result = *mitPointsBegin; // NULL ??
        CoordinateType rResultDistance = static_cast<CoordinateType>(DBL_MAX); // DistanceFunction()(ThisPoint,**mitPointsBegin);
 
        // Searching the tree
        mRoot->SearchNearestPoint(ThisPoint, Result, rResultDistance);
 
        return Result;
    }
 
    SizeType SearchInRadius(
        PointType const& ThisPoint,
        CoordinateType Radius,
        IteratorType Results,
        DistanceIteratorType ResultsDistances,
        SizeType MaxNumberOfResults
        )
    {
        // Using the square of radius for avoiding square root calculation during search
        const CoordinateType Radius2 = Radius * Radius;
 
        // Searching the tree
        SizeType NumberOfResults = 0;
        mRoot->SearchInRadius(ThisPoint, Radius, Radius2, Results, ResultsDistances, NumberOfResults, MaxNumberOfResults);
 
        return NumberOfResults;
    }
 
    SizeType SearchInRadius(
        PointType const& ThisPoint,
        CoordinateType Radius,
        IteratorType Results,
        SizeType MaxNumberOfResults
        )
    {
        // Using the square of radius for avoiding square root calculation during search
        const CoordinateType Radius2 = Radius * Radius;
 
        // Searching the tree
        SizeType NumberOfResults = 0;
        mRoot->SearchInRadius(ThisPoint, Radius, Radius2, Results, NumberOfResults, MaxNumberOfResults);
        return NumberOfResults;
    }
 
    SizeType SearchInBox(
        PointType const& MinPointBox,
        PointType const& MaxPointBox,
        IteratorType Results,
        SizeType MaxNumberOfResults
        )
    {
        SizeType NumberOfResults = 0;
        mRoot->SearchInBox(MinPointBox,MaxPointBox,Results,NumberOfResults,MaxNumberOfResults);
        return NumberOfResults;
    }
 
 
    PointType& BoundingBoxLowPoint()
    {
        return mBoundingBox.GetMinPoint();
    }
 
    PointType& BoundingBoxHighPoint()
    {
        return mBoundingBox.GetMaxPoint();
    }
 
    BoundingBox<PointType>& GetBoundingBox()
    {
        return mBoundingBox;
    }
 
 
 
    virtual std::string Info() const
    {
        return "Tree";
    }
 
    virtual void PrintInfo(std::ostream& rOStream) const
    {
        rOStream << "Tree";
    }
 
    virtual void PrintData(std::ostream& rOStream, std::string const& Perfix = std::string()) const
    {
        mRoot->PrintData(rOStream, "  ");
    }
 
 
private:
 
    static LeafType msEmptyLeaf; 
 
 
    SizeType mBucketSize;                
 
    BoundingBox<PointType> mBoundingBox; 
 
    IteratorType mitPointsBegin;         
    IteratorType mitPointsEnd;           
 
    NodeType* mRoot;                     
 
 
 
 
 
 
    Tree& operator=(Tree const& rOther);
 
    Tree(Tree const& rOther);
 
}; // Class Tree
 
template< class TPartitionType >
typename Tree<TPartitionType>::LeafType Tree<TPartitionType>::msEmptyLeaf;
 
 
 
template<class TPartitionType>
inline std::istream& operator >> (std::istream& rIStream, Tree<TPartitionType>& rThis);
 
template<class TPartitionType>
inline std::ostream& operator << (std::ostream& rOStream, const Tree<TPartitionType>& rThis)
{
    rThis.PrintInfo(rOStream);
    rOStream << std::endl;
    rThis.PrintData(rOStream);
 
    return rOStream;
}
 
}  // namespace Kratos.