Subject: [Boost-commit] svn:boost r84861 - in trunk/boost/geometry: extensions/nsphere extensions/nsphere/index/detail/rtree extensions/nsphere/index/detail/rtree/linear index/detail/rtree/linear
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-21 11:09:09
Author: awulkiew
Date: 2013-06-21 11:09:08 EDT (Fri, 21 Jun 2013)
New Revision: 84861
URL: http://svn.boost.org/trac/boost/changeset/84861
Log:
[geometry]: [index] rtree linear algorithm can now handle nspheres, [extensions] linear find_greatest_normalized_separation implemented for nsphere.
Added:
trunk/boost/geometry/extensions/nsphere/index/detail/rtree/
trunk/boost/geometry/extensions/nsphere/index/detail/rtree/linear/
trunk/boost/geometry/extensions/nsphere/index/detail/rtree/linear/redistribute_elements.hpp (contents, props changed)
Text files modified:
trunk/boost/geometry/extensions/nsphere/index/detail/rtree/linear/redistribute_elements.hpp | 109 ++++++++++++++++++++++++++++++++++++++++
trunk/boost/geometry/extensions/nsphere/nsphere.hpp | 2
trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp | 6 +-
3 files changed, 114 insertions(+), 3 deletions(-)
Added: trunk/boost/geometry/extensions/nsphere/index/detail/rtree/linear/redistribute_elements.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/index/detail/rtree/linear/redistribute_elements.hpp 2013-06-21 11:09:08 EDT (Fri, 21 Jun 2013) (r84861)
@@ -0,0 +1,109 @@
+// Boost.Geometry Index
+//
+// R-tree linear split algorithm implementation
+//
+// Copyright (c) 2008 Federico J. Fernandez.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
+
+#include <boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace linear {
+
+template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex>
+struct find_greatest_normalized_separation<Elements, Parameters, Translator, nsphere_tag, DimensionIndex>
+{
+ typedef typename Elements::value_type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename coordinate_type<indexable_type>::type coordinate_type;
+
+ typedef typename boost::mpl::if_c<
+ boost::is_integral<coordinate_type>::value,
+ double,
+ coordinate_type
+ >::type separation_type;
+
+ static inline void apply(Elements const& elements,
+ Parameters const& parameters,
+ Translator const& translator,
+ separation_type & separation,
+ size_t & seed1,
+ size_t & seed2)
+ {
+ const size_t elements_count = parameters.get_max_elements() + 1;
+ BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
+ BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
+
+ indexable_type const& indexable = rtree::element_indexable(elements[0], translator);
+
+ // find the lowest low, highest high
+ coordinate_type lowest_low = geometry::get<DimensionIndex>(indexable) - geometry::get_radius<0>(indexable);
+ coordinate_type highest_high = geometry::get<DimensionIndex>(indexable) + geometry::get_radius<0>(indexable);
+ // and the lowest high
+ coordinate_type lowest_high = highest_high;
+ size_t lowest_high_index = 0;
+ for ( size_t i = 1 ; i < elements_count ; ++i )
+ {
+ indexable_type const& indexable = rtree::element_indexable(elements[i], translator);
+
+ coordinate_type min_coord = geometry::get<DimensionIndex>(indexable) - geometry::get_radius<0>(indexable);
+ coordinate_type max_coord = geometry::get<DimensionIndex>(indexable) + geometry::get_radius<0>(indexable);
+
+ if ( max_coord < lowest_high )
+ {
+ lowest_high = max_coord;
+ lowest_high_index = i;
+ }
+
+ if ( min_coord < lowest_low )
+ lowest_low = min_coord;
+
+ if ( highest_high < max_coord )
+ highest_high = max_coord;
+ }
+
+ // find the highest low
+ size_t highest_low_index = lowest_high_index == 0 ? 1 : 0;
+ indexable_type const& highest_low_indexable = rtree::element_indexable(elements[highest_low_index], translator);
+ coordinate_type highest_low = geometry::get<DimensionIndex>(highest_low_indexable) - geometry::get_radius<0>(highest_low_indexable);
+ for ( size_t i = highest_low_index ; i < elements_count ; ++i )
+ {
+ indexable_type const& indexable = rtree::element_indexable(elements[i], translator);
+
+ coordinate_type min_coord = geometry::get<DimensionIndex>(indexable) - geometry::get_radius<0>(indexable);
+ if ( highest_low < min_coord &&
+ i != lowest_high_index )
+ {
+ highest_low = min_coord;
+ highest_low_index = i;
+ }
+ }
+
+ coordinate_type const width = highest_high - lowest_low;
+
+ // highest_low - lowest_high
+ separation = difference<separation_type>(lowest_high, highest_low);
+ // BOOST_ASSERT(0 <= width);
+ if ( std::numeric_limits<coordinate_type>::epsilon() < width )
+ separation /= width;
+
+ seed1 = highest_low_index;
+ seed2 = lowest_high_index;
+
+ ::boost::ignore_unused_variable_warning(parameters);
+ }
+};
+
+}}} // namespace detail::rtree::linear
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
Modified: trunk/boost/geometry/extensions/nsphere/nsphere.hpp
==============================================================================
--- trunk/boost/geometry/extensions/nsphere/nsphere.hpp Fri Jun 21 11:04:12 2013 (r84860)
+++ trunk/boost/geometry/extensions/nsphere/nsphere.hpp 2013-06-21 11:09:08 EDT (Fri, 21 Jun 2013) (r84861)
@@ -48,4 +48,6 @@
#include <boost/geometry/extensions/nsphere/index/detail/algorithms/comparable_distance_near.hpp>
#include <boost/geometry/extensions/nsphere/index/detail/algorithms/bounds.hpp>
+#include <boost/geometry/extensions/nsphere/index/detail/rtree/linear/redistribute_elements.hpp>
+
#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_HPP
Modified: trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp Fri Jun 21 11:04:12 2013 (r84860)
+++ trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp 2013-06-21 11:09:08 EDT (Fri, 21 Jun 2013) (r84861)
@@ -341,8 +341,8 @@
elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
// calculate boxes
- geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
- geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
+ detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), box1);
+ detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), box2);
// initialize areas
content_type content1 = index::detail::content(box1);
@@ -424,7 +424,7 @@
}
};
-}} // namespace detail::rtree::visitors
+}} // namespace detail::rtree
}}} // namespace boost::geometry::index