[Boost-commit] svn:boost r77171 - in trunk: boost/geometry/extensions/algorithms/buffer boost/geometry/extensions/strategies libs/geometry/test_extensions/algorithms/buffer

Subject: [Boost-commit] svn:boost r77171 - in trunk: boost/geometry/extensions/algorithms/buffer boost/geometry/extensions/strategies libs/geometry/test_extensions/algorithms/buffer
From: barend.gehrels_at_[hidden]
Date: 2012-03-03 06:24:47

Author: barendgehrels
Date: 2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
New Revision: 77171
URL: http://svn.boost.org/trac/boost/changeset/77171

Log:
Boost.Geometry buffer update
Added:
   trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp   (contents, props changed)
   trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection_with_mapper.hpp   (contents, props changed)
   trunk/boost/geometry/extensions/algorithms/buffer/side_on_convex_range.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp           |    61 +-                                      
   trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp |   907 ++++++++++++++++++++++++--------------- 
   trunk/boost/geometry/extensions/strategies/buffer.hpp                           |     5                                         
   trunk/libs/geometry/test_extensions/algorithms/buffer/linestring_buffer.cpp     |    71 ++-                                     
   trunk/libs/geometry/test_extensions/algorithms/buffer/polygon_buffer.cpp        |    33 +                                       
   trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp           |    25                                         
   6 files changed, 674 insertions(+), 428 deletions(-)

Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
-// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2012 Barend Gehrels, 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
@@ -23,6 +23,10 @@
 #include <boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp>
 #include <boost/geometry/extensions/algorithms/buffer/line_line_intersection.hpp>
 
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+#  include <boost/geometry/extensions/algorithms/buffer/buffered_piece_collection_with_mapper.hpp>
+#endif
+
 
 namespace boost { namespace geometry
 {
@@ -90,7 +94,7 @@
                 Iterator begin, Iterator end,
                 buffer_side_selector side,
                 DistanceStrategy const& distance,
-                JoinStrategy const& join_strategy)
+                JoinStrategy const& join_strategy, bool close = false)
     {
         output_point_type previous_p1, previous_p2;
         output_point_type first_p1, first_p2;
@@ -135,10 +139,10 @@
                 }
                 if (! range_out.empty())
                 {
-                    collection.add_piece(*prev, range_out);
+                    collection.add_piece(buffered_join, *prev, range_out);
                     range_out.clear();
                 }
-                collection.add_piece(*prev, *it, p1, p2);
+                collection.add_piece(buffered_segment, *prev, *it, p1, p2);
 
                 previous_p1 = p1;
                 previous_p2 = p2;
@@ -161,7 +165,7 @@
                 range_out);
             if (! range_out.empty())
             {
-                collection.add_piece(*begin, range_out);
+                collection.add_piece(buffered_join, *begin, range_out);
             }
 
             // Buffer is closed automatically by last closing corner (NOT FOR OPEN POLYGONS - TODO)
@@ -169,6 +173,7 @@
         else if (boost::is_same<Tag, linestring_tag>::value)
         {
             // Assume flat-end-strategy for now
+            // TODO fix this (approach) for one-side buffer (1.5 - -1.0)
             output_point_type rp1, rp2;
             generate_side(last_ip2, last_ip1, 
                     side == buffer_side_left 
@@ -176,12 +181,14 @@
                     : buffer_side_left, 
                 distance, rp2, rp1);
 
+            // For flat end:
             std::vector<output_point_type> range_out;
             range_out.push_back(previous_p2);
-            range_out.push_back(*(end - 1));
-            range_out.push_back(rp2);
-            // For flat:
-            collection.add_piece(last_ip2, range_out);
+            if (close)
+            {
+                range_out.push_back(rp2);
+            }
+            collection.add_piece(buffered_flat_end, range_out);
         }
     }
 };
@@ -251,14 +258,14 @@
             DistanceStrategy const& distance,
             JoinStrategy const& join_strategy)
     {
-        collection.add_input();
+        collection.start_new_ring();
         iterate(collection, boost::begin(linestring), boost::end(linestring),
                 buffer_side_left,
                 distance, join_strategy);
                 
         iterate(collection, boost::rbegin(linestring), boost::rend(linestring),
                 buffer_side_right,
-                distance, join_strategy);
+                distance, join_strategy, true);
 
     }
 };
@@ -284,8 +291,7 @@
         typedef buffer_inserter<ring_tag, input_ring_type, output_ring_type> policy;
 
         {
-            collection.add_input();
-
+            collection.start_new_ring();
             policy::apply(exterior_ring(polygon), collection,
                     distance, join_strategy);
         }
@@ -294,10 +300,7 @@
                     = interior_rings(polygon);
         for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
         {
-            output_ring_type ring;
-
-            collection.add_input();
-
+            collection.start_new_ring();
             policy::apply(*it, collection, distance, join_strategy);
         }
 
@@ -327,7 +330,14 @@
 #endif
     )
 {
-    detail::buffer::buffered_piece_collection<typename geometry::ring_type<GeometryOutput>::type> collection;
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+    detail::buffer::buffered_piece_collection_with_mapper
+#else
+    detail::buffer::buffered_piece_collection
+#endif
+        <
+            typename geometry::ring_type<GeometryOutput>::type
+        > collection;
 
     dispatch::buffer_inserter
         <
@@ -336,20 +346,23 @@
             GeometryOutput
         >::apply(geometry_input, collection, distance_strategy, join_strategy);
 
-    collection.get_turns(geometry_input);
+    collection.get_turns(geometry_input, distance_strategy.factor());
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-    collection.map_offsetted(mapper);
+    //collection.map_offsetted(mapper);
+    collection.map_turns(mapper);
+    //collection.map_opposite_locations(mapper);
 #endif
 
-    collection.discard_points();
+    collection.discard_rings();
+    collection.discard_turns();
     collection.enrich();
     collection.traverse();
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-    //collection.map<geometry::polygon_tag>(mapper);
-    collection.map_turns(mapper);
-    collection.map_traverse(mapper);
+    //collection.map_turns(mapper);
+    collection.map_pieces<geometry::polygon_tag>(mapper); //, false, true);
+    //collection.map_traverse(mapper);
 #endif
 
     collection.assign<GeometryOutput>(out);

Added: trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -0,0 +1,139 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2012 Barend Gehrels, 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_BUFFER_POLICIES_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_POLICIES_HPP
+
+
+#include <cstddef>
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/coordinate_type.hpp>
+#include <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/algorithms/covered_by.hpp>
+#include <boost/geometry/extensions/strategies/buffer_side.hpp>
+
+#include <boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp>
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+
+
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace buffer
+{
+
+
+enum intersection_location_type
+{
+    location_ok, inside_buffer, inside_original
+};
+
+class backtrack_for_buffer
+{
+public :
+    typedef detail::overlay::backtrack_state state_type;
+
+    template <typename Operation, typename Rings, typename Turns, typename Geometry>
+    static inline void apply(std::size_t size_at_start, 
+                Rings& rings, typename boost::range_value<Rings>::type& ring,
+                Turns& turns, Operation& operation,
+                std::string const& reason,
+                Geometry const& ,
+                Geometry const& ,
+                state_type& state
+                )
+    {
+std::cout << "WARNING " << reason << std::endl;
+
+        // TODO this is a copy of dissolve, check this for buffer
+        state.m_good = false;
+        
+        // Make bad output clean
+        rings.resize(size_at_start);
+        ring.clear();
+
+        // Reject this as a starting point
+        operation.visited.set_rejected();
+
+        // And clear all visit info
+        clear_visit_info(turns);
+    }
+};
+
+struct turn_assign_for_buffer
+{
+    static bool const include_no_turn = false;
+    static bool const include_degenerate = false;
+    static bool const include_opposite = true;
+
+    template <typename Point1, typename Point2, typename Turn, typename IntersectionInfo, typename DirInfo>
+    static inline void apply(Turn& turn, Point1 const& p1, Point2 const& p2, IntersectionInfo const& intersection_info, DirInfo const& dir_info)
+    {
+		detail::overlay::calculate_distance_policy::apply(turn, p1, p2,
+						intersection_info, dir_info);
+		if (dir_info.opposite && intersection_info.count == 2)
+		{
+			turn.is_opposite = true;
+		}
+    }
+};
+
+// Should follow traversal-turn-concept (enrichment, visit structure)
+// and adds index in piece vector to find it back
+template <typename Point>
+struct buffer_turn_operation : public detail::overlay::traversal_turn_operation<Point>
+{
+    int piece_index;
+
+    inline buffer_turn_operation()
+        : piece_index(-1)
+    {}
+};
+
+// Version for buffer including type of location, is_opposite, and helper variables
+template <typename Point>
+struct buffer_turn_info : public detail::overlay::turn_info<Point, buffer_turn_operation<Point> >
+{
+	bool is_opposite;
+    
+    intersection_location_type location;
+    
+    int count_within, count_on_helper, count_on_offsetted, count_on_corner;
+	int count_on_opposite, count_on_closed;
+    
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+	std::string debug_string;
+#endif
+
+    inline buffer_turn_info()
+		: is_opposite(false)
+        , location(location_ok)
+        , count_within(0)
+        , count_on_helper(0)
+        , count_on_offsetted(0)
+        , count_on_corner(0)
+		, count_on_opposite(0)
+		, count_on_closed(0)
+    {}
+};
+
+
+}} // namespace detail::buffer
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_POLICIES_HPP

Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -9,8 +9,10 @@
 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
 
+
 #include <cstddef>
 
+#include <set>
 #include <boost/range.hpp>
 
 #include <boost/geometry/core/coordinate_type.hpp>
@@ -25,10 +27,13 @@
 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/algorithms/detail/partition.hpp>
 
-#include <boost/geometry/extensions/algorithms/buffer/buffered_ring.hpp>
-
+#include <boost/geometry/iterators/closing_iterator.hpp>
 
+#include <boost/geometry/extensions/algorithms/buffer/buffered_ring.hpp>
+#include <boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp>
+#include <boost/geometry/extensions/algorithms/buffer/side_on_convex_range.hpp>
 
 
 namespace boost { namespace geometry
@@ -39,68 +44,20 @@
 namespace detail { namespace buffer
 {
 
-
-class backtrack_for_buffer
+enum piece_type
 {
-public :
-    typedef detail::overlay::backtrack_state state_type;
-
-    template <typename Operation, typename Rings, typename Turns, typename Geometry>
-    static inline void apply(std::size_t size_at_start, 
-                Rings& rings, typename boost::range_value<Rings>::type& ring,
-                Turns& turns, Operation& operation,
-                std::string const& reason,
-                Geometry const& ,
-                Geometry const& ,
-                state_type& state
-                )
-    {
-std::cout << "WARNING " << reason << std::endl;
-
-        // TODO this is a copy of dissolve, check this for buffer
-        state.m_good = false;
-        
-        // Make bad output clean
-        rings.resize(size_at_start);
-        ring.clear();
-
-        // Reject this as a starting point
-        operation.visited.set_rejected();
-
-        // And clear all visit info
-        clear_visit_info(turns);
-    }
+    buffered_segment, buffered_join, buffered_flat_end
 };
 
-enum intersection_location_type
+enum segment_relation_code
 {
-    location_ok, inside_buffer, inside_original
+    segment_relation_on_left, 
+    segment_relation_on_right, 
+    segment_relation_within,
+    segment_relation_disjoint
 };
 
 
-// Shoould follow traversal-turn-concept (enrichment, visit structure)
-// and adds index in piece vector to find it back
-template <typename Point>
-struct buffer_turn_operation : public detail::overlay::traversal_turn_operation<Point>
-{
-    int piece_index;
-
-    inline buffer_turn_operation()
-        : piece_index(-1)
-    {}
-};
-
-// Add an "intersection_location_type" which gets true for all intersection points lying inside the buffer or original polygon
-template <typename Point>
-struct buffer_turn_info : public detail::overlay::turn_info<Point, buffer_turn_operation<Point> >
-{
-    intersection_location_type location;
-
-    inline buffer_turn_info()
-        : location(location_ok)
-    {}
-};
-
 // In the end this will go (if we have a multi-point within/covered_by geometry)
 // which is optimized for multi-points and skips linestrings
 template <typename tag>
@@ -112,9 +69,9 @@
 struct check_original<polygon_tag>
 {
     template <typename Point, typename Geometry>
-    static inline bool apply(Point const& point, Geometry const& geometry)
+    static inline int apply(Point const& point, Geometry const& geometry)
     {
-        return geometry::covered_by(point, geometry);
+        return geometry::covered_by(point, geometry) ? 1 : -1;
     }
 };
 
@@ -122,249 +79,574 @@
 struct check_original<linestring_tag>
 {
     template <typename Point, typename Geometry>
-    static inline bool apply(Point const& point, Geometry const& geometry)
+    static inline int apply(Point const& point, Geometry const& geometry)
     {
-        return false;
+        return 0;
     }
 };
 
-template <typename Ring>
-struct buffered_piece_collection
+
+// Returns a pair, taking care that pair.first is smaller than pair.second
+template <typename T>
+inline std::pair<T, T> make_ordered_pair(T const& first, T const& second)
+{
+	return first < second 
+		? std::make_pair(first, second) 
+		: std::make_pair(second, first)
+		;
+}
+
+// TODO replace double by T
+template <typename P1, typename P2>
+inline double calculate_angle(P1 const& from_point, P2 const& to_point)
 {
-    typedef typename geometry::point_type<Ring>::type Point;
-    typedef typename strategy::side::services::default_strategy<typename cs_tag<Point>::type>::type side_strategy;
+    typedef P1 vector_type;
+    vector_type v = from_point;
+    geometry::subtract_point(v, to_point);
+    return atan2(geometry::get<1>(v), geometry::get<0>(v));
+}
 
-    enum piece_type
-    {
-        buffered_segment, buffered_join
-    };
+template <typename Iterator, typename Vector>
+inline Iterator advance_circular(Iterator it, Vector const& vector, int increment = 1)
+{
+	if (it == boost::begin(vector) && increment < 0)
+	{
+		it = boost::end(vector);
+	}
+	it += increment;
+	if (it == boost::end(vector))
+	{
+		it = boost::begin(vector);
+	}
+	return it;
+}
 
-    template <typename Turn>
-    struct redundant_turn
-    {
-        inline bool operator()(Turn const& turn) const
-        {
-            return turn.location != location_ok;
-        }
-    };
+
+// BEGIN clustered
+// TODO will be restructured and moved to clustered-manager
+
+struct angle_info
+{
+    double angle; // TODO: T
+    bool incoming;
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+    std::string debug_info;
+    bool debug;
+#endif
+
+};
+
+struct cluster_info
+{
+    std::vector<angle_info> angles;
+};
+
+struct buffer_cluster_info : public cluster_info
+{
+    std::set<segment_identifier> seg_ids;
+    std::set<int> turn_indices;
+};
+
+// END clustered
+
+
+template <typename Ring>
+struct buffered_piece_collection
+{
+    typedef typename geometry::point_type<Ring>::type point_type;
 
     struct piece
     {
         piece_type type;
         int index;
-        segment_identifier seg_id;
-
-        typedef geometry::model::linestring<Point> buffered_vector_type;
 
         // These both form a complete clockwise ring for each piece (with one dupped point)
-        buffered_vector_type offsetted_segment;
-        buffered_vector_type helper_segments; // 3 for segment, 2 for join - might be empty too
+
+		// 1: half, part of offsetted_rings
+        segment_identifier first_seg_id;
+        int last_segment_index; // no segment-identifier - it is always the same
+
+		// 2: half, not part (will be indexed in one vector too)
+        std::vector<point_type> helper_segments; // 3 points for segment, 2 points for join - 0 points for flat-end
     };
 
+    typedef typename strategy::side::services::default_strategy
+		<
+			typename cs_tag<point_type>::type
+		>::type side_strategy;
     typedef std::vector<piece> piece_vector;
-    piece_vector all_pieces;
-    buffered_ring_collection<buffered_ring<Ring> > offsetted_rings;
+
+    piece_vector m_pieces;
+    buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; // indexed by multi_index
     buffered_ring_collection<Ring> traversed_rings;
     segment_identifier current_segment_id;
 
-    typedef std::vector<buffer_turn_info<Point> > turn_vector_type;
+    typedef std::vector<buffer_turn_info<point_type> > turn_vector_type;
     typedef detail::overlay::get_turn_info
         <
-            Point, Point, buffer_turn_info<Point>,
-            detail::overlay::calculate_distance_policy
+            point_type, point_type, buffer_turn_info<point_type>,
+            turn_assign_for_buffer
         > turn_policy;
-    turn_vector_type turn_vector;
+    turn_vector_type m_turns;
+
 
+	// Segment pairs which are opposite are used to discard turns lying on them
+    typedef std::set<std::pair<segment_identifier, segment_identifier> > opposite_set_type;
+    opposite_set_type m_opposite_segments;
+	// To fast check if it is in:
+	std::set<segment_identifier> m_in_opposite_segments;
 
 
-    inline buffered_piece_collection()
-    {}
+    typedef std::map<point_type, buffer_cluster_info, geometry::less<point_type> > clustered_location_type;
+    clustered_location_type clustered_turn_locations;
 
 
-    inline bool within_piece(buffer_turn_info<Point> const& turn, piece const& pc) const
+    inline bool is_neighbor(piece const& piece1, piece const& piece2) const
     {
-        bool const collinear =
-            turn.operations[0].operation == detail::overlay::operation_continue
-            && turn.operations[0].operation == detail::overlay::operation_continue;
+        if (std::abs(piece1.index - piece2.index) == 1)
+        {
+            return true;
+        }
 
-        // TODO factor out the two loops
+        // TODO: of the same multi_index
+        int const b = boost::size(m_pieces) - 1; // back
+        return (piece1.index == 0 && piece2.index == b)
+            || (piece1.index == b && piece2.index == 0)
+            ;
+    }
 
-        typedef typename boost::range_iterator
-            <
-                typename piece::buffered_vector_type const
-            >::type iterator_type;
+    inline bool skip_neighbor(piece const& piece1, piece const& piece2) const
+    {
+        return piece1.type != piece2.type && is_neighbor(piece1, piece2);
+    }
 
-        if (boost::size(pc.helper_segments) > 0)
+    template <typename Range, typename Iterator>
+    inline typename boost::range_value<Range const>::type next_point(Range const& range, Iterator it) const
+    {
+        Iterator next = it;
+        ++next;
+
+		// Get next point. If end get second point (because ring is assumed to be closed)
+		return next != boost::end(range) ? *next : *(boost::begin(range) + 1);
+    }
+
+    inline void calculate_turns(piece const& piece1, piece const& piece2)
+    {
+        buffer_turn_info<point_type> the_model;
+        the_model.operations[0].piece_index = piece1.index;
+        the_model.operations[0].seg_id = piece1.first_seg_id;
+
+        typedef typename boost::range_iterator<buffered_ring<Ring> const>::type iterator;
+
+		segment_identifier seg_id1 = piece1.first_seg_id;
+		segment_identifier seg_id2 = piece2.first_seg_id;
+
+		if (seg_id1.segment_index < 0 || seg_id2.segment_index < 0)
+		{
+			return;
+		}
+
+		buffered_ring<Ring> const& ring1 = offsetted_rings[seg_id1.multi_index];
+		iterator it1_first = boost::begin(ring1) + seg_id1.segment_index;
+		iterator it1_last = boost::begin(ring1) + piece1.last_segment_index;
+
+		buffered_ring<Ring> const& ring2 = offsetted_rings[seg_id2.multi_index];
+		iterator it2_first = boost::begin(ring2) + seg_id2.segment_index;
+		iterator it2_last = boost::begin(ring2) + piece2.last_segment_index;
+
+        iterator it1 = it1_first;
+        for (iterator prev1 = it1++; 
+                it1 != it1_last; 
+                prev1 = it1++, the_model.operations[0].seg_id.segment_index++)
         {
-            iterator_type it = boost::begin(pc.helper_segments);
-            for (iterator_type prev = it++;
-                it != boost::end(pc.helper_segments);
-                prev = it++)
+            the_model.operations[1].piece_index = piece2.index;
+            the_model.operations[1].seg_id = piece2.first_seg_id;
+
+            iterator it2 = it2_first;
+            for (iterator prev2 = it2++; 
+                    it2 != it2_last;
+                    prev2 = it2++, the_model.operations[1].seg_id.segment_index++)
             {
-                int side = side_strategy::apply(turn.point, *prev, *it);
-                switch(side)
-                {
-                    case 1 : return false;
-                    case 0 : return true;
-                }
+                // Revert (this is used more often - should be common function TODO)
+                the_model.operations[0].other_id = the_model.operations[1].seg_id;
+                the_model.operations[1].other_id = the_model.operations[0].seg_id;
+
+                turn_policy::apply(*prev1, *it1, next_point(ring1, it1),
+                                    *prev2, *it2, next_point(ring2, it2),
+                                    the_model, std::back_inserter(m_turns));
             }
         }
+    }
+
+	inline void fill_opposite_segments()
+	{
+        for (typename boost::range_iterator<turn_vector_type const>::type it =
+            boost::begin(m_turns); it != boost::end(m_turns); ++it)
+        {
+			if (it->is_opposite)
+			{
+				m_opposite_segments.insert(make_ordered_pair(it->operations[0].seg_id, it->operations[1].seg_id));
+				m_in_opposite_segments.insert(it->operations[0].seg_id);
+				m_in_opposite_segments.insert(it->operations[1].seg_id);
+			}
+		}
+	}
 
-        if (boost::size(pc.offsetted_segment) > 0)
+	inline segment_relation_code get_segment_relation(point_type const& point,
+                segment_identifier const& seg_id) const
+	{
+		typedef typename boost::range_iterator<std::vector<point_type> const>::type iterator_type;
+		iterator_type it = boost::begin(offsetted_rings[seg_id.multi_index]) + seg_id.segment_index;
+		iterator_type prev = it++;
+		int side = side_strategy::apply(point, *prev, *it);
+        if (side == 0)
         {
-            iterator_type it = boost::begin(pc.offsetted_segment);
-            for (iterator_type prev = it++;
-                it != boost::end(pc.offsetted_segment);
-                prev = it++)
+            if (geometry::equals(point, *prev))
             {
-                int side = side_strategy::apply(turn.point, *prev, *it);
-                switch(side)
-                {
-                    case 1 : return false;
-                    case 0 : return !collinear;
-                }
+                return segment_relation_on_left;
+            }
+            else if (geometry::equals(point, *it))
+            {
+                return segment_relation_on_right;
+            }
+            else if (collinear_point_on_segment(point, *prev, *it))
+            {
+                return segment_relation_within;
             }
         }
+        return segment_relation_disjoint;
+	}
 
-        return true;
-    }
-
-    // Checks if an intersection point is within one of all pieces
-    // (but skip the pieces of which this intersection point is the result
-    inline bool is_wrong(buffer_turn_info<Point> const& turn, piece const& piece1, piece const& piece2) const
+	// TODO will be restructured and moved to clustered-manager
+    inline void get_points(point_type const& point, buffer_turn_operation<point_type> const& operation, angle_info& tp1, angle_info& tp2) const
     {
-        // We might do this using partition.
-        typename std::vector<piece>::const_iterator it;
-        for (it = boost::begin(all_pieces);
-            it != boost::end(all_pieces);
-            ++it)
+        typedef typename boost::range_iterator
+            <
+                Ring const
+            >::type iterator_type;
+
+        //typedef geometry::ever_circling_iterator<iterator_type> ec_iterator_type;
+
+        std::ostringstream out;
+        out << operation.seg_id.segment_index << "/" << operation.other_id.segment_index << " " << operation_char(operation.operation);
+
+        // Get the vectors (coming in, and going out of this point)
+        buffered_ring<Ring> const& ring = offsetted_rings[operation.seg_id.multi_index];
+
+		iterator_type it = boost::begin(ring) + operation.seg_id.segment_index;
+
+        if (geometry::equals(point, *it))
         {
-            if (it->index != piece1.index && it->index != piece2.index)
-            {
-                if (within_piece(turn, *it))
-                {
-                    return true;
-                }
-            }
+			it = advance_circular(it, ring, -1);
+        }
+
+        tp1.incoming = true;
+        tp1.angle = calculate_angle(*it, point);
+
+		it = advance_circular(it, ring);
+		int const n = boost::size(ring);
+        for (int defensive_check = 0; 
+			geometry::equals(point, *it) && defensive_check < n; 
+			defensive_check++)
+        {
+			it = advance_circular(it, ring);
         }
 
-        return false;
+        tp2.incoming = false;
+        tp2.angle = calculate_angle(*it, point);
 
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+        tp1.debug = operation.seg_id.segment_index == 32;
+        tp1.debug_info = out.str();
+        tp2.debug_info = out.str();
+        tp2.debug = operation.seg_id.segment_index == 32;
+#endif
     }
 
-    inline bool is_neighbor(piece const& piece1, piece const& piece2) const
+    inline void add_segment(int index, point_type const& point, buffer_turn_operation<point_type> const& operation)
     {
-        if (std::abs(piece1.index - piece2.index) == 1)
+        clustered_location_type::iterator it = clustered_turn_locations.find(point);
+        if (it == boost::end(clustered_turn_locations))
         {
-            return true;
+            buffer_cluster_info a;
+			std::pair<clustered_location_type::iterator, bool> pair = clustered_turn_locations.insert(std::make_pair(point, a));
+            it = pair.first;
         }
 
-        int const b = boost::size(all_pieces) - 1; // back
-        return (piece1.index == 0 && piece2.index == b)
-            || (piece1.index == b && piece2.index == 0)
-            ;
-    }
+        buffer_cluster_info& admin = it->second;
+        admin.turn_indices.insert(index);
+        if (admin.seg_ids.count(operation.seg_id) <= 0)
+        {
+            admin.seg_ids.insert(operation.seg_id);
 
-    inline bool skip_neighbor(piece const& piece1, piece const& piece2) const
-    {
-        return piece1.type != piece2.type && is_neighbor(piece1, piece2);
+            angle_info tp[2];
+            get_points(point, operation, tp[0], tp[1]);
+            admin.angles.push_back(tp[0]);
+            admin.angles.push_back(tp[1]);
+        }
     }
 
-    template <typename Iterator>
-    inline Point next_point(piece const& piece, Iterator it) const
+    inline void classify_opposed(int index, buffer_turn_info<point_type>& turn)
     {
-        // Next point in current offseted:
-        Iterator next = it;
-        ++next;
-        if (next != boost::end(piece.offsetted_segment))
+		if (m_in_opposite_segments.count(turn.operations[0].seg_id) > 0
+			|| m_in_opposite_segments.count(turn.operations[1].seg_id) > 0)
         {
-            return *next;
+            add_segment(index, turn.point, turn.operations[0]);
+            add_segment(index, turn.point, turn.operations[1]);
         }
 
-        // TODO: check if there is a second point (there should be one)
-        // Second point from next piece:
-        int next_index = piece.index + 1;
-        if (next_index >= boost::size(all_pieces))
+		bool check_opposite =
+			! turn.opposite()
+			&& ! turn.blocked()
+			&& ((turn.operations[0].operation != detail::overlay::operation_blocked && m_in_opposite_segments.count(turn.operations[0].seg_id) > 0)
+				|| (turn.operations[1].operation != detail::overlay::operation_blocked && m_in_opposite_segments.count(turn.operations[1].seg_id) > 0));
+
+		if (! check_opposite)
+		{
+            return;
+        }
+
+        for (opposite_set_type::const_iterator it = boost::begin(m_opposite_segments);
+            it != boost::end(m_opposite_segments);
+            ++it)
         {
-            next_index = 0;
+            // TODO: if it has something todo with it (operations/first/second):
+            segment_relation_code const code1 = get_segment_relation(turn.point, it->first);
+            segment_relation_code const code2 = get_segment_relation(turn.point, it->second);
+
+            if (code1 == segment_relation_within && code2 == segment_relation_within)
+            {
+                turn.count_on_opposite++;
+                return;
+            }
         }
-        return piece.offsetted_segment[1];
     }
 
-    inline void calculate_turns(piece const& piece1, piece const& piece2)
+
+    inline void classify_turn(buffer_turn_info<point_type>& turn, piece const& pc) const
     {
-        buffer_turn_info<Point> the_model;
-        the_model.operations[0].piece_index = piece1.index;
-        the_model.operations[0].seg_id = piece1.seg_id;
+        if (pc.type == buffered_flat_end)
+        {
+            return;
+        }
 
-        // TODO use partition
-        typedef typename boost::range_iterator<typename piece::buffered_vector_type const>::type iterator;
-        iterator it1 = boost::begin(piece1.offsetted_segment);
-        for (iterator prev1 = it1++; 
-                it1 != boost::end(piece1.offsetted_segment); 
-                prev1 = it1++, the_model.operations[0].seg_id.segment_index++)
+		int flat_ends_involved = 0;
+        for (int i = 0; i < boost::size(turn.operations); i++)
         {
-            the_model.operations[1].piece_index = piece2.index;
-            the_model.operations[1].seg_id = piece2.seg_id;
+			// Don't check any turn against a piece of which is itself the result
+			if (turn.operations[i].piece_index == pc.index)
+			{
+				return;
+			}
 
-            iterator it2 = boost::begin(piece2.offsetted_segment);
-            for (iterator prev2 = it2++; 
-                    it2 != boost::end(piece2.offsetted_segment); 
-                    prev2 = it2++, the_model.operations[1].seg_id.segment_index++)
+            piece const& piece_from_intersection = m_pieces[turn.operations[i].piece_index];
+            if (piece_from_intersection.type == buffered_flat_end)
+			{
+				flat_ends_involved++;
+			}
+		}
+
+        int side_helper = side_on_convex_range<side_strategy>(turn.point, pc.helper_segments);
+        if (side_helper == 1)
+        {
+			// Left or outside
+            return;
+        }
+
+		segment_identifier seg_id = pc.first_seg_id;
+		if (seg_id.segment_index < 0)
+		{
+			// Should not occur
+			std::cout << "Warning: negative segment_index" << std::endl;
+			return;
+		}
+
+		segment_identifier on_segment_seg_id;
+
+		buffered_ring<Ring> const& ring = offsetted_rings[seg_id.multi_index];
+
+        int const side_offsetted = side_on_convex_range<side_strategy>(turn.point, 
+						boost::begin(ring) + seg_id.segment_index, 
+						boost::begin(ring) + pc.last_segment_index,
+						seg_id, on_segment_seg_id);
+        if (side_offsetted == 1)
+        {
+            return;
+        }
+
+        if (side_offsetted == -1 && side_helper == -1)
+        {
+            // It is within (assumed that both halves form a closed convex clockwise ring)
+            turn.count_within++;
+        }
+        if (side_offsetted == 0)
+        {
+	        turn.count_on_offsetted++;
+        }
+        if (side_helper == 0)
+        {
+            if (geometry::equals(turn.point, pc.helper_segments.back())
+                || geometry::equals(turn.point, pc.helper_segments.front()))
             {
-                // Revert (this is used more often - should be common function TODO)
-                the_model.operations[0].other_id = the_model.operations[1].seg_id;
-                the_model.operations[1].other_id = the_model.operations[0].seg_id;
+                turn.count_on_corner++;
+            }
+            else
+            {
+				if (flat_ends_involved == 0)
+				{
+					turn.count_on_helper++;
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+					std::ostringstream out;
+					out << "HLP " << pc.index;
+					turn.debug_string += out.str();
+#endif
+				}
+				else
+				{
+					turn.count_on_corner++;
+				}
+            }
+        }
+    }
+
+	inline void classify_closed()
+	{
+		struct angle_sort
+		{
+			inline bool operator()(angle_info const& left, angle_info const& right) const
+			{
+				return geometry::math::equals(left.angle, right.angle)
+					? int(left.incoming) < int(right.incoming)
+					: left.angle < right.angle
+					;
+			}
+		};
+
+        for (typename boost::range_iterator<clustered_location_type>::type it =
+	            boost::begin(clustered_turn_locations);
+			it != boost::end(clustered_turn_locations); ++it)
+        {
+	        buffer_cluster_info& admin = it->second;
+			if (boost::size(admin.angles) > 1)
+			{
+				std::sort(admin.angles.begin(), admin.angles.end(), angle_sort());
+
+				if (boost::size(admin.angles) == 10)
+				{
+					int kkk = 0;
+				}
+
+				// Verify if completely closed
+				bool closed = true;
+
+				typedef geometry::closing_iterator<std::vector<angle_info> const> closing_iterator;
+				closing_iterator vit(admin.angles);
+				closing_iterator end(admin.angles, true);
+
+				closing_iterator prev = vit++;
+				for( ; vit != end && closed; prev = vit++)
+				{
+					if (! geometry::math::equals(prev->angle, vit->angle)
+						&& ! prev->incoming
+						&& vit->incoming)
+					{
+						closed = false;
+					}
+				}
+				if (closed)
+				{
+					for (std::set<int>::iterator sit = admin.turn_indices.begin();
+						sit != admin.turn_indices.end();
+						++sit)
+					{
+						m_turns[*sit].count_on_closed++;
+					}
+				}
+			}
+        }
+	}
 
+	inline void classify_opposed()
+    {
+        int index = 0;
+        for (typename boost::range_iterator<turn_vector_type>::type it =
+            boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index)
+        {
+            classify_opposed(index, *it);
+		}
+	}
 
-                turn_vector_type turns; // TEMPORARY in the end we can add directly to turn_vector
-                turn_policy::apply(*prev1, *it1, next_point(piece1, it1),
-                                    *prev2, *it2, next_point(piece2, it2),
-                                    the_model, std::back_inserter(turns));
-
-                // Check if it is inside any of the pieces
-                for (typename boost::range_iterator<turn_vector_type>::type it =
-                    boost::begin(turns); it != boost::end(turns); ++it)
+
+    inline void classify_turns()
+    {
+
+        // Check if it is inside any of the pieces
+        // Now: quadratic
+        // TODO: in partition.
+        for (typename boost::range_iterator<turn_vector_type>::type it =
+            boost::begin(m_turns); it != boost::end(m_turns); ++it)
+		{
+            if (it->count_on_opposite == 0 && it->count_on_closed == 0)
+            {
+                typename std::vector<piece>::const_iterator pit;
+                for (pit = boost::begin(m_pieces);
+                    pit != boost::end(m_pieces);
+                    ++pit)
                 {
-                    // TODO: much later in partition.
-                    if (is_wrong(*it, piece1, piece2))
-                    {
-                        it->location = inside_buffer;
-                    }
-                    turn_vector.push_back(*it);
+                    classify_turn(*it, *pit);
                 }
             }
         }
+
+		// Set results:
+        for (typename boost::range_iterator<turn_vector_type>::type it =
+            boost::begin(m_turns); it != boost::end(m_turns); ++it)
+        {
+            if (it->count_within > 0 
+                || it->count_on_helper > 0
+				|| it->count_on_opposite > 0
+				|| it->count_on_closed > 0
+				)
+            {
+                it->location = inside_buffer;
+            }
+        }
     }
 
     template <typename Geometry>
-    inline void check_remaining_points(Geometry const& input_geometry)
+    inline void check_remaining_points(Geometry const& input_geometry, int factor)
     {
         // TODO: this should be done as a collection-of-points, for performance
         for (typename boost::range_iterator<turn_vector_type>::type it =
-            boost::begin(turn_vector); it != boost::end(turn_vector); ++it)
+            boost::begin(m_turns); it != boost::end(m_turns); ++it)
         {
-            if (it->location == location_ok
-                && check_original
+            if (it->location == location_ok)
+			{
+				int code = check_original
                         <
                             typename geometry::tag<Geometry>::type
-                        >::apply(it->point, input_geometry))
-            {
-                it->location = inside_original;
-            }
+                        >::apply(it->point, input_geometry);
+				if (code * factor == 1)
+				{
+					it->location = inside_original;
+				}
+			}
         }
     }
 
-
     template <typename Geometry>
-    inline void get_turns(Geometry const& input_geometry)
+    inline void get_turns(Geometry const& input_geometry, int factor)
     {
-        for(typename piece_vector::const_iterator it1 = boost::begin(all_pieces);
-            it1 != boost::end(all_pieces);
+		// Now: quadratic
+        // TODO use partition
+
+        for(typename piece_vector::const_iterator it1 = boost::begin(m_pieces);
+            it1 != boost::end(m_pieces);
             ++it1)
         {
             for(typename piece_vector::const_iterator it2 = it1 + 1;
-                it2 != boost::end(all_pieces);
+                it2 != boost::end(m_pieces);
                 ++it2)
             {
                 if (! skip_neighbor(*it1, *it2))
@@ -373,15 +655,19 @@
                 }
             }
         }
+
+		fill_opposite_segments();
+		classify_opposed();
+        classify_closed();
+        classify_turns();
+
         if (boost::is_same<typename tag_cast<typename tag<Geometry>::type, areal_tag>::type, areal_tag>())
         {
-            check_remaining_points(input_geometry);
+            check_remaining_points(input_geometry, factor);
         }
-
-        calculate_discarded();
     }
 
-    inline void add_input()
+    inline void start_new_ring()
     {
         int const n = offsetted_rings.size();
         current_segment_id.source_index = 0;
@@ -392,7 +678,7 @@
         offsetted_rings.resize(n + 1);
     }
 
-    inline void add_point(Point const& p)
+    inline int add_point(point_type const& p)
     {
         BOOST_ASSERT
             (
@@ -401,32 +687,31 @@
 
         current_segment_id.segment_index++;
         offsetted_rings.back().push_back(p);
+		return offsetted_rings.back().size();
     }
 
-
     inline piece& add_piece(piece_type type, bool decrease_by_one)
     {
         piece pc;
         pc.type = type;
-        pc.index = boost::size(all_pieces);
-        pc.seg_id = current_segment_id;
+        pc.index = boost::size(m_pieces);
+        pc.first_seg_id = current_segment_id;
 
         std::size_t const n = boost::size(offsetted_rings.back());
+        pc.first_seg_id.segment_index = decrease_by_one ? n - 1 : n;
 
-        pc.seg_id.segment_index = decrease_by_one ? n - 1 : n;
-
-        all_pieces.push_back(pc);
-        return all_pieces.back();
+        m_pieces.push_back(pc);
+        return m_pieces.back();
     }
 
-
-    inline void add_piece(Point const& p1, Point const& p2, 
-            Point const& b1, Point const& b2)
+    inline void add_piece(piece_type type, point_type const& p1, point_type const& p2, 
+            point_type const& b1, point_type const& b2)
     {
-        bool const last_type_join = ! all_pieces.empty() 
-                && all_pieces.back().type != buffered_segment;
+        bool const last_type_join = ! m_pieces.empty() 
+				&& m_pieces.back().first_seg_id.multi_index == current_segment_id.multi_index
+                && m_pieces.back().type == buffered_join;
 
-        piece& pc = add_piece(buffered_segment, last_type_join);
+        piece& pc = add_piece(type, last_type_join);
 
         // If it follows the same piece-type point both should be added.
         // There should be two intersections later and it should be discarded.
@@ -435,10 +720,8 @@
         {
             add_point(b1);
         }
-        add_point(b2);
+        pc.last_segment_index = add_point(b2);
 
-        pc.offsetted_segment.push_back(b1);
-        pc.offsetted_segment.push_back(b2);
         pc.helper_segments.push_back(b2);
         pc.helper_segments.push_back(p2);
         pc.helper_segments.push_back(p1);
@@ -446,11 +729,12 @@
     }
 
     template <typename Range>
-    inline piece& add_piece(Range const& range)
+    inline piece& add_piece(piece_type type, Range const& range)
     {
-        piece& pc = add_piece(buffered_join, true);
+        piece& pc = add_piece(type, true);
 
         bool first = true;
+		int last = offsetted_rings.back().size() + 1;
         for (typename Range::const_iterator it = boost::begin(range);
             it != boost::end(range);
             ++it)
@@ -464,18 +748,20 @@
             }
             if (add)
             {
-                add_point(*it);
+                last = add_point(*it);
             }
 
-            pc.offsetted_segment.push_back(*it);
         }
+
+        pc.last_segment_index = last;
+
         return pc;
     }
 
     template <typename Range>
-    inline void add_piece(Point const& p, Range const& range)
+    inline void add_piece(piece_type type, point_type const& p, Range const& range)
     {
-        piece& pc = add_piece(range);
+        piece& pc = add_piece(type, range);
 
         if (boost::size(range) > 0)
         {
@@ -492,7 +778,7 @@
             typename cs_tag<Ring>::type
         >::type side_strategy_type;
 
-        enrich_intersection_points<false, false>(turn_vector,
+        enrich_intersection_points<false, false>(m_turns,
                     detail::overlay::operation_union,
                     offsetted_rings, offsetted_rings,
                     side_strategy_type());
@@ -500,10 +786,10 @@
 
     // Discards all rings which do have not-OK intersection points only.
     // Those can never be traversed and should not be part of the output.
-    inline void calculate_discarded()
+    inline void discard_rings()
     {
         for (typename boost::range_iterator<turn_vector_type const>::type it =
-            boost::begin(turn_vector); it != boost::end(turn_vector); ++it)
+            boost::begin(m_turns); it != boost::end(m_turns); ++it)
         {
             if (it->location != location_ok)
             {
@@ -518,13 +804,25 @@
         }
     }
                     
-    inline void discard_points()
+    inline void discard_turns()
     {
-        // Erase all points being inside
-        turn_vector.erase(
-            std::remove_if(boost::begin(turn_vector), boost::end(turn_vector),
-            redundant_turn<buffer_turn_info<Point> >()),
-            boost::end(turn_vector));
+		struct redundant_turn
+		{
+			inline bool operator()(buffer_turn_info<point_type> const& turn) const
+			{
+				// Erase discarded turns (location not OK) and the turns
+				// only used to detect oppositeness.
+				return turn.location != location_ok 
+					|| turn.opposite();
+			}
+		};
+
+        m_turns.erase
+			(
+				std::remove_if(boost::begin(m_turns), boost::end(m_turns),
+								redundant_turn()),
+				boost::end(m_turns)
+			);
 
     }
 
@@ -533,20 +831,20 @@
         typedef detail::overlay::traverse
             <
                 false, false, 
-                buffered_ring_collection<buffered_ring<Ring > >, buffered_ring_collection<buffered_ring<Ring > >,
+                buffered_ring_collection<buffered_ring<Ring> >, buffered_ring_collection<buffered_ring<Ring > >,
                 backtrack_for_buffer
             > traverser;
 
         traversed_rings.clear();
         traverser::apply(offsetted_rings, offsetted_rings,
                         detail::overlay::operation_union,
-                        turn_vector, traversed_rings);
+                        m_turns, traversed_rings);
     }
 
     template <typename GeometryOutput, typename OutputIterator>
     inline OutputIterator assign(OutputIterator out)
     {
-        typedef detail::overlay::ring_properties<Point> properties;
+        typedef detail::overlay::ring_properties<point_type> properties;
 
         std::map<ring_identifier, properties> selected;
 
@@ -578,117 +876,6 @@
         return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out);
     }
 
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-
-    template <typename Mapper>
-    inline void map_turns(Mapper& mapper)
-    {
-        int index = 0;
-        for (typename boost::range_iterator<turn_vector_type>::type it =
-            boost::begin(turn_vector); it != boost::end(turn_vector); ++it)
-        {
-            std::string fill = "fill:rgb(0,255,0);";
-            switch(it->location)
-            {
-                case inside_buffer : fill = "fill:rgb(255,0,0);"; break;
-                case inside_original : fill = "fill:rgb(0,0,255);"; break;
-            }
-            mapper.map(it->point, fill, 6);
-            std::ostringstream out;
-            //out << it->operations[0].piece_index << "/" << it->operations[1].piece_index;
-            out << " " <<  all_pieces[it->operations[0].piece_index].seg_id.segment_index
-                 << "+" << all_pieces[it->operations[1].piece_index].seg_id.segment_index;
-            //out << " " <<  all_pieces[it->operations[0].piece_index].index_in_all_points
-            //     << "," << all_pieces[it->operations[1].piece_index].index_in_all_points;
-            //out << " " <<  it->operations[0].seg_id.segment_index
-            //     << "|" << it->operations[1].seg_id.segment_index;
-            out << ":" << operation_char(it->operations[0].operation);
-            mapper.text(it->point, out.str(), "fill:rgb(0,0,0);font-family='Arial';", 5, 5);
-        }
-    }
-
-    template <typename Tag, typename Mapper>
-    inline void map(Mapper& mapper)
-    {
-        for(typename piece_vector::const_iterator it = boost::begin(all_pieces);
-            it != boost::end(all_pieces);
-            ++it)
-        {
-            Ring corner;
-            std::copy(boost::begin(it->offsetted_segment), 
-                    boost::end(it->offsetted_segment), 
-                    std::back_inserter(corner));
-            std::copy(boost::begin(it->helper_segments), 
-                    boost::end(it->helper_segments), 
-                    std::back_inserter(corner));
-
-            if (it->type == buffered_segment)
-            {
-                if(boost::is_same<Tag, ring_tag>::value || boost::is_same<Tag, polygon_tag>::value)
-                {
-                    mapper.map(corner, "opacity:0.3;fill:rgb(255,128,0);stroke:rgb(0,0,0);stroke-width:1");
-                }
-                else if(boost::is_same<Tag, linestring_tag>::value)
-                {
-                    mapper.map(corner, "opacity:0.3;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1");
-                }
-            }
-            else
-            {
-                mapper.map(corner, "opacity:0.3;fill:rgb(255,0,0);stroke:rgb(0,0,0);stroke-width:1");
-            }
-
-
-            // Put starting segment_index in centroid
-            Point centroid;
-            geometry::centroid(corner, centroid);
-            std::ostringstream out;
-            out << it->seg_id.segment_index;
-            mapper.text(centroid, out.str(), "fill:rgb(255,0,0);font-family='Arial';", 5, 5);
-
-        }
-
-        int index = 0;
-        for (typename boost::range_iterator<std::vector<Point> >::type it =
-            boost::begin(offsetted_rings.front()); it != boost::end(offsetted_rings.front()); ++it)
-        {
-            mapper.map(*it, "fill:rgb(0,0,0);", 2);
-            std::ostringstream out;
-            out << index++;
-            mapper.text(*it, out.str(), "fill:rgb(0,0,255);font-family='Arial';", -5, -5);
-        }
-
-    }
-
-    template <typename Mapper>
-    inline void map_traverse(Mapper& mapper)
-    {
-        for(typename buffered_ring_collection<Ring>::const_iterator it = boost::begin(traversed_rings);
-            it != boost::end(traversed_rings);
-            ++it)
-        {
-            mapper.map(*it, "opacity:0.4;fill:none;stroke:rgb(0,255,0);stroke-width:8");
-        }
-    }
-
-    template <typename Mapper>
-    inline void map_offsetted(Mapper& mapper)
-    {
-        for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings);
-            it != boost::end(offsetted_rings);
-            ++it)
-        {
-            if (it->discarded())
-            {
-                mapper.map(*it, "opacity:0.4;fill:none;stroke:rgb(255,0,0);stroke-width:8");
-            }
-            else
-            {
-                mapper.map(*it, "opacity:0.4;fill:none;stroke:rgb(0,0,255);stroke-width:8");
-            }
-        }
-    }
-#endif
 };
 
 

Added: trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection_with_mapper.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection_with_mapper.hpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -0,0 +1,276 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2012 Barend Gehrels, 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_BUFFERED_PIECE_COLLECTION_WM_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_WM_HPP
+
+
+#include <boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp>
+#include <boost/geometry/algorithms/unique.hpp>
+
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace buffer
+{
+
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ 
+template <typename Ring>
+struct buffered_piece_collection_with_mapper 
+        : public buffered_piece_collection<Ring>
+{
+
+
+    template <typename Mapper>
+    inline void map_opposite_locations(Mapper& mapper)
+    {
+        for (typename boost::range_iterator<clustered_location_type const>::type it =
+            boost::begin(clustered_turn_locations); 
+            it != boost::end(clustered_turn_locations); ++it)
+        {
+			mapper.map(it->first, "fill:rgb(0,128,0);", 3);
+
+    		std::ostringstream out;
+			out << it->second.angles.size();
+            for (std::set<int>::const_iterator sit = it->second.turn_indices.begin(); sit != it->second.turn_indices.end(); ++sit)
+            {
+                out << "," << *sit;
+            }
+    		mapper.text(it->first, out.str(), "fill:rgb(0,128,0);font-family='Arial';font-size:8px", 6, 8);
+
+            for (unsigned int i = 0; i < it->second.angles.size(); i++)
+            {
+                geometry::model::linestring<point_type> line;
+                angle_info const& tp = it->second.angles[i];
+                point_type p1, p2;
+                geometry::set<0>(p1, geometry::get<0>(it->first) + cos(tp.angle) * 0.1);
+                geometry::set<1>(p1, geometry::get<1>(it->first) + sin(tp.angle) * 0.1);
+                geometry::set<0>(p2, geometry::get<0>(it->first) + cos(tp.angle) * 0.4);
+                geometry::set<1>(p2, geometry::get<1>(it->first) + sin(tp.angle) * 0.4);
+    			std::ostringstream out;
+                //out << tp.angle << " " << int(tp.incoming);
+                out << (tp.incoming ? "i" : "o") << " " << i;
+                if (tp.incoming)
+                {
+                    int offset = 7;
+                    if (tp.debug) offset += 5;
+                    out << " " << tp.debug_info;
+                    line.push_back(p1);
+                    line.push_back(p2);
+    			    mapper.map(line, "stroke:rgb(0,0,255);stroke-width:1", 1);
+    			    mapper.map(p1, "fill:rgb(0,0,0);", 2);
+    			    mapper.text(p2, out.str(), "fill:rgb(0,0,255);font-family='Arial';font-size:8px", 2, offset);
+                }
+                else
+                {
+                    line.push_back(p1);
+                    line.push_back(p2);
+    			    mapper.map(line, "stroke:rgb(255,0,0);stroke-width:1", 1);
+    			    mapper.map(p2, "fill:rgb(0,0,0);", 2);
+    			    mapper.text(p2, out.str(), "fill:rgb(0,0,255);font-family='Arial';font-size:8px", 2, -2);
+                }
+            }
+        }
+    }
+
+    template <typename Mapper>
+    inline void map_turns(Mapper& mapper)
+    {
+        typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
+        std::map<std::pair<coordinate_type, coordinate_type>, int> offsets;
+
+
+        int index = 0;
+        for (typename boost::range_iterator<turn_vector_type>::type it =
+            boost::begin(m_turns); it != boost::end(m_turns); ++it)
+        {
+			if (! it->opposite())
+			{
+				std::pair<coordinate_type, coordinate_type> p
+					= std::make_pair(geometry::get<0>(it->point), geometry::get<1>(it->point));
+
+				char color = 'g';
+				std::string fill = "fill:rgb(0,255,0);";
+				switch(it->location)
+				{
+					case inside_buffer : fill = "fill:rgb(255,0,0);"; color = 'r'; break;
+					case inside_original : fill = "fill:rgb(0,0,255);"; color = 'b'; break;
+				}
+				std::ostringstream out;
+				out << it->operations[0].piece_index << "/" << it->operations[1].piece_index << std::endl;
+				//out << " " <<  m_pieces[it->operations[0].piece_index].first_seg_id.segment_index
+				//     << "+" << m_pieces[it->operations[1].piece_index].first_seg_id.segment_index;
+				//out << " " <<  m_pieces[it->operations[0].piece_index].index
+				//     << "," << m_pieces[it->operations[1].piece_index].index << std::endl;
+				//out << " " <<  it->operations[0].seg_id.segment_index
+				//     << "|" << it->operations[1].seg_id.segment_index;
+				out << " " << method_char(it->method)
+					<< ":" << operation_char(it->operations[0].operation)
+					<< "/" << operation_char(it->operations[1].operation);
+				out << " " << it->count_within
+					<< "-" << it->count_on_helper
+					<< "-" << it->count_on_corner
+					<< "-" << it->count_on_offsetted
+					<< "-" << it->count_on_closed
+					//|| it->count_on_opposite > 0
+					//<< it->debug_string
+					;
+				out << color << std::endl;
+
+				out << " " <<  it->operations[0].seg_id.segment_index
+					 << "|" << it->operations[1].seg_id.segment_index;
+				//out << it->operations[0].enriched.travels_to_vertex_index
+				//    << "/" << it->operations[1].enriched.travels_to_vertex_index;
+
+				offsets[p] += 10;
+				int offset = offsets[p];
+
+				mapper.map(it->point, fill, 6);
+				mapper.text(it->point, out.str(), "fill:rgb(0,0,0);font-family='Arial';font-size:9px;", 5, offset);
+
+				offsets[p] += 25;
+			}
+        }
+    }
+
+    template <typename Tag, typename Mapper>
+    inline void map_pieces(Mapper& mapper, bool pieces = true, bool indices = true)
+    {
+        for(typename piece_vector::const_iterator it = boost::begin(m_pieces);
+            it != boost::end(m_pieces);
+            ++it)
+        {
+            Ring corner;
+
+			segment_identifier seg_id = it->first_seg_id;
+
+			buffered_ring<Ring> const& ring = offsetted_rings[seg_id.multi_index];
+
+            std::copy(boost::begin(ring) + seg_id.segment_index, 
+                    boost::begin(ring) + it->last_segment_index, 
+                    std::back_inserter(corner));
+            std::copy(boost::begin(it->helper_segments), 
+                    boost::end(it->helper_segments), 
+                    std::back_inserter(corner));
+
+			{
+				// Corners of onesided buffers are empty.
+				// Mapping this might result (for buffer_line_two_bends_right_d_r) in a
+				// "unknown location(0): fatal error in "test_main_caller( argc, argv )":
+				// class boost::numeric::positive_overflow: bad numeric conversion: positive overflow"
+				// This is only in release-mode of MSVC, only for the pieces (mapping of rings)
+				// Must be somewhere in either transform or ublas
+				// TODO: find out why
+				// Making them unique helps somehow (while it then still has the same coordinates...)
+				geometry::unique(corner);
+			}
+
+            if (pieces)
+            {
+                if (it->type == buffered_segment)
+                {
+                    if(boost::is_same<Tag, ring_tag>::value || boost::is_same<Tag, polygon_tag>::value)
+                    {
+                        mapper.map(corner, "opacity:0.3;fill:rgb(255,128,0);stroke:rgb(0,0,0);stroke-width:1");
+                    }
+                    else if(boost::is_same<Tag, linestring_tag>::value)
+                    {
+                        mapper.map(corner, "opacity:0.3;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1");
+                    }
+                }
+                else
+                {
+                    mapper.map(corner, "opacity:0.3;fill:rgb(255,0,0);stroke:rgb(0,0,0);stroke-width:1");
+                }
+            }
+
+            if (indices)
+            {
+
+                // Put starting piece_index / segment_index in centroid
+                point_type centroid;
+			    if (corner.size() > 3)
+			    {
+				    geometry::centroid(corner, centroid);
+			    }
+			    else
+			    {
+				    centroid = corner.front();
+			    }
+                std::ostringstream out;
+                out << it->index << "/" << it->first_seg_id.segment_index << ".." << it->last_segment_index - 1;
+                mapper.text(centroid, out.str(), "fill:rgb(255,0,0);font-family='Arial';", 5, 5);
+            }
+        }
+    }
+
+
+    template <typename Mapper>
+    inline void map_offsetted_points(Mapper& mapper)
+    {
+        for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator oit = boost::begin(offsetted_rings);
+            oit != boost::end(offsetted_rings);
+            ++oit)
+        {
+			int index = 0;
+			for (typename boost::range_iterator<std::vector<point_type> const>::type pit = boost::begin(*oit); pit != boost::end(*oit); ++pit)
+			{
+				mapper.map(*pit, "fill:rgb(0,0,0);", 2);
+				std::ostringstream out;
+				out << index++;
+				mapper.text(*pit, out.str(), "fill:rgb(0,0,255);font-family='Arial';", -5, -5);
+			}
+		}
+    }
+
+    template <typename Mapper>
+    inline void map_traverse(Mapper& mapper)
+    {
+        for(typename buffered_ring_collection<Ring>::const_iterator it = boost::begin(traversed_rings);
+            it != boost::end(traversed_rings);
+            ++it)
+        {
+            mapper.map(*it, "opacity:0.4;fill:none;stroke:rgb(0,255,0);stroke-width:8");
+        }
+    }
+
+    template <typename Mapper>
+    inline void map_offsetted(Mapper& mapper)
+    {
+        for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings);
+            it != boost::end(offsetted_rings);
+            ++it)
+        {
+            if (it->discarded())
+            {
+                mapper.map(*it, "opacity:0.4;fill:none;stroke:rgb(255,0,0);stroke-width:8");
+            }
+            else
+            {
+                mapper.map(*it, "opacity:0.4;fill:none;stroke:rgb(0,0,255);stroke-width:8");
+            }
+        }
+    }
+};
+
+#endif
+
+
+}} // namespace detail::buffer
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_WM_HPP

