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