|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74438 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/algorithms/detail tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-17 14:41:37
Author: awulkiew
Date: 2011-09-17 14:41:36 EDT (Sat, 17 Sep 2011)
New Revision: 74438
URL: http://svn.boost.org/trac/boost/changeset/74438
Log:
maxdist algorithm added
Added:
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/diff_abs.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/maxdist.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/minmaxdist.hpp | 71 +++-----------------------
sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp | 106 ++++++++++++++++++++++++++++++++++++---
2 files changed, 107 insertions(+), 70 deletions(-)
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/diff_abs.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/diff_abs.hpp 2011-09-17 14:41:36 EDT (Sat, 17 Sep 2011)
@@ -0,0 +1,27 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - Abs of difference
+//
+// Copyright 2011 Adam Wulkiewicz.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_DIFF_ABS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_DIFF_ABS_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+template <typename T>
+inline T diff_abs(T const& v1, T const& v2)
+{
+ return v1 < v2 ? v2 - v1 : v1 - v2;
+}
+
+} // namespace detail
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_DIFF_ABS_HPP
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/maxdist.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/maxdist.hpp 2011-09-17 14:41:36 EDT (Sat, 17 Sep 2011)
@@ -0,0 +1,69 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - maxdist used in R-tree k nearest neighbors query
+//
+// Copyright 2011 Adam Wulkiewicz.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MAXDIST_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MAXDIST_HPP
+
+#include <boost/geometry/extensions/index/algorithms/detail/diff_abs.hpp>
+#include <boost/geometry/extensions/index/algorithms/detail/sum_for_indexable.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+// minmaxdist component
+
+struct maxdist_tag {};
+
+template <
+ typename Point,
+ typename BoxIndexable,
+ size_t DimensionIndex>
+struct sum_for_indexable_dimension<Point, BoxIndexable, box_tag, maxdist_tag, DimensionIndex>
+{
+ typedef typename geometry::default_distance_result<Point, BoxIndexable>::type result_type;
+
+ inline static result_type apply(Point const& pt, BoxIndexable const& i)
+ {
+ typedef typename index::traits::coordinate_type<Point>::type point_coord_t;
+ typedef typename index::traits::coordinate_type<BoxIndexable>::type indexable_coord_t;
+
+ point_coord_t pt_c = geometry::get<DimensionIndex>(pt);
+ indexable_coord_t ind_c_min = geometry::get<geometry::min_corner, DimensionIndex>(i);
+ indexable_coord_t ind_c_max = geometry::get<geometry::max_corner, DimensionIndex>(i);
+
+ result_type further_diff = 0;
+
+ if ( (ind_c_min + ind_c_max) / 2 <= pt_c )
+ further_diff = pt_c - ind_c_min;
+ else
+ further_diff = detail::diff_abs(pt_c, ind_c_max); // unsigned values protection
+
+ return further_diff * further_diff;
+ }
+};
+
+} // namespace detail
+
+template <typename Point, typename Indexable>
+typename geometry::default_distance_result<Point, Indexable>::type
+maxdist(Point const& pt, Indexable const& i)
+{
+ return sum_for_indexable<
+ Point,
+ Indexable,
+ typename index::traits::tag<Indexable>::type,
+ maxdist_tag,
+ index::traits::dimension<Indexable>::value
+ >::apply(pt, i);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MAXDIST_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/minmaxdist.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/minmaxdist.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/minmaxdist.hpp 2011-09-17 14:41:36 EDT (Sat, 17 Sep 2011)
@@ -10,67 +10,16 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MINMAXDIST_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MINMAXDIST_HPP
+#include <boost/geometry/extensions/index/algorithms/detail/diff_abs.hpp>
#include <boost/geometry/extensions/index/algorithms/detail/sum_for_indexable.hpp>
#include <boost/geometry/extensions/index/algorithms/detail/smallest_for_indexable.hpp>
+#include <boost/geometry/extensions/index/algorithms/maxdist.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail {
-// awulkiew - use if unsigned values may be used as coordinates
-template <typename T>
-inline T diff_abs(T const& v1, T const& v2)
-{
- return v1 < v2 ? v2 - v1 : v1 - v2;
-}
-
-// minmaxdist component
-
-struct minmaxdist_comp_tag {};
-
-template <
- typename Point,
- typename BoxIndexable,
- size_t DimensionIndex>
-struct sum_for_indexable_dimension<Point, BoxIndexable, box_tag, minmaxdist_comp_tag, DimensionIndex>
-{
- typedef typename geometry::default_distance_result<Point, BoxIndexable>::type result_type;
-
- inline static result_type apply(Point const& pt, BoxIndexable const& i)
- {
- typedef typename index::traits::coordinate_type<Point>::type point_coord_t;
- typedef typename index::traits::coordinate_type<BoxIndexable>::type indexable_coord_t;
-
- point_coord_t pt_c = geometry::get<DimensionIndex>(pt);
- indexable_coord_t ind_c_min = geometry::get<geometry::min_corner, DimensionIndex>(i);
- indexable_coord_t ind_c_max = geometry::get<geometry::max_corner, DimensionIndex>(i);
-
- result_type further_diff = 0;
-
- if ( (ind_c_min + ind_c_max) / 2 <= pt_c )
- further_diff = pt_c - ind_c_min;
- else
- further_diff = diff_abs(pt_c, ind_c_max); // unsigned values protection
-
- return further_diff * further_diff;
- }
-};
-
-template <typename Point, typename Indexable>
-typename geometry::default_distance_result<Point, Indexable>::type
-minmaxdist_comp(Point const& pt, Indexable const& i)
-{
- return sum_for_indexable<
- Point,
- Indexable,
- typename index::traits::tag<Indexable>::type,
- minmaxdist_comp_tag,
- index::traits::dimension<Indexable>::value
- >::apply(pt, i);
-}
-
-// minmaxdist
-
struct minmaxdist_tag {};
template <
@@ -81,7 +30,7 @@
{
typedef typename geometry::default_distance_result<Point, BoxIndexable>::type result_type;
- inline static result_type apply(Point const& pt, BoxIndexable const& i, result_type const& comp)
+ inline static result_type apply(Point const& pt, BoxIndexable const& i, result_type const& maxd)
{
typedef typename index::traits::coordinate_type<Point>::type point_coord_t;
typedef typename index::traits::coordinate_type<BoxIndexable>::type indexable_coord_t;
@@ -97,17 +46,17 @@
result_type closer_comp = 0;
if ( pt_c <= ind_c_avg )
- closer_comp = diff_abs(pt_c, ind_c_min); // unsigned values protection
+ closer_comp = detail::diff_abs(pt_c, ind_c_min); // unsigned values protection
else
- closer_comp = diff_abs(pt_c, ind_c_max); // unsigned values protection
+ closer_comp = detail::diff_abs(pt_c, ind_c_max); // unsigned values protection
result_type further_comp = 0;
if ( ind_c_avg <= pt_c )
further_comp = pt_c - ind_c_min;
else
- further_comp = diff_abs(pt_c, ind_c_max); // unsigned values protection
+ further_comp = detail::diff_abs(pt_c, ind_c_max); // unsigned values protection
- return (comp + closer_comp * closer_comp) - further_comp * further_comp;
+ return (maxd + closer_comp * closer_comp) - further_comp * further_comp;
}
};
@@ -138,7 +87,7 @@
inline static result_type apply(Point const& pt, Indexable const& i)
{
- result_type comp = minmaxdist_comp(pt, i);
+ result_type maxd = maxdist(pt, i);
return smallest_for_indexable<
Point,
@@ -146,7 +95,7 @@
box_tag,
minmaxdist_tag,
index::traits::dimension<Indexable>::value
- >::apply(pt, i, comp);
+ >::apply(pt, i, maxd);
}
};
Modified: sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp 2011-09-17 14:41:36 EDT (Sat, 17 Sep 2011)
@@ -114,7 +114,8 @@
// elements inserting test
{
- std::cout << "inserting time test...\n";
+ std::cout << "rtree inserting time test... ("
+ << values_count << ")\n";
tim.restart();
for (size_t i = 0 ; i < values_count ; ++i )
{
@@ -127,6 +128,24 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
+ std::vector< std::pair<B, size_t> > v;
+
+ // elements inserting test
+ {
+ std::cout << "vector inserting time test... ("
+ << values_count << ")\n";
+ tim.restart();
+ 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));
+
+ v.push_back(std::make_pair(b, i));
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ }
+
// check
if ( bgi::are_boxes_ok(t) )
std::cout << "BOXES OK\n";
@@ -139,7 +158,8 @@
// searching test
{
- std::cout << "query(intersects(B)) searching time test...\n";
+ std::cout << "query(intersects(B)) searching time test... ("
+ << queries_count << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count ; ++i )
@@ -156,7 +176,8 @@
// searching test
{
- std::cout << "query(B) searching time test...\n";
+ std::cout << "query(B) searching time test... ("
+ << queries_count << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count ; ++i )
@@ -173,7 +194,36 @@
// searching test
{
- std::cout << "nearest searching time test...\n";
+ std::cout << "vector searching time test... ("
+ << queries_count / 1000 << ")\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 1000 ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result;
+ for ( std::vector< std::pair<B, size_t> >::const_iterator it = v.begin();
+ it != v.end() ;
+ ++it )
+ {
+ if ( bg::intersects(
+ it->first,
+ B(P(x - 10, y - 10), P(x + 10, y + 10))
+ )
+ )
+ result.push_back(*it);
+ }
+ temp += result.size();
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << "found: " << temp << "\n";
+ }
+
+ // searching test
+ {
+ std::cout << "nearest searching time test... ("
+ << queries_count / 10 << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count / 10 ; ++i )
@@ -189,7 +239,8 @@
// searching test
{
- std::cout << "nearest searching time test...\n";
+ std::cout << "nearest 5 searching time test... ("
+ << queries_count / 10 << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count / 10 ; ++i )
@@ -203,9 +254,43 @@
std::cout << "found: " << temp << "\n";
}
+ // searching test
+ {
+ std::cout << "vector nearest searching time test... ("
+ << queries_count / 1000 << ")\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 1000 ; ++i )
+ {
+ typedef bg::default_distance_result<P, B>::type distance_type;
+
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ std::pair<B, size_t> result;
+ distance_type dist = std::numeric_limits<distance_type>::max();
+
+ for ( std::vector< std::pair<B, size_t> >::const_iterator it = v.begin();
+ it != v.end();
+ ++it )
+ {
+ distance_type cd = bgi::mindist(P(x, y), it->first);
+
+ if ( cd < dist )
+ {
+ result = *it;
+ dist = cd;
+ }
+ }
+ temp += dist < std::numeric_limits<distance_type>::max() ? 1 : 0;
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << "found: " << temp << "\n";
+ }
+
// elements removing test
{
- std::cout << "removing time test...\n";
+ std::cout << "removing time test... ("
+ << remove_count << ")\n";
tim.restart();
for (size_t i = 0 ; i < remove_count ; ++i )
{
@@ -230,7 +315,8 @@
// searching test
{
- std::cout << "searching time test...\n";
+ std::cout << "searching time test... ("
+ << queries_count << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count ; ++i )
@@ -247,7 +333,8 @@
// inserting test
{
- std::cout << "inserting time test...\n";
+ std::cout << "inserting time test... ("
+ << remove_count << ")\n";
tim.restart();
for (size_t i = 0 ; i < remove_count ; ++i )
{
@@ -272,7 +359,8 @@
// searching test
{
- std::cout << "searching time test...\n";
+ std::cout << "searching time test... ("
+ << queries_count << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count ; ++i )
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk