]>
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 | // Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland. | |
7 | ||
8 | // This file was modified by Oracle on 2013, 2014, 2015. | |
9 | // Modifications copyright (c) 2013-2015 Oracle and/or its affiliates. | |
10 | ||
11 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
12 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
13 | ||
14 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
15 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
16 | ||
17 | // Use, modification and distribution is subject to the Boost Software License, | |
18 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
19 | // http://www.boost.org/LICENSE_1_0.txt) | |
20 | ||
21 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP | |
22 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP | |
23 | ||
24 | #include <cstddef> | |
25 | #include <vector> | |
26 | ||
27 | #include <boost/concept/requires.hpp> | |
28 | #include <boost/mpl/assert.hpp> | |
29 | #include <boost/mpl/vector_c.hpp> | |
30 | #include <boost/range.hpp> | |
31 | #include <boost/static_assert.hpp> | |
32 | ||
33 | #include <boost/geometry/algorithms/assign.hpp> | |
34 | #include <boost/geometry/algorithms/envelope.hpp> | |
35 | #include <boost/geometry/algorithms/expand.hpp> | |
36 | ||
37 | #include <boost/geometry/algorithms/detail/interior_iterator.hpp> | |
38 | #include <boost/geometry/algorithms/detail/recalculate.hpp> | |
39 | #include <boost/geometry/algorithms/detail/ring_identifier.hpp> | |
40 | #include <boost/geometry/algorithms/detail/signed_size_type.hpp> | |
41 | ||
42 | #include <boost/geometry/core/access.hpp> | |
43 | #include <boost/geometry/core/closure.hpp> | |
44 | #include <boost/geometry/core/exterior_ring.hpp> | |
45 | #include <boost/geometry/core/point_order.hpp> | |
46 | #include <boost/geometry/core/tags.hpp> | |
47 | ||
48 | #include <boost/geometry/geometries/concepts/check.hpp> | |
49 | #include <boost/geometry/util/math.hpp> | |
50 | #include <boost/geometry/policies/robustness/no_rescale_policy.hpp> | |
51 | #include <boost/geometry/policies/robustness/robust_point_type.hpp> | |
52 | #include <boost/geometry/views/closeable_view.hpp> | |
53 | #include <boost/geometry/views/reversible_view.hpp> | |
54 | #include <boost/geometry/geometries/segment.hpp> | |
55 | ||
56 | #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> | |
57 | ||
58 | namespace boost { namespace geometry | |
59 | { | |
60 | ||
61 | ||
62 | /*! | |
63 | \brief Structure containing section information | |
64 | \details Section information consists of a bounding box, direction | |
65 | information (if it is increasing or decreasing, per dimension), | |
66 | index information (begin-end, ring, multi) and the number of | |
67 | segments in this section | |
68 | ||
69 | \tparam Box box-type | |
70 | \tparam DimensionCount number of dimensions for this section | |
71 | \ingroup sectionalize | |
72 | */ | |
73 | template | |
74 | < | |
75 | typename Box, | |
76 | std::size_t DimensionCount | |
77 | > | |
78 | struct section | |
79 | { | |
80 | typedef Box box_type; | |
81 | static std::size_t const dimension_count = DimensionCount; | |
82 | ||
83 | int directions[DimensionCount]; | |
84 | ring_identifier ring_id; | |
85 | Box bounding_box; | |
86 | ||
87 | // NOTE: size_type could be passed as template parameter | |
88 | // NOTE: these probably also could be of type std::size_t | |
89 | signed_size_type begin_index; | |
90 | signed_size_type end_index; | |
91 | std::size_t count; | |
92 | std::size_t range_count; | |
93 | bool duplicate; | |
94 | signed_size_type non_duplicate_index; | |
95 | ||
96 | bool is_non_duplicate_first; | |
97 | bool is_non_duplicate_last; | |
98 | ||
99 | inline section() | |
100 | : begin_index(-1) | |
101 | , end_index(-1) | |
102 | , count(0) | |
103 | , range_count(0) | |
104 | , duplicate(false) | |
105 | , non_duplicate_index(-1) | |
106 | , is_non_duplicate_first(false) | |
107 | , is_non_duplicate_last(false) | |
108 | { | |
109 | assign_inverse(bounding_box); | |
110 | for (std::size_t i = 0; i < DimensionCount; i++) | |
111 | { | |
112 | directions[i] = 0; | |
113 | } | |
114 | } | |
115 | }; | |
116 | ||
117 | ||
118 | /*! | |
119 | \brief Structure containing a collection of sections | |
120 | \note Derived from a vector, proves to be faster than of deque | |
121 | \note vector might be templated in the future | |
122 | \ingroup sectionalize | |
123 | */ | |
124 | template <typename Box, std::size_t DimensionCount> | |
125 | struct sections : std::vector<section<Box, DimensionCount> > | |
126 | { | |
127 | typedef Box box_type; | |
128 | static std::size_t const value = DimensionCount; | |
129 | }; | |
130 | ||
131 | ||
132 | #ifndef DOXYGEN_NO_DETAIL | |
133 | namespace detail { namespace sectionalize | |
134 | { | |
135 | ||
136 | template | |
137 | < | |
138 | typename DimensionVector, | |
139 | std::size_t Index, | |
140 | std::size_t Count | |
141 | > | |
142 | struct get_direction_loop | |
143 | { | |
144 | typedef typename boost::mpl::at_c<DimensionVector, Index>::type dimension; | |
145 | ||
146 | template <typename Segment> | |
147 | static inline void apply(Segment const& seg, | |
148 | int directions[Count]) | |
149 | { | |
150 | typedef typename coordinate_type<Segment>::type coordinate_type; | |
151 | ||
152 | coordinate_type const diff = | |
153 | geometry::get<1, dimension::value>(seg) | |
154 | - geometry::get<0, dimension::value>(seg); | |
155 | ||
156 | coordinate_type zero = coordinate_type(); | |
157 | directions[Index] = diff > zero ? 1 : diff < zero ? -1 : 0; | |
158 | ||
159 | get_direction_loop | |
160 | < | |
161 | DimensionVector, | |
162 | Index + 1, | |
163 | Count | |
164 | >::apply(seg, directions); | |
165 | } | |
166 | }; | |
167 | ||
168 | template <typename DimensionVector, std::size_t Count> | |
169 | struct get_direction_loop<DimensionVector, Count, Count> | |
170 | { | |
171 | template <typename Segment> | |
172 | static inline void apply(Segment const&, int [Count]) | |
173 | {} | |
174 | }; | |
175 | ||
176 | //! Copy one static array to another | |
177 | template <typename T, std::size_t Index, std::size_t Count> | |
178 | struct copy_loop | |
179 | { | |
180 | static inline void apply(T const source[Count], T target[Count]) | |
181 | { | |
182 | target[Index] = source[Index]; | |
183 | copy_loop<T, Index + 1, Count>::apply(source, target); | |
184 | } | |
185 | }; | |
186 | ||
187 | template <typename T, std::size_t Count> | |
188 | struct copy_loop<T, Count, Count> | |
189 | { | |
190 | static inline void apply(T const [Count], T [Count]) | |
191 | {} | |
192 | }; | |
193 | ||
194 | //! Compare two static arrays | |
195 | template <typename T, std::size_t Index, std::size_t Count> | |
196 | struct compare_loop | |
197 | { | |
198 | static inline bool apply(T const array1[Count], T const array2[Count]) | |
199 | { | |
200 | return array1[Index] != array2[Index] | |
201 | ? false | |
202 | : compare_loop | |
203 | < | |
204 | T, Index + 1, Count | |
205 | >::apply(array1, array2); | |
206 | } | |
207 | }; | |
208 | ||
209 | template <typename T, std::size_t Count> | |
210 | struct compare_loop<T, Count, Count> | |
211 | { | |
212 | static inline bool apply(T const [Count], T const [Count]) | |
213 | { | |
214 | ||
215 | return true; | |
216 | } | |
217 | }; | |
218 | ||
219 | ||
220 | template <std::size_t Dimension, std::size_t DimensionCount> | |
221 | struct check_duplicate_loop | |
222 | { | |
223 | template <typename Segment> | |
224 | static inline bool apply(Segment const& seg) | |
225 | { | |
226 | if (! geometry::math::equals | |
227 | ( | |
228 | geometry::get<0, Dimension>(seg), | |
229 | geometry::get<1, Dimension>(seg) | |
230 | ) | |
231 | ) | |
232 | { | |
233 | return false; | |
234 | } | |
235 | ||
236 | return check_duplicate_loop | |
237 | < | |
238 | Dimension + 1, DimensionCount | |
239 | >::apply(seg); | |
240 | } | |
241 | }; | |
242 | ||
243 | template <std::size_t DimensionCount> | |
244 | struct check_duplicate_loop<DimensionCount, DimensionCount> | |
245 | { | |
246 | template <typename Segment> | |
247 | static inline bool apply(Segment const&) | |
248 | { | |
249 | return true; | |
250 | } | |
251 | }; | |
252 | ||
253 | //! Assign a value to a static array | |
254 | template <typename T, std::size_t Index, std::size_t Count> | |
255 | struct assign_loop | |
256 | { | |
257 | static inline void apply(T dims[Count], T const value) | |
258 | { | |
259 | dims[Index] = value; | |
260 | assign_loop<T, Index + 1, Count>::apply(dims, value); | |
261 | } | |
262 | }; | |
263 | ||
264 | template <typename T, std::size_t Count> | |
265 | struct assign_loop<T, Count, Count> | |
266 | { | |
267 | static inline void apply(T [Count], T const) | |
268 | { | |
269 | } | |
270 | }; | |
271 | ||
272 | template <typename CSTag> | |
273 | struct box_first_in_section | |
274 | { | |
275 | template <typename Box, typename Point> | |
276 | static inline void apply(Box & box, Point const& prev, Point const& curr) | |
277 | { | |
278 | geometry::model::referring_segment<Point const> seg(prev, curr); | |
279 | geometry::envelope(seg, box); | |
280 | } | |
281 | }; | |
282 | ||
283 | template <> | |
284 | struct box_first_in_section<cartesian_tag> | |
285 | { | |
286 | template <typename Box, typename Point> | |
287 | static inline void apply(Box & box, Point const& prev, Point const& curr) | |
288 | { | |
289 | geometry::envelope(prev, box); | |
290 | geometry::expand(box, curr); | |
291 | } | |
292 | }; | |
293 | ||
294 | template <typename CSTag> | |
295 | struct box_next_in_section | |
296 | { | |
297 | template <typename Box, typename Point> | |
298 | static inline void apply(Box & box, Point const& prev, Point const& curr) | |
299 | { | |
300 | geometry::model::referring_segment<Point const> seg(prev, curr); | |
301 | geometry::expand(box, seg); | |
302 | } | |
303 | }; | |
304 | ||
305 | template <> | |
306 | struct box_next_in_section<cartesian_tag> | |
307 | { | |
308 | template <typename Box, typename Point> | |
309 | static inline void apply(Box & box, Point const& , Point const& curr) | |
310 | { | |
311 | geometry::expand(box, curr); | |
312 | } | |
313 | }; | |
314 | ||
315 | /// @brief Helper class to create sections of a part of a range, on the fly | |
316 | template | |
317 | < | |
318 | typename Point, | |
319 | typename DimensionVector | |
320 | > | |
321 | struct sectionalize_part | |
322 | { | |
323 | static const std::size_t dimension_count | |
324 | = boost::mpl::size<DimensionVector>::value; | |
325 | ||
326 | template | |
327 | < | |
328 | typename Iterator, | |
329 | typename RobustPolicy, | |
330 | typename Sections | |
331 | > | |
332 | static inline void apply(Sections& sections, | |
333 | Iterator begin, Iterator end, | |
334 | RobustPolicy const& robust_policy, | |
335 | ring_identifier ring_id, | |
336 | std::size_t max_count) | |
337 | { | |
338 | boost::ignore_unused_variable_warning(robust_policy); | |
339 | ||
340 | typedef typename boost::range_value<Sections>::type section_type; | |
341 | BOOST_STATIC_ASSERT | |
342 | ( | |
343 | (static_cast<std::size_t>(section_type::dimension_count) | |
344 | == static_cast<std::size_t>(boost::mpl::size<DimensionVector>::value)) | |
345 | ); | |
346 | ||
347 | typedef typename geometry::robust_point_type | |
348 | < | |
349 | Point, | |
350 | RobustPolicy | |
351 | >::type robust_point_type; | |
352 | ||
353 | std::size_t const count = std::distance(begin, end); | |
354 | if (count == 0) | |
355 | { | |
356 | return; | |
357 | } | |
358 | ||
359 | signed_size_type index = 0; | |
360 | signed_size_type ndi = 0; // non duplicate index | |
361 | section_type section; | |
362 | ||
363 | bool mark_first_non_duplicated = true; | |
364 | std::size_t last_non_duplicate_index = sections.size(); | |
365 | ||
366 | Iterator it = begin; | |
367 | robust_point_type previous_robust_point; | |
368 | geometry::recalculate(previous_robust_point, *it, robust_policy); | |
369 | ||
370 | for(Iterator previous = it++; | |
371 | it != end; | |
372 | ++previous, ++it, index++) | |
373 | { | |
374 | robust_point_type current_robust_point; | |
375 | geometry::recalculate(current_robust_point, *it, robust_policy); | |
376 | model::referring_segment<robust_point_type> robust_segment( | |
377 | previous_robust_point, current_robust_point); | |
378 | ||
379 | int direction_classes[dimension_count] = {0}; | |
380 | get_direction_loop | |
381 | < | |
382 | DimensionVector, 0, dimension_count | |
383 | >::apply(robust_segment, direction_classes); | |
384 | ||
385 | // if "dir" == 0 for all point-dimensions, it is duplicate. | |
386 | // Those sections might be omitted, if wished, lateron | |
387 | bool duplicate = false; | |
388 | ||
389 | if (direction_classes[0] == 0) | |
390 | { | |
391 | // Recheck because ALL dimensions should be checked, | |
392 | // not only first one. | |
393 | // (dimension_count might be < dimension<P>::value) | |
394 | if (check_duplicate_loop | |
395 | < | |
396 | 0, geometry::dimension<Point>::type::value | |
397 | >::apply(robust_segment) | |
398 | ) | |
399 | { | |
400 | duplicate = true; | |
401 | ||
402 | // Change direction-info to force new section | |
403 | // Note that wo consecutive duplicate segments will generate | |
404 | // only one duplicate-section. | |
405 | // Actual value is not important as long as it is not -1,0,1 | |
406 | assign_loop | |
407 | < | |
408 | int, 0, dimension_count | |
409 | >::apply(direction_classes, -99); | |
410 | } | |
411 | } | |
412 | ||
413 | if (section.count > 0 | |
414 | && (! compare_loop | |
415 | < | |
416 | int, 0, dimension_count | |
417 | >::apply(direction_classes, section.directions) | |
418 | || section.count > max_count) | |
419 | ) | |
420 | { | |
421 | if (! section.duplicate) | |
422 | { | |
423 | last_non_duplicate_index = sections.size(); | |
424 | } | |
425 | ||
426 | sections.push_back(section); | |
427 | section = section_type(); | |
428 | } | |
429 | ||
430 | if (section.count == 0) | |
431 | { | |
432 | section.begin_index = index; | |
433 | section.ring_id = ring_id; | |
434 | section.duplicate = duplicate; | |
435 | section.non_duplicate_index = ndi; | |
436 | section.range_count = count; | |
437 | ||
438 | if (mark_first_non_duplicated && ! duplicate) | |
439 | { | |
440 | section.is_non_duplicate_first = true; | |
441 | mark_first_non_duplicated = false; | |
442 | } | |
443 | ||
444 | copy_loop | |
445 | < | |
446 | int, 0, dimension_count | |
447 | >::apply(direction_classes, section.directions); | |
448 | ||
449 | // In cartesian this is envelope of previous point expanded with current point | |
450 | // in non-cartesian this is envelope of a segment | |
451 | box_first_in_section<typename cs_tag<robust_point_type>::type> | |
452 | ::apply(section.bounding_box, previous_robust_point, current_robust_point); | |
453 | } | |
454 | else | |
455 | { | |
456 | // In cartesian this is expand with current point | |
457 | // in non-cartesian this is expand with a segment | |
458 | box_next_in_section<typename cs_tag<robust_point_type>::type> | |
459 | ::apply(section.bounding_box, previous_robust_point, current_robust_point); | |
460 | } | |
461 | ||
462 | section.end_index = index + 1; | |
463 | section.count++; | |
464 | if (! duplicate) | |
465 | { | |
466 | ndi++; | |
467 | } | |
468 | previous_robust_point = current_robust_point; | |
469 | } | |
470 | ||
471 | // Add last section if applicable | |
472 | if (section.count > 0) | |
473 | { | |
474 | if (! section.duplicate) | |
475 | { | |
476 | last_non_duplicate_index = sections.size(); | |
477 | } | |
478 | ||
479 | sections.push_back(section); | |
480 | } | |
481 | ||
482 | if (last_non_duplicate_index < sections.size() | |
483 | && ! sections[last_non_duplicate_index].duplicate) | |
484 | { | |
485 | sections[last_non_duplicate_index].is_non_duplicate_last = true; | |
486 | } | |
487 | } | |
488 | }; | |
489 | ||
490 | ||
491 | template | |
492 | < | |
493 | closure_selector Closure, | |
494 | bool Reverse, | |
495 | typename Point, | |
496 | typename DimensionVector | |
497 | > | |
498 | struct sectionalize_range | |
499 | { | |
500 | template | |
501 | < | |
502 | typename Range, | |
503 | typename RobustPolicy, | |
504 | typename Sections | |
505 | > | |
506 | static inline void apply(Range const& range, | |
507 | RobustPolicy const& robust_policy, | |
508 | Sections& sections, | |
509 | ring_identifier ring_id, | |
510 | std::size_t max_count) | |
511 | { | |
512 | typedef typename closeable_view<Range const, Closure>::type cview_type; | |
513 | typedef typename reversible_view | |
514 | < | |
515 | cview_type const, | |
516 | Reverse ? iterate_reverse : iterate_forward | |
517 | >::type view_type; | |
518 | ||
519 | cview_type cview(range); | |
520 | view_type view(cview); | |
521 | ||
522 | std::size_t const n = boost::size(view); | |
523 | if (n == 0) | |
524 | { | |
525 | // Zero points, no section | |
526 | return; | |
527 | } | |
528 | ||
529 | if (n == 1) | |
530 | { | |
531 | // Line with one point ==> no sections | |
532 | return; | |
533 | } | |
534 | ||
535 | sectionalize_part<Point, DimensionVector>::apply(sections, | |
536 | boost::begin(view), boost::end(view), | |
537 | robust_policy, ring_id, max_count); | |
538 | } | |
539 | }; | |
540 | ||
541 | template | |
542 | < | |
543 | bool Reverse, | |
544 | typename DimensionVector | |
545 | > | |
546 | struct sectionalize_polygon | |
547 | { | |
548 | template | |
549 | < | |
550 | typename Polygon, | |
551 | typename RobustPolicy, | |
552 | typename Sections | |
553 | > | |
554 | static inline void apply(Polygon const& poly, | |
555 | RobustPolicy const& robust_policy, | |
556 | Sections& sections, | |
557 | ring_identifier ring_id, std::size_t max_count) | |
558 | { | |
559 | typedef typename point_type<Polygon>::type point_type; | |
560 | typedef sectionalize_range | |
561 | < | |
562 | closure<Polygon>::value, Reverse, | |
563 | point_type, DimensionVector | |
564 | > per_range; | |
565 | ||
566 | ring_id.ring_index = -1; | |
567 | per_range::apply(exterior_ring(poly), robust_policy, sections, ring_id, max_count); | |
568 | ||
569 | ring_id.ring_index++; | |
570 | typename interior_return_type<Polygon const>::type | |
571 | rings = interior_rings(poly); | |
572 | for (typename detail::interior_iterator<Polygon const>::type | |
573 | it = boost::begin(rings); it != boost::end(rings); ++it, ++ring_id.ring_index) | |
574 | { | |
575 | per_range::apply(*it, robust_policy, sections, ring_id, max_count); | |
576 | } | |
577 | } | |
578 | }; | |
579 | ||
580 | template <typename DimensionVector> | |
581 | struct sectionalize_box | |
582 | { | |
583 | template | |
584 | < | |
585 | typename Box, | |
586 | typename RobustPolicy, | |
587 | typename Sections | |
588 | > | |
589 | static inline void apply(Box const& box, | |
590 | RobustPolicy const& robust_policy, | |
591 | Sections& sections, | |
592 | ring_identifier const& ring_id, std::size_t max_count) | |
593 | { | |
594 | typedef typename point_type<Box>::type point_type; | |
595 | ||
596 | assert_dimension<Box, 2>(); | |
597 | ||
598 | // Add all four sides of the 2D-box as separate section. | |
599 | // Easiest is to convert it to a polygon. | |
600 | // However, we don't have the polygon type | |
601 | // (or polygon would be a helper-type). | |
602 | // Therefore we mimic a linestring/std::vector of 5 points | |
603 | ||
604 | // TODO: might be replaced by assign_box_corners_oriented | |
605 | // or just "convert" | |
606 | point_type ll, lr, ul, ur; | |
607 | geometry::detail::assign_box_corners(box, ll, lr, ul, ur); | |
608 | ||
609 | std::vector<point_type> points; | |
610 | points.push_back(ll); | |
611 | points.push_back(ul); | |
612 | points.push_back(ur); | |
613 | points.push_back(lr); | |
614 | points.push_back(ll); | |
615 | ||
616 | sectionalize_range | |
617 | < | |
618 | closed, false, | |
619 | point_type, | |
620 | DimensionVector | |
621 | >::apply(points, robust_policy, sections, | |
622 | ring_id, max_count); | |
623 | } | |
624 | }; | |
625 | ||
626 | template <typename DimensionVector, typename Policy> | |
627 | struct sectionalize_multi | |
628 | { | |
629 | template | |
630 | < | |
631 | typename MultiGeometry, | |
632 | typename RobustPolicy, | |
633 | typename Sections | |
634 | > | |
635 | static inline void apply(MultiGeometry const& multi, | |
636 | RobustPolicy const& robust_policy, | |
637 | Sections& sections, ring_identifier ring_id, std::size_t max_count) | |
638 | { | |
639 | ring_id.multi_index = 0; | |
640 | for (typename boost::range_iterator<MultiGeometry const>::type | |
641 | it = boost::begin(multi); | |
642 | it != boost::end(multi); | |
643 | ++it, ++ring_id.multi_index) | |
644 | { | |
645 | Policy::apply(*it, robust_policy, sections, ring_id, max_count); | |
646 | } | |
647 | } | |
648 | }; | |
649 | ||
650 | template <typename Sections> | |
651 | inline void enlarge_sections(Sections& sections) | |
652 | { | |
653 | // Robustness issue. Increase sections a tiny bit such that all points are really within (and not on border) | |
654 | // Reason: turns might, rarely, be missed otherwise (case: "buffer_mp1") | |
655 | // Drawback: not really, range is now completely inside the section. Section is a tiny bit too large, | |
656 | // which might cause (a small number) of more comparisons | |
657 | ||
658 | // NOTE: above is old comment to the not used code expanding the Boxes by relaxed_epsilon(10) | |
659 | ||
660 | // Enlarge sections by scaled epsilon, this should be consistent with math::equals(). | |
661 | // Points and Segments are equal-compared WRT machine epsilon, but Boxes aren't | |
662 | // Enlarging Boxes ensures that they correspond to the bound objects, | |
663 | // Segments in this case, since Sections are collections of Segments. | |
664 | for (typename boost::range_iterator<Sections>::type it = boost::begin(sections); | |
665 | it != boost::end(sections); | |
666 | ++it) | |
667 | { | |
668 | detail::expand_by_epsilon(it->bounding_box); | |
669 | } | |
670 | } | |
671 | ||
672 | ||
673 | }} // namespace detail::sectionalize | |
674 | #endif // DOXYGEN_NO_DETAIL | |
675 | ||
676 | ||
677 | #ifndef DOXYGEN_NO_DISPATCH | |
678 | namespace dispatch | |
679 | { | |
680 | ||
681 | template | |
682 | < | |
683 | typename Tag, | |
684 | typename Geometry, | |
685 | bool Reverse, | |
686 | typename DimensionVector | |
687 | > | |
688 | struct sectionalize | |
689 | { | |
690 | BOOST_MPL_ASSERT_MSG | |
691 | ( | |
692 | false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE | |
693 | , (types<Geometry>) | |
694 | ); | |
695 | }; | |
696 | ||
697 | template | |
698 | < | |
699 | typename Box, | |
700 | bool Reverse, | |
701 | typename DimensionVector | |
702 | > | |
703 | struct sectionalize<box_tag, Box, Reverse, DimensionVector> | |
704 | : detail::sectionalize::sectionalize_box<DimensionVector> | |
705 | {}; | |
706 | ||
707 | template | |
708 | < | |
709 | typename LineString, | |
710 | typename DimensionVector | |
711 | > | |
712 | struct sectionalize | |
713 | < | |
714 | linestring_tag, | |
715 | LineString, | |
716 | false, | |
717 | DimensionVector | |
718 | > | |
719 | : detail::sectionalize::sectionalize_range | |
720 | < | |
721 | closed, false, | |
722 | typename point_type<LineString>::type, | |
723 | DimensionVector | |
724 | > | |
725 | {}; | |
726 | ||
727 | template | |
728 | < | |
729 | typename Ring, | |
730 | bool Reverse, | |
731 | typename DimensionVector | |
732 | > | |
733 | struct sectionalize<ring_tag, Ring, Reverse, DimensionVector> | |
734 | : detail::sectionalize::sectionalize_range | |
735 | < | |
736 | geometry::closure<Ring>::value, Reverse, | |
737 | typename point_type<Ring>::type, | |
738 | DimensionVector | |
739 | > | |
740 | {}; | |
741 | ||
742 | template | |
743 | < | |
744 | typename Polygon, | |
745 | bool Reverse, | |
746 | typename DimensionVector | |
747 | > | |
748 | struct sectionalize<polygon_tag, Polygon, Reverse, DimensionVector> | |
749 | : detail::sectionalize::sectionalize_polygon | |
750 | < | |
751 | Reverse, DimensionVector | |
752 | > | |
753 | {}; | |
754 | ||
755 | template | |
756 | < | |
757 | typename MultiPolygon, | |
758 | bool Reverse, | |
759 | typename DimensionVector | |
760 | > | |
761 | struct sectionalize<multi_polygon_tag, MultiPolygon, Reverse, DimensionVector> | |
762 | : detail::sectionalize::sectionalize_multi | |
763 | < | |
764 | DimensionVector, | |
765 | detail::sectionalize::sectionalize_polygon | |
766 | < | |
767 | Reverse, | |
768 | DimensionVector | |
769 | > | |
770 | > | |
771 | ||
772 | {}; | |
773 | ||
774 | template | |
775 | < | |
776 | typename MultiLinestring, | |
777 | bool Reverse, | |
778 | typename DimensionVector | |
779 | > | |
780 | struct sectionalize<multi_linestring_tag, MultiLinestring, Reverse, DimensionVector> | |
781 | : detail::sectionalize::sectionalize_multi | |
782 | < | |
783 | DimensionVector, | |
784 | detail::sectionalize::sectionalize_range | |
785 | < | |
786 | closed, false, | |
787 | typename point_type<MultiLinestring>::type, | |
788 | DimensionVector | |
789 | > | |
790 | > | |
791 | ||
792 | {}; | |
793 | ||
794 | } // namespace dispatch | |
795 | #endif | |
796 | ||
797 | ||
798 | /*! | |
799 | \brief Split a geometry into monotonic sections | |
800 | \ingroup sectionalize | |
801 | \tparam Geometry type of geometry to check | |
802 | \tparam Sections type of sections to create | |
803 | \param geometry geometry to create sections from | |
804 | \param robust_policy policy to handle robustness issues | |
805 | \param sections structure with sections | |
806 | \param source_index index to assign to the ring_identifiers | |
807 | \param max_count maximal number of points per section | |
808 | (defaults to 10, this seems to give the fastest results) | |
809 | ||
810 | */ | |
811 | template | |
812 | < | |
813 | bool Reverse, | |
814 | typename DimensionVector, | |
815 | typename Geometry, | |
816 | typename Sections, | |
817 | typename RobustPolicy | |
818 | > | |
819 | inline void sectionalize(Geometry const& geometry, | |
820 | RobustPolicy const& robust_policy, | |
821 | Sections& sections, | |
822 | int source_index = 0, | |
823 | std::size_t max_count = 10) | |
824 | { | |
825 | concepts::check<Geometry const>(); | |
826 | ||
827 | typedef typename boost::range_value<Sections>::type section_type; | |
828 | ||
829 | // Compiletime check for point type of section boxes | |
830 | // and point type related to robust policy | |
831 | typedef typename geometry::coordinate_type | |
832 | < | |
833 | typename section_type::box_type | |
834 | >::type ctype1; | |
835 | typedef typename geometry::coordinate_type | |
836 | < | |
837 | typename geometry::robust_point_type | |
838 | < | |
839 | typename geometry::point_type<Geometry>::type, | |
840 | RobustPolicy | |
841 | >::type | |
842 | >::type ctype2; | |
843 | ||
844 | BOOST_MPL_ASSERT((boost::is_same<ctype1, ctype2>)); | |
845 | ||
846 | ||
847 | sections.clear(); | |
848 | ||
849 | ring_identifier ring_id; | |
850 | ring_id.source_index = source_index; | |
851 | ||
852 | dispatch::sectionalize | |
853 | < | |
854 | typename tag<Geometry>::type, | |
855 | Geometry, | |
856 | Reverse, | |
857 | DimensionVector | |
858 | >::apply(geometry, robust_policy, sections, ring_id, max_count); | |
859 | ||
860 | detail::sectionalize::enlarge_sections(sections); | |
861 | } | |
862 | ||
863 | ||
864 | }} // namespace boost::geometry | |
865 | ||
866 | ||
867 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP |