[Boost-commit] svn:boost r61701 - in sandbox/geometry/boost/geometry: algorithms extensions/algorithms/buffer util

Subject: [Boost-commit] svn:boost r61701 - in sandbox/geometry/boost/geometry: algorithms extensions/algorithms/buffer util
From: barend.gehrels_at_[hidden]
Date: 2010-04-30 05:11:08

Author: barendgehrels
Date: 2010-04-30 05:11:07 EDT (Fri, 30 Apr 2010)
New Revision: 61701
URL: http://svn.boost.org/trac/boost/changeset/61701

Log:
Changed area behaviour (now using reversible view to support ccw poylgons)
Added some buffer alternatives (all not perfect)
Added:
   sandbox/geometry/boost/geometry/extensions/algorithms/buffer/sectionalizing_buffer.hpp   (contents, props changed)
   sandbox/geometry/boost/geometry/extensions/algorithms/buffer/splitting_buffer.hpp   (contents, props changed)
   sandbox/geometry/boost/geometry/extensions/algorithms/buffer/traversing_buffer.hpp   (contents, props changed)
   sandbox/geometry/boost/geometry/util/order_as_direction.hpp   (contents, props changed)
Text files modified: 
   sandbox/geometry/boost/geometry/algorithms/area.hpp |    59 ++++++++++++++------------------------- 
   1 files changed, 22 insertions(+), 37 deletions(-)

Modified: sandbox/geometry/boost/geometry/algorithms/area.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/area.hpp	(original)
+++ sandbox/geometry/boost/geometry/algorithms/area.hpp	2010-04-30 05:11:07 EDT (Fri, 30 Apr 2010)
@@ -31,6 +31,9 @@
 #include <boost/geometry/strategies/concepts/area_concept.hpp>
 
 #include <boost/geometry/util/math.hpp>
+#include <boost/geometry/util/order_as_direction.hpp>
+#include <boost/geometry/util/reversible_view.hpp>
+
 
 /*!
 \defgroup area area: calculate area of a geometry
@@ -84,24 +87,8 @@
 };
 
 
-
-
-/*!
-    \brief Calculate area of a ring, specialized per order
- */
-template
-<
-    typename Ring,
-    order_selector Order,
-    // closing_selector Closed -- for now assuming CLOSED, p(0) == p(n-1)
-    typename Strategy
->
+template<typename Ring, iterate_direction Direction, typename Strategy>
 struct ring_area
-{};
-
-
-template<typename Ring, typename Strategy>
-struct ring_area<Ring, clockwise, Strategy>
 {
     BOOST_CONCEPT_ASSERT( (geometry::concept::AreaStrategy<Strategy>) );
 
@@ -114,7 +101,6 @@
         // Ignore warning (because using static method sometimes) on strategy
         boost::ignore_unused_variable_warning(strategy);
 
-
         // A closed linear_ring has at least four points,
         // if not, there is no (zero) area
         if (boost::size(ring) < 4)
@@ -122,39 +108,32 @@
             return type();
         }
 
-        typedef typename boost::range_iterator<Ring const>::type iterator_type;
+        typedef reversible_view<Ring const, Direction> view_type;
+        typedef typename boost::range_iterator<view_type const>::type iterator_type;
 
+        view_type view(ring);
         typename Strategy::state_type state;
+        iterator_type it = boost::begin(view);
 
-        iterator_type it = boost::begin(ring);
         for (iterator_type previous = it++;
-            it != boost::end(ring);
+            it != boost::end(view);
             previous = it++)
         {
             strategy.apply(*previous, *it, state);
         }
-        return strategy.result(state);
 
-    }
-};
-
-template<typename Ring, typename Strategy>
-struct ring_area<Ring, counterclockwise, Strategy>
-{
-    typedef typename Strategy::return_type type;
-    static inline type apply(Ring const& ring, Strategy const& strategy)
-    {
-        // Counter clockwise rings negate the area result
-        return -ring_area<Ring, clockwise, Strategy>::apply(ring, strategy);
+        return strategy.result(state);
     }
 };
 
 
 }} // namespace detail::area
 
+
 #endif // DOXYGEN_NO_DETAIL
 
 
+
 #ifndef DOXYGEN_NO_DISPATCH
 namespace dispatch
 {
@@ -181,13 +160,17 @@
 {};
 
 
-// Area of ring currently returns area of closed rings but it might be argued
-// that it is 0.0, because a ring is just a line.
 template <typename Geometry, order_selector Order, typename Strategy>
 struct area<ring_tag, Geometry, Order, Strategy>
-    : detail::area::ring_area<Geometry, Order, Strategy>
+    : detail::area::ring_area
+        <
+            Geometry, 
+            order_as_direction<Order>::value, 
+            Strategy
+        >
 {};
 
+
 template <typename Polygon, order_selector Order, typename Strategy>
 struct area<polygon_tag, Polygon, Order, Strategy>
     : detail::calculate_polygon_sum
@@ -198,7 +181,7 @@
             detail::area::ring_area
                 <
                     typename ring_type<Polygon>::type,
-                    Order,
+                    order_as_direction<Order>::value,
                     Strategy
                 >
         >
@@ -261,6 +244,8 @@
         >::apply(geometry, strategy);
 }
 
+
 }} // namespace boost::geometry
 
+
 #endif // BOOST_GEOMETRY_ALGORITHMS_AREA_HPP

Added: sandbox/geometry/boost/geometry/extensions/algorithms/buffer/sectionalizing_buffer.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/extensions/algorithms/buffer/sectionalizing_buffer.hpp	2010-04-30 05:11:07 EDT (Fri, 30 Apr 2010)
@@ -0,0 +1,162 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SECTIONALIZING_BUFFER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SECTIONALIZING_BUFFER_HPP
+
+#include <cstddef>
+
+#include <boost/foreach.hpp>
+#include <boost/numeric/conversion/cast.hpp>
+
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
+
+#include <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/strategies/buffer_side.hpp>
+#include <boost/geometry/algorithms/detail/buffer/intersecting_inserter.hpp>
+#include <boost/geometry/algorithms/detail/buffer/linestring_buffer.hpp>
+#include <boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp>
+
+#include <boost/geometry/algorithms/detail/sections/get_section.hpp>
+#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
+
+#include <boost/geometry/algorithms/dissolve.hpp>
+
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace buffer
+{
+
+
+
+template
+<
+    typename GeometryOut, typename Geometry,
+    typename DistanceStrategy,
+    typename JoinStrategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+    , typename Mapper
+#endif
+>
+void sectionalizing_buffer(Geometry const& geometry,
+    std::vector<GeometryOut>& buffered,
+    DistanceStrategy const& distance_strategy,
+    JoinStrategy const& join_strategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+    , Mapper& mapper
+#endif
+    )
+{
+    typedef typename point_type<Geometry>::type point_type;
+    typedef geometry::box<point_type> box_type;
+    typedef geometry::sections<box_type, 2> sections_type;
+    typedef typename geometry::ring_type<GeometryOut>::type ring_type;
+
+    // TEMPORARY
+    typedef intersecting_inserter
+        <
+            std::vector<GeometryOut>
+        > inserter_type;
+
+
+    sections_type sections;
+    geometry::sectionalize(geometry, sections);
+
+
+
+    // Buffer all sections separately, and put them in a temporary vector
+    std::vector<GeometryOut> buffered_sections;
+    BOOST_FOREACH(typename sections_type::value_type const& section, sections)
+    {
+        if (! section.duplicate)
+        {
+            typedef typename boost::range_iterator
+                <
+                    typename geometry::range_type<Geometry>::type const
+                >::type iterator_type;
+
+
+            inserter_type inserter(buffered_sections);
+
+            iterator_type begin, end;
+            typedef std::pair<iterator_type, iterator_type> section_range;
+            geometry::get_section(geometry, section, begin, end);
+            geometry::detail::buffer::linestring_buffer
+                <
+                    section_range, ring_type, DistanceStrategy, JoinStrategy
+                >::apply(std::make_pair(begin, end), inserter,
+                            distance_strategy,
+                            join_strategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+                            , mapper
+#endif
+                            );
+        }
+    }
+
+    // IF there are bowl-like shapes, there can still be self-intersections
+    std::vector<GeometryOut> dissolved;
+    BOOST_FOREACH(GeometryOut const& p, buffered_sections)
+    {
+        geometry::dissolve(p, dissolved);
+    }
+
+    /*BOOST_FOREACH(GeometryOut const& p, buffered_sections)
+    {
+        if (geometry::intersects(p))
+        {
+            //std::cout << ".";
+        }
+    }*/
+
+    // TEMP
+    //buffered.swap(dissolved);
+    //return;
+    // END TEMP
+
+
+    BOOST_FOREACH(GeometryOut const& p, dissolved)
+    {
+        if (buffered.empty())
+        {
+            buffered.push_back(p);
+            //geometry::union_inserter<GeometryOut>(geometry, p, std::back_inserter(buffered));
+        }
+        else if (boost::size(buffered) == 1)
+        {
+            std::vector<GeometryOut> unioned;
+            geometry::union_inserter<GeometryOut>(buffered.front(), p, std::back_inserter(unioned));
+            buffered.swap(unioned);
+        }
+        else
+        {
+            std::cerr << " D " << buffered.size();
+            /*std::vector<GeometryOut> dissolved;
+            dissolved.push_back(p);
+            geometry::dissolver(buffered, dissolved);
+            dissolved.swap(buffered);*/
+        }
+    }
+
+    // Output
+}
+
+
+}} // namespace detail::buffer
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SECTIONALIZING_BUFFER_HPP

