diff options
author | vng <viktor.govako@gmail.com> | 2010-12-26 15:53:05 +0300 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 01:08:50 +0300 |
commit | 1c699a5a4009906f8a712261c5108431655f9f53 (patch) | |
tree | d632f9eb3838a4ab8e47fd1e003cf9769040ce2f /geometry | |
parent | 4223de90999ac069efbef4739e5865318710c706 (diff) |
Add kdtree++ and tree4d as 4-dimensional tree by object's limit rect.
Diffstat (limited to 'geometry')
-rw-r--r-- | geometry/geometry.pro | 2 | ||||
-rw-r--r-- | geometry/geometry_tests/geometry_tests.pro | 2 | ||||
-rw-r--r-- | geometry/geometry_tests/tree_test.cpp | 43 | ||||
-rw-r--r-- | geometry/tree4d.hpp | 106 |
4 files changed, 151 insertions, 2 deletions
diff --git a/geometry/geometry.pro b/geometry/geometry.pro index cfad199ced..eaeb7e42b8 100644 --- a/geometry/geometry.pro +++ b/geometry/geometry.pro @@ -27,4 +27,4 @@ HEADERS += \ pointu_to_uint64.hpp \ simplification.hpp \ transformations.hpp \ - + tree4d.hpp \ diff --git a/geometry/geometry_tests/geometry_tests.pro b/geometry/geometry_tests/geometry_tests.pro index 6be20bb494..322c5d1cb8 100644 --- a/geometry/geometry_tests/geometry_tests.pro +++ b/geometry/geometry_tests/geometry_tests.pro @@ -28,4 +28,4 @@ SOURCES += \ pointu_to_uint64_test.cpp \ simplification_test.cpp \ transformations_test.cpp \ - + tree_test.cpp \ diff --git a/geometry/geometry_tests/tree_test.cpp b/geometry/geometry_tests/tree_test.cpp new file mode 100644 index 0000000000..69a67cf3e0 --- /dev/null +++ b/geometry/geometry_tests/tree_test.cpp @@ -0,0 +1,43 @@ +#include "../../base/SRC_FIRST.hpp" + +#include "../../testing/testing.hpp" + +#include "../tree4d.hpp" + +namespace +{ + struct simple_traits + { + static m2::RectD GetLimitRect(m2::RectD const & r) { return r; } + }; + + typedef m4::Tree<m2::RectD, simple_traits> tree_t; + + bool compare_true(m2::RectD const &, m2::RectD const &) { return true; } +} + +UNIT_TEST(Tree4D_Smoke) +{ + tree_t theTree; + + m2::RectD arr[] = { + m2::RectD(0, 0, 1, 1), + m2::RectD(1, 1, 2, 2), + m2::RectD(2, 2, 3, 3) + }; + + for (size_t i = 0; i < ARRAY_SIZE(arr); ++i) + theTree.ReplaceIf(arr[i], &compare_true); + + vector<m2::RectD> test; + theTree.ForEach(MakeBackInsertFunctor(test)); + TEST_EQUAL(3, test.size(), ()); + + m2::RectD const replaceR(0.5, 0.5, 2.5, 2.5); + theTree.ReplaceIf(replaceR, &compare_true); + + test.clear(); + theTree.ForEach(MakeBackInsertFunctor(test)); + TEST_EQUAL(1, test.size(), ()); + TEST_EQUAL(test[0], replaceR, ()); +} diff --git a/geometry/tree4d.hpp b/geometry/tree4d.hpp new file mode 100644 index 0000000000..7e22ed290f --- /dev/null +++ b/geometry/tree4d.hpp @@ -0,0 +1,106 @@ +#pragma once + +#include "rect2d.hpp" +#include "point2d.hpp" + +#include "../base/stl_add.hpp" + +#include "../std/kdtree.hpp" + + +namespace m4 +{ + template <class T, class TTraits> + class Tree + { + struct value_t + { + T m_val; + double m_pts[4]; + + typedef double value_type; + + value_t(T const & t, m2::RectD const & r) : m_val(t) + { + m_pts[0] = r.minX(); + m_pts[1] = r.minY(); + m_pts[2] = r.maxX(); + m_pts[3] = r.maxY(); + } + + bool IsIntersect(m2::RectD const & r) const + { + return !((m_pts[2] <= r.minX()) || (m_pts[0] >= r.maxX()) || + (m_pts[3] <= r.minY()) || (m_pts[1] >= r.maxY())); + } + + double operator[](size_t i) const { return m_pts[i]; } + }; + + typedef KDTree::KDTree<4, value_t> tree_t; + typedef typename tree_t::_Region_ region_t; + tree_t m_tree; + + public: + + template <class TCompare> + void ReplaceIf(T const & obj, TCompare comp) + { + m2::RectD const rect = TTraits::GetLimitRect(obj); + + region_t rgn; + for (size_t i = 0; i < 4; ++i) + { + if (i % 2 == 0) + { + rgn._M_low_bounds[i] = rect.minX(); + rgn._M_high_bounds[i] = rect.maxX(); + } + else + { + rgn._M_low_bounds[i] = rect.minY(); + rgn._M_high_bounds[i] = rect.maxY(); + } + } + + typedef vector<value_t const *> store_vec_t; + store_vec_t isect; + + class insert_if_intersect + { + store_vec_t & m_isect; + m2::RectD const & m_rect; + + public: + insert_if_intersect(store_vec_t & isect, m2::RectD const & r) + : m_isect(isect), m_rect(r) + { + } + + void operator() (value_t const & v) + { + if (v.IsIntersect(m_rect)) + m_isect.push_back(&v); + } + }; + + m_tree.visit_within_range(rgn, insert_if_intersect(isect, rect)); + + for (size_t i = 0; i < isect.size(); ++i) + if (!comp(obj, isect[i]->m_val)) + return; + + for (store_vec_t::const_iterator i = isect.begin(); i != isect.end(); ++i) + m_tree.erase(**i); + + m_tree.insert(value_t(obj, rect)); + } + + template <class ToDo> + void ForEach(ToDo toDo) const + { + for (tree_t::const_iterator i = m_tree.begin(); i != m_tree.end(); ++i) + toDo((*i).m_val); + } + }; +} |