1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
8 // This file was modified by Oracle on 2013, 2014, 2015.
9 // Modifications copyright (c) 2013-2015 Oracle and/or its affiliates.
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
21 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
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>
33 #include <boost/geometry/algorithms/assign.hpp>
34 #include <boost/geometry/algorithms/envelope.hpp>
35 #include <boost/geometry/algorithms/expand.hpp>
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>
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>
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>
56 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
58 namespace boost { namespace geometry
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
70 \tparam DimensionCount number of dimensions for this section
76 std::size_t DimensionCount
81 static std::size_t const dimension_count = DimensionCount;
83 int directions[DimensionCount];
84 ring_identifier ring_id;
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;
92 std::size_t range_count;
94 signed_size_type non_duplicate_index;
96 bool is_non_duplicate_first;
97 bool is_non_duplicate_last;
105 , non_duplicate_index(-1)
106 , is_non_duplicate_first(false)
107 , is_non_duplicate_last(false)
109 assign_inverse(bounding_box);
110 for (std::size_t i = 0; i < DimensionCount; i++)
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
124 template <typename Box, std::size_t DimensionCount>
125 struct sections : std::vector<section<Box, DimensionCount> >
127 typedef Box box_type;
128 static std::size_t const value = DimensionCount;
132 #ifndef DOXYGEN_NO_DETAIL
133 namespace detail { namespace sectionalize
138 typename DimensionVector,
142 struct get_direction_loop
144 typedef typename boost::mpl::at_c<DimensionVector, Index>::type dimension;
146 template <typename Segment>
147 static inline void apply(Segment const& seg,
148 int directions[Count])
150 typedef typename coordinate_type<Segment>::type coordinate_type;
152 coordinate_type const diff =
153 geometry::get<1, dimension::value>(seg)
154 - geometry::get<0, dimension::value>(seg);
156 coordinate_type zero = coordinate_type();
157 directions[Index] = diff > zero ? 1 : diff < zero ? -1 : 0;
164 >::apply(seg, directions);
168 template <typename DimensionVector, std::size_t Count>
169 struct get_direction_loop<DimensionVector, Count, Count>
171 template <typename Segment>
172 static inline void apply(Segment const&, int [Count])
176 //! Copy one static array to another
177 template <typename T, std::size_t Index, std::size_t Count>
180 static inline void apply(T const source[Count], T target[Count])
182 target[Index] = source[Index];
183 copy_loop<T, Index + 1, Count>::apply(source, target);
187 template <typename T, std::size_t Count>
188 struct copy_loop<T, Count, Count>
190 static inline void apply(T const [Count], T [Count])
194 //! Compare two static arrays
195 template <typename T, std::size_t Index, std::size_t Count>
198 static inline bool apply(T const array1[Count], T const array2[Count])
200 return array1[Index] != array2[Index]
205 >::apply(array1, array2);
209 template <typename T, std::size_t Count>
210 struct compare_loop<T, Count, Count>
212 static inline bool apply(T const [Count], T const [Count])
220 template <std::size_t Dimension, std::size_t DimensionCount>
221 struct check_duplicate_loop
223 template <typename Segment>
224 static inline bool apply(Segment const& seg)
226 if (! geometry::math::equals
228 geometry::get<0, Dimension>(seg),
229 geometry::get<1, Dimension>(seg)
236 return check_duplicate_loop
238 Dimension + 1, DimensionCount
243 template <std::size_t DimensionCount>
244 struct check_duplicate_loop<DimensionCount, DimensionCount>
246 template <typename Segment>
247 static inline bool apply(Segment const&)
253 //! Assign a value to a static array
254 template <typename T, std::size_t Index, std::size_t Count>
257 static inline void apply(T dims[Count], T const value)
260 assign_loop<T, Index + 1, Count>::apply(dims, value);
264 template <typename T, std::size_t Count>
265 struct assign_loop<T, Count, Count>
267 static inline void apply(T [Count], T const)
272 template <typename CSTag>
273 struct box_first_in_section
275 template <typename Box, typename Point>
276 static inline void apply(Box & box, Point const& prev, Point const& curr)
278 geometry::model::referring_segment<Point const> seg(prev, curr);
279 geometry::envelope(seg, box);
284 struct box_first_in_section<cartesian_tag>
286 template <typename Box, typename Point>
287 static inline void apply(Box & box, Point const& prev, Point const& curr)
289 geometry::envelope(prev, box);
290 geometry::expand(box, curr);
294 template <typename CSTag>
295 struct box_next_in_section
297 template <typename Box, typename Point>
298 static inline void apply(Box & box, Point const& prev, Point const& curr)
300 geometry::model::referring_segment<Point const> seg(prev, curr);
301 geometry::expand(box, seg);
306 struct box_next_in_section<cartesian_tag>
308 template <typename Box, typename Point>
309 static inline void apply(Box & box, Point const& , Point const& curr)
311 geometry::expand(box, curr);
315 /// @brief Helper class to create sections of a part of a range, on the fly
319 typename DimensionVector
321 struct sectionalize_part
323 static const std::size_t dimension_count
324 = boost::mpl::size<DimensionVector>::value;
329 typename RobustPolicy,
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)
338 boost::ignore_unused_variable_warning(robust_policy);
340 typedef typename boost::range_value<Sections>::type section_type;
343 (static_cast<std::size_t>(section_type::dimension_count)
344 == static_cast<std::size_t>(boost::mpl::size<DimensionVector>::value))
347 typedef typename geometry::robust_point_type
351 >::type robust_point_type;
353 std::size_t const count = std::distance(begin, end);
359 signed_size_type index = 0;
360 signed_size_type ndi = 0; // non duplicate index
361 section_type section;
363 bool mark_first_non_duplicated = true;
364 std::size_t last_non_duplicate_index = sections.size();
367 robust_point_type previous_robust_point;
368 geometry::recalculate(previous_robust_point, *it, robust_policy);
370 for(Iterator previous = it++;
372 ++previous, ++it, index++)
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);
379 int direction_classes[dimension_count] = {0};
382 DimensionVector, 0, dimension_count
383 >::apply(robust_segment, direction_classes);
385 // if "dir" == 0 for all point-dimensions, it is duplicate.
386 // Those sections might be omitted, if wished, lateron
387 bool duplicate = false;
389 if (direction_classes[0] == 0)
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
396 0, geometry::dimension<Point>::type::value
397 >::apply(robust_segment)
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
408 int, 0, dimension_count
409 >::apply(direction_classes, -99);
413 if (section.count > 0
416 int, 0, dimension_count
417 >::apply(direction_classes, section.directions)
418 || section.count > max_count)
421 if (! section.duplicate)
423 last_non_duplicate_index = sections.size();
426 sections.push_back(section);
427 section = section_type();
430 if (section.count == 0)
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;
438 if (mark_first_non_duplicated && ! duplicate)
440 section.is_non_duplicate_first = true;
441 mark_first_non_duplicated = false;
446 int, 0, dimension_count
447 >::apply(direction_classes, section.directions);
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);
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);
462 section.end_index = index + 1;
468 previous_robust_point = current_robust_point;
471 // Add last section if applicable
472 if (section.count > 0)
474 if (! section.duplicate)
476 last_non_duplicate_index = sections.size();
479 sections.push_back(section);
482 if (last_non_duplicate_index < sections.size()
483 && ! sections[last_non_duplicate_index].duplicate)
485 sections[last_non_duplicate_index].is_non_duplicate_last = true;
493 closure_selector Closure,
496 typename DimensionVector
498 struct sectionalize_range
503 typename RobustPolicy,
506 static inline void apply(Range const& range,
507 RobustPolicy const& robust_policy,
509 ring_identifier ring_id,
510 std::size_t max_count)
512 typedef typename closeable_view<Range const, Closure>::type cview_type;
513 typedef typename reversible_view
516 Reverse ? iterate_reverse : iterate_forward
519 cview_type cview(range);
520 view_type view(cview);
522 std::size_t const n = boost::size(view);
525 // Zero points, no section
531 // Line with one point ==> no sections
535 sectionalize_part<Point, DimensionVector>::apply(sections,
536 boost::begin(view), boost::end(view),
537 robust_policy, ring_id, max_count);
544 typename DimensionVector
546 struct sectionalize_polygon
551 typename RobustPolicy,
554 static inline void apply(Polygon const& poly,
555 RobustPolicy const& robust_policy,
557 ring_identifier ring_id, std::size_t max_count)
559 typedef typename point_type<Polygon>::type point_type;
560 typedef sectionalize_range
562 closure<Polygon>::value, Reverse,
563 point_type, DimensionVector
566 ring_id.ring_index = -1;
567 per_range::apply(exterior_ring(poly), robust_policy, sections, ring_id, max_count);
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)
575 per_range::apply(*it, robust_policy, sections, ring_id, max_count);
580 template <typename DimensionVector>
581 struct sectionalize_box
586 typename RobustPolicy,
589 static inline void apply(Box const& box,
590 RobustPolicy const& robust_policy,
592 ring_identifier const& ring_id, std::size_t max_count)
594 typedef typename point_type<Box>::type point_type;
596 assert_dimension<Box, 2>();
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
604 // TODO: might be replaced by assign_box_corners_oriented
606 point_type ll, lr, ul, ur;
607 geometry::detail::assign_box_corners(box, ll, lr, ul, ur);
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);
621 >::apply(points, robust_policy, sections,
626 template <typename DimensionVector, typename Policy>
627 struct sectionalize_multi
631 typename MultiGeometry,
632 typename RobustPolicy,
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)
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)
645 Policy::apply(*it, robust_policy, sections, ring_id, max_count);
650 template <typename Sections>
651 inline void enlarge_sections(Sections& sections)
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
658 // NOTE: above is old comment to the not used code expanding the Boxes by relaxed_epsilon(10)
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);
668 detail::expand_by_epsilon(it->bounding_box);
673 }} // namespace detail::sectionalize
674 #endif // DOXYGEN_NO_DETAIL
677 #ifndef DOXYGEN_NO_DISPATCH
686 typename DimensionVector
692 false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
701 typename DimensionVector
703 struct sectionalize<box_tag, Box, Reverse, DimensionVector>
704 : detail::sectionalize::sectionalize_box<DimensionVector>
710 typename DimensionVector
719 : detail::sectionalize::sectionalize_range
722 typename point_type<LineString>::type,
731 typename DimensionVector
733 struct sectionalize<ring_tag, Ring, Reverse, DimensionVector>
734 : detail::sectionalize::sectionalize_range
736 geometry::closure<Ring>::value, Reverse,
737 typename point_type<Ring>::type,
746 typename DimensionVector
748 struct sectionalize<polygon_tag, Polygon, Reverse, DimensionVector>
749 : detail::sectionalize::sectionalize_polygon
751 Reverse, DimensionVector
757 typename MultiPolygon,
759 typename DimensionVector
761 struct sectionalize<multi_polygon_tag, MultiPolygon, Reverse, DimensionVector>
762 : detail::sectionalize::sectionalize_multi
765 detail::sectionalize::sectionalize_polygon
776 typename MultiLinestring,
778 typename DimensionVector
780 struct sectionalize<multi_linestring_tag, MultiLinestring, Reverse, DimensionVector>
781 : detail::sectionalize::sectionalize_multi
784 detail::sectionalize::sectionalize_range
787 typename point_type<MultiLinestring>::type,
794 } // namespace dispatch
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)
814 typename DimensionVector,
817 typename RobustPolicy
819 inline void sectionalize(Geometry const& geometry,
820 RobustPolicy const& robust_policy,
822 int source_index = 0,
823 std::size_t max_count = 10)
825 concepts::check<Geometry const>();
827 typedef typename boost::range_value<Sections>::type section_type;
829 // Compiletime check for point type of section boxes
830 // and point type related to robust policy
831 typedef typename geometry::coordinate_type
833 typename section_type::box_type
835 typedef typename geometry::coordinate_type
837 typename geometry::robust_point_type
839 typename geometry::point_type<Geometry>::type,
844 BOOST_MPL_ASSERT((boost::is_same<ctype1, ctype2>));
849 ring_identifier ring_id;
850 ring_id.source_index = source_index;
852 dispatch::sectionalize
854 typename tag<Geometry>::type,
858 >::apply(geometry, robust_policy, sections, ring_id, max_count);
860 detail::sectionalize::enlarge_sections(sections);
864 }} // namespace boost::geometry
867 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP