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

Subject: [Boost-commit] svn:boost r69828 - in trunk/boost/geometry: algorithms algorithms/detail algorithms/detail/overlay multi/algorithms/detail/overlay
From: barend.gehrels_at_[hidden]
Date: 2011-03-10 16:50:40

Author: barendgehrels
Date: 2011-03-10 16:50:35 EST (Thu, 10 Mar 2011)
New Revision: 69828
URL: http://svn.boost.org/trac/boost/changeset/69828

Log:
Refactored/removed quadratic loop (dramatic performance increase)
Added separate and generic divide_and_conquer.hpp 
Added:
   trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp   (contents, props changed)
Removed:
   trunk/boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp  |   183 ++++++++++++++++++++++++++++++++++----- 
   trunk/boost/geometry/algorithms/detail/overlay/get_ring.hpp        |     3                                         
   trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp       |     2                                         
   trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp         |    39 ++++++++                                
   trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp |     4                                         
   trunk/boost/geometry/algorithms/intersection_inserter.hpp          |     1                                         
   6 files changed, 202 insertions(+), 30 deletions(-)

Added: trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp	2011-03-10 16:50:35 EST (Thu, 10 Mar 2011)
@@ -0,0 +1,263 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIVIDE_AND_CONQUER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIVIDE_AND_CONQUER_HPP
+
+#include <vector>
+#include <boost/range/algorithm/copy.hpp>
+#include <boost/geometry/core/coordinate_type.hpp>
+
+namespace boost { namespace geometry
+{
+
+
+namespace detail
+{
+
+// Helper structure
+struct dac_index
+{
+    int index; // in original vector
+    bool is_quad_exceeding;
+
+    dac_index(int i = 0)
+        : index(i)
+        , is_quad_exceeding(false)
+    {}
+};
+
+
+class avoid_duplicates_helper
+{
+    std::set<std::pair<int,int> > processed;
+
+public :
+    template <typename Item>
+    inline bool apply(Item const& item1, Item const& item2)
+    {
+        bool done = false;
+        if (item1.is_quad_exceeding && item2.is_quad_exceeding)
+        {
+            std::pair<int,int> p;
+            if (item1.index < item2.index)
+            {
+                p.first = item1.index;
+                p.second = item2.index;
+            }
+            else
+            {
+                p.first = item2.index;
+                p.second = item1.index;
+            }
+
+            BOOST_AUTO(sit, processed.find(p));
+            if (sit == boost::end(processed))
+            {
+                processed.insert(p);
+            }
+            else
+            {
+                done = true;
+            }
+        }
+        return !done;
+    }
+};
+
+template <typename Visitor>
+class dac_static_visitor_avoiding_duplicates
+{
+    typedef std::vector<dac_index> dac_vector_type;
+    typedef boost::range_iterator<dac_vector_type const>::type dac_iterator_type;
+
+    avoid_duplicates_helper avoid_duplicates;
+    Visitor& m_visitor;
+
+public :
+    dac_static_visitor_avoiding_duplicates(Visitor& visitor)
+        : m_visitor(visitor)
+    {}
+
+    template <typename InputCollection>
+    inline void apply(InputCollection const& collection, 
+        dac_vector_type const& indexes) 
+    {
+        // Quadratic loop over the lowest quad
+        for(dac_iterator_type it1 = boost::begin(indexes); it1 != boost::end(indexes); ++it1)
+        {
+            for(dac_iterator_type it2 = boost::begin(indexes); it2 != boost::end(indexes); ++it2)
+            {
+                // This policy always calls in order of original colection
+                if (it1->index < it2->index)
+                {
+                    // This policy avoids handlig duplicates
+                    if (avoid_duplicates.apply(*it1, *it2))
+                    {
+                        m_visitor.apply(collection[it1->index], collection[it2->index], 
+                                it1->is_quad_exceeding, it2->is_quad_exceeding);
+                    }
+                }
+            }
+        }
+    }
+};
+
+
+template
+<
+    int Dimension,
+    typename Box,
+    typename OverlapsPolicy
+>
+struct divide_and_conquer
+{
+    typedef typename coordinate_type<Box>::type ctype;
+
+    template <typename InputCollection, typename Policy>
+    static inline void next_level(Box const& box, 
+            InputCollection const& collection,
+            std::vector<dac_index> const& fitting_in_quad,
+            std::vector<dac_index> exceeding_quad, // effectively const
+            int level, int min_elements,
+            Policy& policy)
+    {
+        typedef divide_and_conquer
+                <
+                    1 - Dimension,
+                    Box,
+                    OverlapsPolicy
+                > sub_divide;
+
+        if (level < 50
+            && boost::size(fitting_in_quad) > min_elements
+            && boost::size(fitting_in_quad) > boost::size(exceeding_quad)
+            )
+        {
+            sub_divide::apply(box, collection, fitting_in_quad, exceeding_quad, level + 1, min_elements, policy);
+        }
+        else
+        {
+            boost::copy(fitting_in_quad, std::back_inserter(exceeding_quad));
+            policy.apply(collection, exceeding_quad);
+        }
+    }
+
+    template <typename InputCollection, typename Policy>
+    static inline void apply(Box const& box,
+            InputCollection const& collection,
+            std::vector<dac_index> const& fitting_in_quad,
+            std::vector<dac_index>& exceeding_quad, // by value is intentional
+            int level,
+            int min_elements,
+            Policy& policy,
+            int size = -1)
+    {
+
+        typedef typename boost::range_value<InputCollection>::type item_type;
+
+        if (size == -1)
+        {
+            size = boost::size(collection);
+        }
+
+        // Divide input box into two parts, e.g. left/right
+        ctype two = 2;
+        ctype mid = (geometry::get<min_corner, Dimension>(box)
+                + geometry::get<max_corner, Dimension>(box)) / two;
+
+        Box lower = box, upper = box;
+        geometry::set<max_corner, Dimension>(lower, mid);
+        geometry::set<min_corner, Dimension>(upper, mid);
+
+        // Divide collection into three subsets: lower, upper and oversized (not-fitting)
+        // (lower == left or bottom, upper == right or top)
+        std::vector<dac_index> lower_index, upper_index;
+        bool has_exceeding = false;
+        for(std::vector<dac_index>::const_iterator it = boost::begin(fitting_in_quad); it != boost::end(fitting_in_quad); ++it)
+        {
+            bool const overlaps_lower = OverlapsPolicy::apply(lower, collection[it->index]);
+            bool const overlaps_upper = OverlapsPolicy::apply(upper, collection[it->index]);
+
+            if (overlaps_lower && overlaps_upper)
+            {
+                dac_index oversized = *it;
+                oversized.is_quad_exceeding = true;
+                has_exceeding = true;
+                exceeding_quad.push_back(oversized);
+            }
+            else if (overlaps_lower)
+            {
+                lower_index.push_back(*it);
+            }
+            else if (overlaps_upper)
+            {
+                upper_index.push_back(*it);
+            }
+            else
+            {
+                // Is nowhere! Should not occur!
+                BOOST_ASSERT(true);
+            }
+        }
+
+        // Recursively call operation both halves
+        if (boost::size(lower_index) > 0 || has_exceeding)
+        {
+            next_level(lower, collection, lower_index, exceeding_quad, level, min_elements, policy);
+        }
+        if (boost::size(upper_index) > 0)
+        {
+            next_level(upper, collection, upper_index, exceeding_quad, level, min_elements, policy);
+        }
+    }
+};
+}
+
+
+template
+<
+    typename Box,
+    typename ExpandPolicy,
+    typename OverlapsPolicy
+>
+struct divide_and_conquer
+{
+
+    template <typename InputCollection, typename Visitor>
+    static inline void apply(InputCollection const& collection, Visitor& visitor, int min_elements = 16)
+    {
+        std::vector<detail::dac_index> index_vector, empty;
+
+
+        // Determine total box
+        Box total;
+        assign_inverse(total);
+        int index = 0;
+        for(typename boost::range_iterator<InputCollection const>::type it
+            = boost::begin(collection);
+            it != boost::end(collection);
+            ++it, ++index)
+        {
+            ExpandPolicy::apply(total, *it);
+            index_vector.push_back(detail::dac_index(index));
+        }
+
+        // First call to recursive function
+        detail::dac_static_visitor_avoiding_duplicates<Visitor> policy(visitor);
+        detail::divide_and_conquer
+            <
+                0, Box, OverlapsPolicy
+            >::apply(total, collection, index_vector, empty, 0, min_elements, policy);
+    }
+};
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RING_IDENTIFIER_HPP

Modified: trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp	2011-03-10 16:50:35 EST (Thu, 10 Mar 2011)
@@ -10,6 +10,7 @@
 
 #include <boost/geometry/algorithms/area.hpp>
 #include <boost/geometry/algorithms/envelope.hpp>
+#include <boost/geometry/algorithms/detail/divide_and_conquer.hpp>
 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
 #include <boost/geometry/algorithms/detail/overlay/within_util.hpp>
 
@@ -30,7 +31,7 @@
     typename Geometry1, typename Geometry2,
     typename RingCollection
 >
-static inline bool within_selected_input(Item const& item2, ring_identifier ring_id, 
+static inline bool within_selected_input(Item const& item2, ring_identifier const& ring_id, 
         Geometry1 const& geometry1, Geometry2 const& geometry2,
         RingCollection const& collection)
 {
@@ -63,21 +64,92 @@
     typedef typename geometry::area_result<Point>::type area_type;
 
     ring_identifier id;
-    area_type area;
+    area_type real_area;
+    area_type abs_area;
     model::box<Point> envelope;
 
     inline ring_info_helper(ring_identifier i, area_type a)
-        : id(i), area(a)
+        : id(i), real_area(a), abs_area(abs(a))
     {}
 
-    // To be sorted decending
-    inline bool operator<(ring_info_helper<Point> const& other) const
+};
+
+
+struct ring_info_helper_get_box
+{
+    template <typename Box, typename InputItem>
+    static inline void apply(Box& total, InputItem const& item)
     {
-        return abs(this->area) > abs(other.area);
+        boost::geometry::combine(total, item.envelope);
+    }
+};
+
+struct ring_info_helper_ovelaps_box
+{
+    template <typename Box, typename InputItem>
+    static inline bool apply(Box const& box, InputItem const& item)
+    {
+        return ! boost::geometry::detail::disjoint::disjoint_box_box(box, item.envelope);
+    }
+};
+
+template <typename Geometry1, typename Geometry2, typename Collection, typename RingMap>
+struct assign_visitor
+{
+    typedef typename RingMap::mapped_type ring_info_type;
+
+    Geometry1 const& m_geometry1;
+    Geometry2 const& m_geometry2;
+    Collection const& m_collection;
+    RingMap& m_ring_map;
+    bool m_check_for_orientation;
+
+
+    inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c, 
+                RingMap& map, bool check)
+        : m_geometry1(g1)
+        , m_geometry2(g2)
+        , m_collection(c)
+        , m_ring_map(map)
+        , m_check_for_orientation(check)
+    {}
+
+    template <typename Item>
+    inline void apply(Item const& outer, Item const& inner, bool , bool , bool first = true)
+    {
+        if (first && outer.real_area < 0)
+        {
+            // Call reversed function
+            apply(inner, outer, false, false, false);
+            return;
+        }
+
+        if (outer.real_area > 0)
+        {
+            if (inner.real_area < 0 || m_check_for_orientation)
+            {
+                ring_info_type& inner_in_map = m_ring_map[inner.id];
+
+                if (geometry::within(inner_in_map.point, outer.envelope)
+                   && within_selected_input(inner_in_map, outer.id, m_geometry1, m_geometry2, m_collection)
+                   )
+                {
+                    // Only assign parent if that parent is smaller (or if it is the first)
+                    if (inner_in_map.parent.source_index == -1 
+                        || outer.abs_area < inner_in_map.parent_area)
+                    {
+                        inner_in_map.parent = outer.id;
+                        inner_in_map.parent_area = outer.abs_area;
+                    }
+                }
+            }
+        }
     }
 };
 
 
+
+
 template
 <
     typename Geometry1, typename Geometry2,
@@ -95,69 +167,128 @@
 
     typedef typename RingMap::mapped_type ring_info_type;
     typedef typename ring_info_type::point_type point_type;
+    typedef model::box<point_type> box_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;
 
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        boost::timer timer;
+#endif
+
         vector_type vector;
+        vector.reserve(ring_map.size());
+
+        int count_total = ring_map.size();
+        int count_positive = 0;
 
         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)));
