|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r84847 - in trunk/boost/geometry: extensions/nsphere extensions/nsphere/algorithms extensions/nsphere/index extensions/nsphere/index/detail/algorithms extensions/nsphere/strategies extensions/nsphere/strategies/cartesian extensions/nsphere/views index/detail/algorithms index/detail/rtree/node index/detail/rtree/quadratic
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-20 12:30:05
Author: awulkiew
Date: 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013)
New Revision: 84847
URL: http://svn.boost.org/trac/boost/changeset/84847
Log:
[geometry]: [index] added detail::bounds(ind, box) function, quadratic algorithm is able to handle nspheres as Indexables. [extensions] added algorithms required by rtree to handled nspheres as Indexables: centroid(sph), covered_by(sph,box), equals(sph,sph), expand(box,sph), [i]comparable_distance_near(pt,sph), [i]bounds(sph,box), cartesian nsphere_in_box strategy, center_view<Sph> registered as Point.
Added:
trunk/boost/geometry/extensions/nsphere/algorithms/centroid.hpp (contents, props changed)
trunk/boost/geometry/extensions/nsphere/algorithms/covered_by.hpp (contents, props changed)
trunk/boost/geometry/extensions/nsphere/algorithms/equals.hpp (contents, props changed)
trunk/boost/geometry/extensions/nsphere/algorithms/expand.hpp (contents, props changed)
trunk/boost/geometry/extensions/nsphere/index/detail/algorithms/bounds.hpp (contents, props changed)
trunk/boost/geometry/extensions/nsphere/index/detail/algorithms/comparable_distance_near.hpp (contents, props changed)
trunk/boost/geometry/extensions/nsphere/index/indexable.hpp (contents, props changed)
trunk/boost/geometry/extensions/nsphere/strategies/
trunk/boost/geometry/extensions/nsphere/strategies/cartesian/
trunk/boost/geometry/extensions/nsphere/strategies/cartesian/nsphere_in_box.hpp (contents, props changed)
trunk/boost/geometry/extensions/nsphere/views/
trunk/boost/geometry/extensions/nsphere/views/center_view.hpp (contents, props changed)
trunk/boost/geometry/index/detail/algorithms/bounds.hpp (contents, props changed)
Text files modified:
trunk/boost/geometry/extensions/nsphere/algorithms/centroid.hpp | 61 +++++++++++++
trunk/boost/geometry/extensions/nsphere/algorithms/covered_by.hpp | 50 +++++++++++
trunk/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp | 57 +-----------
trunk/boost/geometry/extensions/nsphere/algorithms/equals.hpp | 85 +++++++++++++++++++
trunk/boost/geometry/extensions/nsphere/algorithms/expand.hpp | 133 ++++++++++++++++++++++++++++++
trunk/boost/geometry/extensions/nsphere/algorithms/within.hpp | 14 +++
trunk/boost/geometry/extensions/nsphere/index/detail/algorithms/bounds.hpp | 46 ++++++++++
trunk/boost/geometry/extensions/nsphere/index/detail/algorithms/comparable_distance_near.hpp | 41 +++++++++
trunk/boost/geometry/extensions/nsphere/index/indexable.hpp | 25 +++++
trunk/boost/geometry/extensions/nsphere/nsphere.hpp | 10 ++
trunk/boost/geometry/extensions/nsphere/strategies/cartesian/nsphere_in_box.hpp | 175 ++++++++++++++++++++++++++++++++++++++++
trunk/boost/geometry/extensions/nsphere/views/center_view.hpp | 105 ++++++++++++++++++++++++
trunk/boost/geometry/index/detail/algorithms/bounds.hpp | 41 +++++++++
trunk/boost/geometry/index/detail/rtree/node/node.hpp | 4
trunk/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp | 9 +
15 files changed, 800 insertions(+), 56 deletions(-)
Added: trunk/boost/geometry/extensions/nsphere/algorithms/centroid.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/algorithms/centroid.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,61 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
+// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
+// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
+// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
+
+// 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_ALGORITHMS_CENTROID_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_CENTROID_HPP
+
+#include <boost/geometry/algorithms/centroid.hpp>
+
+#include <boost/geometry/extensions/nsphere/views/center_view.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace centroid
+{
+
+struct centroid_nsphere
+{
+ template<typename NSphere, typename PointCentroid, typename Strategy>
+ static inline void apply(NSphere const& nsphere, PointCentroid& centroid,
+ Strategy const&)
+ {
+ geometry::convert(center_view<const NSphere>(nsphere), centroid);
+ }
+};
+
+}} // namespace detail::centroid
+#endif // DOXYGEN_NO_DETAIL
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+template <typename Geometry>
+struct centroid<Geometry, nsphere_tag>
+ : detail::centroid::centroid_nsphere
+{};
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_CENTROID_HPP
Added: trunk/boost/geometry/extensions/nsphere/algorithms/covered_by.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/algorithms/covered_by.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,50 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
+// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
+// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
+// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
+
+// 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_ALGORITHMS_COVERED_BY_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_COVERED_BY_HPP
+
+
+#include <boost/geometry/algorithms/covered_by.hpp>
+
+#include <boost/geometry/extensions/nsphere/strategies/cartesian/nsphere_in_box.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+template <typename NSphere, typename Box>
+struct covered_by<NSphere, Box, nsphere_tag, box_tag>
+{
+ template <typename Strategy>
+ static inline bool apply(NSphere const& nsphere, Box const& box, Strategy const& strategy)
+ {
+ assert_dimension_equal<NSphere, Box>();
+ boost::ignore_unused_variable_warning(strategy);
+ return strategy.apply(nsphere, box);
+ }
+};
+
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_COVERED_BY_HPP
Modified: trunk/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp
==============================================================================
--- trunk/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp Thu Jun 20 08:14:11 2013 (r84846)
+++ trunk/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -16,10 +16,13 @@
#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_DISJOINT_HPP
#include <boost/geometry/algorithms/disjoint.hpp>
+#include <boost/geometry/algorithms/comparable_distance.hpp>
#include <boost/mpl/if.hpp>
#include <boost/type_traits/is_same.hpp>
+#include <boost/geometry/extensions/nsphere/views/center_view.hpp>
+
namespace boost { namespace geometry
{
@@ -27,48 +30,6 @@
namespace detail { namespace disjoint
{
-template
-<
- typename PoS1, typename PoS2,
- std::size_t Dimension, std::size_t DimensionCount
->
-struct points_or_spheres_comparable_distance_cartesian
-{
- typedef typename boost::mpl::if_<
- ::boost::is_same<typename tag<PoS1>::type, point_tag>, PoS1, typename point_type<PoS1>::type
- >::type point1_type;
-
- typedef typename boost::mpl::if_<
- ::boost::is_same<typename tag<PoS2>::type, point_tag>, PoS2, typename point_type<PoS2>::type
- >::type point2_type;
-
- typedef typename geometry::select_most_precise<
- typename coordinate_type<point1_type>::type, typename coordinate_type<point2_type>::type
- >::type coordinate_type;
-
- typedef typename geometry::default_distance_result<
- point1_type, point2_type
- >::type result_type;
-
- static inline result_type apply(PoS1 const& g1, PoS2 const& g2)
- {
- coordinate_type tmp = get<Dimension>(g1) - get<Dimension>(g2);
-
- return tmp * tmp + points_or_spheres_comparable_distance_cartesian<
- PoS1, PoS2, Dimension + 1, DimensionCount
- >::apply(g1, g2);
- }
-};
-
-template <typename PoS1, typename PoS2, std::size_t DimensionCount>
-struct points_or_spheres_comparable_distance_cartesian<PoS1, PoS2, DimensionCount, DimensionCount>
-{
- static inline int apply(PoS1 const& , PoS2 const& )
- {
- return 0;
- }
-};
-
// Arvo's algorithm implemented
// TODO - implement the method mentioned in the article below and compare performance
// "On Faster Sphere-Box Overlap Testing" - Larsson, T.; Akeine-Moller, T.; Lengyel, E.
@@ -137,9 +98,7 @@
BOOST_MPL_ASSERT_MSG(check_cs, NOT_IMPLEMENTED_FOR_THOSE_COORDINATE_SYSTEMS, (p_cs, s_cs));
return get_radius<0>(s) * get_radius<0>(s)
- < geometry::detail::disjoint::points_or_spheres_comparable_distance_cartesian<
- Point, NSphere, 0, DimensionCount
- >::apply(p, s);
+ < geometry::comparable_distance(p, center_view<const NSphere>(s));
}
};
@@ -171,14 +130,10 @@
BOOST_MPL_ASSERT_MSG(check_cs, NOT_IMPLEMENTED_FOR_THOSE_COORDINATE_SYSTEMS, (s1_cs, s2_cs));
/*return get_radius<0>(s1) + get_radius<0>(s2)
- < ::sqrt(geometry::detail::disjoint::points_or_spheres_comparable_distance_cartesian<
- NSphere1, NSphere2, 0, DimensionCount
- >::apply(s1, s2));*/
+ < ::sqrt(geometry::comparable_distance(center_view<NSphere>(s1), center_view<NSphere>(s2)));*/
return get_radius<0>(s1) * get_radius<0>(s1) + 2 * get_radius<0>(s1) * get_radius<0>(s2) + get_radius<0>(s2) * get_radius<0>(s2)
- < geometry::detail::disjoint::points_or_spheres_comparable_distance_cartesian<
- NSphere1, NSphere2, 0, DimensionCount
- >::apply(s1, s2);
+ < geometry::comparable_distance(center_view<const NSphere1>(s1), center_view<const NSphere2>(s2));
}
};
Added: trunk/boost/geometry/extensions/nsphere/algorithms/equals.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/algorithms/equals.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,85 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
+// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
+// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
+
+// 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_ALGORITHMS_EQUALS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_EQUALS_HPP
+
+
+#include <boost/geometry/algorithms/equals.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace equals
+{
+
+
+template
+<
+ std::size_t Dimension,
+ std::size_t DimensionCount
+>
+struct nsphere_nsphere
+{
+ template <typename S1, typename S2>
+ static inline bool apply(S1 const& s1, S2 const& s2)
+ {
+ if ( !geometry::math::equals(get<Dimension>(s1), get<Dimension>(s2)) )
+ {
+ return false;
+ }
+ return nsphere_nsphere<Dimension + 1, DimensionCount>::apply(s1, s2);
+ }
+};
+
+template <std::size_t DimensionCount>
+struct nsphere_nsphere<DimensionCount, DimensionCount>
+{
+ template <typename S1, typename S2>
+ static inline bool apply(S1 const& , S2 const& )
+ {
+ return true;
+ }
+};
+
+
+}} // namespace detail::equals
+#endif // DOXYGEN_NO_DETAIL
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+template <typename NSphere1, typename NSphere2, std::size_t DimensionCount, bool Reverse>
+struct equals<NSphere1, NSphere2, nsphere_tag, nsphere_tag, DimensionCount, Reverse>
+{
+ template <typename S1, typename S2>
+ static inline bool apply(S1 const& s1, S2 const& s2)
+ {
+ return detail::equals::nsphere_nsphere<0, DimensionCount>::apply(s1, s2)
+ && geometry::math::equals(get_radius<0>(s1), get_radius<0>(s2));
+ }
+};
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_EQUALS_HPP
+
Added: trunk/boost/geometry/extensions/nsphere/algorithms/expand.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/algorithms/expand.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,133 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
+// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
+// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
+// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
+
+// 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_ALGORITHMS_EXPAND_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_EXPAND_HPP
+
+
+#include <cstddef>
+
+#include <boost/numeric/conversion/cast.hpp>
+
+#include <boost/geometry/algorithms/not_implemented.hpp>
+#include <boost/geometry/core/coordinate_dimension.hpp>
+#include <boost/geometry/geometries/concepts/check.hpp>
+
+#include <boost/geometry/util/select_coordinate_type.hpp>
+
+#include <boost/geometry/strategies/compare.hpp>
+#include <boost/geometry/policies/compare.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace expand
+{
+
+
+template
+<
+ typename StrategyLess, typename StrategyGreater,
+ std::size_t Dimension, std::size_t DimensionCount
+>
+struct nsphere_loop
+{
+ template <typename Box, typename NSphere>
+ static inline void apply(Box& box, NSphere const& source)
+ {
+ typedef typename strategy::compare::detail::select_strategy
+ <
+ StrategyLess, 1, NSphere, Dimension
+ >::type less_type;
+
+ typedef typename strategy::compare::detail::select_strategy
+ <
+ StrategyGreater, -1, NSphere, Dimension
+ >::type greater_type;
+
+ typedef typename select_coordinate_type<NSphere, Box>::type coordinate_type;
+
+ less_type less;
+ greater_type greater;
+
+ coordinate_type const min_coord = get<Dimension>(source) - get_radius<0>(source);
+ coordinate_type const max_coord = get<Dimension>(source) + get_radius<0>(source);
+
+ if (less(min_coord, get<min_corner, Dimension>(box)))
+ {
+ set<min_corner, Dimension>(box, min_coord);
+ }
+
+ if (greater(max_coord, get<max_corner, Dimension>(box)))
+ {
+ set<max_corner, Dimension>(box, max_coord);
+ }
+
+ nsphere_loop
+ <
+ StrategyLess, StrategyGreater,
+ Dimension + 1, DimensionCount
+ >::apply(box, source);
+ }
+};
+
+
+template
+<
+ typename StrategyLess, typename StrategyGreater,
+ std::size_t DimensionCount
+>
+struct nsphere_loop
+ <
+ StrategyLess, StrategyGreater,
+ DimensionCount, DimensionCount
+ >
+{
+ template <typename Box, typename NSphere>
+ static inline void apply(Box&, NSphere const&) {}
+};
+
+
+}} // namespace detail::expand
+#endif // DOXYGEN_NO_DETAIL
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+
+// Box + Nsphere -> new box containing also nsphere
+template
+<
+ typename BoxOut, typename NSphere,
+ typename StrategyLess, typename StrategyGreater
+>
+struct expand<BoxOut, NSphere, StrategyLess, StrategyGreater, box_tag, nsphere_tag>
+ : detail::expand::nsphere_loop
+ <
+ StrategyLess, StrategyGreater,
+ 0, dimension<NSphere>::type::value
+ >
+{};
+
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_EXPAND_HPP
Modified: trunk/boost/geometry/extensions/nsphere/algorithms/within.hpp
==============================================================================
--- trunk/boost/geometry/extensions/nsphere/algorithms/within.hpp Thu Jun 20 08:14:11 2013 (r84846)
+++ trunk/boost/geometry/extensions/nsphere/algorithms/within.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -3,6 +3,7 @@
// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
+// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
@@ -207,6 +208,19 @@
};
+
+template <typename NSphere, typename Box>
+struct within<NSphere, Box, nsphere_tag, box_tag>
+{
+ template <typename Strategy>
+ static inline bool apply(NSphere const& nsphere, Box const& box, Strategy const& strategy)
+ {
+ assert_dimension_equal<NSphere, Box>();
+ boost::ignore_unused_variable_warning(strategy);
+ return strategy.apply(nsphere, box);
+ }
+};
+
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
Added: trunk/boost/geometry/extensions/nsphere/index/detail/algorithms/bounds.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/index/detail/algorithms/bounds.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,46 @@
+// Boost.Geometry Index
+//
+// n-dimensional bounds
+//
+// 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_ALGORITHMS_BOUNDS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_DETAIL_ALGORITHMS_BOUNDS_HPP
+
+#include <boost/geometry/index/detail/algorithms/bounds.hpp>
+
+namespace boost { namespace geometry { namespace index { namespace detail {
+
+template <typename Geometry, typename Bounds, std::size_t DimensionIndex, std::size_t DimensionCount>
+struct bounds_nsphere_box
+{
+ static inline void apply(Geometry const& g, Bounds & b)
+ {
+ set<min_corner, DimensionIndex>(b, get<DimensionIndex>(g) - get_radius<0>(g));
+ set<max_corner, DimensionIndex>(b, get<DimensionIndex>(g) + get_radius<0>(g));
+ bounds_nsphere_box<Geometry, Bounds, DimensionIndex+1, DimensionCount>::apply(g, b);
+ }
+};
+
+template <typename Geometry, typename Bounds, std::size_t DimensionCount>
+struct bounds_nsphere_box<Geometry, Bounds, DimensionCount, DimensionCount>
+{
+ static inline void apply(Geometry const& , Bounds & ) {}
+};
+
+namespace dispatch {
+
+template <typename Geometry, typename Bounds>
+struct bounds<Geometry, Bounds, nsphere_tag, box_tag>
+ : bounds_nsphere_box<Geometry, Bounds, 0, dimension<Geometry>::value>
+{};
+
+} // namespace dispatch
+
+}}}} // namespace boost::geometry::index::detail
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_DETAIL_ALGORITHMS_BOUNDS_HPP
Added: trunk/boost/geometry/extensions/nsphere/index/detail/algorithms/comparable_distance_near.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/index/detail/algorithms/comparable_distance_near.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,41 @@
+// Boost.Geometry Index
+//
+// squared distance between point and nearest point of the box or point
+//
+// 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_ALGORITHMS_COMPARABLE_DISTANCE_NEAR_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_DETAIL_ALGORITHMS_COMPARABLE_DISTANCE_NEAR_HPP
+
+#include <boost/geometry/index/detail/algorithms/comparable_distance_near.hpp>
+
+#include <boost/geometry/extensions/nsphere/views/center_view.hpp>
+
+namespace boost { namespace geometry { namespace index { namespace detail {
+
+template <
+ typename Point,
+ typename Indexable,
+ size_t N>
+struct sum_for_indexable<Point, Indexable, nsphere_tag, comparable_distance_near_tag, N>
+{
+ typedef typename default_distance_result<Point, center_view<const Indexable> >::type result_type;
+
+ inline static result_type apply(Point const& pt, Indexable const& i)
+ {
+ result_type center_dist = ::sqrt( comparable_distance(pt, center_view<const Indexable>(i)) );
+ result_type dist = get_radius<0>(i) < center_dist ? center_dist - get_radius<0>(i) : 0;
+ return dist;
+
+ // return dist * dist to be conformant with comparable_distance?
+ // CONSIDER returning negative value related to the distance or normalized distance to the center if dist < radius
+ }
+};
+
+}}}} // namespace boost::geometry::index::detail
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_DETAIL_ALGORITHMS_COMPARABLE_DISTANCE_NEAR_HPP
Added: trunk/boost/geometry/extensions/nsphere/index/indexable.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/index/indexable.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,25 @@
+// Boost.Geometry Index
+//
+// 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_INDEXABLE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_INDEXABLE_HPP
+
+#include <boost/geometry/index/indexable.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+template <typename NSphere>
+struct is_indexable_impl<NSphere, geometry::nsphere_tag> { static const bool value = true; };
+
+} // namespace detail
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_INDEX_INDEXABLE_HPP
Modified: trunk/boost/geometry/extensions/nsphere/nsphere.hpp
==============================================================================
--- trunk/boost/geometry/extensions/nsphere/nsphere.hpp Thu Jun 20 08:14:11 2013 (r84846)
+++ trunk/boost/geometry/extensions/nsphere/nsphere.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -32,11 +32,19 @@
#include <boost/geometry/extensions/nsphere/algorithms/clear.hpp>
#include <boost/geometry/extensions/nsphere/algorithms/envelope.hpp>
#include <boost/geometry/extensions/nsphere/algorithms/num_points.hpp>
-#include <boost/geometry/extensions/nsphere/algorithms/within.hpp>
#include <boost/geometry/extensions/nsphere/algorithms/disjoint.hpp>
+#include <boost/geometry/extensions/nsphere/strategies/cartesian/nsphere_in_box.hpp>
+#include <boost/geometry/extensions/nsphere/algorithms/within.hpp>
+#include <boost/geometry/extensions/nsphere/algorithms/covered_by.hpp>
+#include <boost/geometry/extensions/nsphere/algorithms/expand.hpp>
+#include <boost/geometry/extensions/nsphere/algorithms/equals.hpp>
+#include <boost/geometry/extensions/nsphere/algorithms/centroid.hpp>
+#include <boost/geometry/extensions/nsphere/index/indexable.hpp>
#include <boost/geometry/extensions/nsphere/index/detail/algorithms/content.hpp>
#include <boost/geometry/extensions/nsphere/index/detail/algorithms/is_valid.hpp>
#include <boost/geometry/extensions/nsphere/index/detail/algorithms/margin.hpp>
+#include <boost/geometry/extensions/nsphere/index/detail/algorithms/comparable_distance_near.hpp>
+#include <boost/geometry/extensions/nsphere/index/detail/algorithms/bounds.hpp>
#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_HPP
Added: trunk/boost/geometry/extensions/nsphere/strategies/cartesian/nsphere_in_box.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/strategies/cartesian/nsphere_in_box.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,175 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
+// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
+// Copyright (c) 2013 Adam Wulkiewicz, London, UK.
+
+// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
+// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
+
+// 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_STRATEGIES_CARTESIAN_NSPHERE_IN_BOX_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_STRATEGIES_CARTESIAN_NSPHERE_IN_BOX_HPP
+
+
+#include <boost/geometry/core/access.hpp>
+#include <boost/geometry/core/coordinate_dimension.hpp>
+#include <boost/geometry/strategies/covered_by.hpp>
+#include <boost/geometry/strategies/within.hpp>
+
+
+namespace boost { namespace geometry { namespace strategy
+{
+
+namespace within
+{
+
+struct nsphere_within_range
+{
+ template <typename ContainedValue, typename ContainingValue>
+ static inline bool apply(ContainedValue const& ed_min
+ , ContainedValue const& ed_max
+ , ContainingValue const& ing_min
+ , ContainingValue const& ing_max)
+ {
+ return ing_min < ed_min && ed_max < ing_max;
+ }
+};
+
+
+struct nsphere_covered_by_range
+{
+ template <typename ContainedValue, typename ContainingValue>
+ static inline bool apply(ContainedValue const& ed_min
+ , ContainedValue const& ed_max
+ , ContainingValue const& ing_min
+ , ContainingValue const& ing_max)
+ {
+ return ing_min <= ed_min && ed_max <= ing_max;
+ }
+};
+
+template
+<
+ typename SubStrategy,
+ typename NSphere,
+ typename Box,
+ std::size_t Dimension,
+ std::size_t DimensionCount
+>
+struct relate_nsphere_box_loop
+{
+ static inline bool apply(NSphere const& sphere, Box const& box)
+ {
+ if (! SubStrategy::apply(
+ get<Dimension>(sphere) - get_radius<0>(sphere),
+ get<Dimension>(sphere) + get_radius<0>(sphere),
+ get<min_corner, Dimension>(box),
+ get<max_corner, Dimension>(box))
+ )
+ {
+ return false;
+ }
+
+ return relate_nsphere_box_loop
+ <
+ SubStrategy,
+ NSphere, Box,
+ Dimension + 1, DimensionCount
+ >::apply(sphere, box);
+ }
+};
+
+
+template
+<
+ typename SubStrategy,
+ typename NSphere,
+ typename Box,
+ std::size_t DimensionCount
+>
+struct relate_nsphere_box_loop<SubStrategy, NSphere, Box, DimensionCount, DimensionCount>
+{
+ static inline bool apply(NSphere const& , Box const& )
+ {
+ return true;
+ }
+};
+
+
+template
+<
+ typename NSphere,
+ typename Box,
+ typename SubStrategy = nsphere_within_range
+>
+struct nsphere_in_box
+{
+ static inline bool apply(NSphere const& nsphere, Box const& box)
+ {
+ return relate_nsphere_box_loop
+ <
+ SubStrategy,
+ NSphere, Box,
+ 0, dimension<NSphere>::type::value
+ >::apply(nsphere, box);
+ }
+};
+
+
+} // namespace within
+
+
+#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+
+
+namespace within { namespace services
+{
+
+template <typename NSphere, typename Box>
+struct default_strategy
+ <
+ nsphere_tag, box_tag,
+ nsphere_tag, areal_tag,
+ cartesian_tag, cartesian_tag,
+ NSphere, Box
+ >
+{
+ typedef within::nsphere_in_box<NSphere, Box, within::nsphere_within_range> type;
+};
+
+
+}} // namespace within::services
+
+
+namespace covered_by { namespace services
+{
+
+
+template <typename NSphere, typename Box>
+struct default_strategy
+ <
+ nsphere_tag, box_tag,
+ nsphere_tag, areal_tag,
+ cartesian_tag, cartesian_tag,
+ NSphere, Box
+ >
+{
+ typedef within::nsphere_in_box<NSphere, Box, within::nsphere_covered_by_range> type;
+};
+
+
+}} // namespace covered_by::services
+
+
+#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+
+
+}}} // namespace boost::geometry::strategy
+
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_STRATEGIES_CARTESIAN_NSPHERE_IN_BOX_HPP
Added: trunk/boost/geometry/extensions/nsphere/views/center_view.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/views/center_view.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,105 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
+// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
+// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
+
+// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
+// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
+
+// 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_VIEWS_CENTER_VIEW_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_VIEWS_CENTER_VIEW_HPP
+
+#include <boost/geometry/core/point_type.hpp>
+
+namespace boost { namespace geometry
+{
+
+// Silence warning C4512: assignment operator could not be generated
+#if defined(_MSC_VER)
+#pragma warning(push)
+#pragma warning(disable : 4512)
+#endif
+
+template <typename NSphere>
+struct center_view
+{
+ typedef typename geometry::point_type<NSphere>::type point_type;
+ typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
+
+ explicit center_view(NSphere & nsphere)
+ : m_nsphere(nsphere)
+ {}
+
+ template <std::size_t I> coordinate_type get() const { return geometry::get<I>(m_nsphere); }
+ template <std::size_t I> void set(coordinate_type const& v) { geometry::set<I>(m_nsphere, v); }
+
+private :
+ NSphere & m_nsphere;
+};
+
+#ifndef DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+namespace traits
+{
+
+template<typename NSphere>
+struct tag< center_view<NSphere> >
+{
+ typedef point_tag type;
+};
+
+template<typename NSphere>
+struct coordinate_type< center_view<NSphere> >
+{
+ typedef typename geometry::coordinate_type<
+ typename geometry::point_type<NSphere>::type
+ >::type type;
+};
+
+template<typename NSphere>
+struct coordinate_system< center_view<NSphere> >
+{
+ typedef typename geometry::coordinate_system<
+ typename geometry::point_type<NSphere>::type
+ >::type type;
+};
+
+template<typename NSphere>
+struct dimension< center_view<NSphere> >
+ : geometry::dimension< typename geometry::point_type<NSphere>::type >
+{};
+
+template<typename NSphere, std::size_t Dimension>
+struct access<center_view<NSphere>, Dimension>
+{
+ typedef typename geometry::coordinate_type<
+ typename geometry::point_type<NSphere>::type
+ >::type coordinate_type;
+
+ static inline coordinate_type get(center_view<NSphere> const& p)
+ {
+ return p.template get<Dimension>();
+ }
+
+ static inline void set(center_view<NSphere> & p, coordinate_type const& value)
+ {
+ p.template set<Dimension>(value);
+ }
+};
+
+}
+#endif // DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+
+#if defined(_MSC_VER)
+#pragma warning(pop)
+#endif
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_VIEWS_CENTER_VIEW_HPP
Added: trunk/boost/geometry/index/detail/algorithms/bounds.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/index/detail/algorithms/bounds.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -0,0 +1,41 @@
+// Boost.Geometry Index
+//
+// n-dimensional bounds
+//
+// 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_INDEX_DETAIL_ALGORITHMS_BOUNDS_HPP
+#define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_BOUNDS_HPP
+
+namespace boost { namespace geometry { namespace index { namespace detail {
+
+namespace dispatch {
+
+template <typename Geometry,
+ typename Bounds,
+ typename TagGeometry = typename geometry::tag<Geometry>::type,
+ typename TagBounds = typename geometry::tag<Bounds>::type>
+struct bounds
+{
+ static inline void apply(Geometry const& g, Bounds & b)
+ {
+ geometry::convert(g, b);
+ }
+};
+
+} // namespace dispatch
+
+template <typename Geometry, typename Bounds>
+inline void bounds(Geometry const& g, Bounds & b)
+{
+ concept::check_concepts_and_equal_dimensions<Geometry const, Bounds>();
+ dispatch::bounds<Geometry, Bounds>::apply(g, b);
+}
+
+}}}} // namespace boost::geometry::index::detail
+
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_BOUNDS_HPP
Modified: trunk/boost/geometry/index/detail/rtree/node/node.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/node/node.hpp Thu Jun 20 08:14:11 2013 (r84846)
+++ trunk/boost/geometry/index/detail/rtree/node/node.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -32,6 +32,8 @@
#include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
+#include <boost/geometry/index/detail/algorithms/bounds.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree {
@@ -49,7 +51,7 @@
return result;
}
- geometry::convert(element_indexable(*first, tr), result);
+ detail::bounds(element_indexable(*first, tr), result);
++first;
for ( ; first != last ; ++first )
Modified: trunk/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp Thu Jun 20 08:14:11 2013 (r84846)
+++ trunk/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp 2013-06-20 12:30:05 EDT (Thu, 20 Jun 2013) (r84847)
@@ -57,7 +57,8 @@
indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);
box_type enlarged_box;
- geometry::convert(ind1, enlarged_box);
+ //geometry::convert(ind1, enlarged_box);
+ detail::bounds(ind1, enlarged_box);
geometry::expand(enlarged_box, ind2);
content_type free_content = (index::detail::content(enlarged_box) - index::detail::content(ind1)) - index::detail::content(ind2);
@@ -132,8 +133,10 @@
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);
+ //geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
+ detail::bounds(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[seed2], translator), box2);
// remove seeds
if (seed1 < seed2)
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