Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r85557 - in trunk/boost/geometry: algorithms algorithms/detail strategies/cartesian
From: adam.wulkiewicz_at_[hidden]
Date: 2013-09-03 20:16:51


Author: awulkiew
Date: 2013-09-03 20:16:50 EDT (Tue, 03 Sep 2013)
New Revision: 85557
URL: http://svn.boost.org/trac/boost/changeset/85557

Log:
[geometry] segment/linestring-box intersection moved to detail/disjoint, compilation error fixed.

Text files modified:
   trunk/boost/geometry/algorithms/detail/disjoint.hpp | 115 ++++++++++++++++++++++++++++++++++++
   trunk/boost/geometry/algorithms/disjoint.hpp | 7 +
   trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp | 126 ----------------------------------------
   3 files changed, 119 insertions(+), 129 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/disjoint.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/disjoint.hpp Tue Sep 3 19:55:17 2013 (r85556)
+++ trunk/boost/geometry/algorithms/detail/disjoint.hpp 2013-09-03 20:16:50 EDT (Tue, 03 Sep 2013) (r85557)
@@ -165,6 +165,121 @@
     }
 };
 
+// Segment - Box intersection
+// Based on Ray-AABB intersection
+// http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm
+
+// TODO - later maybe move to strategy::intersects and add a policy to conditionally extract intersection points
+
+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;
+ }
+};
 
 template
 <

Modified: trunk/boost/geometry/algorithms/disjoint.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/disjoint.hpp Tue Sep 3 19:55:17 2013 (r85556)
+++ trunk/boost/geometry/algorithms/disjoint.hpp 2013-09-03 20:16:50 EDT (Tue, 03 Sep 2013) (r85557)
@@ -183,7 +183,7 @@
         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);
+ return ! detail::disjoint::segment_box_intersection<point_type, Box>::apply(p0, p1, box);
     }
 };
 
@@ -201,7 +201,8 @@
         if ( count == 0 )
             return false;
         else if ( count == 1 )
- return geometry::intersects(*::boost::begin(linestring), box);
+ return detail::disjoint::point_box<point_type, Box, 0, dimension<point_type>::value>
+ ::apply(*::boost::begin(linestring), box);
         else
         {
             const_iterator it0 = ::boost::begin(linestring);
@@ -210,7 +211,7 @@
 
             for ( ; it1 != last ; ++it0, ++it1 )
             {
- if ( strategy::intersection::detail::segment_box_intersection<point_type, Box>::apply(*it0, *it1, box) )
+ if ( detail::disjoint::segment_box_intersection<point_type, Box>::apply(*it0, *it1, box) )
                     return false;
             }
             return true;

Modified: trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp
==============================================================================
--- trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp Tue Sep 3 19:55:17 2013 (r85556)
+++ trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp 2013-09-03 20:16:50 EDT (Tue, 03 Sep 2013) (r85557)
@@ -747,132 +747,6 @@
 
 }} // 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
 
 


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