+            vector.push_back(helper(it->first, it->second.get_area()));
+            helper& back = vector.back();
             switch(it->first.source_index)
             {
                 case 0 :
                     geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
-                            vector.back().envelope);
+                            back.envelope);
                     break;
                 case 1 :
                     geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
-                            vector.back().envelope);
+                            back.envelope);
                     break;
                 case 2 :
                     geometry::envelope(get_ring<void>::apply(it->first, collection),
-                            vector.back().envelope);
+                            back.envelope);
                     break;
             }
+            if (back.real_area > 0)
+            {
+                count_positive++;
+            }
         }
 
-        std::sort(vector.begin(), vector.end());
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << " ap: created helper vector: " << timer.elapsed() << std::endl;
+#endif
 
-        // 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)
+        if (count_positive == count_total && ! check_for_orientation)
         {
-            ring_info_type& outer = ring_map[out_it->id];
+            // Only positive rings, no assignment of parents or reversal necessary, ready here.
+            return;
+        }
 
-            if (outer.get_area() > 0)
+        // If there are only a few positive rings, the loop below is not quadratic and can be handled.
+        // If there are many positive rings + many negative ones, we divide and conquer.
+        if (count_positive < 5)
+        {
+            // 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.
+            int np = 0, nn = 0;
+            for (vector_iterator_type out_it = boost::begin(vector);
+                out_it != boost::end(vector); ++out_it)
             {
-                vector_iterator_type inn_it = out_it;
-                for (++inn_it; inn_it != boost::end(vector); ++inn_it)
+                if (out_it->real_area > 0)
                 {
-                    ring_info_type& inner = ring_map[inn_it->id];
-
-                    if ( (inner.get_area() < 0 || check_for_orientation)
-                        && geometry::within(inner.point, out_it->envelope)
-                        && within_selected_input(inner, out_it->id, geometry1, geometry2, collection))
+                    np++;
+                    vector_iterator_type inn_it = out_it;
+                    for (vector_iterator_type inn_it = boost::begin(vector); 
+                        inn_it != boost::end(vector); ++inn_it)
                     {
-                        inner.parent = out_it->id;
+                        // TODO: this is effectively now the same as above (in visitor), harmonize
+                        if ( (inn_it->real_area < 0 || check_for_orientation))
+                        {
+                            ring_info_type& inner = ring_map[inn_it->id];
+                            if (geometry::within(inner.point, out_it->envelope)
+                               && within_selected_input(inner, out_it->id, geometry1, geometry2, collection))
+                            {
+                                if (inner.parent.source_index == -1 || out_it->abs_area < inner.parent_area)
+                                {
+                                    inner.parent = out_it->id;
+                                    inner.parent_area = out_it->abs_area;
+                                }
+                            }
+                        }
                     }
                 }
+                else
+                {
+                    nn++;
+                }
             }
         }
