|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r75555 - trunk/boost/geometry/algorithms/detail/overlay
From: barend.gehrels_at_[hidden]
Date: 2011-11-19 11:37:56
Author: barendgehrels
Date: 2011-11-19 11:37:55 EST (Sat, 19 Nov 2011)
New Revision: 75555
URL: http://svn.boost.org/trac/boost/changeset/75555
Log:
Linestring/polygon overlay, second phase (including touching intersection points)
Text files modified:
trunk/boost/geometry/algorithms/detail/overlay/follow.hpp | 187 +++++++++++++++++++++++++++------------
trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp | 38 +++++++
trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp | 6 +
3 files changed, 169 insertions(+), 62 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-19 11:37:55 EST (Sat, 19 Nov 2011)
@@ -31,24 +31,9 @@
{
-template<typename Turn>
-struct sort_on_segment
-{
- 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;
-
- }
-};
-
/*!
-\brief Follows a linestring from intersection to intersection, outputting which
+\brief Follows a linestring from intersection point to intersection point, outputting which
is inside, or outside, a ring or polygon
\ingroup overlay
*/
@@ -56,49 +41,132 @@
<
typename LineStringOut,
typename LineString,
- typename Turns,
- typename OutputIterator
+ typename Polygon
>
-static inline OutputIterator follow(LineString const& geometry1,
- detail::overlay::operation_type operation,
- Turns& turns, OutputIterator out)
+class follow
{
- typedef typename boost::range_iterator<Turns>::type turn_iterator;
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename boost::range_iterator
- <
- typename turn_type::container_type
- >::type turn_operation_iterator_type;
-
-
- // 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>());
-
- LineStringOut current_piece;
- geometry::segment_identifier current_segment_id(0, -1, -1, -1);
-
- // Iterate through all intersection points (they are ordered along the line)
- bool entered = false;
- for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
+
+ template<typename Turn>
+ struct sort_on_segment
+ {
+ 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;
+
+ }
+ };
+
+ template <typename Turn, typename Operation>
+ static inline bool is_entering(Turn const& turn, Operation const& op)
+ {
+ return op.operation == operation_intersection;
+ }
+
+ 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 (op.operation == operation_union)
+ {
+ if (turn.method == method_crosses)
+ {
+ return true;
+ }
+
+ if (entered)
+ {
+ return true;
+ }
+ if (first)
+ {
+ // Check if first point of line is inside polygon
+ return 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)
{
- // Skip discarded/blocked ones TODO
- ////if (! (it->is_discarded() || it->blocked()))
+ if (turn.method == method_crosses)
+ {
+ return false;
+ }
+
+ if (op.operation == operation_intersection)
+ {
+ if (entered)
+ {
+ return true;
+ }
+ if (first)
+ {
+ // Check if first point of line is inside polygon
+ return geometry::within(linestring[0], polygon);
+ }
+ }
+ return false;
+ }
+
+
+public :
+ template<typename Turns, typename OutputIterator>
+ static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
+ detail::overlay::operation_type operation,
+ Turns& turns, OutputIterator out)
+ {
+ typedef typename boost::range_iterator<Turns>::type turn_iterator;
+ typedef typename boost::range_value<Turns>::type turn_type;
+ typedef typename boost::range_iterator
+ <
+ typename turn_type::container_type
+ >::type turn_operation_iterator_type;
+
+
+ // 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>());
+
+ LineStringOut current_piece;
+ geometry::segment_identifier current_segment_id(0, -1, -1, -1);
+
+ // Iterate through all intersection points (they are ordered along the line)
+ bool entered = false;
+ bool first = true;
+ for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
{
turn_operation_iterator_type iit = boost::begin(it->operations);
- if (iit->operation == operation_intersection)
+ if (is_staying_inside(*it, *iit, entered, first, linestring, polygon))
{
- // Entering
+ debug_traverse(*it, *iit, "-> Staying inside");
+
+ entered = true;
+ }
+ else if (is_entering(*it, *iit))
+ {
+ debug_traverse(*it, *iit, "-> Entering");
+
entered = true;
detail::overlay::append_no_duplicates(current_piece, it->point);
current_segment_id = iit->seg_id;
}
- else if (iit->operation == operation_union)
+ else if (is_leaving(*it, *iit, entered, first, linestring, polygon))
{
- // Leaving
+ debug_traverse(*it, *iit, "-> Leaving");
+
entered = false;
- geometry::copy_segments<false>(geometry1, current_segment_id,
+ geometry::copy_segments<false>(linestring, current_segment_id,
iit->seg_id.segment_index,
current_piece);
detail::overlay::append_no_duplicates(current_piece, it->point);
@@ -109,23 +177,24 @@
current_piece.clear();
}
}
+ first = false;
}
- }
- if (entered)
- {
- geometry::copy_segments<false>(geometry1, current_segment_id,
- boost::size(geometry1) - 1,
- current_piece);
- }
+ if (entered)
+ {
+ geometry::copy_segments<false>(linestring, current_segment_id,
+ boost::size(linestring) - 1,
+ current_piece);
+ }
- // Add the last one, if applicable
- if (! current_piece.empty())
- {
- *out++ = current_piece;
+ // Add the last one, if applicable
+ if (! current_piece.empty())
+ {
+ *out++ = current_piece;
+ }
+ return out;
}
- return out;
-}
+};
}} // namespace detail::overlay
Modified: trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp 2011-11-19 11:37:55 EST (Sat, 19 Nov 2011)
@@ -111,6 +111,24 @@
>
struct intersection_linestring_polygon
{
+
+#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
+ template <typename Turn, typename Operation>
+ static inline void debug_follow(Turn const& turn, Operation op,
+ int index)
+ {
+ std::cout << index
+ << " at " << op.seg_id
+ << " meth: " << method_char(turn.method)
+ << " op: " << operation_char(op.operation)
+ << " vis: " << visited_char(op.visited)
+ << " of: " << operation_char(turn.operations[0].operation)
+ << operation_char(turn.operations[1].operation)
+ << " " << geometry::wkt(turn.point)
+ << std::endl;
+ }
+#endif
+
static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
OutputIterator out,
Strategy const& strategy)
@@ -119,6 +137,7 @@
{
return out;
}
+
typedef typename point_type<LineStringOut>::type point_type;
typedef detail::overlay::traversal_turn_info<point_type> turn_info;
@@ -132,6 +151,8 @@
if (turns.empty())
{
+ // No intersection points, it is either completely inside
+ // or completely outside
if (geometry::within(linestring[0], polygon))
{
LineStringOut copy;
@@ -141,9 +162,22 @@
return out;
}
- return detail::overlay::follow<LineStringOut>
+#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
+ int index = 0;
+ BOOST_FOREACH(turn_info const& turn, turns)
+ {
+ debug_follow(turn, turn.operations[0], index++);
+ }
+#endif
+
+ return detail::overlay::follow
+ <
+ LineStringOut,
+ LineString,
+ Polygon
+ >::apply
(
- linestring,
+ linestring, polygon,
geometry::detail::overlay::operation_intersection,
turns, out
);
Modified: trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp 2011-11-19 11:37:55 EST (Sat, 19 Nov 2011)
@@ -23,7 +23,9 @@
#include <boost/geometry/geometries/concepts/check.hpp>
-#if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT)
+#if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
+ || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
+ || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
# include <string>
# include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
# include <boost/geometry/domains/gis/io/wkt/wkt.hpp>
@@ -46,10 +48,12 @@
#ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
std::cout << header
<< " at " << op.seg_id
+ << " meth: " << method_char(turn.method)
<< " op: " << operation_char(op.operation)
<< " vis: " << visited_char(op.visited)
<< " of: " << operation_char(turn.operations[0].operation)
<< operation_char(turn.operations[1].operation)
+ << " " << geometry::wkt(turn.point)
<< std::endl;
if (boost::contains(header, "Finished"))
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk