// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
// Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland.
-// This file was modified by Oracle on 2013-2020.
-// Modifications copyright (c) 2013-2020 Oracle and/or its affiliates.
+// This file was modified by Oracle on 2013-2021.
+// Modifications copyright (c) 2013-2021 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
#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/algorithms/detail/buffer/buffer_box.hpp>
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/closure.hpp>
#include <boost/geometry/core/tags.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
+#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/segment.hpp>
#include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
#include <boost/geometry/policies/robustness/robust_point_type.hpp>
#include <boost/geometry/util/math.hpp>
#include <boost/geometry/util/normalize_spheroidal_coordinates.hpp>
#include <boost/geometry/util/sequence.hpp>
-#include <boost/geometry/views/closeable_view.hpp>
-#include <boost/geometry/views/reversible_view.hpp>
+#include <boost/geometry/views/detail/closed_clockwise_view.hpp>
// TEMP
#include <boost/geometry/strategy/envelope.hpp>
>
struct section
{
- typedef Box box_type;
+ using box_type = Box;
static std::size_t const dimension_count = DimensionCount;
int directions[DimensionCount];
template <typename Box, std::size_t DimensionCount>
struct sections : std::vector<section<Box, DimensionCount> >
{
- typedef Box box_type;
+ using box_type = Box;
static std::size_t const value = DimensionCount;
};
>
struct get_direction_loop
{
- typedef typename util::sequence_element<Index, DimensionVector>::type dimension;
+ using dimension = typename util::sequence_element<Index, DimensionVector>::type;
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);
+ auto const& c0 = geometry::get<0, dimension::value>(seg);
+ auto const& c1 = geometry::get<1, dimension::value>(seg);
directions[Index] = c1 > c0 ? 1 : c1 < c0 ? -1 : 0;
>
struct get_direction_loop<Point, DimensionVector, 0, Count, spherical_tag>
{
- typedef typename util::sequence_element<0, DimensionVector>::type dimension;
+ using dimension = typename util::sequence_element<0, DimensionVector>::type;
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;
+ using coordinate_type = typename coordinate_type<Segment>::type;
+ using units_t = typename coordinate_system<Point>::type::units;
coordinate_type const diff = math::longitude_distance_signed
<
template <typename CSTag>
struct box_first_in_section
{
- template <typename Box, typename Point, typename EnvelopeStrategy>
+ template <typename Box, typename Point, typename Strategy>
static inline void apply(Box & box, Point const& prev, Point const& curr,
- EnvelopeStrategy const& strategy)
+ Strategy 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>
+ template <typename Box, typename Point, typename Strategy>
static inline void apply(Box & box, Point const& prev, Point const& curr,
- ExpandStrategy const& )
+ Strategy const& strategy)
{
- geometry::envelope(prev, box);
- geometry::expand(box, curr);
+ geometry::envelope(prev, box, strategy);
+ geometry::expand(box, curr, strategy);
}
};
{
template <typename Box, typename Point, typename Strategy>
static inline void apply(Box & box, Point const& , Point const& curr,
- Strategy const& )
+ Strategy const& strategy)
{
- geometry::expand(box, curr);
+ geometry::expand(box, curr, strategy);
}
};
/// @brief Helper class to create sections of a part of a range, on the fly
-template
-<
- typename Point,
- typename DimensionVector
->
+template<typename DimensionVector>
struct sectionalize_part
{
static const std::size_t dimension_count
= util::sequence_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
+ typename Strategy
>
static inline void apply(Sections& sections,
Iterator begin, Iterator end,
RobustPolicy const& robust_policy,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
+ Strategy const& strategy,
ring_identifier ring_id,
std::size_t max_count)
{
boost::ignore_unused(robust_policy);
- typedef typename boost::range_value<Sections>::type section_type;
+ using section_type = typename boost::range_value<Sections>::type;
+ using box_type = typename section_type::box_type;
+ using point_type = typename geometry::point_type<box_type>::type;
+
BOOST_STATIC_ASSERT
(
section_type::dimension_count
== util::sequence_size<DimensionVector>::value
);
- typedef typename geometry::robust_point_type
- <
- Point,
- RobustPolicy
- >::type robust_point_type;
+ using robust_point_type = typename geometry::robust_point_type
+ <
+ point_type,
+ RobustPolicy
+ >::type;
std::size_t const count = std::distance(begin, end);
if (count == 0)
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++)
int direction_classes[dimension_count] = {0};
get_direction_loop
<
- Point, DimensionVector, 0, dimension_count
+ point_type, DimensionVector, 0, dimension_count
>::apply(robust_segment, direction_classes);
// if "dir" == 0 for all point-dimensions, it is duplicate.
// (dimension_count might be < dimension<P>::value)
if (check_duplicate_loop
<
- 0, geometry::dimension<Point>::type::value
+ 0, geometry::dimension<point_type>::type::value
>::apply(robust_segment)
)
{
// 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);
+ ::apply(section.bounding_box, previous_robust_point, current_robust_point, 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);
+ ::apply(section.bounding_box, previous_robust_point, current_robust_point, strategy);
}
section.end_index = index + 1;
<
closure_selector Closure,
bool Reverse,
- typename Point,
typename DimensionVector
>
struct sectionalize_range
typename Range,
typename RobustPolicy,
typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
+ typename Strategy
>
static inline void apply(Range const& range,
RobustPolicy const& robust_policy,
Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
+ Strategy const& 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);
+ detail::closed_clockwise_view
+ <
+ Range const,
+ Closure,
+ Reverse ? counterclockwise : clockwise
+ > const view(range);
std::size_t const n = boost::size(view);
if (n == 0)
return;
}
- sectionalize_part<Point, DimensionVector>::apply(sections,
+ sectionalize_part<DimensionVector>::apply(sections,
boost::begin(view), boost::end(view),
- robust_policy, envelope_strategy, expand_strategy,
+ robust_policy, strategy,
ring_id, max_count);
}
};
typename Polygon,
typename RobustPolicy,
typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
+ typename Strategy
>
static inline void apply(Polygon const& poly,
RobustPolicy const& robust_policy,
Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
+ Strategy const& 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;
+ using sectionalizer = sectionalize_range
+ <
+ closure<Polygon>::value, Reverse, DimensionVector
+ >;
ring_id.ring_index = -1;
- per_range::apply(exterior_ring(poly), robust_policy, sections,
- envelope_strategy, expand_strategy, ring_id, max_count);
+ sectionalizer::apply(exterior_ring(poly), robust_policy, sections,
+ 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)
+ auto const& rings = interior_rings(poly);
+ for (auto 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);
+ sectionalizer::apply(*it, robust_policy, sections,
+ strategy, ring_id, max_count);
}
}
};
typename Box,
typename RobustPolicy,
typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
+ typename Strategy
>
static inline void apply(Box const& box,
RobustPolicy const& robust_policy,
Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
+ Strategy const& strategy,
ring_identifier const& ring_id, std::size_t max_count)
{
- typedef typename point_type<Box>::type point_type;
+ using point_type = typename point_type<Box>::type;
assert_dimension<Box, 2>();
// 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);
+ <
+ closed, false, DimensionVector
+ >::apply(points, robust_policy, sections,
+ strategy, ring_id, max_count);
}
};
typename MultiGeometry,
typename RobustPolicy,
typename Sections,
- typename EnvelopeStrategy,
- typename ExpandStrategy
+ typename Strategy
>
static inline void apply(MultiGeometry const& multi,
RobustPolicy const& robust_policy,
Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
+ Strategy const& strategy,
ring_identifier ring_id,
std::size_t max_count)
{
++it, ++ring_id.multi_index)
{
Policy::apply(*it, robust_policy, sections,
- envelope_strategy, expand_strategy,
+ 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 = std::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)
+ // 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, which is not harmful for the result
+ // (but it might be for the performance).
+ // So it should be on the high side.
+
+ // Use a compilable and workable epsilon for all types, for example:
+ // - for double :~ 2.22e-13
+ // - for float :~ 1e-4
+ // - for Boost.Multiprecision (50) :~ 5.35e-48
+ // - for Boost.Rational : 0/1
+
+ for (auto& section : sections)
{
-#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
+ using gt = decltype(section.bounding_box);
+ using ct = typename geometry::coordinate_type<gt>::type;
+ static ct const eps = math::scaled_epsilon<ct>(1000);
+ expand_by_epsilon(section.bounding_box, eps);
}
}
false,
DimensionVector
>
- : detail::sectionalize::sectionalize_range
- <
- closed, false,
- typename point_type<LineString>::type,
- DimensionVector
- >
+ : detail::sectionalize::sectionalize_range<closed, false, DimensionVector>
{};
template
: detail::sectionalize::sectionalize_range
<
geometry::closure<Ring>::value, Reverse,
- typename point_type<Ring>::type,
DimensionVector
>
{};
: detail::sectionalize::sectionalize_multi
<
DimensionVector,
- detail::sectionalize::sectionalize_range
- <
- closed, false,
- typename point_type<MultiLinestring>::type,
- DimensionVector
- >
+ detail::sectionalize::sectionalize_range<closed, false, DimensionVector>
>
{};
\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 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
typename Geometry,
typename Sections,
typename RobustPolicy,
- typename EnvelopeStrategy,
- typename ExpandStrategy
+ typename Strategy
>
inline void sectionalize(Geometry const& geometry,
RobustPolicy const& robust_policy,
Sections& sections,
- EnvelopeStrategy const& envelope_strategy,
- ExpandStrategy const& expand_strategy,
+ Strategy const& strategy,
int source_index = 0,
std::size_t max_count = 10)
{
- BOOST_STATIC_ASSERT((! std::is_fundamental<EnvelopeStrategy>::value));
-
concepts::check<Geometry const>();
- typedef typename boost::range_value<Sections>::type section_type;
+ using section_type = typename boost::range_value<Sections>::type;
// Compiletime check for point type of section boxes
// and point type related to robust policy
Reverse,
DimensionVector
>::apply(geometry, robust_policy, sections,
- envelope_strategy, expand_strategy,
+ strategy,
ring_id, max_count);
- detail::sectionalize::enlarge_sections(sections, envelope_strategy);
+ detail::sectionalize::enlarge_sections(sections, strategy);
}
int source_index = 0,
std::size_t max_count = 10)
{
- typedef typename strategy::envelope::services::default_strategy
+ using box_type = typename Sections::box_type;
+ using strategy_type = typename strategies::envelope::services::default_strategy
<
- typename tag<Geometry>::type,
- typename cs_tag<Geometry>::type
- >::type envelope_strategy_type;
-
- typedef typename strategy::expand::services::default_strategy
- <
- std::conditional_t
- <
- std::is_same<typename tag<Geometry>::type, box_tag>::value,
- box_tag,
- segment_tag
- >,
- typename cs_tag<Geometry>::type
- >::type expand_strategy_type;
+ Geometry,
+ box_type
+ >::type;
boost::geometry::sectionalize
<
Reverse, DimensionVector
>(geometry, robust_policy, sections,
- envelope_strategy_type(),
- expand_strategy_type(),
+ strategy_type(),
source_index, max_count);
}
projects / ceph.git / blobdiff