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>