|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r53484 - sandbox/ggl/boost/ggl/geometry/algorithms
From: barend.gehrels_at_[hidden]
Date: 2009-05-31 04:24:54
Author: barendgehrels
Date: 2009-05-31 04:24:53 EDT (Sun, 31 May 2009)
New Revision: 53484
URL: http://svn.boost.org/trac/boost/changeset/53484
Log:
Implementation change, moved intersection output linetype template definition such that it can be specified.
Also many style guides because source of these two files is GGL 0.5, downgraded to GGL 0.4 namespaces
Text files modified:
sandbox/ggl/boost/ggl/geometry/algorithms/intersection.hpp | 127 +++++------
sandbox/ggl/boost/ggl/geometry/algorithms/intersection_linestring.hpp | 420 ++++++++++++++++++++-------------------
2 files changed, 276 insertions(+), 271 deletions(-)
Modified: sandbox/ggl/boost/ggl/geometry/algorithms/intersection.hpp
==============================================================================
--- sandbox/ggl/boost/ggl/geometry/algorithms/intersection.hpp (original)
+++ sandbox/ggl/boost/ggl/geometry/algorithms/intersection.hpp 2009-05-31 04:24:53 EDT (Sun, 31 May 2009)
@@ -6,15 +6,14 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef _GEOMETRY_INTERSECTION_HPP
-#define _GEOMETRY_INTERSECTION_HPP
+#ifndef GGL_ALGORITHMS_INTERSECTION_HPP
+#define GGL_ALGORITHMS_INTERSECTION_HPP
-#include <geometry/algorithms/intersection_segment.hpp>
#include <geometry/algorithms/intersection_linestring.hpp>
#include <geometry/algorithms/intersection_polygon.hpp>
+#include <geometry/algorithms/intersection_segment.hpp>
// Helper container and helper geometry
-#include <vector>
#include <geometry/geometries/segment.hpp>
@@ -31,13 +30,13 @@
\par Geometries:
The intersection result is painted with a red outline.
- clip: POLYGON + BOX -> output iterator of polygons
- \image html clip_polygon.png
+\image html clip_polygon.png
- clip: LINESTRING + BOX -> output iterator of linestrings
- \image html clip_linestring.png
+\image html clip_linestring.png
\note There are some difficulties to model an intersection in the template world. The intersection of two segments can
result into nothing, into a point, into another segment. At compiletime the result type is not known. An output iterator
iterating points is appropriate here.
- \image html clip_segment_segment.png
+\image html clip_segment_segment.png
An intersection of two linestrings can result into nothing, one or more points, one or more segments or one or more
linestrings. So an output iterator will NOT do here.
So the output might be changed into a unified algorithm where the output is a multi-geometry.
@@ -63,71 +62,69 @@
\until }
*/
-
namespace geometry
{
- #ifndef DOXYGEN_NO_DISPATCH
- namespace dispatch
- {
-
- template <typename TAG1, typename TAG2, typename G1, typename G2>
- struct intersection {};
-
- template <typename B, typename L>
- struct intersection<box_tag, linestring_tag, B, L>
- {
- template<typename O_IT>
- static inline O_IT calculate(const B& box, const L& linestring, O_IT out)
- {
- typedef typename point_type<L>::type P;
- typedef segment<P> S;
- strategy::intersection::liang_barsky<B, S> strategy;
-
- return (impl::intersection::clip_linestring_with_box(box, linestring, out, strategy));
- }
- };
-
- template <typename B, typename P>
- struct intersection<box_tag, polygon_tag, B, P>
- {
- template<typename O_IT>
- static inline O_IT calculate(const B& box, const P& poly, O_IT out)
- {
- return impl::intersection::poly_weiler_atherton(box, poly, out);
- }
- };
-
- } // namespace dispatch
- #endif
-
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+template <typename Tag1, typename Tag2, typename G1, typename G2>
+struct intersection {};
+template <typename B, typename L>
+struct intersection<box_tag, linestring_tag, B, L>
+{
+ template <typename OutputIterator>
+ static inline OutputIterator calculate(B const& box, L const& linestring, OutputIterator out)
+ {
+ typedef typename point_type<L>::type point_type;
+ strategy::intersection::liang_barsky<B, point_type> strategy;
+ return impl::intersection::clip_linestring_with_box<L>(box, linestring, out, strategy);
+ }
+};
+template <typename B, typename P>
+struct intersection<box_tag, polygon_tag, B, P>
+{
+ template <typename OutputIterator>
+ static inline OutputIterator calculate(B const& box, P const& poly, OutputIterator out)
+ {
+ return impl::intersection::poly_weiler_atherton(box, poly, out);
+ }
+};
- /*!
- \brief Intersects two geometries which each other
- \ingroup intersection
- \details A sequence of points is intersected (clipped) by the specified box
- and the resulting linestring, or pieces of linestrings, are sent to the specified output operator.
- \tparam G1 first geometry type
- \tparam G2 second geometry type
- \tparam O_IT output iterator
- \param geometry1 first geometry (currently only a BOX)
- \param geometry2 second geometry (range, linestring, polygon)
- \param out the output iterator, outputting linestrings or polygons
- \return the output iterator
- \note For linestrings: the default clipping strategy, Liang-Barsky, is used. The algorithm is currently only
- implemented for 2D xy points. It could be generic for most ll cases, but not across the 180
- meridian so that issue is still on the todo-list.
- */
- template <typename G1, typename G2, typename O_IT>
- inline O_IT intersection(const G1& geometry1, const G2& geometry2, O_IT out)
- {
- return dispatch::intersection<typename tag<G1>::type,
- typename tag<G2>::type, G1, G2>::calculate(geometry1, geometry2, out);
- }
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+/*!
+ \brief Intersects two geometries which each other
+ \ingroup intersection
+ \details A sequence of points is intersected (clipped) by the specified box
+ and the resulting linestring, or pieces of linestrings, are sent to the specified output operator.
+ \tparam G1 first geometry type
+ \tparam G2 second geometry type
+ \tparam OutputIterator output iterator
+ \param geometry1 first geometry (currently only a BOX)
+ \param geometry2 second geometry (range, linestring, polygon)
+ \param out the output iterator, outputting linestrings or polygons
+ \return the output iterator
+ \note For linestrings: the default clipping strategy, Liang-Barsky, is used. The algorithm is currently only
+ implemented for 2D xy points. It could be generic for most ll cases, but not across the 180
+ meridian so that issue is still on the todo-list.
+*/
+template <typename G1, typename G2, typename OutputIterator>
+inline OutputIterator intersection(G1 const& geometry1, G2 const& geometry2, OutputIterator out)
+{
+ return dispatch::intersection
+ <
+ typename tag<G1>::type,
+ typename tag<G2>::type,
+ G1,
+ G2
+ >::calculate(geometry1, geometry2, out);
}
-#endif //_GEOMETRY_INTERSECTION_HPP
+} // geometry
+
+#endif //GGL_ALGORITHMS_INTERSECTION_HPP
Modified: sandbox/ggl/boost/ggl/geometry/algorithms/intersection_linestring.hpp
==============================================================================
--- sandbox/ggl/boost/ggl/geometry/algorithms/intersection_linestring.hpp (original)
+++ sandbox/ggl/boost/ggl/geometry/algorithms/intersection_linestring.hpp 2009-05-31 04:24:53 EDT (Sun, 31 May 2009)
@@ -6,223 +6,231 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef _GEOMETRY_INTERSECTION_LINESTRING_HPP
-#define _GEOMETRY_INTERSECTION_LINESTRING_HPP
+#ifndef GGL_ALGORITHMS_INTERSECTION_LINESTRING_HPP
+#define GGL_ALGORITHMS_INTERSECTION_LINESTRING_HPP
#include <boost/range/functions.hpp>
#include <boost/range/metafunctions.hpp>
-
-#include <geometry/algorithms/clear.hpp>
#include <geometry/algorithms/append.hpp>
-
-
+#include <geometry/algorithms/clear.hpp>
+#include <geometry/util/copy.hpp>
#include <geometry/geometries/segment.hpp>
-
namespace geometry
{
- namespace strategy
- {
- namespace intersection
- {
- /*!
- \brief Strategy: line clipping algorithm after Liang Barsky
- \ingroup intersection
- \details The Liang-Barsky line clipping algorithm clips a line with a clipping box.
- It is slightly adapted in the sense that it returns which points are clipped
- \tparam B box type of clipping box
- \tparam S segment type of segments to be clipped
- \note The algorithm is currently only implemented for 2D Cartesian points
- \author Barend Gehrels, and the following recourses
- - A tutorial: http://www.skytopia.com/project/articles/compsci/clipping.html
- - a German applet (link broken): http://ls7-www.cs.uni-dortmund.de/students/projectgroups/acit/lineclip.shtml
- */
- template<typename B, typename S>
- class liang_barsky
- {
- private :
- inline bool check_edge(const double& p, const double& q, double &t1, double &t2) const
- {
- bool visible = true;
-
- if(p < 0)
- {
- double r = q / p;
- if(r > t2) visible = false;
- else if(r > t1) t1 = r;
- }
- else if(p > 0)
- {
- double r = q / p;
- if(r < t1) visible = false;
- else if(r < t2) t2 = r;
- }
- else
- {
- if(q < 0) visible = false;
- }
-
- return visible;
- }
-
- public :
- bool clip_segment(const B& b, S& s, bool& sp1_clipped, bool& sp2_clipped) const
- {
- typedef typename select_coordinate_type<B, S>::type T;
-
- double t1 = 0;
- double t2 = 1;
-
- T dx = get<1, 0>(s) - get<0, 0>(s);
- T dy = get<1, 1>(s) - get<0, 1>(s);
-
- T p1 = -dx;
- T p2 = dx;
- T p3 = -dy;
- T p4 = dy;
-
- T q1 = get<0, 0>(s) - get<min_corner, 0>(b);
- T q2 = get<max_corner, 0>(b) - get<0, 0>(s);
- T q3 = get<0, 1>(s) - get<min_corner, 1>(b);
- T q4 = get<max_corner, 1>(b) - get<0, 1>(s);
-
- if(check_edge(p1, q1, t1, t2) // left
- && check_edge(p2, q2, t1, t2) // right
- && check_edge(p3, q3, t1, t2) // bottom
- && check_edge(p4, q4, t1, t2) // top
- )
- {
- sp1_clipped = t1 > 0;
- sp2_clipped = t2 < 1;
-
- // Todo, maybe: round coordinates in case of integer? define some round_traits<> or so?
- // Take boost-round of Fernando
- if (sp2_clipped)
- {
- set<1, 0>(s, get<0, 0>(s) + t2 * dx);
- set<1, 1>(s, get<0, 1>(s) + t2 * dy);
- }
-
- if(sp1_clipped)
- {
- set<0, 0>(s, get<0, 0>(s) + t1 * dx);
- set<0, 1>(s, get<0, 1>(s) + t1 * dy);
- }
-
- return true;
- }
-
- return false;
- }
-
- template<typename L, typename O_IT>
- inline void add(L& line_out, O_IT out) const
- {
- if (! boost::empty(line_out))
- {
- *out = line_out;
- out++;
- geometry::clear(line_out);
- }
- }
- };
- }
- }
-
-
- #ifndef DOXYGEN_NO_IMPL
- namespace impl
- {
- namespace intersection
- {
-
-
- /*!
- \brief Clips a linestring, or pair of iterators, with a box
- \details A linestring, defined by an iterator pair, is intersected (clipped) by the specified box
- and the resulting linestring, or pieces of linestrings, are sent to the specified output operator.
- \tparam C container type, for example a vector of points, matching the output-iterator type,
- the points should also match the input-iterator type
- \tparam B box type
- \tparam IT in iterator type
- \tparam O_IT output iterator type, which outputs linestrings
- \tparam S strategy, a clipping strategy which should implement the methods "clip_segment" and "add"
- */
- template <typename L, typename B, typename O_IT, typename S>
- O_IT clip_linestring_with_box(const B& b, const L& linestring, O_IT out, const S& strategy)
- {
- if (boost::begin(linestring) == boost::end(linestring))
- {
- return (out);
- }
- typedef typename point_type<L>::type P;
- typedef segment<P> SEG;
-
- L line_out;
-
- typename boost::range_const_iterator<L>::type vertex = boost::begin(linestring);
- typename boost::range_const_iterator<L>::type previous = vertex++;
- while(vertex != boost::end(linestring))
- {
- P p1 = *previous;
- P p2 = *vertex;
-
- // Clip the segment. Five situations:
- // 1. Segment is invisible, finish line if any (shouldn't occur)
- // 2. Segment is completely visible. Add (p1)-p2 to line
- // 3. Point 1 is invisible (clipped), point 2 is visible. Start new line from p1-p2...
- // 4. Point 1 is visible, point 2 is invisible (clipped). End the line with ...p2
- // 5. Point 1 and point 2 are both invisible (clipped). Start/finish an independant line p1-p2
- //
- // This results in:
- // a. if p1 is clipped, start new line
- // b. if segment is partly or completely visible, add the segment
- // c. if p2 is clipped, end the line
-
- bool c1, c2;
- SEG s(p1, p2);
- if (! strategy.clip_segment(b, s, c1, c2))
- {
- strategy.add(line_out, out);
- }
- else
- {
- // a. If necessary, finish the line and add a start a new one
- if (c1)
- {
- strategy.add(line_out, out);
- }
-
- // b. Add p1 only if it is the first point, then add p2
- if (boost::empty(line_out))
- {
- geometry::append(line_out, p1);
- }
- geometry::append(line_out, p2);
-
- // c. If c2 is clipped, finish the line
- if (c2)
- {
- strategy.add(line_out, out);
- }
- }
- previous = vertex++;
- }
- // Add last part
- strategy.add(line_out, out);
- return (out);
- }
-
-
-
- } // namespace intersection
- } // namespace impl
- #endif
+namespace strategy { namespace intersection {
+
+/*!
+ \brief Strategy: line clipping algorithm after Liang Barsky
+ \ingroup intersection
+ \details The Liang-Barsky line clipping algorithm clips a line with a clipping box.
+ It is slightly adapted in the sense that it returns which points are clipped
+ \tparam B input box type of clipping box
+ \tparam P input/output point-type of segments to be clipped
+ \note The algorithm is currently only implemented for 2D Cartesian points
+ \author Barend Gehrels, and the following recourses
+ - A tutorial: http://www.skytopia.com/project/articles/compsci/clipping.html
+ - a German applet (link broken): http://ls7-www.cs.uni-dortmund.de/students/projectgroups/acit/lineclip.shtml
+*/
+template<typename B, typename P>
+class liang_barsky
+{
+private:
+ typedef geometry::segment<P> segment_type;
+ inline bool check_edge(double const& p, double const& q, double& t1, double& t2) const
+ {
+ bool visible = true;
+
+ if(p < 0)
+ {
+ double const r = q / p;
+ if (r > t2)
+ visible = false;
+ else if (r > t1)
+ t1 = r;
+ }
+ else if(p > 0)
+ {
+ double const r = q / p;
+ if (r < t1)
+ visible = false;
+ else if (r < t2)
+ t2 = r;
+ }
+ else
+ {
+ if (q < 0)
+ visible = false;
+ }
+
+ return visible;
+ }
+
+public:
+
+ bool clip_segment(B const& b, segment_type& s, bool& sp1_clipped, bool& sp2_clipped) const
+ {
+ typedef typename select_coordinate_type<B, P>::type coordinate_type;
+
+ double t1 = 0;
+ double t2 = 1;
+
+ coordinate_type const dx = get<1, 0>(s) - get<0, 0>(s);
+ coordinate_type const dy = get<1, 1>(s) - get<0, 1>(s);
+
+ coordinate_type const p1 = -dx;
+ coordinate_type const p2 = dx;
+ coordinate_type const p3 = -dy;
+ coordinate_type const p4 = dy;
+
+ coordinate_type const q1 = get<0, 0>(s) - get<min_corner, 0>(b);
+ coordinate_type const q2 = get<max_corner, 0>(b) - get<0, 0>(s);
+ coordinate_type const q3 = get<0, 1>(s) - get<min_corner, 1>(b);
+ coordinate_type const q4 = get<max_corner, 1>(b) - get<0, 1>(s);
+
+ if (check_edge(p1, q1, t1, t2) // left
+ && check_edge(p2, q2, t1, t2) // right
+ && check_edge(p3, q3, t1, t2) // bottom
+ && check_edge(p4, q4, t1, t2)) // top
+ {
+ sp1_clipped = t1 > 0;
+ sp2_clipped = t2 < 1;
+
+ // TODO: maybe round coordinates in case of integer? define some round_traits<> or so?
+ // Take boost-round of Fernando
+ if (sp2_clipped)
+ {
+ set<1, 0>(s, get<0, 0>(s) + t2 * dx);
+ set<1, 1>(s, get<0, 1>(s) + t2 * dy);
+ }
+
+ if(sp1_clipped)
+ {
+ set<0, 0>(s, get<0, 0>(s) + t1 * dx);
+ set<0, 1>(s, get<0, 1>(s) + t1 * dy);
+ }
+
+ return true;
+ }
+
+ return false;
+ }
+
+ template<typename L, typename OutputIterator>
+ inline void add(L& line_out, OutputIterator out) const
+ {
+ if (!boost::empty(line_out))
+ {
+ *out = line_out;
+ ++out;
+ geometry::clear(line_out);
+ }
+ }
+};
+}} // namespace strategy::intersection
+
+
+#ifndef DOXYGEN_NO_IMPL
+namespace impl { namespace intersection {
+
+
+/*!
+ \brief Clips a linestring, or pair of iterators, with a box
+ \details A linestring, defined by an iterator pair, is intersected (clipped) by the specified box
+ and the resulting linestring, or pieces of linestrings, are sent to the specified output operator.
+ \tparam C container type, for example a vector of points, matching the output-iterator type,
+ the points should also match the input-iterator type
+ \tparam OutputLinestring type of the output linestrings
+ \tparam OutputIterator an output iterator which outputs linestrings
+ \tparam Box box type
+ \tparam OutputIterator output iterator type, which outputs linestrings
+ \tparam Strategy strategy, a clipping strategy which should implement the methods "clip_segment" and "add"
+*/
+template
+<
+ typename OutputLinestring,
+ typename OutputIterator,
+ typename Linestring,
+ typename Box,
+ typename Strategy
+>
+OutputIterator clip_linestring_with_box(Box const& b, Linestring const& linestring,
+ OutputIterator out, Strategy const& strategy)
+{
+ if (boost::begin(linestring) == boost::end(linestring))
+ {
+ return out;
+ }
+
+ typedef typename point_type<OutputLinestring>::type point_type;
+
+ OutputLinestring line_out;
+
+ typedef typename boost::range_const_iterator<Linestring>::type iterator_type;
+ iterator_type vertex = boost::begin(linestring);
+ for(iterator_type previous = vertex++;
+ vertex != boost::end(linestring);
+ previous = vertex++)
+ {
+ point_type p1, p2;
+ copy_coordinates(*previous, p1);
+ copy_coordinates(*vertex, p2);
+
+ // Clip the segment. Five situations:
+ // 1. Segment is invisible, finish line if any (shouldn't occur)
+ // 2. Segment is completely visible. Add (p1)-p2 to line
+ // 3. Point 1 is invisible (clipped), point 2 is visible. Start new line from p1-p2...
+ // 4. Point 1 is visible, point 2 is invisible (clipped). End the line with ...p2
+ // 5. Point 1 and point 2 are both invisible (clipped). Start/finish an independant line p1-p2
+ //
+ // This results in:
+ // a. if p1 is clipped, start new line
+ // b. if segment is partly or completely visible, add the segment
+ // c. if p2 is clipped, end the line
+
+ bool c1 = false;
+ bool c2 = false;
+ segment<point_type> s(p1, p2);
+
+ if (!strategy.clip_segment(b, s, c1, c2))
+ {
+ strategy.add(line_out, out);
+ }
+ else
+ {
+ // a. If necessary, finish the line and add a start a new one
+ if (c1)
+ {
+ strategy.add(line_out, out);
+ }
+
+ // b. Add p1 only if it is the first point, then add p2
+ if (boost::empty(line_out))
+ {
+ geometry::append(line_out, p1);
+ }
+ geometry::append(line_out, p2);
+
+ // c. If c2 is clipped, finish the line
+ if (c2)
+ {
+ strategy.add(line_out, out);
+ }
+ }
+
+ }
+
+ // Add last part
+ strategy.add(line_out, out);
+ return out;
+}
-} // namespace
+}} // namespace impl::intersection
+#endif // DOXYGEN_NO_IMPL
+} // namespace geometry
-#endif //_GEOMETRY_INTERSECTION_LINESTRING_HPP
+#endif // GGL_ALGORITHMS_INTERSECTION_LINESTRING_HPP
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