/usr/include/openturns/KDTree.hxx is in libopenturns-dev 1.9-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 | // -*- C++ -*-
/**
* @brief KDTree structure to speed-up queries on large samples
*
* Copyright 2005-2017 Airbus-EDF-IMACS-Phimeca
*
* This library 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.
*
* This library 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
* along with this library. If not, see <http://www.gnu.org/licenses/>.
*
*/
#ifndef OPENTURNS_KDTREE_HXX
#define OPENTURNS_KDTREE_HXX
#include "openturns/PersistentObject.hxx"
#include "openturns/Sample.hxx"
BEGIN_NAMESPACE_OPENTURNS
class KDNearestNeighboursFinder;
/**
* @class KDTree
*
* Organize d-dimensional points into a hierarchical tree-like structure
*/
class OT_API KDTree
: public PersistentObject
{
CLASSNAME;
friend class KDNearestNeighboursFinder;
public:
/** Default constructor */
KDTree();
/** Parameter constructor */
explicit KDTree(const Sample & sample);
/** Virtual constructor */
virtual KDTree * clone() const;
/** String converter */
virtual String __repr__() const;
/** Check if the tree is empty */
virtual Bool isEmpty() const;
/** Insert a point */
virtual void insert(const Point & point);
/** Get the indices of the k nearest neighbours of the given point */
virtual Indices getNearestNeighboursIndices(const Point & x,
const UnsignedInteger k,
const bool sorted = false) const;
/** Get the k nearest neighbours of the given point */
virtual Sample getNearestNeighbours(const Point & x,
const UnsignedInteger k) const;
/** Get the index of the nearest neighbour of the given point */
virtual UnsignedInteger getNearestNeighbourIndex(const Point & x) const;
/** Get the nearest neighbour of the given point */
virtual Point getNearestNeighbour(const Point & x) const;
/** Points accessor */
Sample getPoints() const;
/** Method save() stores the object through the StorageManager */
virtual void save(Advocate & adv) const;
/** Method load() reloads the object from the StorageManager */
virtual void load(Advocate & adv);
protected:
#ifndef SWIG
/**
* @class KDNode
*
* A node in a KDTree
*/
struct KDNode
{
typedef Pointer< KDNode> KDNodePointer;
/** Parameter constructor */
explicit KDNode(const UnsignedInteger index)
: index_(index)
, p_left_(0)
, p_right_(0)
{
// Nothing to do
}
/** String converter */
String __repr__() const
{
return OSS() << "class=KDNode"
<< " index=" << index_
<< " left=" << (p_left_ ? p_left_->__repr__() : "NULL")
<< " right=" << (p_right_ ? p_right_->__repr__() : "NULL");
}
/* Index of the nodal point */
UnsignedInteger index_;
/* Children */
KDNodePointer p_left_;
KDNodePointer p_right_;
}; /* class KDNode */
#endif
/** Insert the point of the database at index i in the tree */
void insert(KDNode::KDNodePointer & p_node,
const UnsignedInteger index,
const UnsignedInteger activeDimension);
/** Get the index of the nearest neighbour of the given point */
virtual UnsignedInteger getNearestNeighbourIndex(const KDNode::KDNodePointer & p_node,
const Point & x,
Scalar & bestSquaredDistance,
const UnsignedInteger activeDimension) const;
/** Build the tree */
void initialize();
/** The data organized by the tree */
Sample points_;
/** The root of the tree */
KDNode::KDNodePointer p_root_;
}; /* class KDTree */
END_NAMESPACE_OPENTURNS
#endif /* OPENTURNS_KDTREE_HXX */
|