+        else
+        {
+            assign_visitor<Geometry1, Geometry2, RingCollection, RingMap> 
+                        visitor(geometry1, geometry2, collection, ring_map, check_for_orientation);
+
+            geometry::divide_and_conquer
+                <
+                    box_type, ring_info_helper_get_box, ring_info_helper_ovelaps_box
+                >::apply(vector, visitor, 32);
+        }
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << " ap: quadradic loop: " << timer.elapsed() << std::endl;
+        std::cout << " ap: POS " << np << " NEG: " << nn << std::endl;
+        std::cout << " ap: check_for_orientation " << check_for_orientation << std::endl;
+#endif
     }
 
     if (check_for_orientation)
     {
         for (map_iterator_type it = boost::begin(ring_map); it != boost::end(ring_map); ++it)
         {
-            if (it->second.parent.source_index >= 0 && it->second.get_area() > 0)
+            if (geometry::math::equals(it->second.get_area(), 0))
+            {
+                it->second.discarded = true;
+            }
+            else if (it->second.parent.source_index >= 0 && it->second.get_area() > 0)
             {
                 // Discard positive inner ring with parent
                 it->second.discarded = true;

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-10 16:50:35 EST (Thu, 10 Mar 2011)
@@ -32,7 +32,8 @@
 struct get_ring
 {};
 
-// "void" is mapped to a container of rings (multi-ring but that does not exist)
+// A container of rings (multi-ring but that does not exist)
+// gets the "void" tag and is dispatched here.
 template<>
 struct get_ring<void>
 {

Modified: trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp	2011-03-10 16:50:35 EST (Thu, 10 Mar 2011)
@@ -51,9 +51,7 @@
 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
 
 #include <boost/geometry/algorithms/combine.hpp>
-#include <boost/geometry/algorithms/distance.hpp>
 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
-#include <boost/geometry/algorithms/within.hpp>
 
 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
 #  include <sstream>

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-10 16:50:35 EST (Thu, 10 Mar 2011)
@@ -8,7 +8,6 @@
 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
 
-
 #include <deque>
 #include <map>
 
@@ -20,6 +19,7 @@
 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
@@ -170,6 +170,10 @@
 
         container_type turn_points;
 
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        boost::timer timer;
+#endif
+
 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 std::cout << "get turns" << std::endl;
 #endif
@@ -180,6 +184,10 @@
                 detail::overlay::calculate_distance_policy
             >(geometry1, geometry2, turn_points, policy);
 
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << "get_turns: " << timer.elapsed() << std::endl;
+#endif
+
 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 std::cout << "enrich" << std::endl;
 #endif
@@ -191,6 +199,11 @@
                     geometry1, geometry2,
                     side_strategy);
 
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << "enrich_intersection_points: " << timer.elapsed() << std::endl;
+#endif
+
+
 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 std::cout << "traverse" << std::endl;
 #endif
@@ -204,14 +217,28 @@
                     : boost::geometry::detail::overlay::operation_intersection,
                 turn_points, rings);
 
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << "traverse: " << timer.elapsed() << std::endl;
+#endif
+
+
         std::map<ring_identifier, int> map;
         map_turns(map, turn_points);
 
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << "map_turns: " << timer.elapsed() << std::endl;
+#endif
+
         typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties;
 
         std::map<ring_identifier, properties> selected;
         select_rings<Direction>(geometry1, geometry2, map, selected);
 
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << "select_rings: " << timer.elapsed() << std::endl;
+#endif
+
+
         // Add rings created during traversal
         {
             ring_identifier id(2, 0, -1);
@@ -226,7 +253,17 @@
             }
         }
 
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << "add traversal rings: " << timer.elapsed() << std::endl;
+#endif
+
+
         assign_parents(geometry1, geometry2, rings, selected);
+
+#ifdef BOOST_GEOMETRY_TIME_OVERLAY
+        std::cout << "assign_parents: " << timer.elapsed() << std::endl;
+#endif
+
         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-10 16:50:35 EST (Thu, 10 Mar 2011)
@@ -38,6 +38,7 @@
 
     // Filled/used by "assign_rings"
     ring_identifier parent;
+    area_type parent_area;
     std::vector<ring_identifier> children;
 
     inline ring_properties()
@@ -45,6 +46,7 @@
         , within_code(-1)
         , reversed(false)
         , discarded(false)
+        , parent_area(-1)
     {}
 
     template <typename RingOrBox>
@@ -52,6 +54,7 @@
         : within_code(-1)
         , reversed(false)
         , discarded(false)
+        , parent_area(-1)
     {
         this->area = geometry::area(ring_or_box);
         geometry::point_on_border(this->point, ring_or_box, true);
@@ -61,6 +64,7 @@
     inline ring_properties(RingOrBox const& ring_or_box, Geometry const& geometry)
         : reversed(false)
         , discarded(false)
+        , parent_area(-1)
     {
         this->area = geometry::area(ring_or_box);
         geometry::point_on_border(this->point, ring_or_box, true);

Modified: trunk/boost/geometry/algorithms/intersection_inserter.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/intersection_inserter.hpp	(original)
+++ trunk/boost/geometry/algorithms/intersection_inserter.hpp	2011-03-10 16:50:35 EST (Thu, 10 Mar 2011)
@@ -25,6 +25,7 @@
 #include <boost/geometry/algorithms/detail/overlay/clip_linestring.hpp>
 #include <boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp>
 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
+#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
 #include <boost/geometry/ranges/segment_range.hpp>
 
 

Deleted: trunk/boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp
==============================================================================
--- trunk/boost/geometry/multi/algorithms/detail/overlay/add_to_containment.hpp	2011-03-10 16:50:35 EST (Thu, 10 Mar 2011)
+++ (empty file)
@@ -1 +0,0 @@
-//obsolete
\ No newline at end of file