|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r86450 - in trunk: boost/geometry/algorithms boost/geometry/extensions/algorithms boost/geometry/multi/algorithms libs/geometry/doc libs/geometry/test/algorithms
From: barend.gehrels_at_[hidden]
Date: 2013-10-26 09:18:11
Author: barendgehrels
Date: 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013)
New Revision: 86450
URL: http://svn.boost.org/trac/boost/changeset/86450
Log:
[geometry] Added remove_spikes as an algorithm. The first version was already in extensions (for years), that is removed now. The new version works using the recent point_is_spike_or_equal
Added:
trunk/boost/geometry/algorithms/remove_spikes.hpp (contents, props changed)
trunk/boost/geometry/multi/algorithms/remove_spikes.hpp (contents, props changed)
trunk/libs/geometry/test/algorithms/remove_spikes.cpp (contents, props changed)
Deleted:
trunk/boost/geometry/extensions/algorithms/mark_spikes.hpp
trunk/boost/geometry/extensions/algorithms/remove_spikes.hpp
Text files modified:
trunk/boost/geometry/algorithms/remove_spikes.hpp | 208 ++++++++++++++++
/dev/null | 516 ----------------------------------------
trunk/boost/geometry/extensions/algorithms/remove_marked.hpp | 3
/dev/null | 378 -----------------------------
trunk/boost/geometry/multi/algorithms/remove_spikes.hpp | 79 ++++++
trunk/libs/geometry/doc/release_notes.qbk | 4
trunk/libs/geometry/test/algorithms/Jamfile.v2 | 1
trunk/libs/geometry/test/algorithms/remove_spikes.cpp | 165 ++++++++++++
8 files changed, 459 insertions(+), 895 deletions(-)
Added: trunk/boost/geometry/algorithms/remove_spikes.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/algorithms/remove_spikes.hpp 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013) (r86450)
@@ -0,0 +1,208 @@
+// 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 Adam Wulkiewicz, Lodz, Poland.
+
+// 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 <deque>
+
+#include <boost/range.hpp>
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/geometry/core/closure.hpp>
+#include <boost/geometry/core/coordinate_type.hpp>
+#include <boost/geometry/core/cs.hpp>
+#include <boost/geometry/core/interior_rings.hpp>
+#include <boost/geometry/geometries/concepts/check.hpp>
+#include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
+#include <boost/geometry/algorithms/clear.hpp>
+
+
+/*
+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
+{
+
+
+template <typename Range>
+struct range_remove_spikes
+{
+ typedef typename strategy::side::services::default_strategy
+ <
+ typename cs_tag<Range>::type
+ >::type side_strategy;
+
+ typedef typename coordinate_type<Range>::type coordinate_type;
+ typedef typename point_type<Range>::type point_type;
+
+
+ static inline void apply(Range& range)
+ {
+ std::size_t n = boost::size(range);
+ std::size_t const min_num_points = core_detail::closure::minimum_ring_size
+ <
+ geometry::closure<Range>::value
+ >::value;
+ if (n < min_num_points)
+ {
+ return;
+ }
+
+ typedef typename boost::range_iterator<Range>::type iterator;
+
+ std::deque<point_type> cleaned;
+ for (typename boost::range_iterator<Range const>::type it = boost::begin(range);
+ it != boost::end(range); ++it)
+ {
+ // Add point
+ cleaned.push_back(*it);
+
+ while(cleaned.size() >= 3
+ && detail::point_is_spike_or_equal(cleaned.back(), *(cleaned.end() - 3), *(cleaned.end() - 2)))
+ {
+ // Remove pen-ultimate point causing the spike (or which was equal)
+ cleaned.erase(cleaned.end() - 2);
+ }
+ }
+
+ // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
+ if (geometry::closure<Range>::value == geometry::closed)
+ {
+ cleaned.pop_back();
+ }
+
+ bool found = false;
+ do
+ {
+ found = false;
+ // Check for spike in first point
+ int const penultimate = 2;
+ while(cleaned.size() > 3 && detail::point_is_spike_or_equal(cleaned.front(), *(cleaned.end() - penultimate), cleaned.back()))
+ {
+ cleaned.pop_back();
+ found = true;
+ }
+ // Check for spike in second point
+ while(cleaned.size() > 3 && detail::point_is_spike_or_equal(*(cleaned.begin() + 1), cleaned.back(), cleaned.front()))
+ {
+ cleaned.pop_front();
+ found = true;
+ }
+ }
+ while (found);
+
+ // Close if necessary
+ if (geometry::closure<Range>::value == geometry::closed)
+ {
+ cleaned.push_back(cleaned.front());
+ }
+
+ // Copy output
+ geometry::clear(range);
+ std::copy(cleaned.begin(), cleaned.end(), std::back_inserter(range));
+ }
+};
+
+
+template <typename Polygon>
+struct polygon_remove_spikes
+{
+ static inline void apply(Polygon& polygon)
+ {
+ typedef typename geometry::ring_type<Polygon>::type ring_type;
+
+ typedef range_remove_spikes<ring_type> per_range;
+ per_range::apply(exterior_ring(polygon));
+
+ typename interior_return_type<Polygon>::type rings
+ = interior_rings(polygon);
+ for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
+ {
+ per_range::apply(*it);
+ }
+ }
+};
+
+
+}} // namespace detail::remove_spikes
+#endif // DOXYGEN_NO_DETAIL
+
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+
+template
+<
+ typename Geometry,
+ typename Tag = typename tag<Geometry>::type
+>
+struct remove_spikes
+{
+ static inline void apply(Geometry&)
+ {}
+};
+
+
+template <typename Ring>
+struct remove_spikes<Ring, ring_tag>
+ : detail::remove_spikes::range_remove_spikes<Ring>
+{};
+
+
+
+template <typename Polygon>
+struct remove_spikes<Polygon, polygon_tag>
+ : detail::remove_spikes::polygon_remove_spikes<Polygon>
+{};
+
+
+
+} // namespace dispatch
+#endif
+
+
+/*!
+ \ingroup remove_spikes
+ \tparam Geometry geometry type
+ \param geometry the geometry to make remove_spikes
+*/
+template <typename Geometry>
+inline void remove_spikes(Geometry& geometry)
+{
+ concept::check<Geometry>();
+
+ dispatch::remove_spikes<Geometry>::apply(geometry);
+}
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
Deleted: trunk/boost/geometry/extensions/algorithms/mark_spikes.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/mark_spikes.hpp 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013) (r86449)
+++ /dev/null 00:00:00 1970 (deleted)
@@ -1,516 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-
-// Copyright (c) 2010-2012 Barend Gehrels, Amsterdam, the Netherlands.
-
-// 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_EXTENSIONS_ALGORITHMS_MARK_SPIKES_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_ALGORITHMS_MARK_SPIKES_HPP
-
-#include <algorithm>
-
-#include <boost/range.hpp>
-
-#include <boost/geometry/multi/core/tags.hpp>
-
-
-#include <boost/geometry/core/coordinate_type.hpp>
-#include <boost/geometry/core/cs.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
-#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
-#include <boost/geometry/strategies/cartesian/area_surveyor.hpp>
-#include <boost/geometry/util/math.hpp>
-
-#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
-
-#include <boost/geometry/algorithms/area.hpp>
-#include <boost/geometry/algorithms/buffer.hpp>
-#include <boost/geometry/algorithms/distance.hpp>
-#include <boost/geometry/algorithms/perimeter.hpp>
-
-#include <boost/geometry/geometries/box.hpp>
-
-
-/*
-Mark spikes in a ring/polygon.
-Ring
-+---------+
-| |
-| |
-| +===== ^this "indentation" or "intrusion" or "spikey feature" is marked
-| || |
-| || |
-| ++ |
-+---------+
-(the actualy determination if it is marked is done by a policy)
-(things are only marked, removal is done afterwards)
-
-*/
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace mark_spikes
-{
-
-template <typename Range, typename Iterator>
-inline Iterator circular_next(Range const& range, Iterator it)
-{
- ++it;
- if (it == boost::end(range))
- {
- it = boost::begin(range);
- }
- return it;
-}
-
-inline std::size_t circular_next_i(std::size_t i, std::size_t const n)
-{
- if (++i == n)
- {
- i = 0;
- }
- return i;
-}
-
-
-// Calculate the distance over the ring, in the range [it1 .. it2]
-// if it1 < it2: walk from it1 .. it2
-// if it1 > it2: walk from it1 .. end(ring) and from begin(ring) to it2
-// Do NOT call this using begin(ring), end(ring) or 0.0 will be returned
-template
-<
- typename Range,
- typename Iterator,
- typename AreaStrategy,
- typename DistanceStrategy
->
-inline void part_area_and_perimeter(Range const& range,
- Iterator it1, Iterator it2,
- AreaStrategy const& area_strategy,
- DistanceStrategy const& distance_strategy,
- double& area, double& perimeter, int& count)
-{
- perimeter = 0;
- area = 0;
- count = 0;
- if (it1 == boost::end(range) || it2 == boost::end(range) || it1 == it2)
- {
- return;
- }
-
- typename AreaStrategy::state_type area_state;
- Iterator it = circular_next(range, it1), previous = it1;
- Iterator end = circular_next(range, it2);
- while (it != end)
- {
- area_strategy.apply(*previous, *it, area_state);
- perimeter += distance_strategy.apply(*previous, *it);
- previous = it;
- it = circular_next(range, it);
- count++;
- }
-
- // Close the ring, for area
- area_strategy.apply(*it2, *it1, area_state);
- // Do the same for distance to get correct ratio (though this might be discussed)
- perimeter += distance_strategy.apply(*it2, *it1);
-
- area = geometry::math::abs(area_strategy.result(area_state));
-}
-
-
-template <typename Iterator>
-struct helper
-{
- helper(int i1, int i2, Iterator t1, Iterator t2,
- double g, double a, double p, int c)
- : index1(i1)
- , index2(i2)
- , it1(t1)
- , it2(t2)
- , gap_distance(g)
- , area(a)
- , perimeter(p)
- , count(c)
- {
- }
-
- int index1, index2;
- Iterator it1, it2;
- double area, perimeter, gap_distance;
- int count;
-
- inline bool operator<(helper<Iterator> const& other) const
- {
- return this->count > other.count;
- }
-};
-
-
-template <typename Range, typename MarkMap, typename Policy>
-struct range_mark_spikes
-{
- typedef typename point_type<Range>::type point_type;
-
- typedef typename strategy::side::services::default_strategy
- <
- typename cs_tag<Range>::type
- >::type side_strategy_type;
-
- typedef typename strategy::area::services::default_strategy
- <
- typename cs_tag<point_type>::type,
- point_type
- >::type area_strategy_type;
-
- typedef typename strategy::distance::services::default_strategy
- <
- point_tag,
- point_type,
- point_type
- >::type distance_strategy_type;
-
- static inline void apply(Range const& range, ring_identifier id,
- MarkMap& mark_map, Policy const& policy)
- {
- std::size_t const n = boost::size(range);
- if (n < 5)
- {
- return;
- }
-
- typedef typename boost::range_iterator<Range const>::type iterator_type;
-
- // Divide polygon in monotonic sections (in two directions)
- typedef model::box<point_type> box_type;
- typedef geometry::sections<box_type, 2> sections_type;
- sections_type sections;
- geometry::sectionalize<false>(range, sections);
-
- for (typename boost::range_iterator<sections_type>::type it = boost::begin(sections);
- it != boost::end(sections);
- ++it)
- {
- // Enlarge each box with the wished max with of the gap to be sure that
- // when walking through sections all point-pairs are considered
- geometry::buffer(it->bounding_box, it->bounding_box, policy.gap_width() * 1.001);
- }
-
- double const whole_area = geometry::area(range);
-
-
- typedef typename boost::range_iterator<sections_type>::type section_iterator_type;
-
-
- // Find pair-of-points lying the most close to each other,
- // where:
- // - it is in another section
- // - the distance over the ring-part is larger than X
- // - the area of the polygon formed by that ring-part smaller than X
-
- typedef helper<iterator_type> helper_type;
- typedef std::vector<helper_type> helper_vector_type;
- helper_vector_type candidates;
-
- // Quadratic loop over all sections (note this normally does not result in a quadratic loop
- // over all points).
- for(section_iterator_type sit1 = boost::begin(sections); sit1 != boost::end(sections); ++sit1)
- {
- // Note, even though combination sit1/sit2 is handled, the combination sit2/sit1 travels
- // another part over the ring and should be handled as well
- for(section_iterator_type sit2 = boost::begin(sections); sit2 != boost::end(sections); ++sit2)
- {
- if (sit1->id != sit2->id
- && ! geometry::disjoint(sit1->bounding_box, sit2->bounding_box))
- {
- // Check all point combinations in these boxes
- int index1 = sit1->begin_index;
- iterator_type it1 = boost::begin(range) + sit1->begin_index;
- for (unsigned int i = 0; i < sit1->count; i++, ++it1, ++index1)
- {
- iterator_type it2 = boost::begin(range) + sit2->begin_index;
- int index2 = sit2->begin_index;
- for (unsigned int j = 0; j < sit2->count; j++, ++it2, ++index2)
- {
- double dg = geometry::distance(*it1, *it2);
- if (dg < policy.gap_width())
- {
- double area, perimeter;
- int count;
- part_area_and_perimeter(range, it1, it2,
- area_strategy_type(), distance_strategy_type(),
- area, perimeter, count);
-
- if (count >= 2
- && policy.apply(dg, whole_area, count, area, perimeter))
- {
- candidates.push_back(
- helper_type(index1, index2, it1, it2, dg, area, perimeter, count));
- }
- }
- }
- }
- }
- }
- }
-
- if (boost::size(candidates) == 0)
- {
- return;
- }
-
- std::sort(candidates.begin(), candidates.end());
-
- /***
- if (boost::size(candidates) > 1)
- {
-
- // Remove overlaps
- bool first = true;
- typename boost::range_iterator<helper_vector_type>::type it = boost::begin(candidates);
- typename boost::range_iterator<helper_vector_type>::type prev = it;
- ++it;
- while (it != boost::end(candidates))
- {
-
- if ((it->index1 >= prev->index1 && it->index2 <= prev->index2)
-
- )
- {
- candidates.erase(it);
- it = prev + 1;
- }
- else
- {
- prev = it;
- }
- }
- }
- ***/
-
- // Check if some index combinations refer to larger combinations
-#if defined(BOOST_GEOMETRY_DEBUG_MARK_SPIKES)
- for(typename boost::range_iterator<helper_vector_type>::type it
- = boost::begin(candidates); it != boost::end(candidates); ++it)
- {
- std::cout << it->count << " " << it->index1 << " " << it->index2
- << " gd=" << it->gap_distance
- << " a=" << it->area << " p=" << it->perimeter
- << " r=" << (it->perimeter > 0 ? it->area / it->perimeter : 0)
- // << " p1=" << geometry::wkt(*it->it1) << " p2=" << geometry::wkt(*it->it2)
- << std::endl;
- }
-#endif
-
- typedef typename MarkMap::mapped_type bit_vector_type;
-
- // Add new vector to map if necessary
- if (mark_map.find(id) == mark_map.end())
- {
- // Add one to vector
- mark_map[id] = bit_vector_type();
-
- // Initialize it
- bit_vector_type& bits = mark_map[id];
- for (std::size_t i = 0; i < n; i++)
- {
- bits.push_back(false);
- }
- }
-
- bit_vector_type& bits = mark_map[id];
-
- // Mark this range or these ranges
- // TODO: we might use the fact that it is sorted and that ranges are inside others,
- // so skip those...
- for(typename boost::range_iterator<helper_vector_type const>::type it
- = boost::begin(candidates); it != boost::end(candidates); ++it)
- {
- iterator_type pit = boost::begin(range) + it->index1;
- iterator_type end = boost::begin(range) + it->index2;
- int i = it->index1;
- while (pit != end)
- {
- if (i != it->index1 && i != it->index2)
- {
- bits[i] = true;
- }
- pit = circular_next(range, pit);
- i = circular_next_i(i, n);
- }
- }
- }
-};
-
-
-template <typename Polygon, typename MarkMap, typename Policy>
-struct polygon_mark_spikes
-{
- static inline void apply(Polygon const& polygon, ring_identifier id,
- MarkMap& mark_map, Policy const& policy)
- {
- typedef typename geometry::ring_type<Polygon>::type ring_type;
-
- typedef range_mark_spikes<ring_type, MarkMap, Policy> per_range;
-
- // Exterior ring (-1)
- id.ring_index = -1;
- per_range::apply(exterior_ring(polygon), id, mark_map, policy);
-
- typename interior_return_type<Polygon const>::type rings
- = interior_rings(polygon);
- for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
- {
- // Interior ring (zero based)
- id.ring_index++;
- per_range::apply(*it, id, mark_map, policy);
- }
- }
-};
-
-
-template <typename MultiGeometry, typename MarkMap, typename Policy, typename SinglePolicy>
-struct multi_mark_spikes
-{
- static inline void apply(MultiGeometry const& multi, ring_identifier id,
- MarkMap& mark_map, Policy const& policy)
- {
- id.multi_index = 0;
- for (typename boost::range_iterator<MultiGeometry const>::type
- it = boost::begin(multi);
- it != boost::end(multi);
- ++it)
- {
- SinglePolicy::apply(*it, id, mark_map, policy);
- id.multi_index++;
- }
- }
-};
-
-
-}} // namespace detail::mark_spikes
-#endif // DOXYGEN_NO_DETAIL
-
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename Tag,
- typename Geometry,
- typename MarkMap,
- typename Policy
->
-struct mark_spikes
-{
- static inline void apply(Geometry&, Policy const&)
- {}
-};
-
-
-template <typename Ring, typename MarkMap, typename Policy>
-struct mark_spikes<ring_tag, Ring, MarkMap, Policy>
- : detail::mark_spikes::range_mark_spikes<Ring, MarkMap, Policy>
-{};
-
-
-
-template <typename Polygon, typename MarkMap, typename Policy>
-struct mark_spikes<polygon_tag, Polygon, MarkMap, Policy>
- : detail::mark_spikes::polygon_mark_spikes<Polygon, MarkMap, Policy>
-{};
-
-
-template <typename MultiPolygon, typename MarkMap, typename Policy>
-struct mark_spikes<multi_polygon_tag, MultiPolygon, MarkMap, Policy>
- : detail::mark_spikes::multi_mark_spikes
- <
- MultiPolygon,
- MarkMap,
- Policy,
- detail::mark_spikes::polygon_mark_spikes
- <
- typename boost::range_value<MultiPolygon>::type,
- MarkMap,
- Policy
- >
- >
-{};
-
-
-
-} // namespace dispatch
-#endif
-
-
-/*!
- \ingroup mark_spikes
- \tparam Geometry geometry type
- \param geometry the geometry to make mark_spikes
-*/
-template <typename Geometry, typename MarkMap, typename Policy>
-inline bool mark_spikes(Geometry const& geometry,
- MarkMap& mark_map,
- Policy const& policy)
-{
- concept::check<Geometry const>();
-
- ring_identifier id;
-
- dispatch::mark_spikes
- <
- typename tag<Geometry>::type,
- Geometry,
- MarkMap,
- Policy
- >::apply(geometry, id, mark_map, policy);
- return mark_map.size() > 0;
-}
-
-template <typename T = double>
-class select_gapped_spike
-{
-public :
- inline select_gapped_spike(T const gap_width, T const ratio = 0.1)
- : m_gap_width(gap_width)
- , m_ratio(ratio)
- {}
-
-
- inline T gap_width() const
- {
- return m_gap_width;
- }
-
- inline bool apply(T const gap_distance, T const whole_area,
- int count, T const area, T const perimeter) const
- {
- T const ratio = perimeter == 0 ? 0 : area / perimeter;
- return
- perimeter > gap_distance
- && area < whole_area / 10.0
- && ratio < m_ratio;
- }
-
-
-private :
- T m_gap_width;
- T m_ratio;
-};
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_EXTENSIONS_ALGORITHMS_MARK_SPIKES_HPP
Modified: trunk/boost/geometry/extensions/algorithms/remove_marked.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/remove_marked.hpp Sat Oct 26 08:39:50 2013 (r86449)
+++ trunk/boost/geometry/extensions/algorithms/remove_marked.hpp 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013) (r86450)
@@ -12,7 +12,8 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_ALGORITHMS_REMOVE_MARKED_HPP
#define BOOST_GEOMETRY_EXTENSIONS_ALGORITHMS_REMOVE_MARKED_HPP
-
+// PROBABLY OBSOLETE
+// as mark_spikes is now replaced by remove_spikes
#include <boost/range.hpp>
Deleted: trunk/boost/geometry/extensions/algorithms/remove_spikes.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/remove_spikes.hpp 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013) (r86449)
+++ /dev/null 00:00:00 1970 (deleted)
@@ -1,378 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-
-// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
-
-// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
-// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
-
-// 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_EXTENSIONS_ALGORITHMS_REMOVE_SPIKES_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_ALGORITHMS_REMOVE_SPIKES_HPP
-
-// NOTE: obsolete by "mark_spikes"
-
-#include <algorithm>
-#include <deque>
-
-#include <boost/range.hpp>
-#include <boost/typeof/typeof.hpp>
-
-#include <boost/geometry/multi/core/tags.hpp>
-
-
-#include <boost/geometry/core/coordinate_type.hpp>
-#include <boost/geometry/core/cs.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
-#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/strategies/side.hpp>
-#include <boost/geometry/util/math.hpp>
-
-#include <boost/geometry/algorithms/area.hpp>
-#include <boost/geometry/algorithms/distance.hpp>
-#include <boost/geometry/algorithms/perimeter.hpp>
-
-#include <boost/geometry/iterators/ever_circling_iterator.hpp>
-
-#include <boost/geometry/geometries/ring.hpp>
-
-
-/*
-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
-{
-
-
-template <typename Range, typename Policy>
-struct range_remove_spikes
-{
- typedef typename strategy::side::services::default_strategy
- <
- typename cs_tag<Range>::type
- >::type side_strategy_type;
-
- typedef typename coordinate_type<Range>::type coordinate_type;
-
-
- static inline void apply(Range& range, Policy const& policy)
- {
- std::size_t n = boost::size(range);
- if (n < 3)
- {
- return;
- }
-
- typedef typename boost::range_iterator<Range>::type iterator;
- ever_circling_iterator<iterator> it(boost::begin(range), boost::end(range), true);
- ever_circling_iterator<iterator> next(boost::begin(range), boost::end(range), true);
- ever_circling_iterator<iterator> prev(boost::begin(range), boost::end(range), true);
- // If it is "closed", skip the last (or actually the first coming after last) one.
- n--;
-
- it++;
- next++;
- next++;
-
- bool close = false;
-
- std::deque<std::size_t> vertices;
- for (std::size_t i = 0;
- i < n;
- ++i, ++it, ++next)
- {
- if (policy(*prev, *it, *next))
- {
- // It is collinear, middle point (i == 1) will be removed below
- vertices.push_back(i + 1);
- if (i == n - 1)
- {
- vertices.push_front(0);
- close = true;
- }
- }
- else
- {
- prev = it;
- }
- }
- for (std::deque<std::size_t>::reverse_iterator rit = vertices.rbegin();
- rit != vertices.rend(); ++rit)
- {
- range.erase(range.begin() + *rit);
- }
- if (close)
- {
- typename point_type<Range>::type p = range.front();
- range.push_back(p);
- }
- }
-};
-
-
-template <typename Polygon, typename Policy>
-struct polygon_remove_spikes
-{
- static inline void apply(Polygon& polygon, Policy const& policy)
- {
- typedef typename geometry::ring_type<Polygon>::type ring_type;
-
- typedef range_remove_spikes<ring_type, Policy> per_range;
- per_range::apply(exterior_ring(polygon), policy);
-
- typename interior_return_type<Polygon>::type rings
- = interior_rings(polygon);
- for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
- {
- per_range::apply(*it, policy);
- }
- }
-};
-
-
-template <typename MultiGeometry, typename Policy, typename SinglePolicy>
-struct multi_remove_spikes
-{
- static inline void apply(MultiGeometry& multi, Policy const& policy)
- {
- for (typename boost::range_iterator<MultiGeometry>::type
- it = boost::begin(multi);
- it != boost::end(multi);
- ++it)
- {
- SinglePolicy::apply(*it, policy);
- }
- }
-};
-
-
-}} // namespace detail::remove_spikes
-#endif // DOXYGEN_NO_DETAIL
-
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename Tag,
- typename Geometry,
- typename Policy
->
-struct remove_spikes
-{
- static inline void apply(Geometry&, Policy const&)
- {}
-};
-
-
-template <typename Ring, typename Policy>
-struct remove_spikes<ring_tag, Ring, Policy>
- : detail::remove_spikes::range_remove_spikes<Ring, Policy>
-{};
-
-
-
-template <typename Polygon, typename Policy>
-struct remove_spikes<polygon_tag, Polygon, Policy>
- : detail::remove_spikes::polygon_remove_spikes<Polygon, Policy>
-{};
-
-
-template <typename MultiPolygon, typename Policy>
-struct remove_spikes<multi_polygon_tag, MultiPolygon, Policy>
- : detail::remove_spikes::multi_remove_spikes
- <
- MultiPolygon,
- Policy,
- detail::remove_spikes::polygon_remove_spikes
- <
- typename boost::range_value<MultiPolygon>::type,
- Policy
- >
- >
-{};
-
-
-
-} // namespace dispatch
-#endif
-
-
-/*!
- \ingroup remove_spikes
- \tparam Geometry geometry type
- \param geometry the geometry to make remove_spikes
-*/
-template <typename Geometry, typename Policy>
-inline void remove_spikes(Geometry& geometry, Policy const& policy)
-{
- concept::check<Geometry>();
-
- dispatch::remove_spikes
- <
- typename tag<Geometry>::type,
- Geometry,
- Policy
- >::apply(geometry, policy);
-}
-
-
-
-template <typename Point>
-struct remove_elongated_spikes
-{
- typedef typename coordinate_type<Point>::type coordinate_type;
- coordinate_type m_area_div_peri;
- coordinate_type m_dist_div_peri;
- coordinate_type m_area_limit;
- coordinate_type m_distance_limit;
- coordinate_type m_zero;
-
-
- inline remove_elongated_spikes(coordinate_type const& area_div_peri = 0.001
- , coordinate_type const& dist_div_peri = 0.001
- , coordinate_type const& area_limit = 0.01
- , coordinate_type const& distance_limit = 1
- )
- : m_area_div_peri(area_div_peri)
- , m_dist_div_peri(dist_div_peri)
- , m_area_limit(area_limit)
- , m_distance_limit(distance_limit)
- , m_zero(coordinate_type())
- {}
-
-
- inline bool operator()(Point const& prev,
- Point const& current, Point const& next) const
- {
- coordinate_type d1 = geometry::distance(prev, current);
- if (d1 < m_distance_limit)
- {
- geometry::model::ring<Point> triangle;
- triangle.push_back(prev);
- triangle.push_back(current);
- triangle.push_back(next);
- triangle.push_back(prev);
-
- coordinate_type p = geometry::perimeter(triangle);
- if (p > m_zero)
- {
- coordinate_type a = geometry::math::abs(geometry::area(triangle));
- coordinate_type prop1 = a / p;
- coordinate_type prop2 = d1 / p;
-
- bool remove = prop1 < m_area_div_peri
- && prop2 < m_dist_div_peri
- && a < m_area_limit;
-
- /*
- {
- coordinate_type d2 = geometry::distance(prev, next);
- std::cout << std::endl;
- std::cout << "Distance1: " << d1 << std::endl;
- std::cout << "Distance2: " << d2 << std::endl;
- std::cout << "Area: " << a << std::endl;
- std::cout << "Perimeter: " << p << std::endl;
- std::cout << "Prop1: " << prop1 << std::endl;
- std::cout << "Prop2: " << prop2 << std::endl;
- std::cout << "Remove: " << (remove ? "true" : "false") << std::endl;
- }
- */
-
- return remove;
- }
- }
- return false;
- }
-};
-
-
-template <typename Point>
-class remove_by_normalized
-{
- typedef typename coordinate_type<Point>::type coordinate_type;
- coordinate_type m_zero;
- coordinate_type m_limit;
-
-public :
- inline remove_by_normalized(coordinate_type const& lm = 1.0e-7)
- : m_zero(coordinate_type())
- , m_limit(lm)
- {}
-
- inline bool operator()(Point const& prev,
- Point const& current, Point const& next) const
- {
- coordinate_type const x1 = get<0>(prev);
- coordinate_type const y1 = get<1>(prev);
- coordinate_type const x2 = get<0>(current);
- coordinate_type const y2 = get<1>(current);
-
- coordinate_type dx1 = x2 - x1;
- coordinate_type dy1 = y2 - y1;
-
- // Duplicate points (can be created by removing spikes)
- // can be removed as well. (Can be seen as a spike without length)
- if (geometry::math::equals(dx1, 0) && geometry::math::equals(dy1, 0))
- {
- return true;
- }
-
- coordinate_type dx2 = get<0>(next) - x2;
- coordinate_type dy2 = get<1>(next) - y2;
-
- // If middle point is duplicate with next, also.
- if (geometry::math::equals(dx2, 0) && geometry::math::equals(dy2, 0))
- {
- return true;
- }
-
- // Normalize the vectors -> this results in points+direction
- // and is comparible between geometries
- coordinate_type const magnitude1 = sqrt(dx1 * dx1 + dy1 * dy1);
- coordinate_type const magnitude2 = sqrt(dx2 * dx2 + dy2 * dy2);
-
- if (magnitude1 > m_zero && magnitude2 > m_zero)
- {
- dx1 /= magnitude1;
- dy1 /= magnitude1;
- dx2 /= magnitude2;
- dy2 /= magnitude2;
-
- // If the directions are opposite, it can be removed
- if (geometry::math::abs(dx1 + dx2) < m_limit
- && geometry::math::abs(dy1 + dy2) < m_limit)
- {
- return true;
- }
- }
- return false;
- }
-};
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_EXTENSIONS_ALGORITHMS_REMOVE_SPIKES_HPP
Added: trunk/boost/geometry/multi/algorithms/remove_spikes.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/multi/algorithms/remove_spikes.hpp 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013) (r86450)
@@ -0,0 +1,79 @@
+// 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 Adam Wulkiewicz, Lodz, Poland.
+
+// 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_MULTI_ALGORITHMS_REMOVE_SPIKES_HPP
+#define BOOST_GEOMETRY_MULTI_ALGORITHMS_REMOVE_SPIKES_HPP
+
+
+#include <boost/geometry/multi/core/closure.hpp>
+#include <boost/geometry/multi/core/point_order.hpp>
+#include <boost/geometry/multi/core/tags.hpp>
+#include <boost/geometry/multi/geometries/concepts/check.hpp>
+
+#include <boost/geometry/algorithms/remove_spikes.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace remove_spikes
+{
+
+template <typename MultiGeometry, typename SingleVersion>
+struct multi_remove_spikes
+{
+ static inline void apply(MultiGeometry& multi)
+ {
+ for (typename boost::range_iterator<MultiGeometry>::type
+ it = boost::begin(multi);
+ it != boost::end(multi);
+ ++it)
+ {
+ SingleVersion::apply(*it);
+ }
+ }
+};
+
+
+
+}} // namespace detail::remove_spikes
+#endif // DOXYGEN_NO_DETAIL
+
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+
+template <typename MultiPolygon>
+struct remove_spikes<MultiPolygon, multi_polygon_tag>
+ : detail::remove_spikes::multi_remove_spikes
+ <
+ MultiPolygon,
+ detail::remove_spikes::polygon_remove_spikes
+ <
+ typename boost::range_value<MultiPolygon>::type
+ >
+ >
+{};
+
+
+} // namespace dispatch
+#endif
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_REMOVE_SPIKES_HPP
Modified: trunk/libs/geometry/doc/release_notes.qbk
==============================================================================
--- trunk/libs/geometry/doc/release_notes.qbk Sat Oct 26 08:39:50 2013 (r86449)
+++ trunk/libs/geometry/doc/release_notes.qbk 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013) (r86450)
@@ -17,6 +17,10 @@
[heading Boost 1.56]
[/=================]
+[*Additional functionality]
+
+* added remove_spikes, algorithm to remove spikes from a ring, polygon or multi_polygon.
+
[*Solved tickets]
* [@https://svn.boost.org/trac/boost/ticket/9245 9245] Check for process errors in make_qbk.py
Modified: trunk/libs/geometry/test/algorithms/Jamfile.v2
==============================================================================
--- trunk/libs/geometry/test/algorithms/Jamfile.v2 Sat Oct 26 08:39:50 2013 (r86449)
+++ trunk/libs/geometry/test/algorithms/Jamfile.v2 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013) (r86450)
@@ -33,6 +33,7 @@
[ run make.cpp ]
[ run overlaps.cpp ]
[ run perimeter.cpp ]
+ [ run remove_spikes.cpp ]
[ run reverse.cpp ]
[ run simplify.cpp ]
[ run touches.cpp ]
Added: trunk/libs/geometry/test/algorithms/remove_spikes.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/geometry/test/algorithms/remove_spikes.cpp 2013-10-26 09:18:11 EDT (Sat, 26 Oct 2013) (r86450)
@@ -0,0 +1,165 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+// Unit Test
+
+// 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 Adam Wulkiewicz, Lodz, Poland.
+
+// 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)
+
+#include <iostream>
+#include <iomanip>
+#include <string>
+
+// Instead of having a separate (and nearly similar) unit test to test multipolygons,
+// we now include them here and compile them by default. Only undefining the next line
+// will avoid testing multi-geometries
+#define BOOST_GEOMETRY_UNIT_TEST_MULTI
+
+#include <geometry_test_common.hpp>
+
+// The include to test
+#include <boost/geometry/algorithms/remove_spikes.hpp>
+
+// Helper includes
+#include <boost/geometry/algorithms/area.hpp>
+#include <boost/geometry/algorithms/correct.hpp>
+#include <boost/geometry/algorithms/perimeter.hpp>
+#include <boost/geometry/geometries/geometries.hpp>
+#include <boost/geometry/geometries/point_xy.hpp>
+#include <boost/geometry/io/wkt/wkt.hpp>
+#include <boost/geometry/strategies/strategies.hpp>
+
+#if defined(BOOST_GEOMETRY_UNIT_TEST_MULTI)
+
+# include <boost/geometry/multi/algorithms/remove_spikes.hpp>
+
+# include <boost/geometry/multi/algorithms/area.hpp>
+# include <boost/geometry/multi/algorithms/correct.hpp>
+# include <boost/geometry/multi/algorithms/perimeter.hpp>
+# include <boost/geometry/multi/geometries/multi_polygon.hpp>
+# include <boost/geometry/multi/io/wkt/wkt.hpp>
+#endif
+
+
+#if defined(TEST_WITH_SVG)
+# include <boost/geometry/io/svg/svg_mapper.hpp>
+#endif
+
+
+template <typename Geometry>
+inline void test_remove_spikes(std::string const& id,
+ Geometry const& geometry,
+ double expected_area, double expected_perimeter)
+{
+ typedef typename bg::point_type<Geometry>::type point_type;
+
+ double a = bg::area(geometry);
+ double p = bg::perimeter(geometry);
+
+ Geometry processed = geometry;
+ bg::remove_spikes(processed);
+
+ double detected_area = bg::area(processed);
+ double detected_perimeter = bg::perimeter(processed);
+
+ BOOST_CHECK_CLOSE(detected_area, expected_area, 0.01);
+ BOOST_CHECK_CLOSE(detected_perimeter, expected_perimeter, 0.01);
+
+#if defined(TEST_WITH_SVG)
+ {
+ std::ostringstream filename;
+ filename << "remove_spikes_" << id;
+ if (! bg::closure<Geometry>::value)
+ {
+ filename << "_open";
+ }
+ filename << ".svg";
+ std::ofstream svg(filename.str().c_str());
+
+ bg::svg_mapper<typename bg::point_type<Geometry>::type> mapper(svg, 500, 500);
+ mapper.add(geometry);
+ mapper.map(geometry, "fill-opacity:0.3;opacity:0.6;fill:rgb(51,51,153);stroke:rgb(0,0,255);stroke-width:2");
+ mapper.map(processed, "opacity:0.6;fill:none;stroke:rgb(255,0,0);stroke-width:3");
+ }
+#endif
+}
+
+template <typename Geometry>
+void test_geometry(std::string const& id, std::string const& wkt,
+ double expected_area, double expected_perimeter)
+{
+ Geometry geometry;
+ bg::read_wkt(wkt, geometry);
+ bg::correct(geometry);
+ test_remove_spikes(id, geometry, expected_area, expected_perimeter);
+}
+
+template <typename P, bool Clockwise, bool Closed>
+void test_polygons()
+{
+ typedef bg::model::ring<P> ring;
+ typedef bg::model::polygon<P, Clockwise, Closed> polygon;
+
+ test_geometry<polygon>("box",
+ "POLYGON((0 0,0 4,4 4,4 0,0 0))",
+ 16, 16);
+ test_geometry<polygon>("box2",
+ "POLYGON((0 0,0 2,0 4,2 4,4 4,4 2,4 0,2 0,0 0))",
+ 16, 16);
+ test_geometry<polygon>("spike_right",
+ "POLYGON((0 0,0 4,4 4,4 2,6 2,4 2,4 0,0 0))",
+ 16, 16);
+ test_geometry<polygon>("spike_at_corner",
+ "POLYGON((0 0,0 4,6 4,4 4,4 0,0 0))",
+ 16, 16);
+ test_geometry<polygon>("spike_at_first",
+ "POLYGON((0 0,-1 3,0 0,0 4,4 4,4 0,0 0))",
+ 16, 16);
+ test_geometry<polygon>("spike_at_last",
+ "POLYGON((0 0,0 4,4 4,4 0,6 0,0 0))",
+ 16, 16);
+ test_geometry<polygon>("spike_at_closing",
+ "POLYGON((-1 0,0 0,0 4,4 4,4 0,0 0,-1 0))",
+ 16, 16);
+ test_geometry<polygon>("double_spike",
+ "POLYGON((0 0,0 4,4 4,4 2,6 2,5 2,4 2,4 0,0 0))",
+ 16, 16);
+ test_geometry<polygon>("three_double_spike",
+ "POLYGON((0 0,0 4,4 4,4 2,6 2,5 2,4.5 2,4 2,4 0,0 0))",
+ 16, 16);
+ test_geometry<polygon>("spike_with_corner",
+ "POLYGON((0 0,0 4,4 4,4 2,6 2,6 4,6 2,4 2,4 0,0 0))",
+ 16, 16);
+}
+
+
+template <typename P, bool Clockwise, bool Closed>
+void test_multi_polygons()
+{
+ typedef bg::model::ring<P> ring;
+ typedef bg::model::polygon<P, Clockwise, Closed> polygon;
+ typedef bg::model::multi_polygon<polygon> multi_polygon;
+
+ test_geometry<multi_polygon>("multi_spike_with_corner",
+ "MULTIPOLYGON(((0 0,0 4,4 4,4 2,6 2,6 4,6 2,4 2,4 0,0 0)))",
+ 16, 16);
+}
+
+template <typename P, bool Clockwise, bool Closed>
+void test_all()
+{
+ test_polygons<P, Clockwise, Closed>();
+ test_multi_polygons<P, Clockwise, Closed>();
+}
+
+int test_main(int, char* [])
+{
+ test_all<bg::model::d2::point_xy<double>, true, true>();
+ test_all<bg::model::d2::point_xy<double>, true, false>();
+ return 0;
+}
+
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk