/usr/include/boost/geometry/algorithms
Edit: /usr/include/boost/geometry/algorithms/is_convex.hpp (6508B)
// 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace is_convex
{
struct ring_is_convex
{
template
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::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 view_type;
view_type view(ring);
typedef geometry::ever_circling_range_iterator 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::type
>
struct is_convex : not_implemented
{};
template
struct is_convex
{
template
static inline bool apply(Box const& , Strategy const& )
{
// Any box is convex (TODO: consider spherical boxes)
return true;
}
};
template
struct is_convex : detail::is_convex::ring_is_convex
{};
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
namespace resolve_variant {
template
struct is_convex
{
template
static bool apply(Geometry const& geometry, Strategy const& strategy)
{
concepts::check();
return dispatch::is_convex::apply(geometry, strategy);
}
static bool apply(Geometry const& geometry, geometry::default_strategy const&)
{
typedef typename strategy::side::services::default_strategy
<
typename cs_tag::type
>::type side_strategy;
return apply(geometry, side_strategy());
}
};
template
struct is_convex >
{
template
struct visitor: boost::static_visitor
{
Strategy const& m_strategy;
visitor(Strategy const& strategy) : m_strategy(strategy) {}
template
bool operator()(Geometry const& geometry) const
{
return is_convex::apply(geometry, m_strategy);
}
};
template
static inline bool apply(boost::variant const& geometry,
Strategy const& strategy)
{
return boost::apply_visitor(visitor(strategy), geometry);
}
};
} // namespace resolve_variant
// TODO: documentation / qbk
template
inline bool is_convex(Geometry const& geometry)
{
return resolve_variant::is_convex
<
Geometry
>::apply(geometry, geometry::default_strategy());
}
// TODO: documentation / qbk
template
inline bool is_convex(Geometry const& geometry, Strategy const& strategy)
{
return resolve_variant::is_convex::apply(geometry, strategy);
}
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP