]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. | |
6 | ||
1e59de90 TL |
7 | // This file was modified by Oracle on 2018-2022. |
8 | // Modifications copyright (c) 2018-2022 Oracle and/or its affiliates. | |
92f5a8d4 TL |
9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
10 | ||
7c673cae FG |
11 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library |
12 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
13 | ||
14 | // Use, modification and distribution is subject to the Boost Software License, | |
15 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
16 | // http://www.boost.org/LICENSE_1_0.txt) | |
17 | ||
18 | #ifndef BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP | |
19 | #define BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP | |
20 | ||
21 | #include <cstddef> | |
1e59de90 TL |
22 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER |
23 | #include <iostream> | |
24 | #endif | |
92f5a8d4 | 25 | #include <set> |
1e59de90 | 26 | #include <vector> |
7c673cae | 27 | |
1e59de90 | 28 | #include <boost/core/addressof.hpp> |
7c673cae | 29 | #include <boost/core/ignore_unused.hpp> |
20effc67 TL |
30 | #include <boost/range/begin.hpp> |
31 | #include <boost/range/end.hpp> | |
32 | #include <boost/range/size.hpp> | |
33 | #include <boost/range/value_type.hpp> | |
1e59de90 TL |
34 | |
35 | #include <boost/geometry/algorithms/area.hpp> | |
36 | #include <boost/geometry/algorithms/clear.hpp> | |
37 | #include <boost/geometry/algorithms/convert.hpp> | |
38 | #include <boost/geometry/algorithms/detail/dummy_geometries.hpp> | |
39 | #include <boost/geometry/algorithms/detail/equals/point_point.hpp> | |
40 | #include <boost/geometry/algorithms/detail/visit.hpp> | |
41 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
42 | #include <boost/geometry/algorithms/is_empty.hpp> | |
43 | #include <boost/geometry/algorithms/perimeter.hpp> | |
7c673cae FG |
44 | |
45 | #include <boost/geometry/core/cs.hpp> | |
46 | #include <boost/geometry/core/closure.hpp> | |
47 | #include <boost/geometry/core/exterior_ring.hpp> | |
48 | #include <boost/geometry/core/interior_rings.hpp> | |
49 | #include <boost/geometry/core/mutable_range.hpp> | |
50 | #include <boost/geometry/core/tags.hpp> | |
1e59de90 | 51 | #include <boost/geometry/core/visit.hpp> |
7c673cae | 52 | |
1e59de90 | 53 | #include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility |
7c673cae | 54 | #include <boost/geometry/geometries/concepts/check.hpp> |
1e59de90 | 55 | |
7c673cae FG |
56 | #include <boost/geometry/strategies/concepts/simplify_concept.hpp> |
57 | #include <boost/geometry/strategies/default_strategy.hpp> | |
1e59de90 TL |
58 | #include <boost/geometry/strategies/detail.hpp> |
59 | #include <boost/geometry/strategies/distance/comparable.hpp> | |
60 | #include <boost/geometry/strategies/simplify/cartesian.hpp> | |
61 | #include <boost/geometry/strategies/simplify/geographic.hpp> | |
62 | #include <boost/geometry/strategies/simplify/spherical.hpp> | |
7c673cae | 63 | |
1e59de90 | 64 | #include <boost/geometry/util/type_traits_std.hpp> |
7c673cae | 65 | |
1e59de90 TL |
66 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER |
67 | #include <boost/geometry/io/dsv/write.hpp> | |
68 | #endif | |
7c673cae FG |
69 | |
70 | namespace boost { namespace geometry | |
71 | { | |
72 | ||
73 | #ifndef DOXYGEN_NO_DETAIL | |
74 | namespace detail { namespace simplify | |
75 | { | |
76 | ||
1e59de90 TL |
77 | /*! |
78 | \brief Small wrapper around a point, with an extra member "included" | |
79 | \details | |
80 | It has a const-reference to the original point (so no copy here) | |
81 | \tparam the enclosed point type | |
82 | */ | |
83 | template <typename Point> | |
84 | struct douglas_peucker_point | |
85 | { | |
86 | typedef Point point_type; | |
87 | ||
88 | Point const* p; | |
89 | bool included; | |
90 | ||
91 | inline douglas_peucker_point(Point const& ap) | |
92 | : p(boost::addressof(ap)) | |
93 | , included(false) | |
94 | {} | |
95 | }; | |
96 | ||
97 | /*! | |
98 | \brief Implements the simplify algorithm. | |
99 | \details The douglas_peucker policy simplifies a linestring, ring or | |
100 | vector of points using the well-known Douglas-Peucker algorithm. | |
101 | \tparam Point the point type | |
102 | \tparam PointDistanceStrategy point-segment distance strategy to be used | |
103 | \note This strategy uses itself a point-segment-distance strategy which | |
104 | can be specified | |
105 | \author Barend and Maarten, 1995/1996 | |
106 | \author Barend, revised for Generic Geometry Library, 2008 | |
107 | */ | |
108 | ||
109 | /* | |
110 | For the algorithm, see for example: | |
111 | - http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm | |
112 | - http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html | |
113 | */ | |
114 | class douglas_peucker | |
115 | { | |
116 | template <typename Iterator, typename Distance, typename PSDistanceStrategy> | |
117 | static inline void consider(Iterator begin, | |
118 | Iterator end, | |
119 | Distance const& max_dist, | |
120 | int& n, | |
121 | PSDistanceStrategy const& ps_distance_strategy) | |
122 | { | |
123 | typedef typename std::iterator_traits<Iterator>::value_type::point_type point_type; | |
124 | typedef decltype(ps_distance_strategy.apply(std::declval<point_type>(), | |
125 | std::declval<point_type>(), std::declval<point_type>())) distance_type; | |
126 | ||
127 | std::size_t size = end - begin; | |
128 | ||
129 | // size must be at least 3 | |
130 | // because we want to consider a candidate point in between | |
131 | if (size <= 2) | |
132 | { | |
133 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
134 | if (begin != end) | |
135 | { | |
136 | std::cout << "ignore between " << dsv(*(begin->p)) | |
137 | << " and " << dsv(*((end - 1)->p)) | |
138 | << " size=" << size << std::endl; | |
139 | } | |
140 | std::cout << "return because size=" << size << std::endl; | |
141 | #endif | |
142 | return; | |
143 | } | |
144 | ||
145 | Iterator last = end - 1; | |
146 | ||
147 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
148 | std::cout << "find between " << dsv(*(begin->p)) | |
149 | << " and " << dsv(*(last->p)) | |
150 | << " size=" << size << std::endl; | |
151 | #endif | |
152 | ||
153 | ||
154 | // Find most far point, compare to the current segment | |
155 | //geometry::segment<Point const> s(begin->p, last->p); | |
156 | distance_type md(-1.0); // any value < 0 | |
157 | Iterator candidate = end; | |
158 | for (Iterator it = begin + 1; it != last; ++it) | |
159 | { | |
160 | distance_type dist = ps_distance_strategy.apply(*(it->p), *(begin->p), *(last->p)); | |
161 | ||
162 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
163 | std::cout << "consider " << dsv(*(it->p)) | |
164 | << " at " << double(dist) | |
165 | << ((dist > max_dist) ? " maybe" : " no") | |
166 | << std::endl; | |
167 | ||
168 | #endif | |
169 | if (md < dist) | |
170 | { | |
171 | md = dist; | |
172 | candidate = it; | |
173 | } | |
174 | } | |
175 | ||
176 | // If a point is found, set the include flag | |
177 | // and handle segments in between recursively | |
178 | if (max_dist < md && candidate != end) | |
179 | { | |
180 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
181 | std::cout << "use " << dsv(candidate->p) << std::endl; | |
182 | #endif | |
183 | ||
184 | candidate->included = true; | |
185 | n++; | |
186 | ||
187 | consider(begin, candidate + 1, max_dist, n, ps_distance_strategy); | |
188 | consider(candidate, end, max_dist, n, ps_distance_strategy); | |
189 | } | |
190 | } | |
191 | ||
192 | template | |
193 | < | |
194 | typename Range, typename OutputIterator, typename Distance, | |
195 | typename PSDistanceStrategy | |
196 | > | |
197 | static inline OutputIterator apply_(Range const& range, | |
198 | OutputIterator out, | |
199 | Distance const& max_distance, | |
200 | PSDistanceStrategy const& ps_distance_strategy) | |
201 | { | |
202 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
203 | std::cout << "max distance: " << max_distance | |
204 | << std::endl << std::endl; | |
205 | #endif | |
206 | ||
207 | typedef typename boost::range_value<Range>::type point_type; | |
208 | typedef douglas_peucker_point<point_type> dp_point_type; | |
209 | ||
210 | // Copy coordinates, a vector of references to all points | |
211 | std::vector<dp_point_type> ref_candidates(boost::begin(range), | |
212 | boost::end(range)); | |
213 | ||
214 | // Include first and last point of line, | |
215 | // they are always part of the line | |
216 | int n = 2; | |
217 | ref_candidates.front().included = true; | |
218 | ref_candidates.back().included = true; | |
219 | ||
220 | // Get points, recursively, including them if they are further away | |
221 | // than the specified distance | |
222 | consider(boost::begin(ref_candidates), boost::end(ref_candidates), max_distance, n, | |
223 | ps_distance_strategy); | |
224 | ||
225 | // Copy included elements to the output | |
226 | for (auto it = boost::begin(ref_candidates); it != boost::end(ref_candidates); ++it) | |
227 | { | |
228 | if (it->included) | |
229 | { | |
230 | // copy-coordinates does not work because OutputIterator | |
231 | // does not model Point (??) | |
232 | //geometry::convert(*(it->p), *out); | |
233 | *out = *(it->p); | |
234 | ++out; | |
235 | } | |
236 | } | |
237 | return out; | |
238 | } | |
239 | ||
240 | public: | |
241 | template <typename Range, typename OutputIterator, typename Distance, typename Strategies> | |
242 | static inline OutputIterator apply(Range const& range, | |
243 | OutputIterator out, | |
244 | Distance const& max_distance, | |
245 | Strategies const& strategies) | |
246 | { | |
247 | typedef typename boost::range_value<Range>::type point_type; | |
248 | typedef decltype(strategies.distance(detail::dummy_point(), detail::dummy_segment())) distance_strategy_type; | |
249 | ||
250 | typedef typename strategy::distance::services::comparable_type | |
251 | < | |
252 | distance_strategy_type | |
253 | >::type comparable_distance_strategy_type; | |
254 | ||
255 | comparable_distance_strategy_type cstrategy = strategy::distance::services::get_comparable | |
256 | < | |
257 | distance_strategy_type | |
258 | >::apply(strategies.distance(detail::dummy_point(), detail::dummy_segment())); | |
259 | ||
260 | return apply_(range, out, | |
261 | strategy::distance::services::result_from_distance | |
262 | < | |
263 | comparable_distance_strategy_type, point_type, point_type | |
264 | >::apply(cstrategy, max_distance), | |
265 | cstrategy); | |
266 | } | |
267 | }; | |
268 | ||
269 | ||
270 | template <typename Range, typename Strategies> | |
271 | inline bool is_degenerate(Range const& range, Strategies const& strategies) | |
11fdf7f2 TL |
272 | { |
273 | return boost::size(range) == 2 | |
274 | && detail::equals::equals_point_point(geometry::range::front(range), | |
92f5a8d4 | 275 | geometry::range::back(range), |
1e59de90 | 276 | strategies); |
11fdf7f2 TL |
277 | } |
278 | ||
7c673cae FG |
279 | struct simplify_range_insert |
280 | { | |
1e59de90 TL |
281 | template |
282 | < | |
283 | typename Range, typename OutputIterator, typename Distance, | |
284 | typename Impl, typename Strategies | |
285 | > | |
7c673cae | 286 | static inline void apply(Range const& range, OutputIterator out, |
1e59de90 TL |
287 | Distance const& max_distance, |
288 | Impl const& impl, | |
289 | Strategies const& strategies) | |
7c673cae | 290 | { |
1e59de90 | 291 | if (is_degenerate(range, strategies)) |
11fdf7f2 TL |
292 | { |
293 | std::copy(boost::begin(range), boost::begin(range) + 1, out); | |
294 | } | |
295 | else if (boost::size(range) <= 2 || max_distance < 0) | |
7c673cae FG |
296 | { |
297 | std::copy(boost::begin(range), boost::end(range), out); | |
298 | } | |
299 | else | |
300 | { | |
1e59de90 | 301 | impl.apply(range, out, max_distance, strategies); |
7c673cae FG |
302 | } |
303 | } | |
304 | }; | |
305 | ||
306 | ||
1e59de90 TL |
307 | struct simplify_copy_assign |
308 | { | |
309 | template | |
310 | < | |
311 | typename In, typename Out, typename Distance, | |
312 | typename Impl, typename Strategies | |
313 | > | |
314 | static inline void apply(In const& in, Out& out, | |
315 | Distance const& , | |
316 | Impl const& , | |
317 | Strategies const& ) | |
318 | { | |
319 | out = in; | |
320 | } | |
321 | }; | |
322 | ||
323 | ||
7c673cae FG |
324 | struct simplify_copy |
325 | { | |
1e59de90 TL |
326 | template |
327 | < | |
328 | typename RangeIn, typename RangeOut, typename Distance, | |
329 | typename Impl, typename Strategies | |
330 | > | |
11fdf7f2 | 331 | static inline void apply(RangeIn const& range, RangeOut& out, |
1e59de90 TL |
332 | Distance const& , |
333 | Impl const& , | |
334 | Strategies const& ) | |
7c673cae | 335 | { |
1e59de90 TL |
336 | std::copy(boost::begin(range), boost::end(range), |
337 | geometry::range::back_inserter(out)); | |
7c673cae FG |
338 | } |
339 | }; | |
340 | ||
341 | ||
11fdf7f2 | 342 | template <std::size_t MinimumToUseStrategy> |
7c673cae FG |
343 | struct simplify_range |
344 | { | |
1e59de90 TL |
345 | template |
346 | < | |
347 | typename RangeIn, typename RangeOut, typename Distance, | |
348 | typename Impl, typename Strategies | |
349 | > | |
11fdf7f2 | 350 | static inline void apply(RangeIn const& range, RangeOut& out, |
1e59de90 TL |
351 | Distance const& max_distance, |
352 | Impl const& impl, | |
353 | Strategies const& strategies) | |
7c673cae | 354 | { |
11fdf7f2 TL |
355 | // For a RING: |
356 | // Note that, especially if max_distance is too large, | |
357 | // the output ring might be self intersecting while the input ring is | |
358 | // not, although chances are low in normal polygons | |
7c673cae | 359 | |
11fdf7f2 | 360 | if (boost::size(range) <= MinimumToUseStrategy || max_distance < 0) |
7c673cae | 361 | { |
1e59de90 | 362 | simplify_copy::apply(range, out, max_distance, impl, strategies); |
7c673cae FG |
363 | } |
364 | else | |
365 | { | |
1e59de90 TL |
366 | simplify_range_insert::apply(range, geometry::range::back_inserter(out), |
367 | max_distance, impl, strategies); | |
7c673cae | 368 | } |
11fdf7f2 TL |
369 | |
370 | // Verify the two remaining points are equal. If so, remove one of them. | |
371 | // This can cause the output being under the minimum size | |
1e59de90 | 372 | if (is_degenerate(out, strategies)) |
11fdf7f2 TL |
373 | { |
374 | range::resize(out, 1); | |
375 | } | |
7c673cae FG |
376 | } |
377 | }; | |
378 | ||
11fdf7f2 TL |
379 | struct simplify_ring |
380 | { | |
381 | private : | |
382 | template <typename Area> | |
383 | static inline int area_sign(Area const& area) | |
384 | { | |
385 | return area > 0 ? 1 : area < 0 ? -1 : 0; | |
386 | } | |
387 | ||
1e59de90 TL |
388 | template <typename Ring, typename Strategies> |
389 | static std::size_t get_opposite(std::size_t index, Ring const& ring, | |
390 | Strategies const& strategies) | |
11fdf7f2 | 391 | { |
1e59de90 TL |
392 | // TODO: Instead of calling the strategy call geometry::comparable_distance() ? |
393 | ||
394 | auto const cdistance_strategy = strategies::distance::detail::make_comparable(strategies) | |
395 | .distance(detail::dummy_point(), detail::dummy_point()); | |
396 | ||
397 | using point_type = typename geometry::point_type<Ring>::type; | |
398 | using cdistance_type = decltype(cdistance_strategy.apply( | |
399 | std::declval<point_type>(), std::declval<point_type>())); | |
11fdf7f2 TL |
400 | |
401 | // Verify if it is NOT the case that all points are less than the | |
402 | // simplifying distance. If so, output is empty. | |
1e59de90 | 403 | cdistance_type max_cdistance(-1); |
11fdf7f2 | 404 | |
1e59de90 | 405 | point_type const& point = range::at(ring, index); |
11fdf7f2 | 406 | std::size_t i = 0; |
1e59de90 | 407 | for (auto it = boost::begin(ring); it != boost::end(ring); ++it, ++i) |
11fdf7f2 | 408 | { |
1e59de90 TL |
409 | cdistance_type const cdistance = cdistance_strategy.apply(*it, point); |
410 | if (cdistance > max_cdistance) | |
11fdf7f2 | 411 | { |
1e59de90 | 412 | max_cdistance = cdistance; |
11fdf7f2 TL |
413 | index = i; |
414 | } | |
415 | } | |
416 | return index; | |
417 | } | |
418 | ||
419 | public : | |
1e59de90 TL |
420 | template <typename Ring, typename Distance, typename Impl, typename Strategies> |
421 | static inline void apply(Ring const& ring, Ring& out, Distance const& max_distance, | |
422 | Impl const& impl, Strategies const& strategies) | |
11fdf7f2 TL |
423 | { |
424 | std::size_t const size = boost::size(ring); | |
425 | if (size == 0) | |
426 | { | |
427 | return; | |
428 | } | |
429 | ||
1e59de90 TL |
430 | bool const is_closed = closure<Ring>::value == closed; |
431 | ||
432 | // TODO: instead of area() use calculate_point_order() ? | |
433 | ||
434 | int const input_sign = area_sign(geometry::area(ring, strategies)); | |
11fdf7f2 TL |
435 | |
436 | std::set<std::size_t> visited_indexes; | |
437 | ||
438 | // Rotate it into a copied vector | |
439 | // (vector, because source type might not support rotation) | |
440 | // (duplicate end point will be simplified away) | |
441 | typedef typename geometry::point_type<Ring>::type point_type; | |
442 | ||
1e59de90 TL |
443 | std::vector<point_type> rotated; |
444 | rotated.reserve(size + 1); // 1 because open rings are closed | |
11fdf7f2 TL |
445 | |
446 | // Closing point (but it will not start here) | |
447 | std::size_t index = 0; | |
448 | ||
449 | // Iterate (usually one iteration is enough) | |
450 | for (std::size_t iteration = 0; iteration < 4u; iteration++) | |
451 | { | |
452 | // Always take the opposite. Opposite guarantees that no point | |
453 | // "halfway" is chosen, creating an artefact (very narrow triangle) | |
454 | // Iteration 0: opposite to closing point (1/2, = on convex hull) | |
455 | // (this will start simplification with that point | |
456 | // and its opposite ~0) | |
457 | // Iteration 1: move a quarter on that ring, then opposite to 1/4 | |
458 | // (with its opposite 3/4) | |
459 | // Iteration 2: move an eight on that ring, then opposite (1/8) | |
460 | // Iteration 3: again move a quarter, then opposite (7/8) | |
461 | // So finally 8 "sides" of the ring have been examined (if it were | |
462 | // a semi-circle). Most probably, there are only 0 or 1 iterations. | |
463 | switch (iteration) | |
464 | { | |
465 | case 1 : index = (index + size / 4) % size; break; | |
466 | case 2 : index = (index + size / 8) % size; break; | |
467 | case 3 : index = (index + size / 4) % size; break; | |
468 | } | |
1e59de90 | 469 | index = get_opposite(index, ring, strategies); |
11fdf7f2 TL |
470 | |
471 | if (visited_indexes.count(index) > 0) | |
472 | { | |
473 | // Avoid trying the same starting point more than once | |
474 | continue; | |
475 | } | |
476 | ||
1e59de90 TL |
477 | // Do not duplicate the closing point |
478 | auto rot_end = boost::end(ring); | |
479 | std::size_t rot_index = index; | |
480 | if (is_closed && size > 1) | |
481 | { | |
482 | --rot_end; | |
483 | if (rot_index == size - 1) { rot_index = 0; } | |
484 | } | |
485 | ||
486 | std::rotate_copy(boost::begin(ring), range::pos(ring, rot_index), | |
487 | rot_end, std::back_inserter(rotated)); | |
11fdf7f2 TL |
488 | |
489 | // Close the rotated copy | |
1e59de90 | 490 | rotated.push_back(range::at(ring, rot_index)); |
11fdf7f2 | 491 | |
1e59de90 TL |
492 | simplify_range<0>::apply(rotated, out, max_distance, impl, strategies); |
493 | ||
494 | // Open output if needed | |
495 | if (! is_closed && boost::size(out) > 1) | |
496 | { | |
497 | range::pop_back(out); | |
498 | } | |
499 | ||
500 | // TODO: instead of area() use calculate_point_order() ? | |
11fdf7f2 TL |
501 | |
502 | // Verify that what was positive, stays positive (or goes to 0) | |
503 | // and what was negative stays negative (or goes to 0) | |
1e59de90 | 504 | int const output_sign = area_sign(geometry::area(out, strategies)); |
11fdf7f2 TL |
505 | if (output_sign == input_sign) |
506 | { | |
507 | // Result is considered as satisfactory (usually this is the | |
508 | // first iteration - only for small rings, having a scale | |
509 | // similar to simplify_distance, next iterations are tried | |
510 | return; | |
511 | } | |
512 | ||
513 | // Original is simplified away. Possibly there is a solution | |
514 | // when another starting point is used | |
515 | geometry::clear(out); | |
516 | ||
517 | if (iteration == 0 | |
1e59de90 | 518 | && geometry::perimeter(ring, strategies) < 3 * max_distance) |
11fdf7f2 TL |
519 | { |
520 | // Check if it is useful to iterate. A minimal triangle has a | |
521 | // perimeter of a bit more than 3 times the simplify distance | |
522 | return; | |
523 | } | |
524 | ||
525 | // Prepare next try | |
526 | visited_indexes.insert(index); | |
1e59de90 | 527 | rotated.clear(); |
11fdf7f2 TL |
528 | } |
529 | } | |
530 | }; | |
531 | ||
532 | ||
7c673cae FG |
533 | struct simplify_polygon |
534 | { | |
535 | private: | |
536 | ||
537 | template | |
538 | < | |
7c673cae | 539 | typename IteratorIn, |
11fdf7f2 | 540 | typename InteriorRingsOut, |
7c673cae | 541 | typename Distance, |
1e59de90 TL |
542 | typename Impl, |
543 | typename Strategies | |
7c673cae FG |
544 | > |
545 | static inline void iterate(IteratorIn begin, IteratorIn end, | |
1e59de90 TL |
546 | InteriorRingsOut& interior_rings_out, |
547 | Distance const& max_distance, | |
548 | Impl const& impl, Strategies const& strategies) | |
7c673cae | 549 | { |
11fdf7f2 TL |
550 | typedef typename boost::range_value<InteriorRingsOut>::type single_type; |
551 | for (IteratorIn it = begin; it != end; ++it) | |
7c673cae | 552 | { |
11fdf7f2 | 553 | single_type out; |
1e59de90 | 554 | simplify_ring::apply(*it, out, max_distance, impl, strategies); |
11fdf7f2 TL |
555 | if (! geometry::is_empty(out)) |
556 | { | |
1e59de90 | 557 | range::push_back(interior_rings_out, std::move(out)); |
11fdf7f2 | 558 | } |
7c673cae FG |
559 | } |
560 | } | |
561 | ||
562 | template | |
563 | < | |
7c673cae FG |
564 | typename InteriorRingsIn, |
565 | typename InteriorRingsOut, | |
566 | typename Distance, | |
1e59de90 TL |
567 | typename Impl, |
568 | typename Strategies | |
7c673cae | 569 | > |
1e59de90 TL |
570 | static inline void apply_interior_rings(InteriorRingsIn const& interior_rings_in, |
571 | InteriorRingsOut& interior_rings_out, | |
572 | Distance const& max_distance, | |
573 | Impl const& impl, Strategies const& strategies) | |
7c673cae | 574 | { |
11fdf7f2 | 575 | range::clear(interior_rings_out); |
7c673cae | 576 | |
1e59de90 TL |
577 | iterate(boost::begin(interior_rings_in), boost::end(interior_rings_in), |
578 | interior_rings_out, | |
579 | max_distance, | |
580 | impl, strategies); | |
7c673cae FG |
581 | } |
582 | ||
583 | public: | |
1e59de90 | 584 | template <typename Polygon, typename Distance, typename Impl, typename Strategies> |
7c673cae | 585 | static inline void apply(Polygon const& poly_in, Polygon& poly_out, |
1e59de90 TL |
586 | Distance const& max_distance, |
587 | Impl const& impl, Strategies const& strategies) | |
7c673cae | 588 | { |
7c673cae FG |
589 | // Note that if there are inner rings, and distance is too large, |
590 | // they might intersect with the outer ring in the output, | |
591 | // while it didn't in the input. | |
11fdf7f2 | 592 | simplify_ring::apply(exterior_ring(poly_in), exterior_ring(poly_out), |
1e59de90 | 593 | max_distance, impl, strategies); |
7c673cae | 594 | |
1e59de90 TL |
595 | apply_interior_rings(interior_rings(poly_in), interior_rings(poly_out), |
596 | max_distance, impl, strategies); | |
7c673cae FG |
597 | } |
598 | }; | |
599 | ||
600 | ||
601 | template<typename Policy> | |
602 | struct simplify_multi | |
603 | { | |
1e59de90 | 604 | template <typename MultiGeometry, typename Distance, typename Impl, typename Strategies> |
7c673cae | 605 | static inline void apply(MultiGeometry const& multi, MultiGeometry& out, |
1e59de90 TL |
606 | Distance const& max_distance, |
607 | Impl const& impl, Strategies const& strategies) | |
7c673cae | 608 | { |
11fdf7f2 TL |
609 | range::clear(out); |
610 | ||
611 | typedef typename boost::range_value<MultiGeometry>::type single_type; | |
7c673cae | 612 | |
7c673cae | 613 | for (typename boost::range_iterator<MultiGeometry const>::type |
11fdf7f2 | 614 | it = boost::begin(multi); it != boost::end(multi); ++it) |
7c673cae | 615 | { |
11fdf7f2 | 616 | single_type single_out; |
1e59de90 | 617 | Policy::apply(*it, single_out, max_distance, impl, strategies); |
11fdf7f2 TL |
618 | if (! geometry::is_empty(single_out)) |
619 | { | |
1e59de90 | 620 | range::push_back(out, std::move(single_out)); |
11fdf7f2 | 621 | } |
7c673cae FG |
622 | } |
623 | } | |
624 | }; | |
625 | ||
626 | ||
627 | }} // namespace detail::simplify | |
628 | #endif // DOXYGEN_NO_DETAIL | |
629 | ||
630 | ||
631 | #ifndef DOXYGEN_NO_DISPATCH | |
632 | namespace dispatch | |
633 | { | |
634 | ||
635 | template | |
636 | < | |
637 | typename Geometry, | |
638 | typename Tag = typename tag<Geometry>::type | |
639 | > | |
640 | struct simplify: not_implemented<Tag> | |
641 | {}; | |
642 | ||
643 | template <typename Point> | |
644 | struct simplify<Point, point_tag> | |
645 | { | |
1e59de90 TL |
646 | template <typename Distance, typename Impl, typename Strategy> |
647 | static inline void apply(Point const& point, Point& out, Distance const& , | |
648 | Impl const& , Strategy const& ) | |
7c673cae FG |
649 | { |
650 | geometry::convert(point, out); | |
651 | } | |
652 | }; | |
653 | ||
1e59de90 TL |
654 | template <typename Segment> |
655 | struct simplify<Segment, segment_tag> | |
656 | : detail::simplify::simplify_copy_assign | |
657 | {}; | |
658 | ||
659 | template <typename Box> | |
660 | struct simplify<Box, box_tag> | |
661 | : detail::simplify::simplify_copy_assign | |
662 | {}; | |
663 | ||
664 | ||
11fdf7f2 | 665 | // Linestring, keep 2 points (unless those points are the same) |
7c673cae FG |
666 | template <typename Linestring> |
667 | struct simplify<Linestring, linestring_tag> | |
668 | : detail::simplify::simplify_range<2> | |
669 | {}; | |
670 | ||
671 | template <typename Ring> | |
672 | struct simplify<Ring, ring_tag> | |
11fdf7f2 | 673 | : detail::simplify::simplify_ring |
7c673cae FG |
674 | {}; |
675 | ||
676 | template <typename Polygon> | |
677 | struct simplify<Polygon, polygon_tag> | |
678 | : detail::simplify::simplify_polygon | |
679 | {}; | |
680 | ||
681 | ||
682 | template | |
683 | < | |
684 | typename Geometry, | |
685 | typename Tag = typename tag<Geometry>::type | |
686 | > | |
687 | struct simplify_insert: not_implemented<Tag> | |
688 | {}; | |
689 | ||
690 | ||
691 | template <typename Linestring> | |
692 | struct simplify_insert<Linestring, linestring_tag> | |
693 | : detail::simplify::simplify_range_insert | |
694 | {}; | |
695 | ||
696 | template <typename Ring> | |
697 | struct simplify_insert<Ring, ring_tag> | |
698 | : detail::simplify::simplify_range_insert | |
699 | {}; | |
700 | ||
701 | template <typename MultiPoint> | |
702 | struct simplify<MultiPoint, multi_point_tag> | |
703 | : detail::simplify::simplify_copy | |
704 | {}; | |
705 | ||
706 | ||
707 | template <typename MultiLinestring> | |
708 | struct simplify<MultiLinestring, multi_linestring_tag> | |
709 | : detail::simplify::simplify_multi<detail::simplify::simplify_range<2> > | |
710 | {}; | |
711 | ||
712 | ||
713 | template <typename MultiPolygon> | |
714 | struct simplify<MultiPolygon, multi_polygon_tag> | |
715 | : detail::simplify::simplify_multi<detail::simplify::simplify_polygon> | |
716 | {}; | |
717 | ||
718 | ||
719 | } // namespace dispatch | |
720 | #endif // DOXYGEN_NO_DISPATCH | |
721 | ||
722 | ||
723 | namespace resolve_strategy | |
724 | { | |
725 | ||
1e59de90 TL |
726 | template |
727 | < | |
728 | typename Strategies, | |
729 | bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value | |
730 | > | |
7c673cae FG |
731 | struct simplify |
732 | { | |
1e59de90 | 733 | template <typename Geometry, typename Distance> |
7c673cae FG |
734 | static inline void apply(Geometry const& geometry, |
735 | Geometry& out, | |
736 | Distance const& max_distance, | |
1e59de90 | 737 | Strategies const& strategies) |
7c673cae | 738 | { |
1e59de90 TL |
739 | dispatch::simplify |
740 | < | |
741 | Geometry | |
742 | >::apply(geometry, out, max_distance, | |
743 | detail::simplify::douglas_peucker(), | |
744 | strategies); | |
7c673cae | 745 | } |
1e59de90 | 746 | }; |
7c673cae | 747 | |
1e59de90 TL |
748 | template <typename Strategy> |
749 | struct simplify<Strategy, false> | |
750 | { | |
7c673cae FG |
751 | template <typename Geometry, typename Distance> |
752 | static inline void apply(Geometry const& geometry, | |
753 | Geometry& out, | |
754 | Distance const& max_distance, | |
1e59de90 | 755 | Strategy const& strategy) |
7c673cae | 756 | { |
1e59de90 | 757 | using strategies::simplify::services::strategy_converter; |
7c673cae | 758 | |
1e59de90 TL |
759 | simplify |
760 | < | |
761 | decltype(strategy_converter<Strategy>::get(strategy)) | |
762 | >::apply(geometry, out, max_distance, | |
763 | strategy_converter<Strategy>::get(strategy)); | |
764 | } | |
765 | }; | |
7c673cae | 766 | |
1e59de90 TL |
767 | template <> |
768 | struct simplify<default_strategy, false> | |
769 | { | |
770 | template <typename Geometry, typename Distance> | |
771 | static inline void apply(Geometry const& geometry, | |
772 | Geometry& out, | |
773 | Distance const& max_distance, | |
774 | default_strategy) | |
775 | { | |
776 | typedef typename strategies::simplify::services::default_strategy | |
777 | < | |
778 | Geometry | |
779 | >::type strategy_type; | |
780 | ||
781 | simplify | |
782 | < | |
783 | strategy_type | |
784 | >::apply(geometry, out, max_distance, strategy_type()); | |
7c673cae FG |
785 | } |
786 | }; | |
787 | ||
1e59de90 TL |
788 | template |
789 | < | |
790 | typename Strategies, | |
791 | bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value | |
792 | > | |
7c673cae FG |
793 | struct simplify_insert |
794 | { | |
1e59de90 TL |
795 | template<typename Geometry, typename OutputIterator, typename Distance> |
796 | static inline void apply(Geometry const& geometry, | |
797 | OutputIterator& out, | |
798 | Distance const& max_distance, | |
799 | Strategies const& strategies) | |
800 | { | |
801 | dispatch::simplify_insert | |
802 | < | |
803 | Geometry | |
804 | >::apply(geometry, out, max_distance, | |
805 | detail::simplify::douglas_peucker(), | |
806 | strategies); | |
807 | } | |
808 | }; | |
809 | ||
810 | template <typename Strategy> | |
811 | struct simplify_insert<Strategy, false> | |
812 | { | |
813 | template<typename Geometry, typename OutputIterator, typename Distance> | |
7c673cae FG |
814 | static inline void apply(Geometry const& geometry, |
815 | OutputIterator& out, | |
816 | Distance const& max_distance, | |
817 | Strategy const& strategy) | |
818 | { | |
1e59de90 TL |
819 | using strategies::simplify::services::strategy_converter; |
820 | ||
821 | simplify_insert | |
822 | < | |
823 | decltype(strategy_converter<Strategy>::get(strategy)) | |
824 | >::apply(geometry, out, max_distance, | |
825 | strategy_converter<Strategy>::get(strategy)); | |
7c673cae | 826 | } |
1e59de90 | 827 | }; |
7c673cae | 828 | |
1e59de90 TL |
829 | template <> |
830 | struct simplify_insert<default_strategy, false> | |
831 | { | |
7c673cae FG |
832 | template <typename Geometry, typename OutputIterator, typename Distance> |
833 | static inline void apply(Geometry const& geometry, | |
834 | OutputIterator& out, | |
835 | Distance const& max_distance, | |
836 | default_strategy) | |
837 | { | |
1e59de90 TL |
838 | typedef typename strategies::simplify::services::default_strategy |
839 | < | |
840 | Geometry | |
841 | >::type strategy_type; | |
842 | ||
843 | simplify_insert | |
844 | < | |
845 | strategy_type | |
846 | >::apply(geometry, out, max_distance, strategy_type()); | |
7c673cae FG |
847 | } |
848 | }; | |
849 | ||
850 | } // namespace resolve_strategy | |
851 | ||
852 | ||
1e59de90 | 853 | namespace resolve_dynamic { |
7c673cae | 854 | |
1e59de90 | 855 | template <typename Geometry, typename Tag = typename tag<Geometry>::type> |
7c673cae FG |
856 | struct simplify |
857 | { | |
858 | template <typename Distance, typename Strategy> | |
859 | static inline void apply(Geometry const& geometry, | |
860 | Geometry& out, | |
861 | Distance const& max_distance, | |
862 | Strategy const& strategy) | |
863 | { | |
1e59de90 | 864 | resolve_strategy::simplify<Strategy>::apply(geometry, out, max_distance, strategy); |
7c673cae FG |
865 | } |
866 | }; | |
867 | ||
1e59de90 TL |
868 | template <typename Geometry> |
869 | struct simplify<Geometry, dynamic_geometry_tag> | |
7c673cae FG |
870 | { |
871 | template <typename Distance, typename Strategy> | |
1e59de90 TL |
872 | static inline void apply(Geometry const& geometry, |
873 | Geometry& out, | |
874 | Distance const& max_distance, | |
875 | Strategy const& strategy) | |
7c673cae | 876 | { |
1e59de90 | 877 | traits::visit<Geometry>::apply([&](auto const& g) |
7c673cae | 878 | { |
1e59de90 TL |
879 | using geom_t = util::remove_cref_t<decltype(g)>; |
880 | geom_t o; | |
881 | simplify<geom_t>::apply(g, o, max_distance, strategy); | |
882 | out = std::move(o); | |
883 | }, geometry); | |
884 | } | |
885 | }; | |
7c673cae | 886 | |
1e59de90 TL |
887 | template <typename Geometry> |
888 | struct simplify<Geometry, geometry_collection_tag> | |
889 | { | |
7c673cae | 890 | template <typename Distance, typename Strategy> |
1e59de90 TL |
891 | static inline void apply(Geometry const& geometry, |
892 | Geometry& out, | |
893 | Distance const& max_distance, | |
894 | Strategy const& strategy) | |
7c673cae | 895 | { |
1e59de90 TL |
896 | detail::visit_breadth_first([&](auto const& g) |
897 | { | |
898 | using geom_t = util::remove_cref_t<decltype(g)>; | |
899 | geom_t o; | |
900 | simplify<geom_t>::apply(g, o, max_distance, strategy); | |
901 | traits::emplace_back<Geometry>::apply(out, std::move(o)); | |
902 | return true; | |
903 | }, geometry); | |
7c673cae FG |
904 | } |
905 | }; | |
906 | ||
1e59de90 | 907 | } // namespace resolve_dynamic |
7c673cae FG |
908 | |
909 | ||
910 | /*! | |
911 | \brief Simplify a geometry using a specified strategy | |
912 | \ingroup simplify | |
913 | \tparam Geometry \tparam_geometry | |
914 | \tparam Distance A numerical distance measure | |
915 | \tparam Strategy A type fulfilling a SimplifyStrategy concept | |
916 | \param strategy A strategy to calculate simplification | |
917 | \param geometry input geometry, to be simplified | |
918 | \param out output geometry, simplified version of the input geometry | |
919 | \param max_distance distance (in units of input coordinates) of a vertex | |
920 | to other segments to be removed | |
921 | \param strategy simplify strategy to be used for simplification, might | |
922 | include point-distance strategy | |
923 | ||
924 | \image html svg_simplify_country.png "The image below presents the simplified country" | |
925 | \qbk{distinguish,with strategy} | |
926 | */ | |
927 | template<typename Geometry, typename Distance, typename Strategy> | |
928 | inline void simplify(Geometry const& geometry, Geometry& out, | |
929 | Distance const& max_distance, Strategy const& strategy) | |
930 | { | |
931 | concepts::check<Geometry>(); | |
932 | ||
933 | geometry::clear(out); | |
934 | ||
1e59de90 | 935 | resolve_dynamic::simplify<Geometry>::apply(geometry, out, max_distance, strategy); |
7c673cae FG |
936 | } |
937 | ||
938 | ||
939 | ||
940 | ||
941 | /*! | |
942 | \brief Simplify a geometry | |
943 | \ingroup simplify | |
944 | \tparam Geometry \tparam_geometry | |
945 | \tparam Distance \tparam_numeric | |
946 | \note This version of simplify simplifies a geometry using the default | |
947 | strategy (Douglas Peucker), | |
948 | \param geometry input geometry, to be simplified | |
949 | \param out output geometry, simplified version of the input geometry | |
950 | \param max_distance distance (in units of input coordinates) of a vertex | |
951 | to other segments to be removed | |
952 | ||
953 | \qbk{[include reference/algorithms/simplify.qbk]} | |
954 | */ | |
955 | template<typename Geometry, typename Distance> | |
956 | inline void simplify(Geometry const& geometry, Geometry& out, | |
957 | Distance const& max_distance) | |
958 | { | |
959 | concepts::check<Geometry>(); | |
960 | ||
961 | geometry::simplify(geometry, out, max_distance, default_strategy()); | |
962 | } | |
963 | ||
964 | ||
965 | #ifndef DOXYGEN_NO_DETAIL | |
966 | namespace detail { namespace simplify | |
967 | { | |
968 | ||
969 | ||
970 | /*! | |
971 | \brief Simplify a geometry, using an output iterator | |
972 | and a specified strategy | |
973 | \ingroup simplify | |
974 | \tparam Geometry \tparam_geometry | |
975 | \param geometry input geometry, to be simplified | |
976 | \param out output iterator, outputs all simplified points | |
977 | \param max_distance distance (in units of input coordinates) of a vertex | |
978 | to other segments to be removed | |
979 | \param strategy simplify strategy to be used for simplification, | |
980 | might include point-distance strategy | |
981 | ||
982 | \qbk{distinguish,with strategy} | |
983 | \qbk{[include reference/algorithms/simplify.qbk]} | |
984 | */ | |
985 | template<typename Geometry, typename OutputIterator, typename Distance, typename Strategy> | |
986 | inline void simplify_insert(Geometry const& geometry, OutputIterator out, | |
987 | Distance const& max_distance, Strategy const& strategy) | |
988 | { | |
989 | concepts::check<Geometry const>(); | |
990 | ||
1e59de90 | 991 | resolve_strategy::simplify_insert<Strategy>::apply(geometry, out, max_distance, strategy); |
7c673cae FG |
992 | } |
993 | ||
994 | /*! | |
995 | \brief Simplify a geometry, using an output iterator | |
996 | \ingroup simplify | |
997 | \tparam Geometry \tparam_geometry | |
998 | \param geometry input geometry, to be simplified | |
999 | \param out output iterator, outputs all simplified points | |
1000 | \param max_distance distance (in units of input coordinates) of a vertex | |
1001 | to other segments to be removed | |
1002 | ||
1003 | \qbk{[include reference/algorithms/simplify_insert.qbk]} | |
1004 | */ | |
1005 | template<typename Geometry, typename OutputIterator, typename Distance> | |
1006 | inline void simplify_insert(Geometry const& geometry, OutputIterator out, | |
1007 | Distance const& max_distance) | |
1008 | { | |
1009 | // Concept: output point type = point type of input geometry | |
1010 | concepts::check<Geometry const>(); | |
1011 | concepts::check<typename point_type<Geometry>::type>(); | |
1012 | ||
1013 | simplify_insert(geometry, out, max_distance, default_strategy()); | |
1014 | } | |
1015 | ||
1016 | }} // namespace detail::simplify | |
1017 | #endif // DOXYGEN_NO_DETAIL | |
1018 | ||
1019 | ||
1020 | ||
1021 | }} // namespace boost::geometry | |
1022 | ||
1023 | #endif // BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP |