summaryrefslogtreecommitdiff
path: root/libs/geometry/index
diff options
context:
space:
mode:
Diffstat (limited to 'libs/geometry/index')
-rw-r--r--libs/geometry/index/example/benchmark_insert.cpp196
-rw-r--r--libs/geometry/index/test/Jamfile.v25
-rw-r--r--libs/geometry/index/test/rtree/Jamfile.v21
-rw-r--r--libs/geometry/index/test/rtree/exceptions/Jamfile.v21
-rw-r--r--libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp8
-rw-r--r--libs/geometry/index/test/rtree/generated/Jamfile.v21
-rw-r--r--libs/geometry/index/test/rtree/interprocess/Jamfile.v22
-rw-r--r--libs/geometry/index/test/rtree/rtree_move_pack.cpp134
-rw-r--r--libs/geometry/index/test/rtree/rtree_values.cpp86
9 files changed, 419 insertions, 15 deletions
diff --git a/libs/geometry/index/example/benchmark_insert.cpp b/libs/geometry/index/example/benchmark_insert.cpp
new file mode 100644
index 000000000..4fe82e91f
--- /dev/null
+++ b/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/libs/geometry/index/test/Jamfile.v2 b/libs/geometry/index/test/Jamfile.v2
index c2a192e1c..f19f6834c 100644
--- a/libs/geometry/index/test/Jamfile.v2
+++ b/libs/geometry/index/test/Jamfile.v2
@@ -15,12 +15,15 @@ project boost-geometry-index-test
<include>../../test # libs/geometry/test
#<include>../../../../boost/geometry/extensions/contrib/ttmath
<toolset>msvc:<asynch-exceptions>on
+ <toolset>msvc:<cxxflags>/bigobj
+ <host-os>windows,<toolset>intel:<cxxflags>/bigobj
+ <library>/boost/timer//boost_timer
;
test-suite boost-geometry-index-varray
:
[ run varray_old.cpp ]
- [ run varray.cpp : : : <toolset>msvc:<cxxflags>/bigobj ]
+ [ run varray.cpp ]
;
build-project algorithms ;
diff --git a/libs/geometry/index/test/rtree/Jamfile.v2 b/libs/geometry/index/test/rtree/Jamfile.v2
index 463ccb3fa..23578b4e9 100644
--- a/libs/geometry/index/test/rtree/Jamfile.v2
+++ b/libs/geometry/index/test/rtree/Jamfile.v2
@@ -12,6 +12,7 @@ build-project generated ;
test-suite boost-geometry-index-rtree
:
+ [ run rtree_move_pack.cpp ]
[ run rtree_values.cpp ]
[ compile-fail rtree_values_invalid.cpp ]
;
diff --git a/libs/geometry/index/test/rtree/exceptions/Jamfile.v2 b/libs/geometry/index/test/rtree/exceptions/Jamfile.v2
index 1728b245b..84855c4fd 100644
--- a/libs/geometry/index/test/rtree/exceptions/Jamfile.v2
+++ b/libs/geometry/index/test/rtree/exceptions/Jamfile.v2
@@ -17,6 +17,7 @@ rule test_all
: # test-files
: # requirements
<toolset>msvc:<cxxflags>/bigobj
+ <host-os>windows,<toolset>intel:<cxxflags>/bigobj
] ;
}
diff --git a/libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp b/libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp
index d32c6bcca..4aa0ef750 100644
--- a/libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp
+++ b/libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp
@@ -174,9 +174,13 @@ struct visitor<Value, Parameters, Box, Allocators, node_throwing_static_tag, IsV
// allocators
template <typename Allocator, typename Value, typename Parameters, typename Box>
-struct allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>
+class allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>
: public Allocator::template rebind<
- typename node<Value, Parameters, Box, allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>, node_throwing_static_tag>::type
+ typename node<
+ Value, Parameters, Box,
+ allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>,
+ node_throwing_static_tag
+ >::type
>::other
{
typedef typename Allocator::template rebind<
diff --git a/libs/geometry/index/test/rtree/generated/Jamfile.v2 b/libs/geometry/index/test/rtree/generated/Jamfile.v2
index f3900741b..a5a6f3e41 100644
--- a/libs/geometry/index/test/rtree/generated/Jamfile.v2
+++ b/libs/geometry/index/test/rtree/generated/Jamfile.v2
@@ -17,6 +17,7 @@ rule test_all
: # test-files
: # requirements
<toolset>msvc:<cxxflags>/bigobj
+ <host-os>windows,<toolset>intel:<cxxflags>/bigobj
] ;
}
diff --git a/libs/geometry/index/test/rtree/interprocess/Jamfile.v2 b/libs/geometry/index/test/rtree/interprocess/Jamfile.v2
index 9e8a05f2a..1a52eb953 100644
--- a/libs/geometry/index/test/rtree/interprocess/Jamfile.v2
+++ b/libs/geometry/index/test/rtree/interprocess/Jamfile.v2
@@ -23,6 +23,8 @@ rule test_all
<toolset>gcc,<target-os>windows:<linkflags>"-lole32 -loleaut32 -lpsapi -ladvapi32"
<host-os>windows,<toolset>clang:<linkflags>"-lole32 -loleaut32 -lpsapi -ladvapi32"
<toolset>msvc:<cxxflags>/bigobj
+ <host-os>windows,<toolset>intel:<cxxflags>/bigobj
+ <host-os>linux:<linkflags>"-lrt"
] ;
}
diff --git a/libs/geometry/index/test/rtree/rtree_move_pack.cpp b/libs/geometry/index/test/rtree/rtree_move_pack.cpp
new file mode 100644
index 000000000..b7210772d
--- /dev/null
+++ b/libs/geometry/index/test/rtree/rtree_move_pack.cpp
@@ -0,0 +1,134 @@
+// Boost.Geometry Index
+// Unit Test
+
+// Copyright (c) 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 <rtree/test_rtree.hpp>
+
+#include <algorithm>
+#include <boost/container/vector.hpp>
+#include <boost/move/move.hpp>
+#include <boost/move/iterator.hpp>
+
+#include <boost/geometry/geometries/register/point.hpp>
+
+class point_cm
+{
+ BOOST_COPYABLE_AND_MOVABLE(point_cm)
+
+public:
+ point_cm(double xx = 0, double yy = 0)
+ : x(xx)
+ , y(yy)
+ , moved(false)
+ {}
+ point_cm(point_cm const& other)
+ : x(other.x)
+ , y(other.y)
+ , moved(false)
+ {
+ BOOST_CHECK_MESSAGE(false, "copy not allowed");
+ }
+ point_cm & operator=(BOOST_COPY_ASSIGN_REF(point_cm) other)
+ {
+ BOOST_CHECK_MESSAGE(false, "copy not allowed");
+ x = other.x;
+ y = other.y;
+ moved = false;
+ return *this;
+ }
+ point_cm(BOOST_RV_REF(point_cm) other)
+ : x(other.x)
+ , y(other.y)
+ , moved(false)
+ {
+ BOOST_CHECK_MESSAGE(!other.moved, "only one move allowed");
+ other.moved = true;
+ }
+ point_cm & operator=(BOOST_RV_REF(point_cm) other)
+ {
+ BOOST_CHECK_MESSAGE(!other.moved, "only one move allowed");
+ x = other.x;
+ y = other.y;
+ moved = false;
+ other.moved = true;
+ return *this;
+ }
+
+ double x, y;
+ bool moved;
+};
+
+template <typename Point>
+struct indexable
+{
+ typedef Point const& result_type;
+ result_type operator()(Point const& p) const
+ {
+ BOOST_CHECK_MESSAGE(!p.moved, "can't access indexable of moved Value");
+ return p;
+ }
+};
+
+BOOST_GEOMETRY_REGISTER_POINT_2D(point_cm, double, bg::cs::cartesian, x, y)
+
+template <typename Vector>
+void append(Vector & vec, double x, double y)
+{
+ point_cm pt(x, y);
+ BOOST_CHECK(!pt.moved);
+ vec.push_back(boost::move(pt));
+ BOOST_CHECK(pt.moved);
+}
+
+struct test_moved
+{
+ test_moved(bool ex)
+ : expected(ex)
+ {}
+ template <typename Point>
+ void operator()(Point const& p) const
+ {
+ BOOST_CHECK_EQUAL(p.moved, expected);
+ }
+ bool expected;
+};
+
+template <typename Point, typename Params>
+void test_rtree(Params const& params = Params())
+{
+ // sanity check
+ boost::container::vector<Point> vec;
+ append(vec, 0, 0); append(vec, 0, 1); append(vec, 0, 2);
+ append(vec, 1, 0); append(vec, 1, 1); append(vec, 1, 2);
+ append(vec, 2, 0); append(vec, 2, 1); append(vec, 2, 2);
+
+ std::for_each(vec.begin(), vec.end(), test_moved(false));
+
+ bgi::rtree<Point, Params, indexable<Point> > rt(
+ boost::make_move_iterator(vec.begin()),
+ boost::make_move_iterator(vec.end()),
+ params);
+
+ std::for_each(vec.begin(), vec.end(), test_moved(true));
+
+ BOOST_CHECK_EQUAL(rt.size(), vec.size());
+}
+
+
+int test_main(int, char* [])
+{
+ test_rtree< point_cm, bgi::linear<4> >();
+ test_rtree< point_cm, bgi::quadratic<4> >();
+ test_rtree< point_cm, bgi::rstar<4> >();
+
+ test_rtree<point_cm>(bgi::dynamic_linear(4));
+ test_rtree<point_cm>(bgi::dynamic_quadratic(4));
+ test_rtree<point_cm>(bgi::dynamic_rstar(4));
+
+ return 0;
+}
diff --git a/libs/geometry/index/test/rtree/rtree_values.cpp b/libs/geometry/index/test/rtree/rtree_values.cpp
index 2a9c3a0dd..e9eb13810 100644
--- a/libs/geometry/index/test/rtree/rtree_values.cpp
+++ b/libs/geometry/index/test/rtree/rtree_values.cpp
@@ -1,7 +1,7 @@
// Boost.Geometry Index
// Unit Test
-// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
+// Copyright (c) 2014-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
@@ -9,8 +9,10 @@
#include <rtree/test_rtree.hpp>
+#include <boost/core/addressof.hpp>
#include <boost/geometry/geometries/register/point.hpp>
+#include <boost/geometry/geometries/polygon.hpp>
struct point
{
@@ -20,6 +22,30 @@ struct point
BOOST_GEOMETRY_REGISTER_POINT_2D(point, double, bg::cs::cartesian, x, y)
+template <typename Rtree, typename Convertible>
+void check_convertible_to_value(Rtree const& rt, Convertible const& conv)
+{
+ static const bool
+ is_conv_to_indexable
+ = boost::is_convertible<Convertible, typename Rtree::indexable_type>::value;
+ static const bool
+ is_conv_to_value
+ = boost::is_convertible<Convertible, typename Rtree::value_type>::value;
+ static const bool
+ is_same_as_indexable
+ = boost::is_same<Convertible, typename Rtree::indexable_type>::value;
+ static const bool
+ is_same_as_value
+ = boost::is_same<Convertible, typename Rtree::value_type>::value;
+
+ BOOST_CHECK_EQUAL(is_same_as_indexable, false);
+ BOOST_CHECK_EQUAL(is_same_as_value, false);
+ BOOST_CHECK_EQUAL(is_conv_to_indexable, false);
+ BOOST_CHECK_EQUAL(is_conv_to_value, true);
+
+ typename Rtree::value_type const& val = conv;
+ BOOST_CHECK(rt.value_eq()(val, conv));
+}
template <typename Box, typename Params>
void test_pair()
@@ -41,17 +67,49 @@ void test_pair()
rt.insert(val);
rt.insert(std::make_pair(box, 0));
rt.insert(std::make_pair(box, (unsigned short)0));
- BOOST_CHECK( rt.size() == 3 );
+ BOOST_CHECK_EQUAL(rt.size(), 3u);
+
+ check_convertible_to_value(rt, std::make_pair(box, 0));
+ check_convertible_to_value(rt, std::make_pair(box, (unsigned short)0));
+ BOOST_CHECK(bg::covered_by(rt.indexable_get()(std::make_pair(box, 0)), rt.bounds()));
+ BOOST_CHECK(bg::covered_by(rt.indexable_get()(std::make_pair(box, (unsigned short)0)), rt.bounds()));
+
+ BOOST_CHECK_EQUAL(rt.count(val), 3u);
+ BOOST_CHECK_EQUAL(rt.count(std::make_pair(box, 0)), 3u);
+ BOOST_CHECK_EQUAL(rt.count(std::make_pair(box, (unsigned short)0)), 3u);
+ BOOST_CHECK_EQUAL(rt.count(box), 3u);
+
+ BOOST_CHECK_EQUAL(rt.remove(val), 1u);
+ BOOST_CHECK_EQUAL(rt.remove(std::make_pair(box, 0)), 1u);
+ BOOST_CHECK_EQUAL(rt.remove(std::make_pair(box, (unsigned short)0)), 1u);
+ BOOST_CHECK_EQUAL(rt.size(), 0u);
+}
- BOOST_CHECK( rt.count(val) == 3 );
- BOOST_CHECK( rt.count(std::make_pair(box, 0)) == 3 );
- BOOST_CHECK( rt.count(std::make_pair(box, (unsigned short)0)) == 3 );
- BOOST_CHECK( rt.count(box) == 3 );
+template <typename Box, typename Params>
+void test_pair_geom_ptr()
+{
+ typedef typename bg::point_type<Box>::type point_t;
+ typedef bg::model::polygon<point_t> polygon_t;
+
+ typedef std::pair<Box, polygon_t*> Value;
+
+ typename boost::remove_const<Box>::type box;
+ bg::assign_zero(box);
- BOOST_CHECK( rt.remove(val) == 1 );
- BOOST_CHECK( rt.remove(std::make_pair(box, 0)) == 1 );
- BOOST_CHECK( rt.remove(std::make_pair(box, (unsigned short)0)) == 1 );
- BOOST_CHECK( rt.size() == 0 );
+ polygon_t poly;
+
+ Value val(box, boost::addressof(poly));
+
+ bgi::rtree<Value, Params> rt;
+ rt.insert(val);
+ rt.insert(std::make_pair(box, boost::addressof(poly)));
+
+ BOOST_CHECK_EQUAL(rt.size(), 2u);
+
+ BOOST_CHECK_EQUAL(rt.remove(val), 1u);
+ BOOST_CHECK_EQUAL(rt.remove(std::make_pair(box, boost::addressof(poly))), 1u);
+
+ BOOST_CHECK_EQUAL(rt.size(), 0u);
}
template <typename Params>
@@ -60,8 +118,8 @@ void test_point()
bgi::rtree<point, Params> rt;
rt.insert(0.0);
- BOOST_CHECK( rt.size() == 1 );
- BOOST_CHECK( rt.remove(0.0) == 1 );
+ BOOST_CHECK_EQUAL(rt.size(), 1u);
+ BOOST_CHECK_EQUAL(rt.remove(0.0), 1u);
}
int test_main(int, char* [])
@@ -76,6 +134,10 @@ int test_main(int, char* [])
//test_rtree< Box const, bgi::quadratic<4> >();
//test_rtree< Box const, bgi::rstar<4> >();
+ test_pair_geom_ptr< Box, bgi::linear<16> >();
+ test_pair_geom_ptr< Box, bgi::quadratic<4> >();
+ test_pair_geom_ptr< Box, bgi::rstar<4> >();
+
test_point< bgi::linear<16> >();
test_point< bgi::quadratic<4> >();
test_point< bgi::rstar<4> >();
View Lorry Controller Status