[Boost-commit] svn:boost r69510 - in trunk/boost/geometry: algorithms/detail algorithms/detail/overlay multi multi/algorithms multi/algorithms/detail/overlay strategies/agnostic

Subject: [Boost-commit] svn:boost r69510 - in trunk/boost/geometry: algorithms/detail algorithms/detail/overlay multi multi/algorithms multi/algorithms/detail/overlay strategies/agnostic
From: barend.gehrels_at_[hidden]
Date: 2011-03-03 06:22:06

Author: barendgehrels
Date: 2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
New Revision: 69510
URL: http://svn.boost.org/trac/boost/changeset/69510

Log:
Refactored assemble.hpp, now three parts: select_rings, assign_parents, add_rings
Rewritten ring_properties 
Obsoleted add_to_containment.hpp, assemble.hpp
Added:
   trunk/boost/geometry/algorithms/detail/overlay/add_rings.hpp   (contents, props changed)
   trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp   (contents, props changed)
   trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp   (contents, props changed)
   trunk/boost/geometry/algorithms/detail/overlay/within_util.hpp   (contents, props changed)
   trunk/boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/add_to_containment.hpp       |   119 ------                                  
   trunk/boost/geometry/algorithms/detail/overlay/assemble.hpp                 |   677 --------------------------------------- 
   trunk/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp       |     1                                         
   trunk/boost/geometry/algorithms/detail/overlay/get_ring.hpp                 |    21                                         
   trunk/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp        |     1                                         
   trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp                  |    85 ++++                                    
   trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp          |   259 ++-------------                         
   trunk/boost/geometry/algorithms/detail/ring_identifier.hpp                  |     8                                         
   trunk/boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp |    63 ---                                     
   trunk/boost/geometry/multi/algorithms/difference.hpp                        |     3                                         
   trunk/boost/geometry/multi/algorithms/intersection.hpp                      |     2                                         
   trunk/boost/geometry/multi/algorithms/union.hpp                             |     3                                         
   trunk/boost/geometry/multi/multi.hpp                                        |     1                                         
   trunk/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp          |     1                                         
   14 files changed, 141 insertions(+), 1103 deletions(-)

Added: trunk/boost/geometry/algorithms/detail/overlay/add_rings.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/overlay/add_rings.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -0,0 +1,112 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2011, 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_OVERLAY_ADD_RINGS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP
+
+#include <boost/geometry/algorithms/detail/overlay/convert_ring.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+template 
+<
+    typename GeometryOut, 
+    typename Geometry1,
+    typename Geometry2,
+    typename RingCollection
+>
+inline void convert_and_add(GeometryOut& result,
+            Geometry1 const& geometry1, Geometry2 const& geometry2,
+            RingCollection const& collection, 
+            ring_identifier id, 
+            bool reversed, bool append)
+{
+    typedef typename geometry::tag<Geometry1>::type tag1;
+    typedef typename geometry::tag<Geometry2>::type tag2;
+    typedef typename geometry::tag<GeometryOut>::type tag_out;
+
+    if (id.source_index == 0)
+    {
+        convert_ring<tag_out>::apply(result,
+                    get_ring<tag1>::apply(id, geometry1),
+                    append, reversed);
+    }
+    else if (id.source_index == 1)
+    {
+        convert_ring<tag_out>::apply(result,
+                    get_ring<tag2>::apply(id, geometry2),
+                    append, reversed);
+    }
+    else if (id.source_index == 2)
+    {
+        convert_ring<tag_out>::apply(result,
+                    get_ring<void>::apply(id, collection),
+                    append, reversed);
+    }
+}
+
+template
+<
+    typename GeometryOut,
+    typename SelectionMap,
+    typename Geometry1,
+    typename Geometry2,
+    typename RingCollection,
+    typename OutputIterator
+>
+inline OutputIterator add_rings(SelectionMap const& map,
+            Geometry1 const& geometry1, Geometry2 const& geometry2,
+            RingCollection const& collection,
+            OutputIterator out)
+{
+    typedef typename SelectionMap::const_iterator iterator;
+
+    for (iterator it = boost::begin(map);
+        it != boost::end(map);
+        ++it)
+    {
+        if (it->second.parent.source_index == -1)
+        {
+            GeometryOut result;
+            convert_and_add(result, geometry1, geometry2, collection,
+                    it->first, it->second.reversed, false);
+
+            // Add children
+            for (typename std::vector<ring_identifier>::const_iterator child_it
+                        = it->second.children.begin();
+                child_it != it->second.children.end();
+                ++child_it)
+            {
+                iterator mit = map.find(*child_it);
+                if (mit != map.end())
+                {
+                    convert_and_add(result, geometry1, geometry2, collection,
+                            *child_it, mit->second.reversed, true);
+                }
+            }
+            *out++ = result;
+        }
+    }
+    return out;
+}
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP

Modified: trunk/boost/geometry/algorithms/detail/overlay/add_to_containment.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/add_to_containment.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/add_to_containment.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -1,118 +1 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-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_OVERLAY_ADD_TO_CONTAINMENT_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_TO_CONTAINMENT_HPP
-
-
-#include <boost/mpl/assert.hpp>
-#include <boost/range.hpp>
-#include <boost/typeof/typeof.hpp>
-
-
-#include <boost/geometry/core/tags.hpp>
-#include <boost/geometry/core/exterior_ring.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
-#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
-
-#include <boost/geometry/algorithms/convert.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay
-{
-
-
-template <typename Tag, typename Geometry>
-struct add_to_containment
-{
-    BOOST_MPL_ASSERT_MSG
-        (
-            false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
-            , (types<Geometry>)
-        );
-};
-
-template <typename Ring>
-struct add_to_containment<ring_tag, Ring>
-{
-    template <typename ContainmentContainer, typename Map>
-    static inline void apply(ContainmentContainer& container,
-            ring_identifier const& id, Ring const& ring, Map const& map,
-            bool dissolve)
-    {
-        typedef typename range_value<ContainmentContainer>::type prop;
-        bool found = map.find(id) != map.end();
-        if (! dissolve || ! found)
-        {
-            // For dissolve, do not add intersected rings
-            container.push_back(prop(id, ring, found));
-        }
-    }
-};
-
-template <typename Box>
-struct add_to_containment<box_tag, Box>
-{
-    template <typename ContainmentContainer, typename Map>
-    static inline void apply(ContainmentContainer& container,
-            ring_identifier const& id, Box const& box, Map const& map,
-            bool dissolve)
-    {
-        typedef typename range_value<ContainmentContainer>::type prop;
-        bool found = map.find(id) != map.end();
-        if (! dissolve || ! found)
-        {
-            container.push_back(prop(id, box, found));
-        }
-    }
-};
-
-
-template <typename Polygon>
-struct add_to_containment<polygon_tag, Polygon>
-{
-    template <typename ContainmentContainer, typename Map>
-    static inline void apply(ContainmentContainer& container,
-            ring_identifier const& id, Polygon const& polygon, Map const& map,
-            bool dissolve)
-    {
-        // Add exterior ring and interior rings
-        ring_identifier copy = id;
-
-        typedef add_to_containment
-            <
-                ring_tag,
-                typename ring_type<Polygon>::type
-            > policy;
-
-        policy::apply(container, copy, exterior_ring(polygon), map, dissolve);
-        copy.ring_index = 0;
-
-        typename interior_return_type<Polygon const>::type rings
-                    = interior_rings(polygon);
-        for (BOOST_AUTO(it, boost::begin(rings)); it != boost::end(rings);
-            ++it, ++copy.ring_index)
-        {
-            policy::apply(container, copy, *it, map, dissolve);
-        }
-    }
-};
-
-
-}} // namespace detail::overlay
-#endif // DOXYGEN_NO_DETAIL
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_TO_CONTAINMENT_HPP
+//obsolete
\ No newline at end of file

Modified: trunk/boost/geometry/algorithms/detail/overlay/assemble.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/assemble.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/assemble.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -1,676 +1 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-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_OVERLAY_ASSEMBLE_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
-
-
-#include <map>
-#include <vector>
-
-#include <boost/range.hpp>
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-#  define BOOST_GEOMETRY_DEBUG_IDENTIFIER
-#  include <boost/geometry/util/write_dsv.hpp>
-#endif
-
-
-#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
-#include <boost/geometry/algorithms/detail/overlay/convert_ring.hpp>
-#include <boost/geometry/algorithms/detail/overlay/add_to_containment.hpp>
-#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
-#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
-#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
-//#include <boost/geometry/strategies/intersection_result.hpp>
-
-
-#include <boost/geometry/algorithms/combine.hpp>
-#include <boost/geometry/algorithms/envelope.hpp>
-#include <boost/geometry/algorithms/within.hpp>
-
-#include <boost/geometry/util/math.hpp>
-
-#include <boost/geometry/strategies/intersection.hpp>
-#include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp>
-
-
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay
-{
-
-
-template<typename Tag, typename Point, typename Geometry>
-struct within_code
-{};
-
-template<typename Point, typename Box>
-struct within_code<box_tag, Point, Box>
-{
-    static inline int apply(Point const& point, Box const& box)
-    {
-        // 1. Check outside
-        if (get<0>(point) < get<min_corner, 0>(box)
-            || get<0>(point) > get<max_corner, 0>(box)
-            || get<1>(point) < get<min_corner, 1>(box)
-            || get<1>(point) > get<max_corner, 1>(box))
-        {
-            return -1;
-        }
-        // 2. Check border
-        if (geometry::math::equals(get<0>(point), get<min_corner, 0>(box))
-            || geometry::math::equals(get<0>(point), get<max_corner, 0>(box))
-            || geometry::math::equals(get<1>(point), get<min_corner, 1>(box))
-            || geometry::math::equals(get<1>(point), get<max_corner, 1>(box)))
-        {
-            return 0;
-        }
-        return 1;
-    }
-};
-template<typename Point, typename Ring>
-struct within_code<ring_tag, Point, Ring>
-{
-    static inline int apply(Point const& point, Ring const& ring)
-    {
-        // Same as point_in_ring but here ALWAYS with winding.
-        typedef strategy::within::winding<Point> strategy_type;
-
-        return detail::within::point_in_ring
-            <
-                Point,
-                Ring,
-                order_as_direction<geometry::point_order<Ring>::value>::value,
-                geometry::closure<Ring>::value,
-                strategy_type
-            >::apply(point, ring, strategy_type());
-    }
-};
-
-
-template<typename Point, typename Geometry>
-inline int point_in_ring(Point const& point, Geometry const& geometry)
-{
-    return within_code<typename geometry::tag<Geometry>::type, Point, Geometry>
-        ::apply(point, geometry);
-}
-
-template<typename Point, typename Geometry>
-inline bool within_or_touch(Point const& point, Geometry const& geometry)
-{
-    return within_code<typename geometry::tag<Geometry>::type, Point, Geometry>
-        ::apply(point, geometry) >= 0;
-}
-
-
-// Skip for assemble process
-template <typename TurnInfo>
-inline bool skip(TurnInfo const& turn_info)
-{
-    return (turn_info.discarded || turn_info.both(operation_union))
-        && ! turn_info.any_blocked()
-        && ! turn_info.both(operation_intersection)
-        ;
-}
-
-
-
-template <typename TurnPoints, typename Map>
-inline void map_turns(Map& map, TurnPoints const& turn_points)
-{
-    typedef typename boost::range_value<TurnPoints>::type turn_point_type;
-    typedef typename turn_point_type::container_type container_type;
-
-    int index = 0;
-    for (typename boost::range_iterator<TurnPoints const>::type
-            it = boost::begin(turn_points);
-         it != boost::end(turn_points);
-         ++it, ++index)
-    {
-        if (! skip(*it))
-        {
-            int op_index = 0;
-            for (typename boost::range_iterator<container_type const>::type
-                    op_it = boost::begin(it->operations);
-                op_it != boost::end(it->operations);
-                ++op_it, ++op_index)
-            {
-                ring_identifier ring_id
-                    (
-                        op_it->seg_id.source_index,
-                        op_it->seg_id.multi_index,
-                        op_it->seg_id.ring_index
-                    );
-                map[ring_id]++;
-            }
-        }
-    }
-}
-
-
-template
-<
-    typename Container,
-    typename Geometry1,
-    typename Geometry2,
-    typename RingCollection,
-    typename Box
->
-struct enrich_containment
-{
-
-    typedef typename boost::range_value<Container>::type item_type;
-    typedef typename geometry::tag<Geometry1>::type tag1;
-    typedef typename geometry::tag<Geometry2>::type tag2;
-    typedef void tag3; // For the ring-container
-
-
-    static inline void assign(item_type& larger, item_type& smaller, overlay_type direction)
-    {
-        typedef typename geometry::coordinate_type
-            <
-                Geometry1
-            >::type coordinate_type;
-
-        if (larger.signum != 0 && smaller.signum != 0)
-        {
-            if (larger.signum == 1)
-            {
-                smaller.push(larger, direction);
-            }
-            else if (larger.signum == -1)
-            {
-                smaller.pop(/*from*/larger);
-            }
-        }
-    }
-
-
-    // Creates a selection of pointers within the specified box
-    template <typename Collection>
-    static inline void select_by_box(Collection& selection,
-            Collection const& collection,
-            Box const& box)
-    {
-        for (typename boost::range_iterator<Collection const>::type
-                it = boost::begin(collection);
-                it != boost::end(collection);
-                ++it)
-        {
-            if (! geometry::detail::disjoint::disjoint_box_box(box, (*it)->box))
-            {
-                selection.push_back(*it);
-            }
-        }
-    }
-
-    static inline bool contains(item_type const& item1, item_type const& item2,
-            Geometry1 const& geometry1, Geometry2 const& geometry2,
-            RingCollection const& collection)
-    {
-        int code = -1;
-        if (item1.ring_id.source_index == 0)
-        {
-            code = point_in_ring(item2.point,
-                get_ring<tag1>::apply(item1.ring_id, geometry1));
-        }
-        else if (item1.ring_id.source_index == 1)
-        {
-            code = point_in_ring(item2.point,
-                get_ring<tag2>::apply(item1.ring_id, geometry2));
-        }
-        else if (item1.ring_id.source_index == 2)
-        {
-            code = point_in_ring(item2.point,
-                get_ring<tag3>::apply(item1.ring_id, collection));
-        }
-        else
-        {
-            return false;
-        }
-        return code == 0 ? item1.area < 0 : code == 1;
-    }
-
-    template <typename Selection, typename Map>
-    static inline void enrich(Selection& selection, Map& map,
-            Geometry1 const& geometry1, Geometry2 const& geometry2,
-            RingCollection const& collection,
-            overlay_type direction)
-    {
-        typedef typename boost::range_iterator<Selection>::type iterator;
-
-        for (iterator it1 = boost::begin(selection);
-            it1 != boost::end(selection);
-            ++it1)
-        {
-//std::cout << ".";
-            item_type& item1 = **it1;
-            iterator it2 = it1;
-            for (it2++; it2 != boost::end(selection); ++it2)
-            {
-                std::pair<item_type*, item_type*> p
-                            = std::make_pair(*it1, *it2);
-                bool processed = map[p];
-                if (! processed)
-                {
-                    map[p] = true;
-
-                    item_type& item2 = **it2;
-                    if (geometry::within(item2.point, item1.box)
-                        && abs(item2.area) < abs(item1.area)
-                        && contains(item1, item2, geometry1, geometry2,
-                                    collection)
-                        )
-                    {
-                        assign(item1, item2, direction);
-                    }
-                }
-            }
-        }
-    }
-
-    /***
-    template <int Dimension, typename Selection, typename Map>
-    static inline void divide_and_conquer(Selection& selection, Map& map,
-            Geometry1 const& geometry1, Geometry2 const& geometry2,
-            RingCollection const& collection,
-            int direction, Box const& box,
-            std::size_t iteration = 0, std::size_t previous_count = 0)
-    {
-        std::size_t n = boost::size(selection);
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "spatial divide n="
-<< n
-<< " previous=" << previous_count
-<< " iteration=" << iteration
-<< " box: " << geometry::dsv(box) << std::endl;
-#endif
-
-        if (iteration > 3)
-        {
-            enrich(selection, map, geometry1, geometry2, collection, direction);
-            return;
-        }
-
-        // Divide the complete box in two (alternating) halves
-        Box lower = box, upper = box;
-        typedef typename geometry::coordinate_type<Box>::type coordinate_type;
-        coordinate_type two = 2.0;
-        coordinate_type mid
-            = (geometry::get<min_corner, Dimension>(box)
-                + geometry::get<max_corner, Dimension>(box)) / two;
-
-        geometry::set<max_corner, Dimension>(lower, mid);
-        geometry::set<min_corner, Dimension>(upper, mid);
-
-        // select
-        std::vector<item_type*> lower_sel, upper_sel;
-        select_by_box(lower_sel, selection, lower);
-        select_by_box(upper_sel, selection, upper);
-
-        divide_and_conquer<1 - Dimension>(lower_sel, map, geometry1, geometry2,
-                    collection, direction, lower, iteration + 1, n);
-        divide_and_conquer<1 - Dimension>(upper_sel, map, geometry1, geometry2,
-                    collection, direction, upper, iteration + 1, n);
-    }
-    ***/
-
-    static inline void enrich(Container& container,
-            Geometry1 const& geometry1, Geometry2 const& geometry2,
-            RingCollection const& collection,
-            overlay_type direction)
-    {
-        typedef typename boost::range_iterator<Container>::type iterator;
-
-        int n = 0;
-
-        for (iterator it1 = boost::begin(container);
-            it1 != boost::end(container);
-            ++it1)
-        {
-            item_type& item1 = *it1;
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << item1.ring_id << " area: " << item1.area << std::endl;
-#endif
-            iterator it2 = it1;
-            for (it2++; it2 != boost::end(container); ++it2)
-            {
-                item_type& item2 = *it2;
-                if (within_or_touch(item2.point, item1.box)
-                    && geometry::math::abs(item2.area)
-                            < geometry::math::abs(item1.area)
-                    && contains(item1, item2, geometry1, geometry2, collection)
-                    )
-                {
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << " -> contains " << item2.ring_id;
-#endif
-                    n++;
-                    assign(item1, item2, direction);
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << std::endl;
-#endif
-                }
-            }
-        }
-        //std::cout << "Enriched: "  << n << std::endl;
-    }
-
-
-
-    static inline void apply(Container& container,
-            Geometry1 const& geometry1, Geometry2 const& geometry2,
-            RingCollection const& collection,
-            overlay_type direction, Box const& )
-    {
-        if (boost::size(container) == 0)
-        {
-            return;
-        }
-        enrich(container, geometry1, geometry2, collection, direction);
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-        for (typename boost::range_iterator<Container const>::type
-                it = boost::begin(container);
-            it != boost::end(container);
-            ++it)
-        {
-            std::cout << *it << std::endl;
-        }
-#endif
-
-        /***
-        return;
-
-        // Method using divide and conquer (does NOT work corretly!)
-
-        std::vector<item_type*> selection;
-        selection.reserve(boost::size(container));
-        for (typename boost::range_iterator<Container>::type
-                it = boost::begin(container);
-            it != boost::end(container);
-            ++it)
-        {
-            selection.push_back(&(*it));
-        }
-
-        std::map<std::pair<item_type*, item_type*>, bool> map;
-        divide_and_conquer<1>(selection, map, geometry1, geometry2, collection,
-                    direction, box);
-        ***/
-    }
-};
-
-
-template
-<
-    typename GeometryOut,
-    typename Container,
-    typename Geometry1,
-    typename Geometry2,
-    typename RingCollection,
-    typename OutputIterator
->
-inline OutputIterator add_all_rings(Container& container,
-            Geometry1 const& geometry1, Geometry2 const& geometry2,
-            RingCollection const& collection,
-            overlay_type direction, 
-            OutputIterator out)
-{
-    typedef typename boost::range_iterator<Container>::type iterator;
-    typedef typename geometry::tag<GeometryOut>::type tag_out;
-    typedef typename geometry::tag<Geometry1>::type tag1;
-    typedef typename geometry::tag<Geometry2>::type tag2;
-    typedef void tag3; // For the ring-container
-
-
-    bool result_filled = false;
-    GeometryOut result;
-    ring_identifier previous_id;
-    previous_id.source_index = -1;
-
-    for (iterator it = boost::begin(container);
-        it != boost::end(container);
-        ++it)
-    {
-
-        bool const include_as_interior = result_filled
-                && it->id(direction) == previous_id
-                && it->included(direction);
-
-        bool include_and_reverse = direction == overlay_difference
-                && ! include_as_interior
-                && it->negative()
-                && it->included(direction);
-
-        if (it->positive() || include_and_reverse)
-        {
-            // If it is an outer ring, it is included if there are no parents
-            // (union) or if there are parents (intersection)
-            // or for difference it is an exterior ring but becomes an interior ring
-            if (it->included(direction))
-            {
-                if (result_filled && ! include_as_interior)
-                {
-                    *out++ = result;
-                    previous_id.source_index = -1;
-                    result_filled = false;
-                    geometry::clear(result);
-                }
-
-                if (include_as_interior)
-                {
-                    include_and_reverse = true;
-                }
-
-                previous_id = it->ring_id;
-                result_filled = true;
-                if (it->ring_id.source_index == 0)
-                {
-                    convert_ring<tag_out>::apply(result,
-                                get_ring<tag1>::apply(it->ring_id, geometry1), 
-                                include_as_interior, include_and_reverse);
-                }
-                else if (it->ring_id.source_index == 1)
-                {
-                    convert_ring<tag_out>::apply(result,
-                                get_ring<tag2>::apply(it->ring_id, geometry2), 
-                                include_as_interior, include_and_reverse);
-                }
-                else if (it->ring_id.source_index == 2)
-                {
-                    convert_ring<tag_out>::apply(result,
-                                get_ring<tag3>::apply(it->ring_id, collection), 
-                                include_as_interior, include_and_reverse);
-                }
-            }
-        }
-        else if (include_as_interior)
-        {
-            // If it is an interior ring, it is included if
-            // it's parent-id matches the id of the outputted exterior ring
-            if (it->ring_id.source_index == 0)
-            {
-                convert_ring<tag_out>::apply(result,
-                            get_ring<tag1>::apply(it->ring_id,
-                                        geometry1), true, false);
-            }
-            else if (it->ring_id.source_index == 1)
-            {
-                convert_ring<tag_out>::apply(result,
-                            get_ring<tag2>::apply(it->ring_id,
-                                        geometry2), true, false);
-            }
-            else if (it->ring_id.source_index == 2)
-            {
-                convert_ring<tag_out>::apply(result,
-                            get_ring<tag3>::apply(it->ring_id,
-                                        collection), true, false);
-            }
-        }
-    }
-    if (result_filled)
-    {
-        *out++ = result;
-    }
-    return out;
-}
-
-
-template
-<
-    typename GeometryOut,
-    typename Rings, typename Map,
-    typename Geometry1, typename Geometry2,
-    typename OutputIterator
->
-inline OutputIterator assemble(Rings const& rings, Map const& map,
-            Geometry1 const& geometry1,
-            Geometry2 const& geometry2,
-            overlay_type direction, bool , bool splitted,
-            OutputIterator out)
-{
-        typedef typename geometry::tag<Geometry1>::type tag1;
-        typedef typename geometry::tag<Geometry2>::type tag2;
-        typedef typename geometry::tag<GeometryOut>::type tag_out;
-
-        typedef typename geometry::point_type<GeometryOut>::type point_type;
-        typedef typename boost::range_value<Rings>::type ring_type;
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble" << std::endl;
-#endif
-
-        typedef std::vector
-            <
-                ring_properties<point_type>
-            > ring_properties_container_type;
-        ring_properties_container_type ring_properties_container;
-
-        bool const dissolve = direction == overlay_dissolve;
-
-        if (! splitted)
-        {
-            add_to_containment
-                <
-                    tag1,
-                    Geometry1
-                >::apply(ring_properties_container,
-                            ring_identifier(0, -1,-1), geometry1,
-                            map, dissolve);
-        }
-        if (! dissolve)
-        {
-            add_to_containment
-                <
-                    tag2,
-                    Geometry2
-                >::apply(ring_properties_container,
-                            ring_identifier(1, -1,-1), geometry2,
-                            map, false);
-        }
-
-        // Add all produced rings using source index 2
-        {
-            ring_identifier id(2, 0, -1);
-            for (typename boost::range_iterator<Rings const>::type
-                    it = boost::begin(rings);
-                    it != boost::end(rings);
-                    ++it, ++id.multi_index)
-            {
-                ring_properties_container.push_back(
-                        ring_properties<point_type>(id, *it, false, true));
-            }
-        }
-
-        bool only_positive = true;
-        {
-            int pos=0, neg=0;
-            for (typename ring_properties_container_type::const_iterator
-                    it = boost::begin(ring_properties_container);
-                it != boost::end(ring_properties_container);
-                ++it)
-            {
-                if (it->positive())
-                {
-                    pos++;
-                }
-                else
-                {
-                    neg++;
-                    only_positive = false;
-                }
-            }
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-            std::cout << "assemble, pos=" << pos << " neg=" << neg << std::endl;
-#endif
-        }
-
-        //if (! only_positive)
-        {
-            typedef model::box<point_type> box_type;
-            box_type total = geometry::make_envelope<box_type>(geometry1);
-            geometry::combine(total,
-                        geometry::make_envelope<box_type>(geometry2));
-
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble.properties sort "
-    << boost::size(ring_properties_container) << std::endl;
-#endif
-            std::sort(boost::begin(ring_properties_container),
-                boost::end(ring_properties_container));
-
-
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble.enrich containment" << std::endl;
-#endif
-            enrich_containment
-                <
-                    ring_properties_container_type,
-                    Geometry1,
-                    Geometry2,
-                    Rings,
-                    model::box<point_type>
-                >::apply(ring_properties_container,
-                        geometry1, geometry2, rings, direction, total);
-
-    // Sort container on parent-id
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble.properties sort on parent-id "
-    << boost::size(ring_properties_container) << std::endl;
-#endif
-            std::sort(boost::begin(ring_properties_container),
-                    boost::end(ring_properties_container),
-                    sort_on_id_or_parent_id
-                        <
-                            ring_properties<point_type>
-                        >(direction));
-        }
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble.add rings" << std::endl;
-#endif
-        return add_all_rings<GeometryOut>(ring_properties_container,
-                    geometry1, geometry2, rings, direction, out);
-}
-
-
-}} // namespace detail::overlay
-#endif // DOXYGEN_NO_DETAIL
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
+//obsolete
\ No newline at end of file

Added: trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -0,0 +1,182 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2011, 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_OVERLAY_ASSIGN_PARENTS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
+
+#include <boost/geometry/algorithms/area.hpp>
+#include <boost/geometry/algorithms/envelope.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
+#include <boost/geometry/algorithms/detail/overlay/within_util.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+
+template
+<
+    typename Item,
+    typename Geometry1, typename Geometry2,
+    typename RingCollection
+>
+static inline bool contains(ring_identifier ring_id, Item const& item1, Item const& item2,
+        Geometry1 const& geometry1, Geometry2 const& geometry2,
+        RingCollection const& collection)
+{
+    typedef typename geometry::tag<Geometry1>::type tag1;
+    typedef typename geometry::tag<Geometry2>::type tag2;
+
+    int code = -1;
+    switch (ring_id.source_index)
+    {
+        case 0 :
+            code = point_in_ring(item2.point,
+                get_ring<tag1>::apply(ring_id, geometry1));
+            break;
+        case 1 :
+            code = point_in_ring(item2.point,
+                get_ring<tag2>::apply(ring_id, geometry2));
+            break;
+        case 2 :
+            // Within if it is within one of the collection
+            for (BOOST_AUTO(it, boost::begin(collection)); it != boost::end(collection); ++it)
+            {
+                int subcode = point_in_ring(item2.point,
+                    get_ring<ring_tag>::apply(ring_id, *it));
+                if (subcode > code)
+                {
+                    code = subcode;
+                }
+            }
+            break;
+    }
+    return code == 0 ? item1.get_area() < 0 : code == 1;
+}
+
+
+template <typename Point>
+struct ring_info_helper
+{
+    typedef typename geometry::area_result<Point>::type area_type;
+
+    ring_identifier id;
+    area_type area;
+    model::box<Point> envelope;
+
+    inline ring_info_helper(ring_identifier i, area_type a)
+        : id(i), area(a)
+    {}
+
+    // To be sorted decending
+    inline bool operator<(ring_info_helper<Point> const& other) const
+    {
+        return abs(this->area) > abs(other.area);
+    }
+};
+
+
+template
+<
+    typename Geometry1, typename Geometry2,
+    typename RingCollection,
+    typename RingMap
+>
+inline void assign_parents(Geometry1 const& geometry1,
+            Geometry2 const& geometry2,
+            RingCollection const& collection,
+            RingMap& ring_map)
+{
+    typedef typename geometry::tag<Geometry1>::type tag1;
+    typedef typename geometry::tag<Geometry2>::type tag2;
+
+    typedef typename RingMap::mapped_type ring_info_type;
+    typedef typename ring_info_type::point_type point_type;
+
+    typedef typename RingMap::iterator map_iterator_type;
+
+    // A map is not sortable, so copy ring_id/area and added envelope to vector
+    {
+        typedef ring_info_helper<point_type> helper;
+        typedef std::vector<helper> vector_type;
+        typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;
+
+        vector_type vector;
+
+        for (map_iterator_type it = boost::begin(ring_map); it != boost::end(ring_map); ++it)
+        {
+            vector.push_back(helper(it->first, abs(it->second.area)));
+            switch(it->first.source_index)
+            {
+                case 0 :
+                    geometry::envelope(get_ring<tag1>::apply(it->first, geometry1), 
+                            vector.back().envelope);
+                    break;
+                case 1 :
+                    geometry::envelope(get_ring<tag2>::apply(it->first, geometry2), 
+                            vector.back().envelope);
+                    break;
+                case 2 :
+                    geometry::envelope(get_ring<void>::apply(it->first, collection), 
+                            vector.back().envelope);
+                    break;
+            }
+        }
+
+        std::sort(vector.begin(), vector.end());
+
+        // Assign parents
+        // Semi-quadratic loop over rings to compare them to each other (envelope first)
+        // Walks from largest abs(area) to smallest -> most direct parent comes last.
+        for (vector_iterator_type out_it = boost::begin(vector); out_it != boost::end(vector); ++out_it)
+        {
+            ring_info_type& outer = ring_map[out_it->id];
+
+            if (outer.get_area() > 0)
+            {
+                vector_iterator_type inn_it = out_it;
+                for (++inn_it; inn_it != boost::end(vector); ++inn_it)
+                {
+                    ring_info_type& inner = ring_map[inn_it->id];
+
+                    if (inner.get_area() < 0
+                        && geometry::within(inner.point, out_it->envelope)
+                        && contains(out_it->id, outer, inner, geometry1, geometry2, collection))
+                    {
+                        inner.parent = out_it->id;
+                    }
+                }
+            }
+        }
+    }
+
+    // Assign childlist
+    for (map_iterator_type it = boost::begin(ring_map); it != boost::end(ring_map); ++it)
+    {
+        if (it->second.parent.source_index >= 0)
+        {
+            ring_map[it->second.parent].children.push_back(it->first);
+        }
+    }
+
+}
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP

Modified: trunk/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -10,6 +10,7 @@
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENT_POINT_HPP
 
 
+#include <boost/array.hpp>
 #include <boost/mpl/assert.hpp>
 #include <boost/range.hpp>
 

Modified: trunk/boost/geometry/algorithms/detail/overlay/get_ring.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/get_ring.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/get_ring.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -32,25 +32,28 @@
 struct get_ring
 {};
 
+// "void" is mapped to a container of rings (multi-ring but that does not exist)
 template<>
-struct get_ring<ring_tag>
+struct get_ring<void>
 {
-    template<typename Ring>
-    static inline Ring const& apply(ring_identifier const& , Ring const& ring)
+    template<typename Container>
+    static inline typename boost::range_value<Container>::type const&
+                apply(ring_identifier const& id, Container const& container)
     {
-        return ring;
+        return container[id.multi_index];
     }
 };
 
 
+
+
 template<>
-struct get_ring<void>
+struct get_ring<ring_tag>
 {
-    template<typename Container>
-    static inline typename boost::range_value<Container>::type const&
-                apply(ring_identifier const& id, Container const& container)
+    template<typename Ring>
+    static inline Ring const& apply(ring_identifier const& , Ring const& ring)
     {
-        return container[id.multi_index];
+        return ring;
     }
 };
 