Added: trunk/boost/geometry/extensions/algorithms/buffer/side_on_convex_range.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/extensions/algorithms/buffer/side_on_convex_range.hpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -0,0 +1,126 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2012 Barend Gehrels, 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_SIDE_ON_CONVEX_RANGE_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SIDE_ON_CONVEX_RANGE_HPP
+
+#include <boost/range.hpp>
+#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace buffer
+{
+
+template <int D>
+struct collinear_point_on_segment_check
+{
+    typedef double coordinate_type; // TODO just use one - they're all the same (for buffer)
+
+    static inline bool apply_sorted(coordinate_type const& subject, coordinate_type const& c1, coordinate_type const& c2)
+    {
+        return subject >= c1 && subject <= c2;
+    }
+
+    template <typename P0, typename P1, typename P2>
+    static inline bool apply(P0 const& subject, P1 const& p1, P2 const& p2)
+    {
+        coordinate_type const cs = geometry::get<D>(subject);
+        coordinate_type const c1 = geometry::get<D>(p1);
+        coordinate_type const c2 = geometry::get<D>(p2);
+        return c1 > c2 
+            ? apply_sorted(cs, c2, c1)
+            : apply_sorted(cs, c1, c2)
+            ;
+    }
+};
+
+
+// Checks is subject-point is on the segment, provided that it is already determined that it was collinear
+template <typename P0, typename P1, typename P2>
+inline bool collinear_point_on_segment(P0 const& subject, P1 const& p1, P2 const& p2)
+{
+    return collinear_point_on_segment_check<0>::apply(subject, p1, p2)
+        && collinear_point_on_segment_check<1>::apply(subject, p1, p2);
+}
+
+
+template <typename SideStrategy, typename Point, typename Range>
+inline int side_on_convex_range(Point const& subject, Range const& range)
+{
+    bool has_collinear = false;
+
+    typedef typename boost::range_iterator
+        <
+            Range const
+        >::type iterator_type;
+
+    iterator_type it = boost::begin(range);
+    for (iterator_type prev = it++;
+        it != boost::end(range);
+        prev = it++)
+    {
+        int const side = SideStrategy::apply(subject, *prev, *it);
+        switch(side)
+        {
+            case 1 : 
+                return 1;
+            case 0 : 
+                // Check if it is really on the segment.
+                // If not, it is either on the left (because polygon is convex)
+                // or it is still on one of the other segments (if segments are collinear)
+                if (collinear_point_on_segment(subject, *prev, *it))
+                {
+                    return 0;
+                }
+                has_collinear = true;
+                break;
+        }
+    }
+    return has_collinear ? 1 : -1;
+}
+
+template <typename SideStrategy, typename Point, typename Iterator>
+static inline int side_on_convex_range(Point const& subject,
+			Iterator first, Iterator last,
+			/* by value: */ segment_identifier seg_id,
+			segment_identifier& on_segment_seg_id)
+{
+    bool has_collinear = false;
+    Iterator it = first;
+    for (Iterator prev = it++; it != last; prev = it++, seg_id.segment_index++)
+    {
+        int side = SideStrategy::apply(subject, *prev, *it);
+        switch(side)
+        {
+            case 1 : 
+                return 1;
+            case 0 : 
+                // Check if it is REALLY on the segment.
+                // If not, it is either on the left (because polygon is convex)
+                // or it is still on one of the other segments (if segments are collinear)
+                if (collinear_point_on_segment(subject, *prev, *it))
+                {
+					on_segment_seg_id = seg_id;
+                    return 0;
+                }
+                has_collinear = true;
+                break;
+        }
+    }
+    return has_collinear ? 1 : -1;
+}
+
+}} // namespace detail::buffer
+#endif // DOXYGEN_NO_DETAIL
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_SIDE_ON_CONVEX_RANGE_HPP

Modified: trunk/boost/geometry/extensions/strategies/buffer.hpp
==============================================================================
--- trunk/boost/geometry/extensions/strategies/buffer.hpp	(original)
+++ trunk/boost/geometry/extensions/strategies/buffer.hpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -270,6 +270,11 @@
     {
         return side == buffer_side_left ? m_left : m_right;
     }
+    
+    inline int factor() const
+    {
+        return m_left < 0 ? -1 : 1;
+    }
 
 private :
     CoordinateType m_left;

Modified: trunk/libs/geometry/test_extensions/algorithms/buffer/linestring_buffer.cpp
==============================================================================
--- trunk/libs/geometry/test_extensions/algorithms/buffer/linestring_buffer.cpp	(original)
+++ trunk/libs/geometry/test_extensions/algorithms/buffer/linestring_buffer.cpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -31,6 +31,9 @@
 static std::string const overlapping = "LINESTRING(0 0,4 5,7 4,10 6, 10 2,2 2)";
 static std::string const curve = "LINESTRING(2 7,3 5,5 4,7 5,8 7)";
 
+static std::string const for_collinear = "LINESTRING(2 0,0 0,0 4,6 4,6 0,4 0)";
+static std::string const for_collinear2 = "LINESTRING(2 1,2 0,0 0,0 4,6 4,6 0,4 0,4 1)";
+
 static std::string const chained2 = "LINESTRING(0 0,1 1,2 2)";
 static std::string const chained3 = "LINESTRING(0 0,1 1,2 2,3 3)";
 static std::string const chained4 = "LINESTRING(0 0,1 1,2 2,3 3,4 4)";
