summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/extreme_points.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/extreme_points.hpp')
-rw-r--r--boost/geometry/algorithms/detail/extreme_points.hpp93
1 files changed, 58 insertions, 35 deletions
diff --git a/boost/geometry/algorithms/detail/extreme_points.hpp b/boost/geometry/algorithms/detail/extreme_points.hpp
index 65795cd05b..61e984ee3c 100644
--- a/boost/geometry/algorithms/detail/extreme_points.hpp
+++ b/boost/geometry/algorithms/detail/extreme_points.hpp
@@ -5,6 +5,11 @@
// Copyright (c) 2009-2013 Mateusz Loskot, London, UK.
// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland.
+// This file was modified by Oracle on 2017.
+// Modifications copyright (c) 2017 Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
+
// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
@@ -117,12 +122,6 @@ struct extreme_points_on_ring
typedef typename boost::range_iterator<Ring const>::type range_iterator;
typedef typename geometry::point_type<Ring>::type point_type;
- typedef typename geometry::strategy::side::services::default_strategy
- <
- typename geometry::cs_tag<point_type>::type
- >::type side_strategy;
-
-
template <typename CirclingIterator, typename Points>
static inline bool extend(CirclingIterator& it,
std::size_t n,
@@ -214,10 +213,11 @@ struct extreme_points_on_ring
return true;
}
- template <typename Extremes, typename Intruders, typename CirclingIterator>
+ template <typename Extremes, typename Intruders, typename CirclingIterator, typename SideStrategy>
static inline void get_intruders(Ring const& ring, CirclingIterator left, CirclingIterator right,
Extremes const& extremes,
- Intruders& intruders)
+ Intruders& intruders,
+ SideStrategy const& strategy)
{
if (boost::size(extremes) < 3)
{
@@ -238,8 +238,8 @@ struct extreme_points_on_ring
if (coordinate > min_value && other_coordinate > other_min && other_coordinate < other_max)
{
int const factor = geometry::point_order<Ring>::value == geometry::clockwise ? 1 : -1;
- int const first_side = side_strategy::apply(*right, extremes.front(), *(extremes.begin() + 1)) * factor;
- int const last_side = side_strategy::apply(*right, *(extremes.rbegin() + 1), extremes.back()) * factor;
+ int const first_side = strategy.apply(*right, extremes.front(), *(extremes.begin() + 1)) * factor;
+ int const last_side = strategy.apply(*right, *(extremes.rbegin() + 1), extremes.back()) * factor;
// If not lying left from any of the extemes side
if (first_side != 1 && last_side != 1)
@@ -263,10 +263,11 @@ struct extreme_points_on_ring
}
}
- template <typename Extremes, typename Intruders>
+ template <typename Extremes, typename Intruders, typename SideStrategy>
static inline void get_intruders(Ring const& ring,
Extremes const& extremes,
- Intruders& intruders)
+ Intruders& intruders,
+ SideStrategy const& strategy)
{
std::size_t const n = boost::size(ring);
if (n >= 3)
@@ -275,12 +276,12 @@ struct extreme_points_on_ring
geometry::ever_circling_range_iterator<Ring const> right(ring);
++right;
- get_intruders(ring, left, right, extremes, intruders);
+ get_intruders(ring, left, right, extremes, intruders, strategy);
}
}
- template <typename Iterator>
- static inline bool right_turn(Ring const& ring, Iterator it)
+ template <typename Iterator, typename SideStrategy>
+ static inline bool right_turn(Ring const& ring, Iterator it, SideStrategy const& strategy)
{
typename std::iterator_traits<Iterator>::difference_type const index
= std::distance(boost::begin(ring), it);
@@ -295,8 +296,8 @@ struct extreme_points_on_ring
}
int const factor = geometry::point_order<Ring>::value == geometry::clockwise ? 1 : -1;
- int const first_side = side_strategy::apply(*(right - 1), *right, *left) * factor;
- int const last_side = side_strategy::apply(*left, *(left + 1), *right) * factor;
+ int const first_side = strategy.apply(*(right - 1), *right, *left) * factor;
+ int const last_side = strategy.apply(*left, *(left + 1), *right) * factor;
//std::cout << "Candidate at " << geometry::wkt(*it) << " first=" << first_side << " last=" << last_side << std::endl;
@@ -306,8 +307,11 @@ struct extreme_points_on_ring
// Gets the extreme segments (top point plus neighbouring points), plus intruders, if any, on the same ring
- template <typename Extremes, typename Intruders>
- static inline bool apply(Ring const& ring, Extremes& extremes, Intruders& intruders)
+ template <typename Extremes, typename Intruders, typename SideStrategy>
+ static inline bool apply(Ring const& ring,
+ Extremes& extremes,
+ Intruders& intruders,
+ SideStrategy const& strategy)
{
std::size_t const n = boost::size(ring);
if (n < 3)
@@ -321,7 +325,7 @@ struct extreme_points_on_ring
compare<Dimension> smaller;
for (range_iterator it = max_it + 1; it != boost::end(ring); ++it)
{
- if (smaller(*max_it, *it) && right_turn(ring, it))
+ if (smaller(*max_it, *it) && right_turn(ring, it, strategy))
{
max_it = it;
}
@@ -365,7 +369,7 @@ struct extreme_points_on_ring
std::copy(points.begin(), points.end(), std::back_inserter(extremes));
- get_intruders(ring, left, right, extremes, intruders);
+ get_intruders(ring, left, right, extremes, intruders, strategy);
return true;
}
@@ -403,8 +407,9 @@ struct extreme_points<Ring, Dimension, ring_tag>
template<typename Polygon, std::size_t Dimension>
struct extreme_points<Polygon, Dimension, polygon_tag>
{
- template <typename Extremes, typename Intruders>
- static inline bool apply(Polygon const& polygon, Extremes& extremes, Intruders& intruders)
+ template <typename Extremes, typename Intruders, typename SideStrategy>
+ static inline bool apply(Polygon const& polygon, Extremes& extremes, Intruders& intruders,
+ SideStrategy const& strategy)
{
typedef typename geometry::ring_type<Polygon>::type ring_type;
typedef detail::extreme_points::extreme_points_on_ring
@@ -412,7 +417,8 @@ struct extreme_points<Polygon, Dimension, polygon_tag>
ring_type, Dimension
> ring_implementation;
- if (! ring_implementation::apply(geometry::exterior_ring(polygon), extremes, intruders))
+ if (! ring_implementation::apply(geometry::exterior_ring(polygon),
+ extremes, intruders, strategy))
{
return false;
}
@@ -423,7 +429,7 @@ struct extreme_points<Polygon, Dimension, polygon_tag>
for (typename detail::interior_iterator<Polygon const>::type
it = boost::begin(rings); it != boost::end(rings); ++it)
{
- ring_implementation::get_intruders(*it, extremes, intruders);
+ ring_implementation::get_intruders(*it, extremes, intruders, strategy);
}
return true;
@@ -433,8 +439,9 @@ struct extreme_points<Polygon, Dimension, polygon_tag>
template<typename Box>
struct extreme_points<Box, 1, box_tag>
{
- template <typename Extremes, typename Intruders>
- static inline bool apply(Box const& box, Extremes& extremes, Intruders& )
+ template <typename Extremes, typename Intruders, typename SideStrategy>
+ static inline bool apply(Box const& box, Extremes& extremes, Intruders& ,
+ SideStrategy const& )
{
extremes.resize(4);
geometry::detail::assign_box_corners_oriented<false>(box, extremes);
@@ -446,8 +453,9 @@ struct extreme_points<Box, 1, box_tag>
template<typename Box>
struct extreme_points<Box, 0, box_tag>
{
- template <typename Extremes, typename Intruders>
- static inline bool apply(Box const& box, Extremes& extremes, Intruders& )
+ template <typename Extremes, typename Intruders, typename SideStrategy>
+ static inline bool apply(Box const& box, Extremes& extremes, Intruders& ,
+ SideStrategy const& )
{
extremes.resize(4);
geometry::detail::assign_box_corners_oriented<false>(box, extremes);
@@ -460,8 +468,9 @@ struct extreme_points<Box, 0, box_tag>
template<typename MultiPolygon, std::size_t Dimension>
struct extreme_points<MultiPolygon, Dimension, multi_polygon_tag>
{
- template <typename Extremes, typename Intruders>
- static inline bool apply(MultiPolygon const& multi, Extremes& extremes, Intruders& intruders)
+ template <typename Extremes, typename Intruders, typename SideStrategy>
+ static inline bool apply(MultiPolygon const& multi, Extremes& extremes,
+ Intruders& intruders, SideStrategy const& strategy)
{
// Get one for the very first polygon, that is (for the moment) enough.
// It is not guaranteed the "extreme" then, but for the current purpose
@@ -473,7 +482,7 @@ struct extreme_points<MultiPolygon, Dimension, multi_polygon_tag>
typename boost::range_value<MultiPolygon const>::type,
Dimension,
polygon_tag
- >::apply(*boost::begin(multi), extremes, intruders);
+ >::apply(*boost::begin(multi), extremes, intruders, strategy);
}
return false;
@@ -489,8 +498,18 @@ struct extreme_points<MultiPolygon, Dimension, multi_polygon_tag>
for Edge=0 in dimension 0, the right side)
\note We could specify a strategy (less/greater) to get bottom/left side too. However, until now we don't need that.
*/
-template <std::size_t Edge, typename Geometry, typename Extremes, typename Intruders>
-inline bool extreme_points(Geometry const& geometry, Extremes& extremes, Intruders& intruders)
+template
+<
+ std::size_t Edge,
+ typename Geometry,
+ typename Extremes,
+ typename Intruders,
+ typename SideStrategy
+>
+inline bool extreme_points(Geometry const& geometry,
+ Extremes& extremes,
+ Intruders& intruders,
+ SideStrategy const& strategy)
{
concepts::check<Geometry const>();
@@ -509,7 +528,11 @@ inline bool extreme_points(Geometry const& geometry, Extremes& extremes, Intrude
const
>();
- return dispatch::extreme_points<Geometry, Edge>::apply(geometry, extremes, intruders);
+ return dispatch::extreme_points
+ <
+ Geometry,
+ Edge
+ >::apply(geometry, extremes, intruders, strategy);
}