Added: sandbox/geometry/boost/geometry/extensions/algorithms/buffer/splitting_buffer.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/extensions/algorithms/buffer/splitting_buffer.hpp	2010-04-30 05:11:07 EDT (Fri, 30 Apr 2010)
@@ -0,0 +1,115 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SPLITTING_BUFFER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SPLITTING_BUFFER_HPP
+
+#include <cstddef>
+
+#include <boost/foreach.hpp>
+#include <boost/numeric/conversion/cast.hpp>
+
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
+
+#include <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/strategies/buffer_side.hpp>
+#include <boost/geometry/algorithms/detail/buffer/intersecting_inserter.hpp>
+#include <boost/geometry/algorithms/detail/buffer/linestring_buffer.hpp>
+#include <boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp>
+
+
+#include <boost/geometry/algorithms/detail/overlay/dissolver.hpp>
+#include <boost/geometry/algorithms/detail/overlay/split_rings.hpp>
+
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace buffer
+{
+
+
+template
+<
+    typename GeometryOut, typename Geometry,
+    typename DistanceStrategy,
+    typename JoinStrategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+    , typename Mapper
+#endif
+>
+inline void splitting_buffer(Geometry const& geometry,
+    std::vector<GeometryOut>& buffered,
+    DistanceStrategy const& distance_strategy,
+    JoinStrategy const& join_strategy
+
+    , int option
+    )
+{
+    typedef typename ring_type<GeometryOut>::type ring_type;
+    typedef detail::buffer::intersecting_inserter
+        <
+            std::vector<GeometryOut>
+        > inserter_type;
+
+
+    inserter_type inserter(buffered);
+
+    detail::buffer::linestring_buffer
+        <
+            Geometry, GeometryOut, DistanceStrategy, JoinStrategy
+        >::apply(geometry, inserter, distance_strategy, join_strategy);
+
+    if (option == 0)
+    {
+        return;
+    }
+
+    std::vector<ring_type> rings;
+    BOOST_FOREACH(GeometryOut const& polygon, buffered)
+    {
+//std::cout << bg::wkt(polygon) << " ; POLYGON" << std::endl;
+        geometry::split_rings(polygon, rings);
+    }
+
+    if (option == 1)
+    {
+        buffered.resize(rings.size());
+        int i = 0;
+        BOOST_FOREACH(ring_type const& ring, rings)
+        {
+            exterior_ring(buffered[i++]) = ring;
+        }
+        return;
+    }
+
+    std::vector<GeometryOut> buffered_and_unioned;
+    geometry::dissolver(rings, buffered_and_unioned);
+
+    std::vector<GeometryOut> buffered_and_assembled;
+    detail::overlay::assemble<GeometryOut>(buffered_and_unioned,
+            std::map<ring_identifier, int>(),
+            buffered_and_unioned[0], buffered_and_unioned[0], 1, true, true,
+            std::back_inserter(buffered_and_assembled));
+
+    buffered = buffered_and_assembled;
+}
+
+
+
+}} // namespace detail::buffer
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SPLITTING_BUFFER_HPP

