1 #ifndef KNEARESTNEIGHBORS_HPP_ 2 #define KNEARESTNEIGHBORS_HPP_ 11 namespace kNearestNeighbors {
13 template<
class FeatureSpace,
typename Fact>
16 typename FeatureSpace::Metric::Type metric;
17 typename Fact::Handle handle;
18 inline bool operator<(
const QueueEntry &rhs)
const {
19 return metric < rhs.metric;
23 template<
class FeatureSpace,
typename Fact>
27 Node(
const Fact &fact);
28 void addFact(
const Fact &fact);
32 inline const Fact &getFact()
const {
return m_fact; }
36 std::unique_ptr<NodeType> m_subNodes[2];
37 typename FeatureSpace::SplitType m_splittinFeature;
40 template<
class FeatureSpace,
typename Fact>
45 void addFact(
const Fact &fact);
49 std::unique_ptr<NodeType> m_rootNode;
53 template<
class FeatureSpace,
class Fact>
57 m_splittinFeature = FeatureSpace::NO_SPLIT;
60 template<
class FeatureSpace,
class Fact>
63 if (m_splittinFeature == FeatureSpace::NO_SPLIT)
64 m_splittinFeature = FeatureSpace::chooseSplittingFeature(m_fact, fact);
66 unsigned index = FeatureSpace::compare(m_fact, fact, m_splittinFeature);
68 if (m_subNodes[index] ==
nullptr)
71 m_subNodes[index]->addFact(fact);
74 template<
class FeatureSpace,
typename Fact>
79 unsigned end = facts.size()-1;
81 while (start != end) {
82 unsigned center = (start + end) / 2;
83 if (facts[center] < newFact) {
90 unsigned index = start;
91 for (
unsigned i = facts.size()-1; i > index; i--) {
92 facts[i] = facts[i-1];
94 facts[index] = newFact;
98 template<
class FeatureSpace,
class Fact>
103 typename FeatureSpace::Metric::Type metric = FeatureSpace::Metric::compute(features, m_fact);
105 if (facts.size() < k) {
108 if (facts.size() == k)
109 std::sort(facts.begin(), facts.end());
111 if (metric < facts[k-1].metric)
115 if (m_splittinFeature != FeatureSpace::NO_SPLIT) {
116 unsigned first = FeatureSpace::compare(m_fact, features, m_splittinFeature);
118 if (m_subNodes[first] !=
nullptr)
119 m_subNodes[first]->getkNearestNeighbors(features, facts, k);
121 if ((facts.size() < k) || FeatureSpace::Metric::stillInRange(m_fact, features, facts[k-1].metric, m_splittinFeature)) {
122 unsigned second = first ^ 1;
123 if (m_subNodes[second] !=
nullptr)
124 m_subNodes[second]->getkNearestNeighbors(features, facts, k);
130 template<
class FeatureSpace,
class Fact>
134 typename FeatureSpace::Metric::Type metric = FeatureSpace::Metric::compute(features, m_fact);
136 if (metric < fact.metric)
139 if (m_splittinFeature != FeatureSpace::NO_SPLIT) {
140 unsigned first = FeatureSpace::compare(m_fact, features, m_splittinFeature);
142 if (m_subNodes[first] !=
nullptr)
143 m_subNodes[first]->getNearestNeighbor(features, fact);
145 if (FeatureSpace::Metric::stillInRange(m_fact, features, fact.metric, m_splittinFeature)) {
146 unsigned second = first ^ 1;
147 if (m_subNodes[second] !=
nullptr)
148 m_subNodes[second]->getNearestNeighbor(features, fact);
155 template<
class FeatureSpace,
typename Fact>
158 if (m_rootNode ==
nullptr)
161 m_rootNode->addFact(fact);
164 template<
class FeatureSpace,
typename Fact>
172 if (m_rootNode !=
nullptr)
173 m_rootNode->getkNearestNeighbors(features, facts, k);
176 template<
class FeatureSpace,
typename Fact>
182 if (m_rootNode !=
nullptr)
183 m_rootNode->getNearestNeighbor(features, fact);
Definition: CameraPathEvaluation.cpp:10
Definition: KNearestNeighbors.hpp:24
Definition: KNearestNeighbors.hpp:14
Definition: KNearestNeighbors.hpp:41