@@ -46,32 +49,55 @@
     typedef bg::model::linestring<P> linestring;
     typedef bg::model::polygon<P> polygon;
 
-    double factor = +1.0; // does NOT yet work for negative buffer
-    double right = factor * 1.0;
-
-    test_one<linestring, buf::join_round, polygon>("simplex", simplex, 'r', 19.2093727122985, 1.5, right);
-    test_one<linestring, buf::join_miter, polygon>("simplex", simplex, 'm', 19.2093727122985, 1.5, right);
-
-    test_one<linestring, buf::join_round, polygon>("straight", straight, 'r', 19.2093727122985, 1.5, right);
-    test_one<linestring, buf::join_miter, polygon>("straight", straight, 'm', 19.2093727122985, 1.5, right);
+    test_one<linestring, buf::join_round, polygon>("simplex", simplex, 'r', 19.209, 1.5, 1.5);
+    test_one<linestring, buf::join_miter, polygon>("simplex", simplex, 'm', 19.209, 1.5, 1.5);
 
-    test_one<linestring, buf::join_round, polygon>("one_bend", one_bend, 'r', 28.4879539312069, 1.5, right);
-    test_one<linestring, buf::join_miter, polygon>("one_bend", one_bend, 'm', 28.6962056928037, 1.5, right);
+    test_one<linestring, buf::join_miter, polygon>("simplex_asym_neg", simplex, 'm', 3.202, +1.5, -1.0);
+    test_one<linestring, buf::join_miter, polygon>("simplex_asym_pos", simplex, 'm', 3.202, -1.5, +1.0);
 
-    test_one<linestring, buf::join_round, polygon>("two_bends", two_bends, 'r', 39.2220036534424, 1.5, right);
-    test_one<linestring, buf::join_miter, polygon>("two_bends", two_bends, 'm', 39.5128595191957, 1.5, right);
+    //test_one<linestring, buf::join_round, polygon>("straight", straight, 'r', 19.2093727122985, 1.5, 1.5);
+    //test_one<linestring, buf::join_miter, polygon>("straight", straight, 'm', 19.2093727122985, 1.5, 1.5);
 
-    test_one<linestring, buf::join_round, polygon>("overlapping", overlapping, 'r', 65.646005724872, 1.5, right);
-    test_one<linestring, buf::join_miter, polygon>("overlapping", overlapping, 'm', 68.1395194809293, 1.5, right);
+    test_one<linestring, buf::join_round, polygon>("one_bend", one_bend, 'r', 28.488, 1.5, 1.5);
+    test_one<linestring, buf::join_miter, polygon>("one_bend", one_bend, 'm', 28.696, 1.5, 1.5);
+
+    test_one<linestring, buf::join_round, polygon>("two_bends", two_bends, 'r', 39.222, 1.5, 1.5);
+    test_one<linestring, buf::join_miter, polygon>("two_bends", two_bends, 'm', 39.513, 1.5, 1.5);
+    test_one<linestring, buf::join_round, polygon>("two_bends_left", two_bends, 'r', 20.028, 1.5, 0.0);
+    test_one<linestring, buf::join_miter, polygon>("two_bends_left", two_bends, 'm', 20.225, 1.5, 0.0);
+    test_one<linestring, buf::join_round, polygon>("two_bends_right", two_bends, 'r', 19.211, 0.0, 1.5);
+    test_one<linestring, buf::join_miter, polygon>("two_bends_right", two_bends, 'm', 19.288, 0.0, 1.5);
+
+
+	// Next (and all similar cases) which a offsetted-one-sided buffer has to be fixed.
+    //test_one<linestring, buf::join_miter, polygon>("two_bends_neg", two_bends, 'm', 99, +1.5, -1.0);
+    //test_one<linestring, buf::join_miter, polygon>("two_bends_pos", two_bends, 'm', 99, -1.5, +1.0);
+    //test_one<linestring, buf::join_round, polygon>("two_bends_neg", two_bends, 'r', 99, +1.5, -1.0);
+    //test_one<linestring, buf::join_round, polygon>("two_bends_pos", two_bends, 'r', 99, -1.5, +1.0);
+
+    test_one<linestring, buf::join_round, polygon>("overlapping150", overlapping, 'r', 65.646, 1.5, 1.5);
+    test_one<linestring, buf::join_miter, polygon>("overlapping150", overlapping, 'm', 68.140, 1.5, 1.5);
+	// Different cases with intersection points on flat and (left/right from line itself)
+    test_one<linestring, buf::join_round, polygon>("overlapping_asym_150_010", overlapping, 'r', 48.308, 1.5, 0.25);
+    test_one<linestring, buf::join_miter, polygon>("overlapping_asym_150_010", overlapping, 'm', 50.770, 1.5, 0.25);
+    test_one<linestring, buf::join_round, polygon>("overlapping_asym_150_075", overlapping, 'r', 58.506, 1.5, 0.75);
+    test_one<linestring, buf::join_miter, polygon>("overlapping_asym_150_075", overlapping, 'm', 60.985, 1.5, 0.75);
+    test_one<linestring, buf::join_round, polygon>("overlapping_asym_150_100", overlapping, 'r', 62.514, 1.5, 1.0);
+    test_one<linestring, buf::join_miter, polygon>("overlapping_asym_150_100", overlapping, 'm', 64.984, 1.5, 1.0);
+
+    test_one<linestring, buf::join_round, polygon>("for_collinear", for_collinear, 'r', 68.561, 2.0, 2.0);
+    test_one<linestring, buf::join_miter, polygon>("for_collinear", for_collinear, 'm', 72, 2.0, 2.0);
+    test_one<linestring, buf::join_round, polygon>("for_collinear2", for_collinear2, 'r', 74.387, 2.0, 2.0);
+    test_one<linestring, buf::join_miter, polygon>("for_collinear2", for_collinear2, 'm', 78.0, 2.0, 2.0);
+
+    //test_one<linestring, buf::join_round, polygon>("curve", curve, 'r', 99, 5.0, 3.0);
+    //test_one<linestring, buf::join_miter, polygon>("curve", curve, 'm', 99, 5.0, 3.0);
+
+    //test_one<linestring, buf::join_round, polygon>("chained2", chained2, 'r', 99, 2.5, 1.5);
+    //test_one<linestring, buf::join_round, polygon>("chained3", chained3, 'r', 99, 2.5, 1.5);
+    //test_one<linestring, buf::join_round, polygon>("chained4", chained4, 'r', 99, 2.5, 1.5);
 
-    test_one<linestring, buf::join_round, polygon>("curve", curve, 'r', 65.646005724872, 5.0, factor * 3.0);
-    test_one<linestring, buf::join_miter, polygon>("curve", curve, 'm', 68.1395194809293, 5.0, factor * 3.0);
-
-    test_one<linestring, buf::join_round, polygon>("chained2", chained2, 'r', 65.646005724872, 2.5, factor * 1.5);
-    test_one<linestring, buf::join_round, polygon>("chained3", chained3, 'r', 65.646005724872, 2.5, factor * 1.5);
-    test_one<linestring, buf::join_round, polygon>("chained4", chained4, 'r', 65.646005724872, 2.5, factor * 1.5);
-
-    test_one<linestring, buf::join_round, polygon>("reallife1", reallife1, 'r', 65.646005724872, 16.5, factor * 6.5);
+    //test_one<linestring, buf::join_round, polygon>("reallife1", reallife1, 'r', 99, 16.5, 6.5);
 }
 
 
@@ -86,6 +112,5 @@
     test_all<bg::model::point<double, 2, bg::cs::cartesian> >();
     //test_all<bg::model::point<tt, 2, bg::cs::cartesian> >();
 
-
     return 0;
 }

Modified: trunk/libs/geometry/test_extensions/algorithms/buffer/polygon_buffer.cpp
==============================================================================
--- trunk/libs/geometry/test_extensions/algorithms/buffer/polygon_buffer.cpp	(original)
+++ trunk/libs/geometry/test_extensions/algorithms/buffer/polygon_buffer.cpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -25,6 +25,17 @@
     = "POLYGON ((0 0,0 4,1 4,1 1,3 1,3 0,0 0))";
 static std::string const indentation
     = "POLYGON ((0 0,0 5,4 5,4 4,3 3,2 4,2 1,3 2,4 1,4 0,0 0))";
+static std::string const funnelgate
+    = "POLYGON((0 0,0 7,7 7,7 0,5 0,5 1,6 6,1 6,2 1,2 0,0 0))";
+static std::string const gammagate
+    = "POLYGON((0 0,0 6,9 6,9 0,4 0,4 2,7 2,7 4,2 4,2 0,0 0))";
+static std::string const fork_a
+    = "POLYGON((0 0,0 6,9 6,9 0,4 0,4 2,7 2,7 4,6 4,6 5,5 5,5 4,4 4,4 5,3 5,3 4,2 4,2 0,0 0))";
+static std::string const fork_b
+    = "POLYGON((0 0,0 8,14 8,14 0,4 0,4 2,13 2,13 4,12 4,12 7,9 7,9 4,7 4,7 7,4 7,4 4,2 4,2 0,0 0))";
+static std::string const fork_c
+    = "POLYGON((0 0,0 9,12 9,12 0,4 0,4 4,6 4,6 2,8 2,8 4,10 4,10 7,6 7,6 6,2 6,2 0,0 0))";
+
 static std::string const arrow
     = "POLYGON ((1 0,1 5,0.5 4.5,2 10,3.5 4.5,3 5,3 0,1 0))";
 static std::string const tipped_aitch
@@ -54,8 +65,6 @@
 
     typedef bg::model::polygon<P> polygon_type;
 
-test_one<polygon_type, buf::join_round, polygon_type>("saw", saw, 'r', -1, 1.0);
-
     test_one<polygon_type, buf::join_miter, polygon_type>("L", letter_L, 'm', 14.0, 0.5);
     test_one<polygon_type, buf::join_round, polygon_type>("L", letter_L, 'r', 13.7314, 0.5);
     test_one<polygon_type, buf::join_miter, polygon_type>("simplex", simplex, 'm', 52.8733, 1.5);
@@ -80,11 +89,12 @@
     test_one<polygon_type, buf::join_miter, polygon_type>("indentation12", indentation, 'm', 46.3541, 1.2);
     test_one<polygon_type, buf::join_round, polygon_type>("indentation12", indentation, 'r', 45.0537, 1.2);
 
-    test_one<polygon_type, buf::join_miter, polygon_type>("indentation4_neg", indentation, 'm', 6.99098413022335, -0.4);
+	// TODO: fix, the buffered pieces are currently counterclockwise, that should be reversed
+    //test_one<polygon_type, buf::join_miter, polygon_type>("indentation4_neg", indentation, 'm', 6.99098413022335, -0.4);
     //test_one<polygon_type, buf::join_round, polygon_type>("indentation4_neg", indentation, 'r', 7.25523322189147, -0.4);
-    test_one<polygon_type, buf::join_miter, polygon_type>("indentation8_neg", indentation, 'm', 1.36941992048731, -0.8);
+    //test_one<polygon_type, buf::join_miter, polygon_type>("indentation8_neg", indentation, 'm', 1.36941992048731, -0.8);
     //test_one<polygon_type, buf::join_round, polygon_type>("indentation8_neg", indentation, 'r', 1.37375487490664, -0.8);
-    test_one<polygon_type, buf::join_miter, polygon_type>("indentation12_neg", indentation, 'm', 0, -1.2);
+    //test_one<polygon_type, buf::join_miter, polygon_type>("indentation12_neg", indentation, 'm', 0, -1.2);
     //test_one<polygon_type, buf::join_round, polygon_type>("indentation12_neg", indentation, 'r', 0, -1.2);
 
     test_one<polygon_type, buf::join_miter, polygon_type>("donut_simplex6", donut_simplex, 'm', 53.648, 0.6);
@@ -121,11 +131,19 @@
     test_one<polygon_type, buf::join_miter, polygon_type>("snake6", snake, 'm', 75.44, 0.6);
     test_one<polygon_type, buf::join_miter, polygon_type>("snake16", snake, 'm', 114.24, 1.6);
 
+	test_one<polygon_type, buf::join_miter, polygon_type>("funnelgate2", funnelgate, 'm', 120.982, 2);
+    test_one<polygon_type, buf::join_miter, polygon_type>("funnelgate3", funnelgate, 'm', 13*13, 3);
+    test_one<polygon_type, buf::join_miter, polygon_type>("funnelgate4", funnelgate, 'm', 15*15, 4);
+    test_one<polygon_type, buf::join_miter, polygon_type>("gammagate1", gammagate, 'm', 88, 1);
+    test_one<polygon_type, buf::join_miter, polygon_type>("fork_a1", fork_a, 'm', 88, 1);
+    test_one<polygon_type, buf::join_miter, polygon_type>("fork_b1", fork_b, 'm', 154, 1);
+    test_one<polygon_type, buf::join_miter, polygon_type>("fork_c1", fork_c, 'm', 152, 1);
+
+    test_one<polygon_type, buf::join_miter, polygon_type>("gammagate2", gammagate, 'm', 130, 2);
+
     test_one<polygon_type, buf::join_miter, polygon_type>("flower1", flower, 'm', 67.614, 0.1);
     test_one<polygon_type, buf::join_miter, polygon_type>("flower20", flower, 'm', 74.894, 0.20);
     test_one<polygon_type, buf::join_miter, polygon_type>("flower25", flower, 'm', 78.226, 0.25);
-// TODO: fix the flowers-with-miter
-goto skip_flower_miter;
     test_one<polygon_type, buf::join_miter, polygon_type>("flower30", flower, 'm', 81.492494146177947, 0.30);
     test_one<polygon_type, buf::join_miter, polygon_type>("flower35", flower, 'm', 84.694183819917185, 0.35);
     test_one<polygon_type, buf::join_miter, polygon_type>("flower40", flower, 'm', 87.8306529577, 0.40);
@@ -134,7 +152,6 @@
     test_one<polygon_type, buf::join_miter, polygon_type>("flower55", flower, 'm', 96.848737155342079, 0.55);
     test_one<polygon_type, buf::join_miter, polygon_type>("flower60", flower, 'm', 99.724324149315279, 0.60);
 
-skip_flower_miter:
     test_one<polygon_type, buf::join_round, polygon_type>("flower10", flower, 'r', 67.486, 0.10);
     test_one<polygon_type, buf::join_round, polygon_type>("flower20", flower, 'r', 74.702, 0.20);
     test_one<polygon_type, buf::join_round, polygon_type>("flower25", flower, 'r', 78.071, 0.25);

Modified: trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp
==============================================================================
--- trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp	(original)
+++ trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp	2012-03-03 06:24:46 EST (Sat, 03 Mar 2012)
@@ -10,7 +10,7 @@
 #ifndef BOOST_GEOMETRY_TEST_BUFFER_HPP
 #define BOOST_GEOMETRY_TEST_BUFFER_HPP
 
-#define BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+//#define BOOST_GEOMETRY_DEBUG_WITH_MAPPER
 #define TEST_WITH_SVG
 
 #include <fstream>
@@ -96,7 +96,7 @@
         << string_from_type<coordinate_type>::name()
         << "_" << join;
 
-    //std::cout << complete.str() << std::endl;
+    std::cout << complete.str() << std::endl;
 
     std::ostringstream filename;
     filename << "buffer_" << complete.str() << ".svg";
@@ -108,13 +108,13 @@
     {
         bg::model::box<point_type> box;
         bg::envelope(geometry, box);
-        double d = distance_left;
-        if (distance_right > 0)
-        {
-            d += distance_right;
-        }
+        double d = std::abs(distance_left);
+		if (distance_right > -998)
+		{
+			d += std::abs(distance_right);
+		}
 
-        bg::buffer(box, box, std::abs(d) * 1.1);
+        bg::buffer(box, box, d * 1.1);
         mapper.add(box);
     }
 
@@ -127,7 +127,7 @@
     join_strategy_type join_strategy;
 
     typedef bg::strategy::buffer::distance_assymetric<coordinate_type> distance_strategy_type;
-    distance_strategy_type distance_strategy(distance_left, distance_left / 2.0); // TODO: distance_right
+    distance_strategy_type distance_strategy(distance_left, distance_right);
 
     std::vector<GeometryOut> buffered;
 
@@ -154,7 +154,7 @@
     //}
 
 
-    if (distance_left > 0 && expected_area > -0.1)
+    if (expected_area > -0.1)
     {
         BOOST_CHECK_MESSAGE
             (
@@ -181,14 +181,13 @@
         }
     }
 
-
-
     // Map input geometry in green
-    mapper.map(geometry, "opacity:0.5;fill:rgb(0,128,0);stroke:rgb(0,128,0);stroke-width:1");
+    mapper.map(geometry, "opacity:0.5;fill:rgb(0,128,0);stroke:rgb(0,128,0);stroke-width:10");
 
     BOOST_FOREACH(GeometryOut const& polygon, buffered)
     {
         mapper.map(polygon, "opacity:0.4;fill:rgb(255,255,128);stroke:rgb(0,0,0);stroke-width:3");
+        //mapper.map(polygon, "opacity:0.2;fill:none;stroke:rgb(255,0,0);stroke-width:3");
         post_map(polygon, mapper);
     }
 }