/usr/include/boost/geometry/algorithms
Edit: /usr/include/boost/geometry/algorithms/remove_spikes.hpp (9753B)
// Boost.Geometry (aka GGL, Generic Geometry Library)
// Copyright (c) 2007-2013 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2008-2013 Bruno Lalande, Paris, France.
// 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)
#ifndef BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
#define BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
/*
Remove spikes from a ring/polygon.
Ring (having 8 vertices, including closing vertex)
+------+
| |
| +--+
| | ^this "spike" is removed, can be located outside/inside the ring
+------+
(the actualy determination if it is removed is done by a strategy)
*/
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace remove_spikes
{
struct range_remove_spikes
{
template
static inline void apply(Range& range, SideStrategy const& strategy)
{
typedef typename point_type::type point_type;
std::size_t n = boost::size(range);
std::size_t const min_num_points = core_detail::closure::minimum_ring_size
<
geometry::closure::value
>::value - 1; // subtract one: a polygon with only one spike should result into one point
if (n < min_num_points)
{
return;
}
std::vector cleaned;
cleaned.reserve(n);
for (typename boost::range_iterator::type it = boost::begin(range);
it != boost::end(range); ++it)
{
// Add point
cleaned.push_back(*it);
while(cleaned.size() >= 3
&& detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - 3),
range::at(cleaned, cleaned.size() - 2),
range::back(cleaned),
strategy))
{
// Remove pen-ultimate point causing the spike (or which was equal)
cleaned.erase(cleaned.end() - 2);
}
}
typedef typename std::vector::iterator cleaned_iterator;
cleaned_iterator cleaned_b = cleaned.begin();
cleaned_iterator cleaned_e = cleaned.end();
std::size_t cleaned_count = cleaned.size();
// For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
if ( BOOST_GEOMETRY_CONDITION(geometry::closure::value == geometry::closed) )
{
--cleaned_e;
--cleaned_count;
}
bool found = false;
do
{
found = false;
// Check for spike in first point
while(cleaned_count >= 3
&& detail::is_spike_or_equal(*(cleaned_e - 2), // prev
*(cleaned_e - 1), // back
*(cleaned_b), // front
strategy))
{
--cleaned_e;
--cleaned_count;
found = true;
}
// Check for spike in second point
while(cleaned_count >= 3
&& detail::is_spike_or_equal(*(cleaned_e - 1), // back
*(cleaned_b), // front
*(cleaned_b + 1), // next
strategy))
{
++cleaned_b;
--cleaned_count;
found = true;
}
}
while (found);
if (cleaned_count == 2)
{
// Ticket #9871: open polygon with only two points.
// the second point forms, by definition, a spike
--cleaned_e;
//--cleaned_count;
}
// Close if necessary
if ( BOOST_GEOMETRY_CONDITION(geometry::closure::value == geometry::closed) )
{
BOOST_GEOMETRY_ASSERT(cleaned_e != cleaned.end());
*cleaned_e = *cleaned_b;
++cleaned_e;
//++cleaned_count;
}
// Copy output
geometry::clear(range);
std::copy(cleaned_b, cleaned_e, range::back_inserter(range));
}
};
struct polygon_remove_spikes
{
template
static inline void apply(Polygon& polygon, SideStrategy const& strategy)
{
typedef range_remove_spikes per_range;
per_range::apply(exterior_ring(polygon), strategy);
typename interior_return_type::type
rings = interior_rings(polygon);
for (typename detail::interior_iterator::type
it = boost::begin(rings); it != boost::end(rings); ++it)
{
per_range::apply(*it, strategy);
}
}
};
template
struct multi_remove_spikes
{
template
static inline void apply(MultiGeometry& multi, SideStrategy const& strategy)
{
for (typename boost::range_iterator::type
it = boost::begin(multi);
it != boost::end(multi);
++it)
{
SingleVersion::apply(*it, strategy);
}
}
};
}} // namespace detail::remove_spikes
#endif // DOXYGEN_NO_DETAIL
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
template
<
typename Geometry,
typename Tag = typename tag::type
>
struct remove_spikes
{
template
static inline void apply(Geometry&, SideStrategy const&)
{}
};
template
struct remove_spikes
: detail::remove_spikes::range_remove_spikes
{};
template
struct remove_spikes
: detail::remove_spikes::polygon_remove_spikes
{};
template
struct remove_spikes
: detail::remove_spikes::multi_remove_spikes
<
detail::remove_spikes::polygon_remove_spikes
>
{};
} // namespace dispatch
#endif
namespace resolve_variant {
template
struct remove_spikes
{
template
static void apply(Geometry& geometry, Strategy const& strategy)
{
concepts::check();
dispatch::remove_spikes::apply(geometry, strategy);
}
static void apply(Geometry& geometry, geometry::default_strategy const&)
{
typedef typename strategy::side::services::default_strategy
<
typename cs_tag::type
>::type side_strategy;
apply(geometry, side_strategy());
}
};
template
struct remove_spikes >
{
template
struct visitor: boost::static_visitor
{
Strategy const& m_strategy;
visitor(Strategy const& strategy) : m_strategy(strategy) {}
template
void operator()(Geometry& geometry) const
{
remove_spikes::apply(geometry, m_strategy);
}
};
template
static inline void apply(boost::variant& geometry,
Strategy const& strategy)
{
boost::apply_visitor(visitor(strategy), geometry);
}
};
} // namespace resolve_variant
/*!
\ingroup remove_spikes
\tparam Geometry geometry type
\param geometry the geometry to make remove_spikes
*/
template
inline void remove_spikes(Geometry& geometry)
{
resolve_variant::remove_spikes::apply(geometry, geometry::default_strategy());
}
/*!
\ingroup remove_spikes
\tparam Geometry geometry type
\tparam Strategy side strategy type
\param geometry the geometry to make remove_spikes
\param strategy the side strategy used by the algorithm
*/
template
inline void remove_spikes(Geometry& geometry, Strategy const& strategy)
{
resolve_variant::remove_spikes::apply(geometry, strategy);
}
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP