summaryrefslogtreecommitdiff
path: root/libs/geometry/index/example
diff options
context:
space:
mode:
Diffstat (limited to 'libs/geometry/index/example')
-rw-r--r--libs/geometry/index/example/3d_benchmark.cpp161
-rw-r--r--libs/geometry/index/example/Jamfile.v254
-rw-r--r--libs/geometry/index/example/benchmark.cpp157
-rw-r--r--libs/geometry/index/example/benchmark2.cpp85
-rw-r--r--libs/geometry/index/example/benchmark3.cpp98
-rw-r--r--libs/geometry/index/example/benchmark_experimental.cpp407
-rw-r--r--libs/geometry/index/example/glut_vis.cpp722
-rw-r--r--libs/geometry/index/example/random_test.cpp183
8 files changed, 1867 insertions, 0 deletions
diff --git a/libs/geometry/index/example/3d_benchmark.cpp b/libs/geometry/index/example/3d_benchmark.cpp
new file mode 100644
index 000000000..251817681
--- /dev/null
+++ b/libs/geometry/index/example/3d_benchmark.cpp
@@ -0,0 +1,161 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <boost/geometry/index/rtree.hpp>
+
+#include <boost/chrono.hpp>
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+
+int main()
+{
+ namespace bg = boost::geometry;
+ namespace bgi = bg::index;
+ typedef boost::chrono::thread_clock clock_t;
+ typedef boost::chrono::duration<float> dur_t;
+
+ size_t values_count = 500000;
+ size_t queries_count = 200000;
+
+ std::vector< boost::tuple<float, float, float> > coords;
+
+ //randomize values
+ {
+ boost::mt19937 rng;
+ //rng.seed(static_cast<unsigned int>(std::time(0)));
+ float max_val = static_cast<float>(values_count / 2);
+ boost::uniform_real<float> range(-max_val, max_val);
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+
+ coords.reserve(values_count);
+
+ std::cout << "randomizing data\n";
+ for ( size_t i = 0 ; i < values_count ; ++i )
+ {
+ coords.push_back(boost::make_tuple(rnd(), rnd(), rnd()));
+ }
+ std::cout << "randomized\n";
+ }
+
+ typedef bg::model::point<float, 3, bg::cs::cartesian> P;
+ typedef bg::model::box<P> B;
+ //typedef bgi::rtree<B, bgi::linear<32, 8> > RT;
+ //typedef bgi::rtree<B, bgi::quadratic<32, 8> > RT;
+ typedef bgi::rtree<B, bgi::rstar<8, 3> > RT;
+
+ std::cout << "sizeof rtree: " << sizeof(RT) << std::endl;
+
+ for (;;)
+ {
+ RT t;
+
+ // inserting test
+ {
+ clock_t::time_point start = clock_t::now();
+ for (size_t i = 0 ; i < values_count ; ++i )
+ {
+ float x = boost::get<0>(coords[i]);
+ float y = boost::get<1>(coords[i]);
+ float z = boost::get<2>(coords[i]);
+ B b(P(x - 0.5f, y - 0.5f, z - 0.5f), P(x + 0.5f, y + 0.5f, z + 0.5f));
+
+ t.insert(b);
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - insert " << values_count << '\n';
+ }
+
+ std::vector<B> result;
+ result.reserve(100);
+ B result_one;
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = boost::get<0>(coords[i]);
+ float y = boost::get<1>(coords[i]);
+ float z = boost::get<2>(coords[i]);
+ result.clear();
+ t.query(bgi::intersects(B(P(x - 10, y - 10, z - 10), P(x + 10, y + 10, z + 10))), std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(B) " << queries_count << " found " << temp << '\n';
+ }
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 2 ; ++i )
+ {
+ float x1 = boost::get<0>(coords[i]);
+ float y1 = boost::get<1>(coords[i]);
+ float z1 = boost::get<2>(coords[i]);
+ float x2 = boost::get<0>(coords[i+1]);
+ float y2 = boost::get<1>(coords[i+1]);
+ float z2 = boost::get<2>(coords[i+1]);
+ float x3 = boost::get<0>(coords[i+2]);
+ float y3 = boost::get<1>(coords[i+2]);
+ float z3 = boost::get<2>(coords[i+2]);
+ result.clear();
+ t.query(
+ bgi::intersects(B(P(x1 - 10, y1 - 10, z1 - 10), P(x1 + 10, y1 + 10, z1 + 10)))
+ &&
+ !bgi::within(B(P(x2 - 10, y2 - 10, z2 - 10), P(x2 + 10, y2 + 10, z2 + 10)))
+ &&
+ !bgi::overlaps(B(P(x3 - 10, y3 - 10, z3 - 10), P(x3 + 10, y3 + 10, z3 + 10)))
+ ,
+ std::back_inserter(result)
+ );
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(i && !w && !o) " << queries_count << " found " << temp << '\n';
+ }
+
+ result.clear();
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 10 ; ++i )
+ {
+ float x = boost::get<0>(coords[i]) - 100;
+ float y = boost::get<1>(coords[i]) - 100;
+ float z = boost::get<2>(coords[i]) - 100;
+ result.clear();
+ temp += t.query(bgi::nearest(P(x, y, z), 5), std::back_inserter(result));
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(nearest(P, 5)) " << (queries_count / 10) << " found " << temp << '\n';
+ }
+
+ {
+ clock_t::time_point start = clock_t::now();
+ for (size_t i = 0 ; i < values_count / 10 ; ++i )
+ {
+ float x = boost::get<0>(coords[i]);
+ float y = boost::get<1>(coords[i]);
+ float z = boost::get<2>(coords[i]);
+ B b(P(x - 0.5f, y - 0.5f, z - 0.5f), P(x + 0.5f, y + 0.5f, z + 0.5f));
+
+ t.remove(b);
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - remove " << values_count / 10 << '\n';
+ }
+
+ std::cout << "------------------------------------------------\n";
+ }
+
+ return 0;
+}
diff --git a/libs/geometry/index/example/Jamfile.v2 b/libs/geometry/index/example/Jamfile.v2
new file mode 100644
index 000000000..2067e8d7c
--- /dev/null
+++ b/libs/geometry/index/example/Jamfile.v2
@@ -0,0 +1,54 @@
+# Boost.Geometry (aka GGL, Generic Geometry Library)
+#
+# Copyright (c) 2013 Mateusz Loskot, London, UK.
+#
+# Use, modification and distribution is subject to the Boost Software License,
+# Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+
+# Usage:
+# Build as optimised for proper benchmarking:
+# b2 variant=release threading=multi
+# b2 variant=release threading=multi link=static runtime-link=static
+#
+# Set GLUT_ROOT to installation prefix of GLUT or, for Windows,
+# it may be all-in-one directory with GLUT header and binaries.
+
+import os ;
+
+project boost-geometry-index-example
+ : requirements
+ <source>/boost//headers
+ ;
+
+local GLUT_ROOT = [ os.environ GLUT_ROOT ] ;
+if $(GLUT_ROOT)
+{
+ local glut_name = glut ;
+ if [ os.name ] = NT
+ {
+ glut_name = glut32 ;
+ }
+
+ lib glut
+ :
+ :
+ <name>$(glut_name)
+ <search>$(GLUT_ROOT)
+ <search>$(GLUT_ROOT)/lib
+ :
+ :
+ <include>$(GLUT_ROOT)
+ <include>$(GLUT_ROOT)/include
+ ;
+}
+
+exe random_test : random_test.cpp ;
+link benchmark.cpp /boost//chrono : <threading>multi ;
+link benchmark2.cpp /boost//chrono : <threading>multi ;
+link benchmark3.cpp /boost//chrono : <threading>multi ;
+link benchmark_experimental.cpp /boost//chrono : <threading>multi ;
+if $(GLUT_ROOT)
+{
+ link glut_vis.cpp glut ;
+}
diff --git a/libs/geometry/index/example/benchmark.cpp b/libs/geometry/index/example/benchmark.cpp
new file mode 100644
index 000000000..269ea4533
--- /dev/null
+++ b/libs/geometry/index/example/benchmark.cpp
@@ -0,0 +1,157 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#include <boost/geometry/index/rtree.hpp>
+
+#include <boost/chrono.hpp>
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+
+int main()
+{
+ namespace bg = boost::geometry;
+ namespace bgi = bg::index;
+ typedef boost::chrono::thread_clock clock_t;
+ typedef boost::chrono::duration<float> dur_t;
+
+ size_t values_count = 1000000;
+ size_t queries_count = 100000;
+ size_t nearest_queries_count = 10000;
+ unsigned neighbours_count = 10;
+
+ std::vector< std::pair<float, float> > coords;
+
+ //randomize values
+ {
+ boost::mt19937 rng;
+ //rng.seed(static_cast<unsigned int>(std::time(0)));
+ float max_val = static_cast<float>(values_count / 2);
+ boost::uniform_real<float> range(-max_val, max_val);
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+
+ coords.reserve(values_count);
+
+ std::cout << "randomizing data\n";
+ for ( size_t i = 0 ; i < values_count ; ++i )
+ {
+ coords.push_back(std::make_pair(rnd(), rnd()));
+ }
+ std::cout << "randomized\n";
+ }
+
+ typedef bg::model::point<double, 2, bg::cs::cartesian> P;
+ typedef bg::model::box<P> B;
+ typedef bgi::rtree<B, bgi::linear<16, 4> > RT;
+ //typedef bgi::rtree<B, bgi::quadratic<8, 3> > RT;
+ //typedef bgi::rtree<B, bgi::rstar<8, 3> > RT;
+
+ std::cout << "sizeof rtree: " << sizeof(RT) << std::endl;
+
+ for (;;)
+ {
+ RT t;
+
+ // inserting test
+ {
+ clock_t::time_point start = clock_t::now();
+ for (size_t i = 0 ; i < values_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+ t.insert(b);
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - insert " << values_count << '\n';
+ }
+
+ std::vector<B> result;
+ result.reserve(100);
+ B result_one;
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(B) " << queries_count << " found " << temp << '\n';
+ }
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 2 ; ++i )
+ {
+ float x1 = coords[i].first;
+ float y1 = coords[i].second;
+ float x2 = coords[i+1].first;
+ float y2 = coords[i+1].second;
+ float x3 = coords[i+2].first;
+ float y3 = coords[i+2].second;
+ result.clear();
+ t.query(
+ bgi::intersects(B(P(x1 - 10, y1 - 10), P(x1 + 10, y1 + 10)))
+ &&
+ !bgi::within(B(P(x2 - 10, y2 - 10), P(x2 + 10, y2 + 10)))
+ &&
+ !bgi::overlaps(B(P(x3 - 10, y3 - 10), P(x3 + 10, y3 + 10)))
+ ,
+ std::back_inserter(result)
+ );
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(i && !w && !o) " << queries_count << " found " << temp << '\n';
+ }
+
+ result.clear();
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < nearest_queries_count ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ result.clear();
+ temp += t.query(bgi::nearest(P(x, y), neighbours_count), std::back_inserter(result));
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(nearest(P, " << neighbours_count << ")) " << nearest_queries_count << " found " << temp << '\n';
+ }
+
+ {
+ clock_t::time_point start = clock_t::now();
+ for (size_t i = 0 ; i < values_count / 10 ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+ t.remove(b);
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - remove " << values_count / 10 << '\n';
+ }
+
+ std::cout << "------------------------------------------------\n";
+ }
+
+ return 0;
+}
diff --git a/libs/geometry/index/example/benchmark2.cpp b/libs/geometry/index/example/benchmark2.cpp
new file mode 100644
index 000000000..eedeac1b8
--- /dev/null
+++ b/libs/geometry/index/example/benchmark2.cpp
@@ -0,0 +1,85 @@
+// Boost.Geometry Index
+// Compare performance with std::set using 1-dimensional object
+// (i.e. angle, or number line coordiante)
+
+// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#include <boost/geometry/index/rtree.hpp>
+
+#include <boost/chrono.hpp>
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+#include <set>
+
+int main()
+{
+ namespace bg = boost::geometry;
+ namespace bgi = bg::index;
+ typedef boost::chrono::thread_clock clock_t;
+ typedef boost::chrono::duration<float> dur_t;
+
+ size_t values_count = 1001;
+ size_t count_start = 10;
+ size_t count_stop = 1000;
+ size_t count_step = 10;
+ size_t insrem_count = 3000000;
+
+ typedef bg::model::point<float, 1, bg::cs::cartesian> P;
+ //typedef bgi::rtree<P, bgi::linear<8, 3> > RT;
+ typedef bgi::rtree<P, bgi::quadratic<8, 3> > RT;
+ //typedef bgi::rtree<P, bgi::rstar<8, 3> > RT;
+
+ RT t;
+ std::set<float> s;
+ size_t val_i = 0;
+ for ( size_t curr_count = count_start ; curr_count < count_stop ; curr_count += count_step )
+ {
+ // inserting test
+ {
+ for (; val_i < curr_count ; ++val_i )
+ {
+ float v = val_i / 100.0f;
+ P p(v);
+ t.insert(p);
+ s.insert(v);
+ }
+
+ float v = (val_i+1) / 100.0f;
+ P test_p(v);
+
+ std::cout << t.size() << ' ';
+
+ clock_t::time_point start = clock_t::now();
+
+ for (size_t i = 0 ; i < insrem_count ; ++i )
+ {
+ t.insert(test_p);
+ t.remove(test_p);
+ }
+
+ dur_t time = clock_t::now() - start;
+ std::cout << time.count() << ' ';
+
+ start = clock_t::now();
+
+ for (size_t i = 0 ; i < insrem_count ; ++i )
+ {
+ s.insert(v);
+ s.erase(v);
+ }
+
+ time = clock_t::now() - start;
+ std::cout << time.count() << ' ';
+ }
+
+ std::cout << '\n';
+ }
+
+ return 0;
+}
diff --git a/libs/geometry/index/example/benchmark3.cpp b/libs/geometry/index/example/benchmark3.cpp
new file mode 100644
index 000000000..6898e4eb8
--- /dev/null
+++ b/libs/geometry/index/example/benchmark3.cpp
@@ -0,0 +1,98 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#include <boost/geometry/index/rtree.hpp>
+
+#include <boost/chrono.hpp>
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+#include <set>
+
+int main()
+{
+ namespace bg = boost::geometry;
+ namespace bgi = bg::index;
+ typedef boost::chrono::thread_clock clock_t;
+ typedef boost::chrono::duration<float> dur_t;
+
+ size_t stored_count = 100000;
+
+ std::vector< std::pair<float, float> > coords;
+
+ //randomize values
+ {
+ boost::mt19937 rng;
+ //rng.seed(static_cast<unsigned int>(std::time(0)));
+ float max_val = static_cast<float>(stored_count / 10);
+ boost::uniform_real<float> range(-max_val, max_val);
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+
+ coords.reserve(stored_count);
+
+ std::cout << "randomizing data\n";
+ for ( size_t i = 0 ; i < stored_count ; ++i )
+ {
+ coords.push_back(std::make_pair(rnd(), rnd()));
+ }
+ std::cout << "randomized\n";
+ }
+
+ typedef bg::model::point<float, 2, bg::cs::cartesian> P;
+ typedef bgi::rtree<P, bgi::dynamic_linear > RTL;
+ typedef bgi::rtree<P, bgi::dynamic_quadratic > RTQ;
+ typedef bgi::rtree<P, bgi::dynamic_rstar > RTR;
+
+ for ( size_t m = 4 ; m < 33 ; m += 2 )
+ {
+ size_t mm = ::ceil(m / 3.0f);
+
+ RTL rtl(bgi::dynamic_linear(m, mm));
+ RTQ rtq(bgi::dynamic_quadratic(m, mm));
+ RTR rtr(bgi::dynamic_rstar(m, mm));
+
+ std::cout << m << ' ' << mm << ' ';
+
+ // inserting test
+ {
+ clock_t::time_point start = clock_t::now();
+ for (size_t i = 0 ; i < stored_count ; ++i )
+ {
+ P p(coords[i].first, coords[i].second);
+ rtl.insert(p);
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time.count() << ' ';
+
+ start = clock_t::now();
+ for (size_t i = 0 ; i < stored_count ; ++i )
+ {
+ P p(coords[i].first, coords[i].second);
+ rtq.insert(p);
+ }
+ time = clock_t::now() - start;
+ std::cout << time.count() << ' ';
+
+ start = clock_t::now();
+ for (size_t i = 0 ; i < stored_count ; ++i )
+ {
+ float v = i / 100.0f;
+ P p(coords[i].first, coords[i].second);
+ rtr.insert(p);
+ }
+ time = clock_t::now() - start;
+ std::cout << time.count() << ' ';
+ }
+
+ std::cout << '\n';
+ }
+
+ return 0;
+}
diff --git a/libs/geometry/index/example/benchmark_experimental.cpp b/libs/geometry/index/example/benchmark_experimental.cpp
new file mode 100644
index 000000000..5d9c229a3
--- /dev/null
+++ b/libs/geometry/index/example/benchmark_experimental.cpp
@@ -0,0 +1,407 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#define BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+#define BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
+
+#include <iostream>
+
+#include <boost/chrono.hpp>
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+
+#include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/geometries/linestring.hpp>
+#include <boost/geometry/geometries/segment.hpp>
+
+namespace bg = boost::geometry;
+namespace bgi = bg::index;
+
+typedef bg::model::point<double, 2, bg::cs::cartesian> P;
+typedef bg::model::box<P> B;
+typedef bg::model::linestring<P> LS;
+typedef bg::model::segment<P> S;
+typedef B V;
+//typedef P V;
+
+template <typename V>
+struct generate_value {};
+
+template <>
+struct generate_value<B>
+{
+ static inline B apply(float x, float y) { return B(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
+};
+
+template <>
+struct generate_value<P>
+{
+ static inline P apply(float x, float y) { return P(x, y); }
+};
+
+//#include <boost/geometry/extensions/nsphere/nsphere.hpp>
+//typedef bg::model::nsphere<P, double> NS;
+//typedef NS V;
+//
+//template <>
+//struct generate_value<NS>
+//{
+// static inline NS apply(float x, float y) { return NS(P(x, y), 0.5); }
+//};
+
+template <typename I1, typename I2, typename O>
+void mycopy(I1 first, I2 last, O o)
+{
+ for ( ; first != last ; ++o, ++first )
+ *o = *first;
+}
+
+//#define BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
+
+int main()
+{
+ typedef boost::chrono::thread_clock clock_t;
+ typedef boost::chrono::duration<float> dur_t;
+
+#ifndef BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
+ size_t values_count = 1000000;
+ size_t queries_count = 100000;
+ size_t nearest_queries_count = 10000;
+ unsigned neighbours_count = 10;
+ size_t path_queries_count = 2000;
+ size_t path_queries_count2 = 10000;
+ unsigned path_values_count = 10;
+#else
+ size_t values_count = 1000;
+ size_t queries_count = 1;
+ size_t nearest_queries_count = 1;
+ unsigned neighbours_count = 10;
+ size_t path_queries_count = 1;
+ size_t path_queries_count2 = 1;
+ unsigned path_values_count = 10;
+#endif
+
+ float max_val = static_cast<float>(values_count / 2);
+ std::vector< std::pair<float, float> > coords;
+ std::vector<V> values;
+
+ //randomize values
+ {
+ boost::mt19937 rng;
+ //rng.seed(static_cast<unsigned int>(std::time(0)));
+ boost::uniform_real<float> range(-max_val, max_val);
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+
+ coords.reserve(values_count);
+
+ std::cout << "randomizing data\n";
+ for ( size_t i = 0 ; i < values_count ; ++i )
+ {
+ float x = rnd();
+ float y = rnd();
+ coords.push_back(std::make_pair(x, y));
+ values.push_back(generate_value<V>::apply(x, y));
+ }
+ std::cout << "randomized\n";
+ }
+
+ typedef bgi::rtree<V, bgi::linear<16, 4> > RT;
+ //typedef bgi::rtree<V, bgi::quadratic<16, 4> > RT;
+ //typedef bgi::rtree<V, bgi::rstar<16, 4> > RT;
+
+ std::cout << "sizeof rtree: " << sizeof(RT) << std::endl;
+
+ for (;;)
+ {
+ std::vector<V> result;
+ result.reserve(100);
+ B result_one;
+
+ // packing test
+ {
+ clock_t::time_point start = clock_t::now();
+
+ RT t(values.begin(), values.end());
+
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - pack " << values_count << '\n';
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(B) " << queries_count << " found " << temp << '\n';
+ }
+ }
+
+ RT t;
+
+ // inserting test
+ {
+ clock_t::time_point start = clock_t::now();
+ t.insert(values);
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - insert " << values_count << '\n';
+ }
+
+
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(B) " << queries_count << " found " << temp << '\n';
+ }
+
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ std::copy(
+ t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ t.qend(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - qbegin(B) qend(B) " << queries_count << " found " << temp << '\n';
+ }
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ mycopy(
+ t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ t.qend(),
+ std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - qbegin(B) qend() " << queries_count << " found " << temp << '\n';
+ }
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ RT::const_query_iterator first = t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
+ RT::const_query_iterator last = t.qend(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
+ std::copy(first, last, std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - type-erased qbegin(B) qend(B) " << queries_count << " found " << temp << '\n';
+ }
+#endif
+#endif
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 2 ; ++i )
+ {
+ float x1 = coords[i].first;
+ float y1 = coords[i].second;
+ float x2 = coords[i+1].first;
+ float y2 = coords[i+1].second;
+ float x3 = coords[i+2].first;
+ float y3 = coords[i+2].second;
+ result.clear();
+ t.query(
+ bgi::intersects(B(P(x1 - 10, y1 - 10), P(x1 + 10, y1 + 10)))
+ &&
+ !bgi::within(B(P(x2 - 10, y2 - 10), P(x2 + 10, y2 + 10)))
+ &&
+ !bgi::covered_by(B(P(x3 - 10, y3 - 10), P(x3 + 10, y3 + 10)))
+ ,
+ std::back_inserter(result)
+ );
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(i && !w && !c) " << queries_count << " found " << temp << '\n';
+ }
+
+ result.clear();
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < nearest_queries_count ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ result.clear();
+ temp += t.query(bgi::nearest(P(x, y), neighbours_count), std::back_inserter(result));
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(nearest(P, " << neighbours_count << ")) " << nearest_queries_count << " found " << temp << '\n';
+ }
+
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < nearest_queries_count ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ result.clear();
+ std::copy(
+ t.qbegin(bgi::nearest(P(x, y), neighbours_count)),
+ t.qend(bgi::nearest(P(x, y), neighbours_count)),
+ std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - qbegin(nearest(P, " << neighbours_count << ")) qend(n) " << nearest_queries_count << " found " << temp << '\n';
+ }
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < nearest_queries_count ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ result.clear();
+ mycopy(
+ t.qbegin(bgi::nearest(P(x, y), neighbours_count)),
+ t.qend(),
+ std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - qbegin(nearest(P, " << neighbours_count << ")) qend() " << nearest_queries_count << " found " << temp << '\n';
+ }
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < nearest_queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ RT::const_query_iterator first = t.qbegin(bgi::nearest(P(x, y), neighbours_count));
+ RT::const_query_iterator last = t.qend(bgi::nearest(P(x, y), neighbours_count));
+ std::copy(first, last, std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - type-erased qbegin(nearest(P, " << neighbours_count << ")) qend(n) " << nearest_queries_count << " found " << temp << '\n';
+ }
+#endif
+
+ {
+ LS ls;
+ ls.resize(6);
+
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < path_queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ for ( int i = 0 ; i < 3 ; ++i )
+ {
+ float foo = i*max_val/300;
+ ls[2*i] = P(x, y+foo);
+ ls[2*i+1] = P(x+max_val/100, y+foo);
+ }
+ result.clear();
+ t.query(bgi::path(ls, path_values_count), std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(path(LS6, " << path_values_count << ")) " << path_queries_count << " found " << temp << '\n';
+ }
+
+ {
+ LS ls;
+ ls.resize(2);
+
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < path_queries_count2 ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ ls[0] = P(x, y);
+ ls[1] = P(x+max_val/100, y+max_val/100);
+ result.clear();
+ t.query(bgi::path(ls, path_values_count), std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(path(LS2, " << path_values_count << ")) " << path_queries_count2 << " found " << temp << '\n';
+ }
+
+ {
+ clock_t::time_point start = clock_t::now();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < path_queries_count2 ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ S seg(P(x, y), P(x+max_val/100, y+max_val/100));
+ result.clear();
+ t.query(bgi::path(seg, path_values_count), std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - query(path(S, " << path_values_count << ")) " << path_queries_count2 << " found " << temp << '\n';
+ }
+#endif
+ {
+ clock_t::time_point start = clock_t::now();
+ for (size_t i = 0 ; i < values_count / 10 ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+
+ t.remove(generate_value<V>::apply(x, y));
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - remove " << values_count / 10 << '\n';
+ }
+
+ std::cout << "------------------------------------------------\n";
+ }
+
+ return 0;
+}
diff --git a/libs/geometry/index/example/glut_vis.cpp b/libs/geometry/index/example/glut_vis.cpp
new file mode 100644
index 000000000..d6a434707
--- /dev/null
+++ b/libs/geometry/index/example/glut_vis.cpp
@@ -0,0 +1,722 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <GL/glut.h>
+
+#include <boost/foreach.hpp>
+
+#include <boost/geometry/index/rtree.hpp>
+
+#include <boost/geometry/geometries/linestring.hpp>
+#include <boost/geometry/geometries/ring.hpp>
+#include <boost/geometry/geometries/polygon.hpp>
+#include <boost/geometry/multi/geometries/multi_polygon.hpp>
+
+#include <boost/geometry/index/detail/rtree/utilities/gl_draw.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/print.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/are_levels_ok.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/statistics.hpp>
+
+namespace bg = boost::geometry;
+namespace bgi = bg::index;
+
+typedef bg::model::point<float, 2, boost::geometry::cs::cartesian> P;
+typedef bg::model::box<P> B;
+//bgi::rtree<B> t(2, 1);
+typedef bg::model::linestring<P> LS;
+typedef bg::model::ring<P> R;
+typedef bg::model::polygon<P> Poly;
+typedef bg::model::multi_polygon<Poly> MPoly;
+
+typedef bgi::rtree<
+ B,
+ bgi::rstar<4, 2>
+> RTree;
+RTree t;
+std::vector<B> vect;
+
+size_t found_count = 0;
+P search_point;
+size_t count = 5;
+std::vector<B> nearest_boxes;
+B search_box;
+R search_ring;
+Poly search_poly;
+MPoly search_multi_poly;
+LS search_path;
+
+enum query_mode_type {
+ qm_knn, qm_c, qm_d, qm_i, qm_o, qm_w, qm_nc, qm_nd, qm_ni, qm_no, qm_nw, qm_all, qm_ri, qm_pi, qm_mpi, qm_path
+} query_mode = qm_knn;
+
+bool search_valid = false;
+
+void query_knn()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+
+ search_point = P(x, y);
+ nearest_boxes.clear();
+ found_count = t.query(
+ bgi::nearest(search_point, count),
+ std::back_inserter(nearest_boxes)
+ );
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search point: ";
+ bgi::detail::utilities::print_indexable(std::cout, search_point);
+ std::cout << "\nfound: ";
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ {
+ bgi::detail::utilities::print_indexable(std::cout, nearest_boxes[i]);
+ std::cout << '\n';
+ }
+ }
+ else
+ std::cout << "nearest not found\n";
+}
+
+void query_path()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+ float w = 20 + ( rand() % 1000 ) / 100.0f;
+ float h = 20 + ( rand() % 1000 ) / 100.0f;
+
+ search_path.resize(10);
+ float yy = y-h;
+ for ( int i = 0 ; i < 5 ; ++i, yy += h / 2 )
+ {
+ search_path[2 * i] = P(x-w, yy);
+ search_path[2 * i + 1] = P(x+w, yy);
+ }
+
+ nearest_boxes.clear();
+ found_count = t.query(
+ bgi::detail::path<LS>(search_path, count),
+ std::back_inserter(nearest_boxes)
+ );
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search path: ";
+ BOOST_FOREACH(P const& p, search_path)
+ bgi::detail::utilities::print_indexable(std::cout, p);
+ std::cout << "\nfound: ";
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ {
+ bgi::detail::utilities::print_indexable(std::cout, nearest_boxes[i]);
+ std::cout << '\n';
+ }
+ }
+ else
+ std::cout << "values on path not found\n";
+}
+
+template <typename Predicate>
+void query()
+{
+ if ( query_mode != qm_all )
+ {
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+ float w = 10 + ( rand() % 1000 ) / 100.0f;
+ float h = 10 + ( rand() % 1000 ) / 100.0f;
+
+ search_box = B(P(x - w, y - h), P(x + w, y + h));
+ nearest_boxes.clear();
+ found_count = t.query(Predicate(search_box), std::back_inserter(nearest_boxes) );
+ }
+ else
+ {
+ search_box = t.bounds();
+ nearest_boxes.clear();
+ found_count = t.query(Predicate(search_box), std::back_inserter(nearest_boxes) );
+ }
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search box: ";
+ bgi::detail::utilities::print_indexable(std::cout, search_box);
+ std::cout << "\nfound: ";
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ {
+ bgi::detail::utilities::print_indexable(std::cout, nearest_boxes[i]);
+ std::cout << '\n';
+ }
+ }
+ else
+ std::cout << "boxes not found\n";
+}
+
+template <typename Predicate>
+void query_ring()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+ float w = 10 + ( rand() % 1000 ) / 100.0f;
+ float h = 10 + ( rand() % 1000 ) / 100.0f;
+
+ search_ring.clear();
+ search_ring.push_back(P(x - w, y - h));
+ search_ring.push_back(P(x - w/2, y - h));
+ search_ring.push_back(P(x, y - 3*h/2));
+ search_ring.push_back(P(x + w/2, y - h));
+ search_ring.push_back(P(x + w, y - h));
+ search_ring.push_back(P(x + w, y - h/2));
+ search_ring.push_back(P(x + 3*w/2, y));
+ search_ring.push_back(P(x + w, y + h/2));
+ search_ring.push_back(P(x + w, y + h));
+ search_ring.push_back(P(x + w/2, y + h));
+ search_ring.push_back(P(x, y + 3*h/2));
+ search_ring.push_back(P(x - w/2, y + h));
+ search_ring.push_back(P(x - w, y + h));
+ search_ring.push_back(P(x - w, y + h/2));
+ search_ring.push_back(P(x - 3*w/2, y));
+ search_ring.push_back(P(x - w, y - h/2));
+ search_ring.push_back(P(x - w, y - h));
+
+ nearest_boxes.clear();
+ found_count = t.query(Predicate(search_ring), std::back_inserter(nearest_boxes) );
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search ring: ";
+ BOOST_FOREACH(P const& p, search_ring)
+ {
+ bgi::detail::utilities::print_indexable(std::cout, p);
+ std::cout << ' ';
+ }
+ std::cout << "\nfound: ";
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ {
+ bgi::detail::utilities::print_indexable(std::cout, nearest_boxes[i]);
+ std::cout << '\n';
+ }
+ }
+ else
+ std::cout << "boxes not found\n";
+}
+
+template <typename Predicate>
+void query_poly()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+ float w = 10 + ( rand() % 1000 ) / 100.0f;
+ float h = 10 + ( rand() % 1000 ) / 100.0f;
+
+ search_poly.clear();
+ search_poly.outer().push_back(P(x - w, y - h));
+ search_poly.outer().push_back(P(x - w/2, y - h));
+ search_poly.outer().push_back(P(x, y - 3*h/2));
+ search_poly.outer().push_back(P(x + w/2, y - h));
+ search_poly.outer().push_back(P(x + w, y - h));
+ search_poly.outer().push_back(P(x + w, y - h/2));
+ search_poly.outer().push_back(P(x + 3*w/2, y));
+ search_poly.outer().push_back(P(x + w, y + h/2));
+ search_poly.outer().push_back(P(x + w, y + h));
+ search_poly.outer().push_back(P(x + w/2, y + h));
+ search_poly.outer().push_back(P(x, y + 3*h/2));
+ search_poly.outer().push_back(P(x - w/2, y + h));
+ search_poly.outer().push_back(P(x - w, y + h));
+ search_poly.outer().push_back(P(x - w, y + h/2));
+ search_poly.outer().push_back(P(x - 3*w/2, y));
+ search_poly.outer().push_back(P(x - w, y - h/2));
+ search_poly.outer().push_back(P(x - w, y - h));
+
+ search_poly.inners().push_back(Poly::ring_type());
+ search_poly.inners()[0].push_back(P(x - w/2, y - h/2));
+ search_poly.inners()[0].push_back(P(x + w/2, y - h/2));
+ search_poly.inners()[0].push_back(P(x + w/2, y + h/2));
+ search_poly.inners()[0].push_back(P(x - w/2, y + h/2));
+ search_poly.inners()[0].push_back(P(x - w/2, y - h/2));
+
+ nearest_boxes.clear();
+ found_count = t.query(Predicate(search_poly), std::back_inserter(nearest_boxes) );
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search poly outer: ";
+ BOOST_FOREACH(P const& p, search_poly.outer())
+ {
+ bgi::detail::utilities::print_indexable(std::cout, p);
+ std::cout << ' ';
+ }
+ std::cout << "\nfound: ";
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ {
+ bgi::detail::utilities::print_indexable(std::cout, nearest_boxes[i]);
+ std::cout << '\n';
+ }
+ }
+ else
+ std::cout << "boxes not found\n";
+}
+
+template <typename Predicate>
+void query_multi_poly()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+ float w = 10 + ( rand() % 1000 ) / 100.0f;
+ float h = 10 + ( rand() % 1000 ) / 100.0f;
+
+ search_multi_poly.clear();
+
+ search_multi_poly.push_back(Poly());
+ search_multi_poly[0].outer().push_back(P(x - w, y - h));
+ search_multi_poly[0].outer().push_back(P(x - w/2, y - h));
+ search_multi_poly[0].outer().push_back(P(x, y - 3*h/2));
+ search_multi_poly[0].outer().push_back(P(x + w/2, y - h));
+ search_multi_poly[0].outer().push_back(P(x + w, y - h));
+ search_multi_poly[0].outer().push_back(P(x + w, y - h/2));
+ search_multi_poly[0].outer().push_back(P(x + 3*w/2, y));
+ search_multi_poly[0].outer().push_back(P(x + w, y + h/2));
+ search_multi_poly[0].outer().push_back(P(x + w, y + h));
+ search_multi_poly[0].outer().push_back(P(x + w/2, y + h));
+ search_multi_poly[0].outer().push_back(P(x, y + 3*h/2));
+ search_multi_poly[0].outer().push_back(P(x - w/2, y + h));
+ search_multi_poly[0].outer().push_back(P(x - w, y + h));
+ search_multi_poly[0].outer().push_back(P(x - w, y + h/2));
+ search_multi_poly[0].outer().push_back(P(x - 3*w/2, y));
+ search_multi_poly[0].outer().push_back(P(x - w, y - h/2));
+ search_multi_poly[0].outer().push_back(P(x - w, y - h));
+
+ search_multi_poly[0].inners().push_back(Poly::ring_type());
+ search_multi_poly[0].inners()[0].push_back(P(x - w/2, y - h/2));
+ search_multi_poly[0].inners()[0].push_back(P(x + w/2, y - h/2));
+ search_multi_poly[0].inners()[0].push_back(P(x + w/2, y + h/2));
+ search_multi_poly[0].inners()[0].push_back(P(x - w/2, y + h/2));
+ search_multi_poly[0].inners()[0].push_back(P(x - w/2, y - h/2));
+
+ search_multi_poly.push_back(Poly());
+ search_multi_poly[1].outer().push_back(P(x - 2*w, y - 2*h));
+ search_multi_poly[1].outer().push_back(P(x - 6*w/5, y - 2*h));
+ search_multi_poly[1].outer().push_back(P(x - 6*w/5, y - 6*h/5));
+ search_multi_poly[1].outer().push_back(P(x - 2*w, y - 6*h/5));
+ search_multi_poly[1].outer().push_back(P(x - 2*w, y - 2*h));
+
+ search_multi_poly.push_back(Poly());
+ search_multi_poly[2].outer().push_back(P(x + 6*w/5, y + 6*h/5));
+ search_multi_poly[2].outer().push_back(P(x + 2*w, y + 6*h/5));
+ search_multi_poly[2].outer().push_back(P(x + 2*w, y + 2*h));
+ search_multi_poly[2].outer().push_back(P(x + 6*w/5, y + 2*h));
+ search_multi_poly[2].outer().push_back(P(x + 6*w/5, y + 6*h/5));
+
+ nearest_boxes.clear();
+ found_count = t.query(Predicate(search_multi_poly), std::back_inserter(nearest_boxes) );
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search multi_poly[0] outer: ";
+ BOOST_FOREACH(P const& p, search_multi_poly[0].outer())
+ {
+ bgi::detail::utilities::print_indexable(std::cout, p);
+ std::cout << ' ';
+ }
+ std::cout << "\nfound: ";
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ {
+ bgi::detail::utilities::print_indexable(std::cout, nearest_boxes[i]);
+ std::cout << '\n';
+ }
+ }
+ else
+ std::cout << "boxes not found\n";
+}
+
+void search()
+{
+ namespace d = bgi::detail;
+
+ if ( query_mode == qm_knn )
+ query_knn();
+ else if ( query_mode == qm_c )
+ query< d::spatial_predicate<B, d::covered_by_tag, false> >();
+ else if ( query_mode == qm_d )
+ query< d::spatial_predicate<B, d::disjoint_tag, false> >();
+ else if ( query_mode == qm_i )
+ query< d::spatial_predicate<B, d::intersects_tag, false> >();
+ else if ( query_mode == qm_o )
+ query< d::spatial_predicate<B, d::overlaps_tag, false> >();
+ else if ( query_mode == qm_w )
+ query< d::spatial_predicate<B, d::within_tag, false> >();
+ else if ( query_mode == qm_nc )
+ query< d::spatial_predicate<B, d::covered_by_tag, true> >();
+ else if ( query_mode == qm_nd )
+ query< d::spatial_predicate<B, d::disjoint_tag, true> >();
+ else if ( query_mode == qm_ni )
+ query< d::spatial_predicate<B, d::intersects_tag, true> >();
+ else if ( query_mode == qm_no )
+ query< d::spatial_predicate<B, d::overlaps_tag, true> >();
+ else if ( query_mode == qm_nw )
+ query< d::spatial_predicate<B, d::within_tag, true> >();
+ else if ( query_mode == qm_all )
+ query< d::spatial_predicate<B, d::intersects_tag, false> >();
+ else if ( query_mode == qm_ri )
+ query_ring< d::spatial_predicate<R, d::intersects_tag, false> >();
+ else if ( query_mode == qm_pi )
+ query_poly< d::spatial_predicate<Poly, d::intersects_tag, false> >();
+ else if ( query_mode == qm_mpi )
+ query_multi_poly< d::spatial_predicate<MPoly, d::intersects_tag, false> >();
+ else if ( query_mode == qm_path )
+ query_path();
+
+ search_valid = true;
+}
+
+void draw_knn_area(float min_distance, float max_distance)
+{
+ float x = boost::geometry::get<0>(search_point);
+ float y = boost::geometry::get<1>(search_point);
+ float z = bgi::detail::rtree::utilities::view<RTree>(t).depth();
+
+ // search point
+ glBegin(GL_TRIANGLES);
+ glVertex3f(x, y, z);
+ glVertex3f(x + 1, y, z);
+ glVertex3f(x + 1, y + 1, z);
+ glEnd();
+
+ // search min circle
+
+ glBegin(GL_LINE_LOOP);
+ for(float a = 0 ; a < 3.14158f * 2 ; a += 3.14158f / 180)
+ glVertex3f(x + min_distance * ::cos(a), y + min_distance * ::sin(a), z);
+ glEnd();
+
+ // search max circle
+
+ glBegin(GL_LINE_LOOP);
+ for(float a = 0 ; a < 3.14158f * 2 ; a += 3.14158f / 180)
+ glVertex3f(x + max_distance * ::cos(a), y + max_distance * ::sin(a), z);
+ glEnd();
+}
+
+void draw_path(LS const& ls)
+{
+ glBegin(GL_LINE_STRIP);
+
+ BOOST_FOREACH(P const& p, ls)
+ {
+ float x = boost::geometry::get<0>(p);
+ float y = boost::geometry::get<1>(p);
+ float z = bgi::detail::rtree::utilities::view<RTree>(t).depth();
+ glVertex3f(x, y, z);
+ }
+
+ glEnd();
+}
+
+template <typename Box>
+void draw_box(Box const& box)
+{
+ float x1 = boost::geometry::get<bg::min_corner, 0>(box);
+ float y1 = boost::geometry::get<bg::min_corner, 1>(box);
+ float x2 = boost::geometry::get<bg::max_corner, 0>(box);
+ float y2 = boost::geometry::get<bg::max_corner, 1>(box);
+ float z = bgi::detail::rtree::utilities::view<RTree>(t).depth();
+
+ // search box
+ glBegin(GL_LINE_LOOP);
+ glVertex3f(x1, y1, z);
+ glVertex3f(x2, y1, z);
+ glVertex3f(x2, y2, z);
+ glVertex3f(x1, y2, z);
+ glEnd();
+}
+
+template <typename Range>
+void draw_ring(Range const& range)
+{
+ float z = bgi::detail::rtree::utilities::view<RTree>(t).depth();
+
+ // search box
+ glBegin(GL_LINE_LOOP);
+
+ BOOST_FOREACH(P const& p, range)
+ {
+ float x = boost::geometry::get<0>(p);
+ float y = boost::geometry::get<1>(p);
+
+ glVertex3f(x, y, z);
+ }
+ glEnd();
+}
+
+template <typename Polygon>
+void draw_polygon(Polygon const& polygon)
+{
+ draw_ring(polygon.outer());
+ BOOST_FOREACH(Poly::ring_type const& r, polygon.inners())
+ draw_ring(r);
+}
+
+template <typename MultiPolygon>
+void draw_multi_polygon(MultiPolygon const& multi_polygon)
+{
+ BOOST_FOREACH(Poly const& p, multi_polygon)
+ draw_polygon(p);
+}
+
+void render_scene(void)
+{
+ glClear(GL_COLOR_BUFFER_BIT);
+
+ bgi::detail::rtree::utilities::gl_draw(t);
+
+ if ( search_valid )
+ {
+ glColor3f(1.0f, 0.5f, 0.0f);
+
+ if ( query_mode == qm_knn )
+ draw_knn_area(0, 0);
+ else if ( query_mode == qm_ri )
+ draw_ring(search_ring);
+ else if ( query_mode == qm_pi )
+ draw_polygon(search_poly);
+ else if ( query_mode == qm_mpi )
+ draw_multi_polygon(search_multi_poly);
+ else if ( query_mode == qm_path )
+ draw_path(search_path);
+ else
+ draw_box(search_box);
+
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ bgi::detail::utilities::gl_draw_indexable(
+ nearest_boxes[i],
+ bgi::detail::rtree::utilities::view<RTree>(t).depth());
+ }
+
+ glFlush();
+}
+
+void resize(int w, int h)
+{
+ if ( h == 0 )
+ h = 1;
+
+ //float ratio = float(w) / h;
+
+ glMatrixMode(GL_PROJECTION);
+ glLoadIdentity();
+
+ glViewport(0, 0, w, h);
+
+ //gluPerspective(45, ratio, 1, 1000);
+ glOrtho(-150, 150, -150, 150, -150, 150);
+ glMatrixMode(GL_MODELVIEW);
+ glLoadIdentity();
+ /*gluLookAt(
+ 120.0f, 120.0f, 120.0f,
+ 50.0f, 50.0f, -1.0f,
+ 0.0f, 1.0f, 0.0f);*/
+ gluLookAt(
+ 50.0f, 50.0f, 75.0f,
+ 50.0f, 50.0f, -1.0f,
+ 0.0f, 1.0f, 0.0f);
+
+ glClearColor(1.0f, 1.0f, 1.0f, 1.0f);
+ glLineWidth(1.5f);
+
+ srand(1);
+}
+
+void mouse(int button, int state, int /*x*/, int /*y*/)
+{
+ if ( button == GLUT_LEFT_BUTTON && state == GLUT_DOWN )
+ {
+ float x = ( rand() % 100 );
+ float y = ( rand() % 100 );
+ float w = ( rand() % 2 ) + 1;
+ float h = ( rand() % 2 ) + 1;
+
+ B b(P(x - w, y - h),P(x + w, y + h));
+
+ boost::geometry::index::insert(t, b);
+ vect.push_back(b);
+
+ std::cout << "inserted: ";
+ bgi::detail::utilities::print_indexable(std::cout, b);
+ std::cout << '\n';
+
+ std::cout << ( bgi::detail::rtree::utilities::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::detail::rtree::utilities::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+
+ search_valid = false;
+ }
+ else if ( button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN )
+ {
+ if ( vect.empty() )
+ return;
+
+ size_t i = rand() % vect.size();
+ B b = vect[i];
+
+ bgi::remove(t, b);
+ vect.erase(vect.begin() + i);
+
+ std::cout << "removed: ";
+ bgi::detail::utilities::print_indexable(std::cout, b);
+ std::cout << '\n';
+
+ std::cout << ( bgi::detail::rtree::utilities::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::detail::rtree::utilities::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+
+ search_valid = false;
+ }
+ else if ( button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN )
+ {
+ search();
+ }
+
+ glutPostRedisplay();
+}
+
+std::string current_line;
+
+void keyboard(unsigned char key, int /*x*/, int /*y*/)
+{
+ if ( key == '\r' || key == '\n' )
+ {
+ if ( current_line == "t" )
+ {
+ std::cout << "\n";
+ bgi::detail::rtree::utilities::print(std::cout, t);
+ std::cout << "\n";
+ }
+ else if ( current_line == "rand" )
+ {
+ for ( size_t i = 0 ; i < 35 ; ++i )
+ {
+ float x = ( rand() % 100 );
+ float y = ( rand() % 100 );
+ float w = ( rand() % 2 ) + 1;
+ float h = ( rand() % 2 ) + 1;
+
+ B b(P(x - w, y - h),P(x + w, y + h));
+
+ boost::geometry::index::insert(t, b);
+ vect.push_back(b);
+
+ std::cout << "inserted: ";
+ bgi::detail::utilities::print_indexable(std::cout, b);
+ std::cout << '\n';
+ }
+
+ std::cout << ( bgi::detail::rtree::utilities::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::detail::rtree::utilities::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+
+ search_valid = false;
+
+ glutPostRedisplay();
+ }
+ else if ( current_line == "bulk" )
+ {
+ vect.clear();
+
+ for ( size_t i = 0 ; i < 35 ; ++i )
+ {
+ float x = ( rand() % 100 );
+ float y = ( rand() % 100 );
+ float w = ( rand() % 2 ) + 1;
+ float h = ( rand() % 2 ) + 1;
+
+ B b(P(x - w, y - h),P(x + w, y + h));
+ vect.push_back(b);
+
+ std::cout << "inserted: ";
+ bgi::detail::utilities::print_indexable(std::cout, b);
+ std::cout << '\n';
+ }
+
+ RTree t2(vect);
+ t = boost::move(t2);
+
+ std::cout << ( bgi::detail::rtree::utilities::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::detail::rtree::utilities::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+
+ search_valid = false;
+
+ glutPostRedisplay();
+ }
+ else
+ {
+ if ( current_line == "knn" )
+ query_mode = qm_knn;
+ else if ( current_line == "c" )
+ query_mode = qm_c;
+ else if ( current_line == "d" )
+ query_mode = qm_d;
+ else if ( current_line == "i" )
+ query_mode = qm_i;
+ else if ( current_line == "o" )
+ query_mode = qm_o;
+ else if ( current_line == "w" )
+ query_mode = qm_w;
+ else if ( current_line == "nc" )
+ query_mode = qm_nc;
+ else if ( current_line == "nd" )
+ query_mode = qm_nd;
+ else if ( current_line == "ni" )
+ query_mode = qm_ni;
+ else if ( current_line == "no" )
+ query_mode = qm_no;
+ else if ( current_line == "nw" )
+ query_mode = qm_nw;
+ else if ( current_line == "all" )
+ query_mode = qm_all;
+ else if ( current_line == "ri" )
+ query_mode = qm_ri;
+ else if ( current_line == "pi" )
+ query_mode = qm_pi;
+ else if ( current_line == "mpi" )
+ query_mode = qm_mpi;
+ else if ( current_line == "path" )
+ query_mode = qm_path;
+
+ search();
+ glutPostRedisplay();
+ }
+
+ current_line.clear();
+ std::cout << '\n';
+ }
+ else
+ {
+ current_line += key;
+ std::cout << key;
+ }
+}
+
+int main(int argc, char **argv)
+{
+ glutInit(&argc, argv);
+ glutInitDisplayMode(GLUT_DEPTH | GLUT_SINGLE | GLUT_RGBA);
+ glutInitWindowPosition(100,100);
+ glutInitWindowSize(600, 600);
+ glutCreateWindow("boost::geometry::index::rtree GLUT test");
+
+ glutDisplayFunc(render_scene);
+ glutReshapeFunc(resize);
+ glutMouseFunc(mouse);
+ glutKeyboardFunc(keyboard);
+
+ glutMainLoop();
+
+ return 0;
+}
diff --git a/libs/geometry/index/example/random_test.cpp b/libs/geometry/index/example/random_test.cpp
new file mode 100644
index 000000000..f4145152c
--- /dev/null
+++ b/libs/geometry/index/example/random_test.cpp
@@ -0,0 +1,183 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#define BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+#include <boost/geometry/index/rtree.hpp>
+
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+
+int main()
+{
+ namespace bg = boost::geometry;
+ namespace bgi = bg::index;
+
+ size_t values_count = 1000000;
+ size_t queries_count = 10000;
+ size_t nearest_queries_count = 10000;
+ unsigned neighbours_count = 10;
+
+ std::vector< std::pair<float, float> > coords;
+
+ //randomize values
+ {
+ boost::mt19937 rng;
+ //rng.seed(static_cast<unsigned int>(std::time(0)));
+ float max_val = static_cast<float>(values_count / 2);
+ boost::uniform_real<float> range(-max_val, max_val);
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+
+ coords.reserve(values_count);
+
+ std::cout << "randomizing data\n";
+ for ( size_t i = 0 ; i < values_count ; ++i )
+ {
+ coords.push_back(std::make_pair(rnd(), rnd()));
+ }
+ std::cout << "randomized\n";
+ }
+
+ typedef bg::model::point<double, 2, bg::cs::cartesian> P;
+ typedef bg::model::box<P> B;
+ typedef bgi::rtree<B, bgi::linear<16, 4> > RT;
+ //typedef bgi::rtree<B, bgi::quadratic<8, 3> > RT;
+ //typedef bgi::rtree<B, bgi::rstar<8, 3> > RT;
+
+ std::cout << "sizeof rtree: " << sizeof(RT) << std::endl;
+
+ {
+ RT t;
+
+ // inserting
+ {
+ for (size_t i = 0 ; i < values_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+ t.insert(b);
+ }
+ std::cout << "inserted values: " << values_count << '\n';
+ }
+
+ std::vector<B> result;
+ result.reserve(100);
+
+ // test
+ std::vector<size_t> spatial_query_data;
+ size_t spatial_query_index = 0;
+
+ {
+ size_t found_count = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
+
+ // test
+ spatial_query_data.push_back(result.size());
+ found_count += result.size();
+ }
+ std::cout << "spatial queries found: " << found_count << '\n';
+ }
+
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+ {
+ size_t found_count = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ result.clear();
+ std::copy(t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ t.qend(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ std::back_inserter(result));
+
+ // test
+ if ( spatial_query_data[spatial_query_index] != result.size() )
+ std::cout << "Spatial query error - should be: " << spatial_query_data[spatial_query_index] << ", is: " << result.size() << '\n';
+ ++spatial_query_index;
+ found_count += result.size();
+ }
+ std::cout << "incremental spatial queries found: " << found_count << '\n';
+ }
+#endif
+
+ // test
+ std::vector<float> nearest_query_data;
+ size_t nearest_query_data_index = 0;
+
+ {
+ size_t found_count = 0;
+ for (size_t i = 0 ; i < nearest_queries_count ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ result.clear();
+ t.query(bgi::nearest(P(x, y), neighbours_count), std::back_inserter(result));
+
+ // test
+ {
+ float max_dist = 0;
+ BOOST_FOREACH(B const& b, result)
+ {
+ float curr_dist = bgi::detail::comparable_distance_near(P(x, y), b);
+ if ( max_dist < curr_dist )
+ max_dist = curr_dist;
+ }
+ nearest_query_data.push_back(max_dist);
+ }
+ found_count += result.size();
+ }
+ std::cout << "nearest queries found: " << found_count << '\n';
+ }
+
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+ {
+ size_t found_count = 0;
+ for (size_t i = 0 ; i < nearest_queries_count ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ result.clear();
+
+ std::copy(t.qbegin(bgi::nearest(P(x, y), neighbours_count)),
+ t.qend(bgi::nearest(P(x, y), neighbours_count)),
+ std::back_inserter(result));
+
+ // test
+ {
+ float max_dist = 0;
+ BOOST_FOREACH(B const& b, result)
+ {
+ float curr_dist = bgi::detail::comparable_distance_near(P(x, y), b);
+ if ( max_dist < curr_dist )
+ max_dist = curr_dist;
+ }
+ if ( nearest_query_data_index < nearest_query_data.size() &&
+ nearest_query_data[nearest_query_data_index] != max_dist )
+ std::cout << "Max distance error - should be: " << nearest_query_data[nearest_query_data_index] << ", and is: " << max_dist << "\n";
+ ++nearest_query_data_index;
+ }
+ found_count += result.size();
+ }
+ std::cout << "incremental nearest queries found: " << found_count << '\n';
+ }
+#endif
+
+ std::cout << "finished\n";
+ }
+
+ return 0;
+}
View Lorry Controller Status