Modified: trunk/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -13,6 +13,7 @@
 
 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
 
 
 namespace boost { namespace geometry

Modified: trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -16,7 +16,6 @@
 #include <boost/mpl/assert.hpp>
 
 
-#include <boost/geometry/algorithms/detail/overlay/assemble.hpp>
 #include <boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp>
 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
@@ -31,6 +30,11 @@
 
 #include <boost/geometry/iterators/range_type.hpp>
 
+#include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
+#include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
+#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
+#include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
+
 
 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 #  include <boost/geometry/util/write_dsv.hpp>
@@ -46,13 +50,59 @@
 {
 
 
+// Skip for assemble process
+template <typename TurnInfo>
+inline bool skip(TurnInfo const& turn_info)
+{
+    return (turn_info.discarded || turn_info.both(operation_union))
+        && ! turn_info.any_blocked()
+        && ! turn_info.both(operation_intersection)
+        ;
+}
+
+
+
+
+template <typename TurnPoints, typename Map>
+inline void map_turns(Map& map, TurnPoints const& turn_points)
+{
+    typedef typename boost::range_value<TurnPoints>::type turn_point_type;
+    typedef typename turn_point_type::container_type container_type;
+
+    int index = 0;
+    for (typename boost::range_iterator<TurnPoints const>::type
+            it = boost::begin(turn_points);
+         it != boost::end(turn_points);
+         ++it, ++index)
+    {
+        if (! skip(*it))
+        {
+            int op_index = 0;
+            for (typename boost::range_iterator<container_type const>::type
+                    op_it = boost::begin(it->operations);
+                op_it != boost::end(it->operations);
+                ++op_it, ++op_index)
+            {
+                ring_identifier ring_id
+                    (
+                        op_it->seg_id.source_index,
+                        op_it->seg_id.multi_index,
+                        op_it->seg_id.ring_index
+                    );
+                map[ring_id]++;
+            }
+        }
+    }
+}
+
+
 
 template
 <
     typename Geometry1, typename Geometry2,
     bool Reverse1, bool Reverse2, bool ReverseOut,
     typename OutputIterator, typename GeometryOut,
-    overlay_type Direction, 
+    overlay_type Direction,
     typename Strategy
 >
 struct overlay
@@ -88,8 +138,7 @@
             {
                 std::map<ring_identifier, int> map;
                 ring_container_type rings;
-                return assemble<GeometryOut>(rings, map,
-                                geometry1, geometry2, Direction, false, false, out);
+                ////return assemble<GeometryOut>(rings, map, geometry1, geometry2, Direction, false, false, out);
             }
             return out;
         }
@@ -110,7 +159,7 @@
 std::cout << "enrich" << std::endl;
 #endif
         typename Strategy::side_strategy_type side_strategy;
-        geometry::enrich_intersection_points<Reverse1, Reverse2>(turn_points, 
+        geometry::enrich_intersection_points<Reverse1, Reverse2>(turn_points,
                 Direction == overlay_union
                     ? boost::geometry::detail::overlay::operation_union
                     : boost::geometry::detail::overlay::operation_intersection,
@@ -142,8 +191,30 @@
 
         std::map<ring_identifier, int> map;
         map_turns(map, turn_points);
-        return assemble<GeometryOut>(rings, map,
-                        geometry1, geometry2, Direction, false, false, out);
+        //return assemble<GeometryOut>(rings, map, geometry1, geometry2, Direction, false, false, out);
+
+        typedef ring_properties<typename geometry::point_type<Geometry1>::type> info;
+
+        std::map<ring_identifier, info> selected;
+
+        select_rings<Direction>(geometry1, geometry2, map, selected);
+
+        // Add rings from container
+        {
+            ring_identifier id(2, 0, -1);
+            for (typename boost::range_iterator<ring_container_type>::type
+                    it = boost::begin(rings);
+                    it != boost::end(rings);
+                    ++it)
+            {
+                selected[id] = info(*it);
+                id.multi_index++;
+            }
+        }
+
+        assign_parents(geometry1, geometry2, rings, selected);
+        return add_rings<GeometryOut>(selected, geometry1, geometry2, rings, out);
+
     }
 };
 

Modified: trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 //
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Copyright Barend Gehrels 2011, 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)
@@ -10,252 +10,67 @@
 
 
 #include <boost/geometry/algorithms/area.hpp>
