kd_tree.h

Go to the documentation of this file.

/** @file
 *  @author Bram de Greve (bramz@users.sourceforge.net)
 *  @author Tom De Muer (tomdemuer@users.sourceforge.net)
 *
 *  *** BEGIN LICENSE INFORMATION ***
 *  
 *  The contents of this file are subject to the Common Public Attribution License 
 *  Version 1.0 (the "License"); you may not use this file except in compliance with 
 *  the License. You may obtain a copy of the License at 
 *  http://lass.sourceforge.net/cpal-license. The License is based on the 
 *  Mozilla Public License Version 1.1 but Sections 14 and 15 have been added to cover 
 *  use of software over a computer network and provide for limited attribution for 
 *  the Original Developer. In addition, Exhibit A has been modified to be consistent 
 *  with Exhibit B.
 *  
 *  Software distributed under the License is distributed on an "AS IS" basis, WITHOUT 
 *  WARRANTY OF ANY KIND, either express or implied. See the License for the specific 
 *  language governing rights and limitations under the License.
 *  
 *  The Original Code is LASS - Library of Assembled Shared Sources.
 *  
 *  The Initial Developer of the Original Code is Bram de Greve and Tom De Muer.
 *  The Original Developer is the Initial Developer.
 *  
 *  All portions of the code written by the Initial Developer are:
 *  Copyright (C) 2004-2007 the Initial Developer.
 *  All Rights Reserved.
 *  
 *  Contributor(s):
 *
 *  Alternatively, the contents of this file may be used under the terms of the 
 *  GNU General Public License Version 2 or later (the GPL), in which case the 
 *  provisions of GPL are applicable instead of those above.  If you wish to allow use
 *  of your version of this file only under the terms of the GPL and not to allow 
 *  others to use your version of this file under the CPAL, indicate your decision by 
 *  deleting the provisions above and replace them with the notice and other 
 *  provisions required by the GPL License. If you do not delete the provisions above,
 *  a recipient may use your version of this file under either the CPAL or the GPL.
 *  
 *  *** END LICENSE INFORMATION ***
 */



/** @class lass::spat::KdTree
 *  @brief a KD tree for point-like objects
 *  @author Bram de Greve [BdG]
 *
 *  the KD tree does NOT own the objects.  You must keep them yourself!
 */

#ifndef LASS_GUARDIAN_OF_INCLUSION_SPAT_KD_TREE_H
#define LASS_GUARDIAN_OF_INCLUSION_SPAT_KD_TREE_H

//#define LASS_SPAT_KD_TREE_DIAGNOSTICS

#include "spat_common.h"

namespace lass
{
namespace spat
{

template <typename ObjectType>
struct KdTreeObjectTraits
{
    typedef const ObjectType* TObjectIterator;
    typedef const ObjectType& TObjectReference;
    typedef ObjectType TPoint;
    typedef typename TPoint::TValue TValue;
    typedef typename TPoint::TParam TParam;
    typedef typename TPoint::TReference TReference;
    typedef typename TPoint::TConstReference TConstReference;
    enum { dimension = TPoint::dimension };

    static const TPoint& position(TObjectIterator object) { return *object; }
};



template
<
    class ObjectType,
    class ObjectTraits = KdTreeObjectTraits<ObjectType>
>
class KdTree
{
public:

    typedef KdTree<ObjectType, ObjectTraits> TSelf;

    typedef ObjectType TObject;
    typedef ObjectTraits TObjectTraits;

    typedef typename TObjectTraits::TObjectIterator TObjectIterator;
    typedef typename TObjectTraits::TObjectReference TObjectReference;
    typedef typename TObjectTraits::TPoint TPoint;
    typedef typename TObjectTraits::TValue TValue;
    typedef typename TObjectTraits::TParam TParam;
    typedef typename TObjectTraits::TParam TReference;
    typedef typename TObjectTraits::TParam TConstReference;

    enum { dimension = TObjectTraits::dimension };

    class Neighbour
    {
    public:
        Neighbour();
        Neighbour(TObjectIterator object, TValue squaredDistance);

        TObjectIterator object() const;
        TPoint position() const;
        TValue squaredDistance() const;

        TObjectIterator operator->() const;
        TObjectReference operator*() const;
        bool operator<(const Neighbour& other) const;
    private:
        TObjectIterator object_;
        TValue squaredDistance_;
    };

    typedef std::vector<Neighbour> TNeighbourhood;

    KdTree();
    KdTree(TObjectIterator first, TObjectIterator last);

    void reset();
    void reset(TObjectIterator first, TObjectIterator last);

    Neighbour nearestNeighbour(const TPoint& target) const; 
    TValue rangeSearch(const TPoint& target, TParam maxRadius, size_t maxCount,
            TNeighbourhood& neighbourhood) const;

    template <typename OutputIterator> 
    OutputIterator rangeSearch(const TPoint& target, TParam maxRadius, 
            OutputIterator first) const;    
    template <typename RandomIterator>
    RandomIterator rangeSearch(const TPoint& target, TParam maxRadius, size_t maxCount,
            RandomIterator first) const;    

    void swap(TSelf& other);
    const bool isEmpty() const;
    void clear();

    const TObjectIterator end() const;

#ifdef LASS_SPAT_KD_TREE_DIAGNOSTICS
    void diagnostics();
#endif

private:

    typedef std::vector<TObjectIterator> TObjectIterators;
    typedef typename TObjectIterators::iterator TIteratorIterator;

    typedef unsigned char TAxis;
    typedef std::vector<TAxis> TAxes;

    enum { dummyAxis_ = TAxis(-1)} ;

    class LessDim
    {
    public:
        LessDim(TAxis split): split_(split) {}
        bool operator()(const TObjectIterator& a, const TObjectIterator& b) const
        {
            return TObjectTraits::position(a)[split_] < TObjectTraits::position(b)[split_];
        }
    private:
        TAxis split_;
    };

    class Node
    {
    public:
        Node(TObjectIterator object, TAxis axis = dummyAxis_): object_(object), axis_(axis) {}
        const TObjectIterator& object() const { return object_; }
        const TAxis axis() const { return axis_; }
        const TPoint position() const { return TObjectTraits::position(object_); }
    private:
        TObjectIterator object_;
        TAxis axis_;
    };
    typedef std::vector<Node> TNodes;

    void buildHeap();
    void balance(size_t index, TIteratorIterator first, TIteratorIterator last);
    TAxis findSplitAxis(TIteratorIterator first, TIteratorIterator last) const;
    void assignNode(size_t index, TObjectIterator object, TAxis splitAxis);
    size_t findNode(size_t index, const TPoint& target) const;

    void doNearestNeighbour(size_t index, const TPoint& target, Neighbour& best) const;

    template <typename OutputIterator>
    OutputIterator doRangeSearch(size_t index, const TPoint& target, 
        TParam squaredRadius, OutputIterator output) const;
    template <typename RandomIterator>
    RandomIterator doRangeSearch(size_t index, const TPoint& target, TReference squaredRadius, 
        size_t maxCount, RandomIterator first, RandomIterator last) const;

    static TValue squaredDistance(const TPoint& a, const TPoint& b);

    TNodes heap_;
    TObjectIterator begin_;
    TObjectIterator end_;
    size_t size_;
};


}

}

#include "kd_tree.inl"

#endif

// EOF