Subject: [Boost-commit] svn:boost r84237 - trunk/boost/geometry/index/detail/algorithms
From: adam.wulkiewicz_at_[hidden]
Date: 2013-05-11 18:37:04
Author: awulkiew
Date: 2013-05-11 18:37:03 EDT (Sat, 11 May 2013)
New Revision: 84237
URL: http://svn.boost.org/trac/boost/changeset/84237
Log:
geometry.index: path_intersection optimized for 2-point linestrings.
Text files modified:
trunk/boost/geometry/index/detail/algorithms/path_intersection.hpp | 46 +++++++++++++++------------
trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp | 66 ++++++++++++++++++++-------------------
2 files changed, 60 insertions(+), 52 deletions(-)
Modified: trunk/boost/geometry/index/detail/algorithms/path_intersection.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/algorithms/path_intersection.hpp (original)
+++ trunk/boost/geometry/index/detail/algorithms/path_intersection.hpp 2013-05-11 18:37:03 EDT (Sat, 11 May 2013)
@@ -34,34 +34,40 @@
{
typedef typename default_length_result<Linestring>::type length_type;
- static inline bool apply(Indexable const& b, Linestring const& path, length_type & distance)
+ static inline bool apply(Indexable const& b, Linestring const& path, length_type & comparable_distance)
{
typedef typename ::boost::range_value<Linestring>::type point_type;
- typedef typename default_relative_distance_type<Indexable, point_type>::type relative_distance_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(path);
- if ( ::boost::size(path) < 2 )
- return false;
-
- const_iterator it0 = ::boost::begin(path);
- const_iterator it1 = ::boost::begin(path) + 1;
- const_iterator last = ::boost::end(path);
-
- distance = 0;
-
- for ( ; it1 != last ; ++it0, ++it1 )
+ if ( count == 2 )
{
- typename default_distance_result<point_type, point_type>::type
- dist = geometry::distance(*it0, *it1);
+ return index::detail::segment_intersection(b, *::boost::begin(path), *(::boost::begin(path)+1), comparable_distance);
+ }
+ else if ( 2 < count )
+ {
+ const_iterator it0 = ::boost::begin(path);
+ const_iterator it1 = ::boost::begin(path) + 1;
+ const_iterator last = ::boost::end(path);
+
+ comparable_distance = 0;
- relative_distance_type rel_dist;
- if ( index::detail::segment_intersection(b, *it0, *it1, rel_dist) )
+ for ( ; it1 != last ; ++it0, ++it1 )
{
- distance += dist * rel_dist;
- return true;
+ typename default_distance_result<point_type, point_type>::type
+ dist = geometry::distance(*it0, *it1);
+
+ length_type rel_dist;
+ if ( index::detail::segment_intersection(b, *it0, *it1, rel_dist) )
+ {
+ comparable_distance += dist * rel_dist;
+ return true;
+ }
+ else
+ comparable_distance += dist;
}
- else
- distance += dist;
}
return false;
Modified: trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp (original)
+++ trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp 2013-05-11 18:37:03 EDT (Sat, 11 May 2013)
@@ -15,21 +15,21 @@
namespace boost { namespace geometry { namespace index { namespace detail {
-template <typename Indexable, typename Point>
-struct default_relative_distance_type
-{
- typedef typename select_most_precise<
- typename select_most_precise<
- typename traits::coordinate_type<Indexable>::type,
- typename traits::coordinate_type<Point>::type
- >::type,
- float // TODO - use bigger type, calculated from the size of coordinate types
- >::type type;
-
-
- BOOST_MPL_ASSERT_MSG((!::boost::is_unsigned<type>::value),
- THIS_TYPE_SHOULDNT_BE_UNSIGNED, (type));
-};
+//template <typename Indexable, typename Point>
+//struct default_relative_distance_type
+//{
+// typedef typename select_most_precise<
+// typename select_most_precise<
+// typename traits::coordinate_type<Indexable>::type,
+// typename traits::coordinate_type<Point>::type
+// >::type,
+// float // TODO - use bigger type, calculated from the size of coordinate types
+// >::type type;
+//
+//
+// BOOST_MPL_ASSERT_MSG((!::boost::is_unsigned<type>::value),
+// THIS_TYPE_SHOULDNT_BE_UNSIGNED, (type));
+//};
namespace dispatch {
@@ -40,16 +40,15 @@
BOOST_STATIC_ASSERT(I < traits::dimension<Point>::value);
BOOST_STATIC_ASSERT(traits::dimension<Point>::value == traits::dimension<Box>::value);
- typedef typename default_relative_distance_type<Box, Point>::type relative_distance_type;
-
- // WARNING! - relative_distance_type must be IEEE float for this to work
+ // WARNING! - RelativeDistance must be IEEE float for this to work
+ template <typename RelativeDistance>
static inline bool apply(Box const& b, Point const& p0, Point const& p1,
- relative_distance_type & t_near, relative_distance_type & t_far)
+ RelativeDistance & t_near, RelativeDistance & t_far)
{
- relative_distance_type ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
- relative_distance_type tn = ( detail::get<min_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
- relative_distance_type tf = ( detail::get<max_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
+ RelativeDistance ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
+ RelativeDistance tn = ( detail::get<min_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
+ RelativeDistance tf = ( detail::get<max_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
if ( tf < tn )
::std::swap(tn, tf);
@@ -68,10 +67,10 @@
BOOST_STATIC_ASSERT(0 < CurrentDimension);
typedef box_segment_intersection_dim<Box, Point, CurrentDimension - 1> for_dim;
- typedef typename for_dim::relative_distance_type relative_distance_type;
+ template <typename RelativeDistance>
static inline bool apply(Box const& b, Point const& p0, Point const& p1,
- relative_distance_type & t_near, relative_distance_type & t_far)
+ RelativeDistance & t_near, RelativeDistance & t_far)
{
return box_segment_intersection<Box, Point, CurrentDimension - 1>::apply(b, p0, p1, t_near, t_far)
&& for_dim::apply(b, p0, p1, t_near, t_far);
@@ -82,10 +81,10 @@
struct box_segment_intersection<Box, Point, 1>
{
typedef box_segment_intersection_dim<Box, Point, 0> for_dim;
- typedef typename for_dim::relative_distance_type relative_distance_type;
+ template <typename RelativeDistance>
static inline bool apply(Box const& b, Point const& p0, Point const& p1,
- relative_distance_type & t_near, relative_distance_type & t_far)
+ RelativeDistance & t_near, RelativeDistance & t_far)
{
return for_dim::apply(b, p0, p1, t_near, t_far);
}
@@ -107,12 +106,15 @@
struct segment_intersection<Indexable, Point, box_tag>
{
typedef dispatch::box_segment_intersection<Indexable, Point, detail::traits::dimension<Indexable>::value> impl;
- typedef typename impl::relative_distance_type relative_distance_type;
- static inline bool apply(Indexable const& b, Point const& p0, Point const& p1, relative_distance_type & relative_distance)
+ template <typename RelativeDistance>
+ static inline bool apply(Indexable const& b, Point const& p0, Point const& p1, RelativeDistance & relative_distance)
{
- relative_distance_type t_near = -(::std::numeric_limits<relative_distance_type>::max)();
- relative_distance_type t_far = (::std::numeric_limits<relative_distance_type>::max)();
+ static const bool check = !::boost::is_integral<RelativeDistance>::value;
+ BOOST_MPL_ASSERT_MSG(check, RELATIVE_DISTANCE_MUST_BE_FLOATING_POINT_TYPE, (RelativeDistance));
+
+ RelativeDistance t_near = -(::std::numeric_limits<RelativeDistance>::max)();
+ RelativeDistance t_far = (::std::numeric_limits<RelativeDistance>::max)();
return impl::apply(b, p0, p1, t_near, t_far) &&
(t_near <= 1) &&
@@ -122,11 +124,11 @@
} // namespace dispatch
-template <typename Indexable, typename Point> inline
+template <typename Indexable, typename Point, typename RelativeDistance> inline
bool segment_intersection(Indexable const& b,
Point const& p0,
Point const& p1,
- typename default_relative_distance_type<Indexable, Point>::type & relative_distance)
+ RelativeDistance & relative_distance)
{
// TODO check Indexable and Point concepts