Added: sandbox/geometry/boost/geometry/extensions/algorithms/buffer/traversing_buffer.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/extensions/algorithms/buffer/traversing_buffer.hpp	2010-04-30 05:11:07 EDT (Fri, 30 Apr 2010)
@@ -0,0 +1,90 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TRAVERSING_BUFFER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TRAVERSING_BUFFER_HPP
+
+#include <cstddef>
+
+#include <boost/foreach.hpp>
+#include <boost/numeric/conversion/cast.hpp>
+
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
+
+#include <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/strategies/buffer_side.hpp>
+#include <boost/geometry/algorithms/detail/buffer/intersecting_inserter.hpp>
+#include <boost/geometry/algorithms/detail/buffer/linestring_buffer.hpp>
+#include <boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp>
+
+#include <boost/geometry/algorithms/detail/sections/get_section.hpp>
+#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
+
+#include <boost/geometry/algorithms/dissolve.hpp>
+
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace buffer
+{
+
+
+template
+<
+    typename GeometryOut, typename Geometry,
+    typename DistanceStrategy,
+    typename JoinStrategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+    , typename Mapper
+#endif
+>
+inline void traversing_buffer(Geometry const& geometry,
+    std::vector<GeometryOut>& buffered,
+    DistanceStrategy const& distance_strategy,
+    JoinStrategy const& join_strategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+    , Mapper& mapper
+#endif
+    )
+{
+    typedef typename ring_type<GeometryOut>::type ring_type;
+    typedef detail::buffer::intersecting_inserter
+        <
+            std::vector<GeometryOut>
+        > inserter_type;
+
+
+    inserter_type inserter(buffered);
+
+    detail::buffer::linestring_buffer
+        <
+            Geometry, GeometryOut, DistanceStrategy, JoinStrategy
+        >::apply(geometry, inserter, distance_strategy, join_strategy);
+
+    std::vector<GeometryOut> buffered_and_assembled;
+    detail::overlay::assemble<GeometryOut>(buffered,
+            std::map<ring_identifier, int>(),
+            buffered[0], buffered[0], 1, true, true,
+            std::back_inserter(buffered_and_assembled));
+
+    buffered = buffered_and_assembled;
+}
+
+
+}} // namespace detail::buffer
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TRAVERSING_BUFFER_HPP

Added: sandbox/geometry/boost/geometry/util/order_as_direction.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/util/order_as_direction.hpp	2010-04-30 05:11:07 EDT (Fri, 30 Apr 2010)
@@ -0,0 +1,42 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Copyright Bruno Lalande 2008, 2009
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_UTIL_ORDER_AS_DIRECTION_HPP
+#define BOOST_GEOMETRY_UTIL_ORDER_AS_DIRECTION_HPP
+
+#include <boost/geometry/core/point_order.hpp>
+#include <boost/geometry/util/reversible_view.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+template<order_selector Order>
+struct order_as_direction
+{};
+
+
+template<>
+struct order_as_direction<clockwise>
+{
+    static const iterate_direction value = iterate_forward;
+};
+
+
+template<>
+struct order_as_direction<counterclockwise>
+{
+    static const iterate_direction value = iterate_reverse;
+};
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_UTIL_ORDER_AS_DIRECTION_HPP