// Boost.Geometry (aka GGL, Generic Geometry Library)
|
|
// Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
|
|
// This file was modified by Oracle on 2017, 2018.
|
// Modifications copyright (c) 2017-2018 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)
|
|
#ifndef BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP
|
#define BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP
|
|
|
#include <boost/variant/apply_visitor.hpp>
|
#include <boost/variant/static_visitor.hpp>
|
#include <boost/variant/variant_fwd.hpp>
|
|
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
|
#include <boost/geometry/core/access.hpp>
|
#include <boost/geometry/core/closure.hpp>
|
#include <boost/geometry/core/cs.hpp>
|
#include <boost/geometry/core/coordinate_dimension.hpp>
|
#include <boost/geometry/core/point_type.hpp>
|
#include <boost/geometry/geometries/concepts/check.hpp>
|
#include <boost/geometry/iterators/ever_circling_iterator.hpp>
|
#include <boost/geometry/strategies/default_strategy.hpp>
|
#include <boost/geometry/strategies/side.hpp>
|
#include <boost/geometry/views/detail/normalized_view.hpp>
|
|
|
namespace boost { namespace geometry
|
{
|
|
|
#ifndef DOXYGEN_NO_DETAIL
|
namespace detail { namespace is_convex
|
{
|
|
struct ring_is_convex
|
{
|
template <typename Ring, typename SideStrategy>
|
static inline bool apply(Ring const& ring, SideStrategy const& strategy)
|
{
|
typename SideStrategy::equals_point_point_strategy_type
|
eq_pp_strategy = strategy.get_equals_point_point_strategy();
|
|
std::size_t n = boost::size(ring);
|
if (boost::size(ring) < core_detail::closure::minimum_ring_size
|
<
|
geometry::closure<Ring>::value
|
>::value)
|
{
|
// (Too) small rings are considered as non-concave, is convex
|
return true;
|
}
|
|
// Walk in clockwise direction, consider ring as closed
|
// (though closure is not important in this algorithm - any dupped
|
// point is skipped)
|
typedef detail::normalized_view<Ring const> view_type;
|
view_type view(ring);
|
|
typedef geometry::ever_circling_range_iterator<view_type const> it_type;
|
it_type previous(view);
|
it_type current(view);
|
current++;
|
|
std::size_t index = 1;
|
while (equals::equals_point_point(*current, *previous, eq_pp_strategy)
|
&& index < n)
|
{
|
current++;
|
index++;
|
}
|
|
if (index == n)
|
{
|
// All points are apparently equal
|
return true;
|
}
|
|
it_type next = current;
|
next++;
|
while (equals::equals_point_point(*current, *next, eq_pp_strategy))
|
{
|
next++;
|
}
|
|
// We have now three different points on the ring
|
// Walk through all points, use a counter because of the ever-circling
|
// iterator
|
for (std::size_t i = 0; i < n; i++)
|
{
|
int const side = strategy.apply(*previous, *current, *next);
|
if (side == 1)
|
{
|
// Next is on the left side of clockwise ring:
|
// the piece is not convex
|
return false;
|
}
|
|
previous = current;
|
current = next;
|
|
// Advance next to next different point
|
// (because there are non-equal points, this loop is not infinite)
|
next++;
|
while (equals::equals_point_point(*current, *next, eq_pp_strategy))
|
{
|
next++;
|
}
|
}
|
return true;
|
}
|
};
|
|
|
}} // namespace detail::is_convex
|
#endif // DOXYGEN_NO_DETAIL
|
|
|
#ifndef DOXYGEN_NO_DISPATCH
|
namespace dispatch
|
{
|
|
template
|
<
|
typename Geometry,
|
typename Tag = typename tag<Geometry>::type
|
>
|
struct is_convex : not_implemented<Tag>
|
{};
|
|
template <typename Box>
|
struct is_convex<Box, box_tag>
|
{
|
template <typename Strategy>
|
static inline bool apply(Box const& , Strategy const& )
|
{
|
// Any box is convex (TODO: consider spherical boxes)
|
return true;
|
}
|
};
|
|
template <typename Box>
|
struct is_convex<Box, ring_tag> : detail::is_convex::ring_is_convex
|
{};
|
|
|
} // namespace dispatch
|
#endif // DOXYGEN_NO_DISPATCH
|
|
namespace resolve_variant {
|
|
template <typename Geometry>
|
struct is_convex
|
{
|
template <typename Strategy>
|
static bool apply(Geometry const& geometry, Strategy const& strategy)
|
{
|
concepts::check<Geometry>();
|
return dispatch::is_convex<Geometry>::apply(geometry, strategy);
|
}
|
|
static bool apply(Geometry const& geometry, geometry::default_strategy const&)
|
{
|
typedef typename strategy::side::services::default_strategy
|
<
|
typename cs_tag<Geometry>::type
|
>::type side_strategy;
|
|
return apply(geometry, side_strategy());
|
}
|
};
|
|
template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
|
struct is_convex<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
|
{
|
template <typename Strategy>
|
struct visitor: boost::static_visitor<bool>
|
{
|
Strategy const& m_strategy;
|
|
visitor(Strategy const& strategy) : m_strategy(strategy) {}
|
|
template <typename Geometry>
|
bool operator()(Geometry const& geometry) const
|
{
|
return is_convex<Geometry>::apply(geometry, m_strategy);
|
}
|
};
|
|
template <typename Strategy>
|
static inline bool apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
|
Strategy const& strategy)
|
{
|
return boost::apply_visitor(visitor<Strategy>(strategy), geometry);
|
}
|
};
|
|
} // namespace resolve_variant
|
|
// TODO: documentation / qbk
|
template<typename Geometry>
|
inline bool is_convex(Geometry const& geometry)
|
{
|
return resolve_variant::is_convex
|
<
|
Geometry
|
>::apply(geometry, geometry::default_strategy());
|
}
|
|
// TODO: documentation / qbk
|
template<typename Geometry, typename Strategy>
|
inline bool is_convex(Geometry const& geometry, Strategy const& strategy)
|
{
|
return resolve_variant::is_convex<Geometry>::apply(geometry, strategy);
|
}
|
|
|
}} // namespace boost::geometry
|
|
|
#endif // BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP
|
