Subject: [Boost-commit] svn:boost r61227 - sandbox/geometry/boost/geometry/algorithms/detail/buffer
From: barend.gehrels_at_[hidden]
Date: 2010-04-12 12:19:52
Author: barendgehrels
Date: 2010-04-12 12:19:51 EDT (Mon, 12 Apr 2010)
New Revision: 61227
URL: http://svn.boost.org/trac/boost/changeset/61227
Log:
Updated buffer / double->coordinate_type
Added buffering new approach (per segment), do not use this yet.
Added:
sandbox/geometry/boost/geometry/algorithms/detail/buffer/segmenting_buffer.hpp (contents, props changed)
Text files modified:
sandbox/geometry/boost/geometry/algorithms/detail/buffer/polygon_buffer.hpp | 10 +++++-----
1 files changed, 5 insertions(+), 5 deletions(-)
Modified: sandbox/geometry/boost/geometry/algorithms/detail/buffer/polygon_buffer.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/buffer/polygon_buffer.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/buffer/polygon_buffer.hpp 2010-04-12 12:19:51 EDT (Mon, 12 Apr 2010)
@@ -35,20 +35,20 @@
template <typename RingInput, typename RingOutput, typename JoinStrategy>
struct ring_buffer
{
-
+ typedef typename point_type<RingOutput>::type output_point_type;
+ typedef typename coordinate_type<output_point_type>::type coordinate_type;
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
template <typename Mapper>
#endif
static inline void apply(RingInput const& ring, RingOutput& buffered,
- double distance, // TODO: change coordinate type
+ coordinate_type distance,
JoinStrategy const& join_strategy
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
, Mapper& mapper
#endif
)
{
- typedef typename point_type<RingOutput>::type output_point_type;
typedef segment<output_point_type const> segment_type;
typedef typename boost::range_iterator
<
@@ -72,7 +72,6 @@
bool skip = false;
// Generate a block along (int most cases to the left of) the segment
- typedef typename coordinate_type<output_point_type>::type coordinate_type;
// Simulate a vector d (dx,dy)
coordinate_type dx = get<0>(*it) - get<0>(*prev);
@@ -185,7 +184,8 @@
template <typename Mapper>
#endif
static inline void apply(PolygonInput const& polygon, PolygonOutput& buffered,
- double distance, JoinStrategy const& join_strategy
+ typename coordinate_type<PolygonOutput>::type distance,
+ JoinStrategy const& join_strategy
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
, Mapper& mapper
#endif
Added: sandbox/geometry/boost/geometry/algorithms/detail/buffer/segmenting_buffer.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/algorithms/detail/buffer/segmenting_buffer.hpp 2010-04-12 12:19:51 EDT (Mon, 12 Apr 2010)
@@ -0,0 +1,346 @@
+// 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_SEGMENTING_BUFFER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SEGMENTING_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/core/ring_type.hpp>
+
+#include <boost/geometry/strategies/buffer_side.hpp>
+#include <boost/geometry/strategies/buffer_join_round.hpp>
+#include <boost/geometry/algorithms/detail/disjoint.hpp>
+
+
+#include <boost/geometry/algorithms/dissolve.hpp>
+
+
+// TEMPORARY do not use yet.
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace buffer
+{
+
+
+template <typename Point, typename PointOut, typename DistanceType>
+inline bool calculate_parallels(Point const& point1, Point const& point2,
+ PointOut& p1, PointOut& p2, DistanceType const& distance)
+{
+ typedef typename coordinate_type<Point>::type coordinate_type;
+
+ // Simulate a vector d (dx,dy)
+ coordinate_type dx = get<0>(point2) - get<0>(point1);
+ coordinate_type dy = get<1>(point2) - get<1>(point1);
+
+ // For normalization [0,1] (=dot product d.d, sqrt)
+ // TODO: promote to non-integer
+ coordinate_type length = sqrt(dx * dx + dy * dy);
+
+ // Because coordinates are not equal, should been checked before, length should not be zero
+ if(geometry::math::equals(length, 0))
+ {
+ return false;
+ }
+
+ // Generate the normalized perpendicular p, to the left (ccw)
+ coordinate_type px = -dy / length;
+ coordinate_type py = dx / length;
+
+ set<0>(p1, get<0>(point1) + px * distance);
+ set<1>(p1, get<1>(point1) + py * distance);
+
+ set<0>(p2, get<0>(point2) + px * distance);
+ set<1>(p2, get<1>(point2) + py * distance);
+ return true;
+}
+
+
+
+template
+<
+ typename GeometryOut, typename Range,
+ typename DistanceStrategy,
+ typename JoinStrategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , typename Mapper
+#endif
+>
+struct per_segment_buffer
+{
+ typedef typename point_type<Range>::type input_point_type;
+ typedef typename point_type<GeometryOut>::type point_type;
+ typedef typename coordinate_type<point_type>::type coordinate_type;
+ typedef coordinate_type distance_type; // TODO promote to FP
+ typedef segment<point_type const> segment_type;
+ typedef typename geometry::ring_type<GeometryOut>::type ring_type;
+ typedef typename strategy_side<typename cs_tag<point_type>::type>::type side;
+
+ typedef typename boost::range_iterator<Range const>::type iterator_type;
+
+
+ static inline void calculate_tail(input_point_type const& tail, input_point_type const& head,
+ point_type& tail_left, point_type& tail_right,
+ distance_type& distance_left,
+ distance_type& distance_right,
+ distance_type& buffered_length)
+ {
+ coordinate_type ext_x = get<0>(head) - get<0>(tail);
+ coordinate_type ext_y = get<1>(head) - get<1>(tail);
+ distance_type segment_length = sqrt(ext_x * ext_x + ext_y * ext_y);
+
+ if (buffered_length < distance_left)
+ {
+ distance_left = buffered_length;
+ }
+ if (buffered_length < distance_right)
+ {
+ distance_right = buffered_length;
+ }
+
+ distance_type prop_left = distance_left / segment_length;
+ distance_type prop_right = distance_right / segment_length;
+
+ set<0>(tail_left, get<0>(tail) - ext_x * prop_left);
+ set<1>(tail_left, get<1>(tail) - ext_y * prop_left);
+ set<0>(tail_right, get<0>(tail) - ext_x * prop_right);
+ set<1>(tail_right, get<1>(tail) - ext_y * prop_right);
+
+ buffered_length += segment_length;
+ }
+
+
+ static inline void calculate_head(input_point_type const& tail, input_point_type const& head,
+ point_type& head_left, point_type& head_right,
+ distance_type& distance_left,
+ distance_type& distance_right,
+ distance_type const& rest_length)
+ {
+ coordinate_type ext_x = get<0>(head) - get<0>(tail);
+ coordinate_type ext_y = get<1>(head) - get<1>(tail);
+ distance_type segment_length = sqrt(ext_x * ext_x + ext_y * ext_y);
+
+ if (rest_length < distance_left)
+ {
+ distance_left = rest_length;
+ }
+ if (rest_length < distance_right)
+ {
+ distance_right = rest_length;
+ }
+
+ distance_type prop_left = distance_left / segment_length;
+ distance_type prop_right = distance_right / segment_length;
+
+ set<0>(head_left, get<0>(head) + ext_x * prop_left);
+ set<1>(head_left, get<1>(head) + ext_y * prop_left);
+ set<0>(head_right, get<0>(head) + ext_x * prop_right);
+ set<1>(head_right, get<1>(head) + ext_y * prop_right);
+ }
+
+ static inline void apply(Range const& range,
+ std::vector<GeometryOut>& buffered,
+ DistanceStrategy const& distance_strategy,
+ JoinStrategy const& join_strategy
+ #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , Mapper& mapper
+ #endif
+ )
+ {
+ // Buffer all segments separately, and put them in a temporary vector
+ std::vector<GeometryOut> buffered_pieces;
+
+ bool first = true;
+
+ strategy::buffer::join_round2<point_type> new_join;
+ //strategy::buffer::join_none<point_type> new_join;
+
+ distance_type range_length = geometry::length(range);
+ distance_type buffered_length = coordinate_type();
+
+ iterator_type it = boost::begin(range);
+ //iterator_type it_c = boost::end(range);
+ for (iterator_type previous = it++;
+ it != boost::end(range);
+ ++it)
+ {
+ bool const last = it + 1 == boost::end(range);
+
+ distance_type distance_left = distance_strategy.apply(
+ *previous, *it, buffer_side_left);
+ distance_type distance_right = distance_strategy.apply(
+ *previous, *it, buffer_side_right);
+
+ point_type left_ab_p1, left_ab_p2, right_ab_p1, right_ab_p2;
+
+ if (detail::disjoint::disjoint_point_point(*previous, *it)
+ && calculate_parallels(*previous, *it, left_ab_p1, left_ab_p2,
+ distance_left)
+ && calculate_parallels(*previous, *it, right_ab_p1, right_ab_p2,
+ -distance_right)
+ )
+ {
+ {
+ point_type tail_left, tail_right, head_left, head_right;
+
+ // For flat buffers, generate corners only if outside range of buffer_distance
+ distance_type distance_tail_left = distance_left;
+ distance_type distance_tail_right = distance_right;
+ distance_type distance_head_left = distance_left;
+ distance_type distance_head_right = distance_right;
+
+ calculate_tail(*previous, *it,
+ tail_left, tail_right,
+ distance_tail_left, distance_tail_right,
+ buffered_length);
+
+ distance_type const rest_length = range_length - buffered_length;
+
+ calculate_head(*previous, *it,
+ head_left, head_right,
+ distance_head_left, distance_head_right,
+ rest_length);
+
+ // Add non-axis aligned rectangle
+ buffered_pieces.resize(buffered_pieces.size() + 1);
+ ring_type& ring = exterior_ring(buffered_pieces.back());
+ ring.push_back(left_ab_p1);
+ ring.push_back(left_ab_p2);
+
+ if (! last)
+ {
+ new_join.apply(*it, left_ab_p2, left_ab_p2, head_left,
+ distance_left, distance_head_left,
+ std::back_inserter(ring));
+
+ ring.push_back(head_left);
+ ring.push_back(head_right);
+
+ new_join.apply(*it, right_ab_p2, head_right, right_ab_p2,
+ distance_right, distance_head_right,
+ std::back_inserter(ring));
+ }
+
+ ring.push_back(right_ab_p2);
+ ring.push_back(right_ab_p1);
+
+ if (! first)
+ {
+ new_join.apply(*previous, right_ab_p1, right_ab_p1, tail_right,
+ distance_right, distance_tail_right,
+ std::back_inserter(ring));
+
+ ring.push_back(tail_right);
+ ring.push_back(tail_left);
+
+ new_join.apply(*previous, left_ab_p1, tail_left, left_ab_p1,
+ distance_left, distance_tail_left,
+ std::back_inserter(ring));
+ }
+
+ ring.push_back(left_ab_p1);
+ }
+
+ previous = it;
+
+ first = false;
+ }
+ }
+
+ // TEMP
+ buffered.swap(buffered_pieces);
+ return;
+ // END TEMP
+
+
+
+ BOOST_FOREACH(GeometryOut const& p, buffered_pieces)
+ {
+ if (buffered.empty())
+ {
+ buffered.push_back(p);
+ }
+ 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);*/
+ }
+ }
+
+ /***
+ std::vector<GeometryOut> dissolved;
+ BOOST_FOREACH(GeometryOut const& p, buffered)
+ {
+ geometry::dissolve(p, dissolved);
+ }
+ dissolved.swap(buffered);
+ ***/
+
+ // Output
+ }
+};
+
+
+
+template
+<
+ typename GeometryOut, typename Geometry,
+ typename DistanceStrategy,
+ typename JoinStrategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , typename Mapper
+#endif
+>
+inline void segmenting_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
+ )
+{
+ per_segment_buffer
+ <
+ GeometryOut, Geometry,
+ DistanceStrategy, JoinStrategy
+ >::apply(geometry, buffered, distance_strategy, join_strategy);
+}
+
+
+
+}} // namespace detail::buffer
+#endif // DOXYGEN_NO_DETAIL
+
+
+
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SEGMENTING_BUFFER_HPP