-#include <boost/geometry/algorithms/envelope.hpp>
-#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
+#include <boost/geometry/algorithms/within.hpp>
 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
-#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
-#include <boost/geometry/util/math.hpp>
-
-#include <boost/geometry/geometries/box.hpp>
 
 
 namespace boost { namespace geometry
 {
 
 
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
 template <typename Point>
 struct ring_properties
 {
     typedef Point point_type;
-    typedef model::box<Point> box_type;
-
-    ring_identifier ring_id;
-    typename area_result<Point>::type area;
-    int signum;
-
-    bool intersects;
-    bool produced;
-    bool diff_included;
-
-    // "Stack"/counter of non-intersecting parent rings.
-    // This denotes if it a negative ring should be included,
-    int parent_count;
+    typedef typename area_result<Point>::type area_type;
 
-    // ID of the parent
-    ring_identifier parent_ring_id;
+    // Filled by "select_rings"
+    Point point;
+    area_type area;
+
+    int within_code;
+    bool reversed;
+
+    // Filled/used by "assign_rings"
+    ring_identifier parent;
+    std::vector<ring_identifier> children;
 
-    box_type box;
-
-    point_type point;
-    bool has_point;
-
-    // Default constructor (necessary for vector, but not called)
     inline ring_properties()
-        : intersects(false)
-        , produced(false)
-        , diff_included(false)
-        , parent_count(0)
-        , has_point(false)
-    {
-        parent_ring_id.source_index = -1;
-    }
-
-    template <typename Geometry>
-    inline ring_properties(ring_identifier id, Geometry const& geometry,
-            bool i, bool p = false)
-        : ring_id(id)
-        , area(geometry::area(geometry))
-        , intersects(i)
-        , produced(p)
-        , diff_included(false)
-        , parent_count(0)
-        , box(geometry::make_envelope<box_type>(geometry))
-    {
-        has_point = geometry::point_on_border(point, geometry, true);
-        typedef typename coordinate_type<Geometry>::type coordinate_type;
-        coordinate_type const zero = coordinate_type();
-        signum = area > zero ? 1 : area < zero ? -1 : 0;
-        parent_ring_id.source_index = -1;
-    }
-
-    inline bool positive() const { return signum == 1; }
-    inline bool negative() const { return signum == -1; }
-
-    inline bool operator<(ring_properties<Point> const& other) const
-    {
-        // Normal sorting: in reverse order
-        return geometry::math::abs(area) > geometry::math::abs(other.area);
-    }
-
-    inline ring_identifier const& id(overlay_type type) const
-    {
-        if (type == overlay_difference
-            && positive()
-            && parent_ring_id.source_index == 0
-            && ring_id.source_index == 1)
-        {
-            return parent_ring_id;
-        }
-
-        // Return the id of ifself, or of the parent
-        return positive() || parent_ring_id.source_index < 0
-            ? ring_id
-            : parent_ring_id;
-    }
-
-
-    inline void push(ring_properties<Point> const& r,
-                overlay_type direction)
-    {
-        if (r.included(direction))
-        {
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << " id.push " << r.ring_id;
-#endif
-            parent_ring_id = r.ring_id;
-        }
-        else if (direction == overlay_difference
-            && r.ring_id.source_index == this->ring_id.source_index
-            && r.ring_id.source_index == 1)
-        {
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << " diff.parent " << r.ring_id << " of " << this->ring_id;
-#endif
-            diff_included = true;
-        }
-        if (! r.produced || direction == overlay_dissolve)
-        {
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << " or.push " << r.ring_id;
-#endif
-            parent_count++;
-        }
-    }
-
-
-    inline void pop(ring_properties<Point> const& r)
-    {
-        if (! r.produced && parent_count > 0)
-        {
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << " or.pop";
-#endif
-
-            parent_count--;
-        }
-    }
-
-
-    inline bool interior_included(overlay_type direction) const
-    {
-        if (negative())
-        {
-            // Original inner rings are included if there
-            // are two untouched parents (intersection) or one (union);
-            // Produced ones are included if there is a parent found (should be!)
-            return (produced && parent_count > 0)
-                || (direction == overlay_union && parent_count == 1)
-                || (direction == overlay_dissolve && parent_count == 1)
-                || (direction == overlay_intersection && parent_count > 1)
-                || (direction == overlay_difference
-                    && parent_count > 1
-                    && ring_id.source_index == 2 // produced
-                    )
-                ;
-        }
-        return false;
-    }
+        : area(area_type())
+        , within_code(0)
+        , reversed(false)
+    {}
 
-    inline bool included(overlay_type direction) const
+    template <typename RingOrBox>
+    inline ring_properties(RingOrBox const& ring_or_box)
+        : within_code(0)
+        , reversed(false)
     {
-        if (produced && direction != overlay_dissolve)
-        {
-            // Traversed rings are included in all operations,
-            // because traversal was direction-dependant.
-            // On dissolve, this is not the case.
-            return true;
-        }
-        if (intersects)
-        {
-            // Original rings which have intersections should
-            // always be skipped
-            return false;
-        }
-
-        if (positive())
-        {
-            // Outer rings are included if they don't have parents
-            // (union,dissolve,difference if source=0) or have parents (intersection)
-            return (produced && parent_count == 0)
-                || (direction == overlay_union && parent_count == 0)
-                || (direction == overlay_dissolve && parent_count == 0)
-                || (direction == overlay_difference 
-                        && parent_count == 0 
-                        && ring_id.source_index == 0) 
-                || (direction == overlay_difference 
-                        && parent_count > 0
-                        && ring_id.source_index == 1) 
-                || (direction == overlay_intersection && parent_count > 0)
-                ;
-        }
-        else if (negative())
-        {
-            // Inner rings are included if the last encountered parent
-            // matches the operation
-            return interior_included(direction)
-                || (direction == overlay_difference && diff_included);
-        }
-        return false;
+        this->area = geometry::area(ring_or_box);
+        geometry::point_on_border(this->point, ring_or_box, true);
     }
 
-    inline bool untouched() const
+    template <typename RingOrBox, typename Geometry>
+    inline ring_properties(RingOrBox const& ring_or_box, Geometry const& geometry)
+        : reversed(false)
     {
-        // It should be in comparisons on parent/child if:
-        // it is produced
-        // it is not produced, and not intersecting
-        return ! produced && ! intersects;
+        this->area = geometry::area(ring_or_box);
+        geometry::point_on_border(this->point, ring_or_box, true);
+        this->within_code = geometry::within(this->point, geometry) ? 1 : -1;
     }
 
-
-#if defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
-    friend std::ostream& operator<<(std::ostream &os, ring_properties<Point> const& prop)
+    area_type get_area() const
     {
-        os << "prop: " << prop.ring_id << " " << prop.area;
-        os << " count: " << prop.parent_count;
-        std::cout << " parent: " << prop.parent_ring_id;
-        if (prop.produced) std::cout << " produced";
-        if (prop.intersects) std::cout << " intersects";
-        if (prop.included(overlay_union)) std::cout << " @union";
-        if (prop.included(overlay_dissolve)) std::cout << " @dissolve";
-        if (prop.included(overlay_intersection)) std::cout << " @intersection";
-        if (prop.included(overlay_difference)) std::cout << " @difference";
-        return os;
+        return reversed ? -area : area;
     }
-#endif
-
 };
 
-
-template<typename Prop>
-struct sort_on_id_or_parent_id
-{
-    overlay_type m_type;
-public :
-    inline sort_on_id_or_parent_id(overlay_type type)
-        : m_type(type)
-    {}
-
-    inline bool operator()(Prop const& left, Prop const& right) const
-    {
-        ring_identifier const& left_id = left.id(m_type);
-        ring_identifier const& right_id = right.id(m_type);
-
-        // If it is the same, sort on size descending
-        return left_id == right_id
-            ? geometry::math::abs(left.area) > geometry::math::abs(right.area)
-            : left_id < right_id;
-    }
-};
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
 
 
 }} // namespace boost::geometry

Added: trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -0,0 +1,217 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2007-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_OVERLAY_SELECT_RINGS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
+
+
+#include <vector>
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/algorithms/area.hpp>
+#include <boost/geometry/algorithms/within.hpp>
+#include <boost/geometry/algorithms/detail/point_on_border.hpp>
+#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
+#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
+#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+
+namespace dispatch
+{
+
+    template <typename Tag, typename Geometry>
+    struct select_rings
+    {};
+
+    template <typename Box>
+    struct select_rings<box_tag, Box>
+    {
+        template <typename Geometry, typename Map>
+        static inline void apply(Box const& box, Geometry const& geometry, ring_identifier const& id, Map& map)
+        {
+            typedef typename Map::mapped_type info;
+            map[id] = info(box, geometry);
+        }
+    };
+
+    template <typename Ring>
+    struct select_rings<ring_tag, Ring>
+    {
+        template <typename Geometry, typename Map>
+        static inline void apply(Ring const& ring, Geometry const& geometry, ring_identifier const& id, Map& map)
+        {
+            // MAYBE use within-code algorithm (but not important - all these rings should be untouched)
+
+            typedef typename Map::mapped_type info;
+            map[id] = info(ring, geometry);
+        }
+    };
+
+
+    template <typename Polygon>
+    struct select_rings<polygon_tag, Polygon>
+    {
+        template <typename Geometry, typename Map>
+        static inline void apply(Polygon const& polygon, Geometry const& geometry, ring_identifier id, Map& map)
+        {
+            typedef typename geometry::ring_type<Polygon>::type ring_type;
+            typedef select_rings<ring_tag, ring_type> per_ring;
+
+            per_ring::apply(exterior_ring(polygon), geometry, id, map);
+
+            typename interior_return_type<Polygon const>::type rings
+                        = interior_rings(polygon);
+            for (BOOST_AUTO(it, boost::begin(rings)); it != boost::end(rings); ++it)
+            {
+                id.ring_index++;
+                per_ring::apply(*it, geometry, id, map);
+            }
+        }
+    };
+}
+
+
+template<overlay_type OverlayType>
+struct decide
+{};
+
+template<>
+struct decide<overlay_union>
+{
+    template <typename Code>
+    static bool include(ring_identifier const& id, Code const& code)
+    {
+        return code.within_code * -1 == 1;
+    }
+    template <typename Code>
+    static bool reversed(ring_identifier const& , Code const& )
+    {
+        return false;
+    }
+    template <typename Code>
+    static std::string reverse(ring_identifier const& , Code const& )
+    {
+        return "";
+    }
+};
+
+template<>
+struct decide<overlay_difference>
+{
+    template <typename Code>
+    static bool include(ring_identifier const& id, Code const& code)
+    {
+        bool is_first = id.source_index == 0;
+        return code.within_code * -1 * (is_first ? 1 : -1) == 1;
+    }
+    template <typename Code>
+    static bool reversed(ring_identifier const& id, Code const& code)
+    {
+        return include(id, code) && id.source_index == 1;
+    }
+    template <typename Code>
+    static std::string reverse(ring_identifier const& id, Code const& code)
+    {
+        if (include(id, code) && id.source_index == 1)
+        {
+            return " REV";
+        }
+        return "";
+    }
+};
+
+template<>
+struct decide<overlay_intersection>
+{
+    template <typename Code>
+    static bool include(ring_identifier const& id, Code const& code)
+    {
+        return code.within_code * 1 == 1;
+    }
+    template <typename Code>
+    static bool reversed(ring_identifier const& , Code const& )
+    {
+        return false;
+    }
+    template <typename Code>
+    static std::string reverse(ring_identifier const& , Code const& )
+    {
+        return "";
+    }
+};
+
+
+/*!
+\brief The function select_rings select rings based on the overlay-type (union,intersection)
+*/
+template
+<
+    overlay_type OverlayType,
+    typename Geometry1, typename Geometry2,
+    typename IntersectionMap, typename SelectionMap
+>
+inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
+            IntersectionMap const& intersection_map, SelectionMap& selection_map)
+{
+    typedef typename geometry::tag<Geometry1>::type tag1;
+    typedef typename geometry::tag<Geometry2>::type tag2;
+
+    // geometry1 and 2 is a ring, or a (multi)polygon -> dispatch on that
+    SelectionMap map_with_all;
+    dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2, ring_identifier(0, -1, -1), map_with_all);
+    dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1, ring_identifier(1, -1, -1), map_with_all);
+
+    selection_map.clear();
+
+    for (BOOST_AUTO(it, boost::begin(map_with_all)); it != boost::end(map_with_all); ++it)
+    {
+        /*
+        int union_code = it->second.within_code * -1;
+        bool is_first = it->first.source_index == 0;
+        std::cout << it->first << " " << it->second.area
+            << ": " << it->second.within_code
+            << " union: " << union_code
+            << " intersection: " << (it->second.within_code * 1)
+            << " G1-G2: " << (union_code * (is_first ? 1 : -1))
+            << " G2-G1: " << (union_code * (is_first ? -1 : 1))
+            << " -> " << (decide<OverlayType>::include(it->first, it->second) ? "INC" : "")
+            << decide<OverlayType>::reverse(it->first, it->second)
+            << std::endl;
+        */
+
+        bool found = intersection_map.find(it->first) != intersection_map.end();
+        if (! found)
+        {
+            if (decide<OverlayType>::include(it->first, it->second))
+            {
+                selection_map[it->first] = it->second;
+                selection_map[it->first].reversed = decide<OverlayType>::reversed(it->first, it->second);
+            }
+        }
+    }
+}
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP

Added: trunk/boost/geometry/algorithms/detail/overlay/within_util.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/overlay/within_util.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -0,0 +1,97 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2007-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_OVERLAY_WITHIN_UTIL_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_WITHIN_UTIL_HPP
+
+
+
+#include <boost/geometry/algorithms/within.hpp>
+#include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+template<typename Tag, typename Point, typename Geometry>
+struct within_code
+{};
+
+template<typename Point, typename Box>
+struct within_code<box_tag, Point, Box>
+{
+    static inline int apply(Point const& point, Box const& box)
+    {
+        // 1. Check outside
+        if (get<0>(point) < get<min_corner, 0>(box)
+            || get<0>(point) > get<max_corner, 0>(box)
+            || get<1>(point) < get<min_corner, 1>(box)
+            || get<1>(point) > get<max_corner, 1>(box))
+        {
+            return -1;
+        }
+        // 2. Check border
+        if (geometry::math::equals(get<0>(point), get<min_corner, 0>(box))
+            || geometry::math::equals(get<0>(point), get<max_corner, 0>(box))
+            || geometry::math::equals(get<1>(point), get<min_corner, 1>(box))
+            || geometry::math::equals(get<1>(point), get<max_corner, 1>(box)))
+        {
+            return 0;
+        }
+        return 1;
+    }
+};
+template<typename Point, typename Ring>
+struct within_code<ring_tag, Point, Ring>
+{
+    static inline int apply(Point const& point, Ring const& ring)
+    {
+        // Same as point_in_ring but here ALWAYS with winding.
+        typedef strategy::within::winding<Point> strategy_type;
+
+        return detail::within::point_in_ring
+            <
+                Point,
+                Ring,
+                order_as_direction<geometry::point_order<Ring>::value>::value,
+                geometry::closure<Ring>::value,
+                strategy_type
+            >::apply(point, ring, strategy_type());
+    }
+};
+
+
+template<typename Point, typename Geometry>
+inline int point_in_ring(Point const& point, Geometry const& geometry)
+{
+    return within_code<typename geometry::tag<Geometry>::type, Point, Geometry>
+        ::apply(point, geometry);
+}
+
+template<typename Point, typename Geometry>
+inline bool within_or_touch(Point const& point, Geometry const& geometry)
+{
+    return within_code<typename geometry::tag<Geometry>::type, Point, Geometry>
+        ::apply(point, geometry) >= 0;
+}
+
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_WITHIN_UTIL_HPP

Modified: trunk/boost/geometry/algorithms/detail/ring_identifier.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/ring_identifier.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/ring_identifier.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -46,11 +46,11 @@
     }
 
 #if defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
-    friend std::ostream& operator<<(std::ostream &os, ring_identifier const& seg_id)
+    friend std::ostream& operator<<(std::ostream &os, ring_identifier const& ring_id)
     {
-        os << "(s:" << seg_id.source_index;
-        if (seg_id.ring_index >= 0) os << ", r:" << seg_id.ring_index;
-        if (seg_id.multi_index >= 0) os << ", m:" << seg_id.multi_index;
+        os << "(s:" << ring_id.source_index;
+        if (ring_id.ring_index >= 0) os << ", r:" << ring_id.ring_index;
+        if (ring_id.multi_index >= 0) os << ", m:" << ring_id.multi_index;
         os << ")";
         return os;
     }

Modified: trunk/boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp
==============================================================================
--- trunk/boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp	(original)
+++ trunk/boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -1,62 +1 @@
-// 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_MULTI_ALGORITHMS_DETAIL_OVERLAY_ADD_TO_CONTAINMENT_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_ADD_TO_CONTAINMENT_HPP
-
-
-#include <boost/range.hpp>
-
-#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
-#include <boost/geometry/algorithms/detail/overlay/add_to_containment.hpp>
-#include <boost/geometry/multi/core/tags.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay
-{
-
-
-template <typename MultiPolygon>
-struct add_to_containment<multi_polygon_tag, MultiPolygon>
-{
-    template <typename ContainmentContainer, typename Map>
-    static inline void apply(ContainmentContainer& container,
-            ring_identifier const& id, MultiPolygon const& multi_polygon,
-            Map const& map, bool dissolve)
-    {
-        ring_identifier copy = id;
-        copy.multi_index = 0;
-
-        // Add all rings with the updated index
-        for (typename boost::range_iterator<MultiPolygon const>::type it
-                = boost::begin(multi_polygon);
-            it != boost::end(multi_polygon);
-            ++it, ++copy.multi_index)
-        {
-            add_to_containment
-            <
-                polygon_tag,
-                typename boost::range_value<MultiPolygon>::type
-            >::apply(container, copy, *it, map, dissolve);
-        }
-    }
-};
-
-
-}} // namespace detail::overlay
-#endif // DOXYGEN_NO_DETAIL
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_ADD_TO_CONTAINMENT_HPP
+//obsolete
\ No newline at end of file

Added: trunk/boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -0,0 +1,61 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2007-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_MULTI_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
+#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
+
+
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+namespace dispatch
+{
+
+    template <typename Multi>
+    struct select_rings<multi_polygon_tag, Multi>
+    {
+        template <typename Geometry, typename Map>
+        static inline void apply(Multi const& multi, Geometry const& geometry, ring_identifier id, Map& map)
+        {
+            typedef typename boost::range_iterator
+                <
+                    Multi const
+                >::type iterator_type;
+
+            typedef select_rings<polygon_tag, typename boost::range_value<Multi>::type> per_polygon;
+
+            id.multi_index = 0;
+            for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
+            {
+                id.ring_index = -1;
+                per_polygon::apply(*it, geometry, id, map);
+                id.multi_index++;
+            }
+        }
+    };
+}
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP

Modified: trunk/boost/geometry/multi/algorithms/difference.hpp
==============================================================================
--- trunk/boost/geometry/multi/algorithms/difference.hpp	(original)
+++ trunk/boost/geometry/multi/algorithms/difference.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -16,11 +16,12 @@
 #include <boost/geometry/multi/core/point_order.hpp>
 #include <boost/geometry/multi/algorithms/envelope.hpp>
 #include <boost/geometry/multi/algorithms/num_points.hpp>
+#include <boost/geometry/multi/algorithms/within.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/get_ring.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp>
-#include <boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp>
 #include <boost/geometry/multi/algorithms/detail/sections/range_by_section.hpp>
 #include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
 

Modified: trunk/boost/geometry/multi/algorithms/intersection.hpp
==============================================================================
--- trunk/boost/geometry/multi/algorithms/intersection.hpp	(original)
+++ trunk/boost/geometry/multi/algorithms/intersection.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -20,7 +20,7 @@
 #include <boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp>
-#include <boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp>
 #include <boost/geometry/multi/algorithms/detail/sections/range_by_section.hpp>
 #include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
 

Modified: trunk/boost/geometry/multi/algorithms/union.hpp
==============================================================================
--- trunk/boost/geometry/multi/algorithms/union.hpp	(original)
+++ trunk/boost/geometry/multi/algorithms/union.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -16,11 +16,12 @@
 #include <boost/geometry/multi/core/point_order.hpp>
 #include <boost/geometry/multi/algorithms/envelope.hpp>
 #include <boost/geometry/multi/algorithms/num_points.hpp>
+#include <boost/geometry/multi/algorithms/within.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/get_ring.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp>
-#include <boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp>
 #include <boost/geometry/multi/algorithms/detail/sections/range_by_section.hpp>
 #include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
 

Modified: trunk/boost/geometry/multi/multi.hpp
==============================================================================
--- trunk/boost/geometry/multi/multi.hpp	(original)
+++ trunk/boost/geometry/multi/multi.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -50,7 +50,6 @@
 #include <boost/geometry/multi/algorithms/detail/sections/range_by_section.hpp>
 #include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
 
-#include <boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/get_ring.hpp>

Modified: trunk/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp
==============================================================================
--- trunk/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp	(original)
+++ trunk/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp	2011-03-03 06:21:59 EST (Thu, 03 Mar 2011)
@@ -9,7 +9,6 @@
 #ifndef BOOST_GEOMETRY_STRATEGY_AGNOSTIC_POINT_IN_POLY_WINDING_HPP
 #define BOOST_GEOMETRY_STRATEGY_AGNOSTIC_POINT_IN_POLY_WINDING_HPP
 
-#include <boost/logic/tribool.hpp>
 
 #include <boost/geometry/util/math.hpp>
 #include <boost/geometry/util/select_calculation_type.hpp>