Subject: [Boost-commit] svn:boost r75684 - trunk/boost/geometry/algorithms/detail/overlay
From: barend.gehrels_at_[hidden]
Date: 2011-11-27 05:44:23
Author: barendgehrels
Date: 2011-11-27 05:44:22 EST (Sun, 27 Nov 2011)
New Revision: 75684
URL: http://svn.boost.org/trac/boost/changeset/75684
Log:
Linestring/polygon overlay, fix for gcc (and probably more): extracted subclass
Text files modified:
trunk/boost/geometry/algorithms/detail/overlay/follow.hpp | 336 +++++++++++++++++++++++----------------
1 files changed, 200 insertions(+), 136 deletions(-)
Modified: trunk/boost/geometry/algorithms/detail/overlay/follow.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/follow.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/follow.hpp 2011-11-27 05:44:22 EST (Sun, 27 Nov 2011)
@@ -29,174 +29,236 @@
namespace detail { namespace overlay
{
+namespace following
+{
+template <typename Turn, typename Operation>
+static inline bool is_entering(Turn const& turn, Operation const& op)
+{
+ // (Blocked means: blocked for polygon/polygon intersection, because
+ // they are reversed. But for polygon/line it is similar to continue)
+ return op.operation == operation_intersection
+ || op.operation == operation_continue
+ || op.operation == operation_blocked
+ ;
+}
-/*!
-\brief Follows a linestring from intersection point to intersection point, outputting which
- is inside, or outside, a ring or polygon
-\ingroup overlay
- */
-template
+template
<
- typename LineStringOut,
- typename LineString,
- typename Polygon,
- overlay_type OverlayType
+ typename Turn,
+ typename Operation,
+ typename LineString,
+ typename Polygon
>
-class follow
+static inline bool is_leaving(Turn const& turn, Operation const& op,
+ bool entered, bool first,
+ LineString const& linestring, Polygon const& polygon)
{
-
- template<typename Turn>
- struct sort_on_segment
+ if (op.operation == operation_union)
{
- inline bool operator()(Turn const& left, Turn const& right) const
- {
- segment_identifier const& sl = left.operations[0].seg_id;
- segment_identifier const& sr = right.operations[0].seg_id;
-
- return sl == sr
- ? left.operations[0].enriched.distance < right.operations[0].enriched.distance
- : sl < sr;
+ return entered
+ || turn.method == method_crosses
+ || (first && geometry::within(linestring[0], polygon))
+ ;
+ }
+ return false;
+}
- }
- };
- template <typename Turn, typename Operation>
- static inline bool is_entering(Turn const& turn, Operation const& op)
+template
+<
+ typename Turn,
+ typename Operation,
+ typename LineString,
+ typename Polygon
+>
+static inline bool is_staying_inside(Turn const& turn, Operation const& op,
+ bool entered, bool first,
+ LineString const& linestring, Polygon const& polygon)
+{
+ if (turn.method == method_crosses)
{
- // (Blocked means: blocked for polygon/polygon intersection, because
- // they are reversed. But for polygon/line it is similar to continue)
- return op.operation == operation_intersection
- || op.operation == operation_continue
- || op.operation == operation_blocked
- ;
+ // The normal case, this is completely covered with entering/leaving
+ // so stay out of this time consuming "within"
+ return false;
}
- template <typename Turn, typename Operation>
- static inline bool is_leaving(Turn const& turn, Operation const& op,
- bool entered, bool first,
- LineString const& linestring, Polygon const& polygon)
+ if (is_entering(turn, op))
{
- if (op.operation == operation_union)
- {
- return entered
- || turn.method == method_crosses
- || (first && geometry::within(linestring[0], polygon))
- ;
- }
- return false;
+ return entered || (first && geometry::within(linestring[0], polygon));
}
+ return false;
+}
- template <typename Turn, typename Operation>
- static inline bool is_staying_inside(Turn const& turn, Operation const& op,
- bool entered, bool first,
- LineString const& linestring, Polygon const& polygon)
+template <typename Turn>
+static inline bool was_entered(Turn const& turn, bool first)
+{
+ if (first && (turn.method == method_collinear || turn.method == method_equal))
{
- if (turn.method == method_crosses)
- {
- // The normal case, this is completely covered with entering/leaving
- // so stay out of this time consuming "within"
- return false;
- }
+ // If it is the very first point, and either equal or collinear, there is only one
+ // IP generated (on purpose). So consider this as having entered.
+ // Maybe it will leave immediately after that (u/i) but that is checked later.
+ return true;
+ }
+ return false;
+}
- if (is_entering(turn, op))
- {
- return entered || (first && geometry::within(linestring[0], polygon));
- }
- return false;
+// Template specialization structure to call the right actions for the right type
+template<overlay_type OverlayType>
+struct action_selector
+{
+ // If you get here the overlay type is not intersection or difference
+ BOOST_MPL_ASSERT(false);
+};
+
+// Specialization for intersection, containing the implementation
+template<>
+struct action_selector<overlay_intersection>
+{
+ template
+ <
+ typename OutputIterator,
+ typename LineStringOut,
+ typename LineString,
+ typename Point,
+ typename Operation
+ >
+ static inline void enter(LineStringOut& current_piece,
+ LineString const& linestring,
+ segment_identifier& segment_id,
+ int index, Point const& point,
+ Operation const& operation, OutputIterator& out)
+ {
+ // On enter, append the intersection point and remember starting point
+ detail::overlay::append_no_duplicates(current_piece, point);
+ segment_id = operation.seg_id;
}
- template <typename Turn>
- static inline bool was_entered(Turn const& turn, bool first)
+ template
+ <
+ typename OutputIterator,
+ typename LineStringOut,
+ typename LineString,
+ typename Point,
+ typename Operation
+ >
+ static inline void leave(LineStringOut& current_piece,
+ LineString const& linestring,
+ segment_identifier& segment_id,
+ int index, Point const& point,
+ Operation const& operation, OutputIterator& out)
{
- if (first && (turn.method == method_collinear || turn.method == method_equal))
+ // On leave, copy all segments from starting point, append the intersection point
+ // and add the output piece
+ geometry::copy_segments<false>(linestring, segment_id, index, current_piece);
+ detail::overlay::append_no_duplicates(current_piece, point);
+ if (! current_piece.empty())
{
- // If it is the very first point, and either equal or collinear, there is only one
- // IP generated (on purpose). So consider this as having entered.
- // Maybe it will leave immediately after that (u/i) but that is checked later.
- return true;
+ *out++ = current_piece;
+ current_piece.clear();
}
- return false;
}
- // Template specialization structure to call the right actions for the right type
- template<overlay_type OverlayType>
- struct action_selector
+ static inline bool is_entered(bool entered)
{
- // If you get here the overlay type is not intersection or difference
- BOOST_MPL_ASSERT(false);
- };
+ return entered;
+ }
- // Specialization for intersection, containing the implementation
- template<>
- struct action_selector<overlay_intersection>
+ template <typename Point, typename Geometry>
+ static inline bool included(Point const& point, Geometry const& geometry)
{
- template<typename OutputIterator, typename Point, typename Operation>
- static inline void enter(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, int index, Point const& point, Operation const& operation, OutputIterator& out)
- {
- // On enter, append the intersection point and remember starting point
- detail::overlay::append_no_duplicates(current_piece, point);
- segment_id = operation.seg_id;
- }
+ return geometry::within(point, geometry);
+ }
- template<typename OutputIterator, typename Point, typename Operation>
- static inline void leave(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, int index, Point const& point, Operation const& operation, OutputIterator& out)
- {
- // On leave, copy all segments from starting point, append the intersection point
- // and add the output piece
- geometry::copy_segments<false>(linestring, segment_id, index, current_piece);
- detail::overlay::append_no_duplicates(current_piece, point);
- if (! current_piece.empty())
- {
- *out++ = current_piece;
- current_piece.clear();
- }
- }
+};
- static inline bool is_entered(bool entered)
- {
- return entered;
- }
+// Specialization for difference, which reverses these actions
+template<>
+struct action_selector<overlay_difference>
+{
+ typedef action_selector<overlay_intersection> normal_action;
- template <typename Point, typename Geometry>
- static inline bool included(Point const& point, Geometry const& geometry)
- {
- return geometry::within(point, geometry);
- }
+ template
+ <
+ typename OutputIterator,
+ typename LineStringOut,
+ typename LineString,
+ typename Point,
+ typename Operation
+ >
+ static inline void enter(LineStringOut& current_piece,
+ LineString const& linestring,
+ segment_identifier& segment_id,
+ int index, Point const& point,
+ Operation const& operation, OutputIterator& out)
+ {
+ normal_action::leave(current_piece, linestring, segment_id, index,
+ point, operation, out);
+ }
- };
+ template
+ <
+ typename OutputIterator,
+ typename LineStringOut,
+ typename LineString,
+ typename Point,
+ typename Operation
+ >
+ static inline void leave(LineStringOut& current_piece,
+ LineString const& linestring,
+ segment_identifier& segment_id,
+ int index, Point const& point,
+ Operation const& operation, OutputIterator& out)
+ {
+ normal_action::enter(current_piece, linestring, segment_id, index,
+ point, operation, out);
+ }
- // Specialization for difference, which reverses these actions
- template<>
- struct action_selector<overlay_difference>
+ static inline bool is_entered(bool entered)
{
- typedef action_selector<overlay_intersection> normal_action;
+ return ! normal_action::is_entered(entered);
+ }
- template<typename OutputIterator, typename Point, typename Operation>
- static inline void enter(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, int index, Point const& point, Operation const& operation, OutputIterator& out)
- {
- normal_action::leave(current_piece, linestring, segment_id, index, point, operation, out);
- }
+ template <typename Point, typename Geometry>
+ static inline bool included(Point const& point, Geometry const& geometry)
+ {
+ return ! normal_action::included(point, geometry);
+ }
- template<typename OutputIterator, typename Point, typename Operation>
- static inline void leave(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, int index, Point const& point, Operation const& operation, OutputIterator& out)
- {
- normal_action::enter(current_piece, linestring, segment_id, index, point, operation, out);
- }
+};
- static inline bool is_entered(bool entered)
- {
- return ! normal_action::is_entered(entered);
- }
+}
- template <typename Point, typename Geometry>
- static inline bool included(Point const& point, Geometry const& geometry)
+/*!
+\brief Follows a linestring from intersection point to intersection point, outputting which
+ is inside, or outside, a ring or polygon
+\ingroup overlay
+ */
+template
+<
+ typename LineStringOut,
+ typename LineString,
+ typename Polygon,
+ overlay_type OverlayType
+>
+class follow
+{
+
+ template<typename Turn>
+ struct sort_on_segment
+ {
+ inline bool operator()(Turn const& left, Turn const& right) const
{
- return ! normal_action::included(point, geometry);
- }
+ segment_identifier const& sl = left.operations[0].seg_id;
+ segment_identifier const& sr = right.operations[0].seg_id;
+ return sl == sr
+ ? left.operations[0].enriched.distance < right.operations[0].enriched.distance
+ : sl < sr;
+
+ }
};
@@ -206,7 +268,7 @@
template <typename Point, typename Geometry>
static inline bool included(Point const& point, Geometry const& geometry)
{
- return action_selector<OverlayType>::included(point, geometry);
+ return following::action_selector<OverlayType>::included(point, geometry);
}
template<typename Turns, typename OutputIterator>
@@ -221,6 +283,8 @@
typename turn_type::container_type
>::type turn_operation_iterator_type;
+ typedef following::action_selector<OverlayType> action;
+
// Sort intersection points on segments-along-linestring, and distance
// (like in enrich is done for poly/poly)
std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
@@ -235,36 +299,36 @@
{
turn_operation_iterator_type iit = boost::begin(it->operations);
- if (was_entered(*it, first))
+ if (following::was_entered(*it, first))
{
debug_traverse(*it, *iit, "-> Was entered");
entered = true;
}
- if (is_staying_inside(*it, *iit, entered, first, linestring, polygon))
+ if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon))
{
debug_traverse(*it, *iit, "-> Staying inside");
entered = true;
}
- else if (is_entering(*it, *iit))
+ else if (following::is_entering(*it, *iit))
{
debug_traverse(*it, *iit, "-> Entering");
entered = true;
- action_selector<OverlayType>::enter(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
+ action::enter(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
}
- else if (is_leaving(*it, *iit, entered, first, linestring, polygon))
+ else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon))
{
debug_traverse(*it, *iit, "-> Leaving");
entered = false;
- action_selector<OverlayType>::leave(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
+ action::leave(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
}
first = false;
}
- if (action_selector<OverlayType>::is_entered(entered))
+ if (action::is_entered(entered))
{
geometry::copy_segments<false>(linestring, current_segment_id,
boost::size(linestring) - 1,