Chris@16: // Boost.Geometry Index
Chris@16: //
Chris@16: // minmaxdist used in R-tree k nearest neighbors query
Chris@16: //
Chris@101: // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
Chris@16: //
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP
Chris@16: #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/distance.hpp>
Chris@16: #include <boost/geometry/algorithms/comparable_distance.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/algorithms/diff_abs.hpp>
Chris@16: #include <boost/geometry/index/detail/algorithms/sum_for_indexable.hpp>
Chris@16: #include <boost/geometry/index/detail/algorithms/smallest_for_indexable.hpp>
Chris@16: 
Chris@16: namespace boost { namespace geometry { namespace index { namespace detail {
Chris@16: 
Chris@16: struct minmaxdist_tag {};
Chris@16: 
Chris@16: template <
Chris@16:     typename Point,
Chris@16:     typename BoxIndexable,
Chris@16:     size_t DimensionIndex>
Chris@16: struct smallest_for_indexable_dimension<Point, BoxIndexable, box_tag, minmaxdist_tag, DimensionIndex>
Chris@16: {
Chris@101:     typedef typename geometry::default_comparable_distance_result<Point, BoxIndexable>::type result_type;
Chris@16: 
Chris@16:     inline static result_type apply(Point const& pt, BoxIndexable const& i, result_type const& maxd)
Chris@16:     {
Chris@16:         typedef typename coordinate_type<Point>::type point_coord_t;
Chris@16:         typedef typename coordinate_type<BoxIndexable>::type indexable_coord_t;
Chris@16: 
Chris@16:         point_coord_t pt_c = geometry::get<DimensionIndex>(pt);
Chris@16:         indexable_coord_t ind_c_min = geometry::get<geometry::min_corner, DimensionIndex>(i);
Chris@16:         indexable_coord_t ind_c_max = geometry::get<geometry::max_corner, DimensionIndex>(i);
Chris@16: 
Chris@16:         indexable_coord_t ind_c_avg = ind_c_min + (ind_c_max - ind_c_min) / 2;
Chris@16:         // TODO: awulkiew - is (ind_c_min + ind_c_max) / 2 safe?
Chris@16: 
Chris@16:         // TODO: awulkiew - optimize! don't calculate 2x pt_c <= ind_c_avg
Chris@16:         // take particular case pt_c == ind_c_avg into account
Chris@16: 
Chris@16:         result_type closer_comp = 0;
Chris@16:         if ( pt_c <= ind_c_avg )
Chris@16:             closer_comp = detail::diff_abs(pt_c, ind_c_min); // unsigned values protection
Chris@16:         else
Chris@16:             closer_comp = ind_c_max - pt_c;
Chris@16:         
Chris@16:         result_type further_comp = 0;
Chris@16:         if ( ind_c_avg <= pt_c )
Chris@16:             further_comp = pt_c - ind_c_min;
Chris@16:         else
Chris@16:             further_comp = detail::diff_abs(pt_c, ind_c_max); // unsigned values protection
Chris@16: 
Chris@16:         return (maxd + closer_comp * closer_comp) - further_comp * further_comp;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Point, typename Indexable, typename IndexableTag>
Chris@16: struct minmaxdist_impl
Chris@16: {
Chris@16:     BOOST_MPL_ASSERT_MSG(
Chris@16:         (false),
Chris@16:         NOT_IMPLEMENTED_FOR_THIS_INDEXABLE_TAG_TYPE,
Chris@16:         (minmaxdist_impl));
Chris@16: };
Chris@16: 
Chris@16: template <typename Point, typename Indexable>
Chris@16: struct minmaxdist_impl<Point, Indexable, point_tag>
Chris@16: {
Chris@101:     typedef typename geometry::default_comparable_distance_result<Point, Indexable>::type result_type;
Chris@16: 
Chris@16:     inline static result_type apply(Point const& pt, Indexable const& i)
Chris@16:     {
Chris@16:         return geometry::comparable_distance(pt, i);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Point, typename Indexable>
Chris@16: struct minmaxdist_impl<Point, Indexable, box_tag>
Chris@16: {
Chris@101:     typedef typename geometry::default_comparable_distance_result<Point, Indexable>::type result_type;
Chris@16: 
Chris@16:     inline static result_type apply(Point const& pt, Indexable const& i)
Chris@16:     {
Chris@16:         result_type maxd = geometry::comparable_distance(pt, i);
Chris@16: 
Chris@16:         return smallest_for_indexable<
Chris@16:             Point,
Chris@16:             Indexable,
Chris@16:             box_tag,
Chris@16:             minmaxdist_tag,
Chris@16:             dimension<Indexable>::value
Chris@16:         >::apply(pt, i, maxd);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * This is comparable distace.
Chris@16:  */
Chris@16: template <typename Point, typename Indexable>
Chris@101: typename geometry::default_comparable_distance_result<Point, Indexable>::type
Chris@16: minmaxdist(Point const& pt, Indexable const& i)
Chris@16: {
Chris@16:     return detail::minmaxdist_impl<
Chris@16:         Point,
Chris@16:         Indexable,
Chris@16:         typename tag<Indexable>::type
Chris@16:     >::apply(pt, i);
Chris@16: }
Chris@16: 
Chris@16: }}}} // namespace boost::geometry::index::detail
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP