123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
- // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
- // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
- // Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland.
- // This file was modified by Oracle on 2013, 2014, 2015, 2017, 2018, 2019.
- // Modifications copyright (c) 2013-2019 Oracle and/or its affiliates.
- // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
- // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
- // 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_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
- #include <cstddef>
- #include <vector>
- #include <boost/concept/requires.hpp>
- #include <boost/core/ignore_unused.hpp>
- #include <boost/mpl/assert.hpp>
- #include <boost/mpl/vector_c.hpp>
- #include <boost/range.hpp>
- #include <boost/static_assert.hpp>
- #include <boost/type_traits/is_same.hpp>
- #include <boost/type_traits/is_fundamental.hpp>
- #include <boost/geometry/core/config.hpp>
- #include <boost/geometry/algorithms/assign.hpp>
- #include <boost/geometry/algorithms/envelope.hpp>
- #include <boost/geometry/algorithms/expand.hpp>
- #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
- #include <boost/geometry/algorithms/detail/recalculate.hpp>
- #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
- #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
- #include <boost/geometry/core/access.hpp>
- #include <boost/geometry/core/closure.hpp>
- #include <boost/geometry/core/exterior_ring.hpp>
- #include <boost/geometry/core/point_order.hpp>
- #include <boost/geometry/core/tags.hpp>
- #include <boost/geometry/geometries/concepts/check.hpp>
- #include <boost/geometry/util/math.hpp>
- #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
- #include <boost/geometry/policies/robustness/robust_point_type.hpp>
- #include <boost/geometry/views/closeable_view.hpp>
- #include <boost/geometry/views/reversible_view.hpp>
- #include <boost/geometry/geometries/segment.hpp>
- #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
- #include <boost/geometry/algorithms/detail/buffer/buffer_box.hpp>
- #include <boost/geometry/strategies/envelope.hpp>
- #include <boost/geometry/strategies/expand.hpp>
- namespace boost { namespace geometry
- {
- /*!
- \brief Structure containing section information
- \details Section information consists of a bounding box, direction
- information (if it is increasing or decreasing, per dimension),
- index information (begin-end, ring, multi) and the number of
- segments in this section
- \tparam Box box-type
- \tparam DimensionCount number of dimensions for this section
- \ingroup sectionalize
- */
- template
- <
- typename Box,
- std::size_t DimensionCount
- >
- struct section
- {
- typedef Box box_type;
- static std::size_t const dimension_count = DimensionCount;
- int directions[DimensionCount];
- ring_identifier ring_id;
- Box bounding_box;
- // NOTE: size_type could be passed as template parameter
- // NOTE: these probably also could be of type std::size_t
- signed_size_type begin_index;
- signed_size_type end_index;
- std::size_t count;
- std::size_t range_count;
- bool duplicate;
- signed_size_type non_duplicate_index;
- bool is_non_duplicate_first;
- bool is_non_duplicate_last;
- inline section()
- : begin_index(-1)
- , end_index(-1)
- , count(0)
- , range_count(0)
- , duplicate(false)
- , non_duplicate_index(-1)
- , is_non_duplicate_first(false)
- , is_non_duplicate_last(false)
- {
- assign_inverse(bounding_box);
- for (std::size_t i = 0; i < DimensionCount; i++)
- {
- directions[i] = 0;
- }
- }
- };
- /*!
- \brief Structure containing a collection of sections
- \note Derived from a vector, proves to be faster than of deque
- \note vector might be templated in the future
- \ingroup sectionalize
- */
- template <typename Box, std::size_t DimensionCount>
- struct sections : std::vector<section<Box, DimensionCount> >
- {
- typedef Box box_type;
- static std::size_t const value = DimensionCount;
- };
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace sectionalize
- {
- // NOTE: This utility will NOT work for latitudes, dimension 1 in spherical
- // and geographic coordinate system because in these coordinate systems
- // e.g. a segment on northern hemisphere may go towards greater latitude
- // and then towards lesser latitude.
- template
- <
- typename Point,
- typename DimensionVector,
- std::size_t Index,
- std::size_t Count,
- typename CastedCSTag = typename tag_cast
- <
- typename cs_tag<Point>::type,
- spherical_tag
- >::type
- >
- struct get_direction_loop
- {
- typedef typename boost::mpl::at_c<DimensionVector, Index>::type dimension;
- template <typename Segment>
- static inline void apply(Segment const& seg,
- int directions[Count])
- {
- typedef typename coordinate_type<Segment>::type coordinate_type;
- coordinate_type const c0 = geometry::get<0, dimension::value>(seg);
- coordinate_type const c1 = geometry::get<1, dimension::value>(seg);
- directions[Index] = c1 > c0 ? 1 : c1 < c0 ? -1 : 0;
- get_direction_loop
- <
- Point,
- DimensionVector,
- Index + 1,
- Count,
- CastedCSTag
- >::apply(seg, directions);
- }
- };
- template
- <
- typename Point,
- typename DimensionVector,
- std::size_t Count
- >
- struct get_direction_loop<Point, DimensionVector, 0, Count, spherical_tag>
- {
- typedef typename boost::mpl::at_c<DimensionVector, 0>::type dimension;
- template <typename Segment>
- static inline void apply(Segment const& seg,
- int directions[Count])
- {
- typedef typename coordinate_type<Segment>::type coordinate_type;
- typedef typename coordinate_system<Point>::type::units units_t;
- coordinate_type const diff = math::longitude_distance_signed
- <
- units_t, coordinate_type
- >(geometry::get<0, 0>(seg),
- geometry::get<1, 0>(seg));
- coordinate_type zero = coordinate_type();
- directions[0] = diff > zero ? 1 : diff < zero ? -1 : 0;
- get_direction_loop
- <
- Point,
- DimensionVector,
- 1,
- Count,
- spherical_tag
- >::apply(seg, directions);
- }
- };
- template
- <
- typename Point,
- typename DimensionVector,
- std::size_t Count,
- typename CastedCSTag
- >
- struct get_direction_loop<Point, DimensionVector, Count, Count, CastedCSTag>
- {
- template <typename Segment>
- static inline void apply(Segment const&, int [Count])
- {}
- };
- //! Copy one static array to another
- template <typename T, std::size_t Index, std::size_t Count>
- struct copy_loop
- {
- static inline void apply(T const source[Count], T target[Count])
- {
- target[Index] = source[Index];
- copy_loop<T, Index + 1, Count>::apply(source, target);
- }
- };
- template <typename T, std::size_t Count>
- struct copy_loop<T, Count, Count>
- {
- static inline void apply(T const [Count], T [Count])
- {}
- };
- //! Compare two static arrays
- template <typename T, std::size_t Index, std::size_t Count>
- struct compare_loop
- {
- static inline bool apply(T const array1[Count], T const array2[Count])
- {
- return array1[Index] != array2[Index]
- ? false
- : compare_loop
- <
- T, Index + 1, Count
- >::apply(array1, array2);
- }
- };
- template <typename T, std::size_t Count>
- struct compare_loop<T, Count, Count>
- {
- static inline bool apply(T const [Count], T const [Count])
- {
- return true;
- }
- };
- template <std::size_t Dimension, std::size_t DimensionCount>
- struct check_duplicate_loop
- {
- template <typename Segment>
- static inline bool apply(Segment const& seg)
- {
- if (! geometry::math::equals
- (
- geometry::get<0, Dimension>(seg),
- geometry::get<1, Dimension>(seg)
- )
- )
- {
- return false;
- }
- return check_duplicate_loop
- <
- Dimension + 1, DimensionCount
- >::apply(seg);
- }
- };
- template <std::size_t DimensionCount>
- struct check_duplicate_loop<DimensionCount, DimensionCount>
- {
- template <typename Segment>
- static inline bool apply(Segment const&)
- {
- return true;
- }
- };
- //! Assign a value to a static array
- template <typename T, std::size_t Index, std::size_t Count>
- struct assign_loop
- {
- static inline void apply(T dims[Count], T const value)
- {
- dims[Index] = value;
- assign_loop<T, Index + 1, Count>::apply(dims, value);
- }
- };
- template <typename T, std::size_t Count>
- struct assign_loop<T, Count, Count>
- {
- static inline void apply(T [Count], T const)
- {
- }
- };
- template <typename CSTag>
- struct box_first_in_section
- {
- template <typename Box, typename Point, typename EnvelopeStrategy>
- static inline void apply(Box & box, Point const& prev, Point const& curr,
- EnvelopeStrategy const& strategy)
- {
- geometry::model::referring_segment<Point const> seg(prev, curr);
- geometry::envelope(seg, box, strategy);
- }
- };
- template <>
- struct box_first_in_section<cartesian_tag>
- {
- template <typename Box, typename Point, typename ExpandStrategy>
- static inline void apply(Box & box, Point const& prev, Point const& curr,
- ExpandStrategy const& )
- {
- geometry::envelope(prev, box);
- geometry::expand(box, curr);
- }
- };
- template <typename CSTag>
- struct box_next_in_section
- {
- template <typename Box, typename Point, typename Strategy>
- static inline void apply(Box & box, Point const& prev, Point const& curr,
- Strategy const& strategy)
- {
- geometry::model::referring_segment<Point const> seg(prev, curr);
- geometry::expand(box, seg, strategy);
- }
- };
- template <>
- struct box_next_in_section<cartesian_tag>
- {
- template <typename Box, typename Point, typename Strategy>
- static inline void apply(Box & box, Point const& , Point const& curr,
- Strategy const& )
- {
- geometry::expand(box, curr);
- }
- };
- /// @brief Helper class to create sections of a part of a range, on the fly
- template
- <
- typename Point,
- typename DimensionVector
- >
- struct sectionalize_part
- {
- static const std::size_t dimension_count
- = boost::mpl::size<DimensionVector>::value;
- template
- <
- typename Iterator,
- typename RobustPolicy,
- typename Sections
- >
- static inline void apply(Sections& sections,
- Iterator begin, Iterator end,
- RobustPolicy const& robust_policy,
- ring_identifier ring_id,
- std::size_t max_count)
- {
- typedef typename strategy::envelope::services::default_strategy
- <
- segment_tag,
- typename cs_tag<typename Sections::box_type>::type
- >::type envelope_strategy_type;
- typedef typename strategy::expand::services::default_strategy
- <
- segment_tag,
- typename cs_tag<typename Sections::box_type>::type
- >::type expand_strategy_type;
- apply(sections, begin, end,
- robust_policy,
- envelope_strategy_type(),
- expand_strategy_type(),
- ring_id, max_count);
- }
- template
- <
- typename Iterator,
- typename RobustPolicy,
- typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
- >
- static inline void apply(Sections& sections,
- Iterator begin, Iterator end,
- RobustPolicy const& robust_policy,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
- ring_identifier ring_id,
- std::size_t max_count)
- {
- boost::ignore_unused(robust_policy);
- typedef typename boost::range_value<Sections>::type section_type;
- BOOST_STATIC_ASSERT
- (
- (static_cast<std::size_t>(section_type::dimension_count)
- == static_cast<std::size_t>(boost::mpl::size<DimensionVector>::value))
- );
- typedef typename geometry::robust_point_type
- <
- Point,
- RobustPolicy
- >::type robust_point_type;
- std::size_t const count = std::distance(begin, end);
- if (count == 0)
- {
- return;
- }
- signed_size_type index = 0;
- signed_size_type ndi = 0; // non duplicate index
- section_type section;
- bool mark_first_non_duplicated = true;
- std::size_t last_non_duplicate_index = sections.size();
- Iterator it = begin;
- robust_point_type previous_robust_point;
- geometry::recalculate(previous_robust_point, *it, robust_policy);
-
- for(Iterator previous = it++;
- it != end;
- ++previous, ++it, index++)
- {
- robust_point_type current_robust_point;
- geometry::recalculate(current_robust_point, *it, robust_policy);
- model::referring_segment<robust_point_type> robust_segment(
- previous_robust_point, current_robust_point);
- int direction_classes[dimension_count] = {0};
- get_direction_loop
- <
- Point, DimensionVector, 0, dimension_count
- >::apply(robust_segment, direction_classes);
- // if "dir" == 0 for all point-dimensions, it is duplicate.
- // Those sections might be omitted, if wished, lateron
- bool duplicate = false;
- if (direction_classes[0] == 0)
- {
- // Recheck because ALL dimensions should be checked,
- // not only first one.
- // (dimension_count might be < dimension<P>::value)
- if (check_duplicate_loop
- <
- 0, geometry::dimension<Point>::type::value
- >::apply(robust_segment)
- )
- {
- duplicate = true;
- // Change direction-info to force new section
- // Note that wo consecutive duplicate segments will generate
- // only one duplicate-section.
- // Actual value is not important as long as it is not -1,0,1
- assign_loop
- <
- int, 0, dimension_count
- >::apply(direction_classes, -99);
- }
- }
- if (section.count > 0
- && (! compare_loop
- <
- int, 0, dimension_count
- >::apply(direction_classes, section.directions)
- || section.count > max_count)
- )
- {
- if (! section.duplicate)
- {
- last_non_duplicate_index = sections.size();
- }
- sections.push_back(section);
- section = section_type();
- }
- if (section.count == 0)
- {
- section.begin_index = index;
- section.ring_id = ring_id;
- section.duplicate = duplicate;
- section.non_duplicate_index = ndi;
- section.range_count = count;
- if (mark_first_non_duplicated && ! duplicate)
- {
- section.is_non_duplicate_first = true;
- mark_first_non_duplicated = false;
- }
- copy_loop
- <
- int, 0, dimension_count
- >::apply(direction_classes, section.directions);
- // In cartesian this is envelope of previous point expanded with current point
- // in non-cartesian this is envelope of a segment
- box_first_in_section<typename cs_tag<robust_point_type>::type>
- ::apply(section.bounding_box, previous_robust_point, current_robust_point, envelope_strategy);
- }
- else
- {
- // In cartesian this is expand with current point
- // in non-cartesian this is expand with a segment
- box_next_in_section<typename cs_tag<robust_point_type>::type>
- ::apply(section.bounding_box, previous_robust_point, current_robust_point, expand_strategy);
- }
- section.end_index = index + 1;
- section.count++;
- if (! duplicate)
- {
- ndi++;
- }
- previous_robust_point = current_robust_point;
- }
- // Add last section if applicable
- if (section.count > 0)
- {
- if (! section.duplicate)
- {
- last_non_duplicate_index = sections.size();
- }
- sections.push_back(section);
- }
- if (last_non_duplicate_index < sections.size()
- && ! sections[last_non_duplicate_index].duplicate)
- {
- sections[last_non_duplicate_index].is_non_duplicate_last = true;
- }
- }
- };
- template
- <
- closure_selector Closure,
- bool Reverse,
- typename Point,
- typename DimensionVector
- >
- struct sectionalize_range
- {
- template
- <
- typename Range,
- typename RobustPolicy,
- typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
- >
- static inline void apply(Range const& range,
- RobustPolicy const& robust_policy,
- Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
- ring_identifier ring_id,
- std::size_t max_count)
- {
- typedef typename closeable_view<Range const, Closure>::type cview_type;
- typedef typename reversible_view
- <
- cview_type const,
- Reverse ? iterate_reverse : iterate_forward
- >::type view_type;
- cview_type cview(range);
- view_type view(cview);
- std::size_t const n = boost::size(view);
- if (n == 0)
- {
- // Zero points, no section
- return;
- }
- if (n == 1)
- {
- // Line with one point ==> no sections
- return;
- }
- sectionalize_part<Point, DimensionVector>::apply(sections,
- boost::begin(view), boost::end(view),
- robust_policy, envelope_strategy, expand_strategy,
- ring_id, max_count);
- }
- };
- template
- <
- bool Reverse,
- typename DimensionVector
- >
- struct sectionalize_polygon
- {
- template
- <
- typename Polygon,
- typename RobustPolicy,
- typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
- >
- static inline void apply(Polygon const& poly,
- RobustPolicy const& robust_policy,
- Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
- ring_identifier ring_id,
- std::size_t max_count)
- {
- typedef typename point_type<Polygon>::type point_type;
- typedef sectionalize_range
- <
- closure<Polygon>::value, Reverse,
- point_type, DimensionVector
- > per_range;
- ring_id.ring_index = -1;
- per_range::apply(exterior_ring(poly), robust_policy, sections,
- envelope_strategy, expand_strategy, ring_id, max_count);
- ring_id.ring_index++;
- typename interior_return_type<Polygon const>::type
- rings = interior_rings(poly);
- for (typename detail::interior_iterator<Polygon const>::type
- it = boost::begin(rings); it != boost::end(rings); ++it, ++ring_id.ring_index)
- {
- per_range::apply(*it, robust_policy, sections,
- envelope_strategy, expand_strategy, ring_id, max_count);
- }
- }
- };
- template <typename DimensionVector>
- struct sectionalize_box
- {
- template
- <
- typename Box,
- typename RobustPolicy,
- typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
- >
- static inline void apply(Box const& box,
- RobustPolicy const& robust_policy,
- Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
- ring_identifier const& ring_id, std::size_t max_count)
- {
- typedef typename point_type<Box>::type point_type;
- assert_dimension<Box, 2>();
- // Add all four sides of the 2D-box as separate section.
- // Easiest is to convert it to a polygon.
- // However, we don't have the polygon type
- // (or polygon would be a helper-type).
- // Therefore we mimic a linestring/std::vector of 5 points
- // TODO: might be replaced by assign_box_corners_oriented
- // or just "convert"
- point_type ll, lr, ul, ur;
- geometry::detail::assign_box_corners(box, ll, lr, ul, ur);
- std::vector<point_type> points;
- points.push_back(ll);
- points.push_back(ul);
- points.push_back(ur);
- points.push_back(lr);
- points.push_back(ll);
- // NOTE: Use cartesian envelope strategy in all coordinate systems
- // because edges of a box are not geodesic segments
- sectionalize_range
- <
- closed, false,
- point_type,
- DimensionVector
- >::apply(points, robust_policy, sections,
- envelope_strategy, expand_strategy,
- ring_id, max_count);
- }
- };
- template <typename DimensionVector, typename Policy>
- struct sectionalize_multi
- {
- template
- <
- typename MultiGeometry,
- typename RobustPolicy,
- typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
- >
- static inline void apply(MultiGeometry const& multi,
- RobustPolicy const& robust_policy,
- Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
- ring_identifier ring_id,
- std::size_t max_count)
- {
- ring_id.multi_index = 0;
- for (typename boost::range_iterator<MultiGeometry const>::type
- it = boost::begin(multi);
- it != boost::end(multi);
- ++it, ++ring_id.multi_index)
- {
- Policy::apply(*it, robust_policy, sections,
- envelope_strategy, expand_strategy,
- ring_id, max_count);
- }
- }
- };
- // TODO: If it depends on CS it should probably be made into strategy.
- // For now implemented here because of ongoing work on robustness
- // the fact that it interferes with detail::buffer::buffer_box
- // and that we probably need a general strategy for defining epsilon in
- // various coordinate systems, e.g. for point comparison, enlargement of
- // bounding boxes, etc.
- template <typename CSTag>
- struct expand_by_epsilon
- : not_implemented<CSTag>
- {};
- template <>
- struct expand_by_epsilon<cartesian_tag>
- {
- template <typename Box>
- static inline void apply(Box & box)
- {
- detail::expand_by_epsilon(box);
- }
- };
- template <>
- struct expand_by_epsilon<spherical_tag>
- {
- template <typename Box>
- static inline void apply(Box & box)
- {
- typedef typename coordinate_type<Box>::type coord_t;
- static const coord_t eps = boost::is_same<coord_t, float>::value
- ? coord_t(1e-6)
- : coord_t(1e-12);
- detail::expand_by_epsilon(box, eps);
- }
- };
- // TODO: In geographic CS it should probably also depend on FormulaPolicy.
- template <>
- struct expand_by_epsilon<geographic_tag>
- : expand_by_epsilon<spherical_tag>
- {};
- template <typename Sections, typename Strategy>
- inline void enlarge_sections(Sections& sections, Strategy const&)
- {
- // Enlarge sections slightly, this should be consistent with math::equals()
- // and with the tolerances used in general_form intersections.
- // This avoids missing turns.
-
- // Points and Segments are equal-compared WRT machine epsilon, but Boxes aren't
- // Enlarging Boxes ensures that they correspond to the bound objects,
- // Segments in this case, since Sections are collections of Segments.
- // It makes section a tiny bit too large, which might cause (a small number)
- // of more comparisons
- for (typename boost::range_iterator<Sections>::type it = boost::begin(sections);
- it != boost::end(sections);
- ++it)
- {
- #if defined(BOOST_GEOMETRY_USE_RESCALING)
- detail::sectionalize::expand_by_epsilon
- <
- typename Strategy::cs_tag
- >::apply(it->bounding_box);
- #else
- // Expand the box to avoid missing any intersection. The amount is
- // should be larger than epsilon. About the value itself: the smaller
- // it is, the higher the risk to miss intersections. The larger it is,
- // the more comparisons are made. So it should be on the high side.
- detail::buffer::buffer_box(it->bounding_box, 0.001, it->bounding_box);
- #endif
- }
- }
- }} // namespace detail::sectionalize
- #endif // DOXYGEN_NO_DETAIL
- #ifndef DOXYGEN_NO_DISPATCH
- namespace dispatch
- {
- template
- <
- typename Tag,
- typename Geometry,
- bool Reverse,
- typename DimensionVector
- >
- struct sectionalize
- {
- BOOST_MPL_ASSERT_MSG
- (
- false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
- , (types<Geometry>)
- );
- };
- template
- <
- typename Box,
- bool Reverse,
- typename DimensionVector
- >
- struct sectionalize<box_tag, Box, Reverse, DimensionVector>
- : detail::sectionalize::sectionalize_box<DimensionVector>
- {};
- template
- <
- typename LineString,
- typename DimensionVector
- >
- struct sectionalize
- <
- linestring_tag,
- LineString,
- false,
- DimensionVector
- >
- : detail::sectionalize::sectionalize_range
- <
- closed, false,
- typename point_type<LineString>::type,
- DimensionVector
- >
- {};
- template
- <
- typename Ring,
- bool Reverse,
- typename DimensionVector
- >
- struct sectionalize<ring_tag, Ring, Reverse, DimensionVector>
- : detail::sectionalize::sectionalize_range
- <
- geometry::closure<Ring>::value, Reverse,
- typename point_type<Ring>::type,
- DimensionVector
- >
- {};
- template
- <
- typename Polygon,
- bool Reverse,
- typename DimensionVector
- >
- struct sectionalize<polygon_tag, Polygon, Reverse, DimensionVector>
- : detail::sectionalize::sectionalize_polygon
- <
- Reverse, DimensionVector
- >
- {};
- template
- <
- typename MultiPolygon,
- bool Reverse,
- typename DimensionVector
- >
- struct sectionalize<multi_polygon_tag, MultiPolygon, Reverse, DimensionVector>
- : detail::sectionalize::sectionalize_multi
- <
- DimensionVector,
- detail::sectionalize::sectionalize_polygon
- <
- Reverse,
- DimensionVector
- >
- >
- {};
- template
- <
- typename MultiLinestring,
- bool Reverse,
- typename DimensionVector
- >
- struct sectionalize<multi_linestring_tag, MultiLinestring, Reverse, DimensionVector>
- : detail::sectionalize::sectionalize_multi
- <
- DimensionVector,
- detail::sectionalize::sectionalize_range
- <
- closed, false,
- typename point_type<MultiLinestring>::type,
- DimensionVector
- >
- >
- {};
- } // namespace dispatch
- #endif
- /*!
- \brief Split a geometry into monotonic sections
- \ingroup sectionalize
- \tparam Geometry type of geometry to check
- \tparam Sections type of sections to create
- \param geometry geometry to create sections from
- \param robust_policy policy to handle robustness issues
- \param sections structure with sections
- \param envelope_strategy strategy for envelope calculation
- \param expand_strategy strategy for partitions
- \param source_index index to assign to the ring_identifiers
- \param max_count maximal number of points per section
- (defaults to 10, this seems to give the fastest results)
- */
- template
- <
- bool Reverse,
- typename DimensionVector,
- typename Geometry,
- typename Sections,
- typename RobustPolicy,
- typename EnvelopeStrategy,
- typename ExpandStrategy
- >
- inline void sectionalize(Geometry const& geometry,
- RobustPolicy const& robust_policy,
- Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
- int source_index = 0,
- std::size_t max_count = 10)
- {
- BOOST_STATIC_ASSERT((! boost::is_fundamental<EnvelopeStrategy>::value));
- concepts::check<Geometry const>();
- typedef typename boost::range_value<Sections>::type section_type;
- // Compiletime check for point type of section boxes
- // and point type related to robust policy
- typedef typename geometry::coordinate_type
- <
- typename section_type::box_type
- >::type ctype1;
- typedef typename geometry::coordinate_type
- <
- typename geometry::robust_point_type
- <
- typename geometry::point_type<Geometry>::type,
- RobustPolicy
- >::type
- >::type ctype2;
- BOOST_MPL_ASSERT((boost::is_same<ctype1, ctype2>));
- sections.clear();
- ring_identifier ring_id;
- ring_id.source_index = source_index;
- dispatch::sectionalize
- <
- typename tag<Geometry>::type,
- Geometry,
- Reverse,
- DimensionVector
- >::apply(geometry, robust_policy, sections,
- envelope_strategy, expand_strategy,
- ring_id, max_count);
- detail::sectionalize::enlarge_sections(sections, envelope_strategy);
- }
- template
- <
- bool Reverse,
- typename DimensionVector,
- typename Geometry,
- typename Sections,
- typename RobustPolicy
- >
- inline void sectionalize(Geometry const& geometry,
- RobustPolicy const& robust_policy,
- Sections& sections,
- int source_index = 0,
- std::size_t max_count = 10)
- {
- typedef typename strategy::envelope::services::default_strategy
- <
- typename tag<Geometry>::type,
- typename cs_tag<Geometry>::type
- >::type envelope_strategy_type;
- typedef typename strategy::expand::services::default_strategy
- <
- typename boost::mpl::if_c
- <
- boost::is_same<typename tag<Geometry>::type, box_tag>::value,
- box_tag,
- segment_tag
- >::type,
- typename cs_tag<Geometry>::type
- >::type expand_strategy_type;
- boost::geometry::sectionalize
- <
- Reverse, DimensionVector
- >(geometry, robust_policy, sections,
- envelope_strategy_type(),
- expand_strategy_type(),
- source_index, max_count);
- }
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
|