[Boost-commit] svn:boost r85556 - in trunk/boost/geometry: algorithms strategies/cartesian

Subject: [Boost-commit] svn:boost r85556 - in trunk/boost/geometry: algorithms strategies/cartesian
From: adam.wulkiewicz_at_[hidden]
Date: 2013-09-03 19:55:17

Author: awulkiew
Date: 2013-09-03 19:55:17 EDT (Tue, 03 Sep 2013)
New Revision: 85556
URL: http://svn.boost.org/trac/boost/changeset/85556

Log:
[geometry] added n-dimensional segment-box and linestring-box intersects()/disjoint() implementation.

Text files modified: 
   trunk/boost/geometry/algorithms/disjoint.hpp                 |    60 ++++++++++++++++++                      
   trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp |   125 ++++++++++++++++++++++++++++++++++++++++
   2 files changed, 182 insertions(+), 3 deletions(-)

Modified: trunk/boost/geometry/algorithms/disjoint.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/disjoint.hpp	Tue Sep  3 18:03:10 2013	(r85555)
+++ trunk/boost/geometry/algorithms/disjoint.hpp	2013-09-03 19:55:17 EDT (Tue, 03 Sep 2013)	(r85556)
@@ -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.
@@ -172,6 +173,50 @@
     }
 };
 
+template <typename Segment, typename Box>
+struct disjoint_segment_box
+{
+    static inline bool apply(Segment const& segment, Box const& box)
+    {
+        typedef typename point_type<Segment>::type point_type;
+        point_type p0, p1;
+        geometry::detail::assign_point_from_index<0>(segment, p0);
+        geometry::detail::assign_point_from_index<1>(segment, p1);
+
+        return ! strategy::intersection::detail::segment_box_intersection<point_type, Box>::apply(p0, p1, box);
+    }
+};
+
+template <typename Linestring, typename Box>
+struct disjoint_linestring_box
+{
+    static inline bool apply(Linestring const& linestring, Box const& box)
+    {
+        typedef typename ::boost::range_value<Linestring>::type point_type;
+        typedef typename ::boost::range_const_iterator<Linestring>::type const_iterator;        
+        typedef typename ::boost::range_size<Linestring>::type size_type;
+
+        const size_type count = ::boost::size(linestring);
+
+        if ( count == 0 )
+            return false;
+        else if ( count == 1 )
+            return geometry::intersects(*::boost::begin(linestring), box);
+        else
+        {
+            const_iterator it0 = ::boost::begin(linestring);
+            const_iterator it1 = ::boost::begin(linestring) + 1;
+            const_iterator last = ::boost::end(linestring);
+
+            for ( ; it1 != last ; ++it0, ++it1 )
+            {
+                if ( strategy::intersection::detail::segment_box_intersection<point_type, Box>::apply(*it0, *it1, box) )
+                    return false;
+            }
+            return true;
+        }
+    }
+};
 
 }} // namespace detail::disjoint
 #endif // DOXYGEN_NO_DETAIL
@@ -249,9 +294,9 @@
     : detail::disjoint::disjoint_linear<Linestring1, Linestring2>
 {};
 
-template <typename Linestring1, typename Linestring2, bool Reverse>
-struct disjoint<Linestring1, Linestring2, 2, segment_tag, segment_tag, Reverse>
-    : detail::disjoint::disjoint_segment<Linestring1, Linestring2>
+template <typename Segment1, typename Segment2, bool Reverse>
+struct disjoint<Segment1, Segment2, 2, segment_tag, segment_tag, Reverse>
+    : detail::disjoint::disjoint_segment<Segment1, Segment2>
 {};
 
 template <typename Linestring, typename Segment, bool Reverse>
@@ -259,6 +304,15 @@
     : detail::disjoint::disjoint_linear<Linestring, Segment>
 {};
 
+template <typename Segment, typename Box, std::size_t DimensionCount, bool Reverse>
+struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, Reverse>
+    : detail::disjoint::disjoint_segment_box<Segment, Box>
+{};
+
+template <typename Linestring, typename Box, std::size_t DimensionCount, bool Reverse>
+struct disjoint<Linestring, Box, DimensionCount, linestring_tag, box_tag, Reverse>
+    : detail::disjoint::disjoint_linestring_box<Linestring, Box>
+{};
 
 } // namespace dispatch
 #endif // DOXYGEN_NO_DISPATCH

Modified: trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp
==============================================================================
--- trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp	Tue Sep  3 18:03:10 2013	(r85555)
+++ trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp	2013-09-03 19:55:17 EDT (Tue, 03 Sep 2013)	(r85556)
@@ -1,6 +1,7 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 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
@@ -746,7 +747,131 @@
 
 }} // namespace strategy::intersection
 
+// Segment - Box intersection
+// Based on Ray-AABB intersection
+// http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm
 
+// TODO - probably add a policy to conditionally extract intersection points
+
+namespace strategy { namespace intersection {
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail {
+
+template <typename Point, typename Box, size_t I>
+struct segment_box_intersection_dim
+{
+    BOOST_STATIC_ASSERT(I < dimension<Box>::value);
+    BOOST_STATIC_ASSERT(I < dimension<Point>::value);
+    BOOST_STATIC_ASSERT(dimension<Point>::value == dimension<Box>::value);
+
+    typedef typename coordinate_type<Point>::type point_coordinate;
+
+    template <typename RelativeDistance> static inline
+    bool apply(Point const& p0, Point const& p1, Box const& b, RelativeDistance & t_near, RelativeDistance & t_far)
+    {
+        //// WARNING! - RelativeDistance must be IEEE float for this to work (division by 0)
+        //BOOST_STATIC_ASSERT(boost::is_float<RelativeDistance>::value);
+        //// Ray origin is in segment point 0
+        //RelativeDistance ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
+        //RelativeDistance tn = ( geometry::get<min_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
+        //RelativeDistance tf = ( geometry::get<max_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
+
+        // TODO - should we support also unsigned integers?
+        BOOST_STATIC_ASSERT(!boost::is_unsigned<point_coordinate>::value);
+        point_coordinate ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
+        RelativeDistance tn, tf;
+        if ( ::std::abs(ray_d) < ::std::numeric_limits<point_coordinate>::epsilon() )
+        {
+            tn = dist_div_by_zero<RelativeDistance>(geometry::get<min_corner, I>(b) - geometry::get<I>(p0));
+            tf = dist_div_by_zero<RelativeDistance>(geometry::get<max_corner, I>(b) - geometry::get<I>(p0));
+        }
+        else
+        {
+            tn = static_cast<RelativeDistance>(geometry::get<min_corner, I>(b) - geometry::get<I>(p0)) / ray_d;
+            tf = static_cast<RelativeDistance>(geometry::get<max_corner, I>(b) - geometry::get<I>(p0)) / ray_d;
+        }
+
+        if ( tf < tn )
+            ::std::swap(tn, tf);
+
+        if ( t_near < tn )
+            t_near = tn;
+        if ( tf < t_far )
+            t_far = tf;
+
+        return 0 <= t_far && t_near <= t_far && t_near <= 1;
+    }
+
+    template <typename R, typename T> static inline
+    R dist_div_by_zero(T const& val)
+    {
+        if ( ::std::abs(val) < ::std::numeric_limits<T>::epsilon() )
+            return 0;
+        else if ( val < 0 )
+            return -::std::numeric_limits<R>::max();
+        else
+            return ::std::numeric_limits<R>::max();
+    }
+};
+
+template <typename Point, typename Box, size_t CurrentDimension>
+struct segment_box_intersection_impl
+{
+    BOOST_STATIC_ASSERT(0 < CurrentDimension);
+
+    typedef segment_box_intersection_dim<Point, Box, CurrentDimension - 1> for_dim;
+
+    template <typename RelativeDistance>
+    static inline bool apply(Point const& p0, Point const& p1, Box const& b,
+                             RelativeDistance & t_near, RelativeDistance & t_far)
+    {
+        return segment_box_intersection_impl<Point, Box, CurrentDimension - 1>::apply(p0, p1, b, t_near, t_far)
+            && for_dim::apply(p0, p1, b, t_near, t_far);
+    }
+};
+
+template <typename Point, typename Box>
+struct segment_box_intersection_impl<Point, Box, 1>
+{
+    typedef segment_box_intersection_dim<Point, Box, 0> for_dim;
+
+    template <typename RelativeDistance>
+    static inline bool apply(Point const& p0, Point const& p1, Box const& b,
+                             RelativeDistance & t_near, RelativeDistance & t_far)
+    {
+        return for_dim::apply(p0, p1, b, t_near, t_far);
+    }
+};
+
+template <typename Point, typename Box>
+struct segment_box_intersection
+{
+    typedef segment_box_intersection_impl<Point, Box, dimension<Box>::value> impl;
+
+    static inline bool apply(Point const& p0, Point const& p1, Box const& b)
+    {
+        typedef
+        typename geometry::promote_floating_point<
+            typename geometry::select_most_precise<
+                typename coordinate_type<Point>::type,
+                typename coordinate_type<Box>::type
+            >::type
+        >::type relative_distance_type;
+
+        relative_distance_type t_near = -(::std::numeric_limits<relative_distance_type>::max)();
+        relative_distance_type t_far = (::std::numeric_limits<relative_distance_type>::max)();
+
+        return impl::apply(p0, p1, b, t_near, t_far);
+
+        // relative_distance = 0 < t_near ? t_near : 0;
+    }
+};
+
+} // namespace detail
+#endif // DOXYGEN_NO_DETAIL
+
+}} // namespace segment::intersection
 
 }} // namespace boost::geometry