K-d tree: Difference between revisions
m
Reformatted to reduce line count
m (Made random final in QuickSelect.java) |
m (Reformatted to reduce line count) |
||
Line 227:
<lang cpp>#include <algorithm>
#include <array>
#include <vector>▼
#include <cmath>
#include <iostream>
#include <random>
▲#include <vector>
/**
Line 236:
*/
template<typename coordinate_type, size_t dimensions>
class point {
public:
point(std::array<coordinate_type, dimensions> c) : coords_(c) {}
point(std::initializer_list<coordinate_type> list) {▼
{▼
▲ point(std::initializer_list<coordinate_type> list)
size_t n = std::min(dimensions, list.size());
std::copy_n(list.begin(), n, coords_.begin());
Line 253 ⟶ 249:
* @return coordinate in the given dimension
*/
coordinate_type get(size_t index) const {
return coords_[index];
}
Line 264 ⟶ 259:
* @return distance squared from this point to the other point
*/
double distance(const point& pt) const {
double dist = 0;
for (size_t i = 0; i < dimensions; ++i) {
double d = get(i) - pt.get(i);
dist += d * d;
Line 279 ⟶ 272:
template<typename coordinate_type, size_t dimensions>
std::ostream& operator<<(std::ostream& out, const point<coordinate_type, dimensions>& pt) {
out << '(';
for (size_t i = 0; i < dimensions; ++i) {
if (i > 0)
out << ", ";
Line 296 ⟶ 287:
*/
template<typename coordinate_type, size_t dimensions>
class kdtree {
public:
typedef point<coordinate_type, dimensions> point_type;
private:
struct node {
node(const point_type& pt) : point_(pt), left_(nullptr), right_(nullptr) {}▼
coordinate_type get(size_t index) const {▼
▲ node(const point_type& pt) : point_(pt), left_(nullptr), right_(nullptr)
▲ coordinate_type get(size_t index) const
return point_.get(index);
}
double distance(const point_type& pt) const {
return point_.distance(pt);
}
Line 324 ⟶ 309:
std::vector<node> nodes_;
struct node_cmp {
node_cmp(size_t index) : index_(index) {}▼
bool operator()(const node& n1, const node& n2) const {▼
▲ node_cmp(size_t index) : index_(index)
▲ bool operator()(const node& n1, const node& n2) const
return n1.point_.get(index_) < n2.point_.get(index_);
}
Line 336 ⟶ 317:
};
node* make_tree(size_t begin, size_t end, size_t index) {
if (end <= begin)
return nullptr;
Line 348 ⟶ 328:
}
void nearest(node* root, const point_type& point, size_t index) {
if (root == nullptr)
return;
++visited_;
double d = root->distance(point);
if (best_ == nullptr || d < best_dist_) {
best_dist_ = d;
best_ = root;
Line 379 ⟶ 357:
*/
template<typename iterator>
kdtree(iterator begin, iterator end) {
best_ = nullptr;
best_dist_ = 0;
Line 399 ⟶ 376:
*/
template<typename func>
kdtree(func&& f, size_t n) {
best_ = nullptr;
best_dist_ = 0;
Line 413 ⟶ 389:
* Returns true if the tree is empty, false otherwise.
*/
bool empty() const { return nodes_.empty(); }
/**
Line 422 ⟶ 395:
* to nearest().
*/
size_t visited() const { return visited_; }
/**
Line 431 ⟶ 401:
* from the last call to nearest().
*/
double distance() const { return std::sqrt(best_dist_); }
/**
Line 441 ⟶ 408:
*
* @param pt a point
* @
*/
const point_type& nearest(const point_type& pt) {
if (root_ == nullptr)
throw std::logic_error("tree is empty");
Line 455 ⟶ 421:
};
void test_wikipedia() {
typedef point<int, 2> point2d;
typedef kdtree<int, 2> tree2d;
point2d points[] = { { 2, 3 }, { 5, 4 }, { 9, 6 }, { 4, 7 }, { 8, 1 }, { 7, 2 }
tree2d tree(std::begin(points), std::end(points));
Line 474 ⟶ 439:
typedef kdtree<double, 3> tree3d;
struct random_point_generator {
random_point_generator(double min, double max)
: engine_(std::random_device()()), distribution_(min, max) {}
point3d operator()() {
double x = distribution_(engine_);
double y = distribution_(engine_);
Line 493 ⟶ 454:
};
void test_random(size_t count) {
random_point_generator rpg(0, 1);
tree3d tree(rpg, count);
Line 507 ⟶ 467:
}
int main() {
▲ try {
test_wikipedia();
std::cout << '\n';
Line 516 ⟶ 474:
std::cout << '\n';
test_random(1000000);
} catch (const std::exception& e) {▼
▲ catch (const std::exception& e)
std::cerr << e.what() << '\n';
}
return 0;
}</lang>
| |||