summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2019-12-05 15:11:01 +0900
committerDongHun Kwak <dh0128.kwak@samsung.com>2019-12-05 15:11:01 +0900
commit3fdc3e5ee96dca5b11d1694975a65200787eab86 (patch)
tree5c1733853892b8397d67706fa453a9bd978d2102 /boost/geometry/algorithms
parent88e602c57797660ebe0f9e15dbd64c1ff16dead3 (diff)
downloadboost-3fdc3e5ee96dca5b11d1694975a65200787eab86.tar.gz
boost-3fdc3e5ee96dca5b11d1694975a65200787eab86.tar.bz2
boost-3fdc3e5ee96dca5b11d1694975a65200787eab86.zip
Imported Upstream version 1.66.0upstream/1.66.0
Diffstat (limited to 'boost/geometry/algorithms')
-rw-r--r--boost/geometry/algorithms/correct.hpp22
-rw-r--r--boost/geometry/algorithms/correct_closure.hpp235
-rw-r--r--boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp43
-rw-r--r--boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp146
-rw-r--r--boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp29
-rw-r--r--boost/geometry/algorithms/detail/direction_code.hpp25
-rw-r--r--boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp9
-rw-r--r--boost/geometry/algorithms/detail/distance/point_to_geometry.hpp2
-rw-r--r--boost/geometry/algorithms/detail/envelope/box.hpp15
-rw-r--r--boost/geometry/algorithms/detail/envelope/multipoint.hpp5
-rw-r--r--boost/geometry/algorithms/detail/envelope/point.hpp13
-rw-r--r--boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp15
-rw-r--r--boost/geometry/algorithms/detail/envelope/segment.hpp66
-rw-r--r--boost/geometry/algorithms/detail/expand/box.hpp51
-rw-r--r--boost/geometry/algorithms/detail/expand/indexed.hpp42
-rw-r--r--boost/geometry/algorithms/detail/expand/point.hpp116
-rw-r--r--boost/geometry/algorithms/detail/expand/segment.hpp48
-rw-r--r--boost/geometry/algorithms/detail/has_self_intersections.hpp6
-rw-r--r--boost/geometry/algorithms/detail/intersection/multi.hpp16
-rw-r--r--boost/geometry/algorithms/detail/intersects/implementation.hpp3
-rw-r--r--boost/geometry/algorithms/detail/is_simple/linear.hpp3
-rw-r--r--boost/geometry/algorithms/detail/normalize.hpp27
-rw-r--r--boost/geometry/algorithms/detail/overlay/add_rings.hpp43
-rw-r--r--boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp28
-rw-r--r--boost/geometry/algorithms/detail/overlay/assign_parents.hpp45
-rw-r--r--boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp18
-rw-r--r--boost/geometry/algorithms/detail/overlay/follow.hpp12
-rw-r--r--boost/geometry/algorithms/detail/overlay/get_turns.hpp53
-rw-r--r--boost/geometry/algorithms/detail/overlay/handle_colocations.hpp93
-rw-r--r--boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp193
-rw-r--r--boost/geometry/algorithms/detail/overlay/intersection_insert.hpp438
-rw-r--r--boost/geometry/algorithms/detail/overlay/is_self_turn.hpp11
-rw-r--r--boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp83
-rw-r--r--boost/geometry/algorithms/detail/overlay/overlay.hpp133
-rw-r--r--boost/geometry/algorithms/detail/overlay/overlay_type.hpp27
-rw-r--r--boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp1
-rw-r--r--boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp21
-rw-r--r--boost/geometry/algorithms/detail/overlay/segment_identifier.hpp3
-rw-r--r--boost/geometry/algorithms/detail/overlay/select_rings.hpp6
-rw-r--r--boost/geometry/algorithms/detail/overlay/self_turn_points.hpp32
-rw-r--r--boost/geometry/algorithms/detail/overlay/sort_by_side.hpp11
-rw-r--r--boost/geometry/algorithms/detail/overlay/traversal.hpp231
-rw-r--r--boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp153
-rw-r--r--boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp10
-rw-r--r--boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp409
-rw-r--r--boost/geometry/algorithms/detail/overlay/traverse.hpp10
-rw-r--r--boost/geometry/algorithms/detail/overlay/turn_info.hpp13
-rw-r--r--boost/geometry/algorithms/detail/relate/less.hpp83
-rw-r--r--boost/geometry/algorithms/detail/relate/linear_areal.hpp6
-rw-r--r--boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp4
-rw-r--r--boost/geometry/algorithms/detail/relate/point_point.hpp9
-rw-r--r--boost/geometry/algorithms/detail/relate/topology_check.hpp7
-rw-r--r--boost/geometry/algorithms/detail/sections/section_functions.hpp27
-rw-r--r--boost/geometry/algorithms/detail/touches/implementation.hpp6
-rw-r--r--boost/geometry/algorithms/detail/within/multi_point.hpp7
-rw-r--r--boost/geometry/algorithms/dispatch/expand.hpp7
56 files changed, 2292 insertions, 878 deletions
diff --git a/boost/geometry/algorithms/correct.hpp b/boost/geometry/algorithms/correct.hpp
index a572d921d5..07e012fafa 100644
--- a/boost/geometry/algorithms/correct.hpp
+++ b/boost/geometry/algorithms/correct.hpp
@@ -32,6 +32,7 @@
#include <boost/variant/static_visitor.hpp>
#include <boost/variant/variant_fwd.hpp>
+#include <boost/geometry/algorithms/correct_closure.hpp>
#include <boost/geometry/algorithms/detail/interior_iterator.hpp>
#include <boost/geometry/core/closure.hpp>
@@ -45,7 +46,6 @@
#include <boost/geometry/geometries/concepts/check.hpp>
#include <boost/geometry/algorithms/area.hpp>
-#include <boost/geometry/algorithms/disjoint.hpp>
#include <boost/geometry/algorithms/detail/multi_modify.hpp>
#include <boost/geometry/util/order_as_direction.hpp>
@@ -140,23 +140,9 @@ struct correct_ring
template <typename Strategy>
static inline void apply(Ring& r, Strategy const& strategy)
{
- // Check close-ness
- if (boost::size(r) > 2)
- {
- // check if closed, if not, close it
- bool const disjoint = geometry::disjoint(*boost::begin(r), *(boost::end(r) - 1));
- closure_selector const s = geometry::closure<Ring>::value;
-
- if (disjoint && (s == closed))
- {
- geometry::append(r, *boost::begin(r));
- }
- if (! disjoint && s != closed)
- {
- // Open it by removing last point
- geometry::traits::resize<Ring>::apply(r, boost::size(r) - 1);
- }
- }
+ // Correct closure if necessary
+ detail::correct_closure::close_or_open_ring<Ring>::apply(r);
+
// Check area
typedef typename Strategy::return_type area_result_type;
Predicate<area_result_type> predicate;
diff --git a/boost/geometry/algorithms/correct_closure.hpp b/boost/geometry/algorithms/correct_closure.hpp
new file mode 100644
index 0000000000..323107f23a
--- /dev/null
+++ b/boost/geometry/algorithms/correct_closure.hpp
@@ -0,0 +1,235 @@
+// Boost.Geometry
+
+// Copyright (c) 2017 Barend Gehrels, 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_CORRECT_CLOSURE_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_CORRECT_CLOSURE_HPP
+
+#include <cstddef>
+
+#include <boost/range.hpp>
+
+#include <boost/variant/apply_visitor.hpp>
+#include <boost/variant/static_visitor.hpp>
+#include <boost/variant/variant_fwd.hpp>
+
+#include <boost/geometry/algorithms/detail/interior_iterator.hpp>
+
+#include <boost/geometry/core/closure.hpp>
+#include <boost/geometry/core/exterior_ring.hpp>
+#include <boost/geometry/core/interior_rings.hpp>
+#include <boost/geometry/core/ring_type.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+#include <boost/geometry/geometries/concepts/check.hpp>
+
+#include <boost/geometry/algorithms/disjoint.hpp>
+#include <boost/geometry/algorithms/detail/multi_modify.hpp>
+
+namespace boost { namespace geometry
+{
+
+// Silence warning C4127: conditional expression is constant
+#if defined(_MSC_VER)
+#pragma warning(push)
+#pragma warning(disable : 4127)
+#endif
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace correct_closure
+{
+
+template <typename Geometry>
+struct nop
+{
+ static inline void apply(Geometry& )
+ {}
+};
+
+
+// Close a ring, if not closed, or open it
+template <typename Ring>
+struct close_or_open_ring
+{
+ static inline void apply(Ring& r)
+ {
+ if (boost::size(r) <= 2)
+ {
+ return;
+ }
+
+ bool const disjoint = geometry::disjoint(*boost::begin(r),
+ *(boost::end(r) - 1));
+ closure_selector const s = geometry::closure<Ring>::value;
+
+ if (disjoint && s == closed)
+ {
+ // Close it by adding first point
+ geometry::append(r, *boost::begin(r));
+ }
+ else if (! disjoint && s != closed)
+ {
+ // Open it by removing last point
+ geometry::traits::resize<Ring>::apply(r, boost::size(r) - 1);
+ }
+ }
+};
+
+// Close/open exterior ring and all its interior rings
+template <typename Polygon>
+struct close_or_open_polygon
+{
+ typedef typename ring_type<Polygon>::type ring_type;
+
+ static inline void apply(Polygon& poly)
+ {
+ close_or_open_ring<ring_type>::apply(exterior_ring(poly));
+
+ typename interior_return_type<Polygon>::type
+ rings = interior_rings(poly);
+
+ for (typename detail::interior_iterator<Polygon>::type
+ it = boost::begin(rings); it != boost::end(rings); ++it)
+ {
+ close_or_open_ring<ring_type>::apply(*it);
+ }
+ }
+};
+
+}} // namespace detail::correct_closure
+#endif // DOXYGEN_NO_DETAIL
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+template <typename Geometry, typename Tag = typename tag<Geometry>::type>
+struct correct_closure: not_implemented<Tag>
+{};
+
+template <typename Point>
+struct correct_closure<Point, point_tag>
+ : detail::correct_closure::nop<Point>
+{};
+
+template <typename LineString>
+struct correct_closure<LineString, linestring_tag>
+ : detail::correct_closure::nop<LineString>
+{};
+
+template <typename Segment>
+struct correct_closure<Segment, segment_tag>
+ : detail::correct_closure::nop<Segment>
+{};
+
+
+template <typename Box>
+struct correct_closure<Box, box_tag>
+ : detail::correct_closure::nop<Box>
+{};
+
+template <typename Ring>
+struct correct_closure<Ring, ring_tag>
+ : detail::correct_closure::close_or_open_ring<Ring>
+{};
+
+template <typename Polygon>
+struct correct_closure<Polygon, polygon_tag>
+ : detail::correct_closure::close_or_open_polygon<Polygon>
+{};
+
+
+template <typename MultiPoint>
+struct correct_closure<MultiPoint, multi_point_tag>
+ : detail::correct_closure::nop<MultiPoint>
+{};
+
+
+template <typename MultiLineString>
+struct correct_closure<MultiLineString, multi_linestring_tag>
+ : detail::correct_closure::nop<MultiLineString>
+{};
+
+
+template <typename Geometry>
+struct correct_closure<Geometry, multi_polygon_tag>
+ : detail::multi_modify
+ <
+ Geometry,
+ detail::correct_closure::close_or_open_polygon
+ <
+ typename boost::range_value<Geometry>::type
+ >
+ >
+{};
+
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+
+namespace resolve_variant
+{
+
+template <typename Geometry>
+struct correct_closure
+{
+ static inline void apply(Geometry& geometry)
+ {
+ concepts::check<Geometry const>();
+ dispatch::correct_closure<Geometry>::apply(geometry);
+ }
+};
+
+template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
+struct correct_closure<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
+{
+ struct visitor: boost::static_visitor<void>
+ {
+ template <typename Geometry>
+ void operator()(Geometry& geometry) const
+ {
+ correct_closure<Geometry>::apply(geometry);
+ }
+ };
+
+ static inline void
+ apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry)
+ {
+ visitor vis;
+ boost::apply_visitor(vis, geometry);
+ }
+};
+
+} // namespace resolve_variant
+
+
+/*!
+\brief Closes or opens a geometry, according to its type
+\details Corrects a geometry w.r.t. closure points to all rings which do not
+ have a closing point and are typed as they should have one, the first point
+ is appended.
+\ingroup correct_closure
+\tparam Geometry \tparam_geometry
+\param geometry \param_geometry which will be corrected if necessary
+*/
+template <typename Geometry>
+inline void correct_closure(Geometry& geometry)
+{
+ resolve_variant::correct_closure<Geometry>::apply(geometry);
+}
+
+
+#if defined(_MSC_VER)
+#pragma warning(pop)
+#endif
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_CORRECT_CLOSURE_HPP
diff --git a/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp b/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp
index a149f1dd46..990081a86c 100644
--- a/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp
+++ b/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp
@@ -243,6 +243,7 @@ struct buffer_range
EndStrategy const& end_strategy,
RobustPolicy const& robust_policy,
Strategy const& strategy, // side strategy
+ bool linear,
output_point_type& first_p1,
output_point_type& first_p2,
output_point_type& last_p1,
@@ -274,6 +275,10 @@ struct buffer_range
* pup: penultimate_point
*/
+ bool const mark_flat
+ = linear
+ && end_strategy.get_piece_type() == geometry::strategy::buffer::buffered_flat_end;
+
geometry::strategy::buffer::result_code result = geometry::strategy::buffer::result_no_output;
bool first = true;
@@ -318,6 +323,11 @@ struct buffer_range
collection.add_side_piece(*prev, *it, generated_side, first);
+ if (first && mark_flat)
+ {
+ collection.mark_flat_start();
+ }
+
penultimate_point = *prev;
ultimate_point = *it;
last_p1 = generated_side.front();
@@ -331,6 +341,12 @@ struct buffer_range
first_p2 = generated_side.back();
}
}
+
+ if (mark_flat)
+ {
+ collection.mark_flat_end();
+ }
+
return result;
}
};
@@ -396,7 +412,7 @@ inline void buffer_point(Point const& point, Collection& collection,
DistanceStrategy const& distance_strategy,
PointStrategy const& point_strategy)
{
- collection.start_new_ring();
+ collection.start_new_ring(false);
std::vector<OutputPointType> range_out;
point_strategy.apply(point, distance_strategy, range_out);
collection.add_piece(geometry::strategy::buffer::buffered_point, range_out, false);
@@ -499,7 +515,7 @@ struct buffer_inserter_ring
side,
distance_strategy, side_strategy, join_strategy, end_strategy,
robust_policy, strategy,
- first_p1, first_p2, last_p1, last_p2);
+ false, first_p1, first_p2, last_p1, last_p2);
// Generate closing join
if (result == geometry::strategy::buffer::result_normal)
@@ -611,7 +627,7 @@ struct buffer_inserter<ring_tag, RingInput, RingOutput>
RobustPolicy const& robust_policy,
Strategy const& strategy) // side strategy
{
- collection.start_new_ring();
+ collection.start_new_ring(distance.negative());
geometry::strategy::buffer::result_code const code
= buffer_inserter_ring<RingInput, RingOutput>::apply(ring,
collection, distance,
@@ -689,7 +705,7 @@ struct buffer_inserter<linestring_tag, Linestring, Polygon>
begin, end, side,
distance_strategy, side_strategy, join_strategy, end_strategy,
robust_policy, strategy,
- first_p1, first_p2, last_p1, last_p2);
+ true, first_p1, first_p2, last_p1, last_p2);
if (result == geometry::strategy::buffer::result_normal)
{
@@ -729,7 +745,7 @@ struct buffer_inserter<linestring_tag, Linestring, Polygon>
std::size_t n = boost::size(simplified);
if (n > 1)
{
- collection.start_new_ring();
+ collection.start_new_ring(false);
output_point_type first_p1;
code = iterate(collection,
boost::begin(simplified), boost::end(simplified),
@@ -803,7 +819,13 @@ private:
{
for (Iterator it = begin; it != end; ++it)
{
- collection.start_new_ring();
+ // For exterior rings, it deflates if distance is negative.
+ // For interior rings, it is vice versa
+ bool const deflate = is_interior
+ ? ! distance.negative()
+ : distance.negative();
+
+ collection.start_new_ring(deflate);
geometry::strategy::buffer::result_code const code
= policy::apply(*it, collection, distance, side_strategy,
join_strategy, end_strategy, point_strategy,
@@ -865,7 +887,7 @@ public:
Strategy const& strategy) // side strategy
{
{
- collection.start_new_ring();
+ collection.start_new_ring(distance.negative());
geometry::strategy::buffer::result_code const code
= policy::apply(exterior_ring(polygon), collection,
@@ -956,11 +978,6 @@ inline void buffer_inserter(GeometryInput const& geometry_input, OutputIterator
typename tag_cast<typename tag<GeometryInput>::type, areal_tag>::type,
areal_tag
>::type::value;
- bool const linear = boost::is_same
- <
- typename tag_cast<typename tag<GeometryInput>::type, linear_tag>::type,
- linear_tag
- >::type::value;
dispatch::buffer_inserter
<
@@ -977,7 +994,7 @@ inline void buffer_inserter(GeometryInput const& geometry_input, OutputIterator
robust_policy, intersection_strategy.get_side_strategy());
collection.get_turns();
- collection.classify_turns(linear);
+ collection.classify_turns();
if (BOOST_GEOMETRY_CONDITION(areal))
{
collection.check_remaining_points(distance_strategy);
diff --git a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp
index c0d906fe62..bc9c1ca7fb 100644
--- a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp
+++ b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp
@@ -46,6 +46,7 @@
#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
+#include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
@@ -216,7 +217,10 @@ struct buffered_piece_collection
// 2: half, not part of offsetted rings - part of robust ring
std::vector<point_type> helper_points; // 4 points for side, 3 points for join - 0 points for flat-end
#endif
+ bool is_flat_start;
+ bool is_flat_end;
+ bool is_deflated;
bool is_convex;
bool is_monotonic_increasing[2]; // 0=x, 1=y
bool is_monotonic_decreasing[2]; // 0=x, 1=y
@@ -244,6 +248,9 @@ struct buffered_piece_collection
, right_index(-1)
, last_segment_index(-1)
, offsetted_count(-1)
+ , is_flat_start(false)
+ , is_flat_end(false)
+ , is_deflated(false)
, is_convex(false)
, robust_min_comparable_radius(0)
, robust_max_comparable_radius(0)
@@ -295,6 +302,8 @@ struct buffered_piece_collection
piece_vector_type m_pieces;
turn_vector_type m_turns;
signed_size_type m_first_piece_index;
+ bool m_deflate;
+ bool m_has_deflated;
buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; // indexed by multi_index
std::vector<robust_original> robust_originals; // robust representation of the original(s)
@@ -333,6 +342,8 @@ struct buffered_piece_collection
buffered_piece_collection(IntersectionStrategy const& intersection_strategy,
RobustPolicy const& robust_policy)
: m_first_piece_index(-1)
+ , m_deflate(false)
+ , m_has_deflated(false)
, m_intersection_strategy(intersection_strategy)
, m_side_strategy(intersection_strategy.get_side_strategy())
, m_area_strategy(intersection_strategy.template get_area_strategy<point_type>())
@@ -498,7 +509,7 @@ struct buffered_piece_collection
}
}
- inline void classify_turns(bool linear)
+ inline void classify_turns()
{
for (typename boost::range_iterator<turn_vector_type>::type it =
boost::begin(m_turns); it != boost::end(m_turns); ++it)
@@ -507,7 +518,7 @@ struct buffered_piece_collection
{
it->location = inside_buffer;
}
- if (it->count_on_original_boundary > 0 && ! linear)
+ if (it->count_on_original_boundary > 0)
{
it->location = inside_buffer;
}
@@ -524,6 +535,90 @@ struct buffered_piece_collection
}
}
+ struct deflate_properties
+ {
+ bool has_inflated;
+ std::size_t count;
+
+ inline deflate_properties()
+ : has_inflated(false)
+ , count(0u)
+ {}
+ };
+
+ inline void discard_turns_for_deflate()
+ {
+ // Deflate cases should have at least 3 points PER deflated original
+ // to form a correct triangle
+
+ // But if there are intersections between a deflated ring and another
+ // ring, it is all accepted
+
+ // In deflate most turns are i/u by nature, but u/u is also possible
+
+ std::map<signed_size_type, deflate_properties> properties;
+
+ for (typename boost::range_iterator<turn_vector_type const>::type it =
+ boost::begin(m_turns); it != boost::end(m_turns); ++it)
+ {
+ const buffer_turn_info_type& turn = *it;
+ if (turn.location == location_ok)
+ {
+ const buffer_turn_operation_type& op0 = turn.operations[0];
+ const buffer_turn_operation_type& op1 = turn.operations[1];
+
+ if (! m_pieces[op0.seg_id.piece_index].is_deflated
+ || ! m_pieces[op1.seg_id.piece_index].is_deflated)
+ {
+ properties[op0.seg_id.multi_index].has_inflated = true;
+ properties[op1.seg_id.multi_index].has_inflated = true;
+ continue;
+ }
+
+ // It is deflated, update counts
+ for (int i = 0; i < 2; i++)
+ {
+ const buffer_turn_operation_type& op = turn.operations[i];
+ if (op.operation == detail::overlay::operation_union
+ || op.operation == detail::overlay::operation_continue)
+ {
+ properties[op.seg_id.multi_index].count++;
+ }
+ }
+ }
+ }
+
+ for (typename boost::range_iterator<turn_vector_type>::type it =
+ boost::begin(m_turns); it != boost::end(m_turns); ++it)
+ {
+ buffer_turn_info_type& turn = *it;
+
+ if (turn.location == location_ok)
+ {
+ const buffer_turn_operation_type& op0 = turn.operations[0];
+ const buffer_turn_operation_type& op1 = turn.operations[1];
+ signed_size_type const multi0 = op0.seg_id.multi_index;
+ signed_size_type const multi1 = op1.seg_id.multi_index;
+
+ if (multi0 == multi1)
+ {
+ const deflate_properties& prop = properties[multi0];
+ if (! prop.has_inflated && prop.count < 3)
+ {
+ // Property is not inflated
+ // Not enough points, this might be caused by <float> where
+ // detection turn-in-original failed because of numeric errors
+ turn.location = location_discard;
+ }
+ }
+ else
+ {
+ // Two different (possibly deflated) rings
+ }
+ }
+ }
+ }
+
template <typename DistanceStrategy>
inline void check_remaining_points(DistanceStrategy const& distance_strategy)
{
@@ -549,7 +644,7 @@ struct buffered_piece_collection
{
if (deflate && turn.count_in_original <= 0)
{
- // For deflate: it is not in original, discard
+ // For deflate/negative buffers: it is not in original, discard
turn.location = location_discard;
}
else if (! deflate && turn.count_in_original > 0)
@@ -559,6 +654,12 @@ struct buffered_piece_collection
}
}
}
+
+ if (m_has_deflated)
+ {
+ // Either strategy was negative, or there were interior rings
+ discard_turns_for_deflate();
+ }
}
inline bool assert_indices_in_robust_rings() const
@@ -827,7 +928,7 @@ struct buffered_piece_collection
}
}
- inline void start_new_ring()
+ inline void start_new_ring(bool deflate)
{
signed_size_type const n = static_cast<signed_size_type>(offsetted_rings.size());
current_segment_id.source_index = 0;
@@ -839,6 +940,13 @@ struct buffered_piece_collection
current_robust_ring.clear();
m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces));
+ m_deflate = deflate;
+ if (deflate)
+ {
+ // Pieces contain either deflated exterior rings, or inflated
+ // interior rings which are effectively deflated too
+ m_has_deflated = true;
+ }
}
inline void abort_ring()
@@ -973,12 +1081,12 @@ struct buffered_piece_collection
piece pc;
pc.type = type;
pc.index = static_cast<signed_size_type>(boost::size(m_pieces));
+ pc.is_deflated = m_deflate;
current_segment_id.piece_index = pc.index;
pc.first_seg_id = current_segment_id;
-
// Assign left/right (for first/last piece per ring they will be re-assigned later)
pc.left_index = pc.index - 1;
pc.right_index = pc.index + 1;
@@ -1232,6 +1340,24 @@ struct buffered_piece_collection
}
}
+ inline void mark_flat_start()
+ {
+ if (! m_pieces.empty())
+ {
+ piece& back = m_pieces.back();
+ back.is_flat_start = true;
+ }
+ }
+
+ inline void mark_flat_end()
+ {
+ if (! m_pieces.empty())
+ {
+ piece& back = m_pieces.back();
+ back.is_flat_end = true;
+ }
+ }
+
//-------------------------------------------------------------------------
inline void enrich()
@@ -1369,12 +1495,14 @@ struct buffered_piece_collection
overlay_buffer,
backtrack_for_buffer
> traverser;
+ std::map<ring_identifier, overlay::ring_turn_info> turn_info_per_ring;
traversed_rings.clear();
buffer_overlay_visitor visitor;
traverser::apply(offsetted_rings, offsetted_rings,
m_intersection_strategy, m_robust_policy,
m_turns, traversed_rings,
+ turn_info_per_ring,
m_clusters, visitor);
}
@@ -1442,8 +1570,12 @@ struct buffered_piece_collection
}
}
- detail::overlay::assign_parents(offsetted_rings, traversed_rings, selected, m_intersection_strategy, true);
- return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out);
+ // Assign parents, checking orientation but NOT discarding double
+ // negative rings (negative child with negative parent)
+ detail::overlay::assign_parents(offsetted_rings, traversed_rings,
+ selected, m_intersection_strategy, true, false);
+ return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out,
+ m_area_strategy);
}
};
diff --git a/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp b/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp
index d23a3b3fd6..29e49f9dae 100644
--- a/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp
+++ b/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp
@@ -311,7 +311,11 @@ class analyse_turn_wrt_piece
template <typename Point, typename Turn>
static inline analyse_result check_helper_segment(Point const& s1,
Point const& s2, Turn const& turn,
+#if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
+ bool , // is on original, to be reused
+#else
bool is_original,
+#endif
Point const& offsetted)
{
boost::ignore_unused(offsetted);
@@ -340,11 +344,9 @@ class analyse_turn_wrt_piece
if (geometry::covered_by(turn.robust_point, box))
{
- // Points on helper-segments are considered as within
- // Points on original boundary are processed differently
- return is_original
- ? analyse_on_original_boundary
- : analyse_within;
+ // Points on helper-segments (and not on its corners)
+ // are considered as within
+ return analyse_within;
}
// It is collinear but not on the segment. Because these
@@ -424,6 +426,13 @@ class analyse_turn_wrt_piece
{
points[i] = piece.robust_ring[piece.offsetted_count + i];
}
+
+ // 3--offsetted outline--0
+ // | |
+ // left | | right
+ // | |
+ // 2===>==original===>===1
+
}
else if (helper_count == 3)
{
@@ -447,9 +456,15 @@ class analyse_turn_wrt_piece
{
return analyse_on_offsetted;
}
- if (comparator(point, points[1]) || comparator(point, points[2]))
+ if (comparator(point, points[1]))
+ {
+ // On original, right corner
+ return piece.is_flat_end ? analyse_continue : analyse_on_original_boundary;
+ }
+ if (comparator(point, points[2]))
{
- return analyse_on_original_boundary;
+ // On original, left corner
+ return piece.is_flat_start ? analyse_continue : analyse_on_original_boundary;
}
// Right side of the piece
diff --git a/boost/geometry/algorithms/detail/direction_code.hpp b/boost/geometry/algorithms/detail/direction_code.hpp
index c5c5221109..3a7d3d8789 100644
--- a/boost/geometry/algorithms/detail/direction_code.hpp
+++ b/boost/geometry/algorithms/detail/direction_code.hpp
@@ -114,7 +114,9 @@ struct direction_code_impl<Point, spherical_equatorial_tag>
typedef typename geometry::select_coordinate_type <Point1, Point2>::type calc_t;
typedef math::detail::constants_on_spheroid<coord1_t, units_t> constants1;
typedef math::detail::constants_on_spheroid<coord2_t, units_t> constants2;
- typedef math::detail::constants_on_spheroid<calc_t, units_t> constants;
+ static coord1_t const pi_half1 = constants1::max_latitude();
+ static coord2_t const pi_half2 = constants2::max_latitude();
+ static calc_t const c0 = 0;
coord1_t const a0 = geometry::get<0>(segment_a);
coord1_t const a1 = geometry::get<1>(segment_a);
@@ -122,11 +124,6 @@ struct direction_code_impl<Point, spherical_equatorial_tag>
coord1_t const b1 = geometry::get<1>(segment_b);
coord2_t const p0 = geometry::get<0>(p);
coord2_t const p1 = geometry::get<1>(p);
- coord1_t const pi_half1 = constants1::max_latitude();
- coord2_t const pi_half2 = constants2::max_latitude();
- calc_t const pi = constants::half_period();
- calc_t const pi_half = constants::max_latitude();
- calc_t const c0 = 0;
if ( (math::equals(b0, a0) && math::equals(b1, a1))
|| (math::equals(b0, p0) && math::equals(b1, p1)) )
@@ -147,12 +144,12 @@ struct direction_code_impl<Point, spherical_equatorial_tag>
// NOTE: as opposed to the implementation for cartesian CS
// here point b is the origin
- calc_t const dlon1 = math::longitude_distance_signed<units_t>(b0, a0);
- calc_t const dlon2 = math::longitude_distance_signed<units_t>(b0, p0);
+ calc_t const dlon1 = math::longitude_distance_signed<units_t, calc_t>(b0, a0);
+ calc_t const dlon2 = math::longitude_distance_signed<units_t, calc_t>(b0, p0);
bool is_antilon1 = false, is_antilon2 = false;
- calc_t const dlat1 = latitude_distance_signed(b1, a1, dlon1, pi, is_antilon1);
- calc_t const dlat2 = latitude_distance_signed(b1, p1, dlon2, pi, is_antilon2);
+ calc_t const dlat1 = latitude_distance_signed<units_t, calc_t>(b1, a1, dlon1, is_antilon1);
+ calc_t const dlat2 = latitude_distance_signed<units_t, calc_t>(b1, p1, dlon2, is_antilon2);
calc_t mx = is_a_pole || is_b_pole || is_p_pole ?
c0 :
@@ -176,10 +173,12 @@ struct direction_code_impl<Point, spherical_equatorial_tag>
return s1 == s2 ? -1 : 1;
}
- template <typename T>
- static inline T latitude_distance_signed(T const& lat1, T const& lat2, T const& lon_ds, T const& pi, bool & is_antilon)
+ template <typename Units, typename T>
+ static inline T latitude_distance_signed(T const& lat1, T const& lat2, T const& lon_ds, bool & is_antilon)
{
- T const c0 = 0;
+ typedef math::detail::constants_on_spheroid<T, Units> constants;
+ static T const pi = constants::half_period();
+ static T const c0 = 0;
T res = lat2 - lat1;
diff --git a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp
index f8d3e3c593..d7aa9089e3 100644
--- a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp
+++ b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp
@@ -36,10 +36,11 @@
#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
#include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
#include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
-#include <boost/geometry/algorithms/detail/relate/less.hpp>
#include <boost/geometry/algorithms/dispatch/disjoint.hpp>
+#include <boost/geometry/policies/compare.hpp>
+
namespace boost { namespace geometry
{
@@ -56,10 +57,10 @@ class multipoint_multipoint
private:
template <typename Iterator>
class unary_disjoint_predicate
- : detail::relate::less
+ : geometry::less<>
{
private:
- typedef detail::relate::less base_type;
+ typedef geometry::less<> base_type;
public:
unary_disjoint_predicate(Iterator first, Iterator last)
@@ -90,7 +91,7 @@ public:
std::vector<point1_type> points1(boost::begin(multipoint1),
boost::end(multipoint1));
- std::sort(points1.begin(), points1.end(), detail::relate::less());
+ std::sort(points1.begin(), points1.end(), geometry::less<>());
typedef unary_disjoint_predicate
<
diff --git a/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp b/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp
index ab5de3d9b2..9596799cb2 100644
--- a/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp
+++ b/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp
@@ -391,7 +391,7 @@ struct distance
template <typename Point, typename Polygon, typename Strategy>
struct distance
<
- Point, Polygon, Strategy, point_tag, polygon_tag,
+ Point, Polygon, Strategy, point_tag, polygon_tag,
strategy_tag_distance_point_segment, false
> : detail::distance::point_to_polygon
<
diff --git a/boost/geometry/algorithms/detail/envelope/box.hpp b/boost/geometry/algorithms/detail/envelope/box.hpp
index 795f51392e..33b43da255 100644
--- a/boost/geometry/algorithms/detail/envelope/box.hpp
+++ b/boost/geometry/algorithms/detail/envelope/box.hpp
@@ -4,11 +4,12 @@
// Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
-// This file was modified by Oracle on 2015, 2016.
-// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.
+// This file was modified by Oracle on 2015, 2016, 2017.
+// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -146,13 +147,19 @@ namespace dispatch
{
-template <typename Box, typename CS_Tag>
-struct envelope<Box, box_tag, CS_Tag>
+template <typename Box>
+struct envelope<Box, box_tag, cartesian_tag>
: detail::envelope::envelope_box
{};
template <typename Box>
+struct envelope<Box, box_tag, spherical_polar_tag>
+ : detail::envelope::envelope_box_on_spheroid
+{};
+
+
+template <typename Box>
struct envelope<Box, box_tag, spherical_equatorial_tag>
: detail::envelope::envelope_box_on_spheroid
{};
diff --git a/boost/geometry/algorithms/detail/envelope/multipoint.hpp b/boost/geometry/algorithms/detail/envelope/multipoint.hpp
index efee4701c9..eef7563796 100644
--- a/boost/geometry/algorithms/detail/envelope/multipoint.hpp
+++ b/boost/geometry/algorithms/detail/envelope/multipoint.hpp
@@ -1,9 +1,10 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Copyright (c) 2015-2016, Oracle and/or its affiliates.
+// Copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -336,8 +337,6 @@ public:
{
detail::expand::point_loop
<
- strategy::compare::default_strategy,
- strategy::compare::default_strategy,
2, dimension<Box>::value
>::apply(mbr, *it, strategy);
}
diff --git a/boost/geometry/algorithms/detail/envelope/point.hpp b/boost/geometry/algorithms/detail/envelope/point.hpp
index ee0559bf5f..86e73f3aa3 100644
--- a/boost/geometry/algorithms/detail/envelope/point.hpp
+++ b/boost/geometry/algorithms/detail/envelope/point.hpp
@@ -4,11 +4,12 @@
// Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
-// This file was modified by Oracle on 2015, 2016.
+// This file was modified by Oracle on 2015, 2016, 2017.
// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -102,13 +103,19 @@ namespace dispatch
{
-template <typename Point, typename CS_Tag>
-struct envelope<Point, point_tag, CS_Tag>
+template <typename Point>
+struct envelope<Point, point_tag, cartesian_tag>
: detail::envelope::envelope_one_point<0, dimension<Point>::value>
{};
template <typename Point>
+struct envelope<Point, point_tag, spherical_polar_tag>
+ : detail::envelope::envelope_point_on_spheroid
+{};
+
+
+template <typename Point>
struct envelope<Point, point_tag, spherical_equatorial_tag>
: detail::envelope::envelope_point_on_spheroid
{};
diff --git a/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp b/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp
index f61fc422de..9b9e2f85d3 100644
--- a/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp
+++ b/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp
@@ -1,9 +1,10 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Copyright (c) 2015-2016, Oracle and/or its affiliates.
+// Copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -194,8 +195,6 @@ struct envelope_range_of_boxes_by_expansion
{
detail::expand::indexed_loop
<
- strategy::compare::default_strategy,
- strategy::compare::default_strategy,
min_corner,
Dimension,
DimensionCount
@@ -203,8 +202,6 @@ struct envelope_range_of_boxes_by_expansion
detail::expand::indexed_loop
<
- strategy::compare::default_strategy,
- strategy::compare::default_strategy,
max_corner,
Dimension,
DimensionCount
@@ -243,9 +240,15 @@ struct envelope_range_of_boxes
RangeOfBoxes const
>::type iterator_type;
+ static const bool is_equatorial = ! boost::is_same
+ <
+ typename cs_tag<box_type>::type,
+ spherical_polar_tag
+ >::value;
+
typedef math::detail::constants_on_spheroid
<
- coordinate_type, units_type
+ coordinate_type, units_type, is_equatorial
> constants;
typedef longitude_interval<coordinate_type> interval_type;
diff --git a/boost/geometry/algorithms/detail/envelope/segment.hpp b/boost/geometry/algorithms/detail/envelope/segment.hpp
index 7e37194968..97f2fc84a8 100644
--- a/boost/geometry/algorithms/detail/envelope/segment.hpp
+++ b/boost/geometry/algorithms/detail/envelope/segment.hpp
@@ -80,6 +80,35 @@ struct envelope_segment_call_vertex_latitude<CalculationType, geographic_tag>
}
};
+template <typename Units, typename CS_Tag>
+struct envelope_segment_convert_polar
+{
+ template <typename T>
+ static inline void pre(T & , T & ) {}
+
+ template <typename T>
+ static inline void post(T & , T & ) {}
+};
+
+template <typename Units>
+struct envelope_segment_convert_polar<Units, spherical_polar_tag>
+{
+ template <typename T>
+ static inline void pre(T & lat1, T & lat2)
+ {
+ lat1 = math::latitude_convert_ep<Units>(lat1);
+ lat2 = math::latitude_convert_ep<Units>(lat2);
+ }
+
+ template <typename T>
+ static inline void post(T & lat1, T & lat2)
+ {
+ lat1 = math::latitude_convert_ep<Units>(lat1);
+ lat2 = math::latitude_convert_ep<Units>(lat2);
+ std::swap(lat1, lat2);
+ }
+};
+
template <typename CS_Tag>
class envelope_segment_impl
{
@@ -171,7 +200,7 @@ private:
lat1 = lat_min;
}
}
- else if (mid_lat > 0)
+ else
{
// update using max latitude
CalculationType const lat_max_rad = p_max;
@@ -266,29 +295,29 @@ private:
Box, box_coordinate_type, Units
>::type helper_box_type;
- helper_box_type radian_mbr;
+ helper_box_type helper_mbr;
geometry::set
<
min_corner, 0
- >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lon1));
+ >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lon1));
geometry::set
<
min_corner, 1
- >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lat1));
+ >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lat1));
geometry::set
<
max_corner, 0
- >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lon2));
+ >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lon2));
geometry::set
<
max_corner, 1
- >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lat2));
+ >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lat2));
- transform_units(radian_mbr, mbr);
+ transform_units(helper_mbr, mbr);
}
@@ -347,7 +376,14 @@ public:
Box& mbr,
Strategy const& strategy)
{
+ typedef envelope_segment_convert_polar<Units, typename cs_tag<Box>::type> convert_polar;
+
+ convert_polar::pre(lat1, lat2);
+
apply<Units>(lon1, lat1, lon2, lat2, strategy);
+
+ convert_polar::post(lat1, lat2);
+
create_box<Units>(lon1, lat1, lon2, lat2, mbr);
}
@@ -366,7 +402,14 @@ public:
Strategy const& strategy,
CalculationType alp1)
{
+ typedef envelope_segment_convert_polar<Units, typename cs_tag<Box>::type> convert_polar;
+
+ convert_polar::pre(lat1, lat2);
+
apply<Units>(lon1, lat1, lon2, lat2, strategy, alp1);
+
+ convert_polar::post(lat1, lat2);
+
create_box<Units>(lon1, lat1, lon2, lat2, mbr);
}
};
@@ -383,8 +426,6 @@ struct envelope_one_segment
envelope_one_point<Dimension, DimensionCount>::apply(p1, mbr, strategy);
detail::expand::point_loop
<
- strategy::compare::default_strategy,
- strategy::compare::default_strategy,
Dimension,
DimensionCount
>::apply(mbr, p2, strategy);
@@ -409,13 +450,14 @@ struct envelope_segment
envelope_one_segment<2, DimensionCount>::apply(p1, p2, mbr, strategy);
}
- template <typename Segment, typename Box>
- static inline void apply(Segment const& segment, Box& mbr)
+ template <typename Segment, typename Box, typename Strategy>
+ static inline void apply(Segment const& segment, Box& mbr,
+ Strategy const& strategy)
{
typename point_type<Segment>::type p[2];
detail::assign_point_from_index<0>(segment, p[0]);
detail::assign_point_from_index<1>(segment, p[1]);
- apply(p[0], p[1], mbr);
+ apply(p[0], p[1], mbr, strategy);
}
};
diff --git a/boost/geometry/algorithms/detail/expand/box.hpp b/boost/geometry/algorithms/detail/expand/box.hpp
index 3edb23f5ae..485f4d25e6 100644
--- a/boost/geometry/algorithms/detail/expand/box.hpp
+++ b/boost/geometry/algorithms/detail/expand/box.hpp
@@ -5,11 +5,12 @@
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
// Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France.
-// This file was modified by Oracle on 2015, 2016.
-// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.
+// This file was modified by Oracle on 2015, 2016, 2017.
+// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -73,48 +74,54 @@ namespace dispatch
template
<
typename BoxOut, typename BoxIn,
- typename StrategyLess, typename StrategyGreater,
typename CSTagOut, typename CSTag
>
struct expand
<
BoxOut, BoxIn,
- StrategyLess, StrategyGreater,
box_tag, box_tag,
CSTagOut, CSTag
- > : detail::expand::expand_indexed
- <
- 0, dimension<BoxIn>::value, StrategyLess, StrategyGreater
- >
+ >
{
- BOOST_MPL_ASSERT_MSG((boost::is_same<CSTagOut, CSTag>::value),
- COORDINATE_SYSTEMS_MUST_BE_THE_SAME,
+ BOOST_MPL_ASSERT_MSG((false),
+ NOT_IMPLEMENTED_FOR_THESE_COORDINATE_SYSTEMS,
(types<CSTagOut, CSTag>()));
};
-template
-<
- typename BoxOut, typename BoxIn,
- typename StrategyLess, typename StrategyGreater
->
+template <typename BoxOut, typename BoxIn>
+struct expand
+ <
+ BoxOut, BoxIn,
+ box_tag, box_tag,
+ cartesian_tag, cartesian_tag
+ > : detail::expand::expand_indexed
+ <
+ 0, dimension<BoxIn>::value
+ >
+{};
+
+template <typename BoxOut, typename BoxIn>
struct expand
<
BoxOut, BoxIn,
- StrategyLess, StrategyGreater,
box_tag, box_tag,
spherical_equatorial_tag, spherical_equatorial_tag
> : detail::expand::box_on_spheroid
{};
-template
-<
- typename BoxOut, typename BoxIn,
- typename StrategyLess, typename StrategyGreater
->
+template <typename BoxOut, typename BoxIn>
+struct expand
+ <
+ BoxOut, BoxIn,
+ box_tag, box_tag,
+ spherical_polar_tag, spherical_polar_tag
+ > : detail::expand::box_on_spheroid
+{};
+
+template <typename BoxOut, typename BoxIn>
struct expand
<
BoxOut, BoxIn,
- StrategyLess, StrategyGreater,
box_tag, box_tag,
geographic_tag, geographic_tag
> : detail::expand::box_on_spheroid
diff --git a/boost/geometry/algorithms/detail/expand/indexed.hpp b/boost/geometry/algorithms/detail/expand/indexed.hpp
index 28cf0e2e4f..fe7ee4f781 100644
--- a/boost/geometry/algorithms/detail/expand/indexed.hpp
+++ b/boost/geometry/algorithms/detail/expand/indexed.hpp
@@ -5,11 +5,12 @@
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
// Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France.
-// This file was modified by Oracle on 2015, 2016.
-// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.
+// This file was modified by Oracle on 2015, 2016, 2017.
+// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, 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.
@@ -22,15 +23,13 @@
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXPAND_INDEXED_HPP
#include <cstddef>
+#include <functional>
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/tags.hpp>
#include <boost/geometry/util/select_coordinate_type.hpp>
-#include <boost/geometry/strategies/compare.hpp>
-#include <boost/geometry/policies/compare.hpp>
-
#include <boost/geometry/algorithms/dispatch/expand.hpp>
@@ -44,7 +43,6 @@ namespace detail { namespace expand
template
<
- typename StrategyLess, typename StrategyGreater,
std::size_t Index,
std::size_t Dimension, std::size_t DimensionCount
>
@@ -53,27 +51,17 @@ struct indexed_loop
template <typename Box, typename Geometry, typename Strategy>
static inline void apply(Box& box, Geometry const& source, Strategy const& strategy)
{
- typedef typename strategy::compare::detail::select_strategy
- <
- StrategyLess, 1, Box, Dimension
- >::type less_type;
-
- typedef typename strategy::compare::detail::select_strategy
- <
- StrategyGreater, -1, Box, Dimension
- >::type greater_type;
-
typedef typename select_coordinate_type
<
Box,
Geometry
>::type coordinate_type;
- less_type less;
- greater_type greater;
-
coordinate_type const coord = get<Index, Dimension>(source);
+ std::less<coordinate_type> less;
+ std::greater<coordinate_type> greater;
+
if (less(coord, get<min_corner, Dimension>(box)))
{
set<min_corner, Dimension>(box, coord);
@@ -86,21 +74,15 @@ struct indexed_loop
indexed_loop
<
- StrategyLess, StrategyGreater,
Index, Dimension + 1, DimensionCount
>::apply(box, source, strategy);
}
};
-template
-<
- typename StrategyLess, typename StrategyGreater,
- std::size_t Index, std::size_t DimensionCount
->
+template <std::size_t Index, std::size_t DimensionCount>
struct indexed_loop
<
- StrategyLess, StrategyGreater,
Index, DimensionCount, DimensionCount
>
{
@@ -111,11 +93,7 @@ struct indexed_loop
// Changes a box such that the other box is also contained by the box
-template
-<
- std::size_t Dimension, std::size_t DimensionCount,
- typename StrategyLess, typename StrategyGreater
->
+template <std::size_t Dimension, std::size_t DimensionCount>
struct expand_indexed
{
template <typename Box, typename Geometry, typename Strategy>
@@ -125,13 +103,11 @@ struct expand_indexed
{
indexed_loop
<
- StrategyLess, StrategyGreater,
0, Dimension, DimensionCount
>::apply(box, geometry, strategy);
indexed_loop
<
- StrategyLess, StrategyGreater,
1, Dimension, DimensionCount
>::apply(box, geometry, strategy);
}
diff --git a/boost/geometry/algorithms/detail/expand/point.hpp b/boost/geometry/algorithms/detail/expand/point.hpp
index f0cbd1db02..2d8b0feff6 100644
--- a/boost/geometry/algorithms/detail/expand/point.hpp
+++ b/boost/geometry/algorithms/detail/expand/point.hpp
@@ -5,11 +5,12 @@
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
// Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France.
-// This file was modified by Oracle on 2015, 2016.
-// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.
+// This file was modified by Oracle on 2015, 2016, 2017.
+// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, 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.
@@ -23,6 +24,7 @@
#include <cstddef>
#include <algorithm>
+#include <functional>
#include <boost/mpl/assert.hpp>
#include <boost/type_traits/is_same.hpp>
@@ -36,9 +38,6 @@
#include <boost/geometry/util/math.hpp>
#include <boost/geometry/util/select_coordinate_type.hpp>
-#include <boost/geometry/strategies/compare.hpp>
-#include <boost/geometry/policies/compare.hpp>
-
#include <boost/geometry/algorithms/detail/normalize.hpp>
#include <boost/geometry/algorithms/detail/envelope/transform_units.hpp>
@@ -53,33 +52,19 @@ namespace detail { namespace expand
{
-template
-<
- typename StrategyLess, typename StrategyGreater,
- std::size_t Dimension, std::size_t DimensionCount
->
+template <std::size_t Dimension, std::size_t DimensionCount>
struct point_loop
{
template <typename Box, typename Point, typename Strategy>
static inline void apply(Box& box, Point const& source, Strategy const& strategy)
{
- typedef typename strategy::compare::detail::select_strategy
- <
- StrategyLess, 1, Point, Dimension
- >::type less_type;
-
- typedef typename strategy::compare::detail::select_strategy
- <
- StrategyGreater, -1, Point, Dimension
- >::type greater_type;
-
typedef typename select_coordinate_type
<
Point, Box
>::type coordinate_type;
- less_type less;
- greater_type greater;
+ std::less<coordinate_type> less;
+ std::greater<coordinate_type> greater;
coordinate_type const coord = get<Dimension>(source);
@@ -93,37 +78,21 @@ struct point_loop
set<max_corner, Dimension>(box, coord);
}
- point_loop
- <
- StrategyLess, StrategyGreater, Dimension + 1, DimensionCount
- >::apply(box, source, strategy);
+ point_loop<Dimension + 1, DimensionCount>::apply(box, source, strategy);
}
};
-template
-<
- typename StrategyLess,
- typename StrategyGreater,
- std::size_t DimensionCount
->
-struct point_loop
- <
- StrategyLess, StrategyGreater, DimensionCount, DimensionCount
- >
+template <std::size_t DimensionCount>
+struct point_loop<DimensionCount, DimensionCount>
{
template <typename Box, typename Point, typename Strategy>
static inline void apply(Box&, Point const&, Strategy const&) {}
};
-// implementation for the spherical equatorial and geographic coordinate systems
-template
-<
- typename StrategyLess,
- typename StrategyGreater,
- std::size_t DimensionCount
->
+// implementation for the spherical and geographic coordinate systems
+template <std::size_t DimensionCount, bool IsEquatorial = true>
struct point_loop_on_spheroid
{
template <typename Box, typename Point, typename Strategy>
@@ -133,11 +102,12 @@ struct point_loop_on_spheroid
{
typedef typename point_type<Box>::type box_point_type;
typedef typename coordinate_type<Box>::type box_coordinate_type;
+ typedef typename coordinate_system<Box>::type::units units_type;
typedef math::detail::constants_on_spheroid
<
box_coordinate_type,
- typename coordinate_system<Box>::type::units
+ units_type
> constants;
// normalize input point and input box
@@ -157,7 +127,7 @@ struct point_loop_on_spheroid
b_lon_max = geometry::get<max_corner, 0>(box),
b_lat_max = geometry::get<max_corner, 1>(box);
- if (math::equals(math::abs(p_lat), constants::max_latitude()))
+ if (math::is_latitude_pole<units_type, IsEquatorial>(p_lat))
{
// the point of expansion is the either the north or the
// south pole; the only important coordinate here is the
@@ -169,7 +139,7 @@ struct point_loop_on_spheroid
}
if (math::equals(b_lat_min, b_lat_max)
- && math::equals(math::abs(b_lat_min), constants::max_latitude()))
+ && math::is_latitude_pole<units_type, IsEquatorial>(b_lat_min))
{
// the box degenerates to either the north or the south pole;
// the only important coordinate here is the pole's latitude,
@@ -228,7 +198,7 @@ struct point_loop_on_spheroid
point_loop
<
- StrategyLess, StrategyGreater, 2, DimensionCount
+ 2, DimensionCount
>::apply(box, point, strategy);
}
};
@@ -246,56 +216,70 @@ namespace dispatch
template
<
typename BoxOut, typename Point,
- typename StrategyLess, typename StrategyGreater,
typename CSTagOut, typename CSTag
>
struct expand
<
BoxOut, Point,
- StrategyLess, StrategyGreater,
box_tag, point_tag,
CSTagOut, CSTag
- > : detail::expand::point_loop
- <
- StrategyLess, StrategyGreater, 0, dimension<Point>::value
- >
+ >
{
- BOOST_MPL_ASSERT_MSG((boost::is_same<CSTagOut, CSTag>::value),
- COORDINATE_SYSTEMS_MUST_BE_THE_SAME,
+ BOOST_MPL_ASSERT_MSG((false),
+ NOT_IMPLEMENTED_FOR_THESE_COORDINATE_SYSTEMS,
(types<CSTagOut, CSTag>()));
};
-template
-<
- typename BoxOut, typename Point,
- typename StrategyLess, typename StrategyGreater
->
+
+template <typename BoxOut, typename Point>
+struct expand
+ <
+ BoxOut, Point,
+ box_tag, point_tag,
+ cartesian_tag, cartesian_tag
+ > : detail::expand::point_loop
+ <
+ 0, dimension<Point>::value
+ >
+{};
+
+template <typename BoxOut, typename Point>
struct expand
<
BoxOut, Point,
- StrategyLess, StrategyGreater,
box_tag, point_tag,
spherical_equatorial_tag, spherical_equatorial_tag
> : detail::expand::point_loop_on_spheroid
<
- StrategyLess, StrategyGreater, dimension<Point>::value
+ dimension<Point>::value
+ >
+{};
+
+template <typename BoxOut, typename Point>
+struct expand
+ <
+ BoxOut, Point,
+ box_tag, point_tag,
+ spherical_polar_tag, spherical_polar_tag
+ > : detail::expand::point_loop_on_spheroid
+ <
+ dimension<Point>::value,
+ false
>
{};
template
<
- typename BoxOut, typename Point,
- typename StrategyLess, typename StrategyGreater
+ typename BoxOut, typename Point
>
struct expand
<
BoxOut, Point,
- StrategyLess, StrategyGreater,
box_tag, point_tag,
geographic_tag, geographic_tag
> : detail::expand::point_loop_on_spheroid
<
- StrategyLess, StrategyGreater, dimension<Point>::value
+ dimension<Point>::value
>
{};
diff --git a/boost/geometry/algorithms/detail/expand/segment.hpp b/boost/geometry/algorithms/detail/expand/segment.hpp
index 0570e944d4..dddd3d2c7a 100644
--- a/boost/geometry/algorithms/detail/expand/segment.hpp
+++ b/boost/geometry/algorithms/detail/expand/segment.hpp
@@ -5,11 +5,12 @@
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
// Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France.
-// This file was modified by Oracle on 2015, 2016.
-// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.
+// This file was modified by Oracle on 2015, 2016, 2017.
+// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -77,48 +78,57 @@ namespace dispatch
template
<
typename Box, typename Segment,
- typename StrategyLess, typename StrategyGreater,
typename CSTagOut, typename CSTag
>
struct expand
<
Box, Segment,
- StrategyLess, StrategyGreater,
box_tag, segment_tag,
CSTagOut, CSTag
- > : detail::expand::expand_indexed
- <
- 0, dimension<Segment>::value, StrategyLess, StrategyGreater
- >
+ >
{
- BOOST_MPL_ASSERT_MSG((boost::is_same<CSTagOut, CSTag>::value),
- COORDINATE_SYSTEMS_MUST_BE_THE_SAME,
+ BOOST_MPL_ASSERT_MSG((false),
+ NOT_IMPLEMENTED_FOR_THESE_COORDINATE_SYSTEMS,
(types<CSTagOut, CSTag>()));
};
template
<
- typename Box, typename Segment,
- typename StrategyLess, typename StrategyGreater
+ typename Box, typename Segment
>
struct expand
<
Box, Segment,
- StrategyLess, StrategyGreater,
+ box_tag, segment_tag,
+ cartesian_tag, cartesian_tag
+ > : detail::expand::expand_indexed
+ <
+ 0, dimension<Segment>::value
+ >
+{};
+
+template <typename Box, typename Segment>
+struct expand
+ <
+ Box, Segment,
+ box_tag, segment_tag,
+ spherical_polar_tag, spherical_polar_tag
+ > : detail::expand::segment
+{};
+
+template <typename Box, typename Segment>
+struct expand
+ <
+ Box, Segment,
box_tag, segment_tag,
spherical_equatorial_tag, spherical_equatorial_tag
> : detail::expand::segment
{};
-template
-<
- typename Box, typename Segment,
- typename StrategyLess, typename StrategyGreater
->
+template <typename Box, typename Segment>
struct expand
<
Box, Segment,
- StrategyLess, StrategyGreater,
box_tag, segment_tag,
geographic_tag, geographic_tag
> : detail::expand::segment
diff --git a/boost/geometry/algorithms/detail/has_self_intersections.hpp b/boost/geometry/algorithms/detail/has_self_intersections.hpp
index c34bb217a6..1289d946a5 100644
--- a/boost/geometry/algorithms/detail/has_self_intersections.hpp
+++ b/boost/geometry/algorithms/detail/has_self_intersections.hpp
@@ -81,7 +81,11 @@ inline bool has_self_intersections(Geometry const& geometry,
std::deque<turn_info> turns;
detail::disjoint::disjoint_interrupt_policy policy;
- detail::self_get_turn_points::self_turns<false, detail::overlay::assign_null_policy>(geometry, strategy, robust_policy, turns, policy);
+ detail::self_get_turn_points::self_turns
+ <
+ false,
+ detail::overlay::assign_null_policy
+ >(geometry, strategy, robust_policy, turns, policy, 0, false);
#ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
bool first = true;
diff --git a/boost/geometry/algorithms/detail/intersection/multi.hpp b/boost/geometry/algorithms/detail/intersection/multi.hpp
index 88b49b0167..92ce89bb2d 100644
--- a/boost/geometry/algorithms/detail/intersection/multi.hpp
+++ b/boost/geometry/algorithms/detail/intersection/multi.hpp
@@ -237,7 +237,7 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
multi_linestring_tag, multi_linestring_tag, point_tag,
- false, false, false
+ linear_tag, linear_tag, pointlike_tag
> : detail::intersection::intersection_multi_linestring_multi_linestring_point
<
GeometryOut
@@ -259,7 +259,7 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
linestring_tag, multi_linestring_tag, point_tag,
- false, false, false
+ linear_tag, linear_tag, pointlike_tag
> : detail::intersection::intersection_linestring_multi_linestring_point
<
GeometryOut
@@ -281,7 +281,7 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
multi_linestring_tag, box_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
> : detail::intersection::clip_multi_linestring
<
GeometryOut
@@ -303,7 +303,7 @@ struct intersection_insert
OverlayType,
ReverseLinestring, ReverseMultiPolygon, ReverseOut,
linestring_tag, multi_polygon_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
> : detail::intersection::intersection_of_linestring_with_areal
<
ReverseMultiPolygon,
@@ -329,7 +329,7 @@ struct intersection_insert
OverlayType,
ReversePolygon, ReverseMultiLinestring, ReverseOut,
polygon_tag, multi_linestring_tag, linestring_tag,
- true, false, false
+ areal_tag, linear_tag, linear_tag
> : detail::intersection::intersection_of_areal_with_multi_linestring
<
ReversePolygon,
@@ -353,7 +353,7 @@ struct intersection_insert
OverlayType,
ReverseMultiLinestring, ReverseRing, ReverseOut,
multi_linestring_tag, ring_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
> : detail::intersection::intersection_of_multi_linestring_with_areal
<
ReverseRing,
@@ -376,7 +376,7 @@ struct intersection_insert
OverlayType,
ReverseMultiLinestring, ReverseRing, ReverseOut,
multi_linestring_tag, polygon_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
> : detail::intersection::intersection_of_multi_linestring_with_areal
<
ReverseRing,
@@ -401,7 +401,7 @@ struct intersection_insert
OverlayType,
ReverseMultiLinestring, ReverseMultiPolygon, ReverseOut,
multi_linestring_tag, multi_polygon_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
> : detail::intersection::intersection_of_multi_linestring_with_areal
<
ReverseMultiPolygon,
diff --git a/boost/geometry/algorithms/detail/intersects/implementation.hpp b/boost/geometry/algorithms/detail/intersects/implementation.hpp
index 2379168e83..f9b5402d0c 100644
--- a/boost/geometry/algorithms/detail/intersects/implementation.hpp
+++ b/boost/geometry/algorithms/detail/intersects/implementation.hpp
@@ -72,10 +72,11 @@ struct self_intersects
rescale_policy_type robust_policy;
detail::disjoint::disjoint_interrupt_policy policy;
+ // TODO: skip_adjacent should be set to false
detail::self_get_turn_points::get_turns
<
false, turn_policy
- >::apply(geometry, strategy, robust_policy, turns, policy, 0);
+ >::apply(geometry, strategy, robust_policy, turns, policy, 0, true);
return policy.has_intersections;
}
};
diff --git a/boost/geometry/algorithms/detail/is_simple/linear.hpp b/boost/geometry/algorithms/detail/is_simple/linear.hpp
index 5acf56c5b1..e36049a961 100644
--- a/boost/geometry/algorithms/detail/is_simple/linear.hpp
+++ b/boost/geometry/algorithms/detail/is_simple/linear.hpp
@@ -217,6 +217,7 @@ inline bool has_self_intersections(Linear const& linear, Strategy const& strateg
is_acceptable_turn<Linear>
> interrupt_policy(predicate);
+ // TODO: skip_adjacent should be set to false
detail::self_get_turn_points::get_turns
<
false, turn_policy
@@ -224,7 +225,7 @@ inline bool has_self_intersections(Linear const& linear, Strategy const& strateg
strategy,
detail::no_rescale_policy(),
turns,
- interrupt_policy, 0);
+ interrupt_policy, 0, true);
detail::is_valid::debug_print_turns(turns.begin(), turns.end());
debug_print_boundary_points(linear);
diff --git a/boost/geometry/algorithms/detail/normalize.hpp b/boost/geometry/algorithms/detail/normalize.hpp
index 913fe324b7..7a761d42bb 100644
--- a/boost/geometry/algorithms/detail/normalize.hpp
+++ b/boost/geometry/algorithms/detail/normalize.hpp
@@ -1,8 +1,9 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Copyright (c) 2015, Oracle and/or its affiliates.
+// Copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Licensed under the Boost Software License version 1.0.
// http://www.boost.org/users/license.html
@@ -120,7 +121,7 @@ struct assign_loop<1, DimensionCount>
};
-template <typename PointIn, typename PointOut>
+template <typename PointIn, typename PointOut, bool IsEquatorial = true>
struct normalize_point
{
static inline void apply(PointIn const& point_in, PointOut& point_out)
@@ -133,6 +134,7 @@ struct normalize_point
math::normalize_spheroidal_coordinates
<
typename coordinate_system<PointIn>::type::units,
+ IsEquatorial,
in_coordinate_type
>(longitude, latitude);
@@ -144,7 +146,7 @@ struct normalize_point
};
-template <typename BoxIn, typename BoxOut>
+template <typename BoxIn, typename BoxOut, bool IsEquatorial = true>
class normalize_box
{
template <typename UnitsIn, typename UnitsOut, typename CoordinateInType>
@@ -193,6 +195,7 @@ public:
math::normalize_spheroidal_box_coordinates
<
typename coordinate_system<BoxIn>::type::units,
+ IsEquatorial,
in_coordinate_type
>(lon_min, lat_min, lon_max, lat_max);
@@ -237,6 +240,15 @@ struct normalize
template <typename PointIn, typename PointOut>
struct normalize
<
+ PointIn, PointOut, point_tag, point_tag,
+ spherical_polar_tag, spherical_polar_tag
+ > : detail::normalization::normalize_point<PointIn, PointOut, false>
+{};
+
+
+template <typename PointIn, typename PointOut>
+struct normalize
+ <
PointIn, PointOut, point_tag, point_tag, geographic_tag, geographic_tag
> : detail::normalization::normalize_point<PointIn, PointOut>
{};
@@ -254,6 +266,15 @@ struct normalize
template <typename BoxIn, typename BoxOut>
struct normalize
<
+ BoxIn, BoxOut, box_tag, box_tag,
+ spherical_polar_tag, spherical_polar_tag
+ > : detail::normalization::normalize_box<BoxIn, BoxOut, false>
+{};
+
+
+template <typename BoxIn, typename BoxOut>
+struct normalize
+ <
BoxIn, BoxOut, box_tag, box_tag, geographic_tag, geographic_tag
> : detail::normalization::normalize_box<BoxIn, BoxOut>
{};
diff --git a/boost/geometry/algorithms/detail/overlay/add_rings.hpp b/boost/geometry/algorithms/detail/overlay/add_rings.hpp
index fcb240941f..f64eb0b069 100644
--- a/boost/geometry/algorithms/detail/overlay/add_rings.hpp
+++ b/boost/geometry/algorithms/detail/overlay/add_rings.hpp
@@ -62,6 +62,13 @@ inline void convert_and_add(GeometryOut& result,
}
}
+enum add_rings_error_handling
+{
+ add_rings_ignore_unordered,
+ add_rings_add_unordered,
+ add_rings_throw_if_reversed
+};
+
template
<
typename GeometryOut,
@@ -69,16 +76,18 @@ template
typename Geometry1,
typename Geometry2,
typename RingCollection,
- typename OutputIterator
+ typename OutputIterator,
+ typename AreaStrategy
>
inline OutputIterator add_rings(SelectionMap const& map,
Geometry1 const& geometry1, Geometry2 const& geometry2,
RingCollection const& collection,
- OutputIterator out)
+ OutputIterator out,
+ AreaStrategy const& area_strategy,
+ add_rings_error_handling error_handling = add_rings_ignore_unordered)
{
typedef typename SelectionMap::const_iterator iterator;
- typedef typename SelectionMap::mapped_type property_type;
- typedef typename property_type::area_type area_type;
+ typedef typename AreaStrategy::return_type area_type;
area_type const zero = 0;
std::size_t const min_num_points = core_detail::closure::minimum_ring_size
@@ -122,10 +131,22 @@ inline OutputIterator add_rings(SelectionMap const& map,
// Only add rings if they satisfy minimal requirements.
// This cannot be done earlier (during traversal), not
// everything is figured out yet (sum of positive/negative rings)
- if (geometry::num_points(result) >= min_num_points
- && math::larger(geometry::area(result), zero))
+ if (geometry::num_points(result) >= min_num_points)
{
- *out++ = result;
+ area_type const area = geometry::area(result, area_strategy);
+ // Ignore if area is 0
+ if (! math::equals(area, zero))
+ {
+ if (error_handling == add_rings_add_unordered
+ || area > zero)
+ {
+ *out++ = result;
+ }
+ else if (error_handling == add_rings_throw_if_reversed)
+ {
+ BOOST_THROW_EXCEPTION(invalid_output_exception());
+ }
+ }
}
}
}
@@ -139,15 +160,17 @@ template
typename SelectionMap,
typename Geometry,
typename RingCollection,
- typename OutputIterator
+ typename OutputIterator,
+ typename AreaStrategy
>
inline OutputIterator add_rings(SelectionMap const& map,
Geometry const& geometry,
RingCollection const& collection,
- OutputIterator out)
+ OutputIterator out,
+ AreaStrategy const& area_strategy)
{
Geometry empty;
- return add_rings<GeometryOut>(map, geometry, empty, collection, out);
+ return add_rings<GeometryOut>(map, geometry, empty, collection, out, area_strategy);
}
diff --git a/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp b/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp
index 106ecaad07..3f2aea1b1d 100644
--- a/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp
+++ b/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp
@@ -25,7 +25,7 @@ struct ring_with_direction
ring_identifier ring_id;
direction_type direction;
- std::size_t turn_index;
+ signed_size_type turn_index;
int operation_index;
operation_type operation;
signed_size_type region_id;
@@ -50,8 +50,12 @@ struct ring_with_direction
struct rank_with_rings
{
+ // Define a set having a ring, with its direction (from/to). Each ring
+ // arrive at / leaves a cluster only once. TODO: this is not true for
+ // invalid ring. The rank needs to be considered too.
+ typedef std::set<ring_with_direction> container_type;
std::size_t rank;
- std::set<ring_with_direction> rings;
+ container_type rings;
rank_with_rings()
: rank(0)
@@ -60,7 +64,7 @@ struct rank_with_rings
inline bool all_equal(direction_type dir_type) const
{
- for (std::set<ring_with_direction>::const_iterator it = rings.begin();
+ for (container_type::const_iterator it = rings.begin();
it != rings.end(); ++it)
{
if (it->direction != dir_type)
@@ -83,7 +87,7 @@ struct rank_with_rings
inline bool has_only(operation_type op) const
{
- for (std::set<ring_with_direction>::const_iterator it = rings.begin();
+ for (container_type::const_iterator it = rings.begin();
it != rings.end(); ++it)
{
const ring_with_direction& rwd = *it;
@@ -100,7 +104,7 @@ struct rank_with_rings
{
bool has1 = false;
bool has2 = false;
- for (std::set<ring_with_direction>::const_iterator it = rings.begin();
+ for (container_type::const_iterator it = rings.begin();
it != rings.end(); ++it)
{
const ring_with_direction& rwd = *it;
@@ -114,7 +118,7 @@ struct rank_with_rings
inline bool is_isolated() const
{
- for (std::set<ring_with_direction>::const_iterator it = rings.begin();
+ for (container_type::const_iterator it = rings.begin();
it != rings.end(); ++it)
{
const ring_with_direction& rwd = *it;
@@ -128,8 +132,8 @@ struct rank_with_rings
inline bool has_unique_region_id() const
{
- int region_id = -1;
- for (std::set<ring_with_direction>::const_iterator it = rings.begin();
+ signed_size_type region_id = -1;
+ for (container_type::const_iterator it = rings.begin();
it != rings.end(); ++it)
{
const ring_with_direction& rwd = *it;
@@ -145,10 +149,10 @@ struct rank_with_rings
return true;
}
- inline int region_id() const
+ inline signed_size_type region_id() const
{
- int region_id = -1;
- for (std::set<ring_with_direction>::const_iterator it = rings.begin();
+ signed_size_type region_id = -1;
+ for (container_type::const_iterator it = rings.begin();
it != rings.end(); ++it)
{
const ring_with_direction& rwd = *it;
@@ -170,7 +174,7 @@ struct rank_with_rings
typedef typename boost::range_value<Turns>::type turn_type;
typedef typename turn_type::turn_operation_type turn_operation_type;
- for (std::set<ring_with_direction>::const_iterator it = rings.begin();
+ for (container_type::const_iterator it = rings.begin();
it != rings.end(); ++it)
{
const ring_with_direction& rwd = *it;
diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
index 78160f5204..c8ce651007 100644
--- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
+++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
@@ -224,7 +224,8 @@ inline void assign_parents(Geometry1 const& geometry1,
RingCollection const& collection,
RingMap& ring_map,
Strategy const& strategy,
- bool check_for_orientation = false)
+ bool check_for_orientation = false,
+ bool discard_double_negative = false)
{
typedef typename geometry::tag<Geometry1>::type tag1;
typedef typename geometry::tag<Geometry2>::type tag2;
@@ -334,28 +335,38 @@ inline void assign_parents(Geometry1 const& geometry1,
for (map_iterator_type it = boost::begin(ring_map);
it != boost::end(ring_map); ++it)
{
- if (geometry::math::equals(it->second.get_area(), 0))
+ ring_info_type& info = it->second;
+ if (geometry::math::equals(info.get_area(), 0))
{
- it->second.discarded = true;
+ info.discarded = true;
}
- else if (it->second.parent.source_index >= 0
- && math::larger(it->second.get_area(), 0))
+ else if (info.parent.source_index >= 0)
{
- const ring_info_type& parent = ring_map[it->second.parent];
+ const ring_info_type& parent = ring_map[info.parent];
+ bool const pos = math::larger(info.get_area(), 0);
+ bool const parent_pos = math::larger(parent.area, 0);
- if (math::larger(parent.area, 0))
+ bool const double_neg = discard_double_negative && ! pos && ! parent_pos;
+
+ if ((pos && parent_pos) || double_neg)
{
// Discard positive inner ring with positive parent
- it->second.discarded = true;
+ // Also, for some cases (dissolve), negative inner ring
+ // with negative parent shouild be discarded
+ info.discarded = true;
+ }
+
+ if (pos || info.discarded)
+ {
+ // Remove parent ID from any positive or discarded inner rings
+ info.parent.source_index = -1;
}
- // Remove parent ID from any positive inner ring
- it->second.parent.source_index = -1;
}
- else if (it->second.parent.source_index < 0
- && math::smaller(it->second.get_area(), 0))
+ else if (info.parent.source_index < 0
+ && math::smaller(info.get_area(), 0))
{
// Reverse negative ring without parent
- it->second.reversed = true;
+ info.reversed = true;
}
}
}
@@ -372,7 +383,7 @@ inline void assign_parents(Geometry1 const& geometry1,
}
-// Version for one geometry (called by buffer)
+// Version for one geometry (called by buffer/dissolve)
template
<
typename Geometry,
@@ -384,13 +395,15 @@ inline void assign_parents(Geometry const& geometry,
RingCollection const& collection,
RingMap& ring_map,
Strategy const& strategy,
- bool check_for_orientation)
+ bool check_for_orientation,
+ bool discard_double_negative)
{
// Call it with an empty geometry as second geometry (source_id == 1)
// (ring_map should be empty for source_id==1)
Geometry empty;
- assign_parents(geometry, empty, collection, ring_map, strategy, check_for_orientation);
+ assign_parents(geometry, empty, collection, ring_map, strategy,
+ check_for_orientation, discard_double_negative);
}
diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
index 47225328df..e25445651a 100644
--- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
+++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
@@ -118,7 +118,7 @@ inline void enrich_assign(Operations& operations, Turns& turns)
// Cluster behaviour: next should point after cluster, unless
// their seg_ids are not the same
- while (turn.cluster_id != -1
+ while (turn.is_clustered()
&& it->turn_index != next->turn_index
&& turn.cluster_id == turns[next->turn_index].cluster_id
&& op.seg_id == turns[next->turn_index].operations[next->operation_index].seg_id)
@@ -245,10 +245,6 @@ inline void calculate_remaining_distance(Turns& turns)
++it)
{
turn_type& turn = *it;
- if (! turn.both(detail::overlay::operation_continue))
- {
- continue;
- }
op_type& op0 = turn.operations[0];
op_type& op1 = turn.operations[1];
@@ -261,7 +257,7 @@ inline void calculate_remaining_distance(Turns& turns)
int const to_index0 = op0.enriched.get_next_turn_index();
int const to_index1 = op1.enriched.get_next_turn_index();
- if (to_index1 >= 0
+ if (to_index0 >= 0
&& to_index1 >= 0
&& to_index0 != to_index1)
{
@@ -359,12 +355,11 @@ inline void enrich_intersection_points(Turns& turns,
}
if (detail::overlay::is_self_turn<OverlayType>(turn)
- && turn.cluster_id < 0
+ && ! turn.is_clustered()
&& ! turn.both(target_operation))
{
// Only keep self-uu-turns or self-ii-turns
turn.discarded = true;
- turn.cluster_id = -1;
continue;
}
@@ -379,12 +374,12 @@ inline void enrich_intersection_points(Turns& turns,
<
OverlayType,
target_operation
- >::apply(turns, geometry1, geometry2);
+ >::apply(turns, clusters, geometry1, geometry2);
detail::overlay::discard_open_turns
<
OverlayType,
target_operation
- >::apply(turns, geometry1, geometry2);
+ >::apply(turns, clusters, geometry1, geometry2);
// Create a map of vectors of indexed operation-types to be able
// to sort intersection points PER RING
@@ -421,6 +416,9 @@ inline void enrich_intersection_points(Turns& turns,
detail::overlay::enrich_assign(mit->second, turns);
}
+ // Check some specific type of self-turns (after getting enriched info)
+ detail::overlay::discard_self_turns_which_loop<OverlayType>(turns);
+
if (has_colocations)
{
// First gather cluster properties (using even clusters with
diff --git a/boost/geometry/algorithms/detail/overlay/follow.hpp b/boost/geometry/algorithms/detail/overlay/follow.hpp
index 589e12cc2b..4a5993ea31 100644
--- a/boost/geometry/algorithms/detail/overlay/follow.hpp
+++ b/boost/geometry/algorithms/detail/overlay/follow.hpp
@@ -26,6 +26,7 @@
#include <boost/geometry/algorithms/covered_by.hpp>
#include <boost/geometry/algorithms/clear.hpp>
+#include <boost/geometry/algorithms/detail/relate/turns.hpp>
namespace boost { namespace geometry
@@ -343,6 +344,7 @@ template
class follow
{
+#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
template <typename Turn>
struct sort_on_segment
{
@@ -389,7 +391,7 @@ class follow
}
};
-
+#endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
public :
@@ -433,7 +435,15 @@ public :
// Sort intersection points on segments-along-linestring, and distance
// (like in enrich is done for poly/poly)
+ // sort turns by Linear seg_id, then by fraction, then
+ // for same ring id: x, u, i, c
+ // for different ring id: c, i, u, x
+#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
+#else
+ typedef relate::turns::less<0, relate::turns::less_op_linear_areal_single<0> > turn_less;
+ std::sort(boost::begin(turns), boost::end(turns), turn_less());
+#endif
LineStringOut current_piece;
geometry::segment_identifier current_segment_id(0, -1, -1, -1);
diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp
index f88dfe8422..fd1e49ca24 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp
@@ -144,7 +144,7 @@ class get_turns_in_sections
template <typename Geometry, typename Section>
- static inline bool neighbouring(Section const& section,
+ static inline bool adjacent(Section const& section,
signed_size_type index1, signed_size_type index2)
{
// About n-2:
@@ -152,7 +152,7 @@ class get_turns_in_sections
// -> 0-3 are adjacent, don't check on intersections)
// Also tested for open polygons, and/or duplicates
// About first condition: will be optimized by compiler (static)
- // It checks if it is areal (box,ring,(multi)polygon
+ // It checks if it is areal (box, ring, (multi)polygon)
signed_size_type const n = static_cast<signed_size_type>(section.range_count);
boost::ignore_unused_variable_warning(n);
@@ -180,7 +180,7 @@ public :
static inline bool apply(
int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
- bool skip_larger,
+ bool skip_larger, bool skip_adjacent,
IntersectionStrategy const& intersection_strategy,
RobustPolicy const& robust_policy,
Turns& turns,
@@ -214,11 +214,6 @@ public :
signed_size_type index1 = sec1.begin_index;
signed_size_type ndi1 = sec1.non_duplicate_index;
- bool const same_source =
- source_id1 == source_id2
- && sec1.ring_id.multi_index == sec2.ring_id.multi_index
- && sec1.ring_id.ring_index == sec2.ring_id.ring_index;
-
range1_iterator prev1, it1, end1;
get_start_point_iterator(sec1, view1, prev1, it1, end1,
@@ -254,22 +249,32 @@ public :
it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec2.bounding_box, sec1.bounding_box, robust_policy);
++prev2, ++it2, ++index2, ++next2, ++ndi2)
{
- bool skip = same_source;
- if (skip)
+ bool skip = false;
+
+ if (source_id1 == source_id2
+ && sec1.ring_id.multi_index == sec2.ring_id.multi_index
+ && sec1.ring_id.ring_index == sec2.ring_id.ring_index)
{
- // If sources are the same (possibly self-intersecting):
- // skip if it is a neighbouring segment.
- // (including first-last segment
- // and two segments with one or more degenerate/duplicate
- // (zero-length) segments in between)
-
- // Also skip if index1 < index2 to avoid getting all
- // intersections twice (only do this on same source!)
-
- skip = (skip_larger && index1 >= index2)
- || ndi2 == ndi1 + 1
- || neighbouring<Geometry1>(sec1, index1, index2)
- ;
+ // Sources and rings are the same
+
+ if (skip_larger && index1 >= index2)
+ {
+ // Skip to avoid getting all intersections twice
+ skip = true;
+ }
+ else if (skip_adjacent)
+ {
+ // In some cases (dissolve, has_self_intersections)
+ // neighbouring segments should be checked
+ // (for example to detect spikes properly)
+
+ // skip if it is a neighbouring segment.
+ // (including, for areas, first-last segment
+ // and two segments with one or more degenerate/duplicate
+ // (zero-length) segments in between)
+ skip = ndi2 == ndi1 + 1
+ || adjacent<Geometry1>(sec1, index1, index2);
+ }
}
if (! skip)
@@ -431,7 +436,7 @@ struct section_visitor
TurnPolicy
>::apply(m_source_id1, m_geometry1, sec1,
m_source_id2, m_geometry2, sec2,
- false,
+ false, false,
m_intersection_strategy,
m_rescale_policy,
m_turns, m_interrupt_policy);
diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
index f3311b34e9..c634fc450f 100644
--- a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
+++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
@@ -24,6 +24,7 @@
#include <boost/geometry/core/point_order.hpp>
#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
+#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
@@ -181,6 +182,7 @@ inline signed_size_type add_turn_to_cluster(Turn const& turn,
if (cid0 == -1 && cid1 == -1)
{
+ // Because of this, first cluster ID will be 1
++cluster_id;
add_cluster_id(turn.operations[0], cluster_per_segment, cluster_id);
add_cluster_id(turn.operations[1], cluster_per_segment, cluster_id);
@@ -314,7 +316,7 @@ inline void assign_cluster_to_turns(Turns& turns,
if (it != cluster_per_segment.end())
{
#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
- if (turn.cluster_id != -1
+ if (turn.is_clustered()
&& turn.cluster_id != it->second)
{
std::cout << " CONFLICT " << std::endl;
@@ -503,6 +505,7 @@ inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
template
<
+ overlay_type OverlayType,
typename Turns,
typename Clusters
>
@@ -517,38 +520,65 @@ inline void set_colocation(Turns& turns, Clusters const& clusters)
cluster_info const& cinfo = cit->second;
std::set<signed_size_type> const& ids = cinfo.turn_indices;
- bool has_ii = false;
- bool has_uu = false;
+ bool both_target = false;
for (set_iterator it = ids.begin(); it != ids.end(); ++it)
{
turn_type const& turn = turns[*it];
- if (turn.both(operation_intersection))
- {
- has_ii = true;
- }
- if (turn.both(operation_union) || turn.combination(operation_union, operation_blocked))
+ if (turn.both(operation_from_overlay<OverlayType>::value))
{
- has_uu = true;
+ both_target = true;
+ break;
}
}
- if (has_ii || has_uu)
+
+ if (both_target)
{
for (set_iterator it = ids.begin(); it != ids.end(); ++it)
{
turn_type& turn = turns[*it];
- if (has_ii)
- {
- turn.colocated_ii = true;
- }
- if (has_uu)
+
+ if (both_target)
{
- turn.colocated_uu = true;
+ turn.has_colocated_both = true;
}
}
}
}
}
+template
+<
+ typename Turns,
+ typename Clusters
+>
+inline void check_colocation(bool& has_blocked,
+ int cluster_id, Turns const& turns, Clusters const& clusters)
+{
+ typedef typename boost::range_value<Turns>::type turn_type;
+
+ has_blocked = false;
+
+ typename Clusters::const_iterator mit = clusters.find(cluster_id);
+ if (mit == clusters.end())
+ {
+ return;
+ }
+
+ cluster_info const& cinfo = mit->second;
+
+ for (std::set<signed_size_type>::const_iterator it
+ = cinfo.turn_indices.begin();
+ it != cinfo.turn_indices.end(); ++it)
+ {
+ turn_type const& turn = turns[*it];
+ if (turn.any_blocked())
+ {
+ has_blocked = true;
+ }
+ }
+}
+
+
// Checks colocated turns and flags combinations of uu/other, possibly a
// combination of a ring touching another geometry's interior ring which is
// tangential to the exterior ring
@@ -627,6 +657,10 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters,
> cluster_per_segment_type;
cluster_per_segment_type cluster_per_segment;
+
+ // Assign to zero, because of pre-increment later the cluster_id
+ // effectively starts with 1
+ // (and can later be negated to use uniquely with turn_index)
signed_size_type cluster_id = 0;
for (typename map_type::const_iterator it = map.begin();
@@ -640,7 +674,9 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters,
}
assign_cluster_to_turns(turns, clusters, cluster_per_segment);
- set_colocation(turns, clusters);
+ // Get colocated information here and not later, to keep information
+ // on turns which are discarded afterwards
+ set_colocation<OverlayType>(turns, clusters);
discard_interior_exterior_turns
<
do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1,
@@ -758,14 +794,21 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
cinfo.open_count = sbs.open_count(for_operation);
- // Unset the startable flag for all 'closed' zones
+ bool const set_startable
+ = OverlayType != overlay_dissolve_union
+ && OverlayType != overlay_dissolve_intersection;
+
+ // Unset the startable flag for all 'closed' zones. This does not
+ // apply for self-turns, because those counts are not from both
+ // polygons
for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
{
const typename sbs_type::rp& ranked = sbs.m_ranked_points[i];
turn_type& turn = turns[ranked.turn_index];
turn_operation_type& op = turn.operations[ranked.operation_index];
- if (for_operation == operation_union && cinfo.open_count == 0)
+ if (set_startable
+ && for_operation == operation_union && cinfo.open_count == 0)
{
op.enriched.startable = false;
}
@@ -780,6 +823,18 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
op.enriched.rank = ranked.rank;
op.enriched.zone = ranked.zone;
+ if (! set_startable)
+ {
+ continue;
+ }
+
+ if (OverlayType != overlay_difference
+ && is_self_turn<OverlayType>(turn))
+ {
+ // Difference needs the self-turns, TODO: investigate
+ continue;
+ }
+
if ((for_operation == operation_union
&& ranked.count_left != 0)
|| (for_operation == operation_intersection
diff --git a/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp b/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp
index 39c55db759..9c4a3094e0 100644
--- a/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp
+++ b/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp
@@ -11,6 +11,7 @@
#include <boost/range.hpp>
+#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
#include <boost/geometry/algorithms/within.hpp>
@@ -24,9 +25,9 @@ namespace detail { namespace overlay
struct discard_turns
{
- template <typename Turns, typename Geometry0, typename Geometry1>
+ template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1>
static inline
- void apply(Turns& , Geometry0 const& , Geometry1 const& )
+ void apply(Turns& , Clusters const& , Geometry0 const& , Geometry1 const& )
{}
};
@@ -38,9 +39,9 @@ template <>
struct discard_closed_turns<overlay_union, operation_union>
{
- template <typename Turns, typename Geometry0, typename Geometry1>
+ template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1>
static inline
- void apply(Turns& turns,
+ void apply(Turns& turns, Clusters const& clusters,
Geometry0 const& geometry0, Geometry1 const& geometry1)
{
typedef typename boost::range_value<Turns>::type turn_type;
@@ -52,9 +53,7 @@ struct discard_closed_turns<overlay_union, operation_union>
{
turn_type& turn = *it;
- if (turn.cluster_id >= 0
- || turn.discarded
- || ! is_self_turn<overlay_union>(turn))
+ if (turn.discarded || ! is_self_turn<overlay_union>(turn))
{
continue;
}
@@ -75,11 +74,106 @@ struct discard_closed_turns<overlay_union, operation_union>
struct discard_self_intersection_turns
{
- template <typename Turns, typename Geometry0, typename Geometry1>
+private :
+
+ template <typename Turns, typename Clusters>
+ static inline
+ bool any_blocked(signed_size_type cluster_id,
+ const Turns& turns, Clusters const& clusters)
+ {
+ typename Clusters::const_iterator cit = clusters.find(cluster_id);
+ if (cit == clusters.end())
+ {
+ return false;
+ }
+ cluster_info const& cinfo = cit->second;
+ for (std::set<signed_size_type>::const_iterator it
+ = cinfo.turn_indices.begin();
+ it != cinfo.turn_indices.end(); ++it)
+ {
+ typename boost::range_value<Turns>::type const& turn = turns[*it];
+ if (turn.any_blocked())
+ {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ template <typename Turns, typename Clusters>
+ static inline
+ bool is_self_cluster(signed_size_type cluster_id,
+ const Turns& turns, Clusters const& clusters)
+ {
+ typename Clusters::const_iterator cit = clusters.find(cluster_id);
+ if (cit == clusters.end())
+ {
+ return false;
+ }
+
+ cluster_info const& cinfo = cit->second;
+ for (std::set<signed_size_type>::const_iterator it
+ = cinfo.turn_indices.begin();
+ it != cinfo.turn_indices.end(); ++it)
+ {
+ if (! is_self_turn<overlay_intersection>(turns[*it]))
+ {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ template <typename Turn, typename Geometry0, typename Geometry1>
+ static inline
+ bool within(Turn const& turn, Geometry0 const& geometry0,
+ Geometry1 const& geometry1)
+ {
+ return turn.operations[0].seg_id.source_index == 0
+ ? geometry::within(turn.point, geometry1)
+ : geometry::within(turn.point, geometry0);
+ }
+
+ template <typename Turns, typename Clusters,
+ typename Geometry0, typename Geometry1>
+ static inline
+ void discard_clusters(Turns& turns, Clusters const& clusters,
+ Geometry0 const& geometry0, Geometry1 const& geometry1)
+ {
+ for (typename Clusters::const_iterator cit = clusters.begin();
+ cit != clusters.end(); ++cit)
+ {
+ signed_size_type cluster_id = cit->first;
+
+ // If there are only self-turns in the cluster, the cluster should
+ // be located within the other geometry, for intersection
+ if (is_self_cluster(cluster_id, turns, clusters))
+ {
+ cluster_info const& cinfo = cit->second;
+ if (! within(turns[*cinfo.turn_indices.begin()], geometry0, geometry1))
+ {
+ // Discard all turns in cluster
+ for (std::set<signed_size_type>::const_iterator sit = cinfo.turn_indices.begin();
+ sit != cinfo.turn_indices.end(); ++sit)
+ {
+ turns[*sit].discarded = true;
+ }
+ }
+ }
+ }
+ }
+
+public :
+
+ template <typename Turns, typename Clusters,
+ typename Geometry0, typename Geometry1>
static inline
- void apply(Turns& turns,
+ void apply(Turns& turns, Clusters const& clusters,
Geometry0 const& geometry0, Geometry1 const& geometry1)
{
+ discard_clusters(turns, clusters, geometry0, geometry1);
+
typedef typename boost::range_value<Turns>::type turn_type;
for (typename boost::range_iterator<Turns>::type
@@ -89,9 +183,7 @@ struct discard_self_intersection_turns
{
turn_type& turn = *it;
- if (turn.cluster_id >= 0
- || turn.discarded
- || ! is_self_turn<overlay_intersection>(turn))
+ if (turn.discarded || ! is_self_turn<overlay_intersection>(turn))
{
continue;
}
@@ -106,16 +198,22 @@ struct discard_self_intersection_turns
continue;
}
- // It is a non co-located ii self-turn
+ if (turn.is_clustered() && turn.has_colocated_both)
+ {
+ // Don't delete a self-ii-turn colocated with another ii-turn
+ // (for example #case_recursive_boxes_70)
+ // But for some cases (#case_58_iet) they should be deleted,
+ // there are many self-turns there and also blocked turns there
+ if (! any_blocked(turn.cluster_id, turns, clusters))
+ {
+ continue;
+ }
+ }
+
+ // It is a ii self-turn
// Check if it is within the other geometry
// If not, it can be ignored
-
- bool const within =
- turn.operations[0].seg_id.source_index == 0
- ? geometry::within(turn.point, geometry1)
- : geometry::within(turn.point, geometry0);
-
- if (! within)
+ if (! within(turn, geometry0, geometry1))
{
// It is not within another geometry, discard the turn
turn.discarded = true;
@@ -134,6 +232,61 @@ struct discard_open_turns<overlay_intersection, operation_intersection>
// For difference, it should be done in a different way (TODO)
+
+template <overlay_type OverlayType, typename Turns>
+inline void discard_self_turns_which_loop(Turns& turns)
+{
+ if (operation_from_overlay<OverlayType>::value == operation_union)
+ {
+ // For union, self-turn i/u traveling to itself are allowed to form
+ // holes. #case_recursive_boxes_37
+ // TODO: this can be finetuned by inspecting the cluster too,
+ // and if there are non-self-turns the polygons on their sides can
+ // be checked
+ return;
+ }
+
+ typedef typename boost::range_value<Turns>::type turn_type;
+ typedef typename turn_type::turn_operation_type op_type;
+
+ signed_size_type turn_index = 0;
+ for (typename boost::range_iterator<Turns>::type
+ it = boost::begin(turns);
+ it != boost::end(turns);
+ ++it, ++turn_index)
+ {
+ turn_type& turn = *it;
+
+ if (! is_self_turn<OverlayType>(turn))
+ {
+ continue;
+ }
+ if (! turn.combination(operation_intersection, operation_union))
+ {
+ // ii may travel to itself
+ continue;
+ }
+
+ for (int i = 0; i < 2; i++)
+ {
+ op_type& op = turn.operations[i];
+
+ if (op.enriched.startable
+ && op.operation == operation_intersection
+ && op.enriched.get_next_turn_index() == turn_index)
+ {
+ // Self-turn i/u, i part traveling to itself. Discard it.
+ // (alternatively it might be made unstartable - but the
+ // intersection-operation may not be traveled anyway, and the
+ // union-operation is not traveled at all in intersections
+ // #case_recursive_boxes_77
+ turn.discarded = true;
+ }
+ }
+ }
+
+}
+
}} // namespace detail::overlay
#endif //DOXYGEN_NO_DETAIL
diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
index 7106e7b480..60255cd953 100644
--- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
+++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
@@ -208,6 +208,8 @@ struct intersection_of_linestring_with_areal
}
#endif
+#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
+
class is_crossing_turn
{
// return true is the operation is intersection or blocked
@@ -310,6 +312,91 @@ struct intersection_of_linestring_with_areal
return 0;
}
+#else // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
+
+ template <typename Linestring, typename Areal, typename Strategy, typename Turns>
+ static inline bool simple_turns_analysis(Linestring const& linestring,
+ Areal const& areal,
+ Strategy const& strategy,
+ Turns const& turns,
+ int & inside_value)
+ {
+ using namespace overlay;
+
+ bool found_continue = false;
+ bool found_intersection = false;
+ bool found_union = false;
+ bool found_front = false;
+
+ for (typename Turns::const_iterator it = turns.begin();
+ it != turns.end(); ++it)
+ {
+ method_type const method = it->method;
+ operation_type const op = it->operations[0].operation;
+
+ if (method == method_crosses)
+ {
+ return false;
+ }
+ else if (op == operation_intersection)
+ {
+ found_intersection = true;
+ }
+ else if (op == operation_union)
+ {
+ found_union = true;
+ }
+ else if (op == operation_continue)
+ {
+ found_continue = true;
+ }
+
+ if ((found_intersection || found_continue) && found_union)
+ {
+ return false;
+ }
+
+ if (it->operations[0].position == position_front)
+ {
+ found_front = true;
+ }
+ }
+
+ if (found_front)
+ {
+ if (found_intersection)
+ {
+ inside_value = 1; // inside
+ }
+ else if (found_union)
+ {
+ inside_value = -1; // outside
+ }
+ else // continue and blocked
+ {
+ inside_value = 0;
+ }
+ return true;
+ }
+
+ // if needed analyse points of a linestring
+ // NOTE: range_in_geometry checks points of a linestring
+ // until a point inside/outside areal is found
+ // TODO: Could be replaced with point_in_geometry() because found_front is false
+ inside_value = range_in_geometry(linestring, areal, strategy);
+
+ if ( (found_intersection && inside_value == -1) // going in from outside
+ || (found_continue && inside_value == -1) // going on boundary from outside
+ || (found_union && inside_value == 1) ) // going out from inside
+ {
+ return false;
+ }
+
+ return true;
+ }
+
+#endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
+
template
<
typename LineString, typename Areal,
@@ -336,14 +423,30 @@ struct intersection_of_linestring_with_areal
> follower;
typedef typename point_type<LineStringOut>::type point_type;
+#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
typedef detail::overlay::traversal_turn_info
- <
- point_type,
- typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
- > turn_info;
+ <
+ point_type,
+ typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
+ > turn_info;
+#else
+ typedef detail::overlay::turn_info
+ <
+ point_type,
+ typename geometry::segment_ratio_type<point_type, RobustPolicy>::type,
+ detail::overlay::turn_operation_linear
+ <
+ point_type,
+ typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
+ >
+ > turn_info;
+#endif
std::deque<turn_info> turns;
detail::get_turns::no_interrupt_policy policy;
+
+#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
+
geometry::get_turns
<
false,
@@ -366,7 +469,7 @@ struct intersection_of_linestring_with_areal
// until a point inside/outside areal is found
inside_value = overlay::range_in_geometry(linestring, areal, strategy);
}
- // add point to the output if conditions are met
+ // add linestring to the output if conditions are met
if (inside_value != 0 && follower::included(inside_value))
{
LineStringOut copy;
@@ -376,6 +479,47 @@ struct intersection_of_linestring_with_areal
return out;
}
+#else // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
+
+ typedef detail::overlay::get_turn_info_linear_areal
+ <
+ detail::overlay::assign_null_policy
+ > turn_policy;
+
+ dispatch::get_turns
+ <
+ typename geometry::tag<LineString>::type,
+ typename geometry::tag<Areal>::type,
+ LineString,
+ Areal,
+ false,
+ (OverlayType == overlay_intersection ? ReverseAreal : !ReverseAreal),
+ turn_policy
+ >::apply(0, linestring, 1, areal,
+ strategy, robust_policy,
+ turns, policy);
+
+ int inside_value = 0;
+ if (simple_turns_analysis(linestring, areal, strategy, turns, inside_value))
+ {
+ // No crossing the boundary, it is either
+ // inside (interior + borders)
+ // or outside (exterior + borders)
+ // or on boundary
+
+ // add linestring to the output if conditions are met
+ if (follower::included(inside_value))
+ {
+ LineStringOut copy;
+ geometry::convert(linestring, copy);
+ *out++ = copy;
+ }
+
+ return out;
+ }
+
+#endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
+
#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
int index = 0;
for(typename std::deque<turn_info>::const_iterator
@@ -395,6 +539,135 @@ struct intersection_of_linestring_with_areal
};
+template <typename Turns, typename OutputIterator>
+inline OutputIterator intersection_output_turn_points(Turns const& turns,
+ OutputIterator out)
+{
+ for (typename Turns::const_iterator
+ it = turns.begin(); it != turns.end(); ++it)
+ {
+ *out++ = it->point;
+ }
+
+ return out;
+}
+
+template <typename PointOut>
+struct intersection_areal_areal_point
+{
+ template
+ <
+ typename Geometry1, typename Geometry2,
+ typename RobustPolicy,
+ typename OutputIterator,
+ typename Strategy
+ >
+ static inline OutputIterator apply(Geometry1 const& geometry1,
+ Geometry2 const& geometry2,
+ RobustPolicy const& robust_policy,
+ OutputIterator out,
+ Strategy const& strategy)
+ {
+ typedef detail::overlay::turn_info
+ <
+ PointOut,
+ typename segment_ratio_type<PointOut, RobustPolicy>::type
+ > turn_info;
+ std::vector<turn_info> turns;
+
+ detail::get_turns::no_interrupt_policy policy;
+
+ geometry::get_turns
+ <
+ false, false, detail::overlay::assign_null_policy
+ >(geometry1, geometry2, strategy, robust_policy, turns, policy);
+
+ return intersection_output_turn_points(turns, out);
+ }
+};
+
+template <typename PointOut>
+struct intersection_linear_areal_point
+{
+ template
+ <
+ typename Geometry1, typename Geometry2,
+ typename RobustPolicy,
+ typename OutputIterator,
+ typename Strategy
+ >
+ static inline OutputIterator apply(Geometry1 const& geometry1,
+ Geometry2 const& geometry2,
+ RobustPolicy const& robust_policy,
+ OutputIterator out,
+ Strategy const& strategy)
+ {
+ typedef typename geometry::segment_ratio_type
+ <
+ PointOut, RobustPolicy
+ >::type segment_ratio_type;
+
+ typedef detail::overlay::turn_info
+ <
+ PointOut,
+ segment_ratio_type,
+ detail::overlay::turn_operation_linear
+ <
+ PointOut,
+ segment_ratio_type
+ >
+ > turn_info;
+
+ typedef detail::overlay::get_turn_info_linear_areal
+ <
+ detail::overlay::assign_null_policy
+ > turn_policy;
+
+ std::vector<turn_info> turns;
+
+ detail::get_turns::no_interrupt_policy interrupt_policy;
+
+ dispatch::get_turns
+ <
+ typename geometry::tag<Geometry1>::type,
+ typename geometry::tag<Geometry2>::type,
+ Geometry1,
+ Geometry2,
+ false,
+ false,
+ turn_policy
+ >::apply(0, geometry1, 1, geometry2,
+ strategy, robust_policy,
+ turns, interrupt_policy);
+
+ return intersection_output_turn_points(turns, out);
+ }
+};
+
+template <typename PointOut>
+struct intersection_areal_linear_point
+{
+ template
+ <
+ typename Geometry1, typename Geometry2,
+ typename RobustPolicy,
+ typename OutputIterator,
+ typename Strategy
+ >
+ static inline OutputIterator apply(Geometry1 const& geometry1,
+ Geometry2 const& geometry2,
+ RobustPolicy const& robust_policy,
+ OutputIterator out,
+ Strategy const& strategy)
+ {
+ return intersection_linear_areal_point
+ <
+ PointOut
+ >::apply(geometry2, geometry1, robust_policy, out, strategy);
+ }
+};
+
+
}} // namespace detail::intersection
#endif // DOXYGEN_NO_DETAIL
@@ -420,9 +693,9 @@ template
typename TagIn2 = typename geometry::tag<Geometry2>::type,
typename TagOut = typename geometry::tag<GeometryOut>::type,
// metafunction finetuning helpers:
- bool Areal1 = geometry::is_areal<Geometry1>::value,
- bool Areal2 = geometry::is_areal<Geometry2>::value,
- bool ArealOut = geometry::is_areal<GeometryOut>::value
+ typename CastedTagIn1 = typename geometry::tag_cast<TagIn1, areal_tag, linear_tag, pointlike_tag>::type,
+ typename CastedTagIn2 = typename geometry::tag_cast<TagIn2, areal_tag, linear_tag, pointlike_tag>::type,
+ typename CastedTagOut = typename geometry::tag_cast<TagOut, areal_tag, linear_tag, pointlike_tag>::type
>
struct intersection_insert
{
@@ -449,7 +722,7 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
TagIn1, TagIn2, TagOut,
- true, true, true
+ areal_tag, areal_tag, areal_tag
> : detail::overlay::overlay
<Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, GeometryOut, OverlayType>
{};
@@ -471,7 +744,7 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
TagIn, box_tag, TagOut,
- true, true, true
+ areal_tag, areal_tag, areal_tag
> : detail::overlay::overlay
<Geometry, Box, Reverse1, Reverse2, ReverseOut, GeometryOut, OverlayType>
{};
@@ -491,7 +764,7 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
segment_tag, segment_tag, point_tag,
- false, false, false
+ linear_tag, linear_tag, pointlike_tag
> : detail::intersection::intersection_segment_segment_point<GeometryOut>
{};
@@ -510,7 +783,7 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
linestring_tag, linestring_tag, point_tag,
- false, false, false
+ linear_tag, linear_tag, pointlike_tag
> : detail::intersection::intersection_linestring_linestring_point<GeometryOut>
{};
@@ -528,7 +801,7 @@ struct intersection_insert
overlay_intersection,
Reverse1, Reverse2, ReverseOut,
linestring_tag, box_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
>
{
template <typename RobustPolicy, typename OutputIterator, typename Strategy>
@@ -559,7 +832,7 @@ struct intersection_insert
OverlayType,
ReverseLinestring, ReversePolygon, ReverseOut,
linestring_tag, polygon_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
> : detail::intersection::intersection_of_linestring_with_areal
<
ReversePolygon,
@@ -583,7 +856,7 @@ struct intersection_insert
OverlayType,
ReverseLinestring, ReverseRing, ReverseOut,
linestring_tag, ring_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
> : detail::intersection::intersection_of_linestring_with_areal
<
ReverseRing,
@@ -606,7 +879,7 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
segment_tag, box_tag, linestring_tag,
- false, true, false
+ linear_tag, areal_tag, linear_tag
>
{
template <typename RobustPolicy, typename OutputIterator, typename Strategy>
@@ -630,8 +903,7 @@ template
typename PointOut,
overlay_type OverlayType,
bool Reverse1, bool Reverse2, bool ReverseOut,
- typename Tag1, typename Tag2,
- bool Areal1, bool Areal2
+ typename Tag1, typename Tag2
>
struct intersection_insert
<
@@ -640,38 +912,59 @@ struct intersection_insert
OverlayType,
Reverse1, Reverse2, ReverseOut,
Tag1, Tag2, point_tag,
- Areal1, Areal2, false
+ areal_tag, areal_tag, pointlike_tag
>
-{
- template <typename RobustPolicy, typename OutputIterator, typename Strategy>
- static inline OutputIterator apply(Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- RobustPolicy const& robust_policy,
- OutputIterator out, Strategy const& strategy)
- {
-
- typedef detail::overlay::turn_info
- <
- PointOut,
- typename segment_ratio_type<PointOut, RobustPolicy>::type
- > turn_info;
- std::vector<turn_info> turns;
-
- detail::get_turns::no_interrupt_policy policy;
- geometry::get_turns
- <
- false, false, detail::overlay::assign_null_policy
- >(geometry1, geometry2, strategy, robust_policy, turns, policy);
- for (typename std::vector<turn_info>::const_iterator it
- = turns.begin(); it != turns.end(); ++it)
- {
- *out++ = it->point;
- }
+ : public detail::intersection::intersection_areal_areal_point
+ <
+ PointOut
+ >
+{};
- return out;
- }
-};
+template
+<
+ typename Geometry1, typename Geometry2,
+ typename PointOut,
+ overlay_type OverlayType,
+ bool Reverse1, bool Reverse2, bool ReverseOut,
+ typename Tag1, typename Tag2
+>
+struct intersection_insert
+ <
+ Geometry1, Geometry2,
+ PointOut,
+ OverlayType,
+ Reverse1, Reverse2, ReverseOut,
+ Tag1, Tag2, point_tag,
+ linear_tag, areal_tag, pointlike_tag
+ >
+ : public detail::intersection::intersection_linear_areal_point
+ <
+ PointOut
+ >
+{};
+template
+<
+ typename Geometry1, typename Geometry2,
+ typename PointOut,
+ overlay_type OverlayType,
+ bool Reverse1, bool Reverse2, bool ReverseOut,
+ typename Tag1, typename Tag2
+>
+struct intersection_insert
+ <
+ Geometry1, Geometry2,
+ PointOut,
+ OverlayType,
+ Reverse1, Reverse2, ReverseOut,
+ Tag1, Tag2, point_tag,
+ areal_tag, linear_tag, pointlike_tag
+ >
+ : public detail::intersection::intersection_areal_linear_point
+ <
+ PointOut
+ >
+{};
template
<
@@ -713,7 +1006,7 @@ struct intersection_insert
overlay_intersection,
Reverse1, Reverse2, ReverseOut,
Tag1, Tag2, linestring_tag,
- true, true, false
+ areal_tag, areal_tag, linear_tag
>
{
template
@@ -739,47 +1032,20 @@ struct intersection_insert
}
};
-// dispatch for non-areal geometries
-template
-<
- typename Geometry1, typename Geometry2, typename GeometryOut,
- overlay_type OverlayType,
- bool Reverse1, bool Reverse2, bool ReverseOut,
- typename TagIn1, typename TagIn2
->
-struct intersection_insert
- <
- Geometry1, Geometry2, GeometryOut,
- OverlayType,
- Reverse1, Reverse2, ReverseOut,
- TagIn1, TagIn2, linestring_tag,
- false, false, false
- > : intersection_insert
- <
- Geometry1, Geometry2, GeometryOut,
- OverlayType,
- Reverse1, Reverse2, ReverseOut,
- typename tag_cast<TagIn1, pointlike_tag, linear_tag>::type,
- typename tag_cast<TagIn2, pointlike_tag, linear_tag>::type,
- linestring_tag,
- false, false, false
- >
-{};
-
-
// dispatch for difference/intersection of linear geometries
template
<
typename Linear1, typename Linear2, typename LineStringOut,
overlay_type OverlayType,
- bool Reverse1, bool Reverse2, bool ReverseOut
+ bool Reverse1, bool Reverse2, bool ReverseOut,
+ typename TagIn1, typename TagIn2
>
struct intersection_insert
<
Linear1, Linear2, LineStringOut, OverlayType,
Reverse1, Reverse2, ReverseOut,
- linear_tag, linear_tag, linestring_tag,
- false, false, false
+ TagIn1, TagIn2, linestring_tag,
+ linear_tag, linear_tag, linear_tag
> : detail::overlay::linear_linear_linestring
<
Linear1, Linear2, LineStringOut, OverlayType
@@ -800,7 +1066,7 @@ struct intersection_insert
Point1, Point2, PointOut, OverlayType,
Reverse1, Reverse2, ReverseOut,
point_tag, point_tag, point_tag,
- false, false, false
+ pointlike_tag, pointlike_tag, pointlike_tag
> : detail::overlay::point_point_point
<
Point1, Point2, PointOut, OverlayType
@@ -819,7 +1085,7 @@ struct intersection_insert
MultiPoint, Point, PointOut, OverlayType,
Reverse1, Reverse2, ReverseOut,
multi_point_tag, point_tag, point_tag,
- false, false, false
+ pointlike_tag, pointlike_tag, pointlike_tag
> : detail::overlay::multipoint_point_point
<
MultiPoint, Point, PointOut, OverlayType
@@ -838,7 +1104,7 @@ struct intersection_insert
Point, MultiPoint, PointOut, OverlayType,
Reverse1, Reverse2, ReverseOut,
point_tag, multi_point_tag, point_tag,
- false, false, false
+ pointlike_tag, pointlike_tag, pointlike_tag
> : detail::overlay::point_multipoint_point
<
Point, MultiPoint, PointOut, OverlayType
@@ -857,7 +1123,7 @@ struct intersection_insert
MultiPoint1, MultiPoint2, PointOut, OverlayType,
Reverse1, Reverse2, ReverseOut,
multi_point_tag, multi_point_tag, point_tag,
- false, false, false
+ pointlike_tag, pointlike_tag, pointlike_tag
> : detail::overlay::multipoint_multipoint_point
<
MultiPoint1, MultiPoint2, PointOut, OverlayType
@@ -878,7 +1144,7 @@ struct intersection_insert
Point, Linear, PointOut, OverlayType,
Reverse1, Reverse2, ReverseOut,
point_tag, Tag, point_tag,
- false, false, false
+ pointlike_tag, linear_tag, pointlike_tag
> : detail_dispatch::overlay::pointlike_linear_point
<
Point, Linear, PointOut, OverlayType,
@@ -899,7 +1165,7 @@ struct intersection_insert
MultiPoint, Linear, PointOut, OverlayType,
Reverse1, Reverse2, ReverseOut,
multi_point_tag, Tag, point_tag,
- false, false, false
+ pointlike_tag, linear_tag, pointlike_tag
> : detail_dispatch::overlay::pointlike_linear_point
<
MultiPoint, Linear, PointOut, OverlayType,
@@ -919,7 +1185,7 @@ struct intersection_insert
Linestring, MultiPoint, PointOut, overlay_intersection,
Reverse1, Reverse2, ReverseOut,
linestring_tag, multi_point_tag, point_tag,
- false, false, false
+ linear_tag, pointlike_tag, pointlike_tag
>
{
template <typename RobustPolicy, typename OutputIterator, typename Strategy>
diff --git a/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp b/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp
index 9cb7a0fca9..9423a24b33 100644
--- a/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp
+++ b/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp
@@ -41,7 +41,7 @@ struct is_self_turn_check<overlay_buffer>
};
template <>
-struct is_self_turn_check<overlay_dissolve>
+struct is_self_turn_check<overlay_dissolve_union>
{
template <typename Turn>
static inline bool apply(Turn const& turn)
@@ -50,6 +50,15 @@ struct is_self_turn_check<overlay_dissolve>
}
};
+template <>
+struct is_self_turn_check<overlay_dissolve_intersection>
+{
+ template <typename Turn>
+ static inline bool apply(Turn const& turn)
+ {
+ return false;
+ }
+};
template <overlay_type OverlayType, typename Turn>
bool is_self_turn(Turn const& turn)
diff --git a/boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp b/boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp
new file mode 100644
index 0000000000..87fdd00d58
--- /dev/null
+++ b/boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp
@@ -0,0 +1,83 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2017-2017 Barend Gehrels, 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_OVERLAY_NEEDS_SELF_TURNS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_NEEDS_SELF_TURNS_HPP
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/tags.hpp>
+#include <boost/geometry/algorithms/num_interior_rings.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+template
+<
+ typename Geometry,
+ typename Tag = typename tag<Geometry>::type
+>
+struct needs_self_turns
+{
+};
+
+template <typename Geometry>
+struct needs_self_turns<Geometry, box_tag>
+{
+ static inline bool apply(Geometry const&)
+ {
+ return false;
+ }
+};
+
+template <typename Geometry>
+struct needs_self_turns<Geometry, ring_tag>
+{
+ static inline bool apply(Geometry const&)
+ {
+ return false;
+ }
+};
+
+template <typename Geometry>
+struct needs_self_turns<Geometry, polygon_tag>
+{
+ static inline bool apply(Geometry const& polygon)
+ {
+ return geometry::num_interior_rings(polygon) > 0;
+ }
+};
+
+template <typename Geometry>
+struct needs_self_turns<Geometry, multi_polygon_tag>
+{
+ static inline bool apply(Geometry const& multi)
+ {
+ typedef typename boost::range_value<Geometry>::type polygon_type;
+ std::size_t const n = boost::size(multi);
+ return n > 1 || (n == 1
+ && needs_self_turns<polygon_type>
+ ::apply(*boost::begin(multi)));
+ }
+};
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_NEEDS_SELF_TURNS_HPP
diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp
index 10829abd4f..f24cde8b8f 100644
--- a/boost/geometry/algorithms/detail/overlay/overlay.hpp
+++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp
@@ -29,6 +29,7 @@
#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
+#include <boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
@@ -99,89 +100,88 @@ template
inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters)
{
typedef typename boost::range_value<Turns>::type turn_type;
+ typedef typename turn_type::turn_operation_type turn_operation_type;
typedef typename turn_type::container_type container_type;
static const operation_type target_operation
= operation_from_overlay<OverlayType>::value;
static const operation_type opposite_operation
- = target_operation == operation_union ? operation_intersection : operation_union;
+ = target_operation == operation_union
+ ? operation_intersection
+ : operation_union;
- signed_size_type turn_index = 0;
for (typename boost::range_iterator<Turns const>::type
it = boost::begin(turns);
it != boost::end(turns);
- ++it, turn_index++)
+ ++it)
{
- typename boost::range_value<Turns>::type const& turn = *it;
-
- bool const colocated_target = target_operation == operation_union
- ? turn.colocated_uu : turn.colocated_ii;
- bool const colocated_opp = target_operation == operation_union
- ? turn.colocated_ii : turn.colocated_uu;
- bool const both_opposite = turn.both(opposite_operation);
-
- bool const traversed
- = turn.operations[0].visited.finalized()
- || turn.operations[0].visited.rejected()
- || turn.operations[1].visited.finalized()
- || turn.operations[1].visited.rejected()
- || turn.both(operation_blocked)
- || turn.combination(opposite_operation, operation_blocked);
-
- bool is_closed = false;
- if (turn.cluster_id >= 0 && target_operation == operation_union)
- {
- typename Clusters::const_iterator mit = clusters.find(turn.cluster_id);
- BOOST_ASSERT(mit != clusters.end());
+ turn_type const& turn = *it;
- cluster_info const& cinfo = mit->second;
- is_closed = cinfo.open_count == 0;
- }
+ bool cluster_checked = false;
+ bool has_blocked = false;
for (typename boost::range_iterator<container_type const>::type
op_it = boost::begin(turn.operations);
op_it != boost::end(turn.operations);
++op_it)
{
+ turn_operation_type const& op = *op_it;
ring_identifier const ring_id
(
- op_it->seg_id.source_index,
- op_it->seg_id.multi_index,
- op_it->seg_id.ring_index
+ op.seg_id.source_index,
+ op.seg_id.multi_index,
+ op.seg_id.ring_index
);
- if (traversed || is_closed || ! op_it->enriched.startable)
+ if (! is_self_turn<OverlayType>(turn)
+ && (
+ (target_operation == operation_union
+ && op.enriched.count_left > 0)
+ || (target_operation == operation_intersection
+ && op.enriched.count_right <= 2)))
{
- turn_info_map[ring_id].has_traversed_turn = true;
+ // Avoid including untraversed rings which have polygons on
+ // their left side (union) or not two on their right side (int)
+ // This can only be done for non-self-turns because of count
+ // information
+ turn_info_map[ring_id].has_blocked_turn = true;
+ continue;
}
- else if (both_opposite && colocated_target)
- {
- // For union: ii, colocated with a uu
- // For example, two interior rings touch where two exterior rings also touch.
- // The interior rings are not yet traversed, and should be taken from the input
-
- // For intersection: uu, colocated with an ii
- // unless it is two interior inner rings colocated with a uu
- // So don't set has_traversed_turn here
+ if (turn.any_blocked())
+ {
+ turn_info_map[ring_id].has_blocked_turn = true;
+ }
+ if (turn_info_map[ring_id].has_traversed_turn
+ || turn_info_map[ring_id].has_blocked_turn)
+ {
+ continue;
}
- else if (both_opposite && ! is_self_turn<OverlayType>(turn))
+
+ // Check information in colocated turns
+ if (! cluster_checked && turn.is_clustered())
{
- // For union, mark any ring with a ii turn as traversed
- // For intersection, any uu - but not if it is a self-turn
- turn_info_map[ring_id].has_traversed_turn = true;
+ check_colocation(has_blocked, turn.cluster_id, turns, clusters);
+ cluster_checked = true;
}
- else if (colocated_opp && ! colocated_target)
+
+ // Block rings where any other turn is blocked,
+ // and (with exceptions): i for union and u for intersection
+ // Exceptions: don't block self-uu for intersection
+ // don't block self-ii for union
+ // don't block (for union) i/u if there is an self-ii too
+ if (has_blocked
+ || (op.operation == opposite_operation
+ && ! turn.has_colocated_both
+ && ! (turn.both(opposite_operation)
+ && is_self_turn<OverlayType>(turn))))
{
- // For union, a turn colocated with ii and NOT with uu/ux
- // For intersection v.v.
- turn_info_map[ring_id].has_traversed_turn = true;
+ turn_info_map[ring_id].has_blocked_turn = true;
}
}
}
}
-
template
<
typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
@@ -234,7 +234,8 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy);
ring_container_type rings;
assign_parents(geometry1, geometry2, rings, all_of_one_of_them, strategy);
- return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
+ return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out,
+ strategy.template get_area_strategy<point_type1>());
}
@@ -306,9 +307,13 @@ std::cout << "get turns" << std::endl;
visitor.visit_turns(1, turns);
#ifdef BOOST_GEOMETRY_INCLUDE_SELF_TURNS
+ if (needs_self_turns<Geometry1>::apply(geometry1))
{
self_get_turn_points::self_turns<Reverse1, assign_null_policy>(geometry1,
strategy, robust_policy, turns, policy, 0);
+ }
+ if (needs_self_turns<Geometry2>::apply(geometry2))
+ {
self_get_turn_points::self_turns<Reverse2, assign_null_policy>(geometry2,
strategy, robust_policy, turns, policy, 1);
}
@@ -320,6 +325,7 @@ std::cout << "enrich" << std::endl;
#endif
typename Strategy::side_strategy_type side_strategy = strategy.get_side_strategy();
cluster_type clusters;
+ std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
clusters, geometry1, geometry2,
@@ -343,11 +349,12 @@ std::cout << "traverse" << std::endl;
strategy,
robust_policy,
turns, rings,
+ turn_info_per_ring,
clusters,
visitor
);
+ visitor.visit_turns(3, turns);
- std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters);
typedef typename Strategy::template area_strategy<point_type>::type area_strategy_type;
@@ -364,9 +371,8 @@ std::cout << "traverse" << std::endl;
selected_ring_properties, strategy);
// Add rings created during traversal
+ area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>();
{
- area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>();
-
ring_identifier id(2, 0, -1);
for (typename boost::range_iterator<ring_container_type>::type
it = boost::begin(rings);
@@ -381,7 +387,24 @@ std::cout << "traverse" << std::endl;
assign_parents(geometry1, geometry2, rings, selected_ring_properties, strategy);
- return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out);
+ // NOTE: There is no need to check result area for union because
+ // as long as the polygons in the input are valid the resulting
+ // polygons should be valid as well.
+ // By default the area is checked (this is old behavior) however this
+ // can be changed with #define. This may be important in non-cartesian CSes.
+ // The result may be too big, so the area is negative. In this case either
+ // it can be returned or an exception can be thrown.
+ return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out,
+ area_strategy,
+ OverlayType == overlay_union ?
+#if defined(BOOST_GEOMETRY_UNION_THROW_INVALID_OUTPUT_EXCEPTION)
+ add_rings_throw_if_reversed
+#elif defined(BOOST_GEOMETRY_UNION_RETURN_INVALID)
+ add_rings_add_unordered
+#else
+ add_rings_ignore_unordered
+#endif
+ : add_rings_ignore_unordered);
}
template <typename RobustPolicy, typename OutputIterator, typename Strategy>
diff --git a/boost/geometry/algorithms/detail/overlay/overlay_type.hpp b/boost/geometry/algorithms/detail/overlay/overlay_type.hpp
index 0f60840973..f3ec9eaa64 100644
--- a/boost/geometry/algorithms/detail/overlay/overlay_type.hpp
+++ b/boost/geometry/algorithms/detail/overlay/overlay_type.hpp
@@ -21,7 +21,8 @@ enum overlay_type
overlay_intersection,
overlay_difference,
overlay_buffer,
- overlay_dissolve
+ overlay_dissolve_union,
+ overlay_dissolve_intersection
};
#ifndef DOXYGEN_NO_DETAIL
@@ -42,6 +43,17 @@ enum operation_type
template <overlay_type OverlayType>
struct operation_from_overlay
{
+};
+
+template <>
+struct operation_from_overlay<overlay_union>
+{
+ static const operation_type value = operation_union;
+};
+
+template <>
+struct operation_from_overlay<overlay_buffer>
+{
static const operation_type value = operation_union;
};
@@ -57,6 +69,19 @@ struct operation_from_overlay<overlay_difference>
static const operation_type value = operation_intersection;
};
+template <>
+struct operation_from_overlay<overlay_dissolve_union>
+{
+ static const operation_type value = operation_union;
+};
+
+template <>
+struct operation_from_overlay<overlay_dissolve_intersection>
+{
+ static const operation_type value = operation_intersection;
+};
+
+
}} // namespace detail::overlay
#endif //DOXYGEN_NO_DETAIL
diff --git a/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp b/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp
index 0a7c3bc469..6f8fdd32b8 100644
--- a/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp
+++ b/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp
@@ -32,7 +32,6 @@
#include <boost/geometry/algorithms/detail/not.hpp>
#include <boost/geometry/algorithms/detail/partition.hpp>
-#include <boost/geometry/algorithms/detail/relate/less.hpp>
#include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
diff --git a/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp b/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp
index 438a377876..88aedecf86 100644
--- a/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp
+++ b/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp
@@ -1,12 +1,13 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Copyright (c) 2014-2015, Oracle and/or its affiliates.
+// Copyright (c) 2014-2017, Oracle and/or its affiliates.
+
+// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Licensed under the Boost Software License version 1.0.
// http://www.boost.org/users/license.html
-// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
-
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP
@@ -24,10 +25,11 @@
#include <boost/geometry/algorithms/convert.hpp>
#include <boost/geometry/algorithms/not_implemented.hpp>
-#include <boost/geometry/algorithms/detail/relate/less.hpp>
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
+#include <boost/geometry/policies/compare.hpp>
+
namespace boost { namespace geometry
{
@@ -264,17 +266,20 @@ struct multipoint_multipoint_point
>::apply(multipoint2, multipoint1, robust_policy, oit, strategy);
}
- std::vector<typename boost::range_value<MultiPoint2>::type>
- points2(boost::begin(multipoint2), boost::end(multipoint2));
+ typedef typename boost::range_value<MultiPoint2>::type point2_type;
+
+ std::vector<point2_type> points2(boost::begin(multipoint2),
+ boost::end(multipoint2));
- std::sort(points2.begin(), points2.end(), detail::relate::less());
+ geometry::less<> const less = geometry::less<>();
+ std::sort(points2.begin(), points2.end(), less);
for (typename boost::range_iterator<MultiPoint1 const>::type
it1 = boost::begin(multipoint1);
it1 != boost::end(multipoint1); ++it1)
{
bool found = std::binary_search(points2.begin(), points2.end(),
- *it1, detail::relate::less());
+ *it1, less);
action_selector_pl_pl
<
diff --git a/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp b/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp
index 5447c8813e..14e84c9496 100644
--- a/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp
+++ b/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp
@@ -57,6 +57,7 @@ struct segment_identifier
return source_index != other.source_index ? source_index < other.source_index
: multi_index !=other.multi_index ? multi_index < other.multi_index
: ring_index != other.ring_index ? ring_index < other.ring_index
+ : piece_index != other.piece_index ? piece_index < other.piece_index
: segment_index < other.segment_index
;
}
@@ -66,6 +67,7 @@ struct segment_identifier
return source_index == other.source_index
&& segment_index == other.segment_index
&& ring_index == other.ring_index
+ && piece_index == other.piece_index
&& multi_index == other.multi_index
;
}
@@ -79,6 +81,7 @@ struct segment_identifier
;
if (seg_id.ring_index >= 0) os << ", r:" << seg_id.ring_index;
if (seg_id.multi_index >= 0) os << ", m:" << seg_id.multi_index;
+ if (seg_id.piece_index >= 0) os << ", p:" << seg_id.piece_index;
return os;
}
#endif
diff --git a/boost/geometry/algorithms/detail/overlay/select_rings.hpp b/boost/geometry/algorithms/detail/overlay/select_rings.hpp
index 67a4f4bb75..262ba748ab 100644
--- a/boost/geometry/algorithms/detail/overlay/select_rings.hpp
+++ b/boost/geometry/algorithms/detail/overlay/select_rings.hpp
@@ -41,10 +41,12 @@ namespace detail { namespace overlay
struct ring_turn_info
{
bool has_traversed_turn;
+ bool has_blocked_turn;
bool within_other;
ring_turn_info()
: has_traversed_turn(false)
+ , has_blocked_turn(false)
, within_other(false)
{}
};
@@ -265,9 +267,9 @@ inline void update_ring_selection(Geometry1 const& geometry1,
info = tcit->second; // Copy by value
}
- if (info.has_traversed_turn)
+ if (info.has_traversed_turn || info.has_blocked_turn)
{
- // This turn is traversed (or blocked),
+ // This turn is traversed or blocked,
// don't include the original ring
continue;
}
diff --git a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
index 5e9d8efa8e..a00606b087 100644
--- a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
+++ b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
@@ -78,19 +78,22 @@ struct self_section_visitor
Turns& m_turns;
InterruptPolicy& m_interrupt_policy;
std::size_t m_source_index;
+ bool m_skip_adjacent;
inline self_section_visitor(Geometry const& g,
IntersectionStrategy const& is,
RobustPolicy const& rp,
Turns& turns,
InterruptPolicy& ip,
- std::size_t source_index)
+ std::size_t source_index,
+ bool skip_adjacent)
: m_geometry(g)
, m_intersection_strategy(is)
, m_rescale_policy(rp)
, m_turns(turns)
, m_interrupt_policy(ip)
, m_source_index(source_index)
+ , m_skip_adjacent(skip_adjacent)
{}
template <typename Section>
@@ -109,7 +112,7 @@ struct self_section_visitor
TurnPolicy
>::apply(m_source_index, m_geometry, sec1,
m_source_index, m_geometry, sec2,
- false,
+ false, m_skip_adjacent,
m_intersection_strategy,
m_rescale_policy,
m_turns, m_interrupt_policy);
@@ -132,7 +135,7 @@ struct get_turns
RobustPolicy const& robust_policy,
Turns& turns,
InterruptPolicy& interrupt_policy,
- std::size_t source_index)
+ std::size_t source_index, bool skip_adjacent)
{
typedef model::box
<
@@ -143,9 +146,11 @@ struct get_turns
>::type
> box_type;
- typedef geometry::sections<box_type, 1> sections_type;
+ // sectionalize in two dimensions to detect
+ // all potential spikes correctly
+ typedef geometry::sections<box_type, 2> sections_type;
- typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
+ typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions;
sections_type sec;
geometry::sectionalize<Reverse, dimensions>(geometry, robust_policy, sec,
@@ -155,7 +160,7 @@ struct get_turns
<
Reverse, Geometry,
Turns, TurnPolicy, IntersectionStrategy, RobustPolicy, InterruptPolicy
- > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index);
+ > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index, skip_adjacent);
// false if interrupted
geometry::partition
@@ -224,7 +229,8 @@ struct self_get_turn_points
RobustPolicy const& ,
Turns& ,
InterruptPolicy& ,
- std::size_t)
+ std::size_t /*source_index*/,
+ bool /*skip_adjacent*/)
{
return true;
}
@@ -286,7 +292,8 @@ inline void self_turns(Geometry const& geometry,
RobustPolicy const& robust_policy,
Turns& turns,
InterruptPolicy& interrupt_policy,
- std::size_t source_index = 0)
+ std::size_t source_index = 0,
+ bool skip_adjacent = false)
{
concepts::check<Geometry const>();
@@ -298,7 +305,8 @@ inline void self_turns(Geometry const& geometry,
typename tag<Geometry>::type,
Geometry,
turn_policy
- >::apply(geometry, strategy, robust_policy, turns, interrupt_policy, source_index);
+ >::apply(geometry, strategy, robust_policy, turns, interrupt_policy,
+ source_index, skip_adjacent);
}
}} // namespace detail::self_get_turn_points
@@ -331,7 +339,8 @@ inline void self_turns(Geometry const& geometry,
RobustPolicy const& robust_policy,
Turns& turns,
InterruptPolicy& interrupt_policy,
- std::size_t source_index = 0)
+ std::size_t source_index = 0,
+ bool skip_adjacent = false)
{
concepts::check<Geometry const>();
@@ -344,7 +353,8 @@ inline void self_turns(Geometry const& geometry,
<
reverse,
AssignPolicy
- >(geometry, strategy, robust_policy, turns, interrupt_policy, source_index);
+ >(geometry, strategy, robust_policy, turns, interrupt_policy,
+ source_index, skip_adjacent);
}
diff --git a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp
index 5ad2e41b12..fea5698ae1 100644
--- a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp
+++ b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp
@@ -91,13 +91,20 @@ struct less_by_index
template <typename T>
inline bool operator()(const T& first, const T& second) const
{
+ // Length might be considered too
// First order by from/to
if (first.direction != second.direction)
{
return first.direction < second.direction;
}
- // All the same, order by turn index (we might consider length too)
- return first.turn_index < second.turn_index;
+ // Then by turn index
+ if (first.turn_index != second.turn_index)
+ {
+ return first.turn_index < second.turn_index;
+ }
+ // This can also be the same (for example in buffer), but seg_id is
+ // never the same
+ return first.seg_id < second.seg_id;
}
};
diff --git a/boost/geometry/algorithms/detail/overlay/traversal.hpp b/boost/geometry/algorithms/detail/overlay/traversal.hpp
index 69d62b788b..6a9b1def99 100644
--- a/boost/geometry/algorithms/detail/overlay/traversal.hpp
+++ b/boost/geometry/algorithms/detail/overlay/traversal.hpp
@@ -131,7 +131,8 @@ struct traversal
{
}
- inline void finalize_visit_info()
+ template <typename TurnInfoMap>
+ inline void finalize_visit_info(TurnInfoMap& turn_info_map)
{
for (typename boost::range_iterator<Turns>::type
it = boost::begin(m_turns);
@@ -142,6 +143,32 @@ struct traversal
for (int i = 0; i < 2; i++)
{
turn_operation_type& op = turn.operations[i];
+ if (op.visited.visited()
+ || op.visited.started()
+ || op.visited.finished() )
+ {
+ ring_identifier const ring_id
+ (
+ op.seg_id.source_index,
+ op.seg_id.multi_index,
+ op.seg_id.ring_index
+ );
+ turn_info_map[ring_id].has_traversed_turn = true;
+
+ if (op.operation == operation_continue)
+ {
+ // Continue operations should mark the other operation
+ // as traversed too
+ turn_operation_type& other_op = turn.operations[1 - i];
+ ring_identifier const other_ring_id
+ (
+ other_op.seg_id.source_index,
+ other_op.seg_id.multi_index,
+ other_op.seg_id.ring_index
+ );
+ turn_info_map[other_ring_id].has_traversed_turn = true;
+ }
+ }
op.visited.finalize();
}
}
@@ -192,7 +219,7 @@ struct traversal
{
op.visited.set_visited();
}
- if (turn.cluster_id >= 0)
+ if (turn.is_clustered())
{
set_visited_in_cluster(turn.cluster_id, op.enriched.rank);
}
@@ -204,6 +231,16 @@ struct traversal
return op.visited.visited();
}
+ template <signed_size_type segment_identifier::*Member>
+ inline bool select_source_generic(bool switch_source,
+ segment_identifier const& current,
+ segment_identifier const& previous) const
+ {
+ return switch_source
+ ? current.*Member != previous.*Member
+ : current.*Member == previous.*Member;
+ }
+
inline bool select_source(signed_size_type turn_index,
segment_identifier const& candidate_seg_id,
segment_identifier const& previous_seg_id) const
@@ -211,22 +248,6 @@ struct traversal
// For uu/ii, only switch sources if indicated
turn_type const& turn = m_turns[turn_index];
- if (OverlayType == overlay_buffer)
- {
- // Buffer does not use source_index (always 0)
- return turn.switch_source
- ? candidate_seg_id.multi_index != previous_seg_id.multi_index
- : candidate_seg_id.multi_index == previous_seg_id.multi_index;
- }
-
- if (is_self_turn<OverlayType>(turn))
- {
- // Also, if it is a self-turn, stay on same ring (multi/ring)
- return turn.switch_source
- ? candidate_seg_id.multi_index != previous_seg_id.multi_index
- : candidate_seg_id.multi_index == previous_seg_id.multi_index;
- }
-
#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
if (turn.switch_source)
{
@@ -237,9 +258,24 @@ struct traversal
std::cout << "DON'T SWITCH SOURCES at " << turn_index << std::endl;
}
#endif
- return turn.switch_source
- ? candidate_seg_id.source_index != previous_seg_id.source_index
- : candidate_seg_id.source_index == previous_seg_id.source_index;
+ if (OverlayType == overlay_buffer
+ || OverlayType == overlay_dissolve_union)
+ {
+ // Buffer does not use source_index (always 0).
+ return select_source_generic<&segment_identifier::multi_index>(
+ turn.switch_source, candidate_seg_id, previous_seg_id);
+ }
+
+ if (is_self_turn<OverlayType>(turn))
+ {
+ // Also, if it is a self-turn, stay on same ring (multi/ring)
+ return select_source_generic<&segment_identifier::multi_index>(
+ turn.switch_source, candidate_seg_id, previous_seg_id);
+ }
+
+ // Use source_index
+ return select_source_generic<&segment_identifier::source_index>(
+ turn.switch_source, candidate_seg_id, previous_seg_id);
}
inline bool traverse_possible(signed_size_type turn_index) const
@@ -253,7 +289,7 @@ struct traversal
// It is not a dead end if there is an operation to continue, or of
// there is a cluster (assuming for now we can get out of the cluster)
- return turn.cluster_id >= 0
+ return turn.is_clustered()
|| turn.has(target_operation)
|| turn.has(operation_continue);
}
@@ -318,6 +354,7 @@ struct traversal
if (op.operation == target_operation
&& ! op.visited.finished()
+ && ! op.visited.visited()
&& (! result || select_source(turn_index, op.seg_id, previous_seg_id)))
{
selected_op_index = i;
@@ -380,13 +417,51 @@ struct traversal
return true;
}
+ inline int select_turn_in_cluster_union(std::size_t selected_rank,
+ typename sbs_type::rp const& ranked_point,
+ signed_size_type start_turn_index, int start_op_index) const
+ {
+ // Returns 0 if it not OK
+ // Returns 1 if it OK
+ // Returns 2 if it OK and start turn matches
+ // Returns 3 if it OK and start turn and start op both match
+ if (ranked_point.rank != selected_rank
+ || ranked_point.direction != sort_by_side::dir_to)
+ {
+ return 0;
+ }
+
+ turn_type const& turn = m_turns[ranked_point.turn_index];
+ turn_operation_type const& op = turn.operations[ranked_point.operation_index];
+
+ // Check finalized: TODO: this should be finetuned, it is not necessary
+ if (op.visited.finalized())
+ {
+ return 0;
+ }
+
+ if (OverlayType != overlay_dissolve_union
+ && (op.enriched.count_left != 0 || op.enriched.count_right == 0))
+ {
+ // Check counts: in some cases interior rings might be generated with
+ // polygons on both sides. For dissolve it can be anything.
+ return 0;
+ }
+
+ return ranked_point.turn_index == start_turn_index
+ && ranked_point.operation_index == start_op_index ? 3
+ : ranked_point.turn_index == start_turn_index ? 2
+ : 1
+ ;
+ }
+
inline bool select_from_cluster_union(signed_size_type& turn_index,
- int& op_index, sbs_type& sbs) const
+ int& op_index, sbs_type& sbs,
+ signed_size_type start_turn_index, int start_op_index) const
{
std::vector<sort_by_side::rank_with_rings> aggregation;
sort_by_side::aggregate_operations(sbs, aggregation, m_turns, operation_union);
-
sort_by_side::rank_with_rings const& incoming = aggregation.front();
// Take the first one outgoing for the incoming region
@@ -402,62 +477,32 @@ struct traversal
}
}
+ int best_code = 0;
+ bool result = false;
for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++)
{
typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
- if (ranked_point.rank == selected_rank
- && ranked_point.direction == sort_by_side::dir_to)
- {
- turn_index = ranked_point.turn_index;
- op_index = ranked_point.operation_index;
-
- turn_type const& turn = m_turns[turn_index];
- turn_operation_type const& op = turn.operations[op_index];
-
- if (op.enriched.count_left == 0
- && op.enriched.count_right > 0
- && ! op.visited.finalized())
- {
- // In some cases interior rings might be generated with polygons
- // on both sides
-
- // TODO: this should be finetuned such that checking
- // finalized is not necessary
- return true;
- }
- }
- }
- return false;
- }
-
- inline bool all_operations_of_type(sort_by_side::rank_with_rings const& rwr,
- operation_type op_type,
- sort_by_side::direction_type dir) const
- {
- typedef std::set<sort_by_side::ring_with_direction>::const_iterator sit_type;
- for (sit_type it = rwr.rings.begin(); it != rwr.rings.end(); ++it)
- {
- sort_by_side::ring_with_direction const& rwd = *it;
- if (rwd.direction != dir)
+ if (ranked_point.rank > selected_rank)
{
- return false;
- }
- turn_type const& turn = m_turns[rwd.turn_index];
- if (! turn.both(op_type))
- {
- return false;
+ // Sorted on rank, so it makes no sense to continue
+ break;
}
- // Check if this is not yet taken
- turn_operation_type const& op = turn.operations[rwd.operation_index];
- if (op.visited.finalized())
+ int const code
+ = select_turn_in_cluster_union(selected_rank, ranked_point,
+ start_turn_index, start_op_index);
+
+ if (code > best_code)
{
- return false;
+ // It is 1 or higher and matching better than previous
+ best_code = code;
+ turn_index = ranked_point.turn_index;
+ op_index = ranked_point.operation_index;
+ result = true;
}
-
}
- return true;
+ return result;
}
inline bool analyze_cluster_intersection(signed_size_type& turn_index,
@@ -475,12 +520,14 @@ struct traversal
|| intersection_pattern_common_interior2(selected_rank, aggregation)
|| intersection_pattern_common_interior3(selected_rank, aggregation)
|| intersection_pattern_common_interior4(selected_rank, aggregation)
+ || intersection_pattern_common_interior5(selected_rank, aggregation)
+ || intersection_pattern_common_interior6(selected_rank, aggregation)
;
if (! detected)
{
- int incoming_region_id = 0;
- std::set<int> outgoing_region_ids;
+ signed_size_type incoming_region_id = 0;
+ std::set<signed_size_type> outgoing_region_ids;
for (std::size_t i = 0; i < aggregation.size(); i++)
{
@@ -530,7 +577,7 @@ struct traversal
{
for (int i = 0; i < 2; i++)
{
- int const region_id = turn.operations[i].enriched.region_id;
+ signed_size_type const region_id = turn.operations[i].enriched.region_id;
if (outgoing_region_ids.count(region_id) == 1)
{
selected_rank = 0;
@@ -545,6 +592,9 @@ struct traversal
if (selected_rank > 0)
{
+ typename turn_operation_type::comparable_distance_type
+ min_remaining_distance = 0;
+
std::size_t selected_index = sbs.m_ranked_points.size();
for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
{
@@ -562,8 +612,13 @@ struct traversal
continue;
}
- // Take the last turn from this rank
- selected_index = i;
+ // Take turn with the smallest remaining distance
+ if (selected_index == sbs.m_ranked_points.size()
+ || ranked_op.remaining_distance < min_remaining_distance)
+ {
+ selected_index = i;
+ min_remaining_distance = ranked_op.remaining_distance;
+ }
}
}
@@ -581,13 +636,13 @@ struct traversal
inline bool select_turn_from_cluster(signed_size_type& turn_index,
int& op_index,
- signed_size_type start_turn_index,
+ signed_size_type start_turn_index, int start_op_index,
segment_identifier const& previous_seg_id) const
{
bool const is_union = target_operation == operation_union;
turn_type const& turn = m_turns[turn_index];
- BOOST_ASSERT(turn.cluster_id >= 0);
+ BOOST_ASSERT(turn.is_clustered());
typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id);
BOOST_ASSERT(mit != m_clusters.end());
@@ -628,7 +683,8 @@ struct traversal
if (is_union)
{
- result = select_from_cluster_union(turn_index, op_index, sbs);
+ result = select_from_cluster_union(turn_index, op_index, sbs,
+ start_turn_index, start_op_index);
}
else
{
@@ -669,11 +725,15 @@ struct traversal
turn_operation_type const& start_op,
int start_op_index) const
{
- if (OverlayType != overlay_buffer)
+ if (OverlayType != overlay_buffer
+ && OverlayType != overlay_dissolve_union
+ && OverlayType != overlay_dissolve_intersection)
{
return;
}
+ const bool allow_uu = OverlayType != overlay_buffer;
+
// It travels to itself, can happen. If this is a buffer, it can
// sometimes travel to itself in the following configuration:
//
@@ -696,7 +756,10 @@ struct traversal
= start_turn.operations[1 - start_op_index];
bool const correct
- = ! start_turn.both(operation_union)
+ = (allow_uu || ! start_turn.both(operation_union))
+ && start_op.seg_id.source_index == other_op.seg_id.source_index
+ && start_op.seg_id.multi_index == other_op.seg_id.multi_index
+ && start_op.seg_id.ring_index == other_op.seg_id.ring_index
&& start_op.seg_id.segment_index == to_vertex_index;
#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
@@ -770,7 +833,7 @@ struct traversal
if (target_operation == operation_intersection)
{
bool const back_at_start_cluster
- = current_turn.cluster_id >= 0
+ = current_turn.is_clustered()
&& m_turns[start_turn_index].cluster_id == current_turn.cluster_id;
if (turn_index == start_turn_index || back_at_start_cluster)
@@ -781,7 +844,7 @@ struct traversal
return true;
}
- if (current_turn.cluster_id < 0
+ if (! current_turn.is_clustered()
&& current_turn.both(operation_intersection))
{
if (analyze_ii_intersection(turn_index, op_index,
@@ -792,10 +855,10 @@ struct traversal
}
}
- if (current_turn.cluster_id >= 0)
+ if (current_turn.is_clustered())
{
if (! select_turn_from_cluster(turn_index, op_index,
- start_turn_index, previous_seg_id))
+ start_turn_index, start_op_index, previous_seg_id))
{
return false;
}
diff --git a/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp b/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp
index 12279d762f..a8abea230e 100644
--- a/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp
+++ b/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp
@@ -32,8 +32,8 @@ inline bool check_pairs(std::vector<sort_by_side::rank_with_rings> const& aggreg
{
sort_by_side::rank_with_rings const& curr = aggregation[i];
sort_by_side::rank_with_rings const& next = aggregation[i + 1];
- int const curr_id = curr.region_id();
- int const next_id = next.region_id();
+ signed_size_type const curr_id = curr.region_id();
+ signed_size_type const next_id = next.region_id();
bool const possible =
curr.rings.size() == 2
@@ -249,7 +249,7 @@ inline bool intersection_pattern_common_interior4(std::size_t& selected_rank,
//Rank 1 {13[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->15} {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->15}
//Rank 2 {13[0] (s:0, r:0, m:0) i F rgn: 2 ISO} {11[1] (s:1, r:1, m:0) i F rgn: 2 ISO}
- // LEAVING (in two different directions, take last one)
+ // LEAVING (in two different directions, take penultimate one)
//Rank 3 {10[1] (s:1, m:0) i T rgn: 1 ISO ->0}
//Rank 4 {11[0] (s:0, m:0) i T rgn: 1 ISO ->12}
@@ -292,12 +292,157 @@ inline bool intersection_pattern_common_interior4(std::size_t& selected_rank,
// Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
if (check_pairs(aggregation, incoming.region_id(), 1, n - 3))
{
- selected_rank = n - 1;
+ selected_rank = n - 2;
return true;
}
return false;
}
+inline bool intersection_pattern_common_interior5(std::size_t& selected_rank,
+ std::vector<sort_by_side::rank_with_rings> const& aggregation)
+{
+ // Pattern: isolated regions
+
+ // See #case_recursive_boxes_65
+
+ // INCOMING:
+ // Rank 0 {19[0] (s:0, r:2, m:0) i F rgn: 4 ISO}
+
+ // Rank 1 {19[1] (s:1, m:0) i T rgn: 1 ISO FIN ->18 (2.5)}
+ // Rank 2 {21[1] (s:1, m:2) i F rgn: 1 ISO}
+ // Rank 3 {21[1] (s:1, m:2) i T rgn: 1 ISO ->17 (2)}
+ // Rank 4 {19[1] (s:1, m:0) i F rgn: 1 ISO FIN}
+
+ // LEAVING (take this one):
+ // Rank 5 {19[0] (s:0, r:2, m:0) i T rgn: 4 ISO ->22 (1)}
+
+ std::size_t const n = aggregation.size();
+ if (n < 3)
+ {
+ return false;
+ }
+
+ sort_by_side::rank_with_rings const& incoming = aggregation.front();
+ sort_by_side::rank_with_rings const& outgoing = aggregation.back();
+
+ bool const incoming_ok =
+ incoming.all_from()
+ && incoming.has_unique_region_id()
+ && incoming.is_isolated();
+
+ if (! incoming_ok)
+ {
+ return false;
+ }
+
+ signed_size_type const incoming_region_id = incoming.region_id();
+
+ bool const outgoing_ok =
+ outgoing.all_to()
+ && outgoing.has_unique_region_id()
+ && outgoing.is_isolated()
+ && outgoing.region_id() == incoming_region_id;
+
+ if (! outgoing_ok)
+ {
+ return false;
+ }
+
+ selected_rank = n - 1;
+ bool other_region = true;
+
+ // Assumed is that other regions go (T) and come back (F)
+ for (std::size_t i = 1; i < n - 1; i++)
+ {
+ sort_by_side::rank_with_rings const& rwr = aggregation[i];
+ if (! rwr.has_unique_region_id() || ! rwr.is_isolated())
+ {
+ return false;
+ }
+ signed_size_type const region_id = rwr.region_id();
+ if (other_region && region_id != incoming_region_id)
+ {
+ // OK
+ }
+ else if (other_region && region_id == incoming_region_id)
+ {
+ // OK, next phase (same region as incoming region)
+ selected_rank = i;
+ other_region = false;
+ }
+ else if (! other_region && region_id != incoming_region_id)
+ {
+ // After that the region is the same is incoming, it should
+ // stay like that
+ return false;
+ }
+ }
+
+ return true;
+}
+
+inline bool intersection_pattern_common_interior6(std::size_t& selected_rank,
+ std::vector<sort_by_side::rank_with_rings> const& aggregation)
+{
+ // Pattern: isolated regions in between
+
+ // See #case_recursive_boxes_75
+
+ // Incoming: one region
+ // In between: several rings having isolated region, all the same
+ // Outging == incoming
+
+ std::size_t const n = aggregation.size();
+ if (n < 3)
+ {
+ return false;
+ }
+
+ sort_by_side::rank_with_rings const& incoming = aggregation.front();
+ sort_by_side::rank_with_rings const& outgoing = aggregation.back();
+ sort_by_side::rank_with_rings const& first_isolated = aggregation[2];
+
+ bool const incoming_ok =
+ incoming.all_from()
+ && incoming.has_unique_region_id()
+ && ! incoming.is_isolated();
+
+ if (! incoming_ok)
+ {
+ return false;
+ }
+
+ signed_size_type const incoming_region_id = incoming.region_id();
+
+ bool const outgoing_ok =
+ outgoing.all_to()
+ && outgoing.has_unique_region_id()
+ && ! outgoing.is_isolated()
+ && outgoing.region_id() == incoming_region_id;
+
+ if (! outgoing_ok)
+ {
+ return false;
+ }
+
+ const signed_size_type isolated_region_id = first_isolated.region_id();
+
+ for (std::size_t i = 1; i < n - 1; i++)
+ {
+ sort_by_side::rank_with_rings const& rwr = aggregation[i];
+ if (! rwr.has_unique_region_id()
+ || ! rwr.is_isolated()
+ || rwr.region_id() != isolated_region_id)
+ {
+ return false;
+ }
+ }
+
+ selected_rank = n - 1;
+
+ return true;
+}
+
}} // namespace detail::overlay
#endif // DOXYGEN_NO_DETAIL
diff --git a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp
index af643a822b..4df3f6e7ac 100644
--- a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp
+++ b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp
@@ -41,6 +41,7 @@ template
typename Geometry1,
typename Geometry2,
typename Turns,
+ typename TurnInfoMap,
typename Clusters,
typename IntersectionStrategy,
typename RobustPolicy,
@@ -64,7 +65,8 @@ struct traversal_ring_creator
= operation_from_overlay<OverlayType>::value;
inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2,
- Turns& turns, Clusters const& clusters,
+ Turns& turns, TurnInfoMap& turn_info_map,
+ Clusters const& clusters,
IntersectionStrategy const& intersection_strategy,
RobustPolicy const& robust_policy, Visitor& visitor)
: m_trav(geometry1, geometry2, turns, clusters,
@@ -73,6 +75,7 @@ struct traversal_ring_creator
, m_geometry1(geometry1)
, m_geometry2(geometry2)
, m_turns(turns)
+ , m_turn_info_map(turn_info_map)
, m_clusters(clusters)
, m_intersection_strategy(intersection_strategy)
, m_robust_policy(robust_policy)
@@ -203,7 +206,7 @@ struct traversal_ring_creator
return traverse_error_none;
}
- if (start_turn.cluster_id >= 0)
+ if (start_turn.is_clustered())
{
turn_type const& turn = m_turns[current_turn_index];
if (turn.cluster_id == start_turn.cluster_id)
@@ -286,7 +289,7 @@ struct traversal_ring_creator
m_robust_policy);
rings.push_back(ring);
- m_trav.finalize_visit_info();
+ m_trav.finalize_visit_info(m_turn_info_map);
finalized_ring_size++;
}
}
@@ -347,6 +350,7 @@ private:
Geometry1 const& m_geometry1;
Geometry2 const& m_geometry2;
Turns& m_turns;
+ TurnInfoMap& m_turn_info_map; // contains turn-info information per ring
Clusters const& m_clusters;
IntersectionStrategy const& m_intersection_strategy;
RobustPolicy const& m_robust_policy;
diff --git a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp
index 0b4f393ef4..72f9c4f12a 100644
--- a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp
+++ b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp
@@ -48,17 +48,24 @@ template
>
struct traversal_switch_detector
{
- enum isolation_type { isolation_unknown = -1, isolation_no = 0, isolation_yes = 1 };
+ enum isolation_type
+ {
+ isolation_unknown = -1,
+ isolation_no = 0,
+ isolation_yes = 1,
+ isolation_multiple = 2
+ };
typedef typename boost::range_value<Turns>::type turn_type;
typedef typename turn_type::turn_operation_type turn_operation_type;
+ typedef std::set<signed_size_type> set_type;
// Per ring, first turns are collected (in turn_indices), and later
// a region_id is assigned
struct merged_ring_properties
{
signed_size_type region_id;
- std::set<signed_size_type> turn_indices;
+ set_type turn_indices;
merged_ring_properties()
: region_id(-1)
@@ -68,7 +75,8 @@ struct traversal_switch_detector
struct connection_properties
{
std::size_t count;
- std::set<signed_size_type> cluster_indices;
+ // Contains turn-index OR, if clustered, minus-cluster_id
+ set_type unique_turn_ids;
connection_properties()
: count(0)
{}
@@ -82,6 +90,7 @@ struct traversal_switch_detector
{
signed_size_type region_id;
isolation_type isolated;
+ set_type unique_turn_ids;
// Maps from connected region_id to their properties
connection_map connected_region_counts;
@@ -96,7 +105,7 @@ struct traversal_switch_detector
typedef std::map<ring_identifier, merged_ring_properties > merge_map;
typedef std::map<signed_size_type, region_properties> region_connection_map;
- typedef std::set<signed_size_type>::const_iterator set_iterator;
+ typedef set_type::const_iterator set_iterator;
inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2,
Turns& turns, Clusters& clusters,
@@ -110,111 +119,232 @@ struct traversal_switch_detector
{
}
- isolation_type get_isolation(region_properties const& properties,
- signed_size_type parent_region_id,
- const std::set<signed_size_type>& visited)
+ bool inspect_difference(set_type& turn_id_difference,
+ set_type const& turn_ids,
+ set_type const& other_turn_ids) const
{
- if (properties.isolated != isolation_unknown)
+ // TODO: consider if std::set_difference can be used in the final version
+ int const turn_count = turn_ids.size();
+ int const other_turn_count = other_turn_ids.size();
+
+ // First quick check on size (TODO: implement multiple-multiple connections)
+ if (turn_count - other_turn_count > 1)
{
- return properties.isolated;
+ return false;
}
- bool all_colocated = true;
- int unique_cluster_id = -1;
- for (typename connection_map::const_iterator it = properties.connected_region_counts.begin();
- all_colocated && it != properties.connected_region_counts.end(); ++it)
+ // Check if all turns are also present in the connection.
+ // The difference is returned
+ for (set_iterator it = turn_ids.begin(); it != turn_ids.end(); ++it)
{
- connection_properties const& cprop = it->second;
- if (cprop.cluster_indices.size() != 1)
- {
- // Either no cluster (non colocated point), or more clusters
- all_colocated = false;
- }
- int const cluster_id = *cprop.cluster_indices.begin();
- if (cluster_id == -1)
+ signed_size_type const& id = *it;
+ if (other_turn_ids.count(id) == 0)
{
- all_colocated = false;
- }
- else if (unique_cluster_id == -1)
- {
- unique_cluster_id = cluster_id;
- }
- else if (unique_cluster_id != cluster_id)
- {
- all_colocated = false;
+ turn_id_difference.insert(id);
}
}
- if (all_colocated)
+ return true;
+ }
+
+ bool one_connection_to_another_region(region_properties const& region) const
+ {
+ // For example:
+ // +----------------------+
+ // | __ |
+ // | / \|
+ // | | x
+ // | \__/|
+ // | |
+ // +----------------------+
+
+ if (region.connected_region_counts.size() == 1)
{
- return isolation_yes;
+ connection_properties const& cprop = region.connected_region_counts.begin()->second;
+ return cprop.count <= 1;
}
+ return region.connected_region_counts.empty();
+ }
+ // TODO: might be combined with previous
+ bool multiple_connections_to_one_region(region_properties const& region) const
+ {
+ // For example:
+ // +----------------------+
+ // | __ |
+ // | / \|
+ // | | x
+ // | \ /|
+ // | / \|
+ // | | x
+ // | \__/|
+ // | |
+ // +----------------------+
+
+ if (region.connected_region_counts.size() == 1)
+ {
+ connection_properties const& cprop = region.connected_region_counts.begin()->second;
+ return cprop.count > 1;
+ }
+ return false;
+ }
- // It is isolated if there is only one connection, or if there are more connections but all
- // of them are isolated themselves, or if there are more connections
- // but they are all colocated
- std::size_t non_isolation_count = 0;
- bool child_not_isolated = false;
- for (typename connection_map::const_iterator it = properties.connected_region_counts.begin();
- it != properties.connected_region_counts.end(); ++it)
+ bool one_connection_to_multiple_regions(region_properties const& region) const
+ {
+ // For example:
+ // +----------------------+
+ // | __ | __
+ // | / \|/ |
+ // | | x |
+ // | \__/|\__|
+ // | |
+ // +----------------------+
+
+ bool first = true;
+ signed_size_type first_turn_id = 0;
+ for (typename connection_map::const_iterator it = region.connected_region_counts.begin();
+ it != region.connected_region_counts.end(); ++it)
{
- signed_size_type const region_id = it->first;
connection_properties const& cprop = it->second;
- if (region_id == parent_region_id)
+ if (cprop.count != 1)
{
- // Normal situation, skip its direct parent
- continue;
+ return false;
}
- if (visited.count(region_id) > 0)
+ signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin();
+ if (first)
{
- // Find one of its ancestors again, this is a ring. Not isolated.
- return isolation_no;
+ first_turn_id = unique_turn_id;
+ first = false;
}
- if (cprop.count > 1)
+ else if (first_turn_id != unique_turn_id)
{
- return isolation_no;
+ return false;
}
+ }
+ return true;
+ }
- typename region_connection_map::iterator mit = m_connected_regions.find(region_id);
+ bool has_only_isolated_children(region_properties const& region) const
+ {
+ bool first_with_turn = true;
+ bool first_with_multiple = true;
+ signed_size_type first_turn_id = 0;
+ signed_size_type first_multiple_region_id = 0;
+
+ for (typename connection_map::const_iterator it = region.connected_region_counts.begin();
+ it != region.connected_region_counts.end(); ++it)
+ {
+ signed_size_type const region_id = it->first;
+ connection_properties const& cprop = it->second;
+
+ typename region_connection_map::const_iterator mit = m_connected_regions.find(region_id);
if (mit == m_connected_regions.end())
{
// Should not occur
- continue;
+ return false;
}
- std::set<signed_size_type> vis = visited;
- vis.insert(parent_region_id);
+ region_properties const& connected_region = mit->second;
+
+ bool const multiple = connected_region.isolated == isolation_multiple;
- region_properties& prop = mit->second;
- if (prop.isolated == isolation_unknown)
+ if (cprop.count != 1)
{
- isolation_type const iso = get_isolation(prop, properties.region_id, vis);
- prop.isolated = iso;
- if (iso == isolation_no)
+ if (! multiple)
+ {
+ return false;
+ }
+
+ // It connects multiple times to an isolated region.
+ // This is allowed as long as it happens only once
+ if (first_with_multiple)
+ {
+ first_multiple_region_id = connected_region.region_id;
+ first_with_multiple = false;
+ }
+ else if (first_multiple_region_id != connected_region.region_id)
+ {
+ return false;
+ }
+
+ // Turns in region should be either present in the connection,
+ // of form part of the connection with the other region
+ set_type diff;
+ if (! inspect_difference(diff, region.unique_turn_ids,
+ connected_region.unique_turn_ids))
{
- child_not_isolated = true;
+ return false;
+ }
+ if (diff.size() > 1)
+ {
+ // For now:
+ return false;
}
}
- if (prop.isolated == isolation_no)
+
+ if (connected_region.isolated != isolation_yes && ! multiple)
{
- non_isolation_count++;
+ signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin();
+ if (first_with_turn)
+ {
+ first_turn_id = unique_turn_id;
+ first_with_turn = false;
+ }
+ else if (first_turn_id != unique_turn_id)
+ {
+ return false;
+ }
}
}
-
- return child_not_isolated || non_isolation_count > 1 ? isolation_no : isolation_yes;
+ // If there is only one connection (with a 'parent'), and all other
+ // connections are itself isolated, it is isolated
+ return true;
}
void get_isolated_regions()
{
- for (typename region_connection_map::iterator it = m_connected_regions.begin();
+ typedef typename region_connection_map::iterator it_type;
+
+ // First time: check regions isolated (one connection only),
+ // semi-isolated (multiple connections between same region),
+ // and complex isolated (connection with multiple rings but all
+ // at same point)
+ for (it_type it = m_connected_regions.begin();
it != m_connected_regions.end(); ++it)
{
region_properties& properties = it->second;
- if (properties.isolated == isolation_unknown)
+ if (one_connection_to_another_region(properties))
{
- std::set<signed_size_type> visited;
- properties.isolated = get_isolation(properties, properties.region_id, visited);
+ properties.isolated = isolation_yes;
+ }
+ else if (multiple_connections_to_one_region(properties))
+ {
+ properties.isolated = isolation_multiple;
+ }
+ else if (one_connection_to_multiple_regions(properties))
+ {
+ properties.isolated = isolation_yes;
+ }
+ }
+
+ // Propagate isolation to next level
+ // TODO: should be optimized
+ std::size_t defensive_check = 0;
+ bool changed = true;
+ while (changed && defensive_check++ < m_connected_regions.size())
+ {
+ changed = false;
+ for (it_type it = m_connected_regions.begin();
+ it != m_connected_regions.end(); ++it)
+ {
+ region_properties& properties = it->second;
+
+ if (properties.isolated == isolation_unknown
+ && has_only_isolated_children(properties))
+ {
+ properties.isolated = isolation_yes;
+ changed = true;
+ }
}
}
}
@@ -238,7 +368,7 @@ struct traversal_switch_detector
}
}
- void assign_regions()
+ void assign_region_ids()
{
for (typename merge_map::const_iterator it
= m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
@@ -259,39 +389,53 @@ struct traversal_switch_detector
op.enriched.region_id = properties.region_id;
}
}
- signed_size_type const& id0 = turn.operations[0].enriched.region_id;
- signed_size_type const& id1 = turn.operations[1].enriched.region_id;
- if (id0 != id1 && id0 != -1 && id1 != -1)
- {
- // Force insertion
- m_connected_regions[id0].region_id = id0;
- m_connected_regions[id1].region_id = id1;
+ }
+ }
+ }
- connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1];
- connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0];
+ void assign_connected_regions()
+ {
+ for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
+ {
+ turn_type const& turn = m_turns[turn_index];
- if (turn.cluster_id < 0)
- {
- // Turn is not colocated, add reference to connection
- prop0.count++;
- prop1.count++;
- }
- else
- {
- // Turn is colocated, only add region reference if it was not yet registered
- if (prop0.cluster_indices.count(turn.cluster_id) == 0)
- {
- prop0.count++;
- }
- if (prop1.cluster_indices.count(turn.cluster_id) == 0)
- {
- prop1.count++;
- }
- }
- // Insert cluster-id (also -1 is inserted - reinsertion of
- // same cluster id is OK)
- prop0.cluster_indices.insert(turn.cluster_id);
- prop1.cluster_indices.insert(turn.cluster_id);
+ signed_size_type const unique_turn_id
+ = turn.is_clustered() ? -turn.cluster_id : turn_index;
+
+ turn_operation_type op0 = turn.operations[0];
+ turn_operation_type op1 = turn.operations[1];
+
+ signed_size_type const& id0 = op0.enriched.region_id;
+ signed_size_type const& id1 = op1.enriched.region_id;
+
+ // Add region (by assigning) and add involved turns
+ if (id0 != -1)
+ {
+ m_connected_regions[id0].region_id = id0;
+ m_connected_regions[id0].unique_turn_ids.insert(unique_turn_id);
+ }
+ if (id1 != -1 && id0 != id1)
+ {
+ m_connected_regions[id1].region_id = id1;
+ m_connected_regions[id1].unique_turn_ids.insert(unique_turn_id);
+ }
+
+ if (id0 != id1 && id0 != -1 && id1 != -1)
+ {
+ // Assign connections
+ connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1];
+ connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0];
+
+ // Reference this turn or cluster to later check uniqueness on ring
+ if (prop0.unique_turn_ids.count(unique_turn_id) == 0)
+ {
+ prop0.count++;
+ prop0.unique_turn_ids.insert(unique_turn_id);
+ }
+ if (prop1.unique_turn_ids.count(unique_turn_id) == 0)
+ {
+ prop1.count++;
+ prop1.unique_turn_ids.insert(unique_turn_id);
}
}
}
@@ -306,7 +450,7 @@ struct traversal_switch_detector
return false;
}
- if (turn.cluster_id == -1)
+ if (! turn.is_clustered())
{
// If it is a uu/ii-turn (non clustered), it is never same region
return ! (turn.both(operation_union) || turn.both(operation_intersection));
@@ -320,39 +464,22 @@ struct traversal_switch_detector
== turn.operations[1].enriched.zone;
}
- // If a cluster contains an ii/cc it is not same region (for intersection)
- typename Clusters::const_iterator it = m_clusters.find(turn.cluster_id);
- if (it == m_clusters.end())
- {
- // Should not occur
- return true;
- }
-
- cluster_info const& cinfo = it->second;
- for (set_iterator sit = cinfo.turn_indices.begin();
- sit != cinfo.turn_indices.end(); ++sit)
- {
- turn_type const& cluster_turn = m_turns[*sit];
- if (cluster_turn.both(operation_union)
- || cluster_turn.both(operation_intersection))
- {
- return false;
- }
- }
-
- // It is the same region
- return false;
+ // For an intersection, two regions connect if they are not ii
+ // (ii-regions are isolated) or, in some cases, not iu (for example
+ // when a multi-polygon is inside an interior ring and connecting it)
+ return ! (turn.both(operation_intersection)
+ || turn.combination(operation_intersection, operation_union));
}
- inline int get_region_id(turn_operation_type const& op) const
+ inline signed_size_type get_region_id(turn_operation_type const& op) const
{
return op.enriched.region_id;
}
void create_region(signed_size_type& new_region_id, ring_identifier const& ring_id,
- merged_ring_properties& properties, int region_id = -1)
+ merged_ring_properties& properties, signed_size_type region_id = -1)
{
if (properties.region_id > 0)
{
@@ -400,7 +527,7 @@ struct traversal_switch_detector
}
void propagate_region(signed_size_type& new_region_id,
- ring_identifier const& ring_id, int region_id)
+ ring_identifier const& ring_id, signed_size_type region_id)
{
typename merge_map::iterator it = m_turns_per_ring.find(ring_id);
if (it != m_turns_per_ring.end())
@@ -438,7 +565,7 @@ struct traversal_switch_detector
}
}
- // All rings having turns are in the map. Now iterate them
+ // All rings having turns are in turns/ring map. Process them.
{
signed_size_type new_region_id = 1;
for (typename merge_map::iterator it
@@ -447,7 +574,8 @@ struct traversal_switch_detector
create_region(new_region_id, it->first, it->second);
}
- assign_regions();
+ assign_region_ids();
+ assign_connected_regions();
get_isolated_regions();
assign_isolation();
}
@@ -464,9 +592,8 @@ struct traversal_switch_detector
}
// A touching cluster, gather regions
- std::set<int> regions;
-
- std::set<signed_size_type> const& ids = cinfo.turn_indices;
+ set_type regions;
+ set_type const& ids = cinfo.turn_indices;
#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
std::cout << "SWITCH EXAMINE CLUSTER " << it->first << std::endl;
@@ -476,14 +603,10 @@ struct traversal_switch_detector
{
signed_size_type turn_index = *sit;
turn_type const& turn = m_turns[turn_index];
- if (turn.colocated_ii && ! turn.colocated_uu)
- {
- continue;
- }
for (int oi = 0; oi < 2; oi++)
{
- int const region = get_region_id(turn.operations[oi]);
- regions.insert(region);
+ signed_size_type const region_id = get_region_id(turn.operations[oi]);
+ regions.insert(region_id);
}
}
// Switch source if this cluster connects the same region
@@ -497,24 +620,16 @@ struct traversal_switch_detector
if (turn.discarded
|| turn.blocked()
- || turn.cluster_id >= 0
+ || turn.is_clustered()
|| ! (turn.both(operation_union) || turn.both(operation_intersection)))
{
// Skip discarded, blocked, non-uu/ii and clustered turns
continue;
}
- if (OverlayType == overlay_buffer)
- {
- // For deflate, the region approach does not work because many
- // pieces are outside the real polygons
- // TODO: implement this in another way for buffer
- // (because now buffer might output invalid geometries)
- continue;
- }
- int const region0 = get_region_id(turn.operations[0]);
- int const region1 = get_region_id(turn.operations[1]);
+ signed_size_type const region0 = get_region_id(turn.operations[0]);
+ signed_size_type const region1 = get_region_id(turn.operations[1]);
// Switch sources for same region
turn.switch_source = region0 == region1;
@@ -529,7 +644,7 @@ struct traversal_switch_detector
turn_type const& turn = m_turns[turn_index];
if ((turn.both(operation_union) || turn.both(operation_intersection))
- && turn.cluster_id < 0)
+ && ! turn.is_clustered())
{
std::cout << "UU/II SWITCH RESULT "
<< turn_index << " -> "
diff --git a/boost/geometry/algorithms/detail/overlay/traverse.hpp b/boost/geometry/algorithms/detail/overlay/traverse.hpp
index 058f6c9458..b9cbea3127 100644
--- a/boost/geometry/algorithms/detail/overlay/traverse.hpp
+++ b/boost/geometry/algorithms/detail/overlay/traverse.hpp
@@ -62,14 +62,16 @@ public :
typename RobustPolicy,
typename Turns,
typename Rings,
- typename Visitor,
- typename Clusters
+ typename TurnInfoMap,
+ typename Clusters,
+ typename Visitor
>
static inline void apply(Geometry1 const& geometry1,
Geometry2 const& geometry2,
IntersectionStrategy const& intersection_strategy,
RobustPolicy const& robust_policy,
Turns& turns, Rings& rings,
+ TurnInfoMap& turn_info_map,
Clusters& clusters,
Visitor& visitor)
{
@@ -89,11 +91,11 @@ public :
<
Reverse1, Reverse2, OverlayType,
Geometry1, Geometry2,
- Turns, Clusters,
+ Turns, TurnInfoMap, Clusters,
IntersectionStrategy,
RobustPolicy, Visitor,
Backtrack
- > trav(geometry1, geometry2, turns, clusters,
+ > trav(geometry1, geometry2, turns, turn_info_map, clusters,
intersection_strategy, robust_policy, visitor);
std::size_t finalized_ring_size = boost::size(rings);
diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp
index 3a4c2e94a1..3ed75cf09e 100644
--- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp
+++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp
@@ -90,12 +90,10 @@ struct turn_info
Point point;
method_type method;
bool touch_only; // True in case of method touch(interior) and lines do not cross
- signed_size_type cluster_id; // For multiple turns on same location, >= 0. Else -1
+ signed_size_type cluster_id; // For multiple turns on same location, > 0. Else -1. 0 is unused.
bool discarded;
- // TODO: move this to enriched
- bool colocated_ii; // Colocated with a ii turn (TODO: or a ix turn)
- bool colocated_uu; // Colocated with a uu turn or a ux turn
+ bool has_colocated_both; // Colocated with a uu turn (for union) or ii (other)
bool switch_source; // For u/u turns which can either switch or not
Container operations;
@@ -105,8 +103,7 @@ struct turn_info
, touch_only(false)
, cluster_id(-1)
, discarded(false)
- , colocated_ii(false)
- , colocated_uu(false)
+ , has_colocated_both(false)
, switch_source(false)
{}
@@ -138,6 +135,10 @@ struct turn_info
{
return has(operation_blocked);
}
+ inline bool is_clustered() const
+ {
+ return cluster_id > 0;
+ }
private :
inline bool has12(operation_type type1, operation_type type2) const
diff --git a/boost/geometry/algorithms/detail/relate/less.hpp b/boost/geometry/algorithms/detail/relate/less.hpp
deleted file mode 100644
index 462fcc35f1..0000000000
--- a/boost/geometry/algorithms/detail/relate/less.hpp
+++ /dev/null
@@ -1,83 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-
-// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
-
-// This file was modified by Oracle on 2014.
-// Modifications copyright (c) 2014, Oracle and/or its affiliates.
-
-// 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)
-
-// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LESS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LESS_HPP
-
-#include <boost/geometry/core/coordinate_dimension.hpp>
-#include <boost/geometry/core/coordinate_type.hpp>
-#include <boost/geometry/util/math.hpp>
-
-namespace boost { namespace geometry
-{
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace detail_dispatch { namespace relate {
-
-// TODO: Integrate it with geometry::less?
-
-template <typename Point1,
- typename Point2,
- std::size_t I = 0,
- std::size_t D = geometry::dimension<Point1>::value>
-struct less
-{
- static inline bool apply(Point1 const& left, Point2 const& right)
- {
- typename geometry::coordinate_type<Point1>::type
- cleft = geometry::get<I>(left);
- typename geometry::coordinate_type<Point2>::type
- cright = geometry::get<I>(right);
-
- if ( geometry::math::equals(cleft, cright) )
- {
- return less<Point1, Point2, I + 1, D>::apply(left, right);
- }
- else
- {
- return cleft < cright;
- }
- }
-};
-
-template <typename Point1, typename Point2, std::size_t D>
-struct less<Point1, Point2, D, D>
-{
- static inline bool apply(Point1 const&, Point2 const&)
- {
- return false;
- }
-};
-
-}} // namespace detail_dispatch::relate
-
-#endif
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace relate {
-
-struct less
-{
- template <typename Point1, typename Point2>
- inline bool operator()(Point1 const& point1, Point2 const& point2) const
- {
- return detail_dispatch::relate::less<Point1, Point2>::apply(point1, point2);
- }
-};
-
-}} // namespace detail::relate
-#endif // DOXYGEN_NO_DETAIL
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LESS_HPP
diff --git a/boost/geometry/algorithms/detail/relate/linear_areal.hpp b/boost/geometry/algorithms/detail/relate/linear_areal.hpp
index f1b4fdf81a..ddbd7d615a 100644
--- a/boost/geometry/algorithms/detail/relate/linear_areal.hpp
+++ b/boost/geometry/algorithms/detail/relate/linear_areal.hpp
@@ -260,17 +260,19 @@ struct linear_areal
if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
return;
+ typedef typename IntersectionStrategy::template point_in_geometry_strategy<Geometry1, Geometry2>::type within_strategy_type;
+ within_strategy_type const within_strategy = intersection_strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>();
boundary_checker<Geometry1> boundary_checker1(geometry1);
no_turns_la_linestring_pred
<
Geometry2,
Result,
- typename IntersectionStrategy::template point_in_geometry_strategy<Geometry1, Geometry2>::type,
+ within_strategy_type,
boundary_checker<Geometry1>,
TransposeResult
> pred1(geometry2,
result,
- intersection_strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>(),
+ within_strategy,
boundary_checker1);
for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1);
if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
diff --git a/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp b/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp
index 47c6963b87..8d5f21555c 100644
--- a/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp
+++ b/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp
@@ -121,7 +121,7 @@ struct multi_point_geometry_eb<Geometry, multi_linestring_tag>
template <typename Point>
bool apply(Point const& boundary_point)
{
- if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, relate::less()))
+ if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, geometry::less<>()))
{
m_boundary_found = true;
return false;
@@ -143,7 +143,7 @@ struct multi_point_geometry_eb<Geometry, multi_linestring_tag>
typedef typename boost::range_value<MultiPoint>::type point_type;
typedef std::vector<point_type> points_type;
points_type points(boost::begin(multi_point), boost::end(multi_point));
- std::sort(points.begin(), points.end(), relate::less());
+ std::sort(points.begin(), points.end(), geometry::less<>());
boundary_visitor<points_type> visitor(points);
tc.for_each_boundary_point(visitor);
diff --git a/boost/geometry/algorithms/detail/relate/point_point.hpp b/boost/geometry/algorithms/detail/relate/point_point.hpp
index 68d8be031e..e0bed72ba3 100644
--- a/boost/geometry/algorithms/detail/relate/point_point.hpp
+++ b/boost/geometry/algorithms/detail/relate/point_point.hpp
@@ -21,9 +21,10 @@
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
#include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
-#include <boost/geometry/algorithms/detail/relate/less.hpp>
#include <boost/geometry/algorithms/detail/relate/result.hpp>
+#include <boost/geometry/policies/compare.hpp>
+
namespace boost { namespace geometry
{
@@ -213,7 +214,9 @@ struct multipoint_multipoint
// sort points from the 1 MPt
typedef typename geometry::point_type<SortedMultiPoint>::type point_type;
std::vector<point_type> points(boost::begin(sorted_mpt), boost::end(sorted_mpt));
- std::sort(points.begin(), points.end(), less());
+
+ geometry::less<> const less = geometry::less<>();
+ std::sort(points.begin(), points.end(), less);
bool found_inside = false;
bool found_outside = false;
@@ -224,7 +227,7 @@ struct multipoint_multipoint
it != boost::end(iterated_mpt) ; ++it )
{
bool ii =
- std::binary_search(points.begin(), points.end(), *it, less());
+ std::binary_search(points.begin(), points.end(), *it, less);
if ( ii )
found_inside = true;
else
diff --git a/boost/geometry/algorithms/detail/relate/topology_check.hpp b/boost/geometry/algorithms/detail/relate/topology_check.hpp
index 654999d8fb..810466ec05 100644
--- a/boost/geometry/algorithms/detail/relate/topology_check.hpp
+++ b/boost/geometry/algorithms/detail/relate/topology_check.hpp
@@ -13,7 +13,8 @@
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
-#include <boost/geometry/algorithms/detail/relate/less.hpp>
+
+#include <boost/geometry/policies/compare.hpp>
#include <boost/geometry/util/has_nan_coordinate.hpp>
#include <boost/geometry/util/range.hpp>
@@ -214,7 +215,7 @@ private:
if (! m_endpoints.empty() )
{
- std::sort(m_endpoints.begin(), m_endpoints.end(), relate::less());
+ std::sort(m_endpoints.begin(), m_endpoints.end(), geometry::less<>());
m_has_boundary = find_odd_count(m_endpoints.begin(), m_endpoints.end());
}
@@ -224,7 +225,7 @@ private:
template <typename It, typename Point>
static inline std::size_t count_equal(It first, It last, Point const& point)
{
- std::pair<It, It> rng = std::equal_range(first, last, point, relate::less());
+ std::pair<It, It> rng = std::equal_range(first, last, point, geometry::less<>());
return (std::size_t)std::distance(rng.first, rng.second);
}
diff --git a/boost/geometry/algorithms/detail/sections/section_functions.hpp b/boost/geometry/algorithms/detail/sections/section_functions.hpp
index 67df3060c4..d283784e2c 100644
--- a/boost/geometry/algorithms/detail/sections/section_functions.hpp
+++ b/boost/geometry/algorithms/detail/sections/section_functions.hpp
@@ -19,6 +19,9 @@
#include <boost/geometry/algorithms/detail/recalculate.hpp>
#include <boost/geometry/policies/robustness/robust_point_type.hpp>
+// For spherical/geographic longitudes covered_by point/box
+#include <boost/geometry/strategies/cartesian/point_in_box.hpp>
+
namespace boost { namespace geometry
{
@@ -61,17 +64,33 @@ struct preceding_check<0, Geometry, spherical_tag>
calc_t const c0 = 0;
+ calc_t const value = get<0>(point);
+ calc_t const other_min = get<min_corner, 0>(other_box);
+ calc_t const other_max = get<max_corner, 0>(other_box);
+
+ bool const pt_covered = strategy::within::covered_by_range
+ <
+ Point, 0, spherical_tag
+ >::apply(value,
+ other_min,
+ other_max);
+
+ if (pt_covered)
+ {
+ return false;
+ }
+
if (dir == 1)
{
calc_t const diff_min = math::longitude_distance_signed
<
units_t, calc_t
- >(get<min_corner, 0>(other_box), get<0>(point));
+ >(other_min, value);
calc_t const diff_min_min = math::longitude_distance_signed
<
units_t, calc_t
- >(get<min_corner, 0>(other_box), get<min_corner, 0>(point_box));
+ >(other_min, get<min_corner, 0>(point_box));
return diff_min < c0 && diff_min_min <= c0 && diff_min_min <= diff_min;
}
@@ -80,12 +99,12 @@ struct preceding_check<0, Geometry, spherical_tag>
calc_t const diff_max = math::longitude_distance_signed
<
units_t, calc_t
- >(get<max_corner, 0>(other_box), get<0>(point));
+ >(other_max, value);
calc_t const diff_max_max = math::longitude_distance_signed
<
units_t, calc_t
- >(get<max_corner, 0>(other_box), get<max_corner, 0>(point_box));
+ >(other_max, get<max_corner, 0>(point_box));
return diff_max > c0 && diff_max_max >= c0 && diff_max <= diff_max_max;
}
diff --git a/boost/geometry/algorithms/detail/touches/implementation.hpp b/boost/geometry/algorithms/detail/touches/implementation.hpp
index 94f1fba581..0cdb8ad1d4 100644
--- a/boost/geometry/algorithms/detail/touches/implementation.hpp
+++ b/boost/geometry/algorithms/detail/touches/implementation.hpp
@@ -413,7 +413,8 @@ struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false>
#endif // DOXYGEN_NO_DISPATCH
-namespace resolve_variant {
+namespace resolve_variant
+{
template <typename Geometry>
struct self_touches
@@ -443,10 +444,11 @@ struct self_touches
detail::touches::areal_interrupt_policy policy;
strategy_type strategy;
rescale_policy_type robust_policy;
+ // TODO: skip_adjacent should be set to false
detail::self_get_turn_points::get_turns
<
false, policy_type
- >::apply(geometry, strategy, robust_policy, turns, policy, 0);
+ >::apply(geometry, strategy, robust_policy, turns, policy, 0, true);
return policy.result();
}
diff --git a/boost/geometry/algorithms/detail/within/multi_point.hpp b/boost/geometry/algorithms/detail/within/multi_point.hpp
index 7e85f33383..359853f6a4 100644
--- a/boost/geometry/algorithms/detail/within/multi_point.hpp
+++ b/boost/geometry/algorithms/detail/within/multi_point.hpp
@@ -21,7 +21,6 @@
#include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
-#include <boost/geometry/algorithms/detail/relate/less.hpp>
#include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
#include <boost/geometry/algorithms/envelope.hpp>
#include <boost/geometry/algorithms/detail/partition.hpp>
@@ -33,6 +32,8 @@
#include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/policies/compare.hpp>
+
#include <boost/geometry/strategies/covered_by.hpp>
#include <boost/geometry/strategies/disjoint.hpp>
@@ -63,7 +64,7 @@ struct multi_point_point
}
};
-// NOTE: currently the strategy is ignored, math::equals() is used inside relate::less
+// NOTE: currently the strategy is ignored, math::equals() is used inside geometry::less<>
struct multi_point_multi_point
{
template <typename MultiPoint1, typename MultiPoint2, typename Strategy>
@@ -73,7 +74,7 @@ struct multi_point_multi_point
{
typedef typename boost::range_value<MultiPoint2>::type point2_type;
- relate::less const less = relate::less();
+ geometry::less<> const less = geometry::less<>();
std::vector<point2_type> points2(boost::begin(multi_point2), boost::end(multi_point2));
std::sort(points2.begin(), points2.end(), less);
diff --git a/boost/geometry/algorithms/dispatch/expand.hpp b/boost/geometry/algorithms/dispatch/expand.hpp
index 2c23d6a1ce..c7a7696480 100644
--- a/boost/geometry/algorithms/dispatch/expand.hpp
+++ b/boost/geometry/algorithms/dispatch/expand.hpp
@@ -5,10 +5,11 @@
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
// Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France.
-// This file was modified by Oracle on 2015.
-// Modifications copyright (c) 2015, Oracle and/or its affiliates.
+// This file was modified by Oracle on 2015, 2017.
+// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, 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.
@@ -39,8 +40,6 @@ namespace dispatch
template
<
typename GeometryOut, typename Geometry,
- typename StrategyLess = strategy::compare::default_strategy,
- typename StrategyGreater = strategy::compare::default_strategy,
typename TagOut = typename tag<GeometryOut>::type,
typename Tag = typename tag<Geometry>::type,
typename CSTagOut = typename cs_tag<GeometryOut>::type,