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