Subject: [Boost-commit] svn:boost r84811 - in trunk/boost/geometry/extensions: ball nsphere nsphere/algorithms
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-16 18:24:12
Author: awulkiew
Date: 2013-06-16 18:24:12 EDT (Sun, 16 Jun 2013)
New Revision: 84811
URL: http://svn.boost.org/trac/boost/changeset/84811
Log:
[geometry][extensions]: disjoint/intersects implemented for nsphere, ball removed.
Added:
trunk/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp (contents, props changed)
Deleted:
trunk/boost/geometry/extensions/ball/
Text files modified:
trunk/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp | 187 ++++++++++++++++++++++++++++++++++++++++
trunk/boost/geometry/extensions/nsphere/nsphere.hpp | 1
2 files changed, 188 insertions(+), 0 deletions(-)
Added: trunk/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp 2013-06-16 18:24:12 EDT (Sun, 16 Jun 2013) (r84811)
@@ -0,0 +1,187 @@
+// 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_DISJOINT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_DISJOINT_HPP
+
+#include <boost/geometry/algorithms/disjoint.hpp>
+
+#include <boost/mpl/if.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+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.
+template
+<
+ typename Box, typename NSphere,
+ std::size_t Dimension, std::size_t DimensionCount
+>
+struct box_nsphere_comparable_distance_cartesian
+{
+ typedef typename geometry::select_most_precise<
+ typename coordinate_type<typename point_type<Box>::type>::type,
+ typename coordinate_type<typename point_type<NSphere>::type>::type
+ >::type coordinate_type;
+
+ typedef typename geometry::default_distance_result<
+ Box,
+ typename point_type<NSphere>::type
+ >::type result_type;
+
+ static inline result_type apply(Box const& box, NSphere const& nsphere)
+ {
+ result_type r = 0;
+
+ if( get<Dimension>(nsphere) < get<min_corner, Dimension>(box) )
+ {
+ coordinate_type tmp = get<min_corner, Dimension>(box) - get<Dimension>(nsphere);
+ r = tmp*tmp;
+ }
+ else if( get<max_corner, Dimension>(box) < get<Dimension>(nsphere) )
+ {
+ coordinate_type tmp = get<Dimension>(nsphere) - get<max_corner, Dimension>(box);
+ r = tmp*tmp;
+ }
+
+ return r + box_nsphere_comparable_distance_cartesian<
+ Box, NSphere, Dimension + 1, DimensionCount
+ >::apply(box, nsphere);
+ }
+};
+
+template <typename Box, typename NSphere, std::size_t DimensionCount>
+struct box_nsphere_comparable_distance_cartesian<Box, NSphere, DimensionCount, DimensionCount>
+{
+ static inline int apply(Box const& , NSphere const& )
+ {
+ return 0;
+ }
+};
+
+}} // namespace detail::disjoint
+#endif // DOXYGEN_NO_DETAIL
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+template <typename Point, typename NSphere, std::size_t DimensionCount, bool Reverse>
+struct disjoint<Point, NSphere, DimensionCount, point_tag, nsphere_tag, Reverse>
+{
+ static inline bool apply(Point const& p, NSphere const& s)
+ {
+ typedef typename coordinate_system<Point>::type p_cs;
+ typedef typename typename coordinate_system<NSphere>::type s_cs;
+ static const bool check_cs = ::boost::is_same<p_cs, cs::cartesian>::value && ::boost::is_same<s_cs, cs::cartesian>::value;
+ 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);
+ }
+};
+
+template <typename NSphere, typename Box, std::size_t DimensionCount, bool Reverse>
+struct disjoint<NSphere, Box, DimensionCount, nsphere_tag, box_tag, Reverse>
+{
+ static inline bool apply(NSphere const& s, Box const& b)
+ {
+ typedef typename coordinate_system<Box>::type b_cs;
+ typedef typename typename coordinate_system<NSphere>::type s_cs;
+ static const bool check_cs = ::boost::is_same<b_cs, cs::cartesian>::value && ::boost::is_same<s_cs, cs::cartesian>::value;
+ BOOST_MPL_ASSERT_MSG(check_cs, NOT_IMPLEMENTED_FOR_THOSE_COORDINATE_SYSTEMS, (b_cs, s_cs));
+
+ return get_radius<0>(s) * get_radius<0>(s)
+ < geometry::detail::disjoint::box_nsphere_comparable_distance_cartesian<
+ Box, NSphere, 0, DimensionCount
+ >::apply(b, s);
+ }
+};
+
+template <typename NSphere1, typename NSphere2, std::size_t DimensionCount, bool Reverse>
+struct disjoint<NSphere1, NSphere2, DimensionCount, nsphere_tag, nsphere_tag, Reverse>
+{
+ static inline bool apply(NSphere1 const& s1, NSphere2 const& s2)
+ {
+ typedef typename typename coordinate_system<NSphere1>::type s1_cs;
+ typedef typename typename coordinate_system<NSphere2>::type s2_cs;
+ static const bool check_cs = ::boost::is_same<s1_cs, cs::cartesian>::value && ::boost::is_same<s2_cs, cs::cartesian>::value;
+ 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<
+ Point, NSphere, 0, DimensionCount
+ >::apply(p, s));
+ }
+};
+
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_ALGORITHMS_DISJOINT_HPP
Modified: trunk/boost/geometry/extensions/nsphere/nsphere.hpp
==============================================================================
--- trunk/boost/geometry/extensions/nsphere/nsphere.hpp Sun Jun 16 17:29:52 2013 (r84810)
+++ trunk/boost/geometry/extensions/nsphere/nsphere.hpp 2013-06-16 18:24:12 EDT (Sun, 16 Jun 2013) (r84811)
@@ -33,5 +33,6 @@
#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>
#endif // BOOST_GEOMETRY_EXTENSIONS_NSPHERE_HPP