|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r71927 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-05-13 16:23:17
Author: awulkiew
Date: 2011-05-13 16:23:16 EDT (Fri, 13 May 2011)
New Revision: 71927
URL: http://svn.boost.org/trac/boost/changeset/71927
Log:
intersects changed to within in remove visitor + some comments added
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/within.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 7 +++++--
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 5 +++++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 6 +++---
sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp | 9 +++++++++
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 9 +++++++++
sandbox-branches/geometry/index_080_new/tests/main.cpp | 9 +++++++++
6 files changed, 40 insertions(+), 5 deletions(-)
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/within.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/within.hpp 2011-05-13 16:23:16 EDT (Fri, 13 May 2011)
@@ -0,0 +1,131 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - n-dimensional within box
+//
+// 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_WITHIN_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_WITHIN_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+namespace dispatch {
+
+template <size_t Corner, size_t DimensionIndex, typename Indexable, typename IndexableTag>
+struct within_compare
+{
+ // TODO: awulkiew - static assert?
+};
+
+template <size_t DimensionIndex, typename Indexable>
+struct within_compare<min_corner, DimensionIndex, Indexable, box_tag>
+{
+ template <typename Box>
+ static inline bool apply(Box const& b1, Indexable const& b2)
+ {
+ return index::get<min_corner, DimensionIndex>(b1) <= index::get<min_corner, DimensionIndex>(b2);
+ }
+};
+
+template <size_t DimensionIndex, typename Indexable>
+struct within_compare<max_corner, DimensionIndex, Indexable, box_tag>
+{
+ template <typename Box>
+ static inline bool apply(Box const& b1, Indexable const& b2)
+ {
+ return index::get<max_corner, DimensionIndex>(b2) <= index::get<max_corner, DimensionIndex>(b1);
+ }
+};
+
+template <size_t DimensionIndex, typename Indexable>
+struct within_compare<min_corner, DimensionIndex, Indexable, point_tag>
+{
+ template <typename Box>
+ static inline bool apply(Box const& b, Indexable const& p)
+ {
+ return index::get<min_corner, DimensionIndex>(b) <= index::get<DimensionIndex>(p);
+ }
+};
+
+template <size_t DimensionIndex, typename Indexable>
+struct within_compare<max_corner, DimensionIndex, Indexable, point_tag>
+{
+ template <typename Box>
+ static inline bool apply(Box const& b, Indexable const& p)
+ {
+ return index::get<DimensionIndex>(p) <= index::get<max_corner, DimensionIndex>(b);
+ }
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename Box, typename Indexable, size_t CurrentDimension>
+struct within_for_each_dimension
+{
+ BOOST_STATIC_ASSERT(0 < CurrentDimension);
+ BOOST_STATIC_ASSERT(CurrentDimension <= traits::dimension<Box>::value);
+ BOOST_STATIC_ASSERT(traits::dimension<Indexable>::value == traits::dimension<Box>::value);
+
+ static inline bool apply(Box const& b, Indexable const& i)
+ {
+ return
+ within_for_each_dimension<
+ Box,
+ Indexable,
+ CurrentDimension - 1
+ >::apply(b, i) &&
+ dispatch::within_compare<
+ min_corner,
+ CurrentDimension - 1,
+ Indexable,
+ typename traits::tag<Indexable>::type
+ >::apply(b, i) &&
+ dispatch::within_compare<
+ max_corner,
+ CurrentDimension - 1,
+ Indexable,
+ typename traits::tag<Indexable>::type
+ >::apply(b, i);
+ }
+};
+
+template <typename Box, typename Indexable>
+struct within_for_each_dimension<Box, Indexable, 1>
+{
+ BOOST_STATIC_ASSERT(1 <= traits::dimension<Box>::value);
+ BOOST_STATIC_ASSERT(traits::dimension<Indexable>::value == traits::dimension<Box>::value);
+
+ static inline bool apply(Box const& b, Indexable const& i)
+ {
+ return
+ dispatch::within_compare<
+ min_corner,
+ 0,
+ Indexable,
+ typename traits::tag<Indexable>::type
+ >::apply(b, i) &&
+ dispatch::within_compare<
+ max_corner,
+ 0,
+ Indexable,
+ typename traits::tag<Indexable>::type
+ >::apply(b, i);
+ }
+};
+
+} // namespace detail
+
+template <typename Box, typename Indexable>
+bool within(Box const& box, Indexable const& i)
+{
+ return detail::within_for_each_dimension<Box, Indexable, traits::dimension<Box>::value>::apply(box, i);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_WITHIN_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2011-05-13 16:23:16 EDT (Fri, 13 May 2011)
@@ -77,7 +77,7 @@
child_type const& ch_i = children[i];
Box box_exp(ch_i.first);
- // calculate expanded box fo node ch_i
+ // calculate expanded box of child node ch_i
geometry::expand(box_exp, indexable);
// calculate area and area diff
@@ -126,18 +126,21 @@
area_type smallest_area_diff = std::numeric_limits<area_type>::max();
area_type smallest_area = std::numeric_limits<area_type>::max();
- // caculate areas and areas of all nodes' boxes
+ // choose the child which requires smallest box expansion to store the indexable
for ( size_t i = 0 ; i < children_count ; ++i )
{
typedef typename children_type::value_type child_type;
child_type const& ch_i = children[i];
+ // expanded child node's box
Box box_exp(ch_i.first);
geometry::expand(box_exp, indexable);
+ // areas difference
area_type area = index::area(box_exp);
area_type area_diff = area - index::area(ch_i.first);
+ // update the result
if ( area_diff < smallest_area_diff ||
( area_diff == smallest_area_diff && area < smallest_area ) )
{
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2011-05-13 16:23:16 EDT (Fri, 13 May 2011)
@@ -52,12 +52,15 @@
typedef typename children_type::value_type child_type;
child_type const& ch_i = children[i];
+ // expanded child node's box
Box box_exp(ch_i.first);
geometry::expand(box_exp, indexable);
+ // areas difference
area_type area = index::area(box_exp);
area_type area_diff = area - index::area(ch_i.first);
+ // update the result
if ( area_diff < smallest_area_diff ||
( area_diff == smallest_area_diff && area < smallest_area ) )
{
@@ -95,6 +98,7 @@
size_t max_elems,
Translator const& tr)
{
+ // create additional node
node * second_node = rtree::create_node(Node());
Node & n2 = rtree::get<Node>(*second_node);
@@ -221,6 +225,7 @@
size_t current_child_index_bckup = m_current_child_index;
size_t current_level_bckup = m_current_level;
+ // calculate new traverse inputs
m_parent = &n;
m_current_child_index = choosen_node_index;
++m_current_level;
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2011-05-13 16:23:16 EDT (Fri, 13 May 2011)
@@ -14,6 +14,8 @@
#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+#include <boost/geometry/extensions/index/algorithms/within.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree { namespace visitors {
@@ -52,9 +54,7 @@
size_t child_node_index = 0;
for ( ; child_node_index < children.size() ; ++child_node_index )
{
- // TODO: awulkiew - change intersects to within
-
- if ( geometry::intersects(children[child_node_index].first, m_tr(m_value)) )
+ if ( index::within(children[child_node_index].first, m_tr(m_value)) )
{
// next traversing step
traverse_apply_visitor(n, child_node_index);
Modified: sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp 2011-05-13 16:23:16 EDT (Fri, 13 May 2011)
@@ -1,3 +1,12 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - example
+//
+// 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)
+
#include <gl/glut.h>
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
Modified: sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp 2011-05-13 16:23:16 EDT (Fri, 13 May 2011)
@@ -1,3 +1,12 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - example
+//
+// 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)
+
//#define BOOST_GEOMETRY_INDEX_USE_VARIANT_NODES
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
Modified: sandbox-branches/geometry/index_080_new/tests/main.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/main.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/main.cpp 2011-05-13 16:23:16 EDT (Fri, 13 May 2011)
@@ -1,3 +1,12 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - example
+//
+// 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)
+
#include <tests/translators.hpp>
#include <tests/rtree_native.hpp>
#include <tests/rtree_filters.hpp>
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