summaryrefslogtreecommitdiffstats
path: root/src/boost/libs/geometry/index/example
diff options
context:
space:
mode:
Diffstat (limited to 'src/boost/libs/geometry/index/example')
-rw-r--r--src/boost/libs/geometry/index/example/3d_benchmark.cpp161
-rw-r--r--src/boost/libs/geometry/index/example/Jamfile.v255
-rw-r--r--src/boost/libs/geometry/index/example/benchmark.cpp158
-rw-r--r--src/boost/libs/geometry/index/example/benchmark2.cpp86
-rw-r--r--src/boost/libs/geometry/index/example/benchmark3.cpp99
-rw-r--r--src/boost/libs/geometry/index/example/benchmark_experimental.cpp482
-rw-r--r--src/boost/libs/geometry/index/example/benchmark_insert.cpp196
-rw-r--r--src/boost/libs/geometry/index/example/glut_vis.cpp1094
-rw-r--r--src/boost/libs/geometry/index/example/random_test.cpp185
-rw-r--r--src/boost/libs/geometry/index/example/serialize.cpp168
10 files changed, 2684 insertions, 0 deletions
diff --git a/src/boost/libs/geometry/index/example/3d_benchmark.cpp b/src/boost/libs/geometry/index/example/3d_benchmark.cpp
new file mode 100644
index 00000000..25181768
--- /dev/null
+++ b/src/boost/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/src/boost/libs/geometry/index/example/Jamfile.v2 b/src/boost/libs/geometry/index/example/Jamfile.v2
new file mode 100644
index 00000000..5cfa81a0
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/Jamfile.v2
@@ -0,0 +1,55 @@
+# 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
+ <implicit-dependency>/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 serialize.cpp /boost//serialization : ;
+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/src/boost/libs/geometry/index/example/benchmark.cpp b/src/boost/libs/geometry/index/example/benchmark.cpp
new file mode 100644
index 00000000..ba2a1dec
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/benchmark.cpp
@@ -0,0 +1,158 @@
+// 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.hpp>
+#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/src/boost/libs/geometry/index/example/benchmark2.cpp b/src/boost/libs/geometry/index/example/benchmark2.cpp
new file mode 100644
index 00000000..48194cbd
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/benchmark2.cpp
@@ -0,0 +1,86 @@
+// 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.hpp>
+#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/src/boost/libs/geometry/index/example/benchmark3.cpp b/src/boost/libs/geometry/index/example/benchmark3.cpp
new file mode 100644
index 00000000..ad1910e4
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/benchmark3.cpp
@@ -0,0 +1,99 @@
+// 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.hpp>
+#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/src/boost/libs/geometry/index/example/benchmark_experimental.cpp b/src/boost/libs/geometry/index/example/benchmark_experimental.cpp
new file mode 100644
index 00000000..6556d766
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/benchmark_experimental.cpp
@@ -0,0 +1,482 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2015 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
+
+#include <iostream>
+
+#include <boost/chrono.hpp>
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+#include <boost/range/algorithm/copy.hpp>
+
+#include <boost/geometry.hpp>
+#include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/geometries/linestring.hpp>
+#include <boost/geometry/geometries/segment.hpp>
+
+#include <boost/geometry/index/detail/rtree/utilities/are_levels_ok.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/are_boxes_ok.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 P V;
+typedef B V;
+//typedef S V;
+//#define SEGMENT_INDEXABLE
+
+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<S>
+{
+ static inline S apply(float x, float y) { return S(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 = 20000;
+ unsigned neighbours_count = 10;
+ size_t path_queries_count = 2000;
+ size_t path_queries_count2 = 20000;
+ 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'*/;
+
+ std::cout << (bgi::detail::rtree::utilities::are_levels_ok(t) ? " ok" : " NOK")
+ << (bgi::detail::rtree::utilities::are_boxes_ok(t) ? " ok\n" : "NOK\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'*/;
+
+ std::cout << (bgi::detail::rtree::utilities::are_levels_ok(t) ? " ok" : " NOK")
+ << (bgi::detail::rtree::utilities::are_boxes_ok(t) ? " ok\n" : "NOK\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';
+ }
+
+ {
+ 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();
+ boost::copy(t | bgi::adaptors::queried(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 << " - range queried(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';
+ }
+ {
+ 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();
+ boost::copy(
+ std::make_pair(
+ 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 << " - range qbegin(B) qend(B)" << queries_count << " found " << temp << '\n';
+ }
+#endif // 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();
+ 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();
+ 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() " << 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();
+ 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();
+ boost::copy(std::make_pair(first, last), std::back_inserter(result));
+ temp += result.size();
+ }
+ dur_t time = clock_t::now() - start;
+ std::cout << time << " - range type-erased qbegin(B) qend() " << queries_count << " found " << temp << '\n';
+ }
+
+#ifndef SEGMENT_INDEXABLE
+ {
+ 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';
+ }
+#endif
+
+ 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';
+ }
+#endif // 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;
+ 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();
+ 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() " << nearest_queries_count << " found " << temp << '\n';
+ }
+
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+#ifndef SEGMENT_INDEXABLE
+
+ {
+ 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
+#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 << (bgi::detail::rtree::utilities::are_boxes_ok(t) ? " boxes ok\n" : "boxes NOT ok\n");
+ }
+
+ std::cout << "------------------------------------------------\n";
+ }
+
+ return 0;
+}
diff --git a/src/boost/libs/geometry/index/example/benchmark_insert.cpp b/src/boost/libs/geometry/index/example/benchmark_insert.cpp
new file mode 100644
index 00000000..4fe82e91
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/benchmark_insert.cpp
@@ -0,0 +1,196 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2015 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 <vector>
+#include <algorithm>
+
+#include <boost/chrono.hpp>
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+
+#include <boost/geometry.hpp>
+#include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/geometries/geometries.hpp>
+
+#include <boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/are_counts_ok.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/are_levels_ok.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::segment<P> S;
+typedef P V;
+//typedef B V;
+//typedef S 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<S>
+{
+ static inline S apply(float x, float y) { return S(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); }
+};
+
+template <typename RT>
+void test_queries(RT const& t, std::vector< std::pair<float, float> > const& coords, size_t queries_count)
+{
+ typedef boost::chrono::thread_clock clock_t;
+ typedef boost::chrono::duration<float> dur_t;
+
+ std::vector<V> result;
+ result.reserve(100);
+
+ 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.count() << " " << temp << '\n';
+}
+
+//#define BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
+
+int main()
+{
+ //typedef bgi::rtree<V, bgi::linear<4, 2> > RT;
+ //typedef bgi::rtree<V, bgi::linear<16, 4> > RT;
+ //typedef bgi::rtree<V, bgi::quadratic<4, 2> > RT;
+ typedef bgi::rtree<V, bgi::rstar<8, 2> > RT;
+
+ 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 = 20000;
+ unsigned neighbours_count = 10;
+ size_t max_range_inserts = 10;
+#else
+ size_t values_count = 10000;
+ size_t queries_count = 1000;
+ size_t nearest_queries_count = 100;
+ unsigned neighbours_count = 10;
+ size_t max_range_inserts = 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";
+ }
+
+ for (;;)
+ {
+ // packing test
+ {
+ clock_t::time_point start = clock_t::now();
+
+ RT t(values.begin(), values.end());
+
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
+
+ dur_t time = clock_t::now() - start;
+ std::cout << "pack(" << values_count << ") - " << time.count() << ", ";
+
+ test_queries(t, coords, queries_count);
+ }
+
+ {
+ size_t n_per_max = values_count / max_range_inserts;
+
+ for ( size_t j = 0 ; j < max_range_inserts ; ++j )
+ {
+ clock_t::time_point start = clock_t::now();
+
+ RT t;
+
+ // perform j range-inserts
+ for ( size_t i = 0 ; i < j ; ++i )
+ {
+ t.insert(values.begin() + n_per_max * i,
+ values.begin() + (std::min)(n_per_max * (i + 1), values_count));
+ }
+
+ if ( !t.empty() )
+ {
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
+ }
+
+ // perform n-n/max_inserts*j inserts
+ size_t inserted_count = (std::min)(n_per_max*j, values_count);
+ for ( size_t i = inserted_count ; i < values_count ; ++i )
+ {
+ t.insert(values[i]);
+ }
+
+ if ( !t.empty() )
+ {
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
+ BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
+ }
+
+ dur_t time = clock_t::now() - start;
+ std::cout << j << "*insert(N/" << max_range_inserts << ")+insert(" << (values_count - inserted_count) << ") - " << time.count() << ", ";
+
+ test_queries(t, coords, queries_count);
+ }
+ }
+
+ std::cout << "------------------------------------------------\n";
+ }
+
+ return 0;
+}
diff --git a/src/boost/libs/geometry/index/example/glut_vis.cpp b/src/boost/libs/geometry/index/example/glut_vis.cpp
new file mode 100644
index 00000000..2c5f5740
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/glut_vis.cpp
@@ -0,0 +1,1094 @@
+// Boost.Geometry Index
+// OpenGL visualization
+
+// Copyright (c) 2011-2014 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.hpp>
+#include <boost/geometry/index/rtree.hpp>
+
+#include <boost/geometry/geometries/linestring.hpp>
+#include <boost/geometry/geometries/segment.hpp>
+#include <boost/geometry/geometries/ring.hpp>
+#include <boost/geometry/geometries/polygon.hpp>
+#include <boost/geometry/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>
+
+#include <boost/variant.hpp>
+
+#define ENABLE_POINTS_AND_SEGMENTS
+
+namespace bg = boost::geometry;
+namespace bgi = bg::index;
+
+// used types
+
+typedef bg::model::point<float, 2, boost::geometry::cs::cartesian> P;
+typedef bg::model::box<P> B;
+typedef bg::model::linestring<P> LS;
+typedef bg::model::segment<P> S;
+typedef bg::model::ring<P> R;
+typedef bg::model::polygon<P> Poly;
+typedef bg::model::multi_polygon<Poly> MPoly;
+
+// containers variant
+
+template <typename V>
+struct containers
+{
+ containers & operator=(containers const& c)
+ {
+ tree = c.tree;
+ values = c.values;
+ result = c.result;
+ return *this;
+ }
+
+ bgi::rtree< V, bgi::rstar<4, 2> > tree;
+ std::vector<V> values;
+ std::vector<V> result;
+};
+
+boost::variant<
+ containers<B>
+#ifdef ENABLE_POINTS_AND_SEGMENTS
+ , containers<P>
+ , containers<S>
+#endif
+> cont;
+
+// visitors
+
+template <typename Pred>
+struct query_v : boost::static_visitor<size_t>
+{
+ Pred m_pred;
+ query_v(Pred const& pred) : m_pred(pred) {}
+
+ template <typename C>
+ size_t operator()(C & c) const
+ {
+ c.result.clear();
+ return c.tree.query(m_pred, std::back_inserter(c.result));
+ }
+};
+template <typename Cont, typename Pred>
+inline size_t query(Cont & cont, Pred const& pred)
+{
+ return boost::apply_visitor(query_v<Pred>(pred), cont);
+}
+
+struct print_result_v : boost::static_visitor<>
+{
+ template <typename C>
+ void operator()(C & c) const
+ {
+ for ( size_t i = 0 ; i < c.result.size() ; ++i )
+ {
+ bgi::detail::utilities::print_indexable(std::cout, c.result[i]);
+ std::cout << '\n';
+ }
+ }
+};
+template <typename Cont>
+inline void print_result(Cont const& cont)
+{
+ boost::apply_visitor(print_result_v(), cont);
+}
+
+struct bounds_v : boost::static_visitor<B>
+{
+ template <typename C>
+ B operator()(C & c) const
+ {
+ return c.tree.bounds();
+ }
+};
+template <typename Cont>
+inline B bounds(Cont const& cont)
+{
+ return boost::apply_visitor(bounds_v(), cont);
+}
+
+struct depth_v : boost::static_visitor<size_t>
+{
+ template <typename C>
+ size_t operator()(C & c) const
+ {
+ return get(c.tree);
+ }
+ template <typename RTree>
+ static size_t get(RTree const& t)
+ {
+ return bgi::detail::rtree::utilities::view<RTree>(t).depth();
+ }
+};
+template <typename Cont>
+inline size_t depth(Cont const& cont)
+{
+ return boost::apply_visitor(depth_v(), cont);
+}
+
+struct draw_tree_v : boost::static_visitor<>
+{
+ template <typename C>
+ void operator()(C & c) const
+ {
+ bgi::detail::rtree::utilities::gl_draw(c.tree);
+ }
+};
+template <typename Cont>
+inline void draw_tree(Cont const& cont)
+{
+ return boost::apply_visitor(draw_tree_v(), cont);
+}
+
+struct draw_result_v : boost::static_visitor<>
+{
+ template <typename C>
+ void operator()(C & c) const
+ {
+ for ( size_t i = 0 ; i < c.result.size() ; ++i )
+ {
+ bgi::detail::utilities::gl_draw_indexable(c.result[i], depth_v::get(c.tree));
+ }
+ }
+};
+template <typename Cont>
+inline void draw_result(Cont const& cont)
+{
+ return boost::apply_visitor(draw_result_v(), cont);
+}
+
+struct print_tree_v : boost::static_visitor<>
+{
+ template <typename C>
+ void operator()(C & c) const
+ {
+ bgi::detail::rtree::utilities::print(std::cout, c.tree);
+ }
+};
+template <typename Cont>
+inline void print_tree(Cont const& cont)
+{
+ return boost::apply_visitor(print_tree_v(), cont);
+}
+
+// globals used in querying
+
+size_t found_count = 0;
+size_t count = 5;
+
+P search_point;
+B search_box;
+R search_ring;
+Poly search_poly;
+MPoly search_multi_poly;
+S search_segment;
+LS search_linestring;
+LS search_path;
+
+enum query_mode_type {
+ qm_knn, qm_knnb, qm_knns, 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_si, qm_lsi, qm_path
+} query_mode = qm_knn;
+
+bool search_valid = false;
+
+// various queries
+
+void query_knn()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+
+ if ( query_mode == qm_knn )
+ {
+ search_point = P(x, y);
+ found_count = query(cont, bgi::nearest(search_point, count));
+ }
+ else if ( query_mode == qm_knnb )
+ {
+ float w = 2 + ( rand() % 1000 ) / 500.0f;
+ float h = 2 + ( rand() % 1000 ) / 500.0f;
+ search_box = B(P(x - w, y - h), P(x + w, y + h));
+ found_count = query(cont, bgi::nearest(search_box, count));
+ }
+ else if ( query_mode == qm_knns )
+ {
+ int signx = rand() % 2 ? 1 : -1;
+ int signy = rand() % 2 ? 1 : -1;
+ float w = (10 + ( rand() % 1000 ) / 100.0f) * signx;
+ float h = (10 + ( rand() % 1000 ) / 100.0f) * signy;
+ search_segment = S(P(x - w, y - h), P(x + w, y + h));
+ found_count = query(cont, bgi::nearest(search_segment, count));
+ }
+ else
+ {
+ BOOST_ASSERT(false);
+ }
+
+ if ( found_count > 0 )
+ {
+ if ( query_mode == qm_knn )
+ {
+ std::cout << "search point: ";
+ bgi::detail::utilities::print_indexable(std::cout, search_point);
+ }
+ else if ( query_mode == qm_knnb )
+ {
+ std::cout << "search box: ";
+ bgi::detail::utilities::print_indexable(std::cout, search_box);
+ }
+ else if ( query_mode == qm_knns )
+ {
+ std::cout << "search segment: ";
+ bgi::detail::utilities::print_indexable(std::cout, search_segment);
+ }
+ else
+ {
+ BOOST_ASSERT(false);
+ }
+ std::cout << "\nfound: ";
+ print_result(cont);
+ }
+ else
+ std::cout << "nearest not found\n";
+}
+
+#ifndef ENABLE_POINTS_AND_SEGMENTS
+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);
+ }
+
+ found_count = query(cont, bgi::detail::path<LS>(search_path, count));
+
+ 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: ";
+ print_result(cont);
+ }
+ else
+ std::cout << "values on path not found\n";
+}
+#endif
+
+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));
+ }
+ else
+ {
+ search_box = bounds(cont);
+ }
+
+ found_count = query(cont, Predicate(search_box));
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search box: ";
+ bgi::detail::utilities::print_indexable(std::cout, search_box);
+ std::cout << "\nfound: ";
+ print_result(cont);
+ }
+ 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));
+
+ found_count = query(cont, Predicate(search_ring));
+
+ 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: ";
+ print_result(cont);
+ }
+ 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));
+
+ found_count = query(cont, Predicate(search_poly));
+
+ 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: ";
+ print_result(cont);
+ }
+ 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));
+
+ found_count = query(cont, Predicate(search_multi_poly));
+
+ 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: ";
+ print_result(cont);
+ }
+ else
+ std::cout << "boxes not found\n";
+}
+
+template <typename Predicate>
+void query_segment()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+ float w = 10.0f - ( rand() % 1000 ) / 50.0f;
+ float h = 10.0f - ( rand() % 1000 ) / 50.0f;
+ w += 0 <= w ? 10 : -10;
+ h += 0 <= h ? 10 : -10;
+
+ boost::geometry::set<0, 0>(search_segment, x - w);
+ boost::geometry::set<0, 1>(search_segment, y - h);
+ boost::geometry::set<1, 0>(search_segment, x + w);
+ boost::geometry::set<1, 1>(search_segment, y + h);
+
+ found_count = query(cont, Predicate(search_segment));
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search segment: ";
+ bgi::detail::utilities::print_indexable(std::cout, P(x-w, y-h));
+ bgi::detail::utilities::print_indexable(std::cout, P(x+w, y+h));
+
+ std::cout << "\nfound: ";
+ print_result(cont);
+ }
+ else
+ std::cout << "boxes not found\n";
+}
+
+template <typename Predicate>
+void query_linestring()
+{
+ 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_linestring.clear();
+ float a = 0;
+ float d = 0;
+ for ( size_t i = 0 ; i < 300 ; ++i, a += 0.05, d += 0.005 )
+ {
+ float xx = x + w * d * ::cos(a);
+ float yy = y + h * d * ::sin(a);
+ search_linestring.push_back(P(xx, yy));
+ }
+
+ found_count = query(cont, Predicate(search_linestring));
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search linestring: ";
+ BOOST_FOREACH(P const& p, search_linestring)
+ {
+ bgi::detail::utilities::print_indexable(std::cout, p);
+ std::cout << ' ';
+ }
+ std::cout << "\nfound: ";
+ print_result(cont);
+ }
+ else
+ std::cout << "boxes not found\n";
+}
+
+// the function running the correct query based on the query_mode
+
+void search()
+{
+ namespace d = bgi::detail;
+
+ if ( query_mode == qm_knn || query_mode == qm_knnb || query_mode == qm_knns )
+ query_knn();
+ 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_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_all )
+ query< d::spatial_predicate<B, d::intersects_tag, false> >();
+#ifdef ENABLE_POINTS_AND_SEGMENTS
+ else
+ std::cout << "query disabled\n";
+#else
+ else if ( query_mode == qm_c )
+ query< d::spatial_predicate<B, d::covered_by_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_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_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_si )
+ query_segment< d::spatial_predicate<S, d::intersects_tag, false> >();
+ else if ( query_mode == qm_lsi )
+ query_linestring< d::spatial_predicate<LS, d::intersects_tag, false> >();
+ else if ( query_mode == qm_path )
+ query_path();
+#endif
+
+ search_valid = true;
+}
+
+// various drawing functions
+
+void draw_point(P const& p)
+{
+ float x = boost::geometry::get<0>(p);
+ float y = boost::geometry::get<1>(p);
+ float z = depth(cont);
+
+ glBegin(GL_QUADS);
+ glVertex3f(x+1, y, z);
+ glVertex3f(x, y+1, z);
+ glVertex3f(x-1, y, z);
+ glVertex3f(x, y-1, z);
+ glEnd();
+}
+
+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 = depth(cont);
+
+ draw_point(search_point);
+
+ // 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_linestring(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 = depth(cont);
+ glVertex3f(x, y, z);
+ }
+
+ glEnd();
+}
+
+void draw_segment(S const& s)
+{
+ float x1 = boost::geometry::get<0, 0>(s);
+ float y1 = boost::geometry::get<0, 1>(s);
+ float x2 = boost::geometry::get<1, 0>(s);
+ float y2 = boost::geometry::get<1, 1>(s);
+ float z = depth(cont);
+
+ glBegin(GL_LINES);
+ glVertex3f(x1, y1, z);
+ glVertex3f(x2, y2, 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 = depth(cont);
+
+ // 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 = depth(cont);
+
+ // 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);
+}
+
+// render the scene -> tree, if searching data available also the query geometry and result
+
+void render_scene(void)
+{
+ glClear(GL_COLOR_BUFFER_BIT);
+
+ draw_tree(cont);
+
+ if ( search_valid )
+ {
+ glColor3f(1.0f, 0.25f, 0.0f);
+
+ if ( query_mode == qm_knn )
+ draw_knn_area(0, 0);
+ else if ( query_mode == qm_knnb )
+ draw_box(search_box);
+ else if ( query_mode == qm_knns )
+ draw_segment(search_segment);
+ 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_si )
+ draw_segment(search_segment);
+ else if ( query_mode == qm_lsi )
+ draw_linestring(search_linestring);
+ else if ( query_mode == qm_path )
+ draw_linestring(search_path);
+ else
+ draw_box(search_box);
+
+ glColor3f(1.0f, 0.5f, 0.0f);
+
+ draw_result(cont);
+ }
+
+ 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);
+}
+
+// randomize various indexables
+
+inline void rand_val(B & b)
+{
+ 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));
+}
+inline void rand_val(P & p)
+{
+ float x = ( rand() % 100 );
+ float y = ( rand() % 100 );
+ p = P(x, y);
+}
+inline void rand_val(S & s)
+{
+ float x = ( rand() % 100 );
+ float y = ( rand() % 100 );
+ float w = ( rand() % 2 + 1) * (rand() % 2 ? 1.0f : -1.0f);
+ float h = ( rand() % 2 + 1) * (rand() % 2 ? 1.0f : -1.0f);
+ s = S(P(x - w, y - h),P(x + w, y + h));
+}
+
+// more higher-level visitors
+
+struct insert_random_value_v : boost::static_visitor<>
+{
+ template <typename V>
+ void operator()(containers<V> & c) const
+ {
+ V v;
+ rand_val(v);
+
+ boost::geometry::index::insert(c.tree, v);
+ c.values.push_back(v);
+
+ std::cout << "inserted: ";
+ bgi::detail::utilities::print_indexable(std::cout, v);
+ std::cout << '\n';
+
+ std::cout << ( bgi::detail::rtree::utilities::are_boxes_ok(c.tree) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::detail::rtree::utilities::are_levels_ok(c.tree) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+ }
+};
+template <typename Cont>
+inline void insert_random_value(Cont & cont)
+{
+ return boost::apply_visitor(insert_random_value_v(), cont);
+}
+
+struct remove_random_value_v : boost::static_visitor<>
+{
+ template <typename V>
+ void operator()(containers<V> & c) const
+ {
+ if ( c.values.empty() )
+ return;
+
+ size_t i = rand() % c.values.size();
+ V v = c.values[i];
+
+ c.tree.remove(v);
+ c.values.erase(c.values.begin() + i);
+
+ std::cout << "removed: ";
+ bgi::detail::utilities::print_indexable(std::cout, v);
+ std::cout << '\n';
+
+ std::cout << ( bgi::detail::rtree::utilities::are_boxes_ok(c.tree) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::detail::rtree::utilities::are_levels_ok(c.tree) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+ }
+};
+template <typename Cont>
+inline void remove_random_value(Cont & cont)
+{
+ return boost::apply_visitor(remove_random_value_v(), cont);
+}
+
+// handle mouse input
+
+void mouse(int button, int state, int /*x*/, int /*y*/)
+{
+ if ( button == GLUT_LEFT_BUTTON && state == GLUT_DOWN )
+ {
+ insert_random_value(cont);
+ search_valid = false;
+ }
+ else if ( button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN )
+ {
+ remove_random_value(cont);
+ search_valid = false;
+ }
+ else if ( button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN )
+ {
+ search();
+ }
+
+ glutPostRedisplay();
+}
+
+// more higher-level visitors
+
+struct insert_random_values_v : boost::static_visitor<>
+{
+ template <typename V>
+ void operator()(containers<V> & c) const
+ {
+ for ( size_t i = 0 ; i < 35 ; ++i )
+ {
+ V v;
+ rand_val(v);
+
+ c.tree.insert(v);
+ c.values.push_back(v);
+
+ std::cout << "inserted: ";
+ bgi::detail::utilities::print_indexable(std::cout, v);
+ std::cout << '\n';
+ }
+
+ std::cout << ( bgi::detail::rtree::utilities::are_boxes_ok(c.tree) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::detail::rtree::utilities::are_levels_ok(c.tree) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+ }
+};
+template <typename Cont>
+inline void insert_random_values(Cont & cont)
+{
+ return boost::apply_visitor(insert_random_values_v(), cont);
+}
+
+struct bulk_insert_random_values_v : boost::static_visitor<>
+{
+ template <typename V>
+ void operator()(containers<V> & c) const
+ {
+ c.values.clear();
+
+ for ( size_t i = 0 ; i < 35 ; ++i )
+ {
+ V v;
+ rand_val(v);
+
+ c.values.push_back(v);
+
+ std::cout << "inserted: ";
+ bgi::detail::utilities::print_indexable(std::cout, v);
+ std::cout << '\n';
+ }
+
+ create(c.tree, c.values);
+
+ std::cout << ( bgi::detail::rtree::utilities::are_boxes_ok(c.tree) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::detail::rtree::utilities::are_levels_ok(c.tree) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+ }
+
+ template <typename Tree, typename Values>
+ void create(Tree & tree, Values const& values) const
+ {
+ Tree t(values);
+ tree = boost::move(t);
+ }
+};
+template <typename Cont>
+inline void bulk_insert_random_values(Cont & cont)
+{
+ return boost::apply_visitor(bulk_insert_random_values_v(), cont);
+}
+
+// handle keyboard input
+
+std::string current_line;
+
+void keyboard(unsigned char key, int /*x*/, int /*y*/)
+{
+ if ( key == '\r' || key == '\n' )
+ {
+ if ( current_line == "storeb" )
+ {
+ cont = containers<B>();
+ glutPostRedisplay();
+ }
+#ifdef ENABLE_POINTS_AND_SEGMENTS
+ else if ( current_line == "storep" )
+ {
+ cont = containers<P>();
+ glutPostRedisplay();
+ }
+ else if ( current_line == "stores" )
+ {
+ cont = containers<S>();
+ glutPostRedisplay();
+ }
+#endif
+ else if ( current_line == "t" )
+ {
+ std::cout << "\n";
+ print_tree(cont);
+ std::cout << "\n";
+ }
+ else if ( current_line == "rand" )
+ {
+ insert_random_values(cont);
+ search_valid = false;
+
+ glutPostRedisplay();
+ }
+ else if ( current_line == "bulk" )
+ {
+ bulk_insert_random_values(cont);
+ search_valid = false;
+
+ glutPostRedisplay();
+ }
+ else
+ {
+ if ( current_line == "knn" )
+ query_mode = qm_knn;
+ else if ( current_line == "knnb" )
+ query_mode = qm_knnb;
+ else if ( current_line == "knns" )
+ query_mode = qm_knns;
+ 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 == "si" )
+ query_mode = qm_si;
+ else if ( current_line == "lsi" )
+ query_mode = qm_lsi;
+ else if ( current_line == "path" )
+ query_mode = qm_path;
+
+ search();
+ glutPostRedisplay();
+ }
+
+ current_line.clear();
+ std::cout << '\n';
+ }
+ else
+ {
+ current_line += key;
+ std::cout << key;
+ }
+}
+
+// main function
+
+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/src/boost/libs/geometry/index/example/random_test.cpp b/src/boost/libs/geometry/index/example/random_test.cpp
new file mode 100644
index 00000000..1c40d155
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/random_test.cpp
@@ -0,0 +1,185 @@
+// 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.hpp>
+#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;
+}
diff --git a/src/boost/libs/geometry/index/example/serialize.cpp b/src/boost/libs/geometry/index/example/serialize.cpp
new file mode 100644
index 00000000..11ce08bc
--- /dev/null
+++ b/src/boost/libs/geometry/index/example/serialize.cpp
@@ -0,0 +1,168 @@
+// 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 <fstream>
+
+#define BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+
+#include <boost/geometry.hpp>
+#include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/statistics.hpp>
+
+#include <boost/archive/binary_oarchive.hpp>
+#include <boost/archive/binary_iarchive.hpp>
+#include <boost/archive/xml_oarchive.hpp>
+#include <boost/archive/xml_iarchive.hpp>
+#include <boost/serialization/vector.hpp>
+
+#include <boost/foreach.hpp>
+#include <boost/timer.hpp>
+
+template <typename T, size_t I = 0, size_t S = boost::tuples::length<T>::value>
+struct print_tuple
+{
+ template <typename Os>
+ static inline Os & apply(Os & os, T const& t)
+ {
+ os << boost::get<I>(t) << ", ";
+ return print_tuple<T, I+1>::apply(os, t);
+ }
+};
+
+template <typename T, size_t S>
+struct print_tuple<T, S, S>
+{
+ template <typename Os>
+ static inline Os & apply(Os & os, T const&)
+ {
+ return os;
+ }
+};
+
+int main()
+{
+ namespace bg = boost::geometry;
+ namespace bgi = bg::index;
+
+ typedef boost::tuple<std::size_t, std::size_t, std::size_t, std::size_t, std::size_t, std::size_t> S;
+
+ typedef bg::model::point<double, 2, bg::cs::cartesian> P;
+ typedef bg::model::box<P> B;
+ typedef B V;
+ //typedef bgi::rtree<V, bgi::linear<16> > RT;
+ //typedef bgi::rtree<V, bgi::quadratic<8, 3> > RT;
+ //typedef bgi::rtree<V, bgi::rstar<8, 3> > RT;
+ typedef bgi::rtree<V, bgi::dynamic_linear > RT;
+
+ //RT tree;
+ RT tree(bgi::dynamic_linear(16));
+ std::vector<V> vect;
+
+ boost::timer t;
+
+ //insert values
+ {
+ for ( double x = 0 ; x < 1000 ; x += 1 )
+ for ( double y = 0 ; y < 1000 ; y += 1 )
+ vect.push_back(B(P(x, y), P(x+0.5, y+0.5)));
+ RT tmp(vect, tree.parameters());
+ tree = boost::move(tmp);
+ }
+ B q(P(5, 5), P(6, 6));
+ S s;
+
+ std::cout << "vector and tree created in: " << t.elapsed() << std::endl;
+
+ print_tuple<S>::apply(std::cout, bgi::detail::rtree::utilities::statistics(tree)) << std::endl;
+ std::cout << boost::get<0>(s) << std::endl;
+ BOOST_FOREACH(V const& v, tree | bgi::adaptors::queried(bgi::intersects(q)))
+ std::cout << bg::wkt<V>(v) << std::endl;
+
+ // save
+ {
+ std::ofstream ofs("serialized_vector.bin", std::ios::binary | std::ios::trunc);
+ boost::archive::binary_oarchive oa(ofs);
+ t.restart();
+ oa << vect;
+ std::cout << "vector saved to bin in: " << t.elapsed() << std::endl;
+ }
+ {
+ std::ofstream ofs("serialized_tree.bin", std::ios::binary | std::ios::trunc);
+ boost::archive::binary_oarchive oa(ofs);
+ t.restart();
+ oa << tree;
+ std::cout << "tree saved to bin in: " << t.elapsed() << std::endl;
+ }
+ {
+ std::ofstream ofs("serialized_tree.xml", std::ios::trunc);
+ boost::archive::xml_oarchive oa(ofs);
+ t.restart();
+ oa << boost::serialization::make_nvp("rtree", tree);
+ std::cout << "tree saved to xml in: " << t.elapsed() << std::endl;
+ }
+
+ t.restart();
+ vect.clear();
+ std::cout << "vector cleared in: " << t.elapsed() << std::endl;
+
+ t.restart();
+ tree.clear();
+ std::cout << "tree cleared in: " << t.elapsed() << std::endl;
+
+ // load
+
+ {
+ std::ifstream ifs("serialized_vector.bin", std::ios::binary);
+ boost::archive::binary_iarchive ia(ifs);
+ t.restart();
+ ia >> vect;
+ std::cout << "vector loaded from bin in: " << t.elapsed() << std::endl;
+ t.restart();
+ RT tmp(vect, tree.parameters());
+ tree = boost::move(tmp);
+ std::cout << "tree rebuilt from vector in: " << t.elapsed() << std::endl;
+ }
+
+ t.restart();
+ tree.clear();
+ std::cout << "tree cleared in: " << t.elapsed() << std::endl;
+
+ {
+ std::ifstream ifs("serialized_tree.bin", std::ios::binary);
+ boost::archive::binary_iarchive ia(ifs);
+ t.restart();
+ ia >> tree;
+ std::cout << "tree loaded from bin in: " << t.elapsed() << std::endl;
+ }
+
+ std::cout << "loaded from bin" << std::endl;
+ print_tuple<S>::apply(std::cout, bgi::detail::rtree::utilities::statistics(tree)) << std::endl;
+ BOOST_FOREACH(V const& v, tree | bgi::adaptors::queried(bgi::intersects(q)))
+ std::cout << bg::wkt<V>(v) << std::endl;
+
+ t.restart();
+ tree.clear();
+ std::cout << "tree cleared in: " << t.elapsed() << std::endl;
+
+ {
+ std::ifstream ifs("serialized_tree.xml");
+ boost::archive::xml_iarchive ia(ifs);
+ t.restart();
+ ia >> boost::serialization::make_nvp("rtree", tree);
+ std::cout << "tree loaded from xml in: " << t.elapsed() << std::endl;
+ }
+
+ std::cout << "loaded from xml" << std::endl;
+ print_tuple<S>::apply(std::cout, bgi::detail::rtree::utilities::statistics(tree)) << std::endl;
+ BOOST_FOREACH(V const& v, tree | bgi::adaptors::queried(bgi::intersects(q)))
+ std::cout << bg::wkt<V>(v) << std::endl;
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-23 17:17:41 +0000