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