KDTree.h

Go to the documentation of this file.

// -*- lsst-c++ -*-

/* 
 * LSST Data Management System
 * Copyright 2008, 2009, 2010 LSST Corporation.
 * 
 * This product includes software developed by the
 * LSST Project (http://www.lsst.org/).
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program 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 General Public License for more details.
 * 
 * You should have received a copy of the LSST License Statement and 
 * the GNU General Public License along with this program.  If not, 
 * see <http://www.lsstcorp.org/LegalNotices/>.
 */
 
#ifndef LSST_AP_CLUSTER_DETAIL_KDTREE_H
#define LSST_AP_CLUSTER_DETAIL_KDTREE_H

#include <limits>

#include "boost/scoped_array.hpp"

#include "Eigen/Core"


namespace lsst { namespace ap { namespace cluster { namespace detail {

struct KDTreeNode {
    double split;   
    int splitDim;   
    int right;      

    KDTreeNode() :
        split(std::numeric_limits<double>::quiet_NaN()),
        splitDim(-1),
        right(-1)
    { }
};


template <int K, typename DataT>
struct Point {
    static int const PROCESSED = -2;
    static int const UNPROCESSED = -1;
    
    Eigen::Matrix<double, K, 1> coords; 
    double dist;        
    double reach;       
    DataT data;         
    int next;           
    int state;          

    Point() :
        coords(),
        dist(std::numeric_limits<double>::quiet_NaN()),
        reach(std::numeric_limits<double>::infinity()),
        data(),
        next(-1),
        state(UNPROCESSED)
    { }

    ~Point() { }
};


template <int K, typename DataT>
class KDTree {
public:
    typedef Eigen::Matrix<double, K, 1> Vector;

    static int const MAX_HEIGHT = 30; 

    KDTree(Point<K, DataT> * points,
           int numPoints,
           int pointsPerLeaf,
           double leafExtentThreshold);
    ~KDTree();

    int size() const {
        return _numPoints;
    }
    int height() const {
        return _height;
    }
    Point<K, DataT> const * getPoints() const {
        return _points;
    }

    template <typename MetricT>
    int inRange(Vector const & v, double const distance, MetricT const & metric);

private:
    Point<K, DataT> * _points;
    int _numPoints;
    int _height;
    boost::scoped_array<KDTreeNode> _nodes;

    void build(double leafExtentThreshold);
};

}}}} // namespace lsst::ap::cluster::detail

#endif // LSST_AP_CLUSTER_DETAIL_KDTREE_H