summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/overlay
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2016-03-21 06:45:20 (GMT)
committerDongHun Kwak <dh0128.kwak@samsung.com>2016-03-21 06:46:37 (GMT)
commit733b5d5ae2c5d625211e2985ac25728ac3f54883 (patch)
treea5b214744b256f07e1dc2bd7273035a7808c659f /boost/geometry/algorithms/detail/overlay
parent08c1e93fa36a49f49325a07fe91ff92c964c2b6c (diff)
downloadboost-733b5d5ae2c5d625211e2985ac25728ac3f54883.zip
boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.tar.gz
boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.tar.bz2
Imported Upstream version 1.58.0upstream/1.58.0refs/changes/33/62933/1
Change-Id: If0072143aa26874812e0db6872e1efb10a3e5e94 Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay')
-rw-r--r--boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp7
-rw-r--r--boost/geometry/algorithms/detail/overlay/assign_parents.hpp19
-rw-r--r--boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp33
-rw-r--r--boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp59
-rw-r--r--boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp26
-rw-r--r--boost/geometry/algorithms/detail/overlay/get_turn_info.hpp111
-rw-r--r--boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp10
-rw-r--r--boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp4
-rw-r--r--boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp195
-rw-r--r--boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp78
-rw-r--r--boost/geometry/algorithms/detail/overlay/get_turns.hpp80
-rw-r--r--boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp43
-rw-r--r--boost/geometry/algorithms/detail/overlay/intersection_insert.hpp9
-rw-r--r--boost/geometry/algorithms/detail/overlay/linear_linear.hpp5
-rw-r--r--boost/geometry/algorithms/detail/overlay/overlay.hpp118
-rw-r--r--boost/geometry/algorithms/detail/overlay/ring_properties.hpp14
-rw-r--r--boost/geometry/algorithms/detail/overlay/select_rings.hpp217
-rw-r--r--boost/geometry/algorithms/detail/overlay/self_turn_points.hpp25
18 files changed, 573 insertions, 480 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp b/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp
index d44db17..285edfd 100644
--- a/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp
+++ b/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp
@@ -20,6 +20,7 @@
#include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
+#include <boost/geometry/util/condition.hpp>
#include <boost/geometry/util/range.hpp>
@@ -42,7 +43,7 @@ inline bool points_equal_or_close(Point1 const& point1,
return true;
}
- if (! RobustPolicy::enabled)
+ if (BOOST_GEOMETRY_CONDITION(! RobustPolicy::enabled))
{
return false;
}
@@ -127,7 +128,7 @@ inline void clean_closing_dups_and_spikes(Range& range,
iterator_type first = boost::begin(range);
iterator_type second = first + 1;
iterator_type ultimate = boost::end(range) - 1;
- if (closed)
+ if (BOOST_GEOMETRY_CONDITION(closed))
{
ultimate--;
}
@@ -137,7 +138,7 @@ inline void clean_closing_dups_and_spikes(Range& range,
if (point_is_spike_or_equal(*second, *ultimate, *first, robust_policy))
{
range::erase(range, first);
- if (closed)
+ if (BOOST_GEOMETRY_CONDITION(closed))
{
// Remove closing last point
range::resize(range, boost::size(range) - 1);
diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
index 67b48cc..178f382 100644
--- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
+++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
@@ -18,11 +18,6 @@
#include <boost/geometry/geometries/box.hpp>
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
-# include <boost/timer.hpp>
-#endif
-
-
namespace boost { namespace geometry
{
@@ -186,11 +181,6 @@ inline void assign_parents(Geometry1 const& geometry1,
typedef std::vector<helper> vector_type;
typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- boost::timer timer;
-#endif
-
-
std::size_t count_total = ring_map.size();
std::size_t count_positive = 0;
std::size_t index_positive = 0; // only used if count_positive>0
@@ -226,10 +216,6 @@ inline void assign_parents(Geometry1 const& geometry1,
}
}
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << " ap: created helper vector: " << timer.elapsed() << std::endl;
-#endif
-
if (! check_for_orientation)
{
if (count_positive == count_total)
@@ -272,11 +258,6 @@ inline void assign_parents(Geometry1 const& geometry1,
<
box_type, ring_info_helper_get_box, ring_info_helper_ovelaps_box
>::apply(vector, visitor);
-
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << " ap: quadradic loop: " << timer.elapsed() << std::endl;
- std::cout << " ap: check_for_orientation " << check_for_orientation << std::endl;
-#endif
}
if (check_for_orientation)
diff --git a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp
index 20a6d7f..13e0a5a 100644
--- a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp
+++ b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp
@@ -11,6 +11,7 @@
#include <boost/array.hpp>
+#include <boost/assert.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/range.hpp>
@@ -21,8 +22,7 @@
#include <boost/geometry/algorithms/convert.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
#include <boost/geometry/util/range.hpp>
-#include <boost/geometry/views/closeable_view.hpp>
-#include <boost/geometry/views/reversible_view.hpp>
+#include <boost/geometry/views/detail/normalized_view.hpp>
namespace boost { namespace geometry
@@ -37,41 +37,24 @@ namespace detail { namespace copy_segments
template <typename Range, bool Reverse, typename SegmentIdentifier, typename PointOut>
struct copy_segment_point_range
{
- typedef typename closeable_view
- <
- Range const,
- closure<Range>::value
- >::type cview_type;
-
- typedef typename reversible_view
- <
- cview_type const,
- Reverse ? iterate_reverse : iterate_forward
- >::type rview_type;
-
static inline bool apply(Range const& range,
SegmentIdentifier const& seg_id, bool second,
PointOut& point)
{
+ detail::normalized_view<Range const> view(range);
+
+ signed_index_type const n = boost::size(view);
signed_index_type index = seg_id.segment_index;
if (second)
{
index++;
- if (index >= int(boost::size(range)))
+ if (index >= n)
{
index = 0;
}
}
- // Exception?
- if (index >= int(boost::size(range)))
- {
- return false;
- }
-
- cview_type cview(range);
- rview_type view(cview);
-
+ BOOST_ASSERT(index >= 0 && index < n);
geometry::convert(*(boost::begin(view) + index), point);
return true;
@@ -323,6 +306,8 @@ inline bool copy_segment_point(Geometry1 const& geometry1, Geometry2 const& geom
concept::check<Geometry1 const>();
concept::check<Geometry2 const>();
+ BOOST_ASSERT(seg_id.source_index == 0 || seg_id.source_index == 1);
+
if (seg_id.source_index == 0)
{
return dispatch::copy_segment_point
diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
index 9484479..7ed93f5 100644
--- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
+++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
@@ -56,13 +56,13 @@ struct indexed_turn_operation
TurnOperation const* subject;
inline indexed_turn_operation(std::size_t ti, std::size_t oi,
- TurnOperation const& s,
+ TurnOperation const& sub,
segment_identifier const& oid)
: turn_index(ti)
, operation_index(oi)
, discarded(false)
, other_seg_id(&oid)
- , subject(&s)
+ , subject(boost::addressof(sub))
{}
};
@@ -114,6 +114,12 @@ private :
typedef typename geometry::point_type<Geometry1>::type point_type;
+ inline bool default_order(Indexed const& left, Indexed const& right) const
+ {
+ // We've nothing to sort on. Take the indexes
+ return left.turn_index < right.turn_index;
+ }
+
inline bool consider_relative_order(Indexed const& left,
Indexed const& right) const
{
@@ -148,7 +154,12 @@ private :
// If they both turn left: the most left as last
// If they both turn right: this is not relevant, but take also here most left
- return side_rj_s < side_sj_r;
+ if (side_rj_s != side_sj_r)
+ {
+ return side_rj_s < side_sj_r;
+ }
+
+ return default_order(left, right);
}
public :
@@ -157,30 +168,32 @@ public :
// but to the "indexed_turn_operation"
inline bool operator()(Indexed const& left, Indexed const& right) const
{
- segment_identifier const& sl = left.subject->seg_id;
- segment_identifier const& sr = right.subject->seg_id;
+ if (! (left.subject->seg_id == right.subject->seg_id))
+ {
+ return left.subject->seg_id < right.subject->seg_id;
+ }
+
+ // Both left and right are located on the SAME segment.
- if (sl == sr)
+ if (! (left.subject->fraction == right.subject->fraction))
{
- // Both left and right are located on the SAME segment.
- if (left.subject->fraction == right.subject->fraction)
- {
- // First check "real" intersection (crosses)
- // -> distance zero due to precision, solve it by sorting
- if (m_turn_points[left.turn_index].method == method_crosses
- && m_turn_points[right.turn_index].method == method_crosses)
- {
- return consider_relative_order(left, right);
- }
+ return left.subject->fraction < right.subject->fraction;
+ }
- // If that is not the case, cluster it later on.
- // Indicate that this is necessary.
- *m_clustered = true;
- }
+
+ // First check "real" intersection (crosses)
+ // -> distance zero due to precision, solve it by sorting
+ if (m_turn_points[left.turn_index].method == method_crosses
+ && m_turn_points[right.turn_index].method == method_crosses)
+ {
+ return consider_relative_order(left, right);
}
- return sl == sr
- ? left.subject->fraction < right.subject->fraction
- : sl < sr;
+
+ // If that is not the case, cluster it later on.
+ // Indicate that this is necessary.
+ *m_clustered = true;
+
+ return default_order(left, right);
}
};
diff --git a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp
index 85378e0..7bcc0b9 100644
--- a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp
+++ b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp
@@ -35,6 +35,23 @@
namespace boost { namespace geometry
{
+#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
+class inconsistent_turns_exception : public geometry::exception
+{
+public:
+
+ inline inconsistent_turns_exception() {}
+
+ virtual ~inconsistent_turns_exception() throw()
+ {}
+
+ virtual char const* what() const throw()
+ {
+ return "Boost.Geometry Inconsistent Turns exception";
+ }
+};
+#endif
+
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
@@ -304,7 +321,14 @@ public:
oit);
}
- BOOST_ASSERT( enter_count == 0 );
+#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
+ if (enter_count != 0)
+ {
+ throw inconsistent_turns_exception();
+ }
+#else
+ BOOST_ASSERT(enter_count == 0);
+#endif
return process_end(entered, linestring,
current_segment_id, current_piece,
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
index 240b6de..b3b1a06 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
@@ -2,6 +2,11 @@
// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// This file was modified by Oracle on 2015.
+// Modifications copyright (c) 2015 Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
+
// 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)
@@ -11,6 +16,8 @@
#include <boost/assert.hpp>
+#include <boost/core/ignore_unused.hpp>
+
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/strategies/intersection.hpp>
@@ -104,17 +111,19 @@ struct base_turn_handler
template <typename TurnInfo, typename IntersectionInfo>
static inline void assign_point(TurnInfo& ti,
method_type method,
- IntersectionInfo const& info, int index)
+ IntersectionInfo const& info, unsigned int index)
{
ti.method = method;
- BOOST_ASSERT(index >= 0 && unsigned(index) < info.count); // TODO remove this
+
+ BOOST_ASSERT(index < info.count);
+
geometry::convert(info.intersections[index], ti.point);
ti.operations[0].fraction = info.fractions[index].robust_ra;
ti.operations[1].fraction = info.fractions[index].robust_rb;
}
template <typename IntersectionInfo>
- static inline int non_opposite_to_index(IntersectionInfo const& info)
+ static inline unsigned int non_opposite_to_index(IntersectionInfo const& info)
{
return info.fractions[0].robust_rb < info.fractions[1].robust_rb
? 1 : 0;
@@ -132,7 +141,7 @@ struct touch_interior : public base_turn_handler
// Index: 0, P is the interior, Q is touching and vice versa
template
<
- int Index,
+ unsigned int Index,
typename Point1,
typename Point2,
typename IntersectionInfo,
@@ -155,8 +164,9 @@ struct touch_interior : public base_turn_handler
// 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR
// and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i
- static int const index_p = Index;
- static int const index_q = 1 - Index;
+ BOOST_STATIC_ASSERT(Index <= 1);
+ static unsigned int const index_p = Index;
+ static unsigned int const index_q = 1 - Index;
int const side_qi_p = dir_info.sides.template get<index_q, 0>();
int const side_qk_p = side.qk_wrt_p1();
@@ -166,7 +176,7 @@ struct touch_interior : public base_turn_handler
// Q crosses P from left->right or from right->left (test "ML1")
// Union: folow P (left->right) or Q (right->left)
// Intersection: other turn
- int index = side_qk_p == -1 ? index_p : index_q;
+ unsigned int index = side_qk_p == -1 ? index_p : index_q;
ti.operations[index].operation = operation_union;
ti.operations[1 - index].operation = operation_intersection;
return;
@@ -193,7 +203,7 @@ struct touch_interior : public base_turn_handler
// or Q turns right on the right side of P (test "MR2")
// Union: take left turn (Q if Q turns left, P if Q turns right)
// Intersection: other turn
- int index = side_qk_q == 1 ? index_q : index_p;
+ unsigned int index = side_qk_q == 1 ? index_q : index_p;
ti.operations[index].operation = operation_union;
ti.operations[1 - index].operation = operation_intersection;
}
@@ -215,10 +225,10 @@ struct touch_interior : public base_turn_handler
// Opposite direction, which is never travelled.
// If Q turns left, P continues for intersection
// If Q turns right, P continues for union
- ti.operations[Index].operation = side_qk_q == 1
+ ti.operations[index_p].operation = side_qk_q == 1
? operation_intersection
: operation_union;
- ti.operations[1 - Index].operation = operation_blocked;
+ ti.operations[index_q].operation = operation_blocked;
}
}
else
@@ -503,27 +513,25 @@ struct equal_opposite : public base_turn_handler
typename Point1,
typename Point2,
typename OutputIterator,
- typename IntersectionInfo,
- typename DirInfo
+ typename IntersectionInfo
>
static inline void apply(Point1 const& pi, Point2 const& qi,
/* by value: */ TurnInfo tp,
OutputIterator& out,
- IntersectionInfo const& intersection_info,
- DirInfo const& dir_info)
+ IntersectionInfo const& intersection_info)
{
// For equal-opposite segments, normally don't do anything.
if (AssignPolicy::include_opposite)
{
tp.method = method_equal;
- for (int i = 0; i < 2; i++)
+ for (unsigned int i = 0; i < 2; i++)
{
tp.operations[i].operation = operation_opposite;
}
- for (unsigned int i = 0; i < intersection_info.count; i++)
+ for (unsigned int i = 0; i < intersection_info.i_info().count; i++)
{
- assign_point(tp, method_none, intersection_info, i);
- AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
+ assign_point(tp, method_none, intersection_info.i_info(), i);
+ AssignPolicy::apply(tp, pi, qi, intersection_info);
*out++ = tp;
}
}
@@ -653,7 +661,7 @@ private :
template
<
- int Index,
+ unsigned int Index,
typename Point1,
typename Point2,
typename IntersectionInfo
@@ -663,8 +671,9 @@ private :
Point2 const& , Point2 const& , int side_rk_s,
TurnInfo& tp, IntersectionInfo const& intersection_info)
{
- boost::ignore_unused_variable_warning(handle_robustness);
- boost::ignore_unused_variable_warning(side_rk_s);
+ BOOST_STATIC_ASSERT(Index <= 1);
+
+ boost::ignore_unused(handle_robustness, side_rk_s);
operation_type blocked = operation_blocked;
switch(side_rk_r)
@@ -715,7 +724,6 @@ public:
typename Point2,
typename OutputIterator,
typename IntersectionInfo,
- typename DirInfo,
typename SidePolicy
>
static inline void apply(
@@ -727,10 +735,9 @@ public:
OutputIterator& out,
IntersectionInfo const& intersection_info,
- DirInfo const& dir_info,
SidePolicy const& side)
{
- apply(pi, pj, pk, qi, qj, qk, tp_model, out, intersection_info, dir_info, side, empty_transformer);
+ apply(pi, pj, pk, qi, qj, qk, tp_model, out, intersection_info, side, empty_transformer);
}
public:
@@ -740,7 +747,6 @@ public:
typename Point2,
typename OutputIterator,
typename IntersectionInfo,
- typename DirInfo,
typename SidePolicy,
typename TurnTransformer
>
@@ -752,50 +758,52 @@ public:
TurnInfo const& tp_model,
OutputIterator& out,
- IntersectionInfo const& intersection_info,
- DirInfo const& dir_info,
+ IntersectionInfo const& info,
SidePolicy const& side,
TurnTransformer turn_transformer,
bool const is_pk_valid = true, bool const is_qk_valid = true)
{
TurnInfo tp = tp_model;
+ int const p_arrival = info.d_info().arrival[0];
+ int const q_arrival = info.d_info().arrival[1];
+
// If P arrives within Q, there is a turn dependent on P
- if ( dir_info.arrival[0] == 1
+ if ( p_arrival == 1
&& is_pk_valid
- && set_tp<0>(pi, pj, pk, side.pk_wrt_p1(), true, qi, qj, side.pk_wrt_q1(), tp, intersection_info) )
+ && set_tp<0>(pi, pj, pk, side.pk_wrt_p1(), true, qi, qj, side.pk_wrt_q1(), tp, info.i_info()) )
{
turn_transformer(tp);
- AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
+ AssignPolicy::apply(tp, pi, qi, info);
*out++ = tp;
}
// If Q arrives within P, there is a turn dependent on Q
- if ( dir_info.arrival[1] == 1
+ if ( q_arrival == 1
&& is_qk_valid
- && set_tp<1>(qi, qj, qk, side.qk_wrt_q1(), false, pi, pj, side.qk_wrt_p1(), tp, intersection_info) )
+ && set_tp<1>(qi, qj, qk, side.qk_wrt_q1(), false, pi, pj, side.qk_wrt_p1(), tp, info.i_info()) )
{
turn_transformer(tp);
- AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
+ AssignPolicy::apply(tp, pi, qi, info);
*out++ = tp;
}
if (AssignPolicy::include_opposite)
{
// Handle cases not yet handled above
- if ((dir_info.arrival[1] == -1 && dir_info.arrival[0] == 0)
- || (dir_info.arrival[0] == -1 && dir_info.arrival[1] == 0))
+ if ((q_arrival == -1 && p_arrival == 0)
+ || (p_arrival == -1 && q_arrival == 0))
{
- for (int i = 0; i < 2; i++)
+ for (unsigned int i = 0; i < 2; i++)
{
tp.operations[i].operation = operation_opposite;
}
- for (unsigned int i = 0; i < intersection_info.count; i++)
+ for (unsigned int i = 0; i < info.i_info().count; i++)
{
- assign_point(tp, method_collinear, intersection_info, i);
- AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
+ assign_point(tp, method_collinear, info.i_info(), i);
+ AssignPolicy::apply(tp, pi, qi, info);
*out++ = tp;
}
}
@@ -833,7 +841,7 @@ struct crosses : public base_turn_handler
// Intersection: take Q
// Otherwise: vice versa
int const side_qi_p1 = dir_info.sides.template get<1, 0>();
- int const index = side_qi_p1 == 1 ? 0 : 1;
+ unsigned int const index = side_qi_p1 == 1 ? 0 : 1;
ti.operations[index].operation = operation_union;
ti.operations[1 - index].operation = operation_intersection;
}
@@ -867,10 +875,9 @@ struct assign_null_policy
typename Info,
typename Point1,
typename Point2,
- typename IntersectionInfo,
- typename DirInfo
+ typename IntersectionInfo
>
- static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&, DirInfo const&)
+ static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&)
{}
};
@@ -933,7 +940,7 @@ struct get_turn_info
&& inters.i_info().count > 0)
{
only_convert::apply(tp, inters.i_info());
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
break;
@@ -968,7 +975,7 @@ struct get_turn_info
tp, inters.i_info(), inters.d_info(),
swapped_side_calc);
}
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
break;
@@ -976,7 +983,7 @@ struct get_turn_info
{
crosses<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
tp, inters.i_info(), inters.d_info());
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
break;
@@ -985,7 +992,7 @@ struct get_turn_info
// Both touch (both arrive there)
touch<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
tp, inters.i_info(), inters.d_info(), inters.sides());
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
break;
@@ -997,7 +1004,7 @@ struct get_turn_info
// or collinear-and-ending at intersection point
equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
tp, inters.i_info(), inters.d_info(), inters.sides());
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
else
@@ -1007,7 +1014,7 @@ struct get_turn_info
TurnInfo,
AssignPolicy
>::apply(pi, qi,
- tp, out, inters.i_info(), inters.d_info());
+ tp, out, inters);
}
}
break;
@@ -1032,7 +1039,7 @@ struct get_turn_info
tp, inters.i_info(), inters.d_info(), inters.sides());
}
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
else
@@ -1042,7 +1049,7 @@ struct get_turn_info
TurnInfo,
AssignPolicy
>::apply(pi, pj, pk, qi, qj, qk,
- tp, out, inters.i_info(), inters.d_info(), inters.sides());
+ tp, out, inters, inters.sides());
}
}
break;
@@ -1052,7 +1059,7 @@ struct get_turn_info
if (AssignPolicy::include_degenerate)
{
only_convert::apply(tp, inters.i_info());
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
}
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp
index ca1b9d9..4a3cacb 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp
@@ -290,7 +290,7 @@ struct get_turn_info_for_endpoint
linear_intersections::ip_info const& ip_info,
TurnInfo const& tp_model,
IntersectionInfo const& inters,
- int ip_index,
+ unsigned int ip_index,
OutputIterator out)
{
#ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS_LINEAR_LINEAR
@@ -396,7 +396,7 @@ struct get_turn_info_for_endpoint
RobustPoint2 const& ri2, RobustPoint2 const& rj2, RobustPoint2 const& rk2,
bool first1, bool last1, bool first2, bool last2,
bool ip_i2, bool ip_j2, TurnInfo const& tp_model,
- IntersectionInfo const& inters, int ip_index,
+ IntersectionInfo const& inters, unsigned int ip_index,
operation_type & op1, operation_type & op2)
{
boost::ignore_unused_variable_warning(i2);
@@ -535,7 +535,7 @@ struct get_turn_info_for_endpoint
typename OutputIterator>
static inline void assign(Point1 const& pi, Point2 const& qi,
IntersectionResult const& result,
- int ip_index,
+ unsigned int ip_index,
method_type method,
operation_type op0, operation_type op1,
turn_position pos0, turn_position pos1,
@@ -585,7 +585,9 @@ struct get_turn_info_for_endpoint
}
}
- AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
+ // TODO: this should get an intersection_info, which is unavailable here
+ // Because the assign_null policy accepts any structure, we pass the result instead for now
+ AssignPolicy::apply(tp, pi, qi, result);
*out++ = tp;
}
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp
index eead0d7..e0d7510 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp
@@ -2,8 +2,8 @@
// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
-// This file was modified by Oracle on 2013, 2014.
-// Modifications copyright (c) 2013-2014 Oracle and/or its affiliates.
+// This file was modified by Oracle on 2013, 2014, 2015.
+// Modifications copyright (c) 2013-2015 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
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp
index 873567b..7194654 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp
@@ -2,18 +2,20 @@
// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
-// This file was modified by Oracle on 2013, 2014.
-// Modifications copyright (c) 2013-2014 Oracle and/or its affiliates.
+// This file was modified by Oracle on 2013, 2014, 2015.
+// Modifications copyright (c) 2013-2015 Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// 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_OVERLAY_GET_TURN_INFO_LA_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LA_HPP
+#include <boost/geometry/util/condition.hpp>
+
#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp>
@@ -28,6 +30,8 @@ namespace detail { namespace overlay {
template<typename AssignPolicy>
struct get_turn_info_linear_areal
{
+ // Currently only Linear spikes are handled
+ // Areal spikes are ignored
static const bool handle_spikes = true;
template
@@ -122,7 +126,7 @@ struct get_turn_info_linear_areal
calculate_spike_operation(tp.operations[0].operation,
inters, is_p_last);
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
@@ -135,7 +139,7 @@ struct get_turn_info_linear_areal
replace_operations_i(tp.operations[0].operation, tp.operations[1].operation);
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
break;
@@ -220,9 +224,9 @@ struct get_turn_info_linear_areal
inters, is_p_last);
// TODO: move this into the append_xxx and call for each turn?
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
- if ( ! handle_spikes
+ if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
|| ignore_spike
|| ! append_opposite_spikes<append_touches>( // for 'i' or 'c' i???
tp, inters, is_p_last, is_q_last, out) )
@@ -256,10 +260,10 @@ struct get_turn_info_linear_areal
transformer(tp);
// TODO: move this into the append_xxx and call for each turn?
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
// conditionally handle spikes
- if ( ! handle_spikes
+ if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
|| ! append_collinear_spikes(tp, inters, is_p_last, is_q_last,
method_touch, append_equal, out) )
{
@@ -273,7 +277,7 @@ struct get_turn_info_linear_areal
TurnInfo,
AssignPolicy
>::apply(pi, qi,
- tp, out, inters.i_info(), inters.d_info());
+ tp, out, inters);
}
}
}
@@ -319,10 +323,10 @@ struct get_turn_info_linear_areal
transformer(tp);
// TODO: move this into the append_xxx and call for each turn?
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
// conditionally handle spikes
- if ( ! handle_spikes
+ if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
|| ! append_collinear_spikes(tp, inters, is_p_last, is_q_last,
method_replace, version, out) )
{
@@ -336,7 +340,7 @@ struct get_turn_info_linear_areal
turn_transformer_ec<false> transformer(method_touch_interior);
// conditionally handle spikes
- if ( handle_spikes )
+ if ( BOOST_GEOMETRY_CONDITION(handle_spikes) )
{
append_opposite_spikes<append_collinear_opposite>(
tp, inters, is_p_last, is_q_last, out);
@@ -351,8 +355,9 @@ struct get_turn_info_linear_areal
TurnInfo,
AssignPolicy
>::apply(pi, pj, pk, qi, qj, qk,
- tp, out, inters.i_info(), inters.d_info(),
- inters.sides(), transformer);
+ tp, out, inters,
+ inters.sides(), transformer,
+ !is_p_last, true); // qk is always valid
}
}
}
@@ -360,7 +365,7 @@ struct get_turn_info_linear_areal
case '0' :
{
// degenerate points
- if (AssignPolicy::include_degenerate)
+ if ( BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate) )
{
only_convert::apply(tp, inters.i_info());
@@ -376,7 +381,7 @@ struct get_turn_info_linear_areal
}
// tp.operations[1].position = position_middle;
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
}
@@ -408,20 +413,37 @@ struct get_turn_info_linear_areal
if ( is_p_spike )
{
- bool going_in = false, going_out = false;
-
int const pk_q1 = inters.sides().pk_wrt_q1();
- int const pk_q2 = inters.sides().pk_wrt_q2();
+
+ bool going_in = pk_q1 < 0; // Pk on the right
+ bool going_out = pk_q1 > 0; // Pk on the left
- if ( inters.sides().qk_wrt_q1() <= 0 ) // Q turning R or C
+ int const qk_q1 = inters.sides().qk_wrt_q1();
+
+ // special cases
+ if ( qk_q1 < 0 ) // Q turning R
{
- going_in = pk_q1 < 0 && pk_q2 < 0; // Pk on the right of both
- going_out = pk_q1 > 0 || pk_q2 > 0; // Pk on the left of one of them
+ // spike on the edge point
+ // if it's already known that the spike is going out this musn't be checked
+ if ( ! going_out
+ && equals::equals_point_point(inters.rpj(), inters.rqj()) )
+ {
+ int const pk_q2 = inters.sides().pk_wrt_q2();
+ going_in = pk_q1 < 0 && pk_q2 < 0; // Pk on the right of both
+ going_out = pk_q1 > 0 || pk_q2 > 0; // Pk on the left of one of them
+ }
}
- else
+ else if ( qk_q1 > 0 ) // Q turning L
{
- going_in = pk_q1 < 0 || pk_q2 < 0; // Pk on the right of one of them
- going_out = pk_q1 > 0 && pk_q2 > 0; // Pk on the left of both
+ // spike on the edge point
+ // if it's already known that the spike is going in this musn't be checked
+ if ( ! going_in
+ && equals::equals_point_point(inters.rpj(), inters.rqj()) )
+ {
+ int const pk_q2 = inters.sides().pk_wrt_q2();
+ going_in = pk_q1 < 0 || pk_q2 < 0; // Pk on the right of one of them
+ going_out = pk_q1 > 0 && pk_q2 > 0; // Pk on the left of both
+ }
}
if ( going_in )
@@ -461,10 +483,16 @@ struct get_turn_info_linear_areal
&& inters.is_spike_p();
// TODO: throw an exception for spike in Areal?
- /*bool is_q_spike = tp.operations[1].operation == spike_op
- && ! is_q_last
- && inters.is_spike_q();*/
+ /*bool is_q_spike = tp.operations[1].operation == operation_continue
+ && inters.is_spike_q();
+ // both are collinear spikes on the same IP, we can just follow both
+ if ( is_p_spike && is_q_spike )
+ {
+ return false;
+ }
+ // spike on Linear - it's turning back on the boundary of Areal
+ else*/
if ( is_p_spike )
{
tp.method = method;
@@ -477,7 +505,18 @@ struct get_turn_info_linear_areal
return true;
}
-
+ // spike on Areal - Linear is going outside
+ /*else if ( is_q_spike )
+ {
+ tp.method = method;
+ tp.operations[0].operation = operation_union;
+ tp.operations[1].operation = operation_continue;
+ *out++ = tp;
+ *out++ = tp;
+
+ return true;
+ }*/
+
return false;
}
@@ -492,48 +531,71 @@ struct get_turn_info_linear_areal
bool is_p_last, bool /*is_q_last*/,
OutIt out)
{
- bool is_p_spike = ( Version == append_touches ?
+ static const bool is_version_touches = (Version == append_touches);
+
+ bool is_p_spike = ( is_version_touches ?
( tp.operations[0].operation == operation_continue
|| tp.operations[0].operation == operation_intersection ) : // i ???
true )
&& ! is_p_last
&& inters.is_spike_p();
+
// TODO: throw an exception for spike in Areal?
- /*bool is_q_spike = ( Version == append_touches ?
- ( tp.operations[1].operation == operation_continue
- || tp.operations[1].operation == operation_intersection ) :
- true )
- && ! is_q_last
- && inters.is_spike_q();*/
+ /*bool is_q_spike = ( ( Version == append_touches
+ && tp.operations[1].operation == operation_continue )
+ || ( Version == append_collinear_opposite
+ && tp.operations[1].operation == operation_none ) )
+ && inters.is_spike_q();
- if ( is_p_spike && ( Version == append_touches || inters.d_info().arrival[0] == 1 ) )
+ if ( is_p_spike && is_q_spike )
{
- if ( Version == append_touches )
- {
- tp.operations[0].is_collinear = true;
- //tp.operations[1].is_collinear = false;
- tp.method = method_touch;
- }
- else
+ // u/u or nothing?
+ return false;
+ }
+ else*/
+ if ( is_p_spike )
+ {
+ if ( BOOST_GEOMETRY_CONDITION(is_version_touches)
+ || inters.d_info().arrival[0] == 1 )
{
- tp.operations[0].is_collinear = true;
- //tp.operations[1].is_collinear = false;
-
- BOOST_ASSERT(inters.i_info().count > 1);
- base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1);
+ if ( BOOST_GEOMETRY_CONDITION(is_version_touches) )
+ {
+ tp.operations[0].is_collinear = true;
+ //tp.operations[1].is_collinear = false;
+ tp.method = method_touch;
+ }
+ else
+ {
+ tp.operations[0].is_collinear = true;
+ //tp.operations[1].is_collinear = false;
- AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters.i_info(), inters.d_info());
- }
+ BOOST_ASSERT(inters.i_info().count > 1);
+ base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1);
- tp.operations[0].operation = operation_blocked;
+ AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters);
+ }
+
+ tp.operations[0].operation = operation_blocked;
+ tp.operations[1].operation = operation_continue; // boundary
+ *out++ = tp;
+ tp.operations[0].operation = operation_continue; // boundary
+ //tp.operations[1].operation = operation_continue; // boundary
+ *out++ = tp;
+
+ return true;
+ }
+ }
+ /*else if ( is_q_spike )
+ {
+ tp.operations[0].is_collinear = true;
+ tp.method = is_version_touches ? method_touch : method_touch_interior;
+ tp.operations[0].operation = operation_continue;
tp.operations[1].operation = operation_continue; // boundary
*out++ = tp;
- tp.operations[0].operation = operation_continue; // boundary
- //tp.operations[1].operation = operation_continue; // boundary
*out++ = tp;
return true;
- }
+ }*/
return false;
}
@@ -587,7 +649,7 @@ struct get_turn_info_linear_areal
operation_type & op1 = turn.operations[1].operation;
// NOTE: probably only if methods are WRT IPs, not segments!
- if ( IsFront
+ if ( BOOST_GEOMETRY_CONDITION(IsFront)
|| op0 == operation_intersection || op0 == operation_union
|| op1 == operation_intersection || op1 == operation_union )
{
@@ -666,7 +728,9 @@ struct get_turn_info_linear_areal
// ANALYSE AND ASSIGN FIRST
// IP on the first point of Linear Geometry
- if ( EnableFirst && is_p_first && ip0.is_pi && !ip0.is_qi ) // !q0i prevents duplication
+ bool was_first_point_handled = false;
+ if ( BOOST_GEOMETRY_CONDITION(EnableFirst)
+ && is_p_first && ip0.is_pi && !ip0.is_qi ) // !q0i prevents duplication
{
TurnInfo tp = tp_model;
tp.operations[0].position = position_front;
@@ -735,14 +799,16 @@ struct get_turn_info_linear_areal
// here is_p_first_ip == true
tp.operations[0].is_collinear = false;
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
+
+ was_first_point_handled = true;
}
// ANALYSE AND ASSIGN LAST
// IP on the last point of Linear Geometry
- if ( EnableLast
+ if ( BOOST_GEOMETRY_CONDITION(EnableLast)
&& is_p_last
&& ( ip_count > 1 ? (ip1.is_pj && !ip1.is_qi) : (ip0.is_pj && !ip0.is_qi) ) ) // prevents duplication
{
@@ -783,13 +849,14 @@ struct get_turn_info_linear_areal
// equals<> or collinear<> will assign the second point,
// we'd like to assign the first one
- int ip_index = ip_count > 1 ? 1 : 0;
+ unsigned int ip_index = ip_count > 1 ? 1 : 0;
base_turn_handler::assign_point(tp, tp.method, inters.i_info(), ip_index);
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
- return true;
+ // don't ignore the first IP if the segment is opposite
+ return !( opposite && ip_count > 1 ) || was_first_point_handled;
}
// don't ignore anything for now
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp
index 4f03848..1ec88e5 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp
@@ -2,8 +2,8 @@
// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
-// This file was modified by Oracle on 2013, 2014.
-// Modifications copyright (c) 2013-2014 Oracle and/or its affiliates.
+// This file was modified by Oracle on 2013, 2014, 2015.
+// Modifications copyright (c) 2013-2015 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
@@ -17,6 +17,8 @@
#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp>
+#include <boost/geometry/util/condition.hpp>
+
namespace boost { namespace geometry {
#ifndef DOXYGEN_NO_DETAIL
@@ -120,7 +122,7 @@ struct get_turn_info_linear_linear
tp.operations[0].operation,
tp.operations[1].operation);
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
}
@@ -132,7 +134,7 @@ struct get_turn_info_linear_linear
replace_operations_i(tp.operations[0].operation, tp.operations[1].operation);
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
break;
@@ -260,9 +262,9 @@ struct get_turn_info_linear_linear
tp.operations[1].operation);
// TODO: move this into the append_xxx and call for each turn?
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
- if ( ! handle_spikes
+ if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
|| ! append_opposite_spikes<append_touches>(tp, inters,
is_p_last, is_q_last,
out) )
@@ -293,18 +295,24 @@ struct get_turn_info_linear_linear
equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
tp, inters.i_info(), inters.d_info(), inters.sides());
+ operation_type spike_op
+ = ( tp.operations[0].operation != operation_continue
+ || tp.operations[1].operation != operation_continue ) ?
+ operation_union :
+ operation_continue;
+
// transform turn
turn_transformer_ec transformer(method_touch);
transformer(tp);
// TODO: move this into the append_xxx and call for each turn?
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
// conditionally handle spikes
- if ( ! handle_spikes
+ if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
|| ! append_collinear_spikes(tp, inters,
is_p_last, is_q_last,
- method_touch, operation_union,
+ method_touch, spike_op,
out) )
{
*out++ = tp; // no spikes
@@ -318,7 +326,7 @@ struct get_turn_info_linear_linear
<
TurnInfo,
AssignPolicy
- >::apply(pi, qi, tp, out, inters.i_info(), inters.d_info());
+ >::apply(pi, qi, tp, out, inters);
}
}
}
@@ -351,7 +359,11 @@ struct get_turn_info_linear_linear
tp, inters.i_info(), inters.d_info(), inters.sides());
method_replace = method_touch;
- spike_op = operation_union;
+ if ( tp.operations[0].operation != operation_continue
+ || tp.operations[1].operation != operation_continue )
+ {
+ spike_op = operation_union;
+ }
}
else
{
@@ -367,10 +379,10 @@ struct get_turn_info_linear_linear
transformer(tp);
// TODO: move this into the append_xxx and call for each turn?
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
// conditionally handle spikes
- if ( ! handle_spikes
+ if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
|| ! append_collinear_spikes(tp, inters,
is_p_last, is_q_last,
method_replace, spike_op,
@@ -386,7 +398,7 @@ struct get_turn_info_linear_linear
turn_transformer_ec transformer(method_touch_interior);
// conditionally handle spikes
- if ( handle_spikes )
+ if ( BOOST_GEOMETRY_CONDITION(handle_spikes) )
{
append_opposite_spikes<append_collinear_opposite>(tp, inters,
is_p_last, is_q_last,
@@ -402,7 +414,7 @@ struct get_turn_info_linear_linear
TurnInfo,
AssignPolicy
>::apply(pi, pj, pk, qi, qj, qk,
- tp, out, inters.i_info(), inters.d_info(), inters.sides(),
+ tp, out, inters, inters.sides(),
transformer, !is_p_last, !is_q_last);
}
}
@@ -411,7 +423,7 @@ struct get_turn_info_linear_linear
case '0' :
{
// degenerate points
- if (AssignPolicy::include_degenerate)
+ if ( BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate) )
{
only_convert::apply(tp, inters.i_info());
@@ -437,7 +449,7 @@ struct get_turn_info_linear_linear
tp.operations[1].position = position_back;
}
- AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, pi, qi, inters);
*out++ = tp;
}
}
@@ -478,6 +490,14 @@ struct get_turn_info_linear_linear
if ( is_p_spike && is_q_spike )
{
+ if ( tp.method == method_equal
+ && tp.operations[0].operation == operation_continue
+ && tp.operations[1].operation == operation_continue )
+ {
+ // treat both non-opposite collinear spikes as no-spikes
+ return false;
+ }
+
tp.method = method;
tp.operations[0].operation = operation_blocked;
tp.operations[1].operation = operation_blocked;
@@ -527,13 +547,15 @@ struct get_turn_info_linear_linear
bool is_p_last, bool is_q_last,
OutIt out)
{
- bool is_p_spike = ( Version == append_touches ?
+ static const bool is_version_touches = (Version == append_touches);
+
+ bool is_p_spike = ( is_version_touches ?
( tp.operations[0].operation == operation_continue
|| tp.operations[0].operation == operation_intersection ) :
true )
&& ! is_p_last
&& inters.is_spike_p();
- bool is_q_spike = ( Version == append_touches ?
+ bool is_q_spike = ( is_version_touches ?
( tp.operations[1].operation == operation_continue
|| tp.operations[1].operation == operation_intersection ) :
true )
@@ -542,9 +564,11 @@ struct get_turn_info_linear_linear
bool res = false;
- if ( is_p_spike && ( Version == append_touches || inters.d_info().arrival[0] == 1 ) )
+ if ( is_p_spike
+ && ( BOOST_GEOMETRY_CONDITION(is_version_touches)
+ || inters.d_info().arrival[0] == 1 ) )
{
- if ( Version == append_touches )
+ if ( BOOST_GEOMETRY_CONDITION(is_version_touches) )
{
tp.operations[0].is_collinear = true;
tp.operations[1].is_collinear = false;
@@ -560,8 +584,7 @@ struct get_turn_info_linear_linear
base_turn_handler::assign_point(tp, method_touch_interior,
inters.i_info(), 1);
- AssignPolicy::apply(tp, inters.pi(), inters.qi(),
- inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters);
}
tp.operations[0].operation = operation_blocked;
@@ -574,9 +597,11 @@ struct get_turn_info_linear_linear
res = true;
}
- if ( is_q_spike && ( Version == append_touches || inters.d_info().arrival[1] == 1 ) )
+ if ( is_q_spike
+ && ( BOOST_GEOMETRY_CONDITION(is_version_touches)
+ || inters.d_info().arrival[1] == 1 ) )
{
- if ( Version == append_touches )
+ if ( BOOST_GEOMETRY_CONDITION(is_version_touches) )
{
tp.operations[0].is_collinear = false;
tp.operations[1].is_collinear = true;
@@ -591,8 +616,7 @@ struct get_turn_info_linear_linear
base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 0);
- AssignPolicy::apply(tp, inters.pi(), inters.qi(),
- inters.i_info(), inters.d_info());
+ AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters);
}
tp.operations[0].operation = operation_intersection;
diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp
index a96538c..a5d8f3f 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp
@@ -54,6 +54,7 @@
#include <boost/geometry/algorithms/detail/interior_iterator.hpp>
#include <boost/geometry/algorithms/detail/partition.hpp>
#include <boost/geometry/algorithms/detail/recalculate.hpp>
+#include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
@@ -62,8 +63,7 @@
#include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
-
-#include <boost/geometry/algorithms/expand.hpp>
+#include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
# include <sstream>
@@ -229,7 +229,7 @@ public :
// section 2: [--------------]
// section 1: |----|---|---|---|---|
for (prev1 = it1++, next1++;
- it1 != end1 && ! exceeding<0>(dir1, *prev1, sec2.bounding_box, robust_policy);
+ it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec2.bounding_box, robust_policy);
++prev1, ++it1, ++index1, ++next1, ++ndi1)
{
ever_circling_iterator<range1_iterator> nd_next1(
@@ -247,7 +247,7 @@ public :
next2++;
for (prev2 = it2++, next2++;
- it2 != end2 && ! exceeding<0>(dir2, *prev2, sec1.bounding_box, robust_policy);
+ it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec1.bounding_box, robust_policy);
++prev2, ++it2, ++index2, ++next2, ++ndi2)
{
bool skip = same_source;
@@ -299,8 +299,8 @@ public :
if (InterruptPolicy::enabled)
{
if (interrupt_policy.apply(
- std::make_pair(boost::begin(turns) + size_before,
- boost::end(turns))))
+ std::make_pair(range::pos(turns, size_before),
+ boost::end(turns))))
{
return false;
}
@@ -318,25 +318,6 @@ private :
typedef typename model::referring_segment<point1_type const> segment1_type;
typedef typename model::referring_segment<point2_type const> segment2_type;
-
- template <size_t Dim, typename Point, typename Box, typename RobustPolicy>
- static inline bool preceding(int dir, Point const& point, Box const& box, RobustPolicy const& robust_policy)
- {
- typename robust_point_type<Point, RobustPolicy>::type robust_point;
- geometry::recalculate(robust_point, point, robust_policy);
- return (dir == 1 && get<Dim>(robust_point) < get<min_corner, Dim>(box))
- || (dir == -1 && get<Dim>(robust_point) > get<max_corner, Dim>(box));
- }
-
- template <size_t Dim, typename Point, typename Box, typename RobustPolicy>
- static inline bool exceeding(int dir, Point const& point, Box const& box, RobustPolicy const& robust_policy)
- {
- typename robust_point_type<Point, RobustPolicy>::type robust_point;
- geometry::recalculate(robust_point, point, robust_policy);
- return (dir == 1 && get<Dim>(robust_point) > get<max_corner, Dim>(box))
- || (dir == -1 && get<Dim>(robust_point) < get<min_corner, Dim>(box));
- }
-
template <typename Iterator, typename RangeIterator, typename Section, typename RobustPolicy>
static inline void advance_to_non_duplicate_next(Iterator& next,
RangeIterator const& it, Section const& section, RobustPolicy const& robust_policy)
@@ -387,7 +368,7 @@ private :
// Mimic section-iterator:
// Skip to point such that section interects other box
prev = it++;
- for(; it != end && preceding<0>(dir, *it, other_bounding_box, robust_policy);
+ for(; it != end && detail::section::preceding<0>(dir, *it, other_bounding_box, robust_policy);
prev = it++, index++, ndi++)
{}
// Go back one step because we want to start completely preceding
@@ -395,24 +376,6 @@ private :
}
};
-struct get_section_box
-{
- template <typename Box, typename InputItem>
- static inline void apply(Box& total, InputItem const& item)
- {
- geometry::expand(total, item.bounding_box);
- }
-};
-
-struct ovelaps_section_box
-{
- template <typename Box, typename InputItem>
- static inline bool apply(Box const& box, InputItem const& item)
- {
- return ! detail::disjoint::disjoint_box_box(box, item.bounding_box);
- }
-};
-
template
<
typename Geometry1, typename Geometry2,
@@ -496,12 +459,15 @@ public:
point_type, RobustPolicy
>::type
> box_type;
- typedef typename geometry::sections<box_type, 2> sections_type;
+ typedef geometry::sections<box_type, 2> sections_type;
sections_type sec1, sec2;
+ typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions;
- geometry::sectionalize<Reverse1>(geometry1, robust_policy, true, sec1, 0);
- geometry::sectionalize<Reverse2>(geometry2, robust_policy, true, sec2, 1);
+ geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy,
+ sec1, 0);
+ geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy,
+ sec2, 1);
// ... and then partition them, intersecting overlapping sections in visitor method
section_visitor
@@ -513,7 +479,9 @@ public:
geometry::partition
<
- box_type, get_section_box, ovelaps_section_box
+ box_type,
+ detail::section::get_section_box,
+ detail::section::overlaps_section_box
>::apply(sec1, sec2, visitor);
}
};
@@ -556,7 +524,8 @@ struct get_turns_cs
RobustPolicy const& robust_policy,
Turns& turns,
InterruptPolicy& interrupt_policy,
- int multi_index = -1, int ring_index = -1)
+ signed_index_type multi_index = -1,
+ signed_index_type ring_index = -1)
{
if ( boost::size(range) <= 1)
{
@@ -569,7 +538,8 @@ struct get_turns_cs
cview_type cview(range);
view_type view(cview);
- typename boost::range_size<view_type>::type segments_count1 = boost::size(view) - 1;
+ typedef typename boost::range_size<view_type>::type size_type;
+ size_type segments_count1 = boost::size(view) - 1;
iterator_type it = boost::begin(view);
@@ -582,7 +552,7 @@ struct get_turns_cs
//char previous_side[2] = {0, 0};
- int index = 0;
+ signed_index_type index = 0;
for (iterator_type prev = it++;
it != boost::end(view);
@@ -621,7 +591,7 @@ struct get_turns_cs
bp[0], bp[1], bp[2], bp[3],
// NOTE: some dummy values could be passed below since this would be called only for Polygons and Boxes
index == 0,
- unsigned(index) == segments_count1,
+ size_type(index) == segments_count1,
robust_policy,
turns, interrupt_policy);
// Future performance enhancement:
@@ -726,7 +696,7 @@ struct get_turns_polygon_cs
int source_id2, Box const& box,
RobustPolicy const& robust_policy,
Turns& turns, InterruptPolicy& interrupt_policy,
- int multi_index = -1)
+ signed_index_type multi_index = -1)
{
typedef typename geometry::ring_type<Polygon>::type ring_type;
@@ -744,7 +714,7 @@ struct get_turns_polygon_cs
turns, interrupt_policy,
multi_index, -1);
- int i = 0;
+ signed_index_type i = 0;
typename interior_return_type<Polygon const>::type
rings = interior_rings(polygon);
@@ -783,7 +753,7 @@ struct get_turns_multi_polygon_cs
Multi const
>::type iterator_type;
- int i = 0;
+ signed_index_type i = 0;
for (iterator_type it = boost::begin(multi);
it != boost::end(multi);
++it, ++i)
diff --git a/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp b/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp
index 085933d..277a223 100644
--- a/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp
+++ b/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp
@@ -28,6 +28,11 @@
#include <boost/geometry/geometries/segment.hpp>
+// TODO: the approach below should be completely replaced by the new
+// get_left_turns, to keep the outgoing vector which has open space one of its
+// sides.
+
+
namespace boost { namespace geometry
{
@@ -76,6 +81,12 @@ private :
RobustPolicy
>::type robust_point_type;
+ inline bool default_order(Indexed const& left, Indexed const& right) const
+ {
+ // We've nothing to sort on. Take the indexes
+ return left.turn_index < right.turn_index;
+ }
+
// Still necessary in some situations,
// for example #case_102_multi, #case_107_multi, #case_recursive_boxes_3
inline void get_situation_map(Indexed const& left, Indexed const& right,
@@ -336,7 +347,7 @@ private :
#endif
//debug_consider(0, left, right, header, false, "-> return", ret);
- return left.turn_index < right.turn_index;
+ return default_order(left, right);
}
@@ -369,11 +380,17 @@ private :
// Both located at same side (#58, pie_21_7_21_0_3)
if (side_ri_p * side_si_p == 1 && side_si_r != 0)
{
- // Take the most left one
if (left.subject->operation == operation_union
&& right.subject->operation == operation_union)
{
- bool ret = side_si_r == 1;
+ int const side_ri_s = m_strategy.apply(si, sj, ri);
+ if (side_si_r == side_ri_s)
+ {
+ return default_order(left, right);
+ }
+
+ // Take the most left one
+ bool const ret = side_si_r == 1;
//debug_consider(0, left, right, header, false, "same side", ret);
return ret;
}
@@ -407,6 +424,12 @@ private :
// One coming from left (#90, #94, #95)
if (side_si_r != 0 && (side_ri_p != 0 || side_si_p != 0))
{
+ int const side_ri_s = m_strategy.apply(si, sj, ri);
+ if (side_si_r == side_ri_s)
+ {
+ return default_order(left, right);
+ }
+
bool ret = false;
#if BOOST_GEOMETRY_HANDLE_TANGENCIES_WITH_OVERLAP_INFO
@@ -464,7 +487,7 @@ private :
return ! consider_iu_iu(right, left, header, true);
}
- return left.turn_index < right.turn_index;
+ return default_order(left, right);
}
inline bool consider_ii(Indexed const& left, Indexed const& right,
@@ -488,19 +511,17 @@ private :
bool const ret = side_si_r != 1;
return ret;
}
- return left.turn_index < right.turn_index;
+ return default_order(left, right);
}
public :
inline bool operator()(Indexed const& left, Indexed const& right) const
{
- bool const default_order = left.turn_index < right.turn_index;
-
if ((m_turn_points[left.turn_index].discarded || left.discarded)
&& (m_turn_points[right.turn_index].discarded || right.discarded))
{
- return default_order;
+ return default_order(left, right);
}
else if (m_turn_points[left.turn_index].discarded || left.discarded)
{
@@ -525,7 +546,7 @@ public :
// uu/uu, Order is arbitrary
// Note: uu/uu is discarded now before so this point will
// not be reached.
- return default_order;
+ return default_order(left, right);
}
else if (m_turn_points[left.turn_index].combination(operation_intersection, operation_union)
&& m_turn_points[right.turn_index].combination(operation_intersection, operation_union))
@@ -587,7 +608,7 @@ public :
<< std::endl;
#endif
- return default_order;
+ return default_order(left, right);
}
};
@@ -708,7 +729,7 @@ inline void handle_cluster(Iterator begin_cluster, Iterator end_cluster,
for_operation, geometry1, geometry2, strategy);
- // Then sort this range (discard rows will be ordered first and will be removed in enrich_assign)
+ // Then sort this range (discarded rows will be ordered first and will be removed in enrich_assign)
std::sort(begin_cluster, end_cluster,
sort_in_cluster
<
diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
index a13a627..3101de8 100644
--- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
+++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
@@ -43,9 +43,9 @@
#include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
#include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
-
#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
-#include <boost/foreach.hpp>
+#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
+#include <boost/geometry/io/wkt/wkt.hpp>
#endif
namespace boost { namespace geometry
@@ -254,9 +254,10 @@ struct intersection_of_linestring_with_areal
#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
int index = 0;
- BOOST_FOREACH(turn_info const& turn, turns)
+ for(typename std::deque<turn_info>::const_iterator
+ it = turns.begin(); it != turns.end(); ++it)
{
- debug_follow(turn, turn.operations[0], index++);
+ debug_follow(*it, it->operations[0], index++);
}
#endif
diff --git a/boost/geometry/algorithms/detail/overlay/linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/linear_linear.hpp
index 3a7a7a7..d4ebcf2 100644
--- a/boost/geometry/algorithms/detail/overlay/linear_linear.hpp
+++ b/boost/geometry/algorithms/detail/overlay/linear_linear.hpp
@@ -144,11 +144,10 @@ protected:
typename Info,
typename Point1,
typename Point2,
- typename IntersectionInfo,
- typename DirInfo
+ typename IntersectionInfo
>
static inline void apply(Info& , Point1 const& , Point2 const& ,
- IntersectionInfo const& , DirInfo const& )
+ IntersectionInfo const& )
{
}
};
diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp
index 44b5a0d..a2f5284 100644
--- a/boost/geometry/algorithms/detail/overlay/overlay.hpp
+++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp
@@ -44,10 +44,6 @@
# include <boost/geometry/io/dsv/write.hpp>
#endif
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
-# include <boost/timer.hpp>
-#endif
-
namespace boost { namespace geometry
{
@@ -57,19 +53,10 @@ namespace boost { namespace geometry
namespace detail { namespace overlay
{
-// Skip for assemble process
-template <typename TurnInfo>
-inline bool skip(TurnInfo const& turn_info)
-{
- return (turn_info.discarded || turn_info.both(operation_union))
- && ! turn_info.any_blocked()
- && ! turn_info.both(operation_intersection)
- ;
-}
-
-template <typename TurnPoints, typename Map>
-inline void map_turns(Map& map, TurnPoints const& turn_points)
+template <typename TurnPoints, typename TurnInfoMap>
+inline void get_ring_turn_info(TurnInfoMap& turn_info_map,
+ TurnPoints const& turn_points)
{
typedef typename boost::range_value<TurnPoints>::type turn_point_type;
typedef typename turn_point_type::container_type container_type;
@@ -79,20 +66,32 @@ inline void map_turns(Map& map, TurnPoints const& turn_points)
it != boost::end(turn_points);
++it)
{
- if (! skip(*it))
+ typename boost::range_value<TurnPoints>::type const& turn_info = *it;
+ bool both_uu = turn_info.both(operation_union);
+ bool skip = (turn_info.discarded || both_uu)
+ && ! turn_info.any_blocked()
+ && ! turn_info.both(operation_intersection)
+ ;
+
+ for (typename boost::range_iterator<container_type const>::type
+ op_it = boost::begin(turn_info.operations);
+ op_it != boost::end(turn_info.operations);
+ ++op_it)
{
- for (typename boost::range_iterator<container_type const>::type
- op_it = boost::begin(it->operations);
- op_it != boost::end(it->operations);
- ++op_it)
+ ring_identifier ring_id
+ (
+ op_it->seg_id.source_index,
+ op_it->seg_id.multi_index,
+ op_it->seg_id.ring_index
+ );
+
+ if (! skip)
{
- ring_identifier ring_id
- (
- op_it->seg_id.source_index,
- op_it->seg_id.multi_index,
- op_it->seg_id.ring_index
- );
- map[ring_id]++;
+ turn_info_map[ring_id].has_normal_turn = true;
+ }
+ else if (both_uu)
+ {
+ turn_info_map[ring_id].has_uu_turn = true;
}
}
}
@@ -137,10 +136,10 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
#endif
- std::map<ring_identifier, int> empty;
+ std::map<ring_identifier, ring_turn_info> empty;
std::map<ring_identifier, properties> all_of_one_of_them;
- select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them, false);
+ select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them);
ring_container_type rings;
assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
@@ -193,10 +192,6 @@ struct overlay
container_type turn_points;
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- boost::timer timer;
-#endif
-
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "get turns" << std::endl;
#endif
@@ -207,10 +202,6 @@ std::cout << "get turns" << std::endl;
detail::overlay::assign_null_policy
>(geometry1, geometry2, robust_policy, turn_points, policy);
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << "get_turns: " << timer.elapsed() << std::endl;
-#endif
-
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "enrich" << std::endl;
#endif
@@ -223,11 +214,6 @@ std::cout << "enrich" << std::endl;
robust_policy,
side_strategy);
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << "enrich_intersection_points: " << timer.elapsed() << std::endl;
-#endif
-
-
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "traverse" << std::endl;
#endif
@@ -245,27 +231,18 @@ std::cout << "traverse" << std::endl;
turn_points, rings
);
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << "traverse: " << timer.elapsed() << std::endl;
-#endif
-
-
- std::map<ring_identifier, int> map;
- map_turns(map, turn_points);
-
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << "map_turns: " << timer.elapsed() << std::endl;
-#endif
-
- typedef ring_properties<typename geometry::point_type<GeometryOut>::type> properties;
-
- std::map<ring_identifier, properties> selected;
- select_rings<Direction>(geometry1, geometry2, map, selected, ! turn_points.empty());
+ std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
+ get_ring_turn_info(turn_info_per_ring, turn_points);
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << "select_rings: " << timer.elapsed() << std::endl;
-#endif
+ typedef ring_properties
+ <
+ typename geometry::point_type<GeometryOut>::type
+ > properties;
+ // Select all rings which are NOT touched by any intersection point
+ std::map<ring_identifier, properties> selected_ring_properties;
+ select_rings<Direction>(geometry1, geometry2, turn_info_per_ring,
+ selected_ring_properties);
// Add rings created during traversal
{
@@ -275,24 +252,15 @@ std::cout << "traverse" << std::endl;
it != boost::end(rings);
++it)
{
- selected[id] = properties(*it, true);
- selected[id].reversed = ReverseOut;
+ selected_ring_properties[id] = properties(*it);
+ selected_ring_properties[id].reversed = ReverseOut;
id.multi_index++;
}
}
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << "add traversal rings: " << timer.elapsed() << std::endl;
-#endif
-
-
- assign_parents(geometry1, geometry2, rings, selected);
-
-#ifdef BOOST_GEOMETRY_TIME_OVERLAY
- std::cout << "assign_parents: " << timer.elapsed() << std::endl;
-#endif
+ assign_parents(geometry1, geometry2, rings, selected_ring_properties);
- return add_rings<GeometryOut>(selected, geometry1, geometry2, rings, out);
+ return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out);
}
};
diff --git a/boost/geometry/algorithms/detail/overlay/ring_properties.hpp b/boost/geometry/algorithms/detail/overlay/ring_properties.hpp
index a608869..b469052 100644
--- a/boost/geometry/algorithms/detail/overlay/ring_properties.hpp
+++ b/boost/geometry/algorithms/detail/overlay/ring_properties.hpp
@@ -33,8 +33,7 @@ struct ring_properties
Point point;
area_type area;
- // Filled by "update_selection_map"
- int within_code;
+ // Filled by "update_ring_selection"
bool reversed;
// Filled/used by "assign_rings"
@@ -45,21 +44,22 @@ struct ring_properties
inline ring_properties()
: area(area_type())
- , within_code(-1)
, reversed(false)
, discarded(false)
, parent_area(-1)
{}
template <typename RingOrBox>
- inline ring_properties(RingOrBox const& ring_or_box, bool midpoint)
- : within_code(-1)
- , reversed(false)
+ inline ring_properties(RingOrBox const& ring_or_box)
+ : reversed(false)
, discarded(false)
, parent_area(-1)
{
this->area = geometry::area(ring_or_box);
- geometry::point_on_border(this->point, ring_or_box, midpoint);
+ // We should take a point somewhere in the middle of the ring,
+ // to avoid taking a point on a (self)tangency,
+ // in cases where multiple points come together
+ geometry::point_on_border(this->point, ring_or_box, true);
}
inline area_type get_area() const
diff --git a/boost/geometry/algorithms/detail/overlay/select_rings.hpp b/boost/geometry/algorithms/detail/overlay/select_rings.hpp
index 385658a..d18e012 100644
--- a/boost/geometry/algorithms/detail/overlay/select_rings.hpp
+++ b/boost/geometry/algorithms/detail/overlay/select_rings.hpp
@@ -1,6 +1,6 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
// Use, modification and distribution is subject to the Boost Software License,
@@ -20,7 +20,6 @@
#include <boost/geometry/algorithms/area.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/algorithms/detail/interior_iterator.hpp>
-#include <boost/geometry/algorithms/detail/point_on_border.hpp>
#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
@@ -34,6 +33,18 @@ namespace boost { namespace geometry
namespace detail { namespace overlay
{
+struct ring_turn_info
+{
+ bool has_uu_turn;
+ bool has_normal_turn;
+ bool within_other;
+
+ ring_turn_info()
+ : has_uu_turn(false)
+ , has_normal_turn(false)
+ , within_other(false)
+ {}
+};
namespace dispatch
{
@@ -45,41 +56,41 @@ namespace dispatch
template <typename Box>
struct select_rings<box_tag, Box>
{
- template <typename Geometry, typename Map>
+ template <typename Geometry, typename RingPropertyMap>
static inline void apply(Box const& box, Geometry const& ,
- ring_identifier const& id, Map& map, bool midpoint)
+ ring_identifier const& id, RingPropertyMap& ring_properties)
{
- map[id] = typename Map::mapped_type(box, midpoint);
+ ring_properties[id] = typename RingPropertyMap::mapped_type(box);
}
- template <typename Map>
+ template <typename RingPropertyMap>
static inline void apply(Box const& box,
- ring_identifier const& id, Map& map, bool midpoint)
+ ring_identifier const& id, RingPropertyMap& ring_properties)
{
- map[id] = typename Map::mapped_type(box, midpoint);
+ ring_properties[id] = typename RingPropertyMap::mapped_type(box);
}
};
template <typename Ring>
struct select_rings<ring_tag, Ring>
{
- template <typename Geometry, typename Map>
+ template <typename Geometry, typename RingPropertyMap>
static inline void apply(Ring const& ring, Geometry const& ,
- ring_identifier const& id, Map& map, bool midpoint)
+ ring_identifier const& id, RingPropertyMap& ring_properties)
{
if (boost::size(ring) > 0)
{
- map[id] = typename Map::mapped_type(ring, midpoint);
+ ring_properties[id] = typename RingPropertyMap::mapped_type(ring);
}
}
- template <typename Map>
+ template <typename RingPropertyMap>
static inline void apply(Ring const& ring,
- ring_identifier const& id, Map& map, bool midpoint)
+ ring_identifier const& id, RingPropertyMap& ring_properties)
{
if (boost::size(ring) > 0)
{
- map[id] = typename Map::mapped_type(ring, midpoint);
+ ring_properties[id] = typename RingPropertyMap::mapped_type(ring);
}
}
};
@@ -88,14 +99,14 @@ namespace dispatch
template <typename Polygon>
struct select_rings<polygon_tag, Polygon>
{
- template <typename Geometry, typename Map>
+ template <typename Geometry, typename RingPropertyMap>
static inline void apply(Polygon const& polygon, Geometry const& geometry,
- ring_identifier id, Map& map, bool midpoint)
+ ring_identifier id, RingPropertyMap& ring_properties)
{
typedef typename geometry::ring_type<Polygon>::type ring_type;
typedef select_rings<ring_tag, ring_type> per_ring;
- per_ring::apply(exterior_ring(polygon), geometry, id, map, midpoint);
+ per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties);
typename interior_return_type<Polygon const>::type
rings = interior_rings(polygon);
@@ -103,18 +114,18 @@ namespace dispatch
it = boost::begin(rings); it != boost::end(rings); ++it)
{
id.ring_index++;
- per_ring::apply(*it, geometry, id, map, midpoint);
+ per_ring::apply(*it, geometry, id, ring_properties);
}
}
- template <typename Map>
+ template <typename RingPropertyMap>
static inline void apply(Polygon const& polygon,
- ring_identifier id, Map& map, bool midpoint)
+ ring_identifier id, RingPropertyMap& ring_properties)
{
typedef typename geometry::ring_type<Polygon>::type ring_type;
typedef select_rings<ring_tag, ring_type> per_ring;
- per_ring::apply(exterior_ring(polygon), id, map, midpoint);
+ per_ring::apply(exterior_ring(polygon), id, ring_properties);
typename interior_return_type<Polygon const>::type
rings = interior_rings(polygon);
@@ -122,7 +133,7 @@ namespace dispatch
it = boost::begin(rings); it != boost::end(rings); ++it)
{
id.ring_index++;
- per_ring::apply(*it, id, map, midpoint);
+ per_ring::apply(*it, id, ring_properties);
}
}
};
@@ -130,9 +141,9 @@ namespace dispatch
template <typename Multi>
struct select_rings<multi_polygon_tag, Multi>
{
- template <typename Geometry, typename Map>
+ template <typename Geometry, typename RingPropertyMap>
static inline void apply(Multi const& multi, Geometry const& geometry,
- ring_identifier id, Map& map, bool midpoint)
+ ring_identifier id, RingPropertyMap& ring_properties)
{
typedef typename boost::range_iterator
<
@@ -145,7 +156,7 @@ namespace dispatch
for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
{
id.ring_index = -1;
- per_polygon::apply(*it, geometry, id, map, midpoint);
+ per_polygon::apply(*it, geometry, id, ring_properties);
id.multi_index++;
}
}
@@ -161,14 +172,12 @@ struct decide
template<>
struct decide<overlay_union>
{
- template <typename Code>
- static bool include(ring_identifier const& , Code const& code)
+ static bool include(ring_identifier const& , ring_turn_info const& info)
{
- return code.within_code * -1 == 1;
+ return info.has_uu_turn || ! info.within_other;
}
- template <typename Code>
- static bool reversed(ring_identifier const& , Code const& )
+ static bool reversed(ring_identifier const& , ring_turn_info const& )
{
return false;
}
@@ -177,31 +186,43 @@ struct decide<overlay_union>
template<>
struct decide<overlay_difference>
{
- template <typename Code>
- static bool include(ring_identifier const& id, Code const& code)
+ static bool include(ring_identifier const& id, ring_turn_info const& info)
{
- bool is_first = id.source_index == 0;
- return code.within_code * -1 * (is_first ? 1 : -1) == 1;
+ // Difference: A - B
+
+ // If this is A (source_index=0) and there is only a u/u turn,
+ // then the ring is inside B
+ // If this is B (source_index=1) and there is only a u/u turn,
+ // then the ring is NOT inside A
+
+ // If this is A and the ring is within the other geometry,
+ // then we should NOT include it.
+ // If this is B then we SHOULD include it.
+
+ bool const is_first = id.source_index == 0;
+ bool const within_other = info.within_other
+ || (is_first && info.has_uu_turn);
+ return is_first ? ! within_other : within_other;
}
- template <typename Code>
- static bool reversed(ring_identifier const& id, Code const& code)
+ static bool reversed(ring_identifier const& id, ring_turn_info const& info)
{
- return include(id, code) && id.source_index == 1;
+ // Difference: A - B
+ // If this is B, and the ring is included, it should be reversed afterwards
+
+ return id.source_index == 1 && include(id, info);
}
};
template<>
struct decide<overlay_intersection>
{
- template <typename Code>
- static bool include(ring_identifier const& , Code const& code)
+ static bool include(ring_identifier const& , ring_turn_info const& info)
{
- return code.within_code * 1 == 1;
+ return ! info.has_uu_turn && info.within_other;
}
- template <typename Code>
- static bool reversed(ring_identifier const& , Code const& )
+ static bool reversed(ring_identifier const& , ring_turn_info const& )
{
return false;
}
@@ -211,61 +232,60 @@ struct decide<overlay_intersection>
template
<
overlay_type OverlayType,
- typename Geometry1, typename Geometry2,
- typename IntersectionMap, typename SelectionMap
+ typename Geometry1,
+ typename Geometry2,
+ typename TurnInfoMap,
+ typename RingPropertyMap
>
-inline void update_selection_map(Geometry1 const& geometry1,
+inline void update_ring_selection(Geometry1 const& geometry1,
Geometry2 const& geometry2,
- IntersectionMap const& intersection_map,
- SelectionMap const& map_with_all, SelectionMap& selection_map)
+ TurnInfoMap const& turn_info_map,
+ RingPropertyMap const& all_ring_properties,
+ RingPropertyMap& selected_ring_properties)
{
- selection_map.clear();
+ selected_ring_properties.clear();
- for (typename SelectionMap::const_iterator it = boost::begin(map_with_all);
- it != boost::end(map_with_all);
+ for (typename RingPropertyMap::const_iterator it = boost::begin(all_ring_properties);
+ it != boost::end(all_ring_properties);
++it)
{
- /*
- int union_code = it->second.within_code * -1;
- bool is_first = it->first.source_index == 0;
- std::cout << it->first << " " << it->second.area
- << ": " << it->second.within_code
- << " union: " << union_code
- << " intersection: " << (it->second.within_code * 1)
- << " G1-G2: " << (union_code * (is_first ? 1 : -1))
- << " G2-G1: " << (union_code * (is_first ? -1 : 1))
- << " -> " << (decide<OverlayType>::include(it->first, it->second) ? "INC" : "")
- << decide<OverlayType>::reverse(it->first, it->second)
- << std::endl;
- */
-
- bool found = intersection_map.find(it->first) != intersection_map.end();
- if (! found)
+ ring_identifier const& id = it->first;
+
+ ring_turn_info info;
+
+ typename TurnInfoMap::const_iterator tcit = turn_info_map.find(id);
+ if (tcit != turn_info_map.end())
{
- ring_identifier const id = it->first;
- typename SelectionMap::mapped_type properties = it->second; // Copy by value
+ info = tcit->second; // Copy by value
+ }
- // Calculate the "within code" (previously this was done earlier but is
- // much efficienter here - it can be even more efficient doing it all at once,
- // using partition, TODO)
- // So though this is less elegant than before, it avoids many unused point-in-poly calculations
+ if (info.has_normal_turn)
+ {
+ // There are normal turns on this ring. It should be traversed, we
+ // don't include the original ring
+ continue;
+ }
+
+ if (! info.has_uu_turn)
+ {
+ // Check if the ring is within the other geometry, by taking
+ // a point lying on the ring
switch(id.source_index)
{
case 0 :
- properties.within_code
- = geometry::within(properties.point, geometry2) ? 1 : -1;
+ info.within_other = geometry::within(it->second.point, geometry2);
break;
case 1 :
- properties.within_code
- = geometry::within(properties.point, geometry1) ? 1 : -1;
+ info.within_other = geometry::within(it->second.point, geometry1);
break;
}
+ }
- if (decide<OverlayType>::include(id, properties))
- {
- properties.reversed = decide<OverlayType>::reversed(id, properties);
- selection_map[id] = properties;
- }
+ if (decide<OverlayType>::include(id, info))
+ {
+ typename RingPropertyMap::mapped_type properties = it->second; // Copy by value
+ properties.reversed = decide<OverlayType>::reversed(id, info);
+ selected_ring_properties[id] = properties;
}
}
}
@@ -277,44 +297,47 @@ inline void update_selection_map(Geometry1 const& geometry1,
template
<
overlay_type OverlayType,
- typename Geometry1, typename Geometry2,
- typename IntersectionMap, typename SelectionMap
+ typename Geometry1,
+ typename Geometry2,
+ typename RingTurnInfoMap,
+ typename RingPropertyMap
>
inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
- IntersectionMap const& intersection_map,
- SelectionMap& selection_map, bool midpoint)
+ RingTurnInfoMap const& turn_info_per_ring,
+ RingPropertyMap& selected_ring_properties)
{
typedef typename geometry::tag<Geometry1>::type tag1;
typedef typename geometry::tag<Geometry2>::type tag2;
- SelectionMap map_with_all;
+ RingPropertyMap all_ring_properties;
dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
- ring_identifier(0, -1, -1), map_with_all, midpoint);
+ ring_identifier(0, -1, -1), all_ring_properties);
dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
- ring_identifier(1, -1, -1), map_with_all, midpoint);
+ ring_identifier(1, -1, -1), all_ring_properties);
- update_selection_map<OverlayType>(geometry1, geometry2, intersection_map,
- map_with_all, selection_map);
+ update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring,
+ all_ring_properties, selected_ring_properties);
}
template
<
overlay_type OverlayType,
typename Geometry,
- typename IntersectionMap, typename SelectionMap
+ typename RingTurnInfoMap,
+ typename RingPropertyMap
>
inline void select_rings(Geometry const& geometry,
- IntersectionMap const& intersection_map,
- SelectionMap& selection_map, bool midpoint)
+ RingTurnInfoMap const& turn_info_per_ring,
+ RingPropertyMap& selected_ring_properties)
{
typedef typename geometry::tag<Geometry>::type tag;
- SelectionMap map_with_all;
+ RingPropertyMap all_ring_properties;
dispatch::select_rings<tag, Geometry>::apply(geometry,
- ring_identifier(0, -1, -1), map_with_all, midpoint);
+ ring_identifier(0, -1, -1), all_ring_properties);
- update_selection_map<OverlayType>(geometry, geometry, intersection_map,
- map_with_all, selection_map);
+ update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring,
+ all_ring_properties, selected_ring_properties);
}
diff --git a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
index 8dffeae..b1f984f 100644
--- a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
+++ b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
@@ -23,9 +23,12 @@
#include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
#include <boost/geometry/algorithms/detail/partition.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
#include <boost/geometry/geometries/box.hpp>
+#include <boost/geometry/util/condition.hpp>
+
namespace boost { namespace geometry
{
@@ -96,7 +99,7 @@ struct self_section_visitor
m_rescale_policy,
m_turns, m_interrupt_policy);
}
- if (m_interrupt_policy.has_intersections)
+ if (BOOST_GEOMETRY_CONDITION(m_interrupt_policy.has_intersections))
{
// TODO: we should give partition an interrupt policy.
// Now we throw, and catch below, to stop the partition loop.
@@ -121,15 +124,19 @@ struct get_turns
{
typedef model::box
<
- typename geometry::point_type<Geometry>::type
+ typename geometry::robust_point_type
+ <
+ typename geometry::point_type<Geometry>::type,
+ RobustPolicy
+ >::type
> box_type;
- typedef typename geometry::sections
- <
- box_type, 1
- > sections_type;
+
+ typedef geometry::sections<box_type, 1> sections_type;
+
+ typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
sections_type sec;
- geometry::sectionalize<false>(geometry, robust_policy, false, sec);
+ geometry::sectionalize<false, dimensions>(geometry, robust_policy, sec);
self_section_visitor
<
@@ -142,8 +149,8 @@ struct get_turns
geometry::partition
<
box_type,
- detail::get_turns::get_section_box,
- detail::get_turns::ovelaps_section_box
+ detail::section::get_section_box,
+ detail::section::overlaps_section_box
>::apply(sec, visitor);
}
catch(self_ip_exception const& )