[Boost-commit] svn:boost r84811 - in trunk/boost/geometry/extensions: ball nsphere nsphere/algorithms

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