Subject: [Boost-commit] svn:boost r59684 - in sandbox/geometry/boost/geometry: algorithms algorithms/detail algorithms/detail/overlay algorithms/overlay multi multi/algorithms/overlay
From: barend.gehrels_at_[hidden]
Date: 2010-02-14 16:51:11
Author: barendgehrels
Date: 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
New Revision: 59684
URL: http://svn.boost.org/trac/boost/changeset/59684
Log:
Replaced "return_if_found" by InterruptPolicy
Removed:
sandbox/geometry/boost/geometry/algorithms/overlay/get_intersection_points.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/intersection_point.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/self_intersection_points.hpp
sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_intersection_points.hpp
Text files modified:
sandbox/geometry/boost/geometry/algorithms/detail/disjoint.hpp | 2
sandbox/geometry/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp | 8
sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp | 6
sandbox/geometry/boost/geometry/algorithms/disjoint.hpp | 45 ++++
sandbox/geometry/boost/geometry/algorithms/equals.hpp | 117 ++++++++-----
sandbox/geometry/boost/geometry/algorithms/intersection.hpp | 20 -
sandbox/geometry/boost/geometry/algorithms/intersects.hpp | 38 ++--
sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp | 33 +-
sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp | 2
sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp | 2
sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp | 12
sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp | 345 ++++++++++++++++++---------------------
sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp | 98 ++++++-----
sandbox/geometry/boost/geometry/algorithms/union.hpp | 9
sandbox/geometry/boost/geometry/algorithms/within.hpp | 1
sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp | 2
sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp | 21 +-
sandbox/geometry/boost/geometry/multi/multi.hpp | 1
18 files changed, 398 insertions(+), 364 deletions(-)
Modified: sandbox/geometry/boost/geometry/algorithms/detail/disjoint.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/disjoint.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/disjoint.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -11,7 +11,7 @@
// Note: contrary to most files, the geometry::detail::disjoint namespace
// is partly implemented in a separate file, to avoid circular references
-// disjoint -> get_intersection_points -> disjoint
+// disjoint -> get_turns -> disjoint
#include <boost/geometry/core/access.hpp>
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -26,13 +26,15 @@
extra information.
This policy calculates the distance (using default distance strategy)
*/
-struct CalculateDistancePolicy
+struct calculate_distance_policy
{
template <typename Point1, typename Point2, typename Info>
static inline void apply(Info& info, Point1 const& p1, Point2 const& p2)
{
- info.operations[0].enriched.distance = boost::geometry::distance(info.point, p1);
- info.operations[1].enriched.distance = boost::geometry::distance(info.point, p2);
+ info.operations[0].enriched.distance
+ = boost::geometry::distance(info.point, p1);
+ info.operations[1].enriched.distance
+ = boost::geometry::distance(info.point, p2);
}
};
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -674,11 +674,11 @@
/*!
\brief Policy doing nothing
- \details get_turn_info can have an optional policy to get some
+ \details get_turn_info can have an optional policy to get/assign some
extra information. By default it does not, and this class
is that default.
*/
-struct NullPolicy
+struct assign_null_policy
{
template <typename Point1, typename Point2, typename Info>
static inline void apply(Info& info, Point1 const& p1, Point2 const& p2)
@@ -704,7 +704,7 @@
typename Point1,
typename Point2,
typename TurnInfo,
- typename AssignPolicy = NullPolicy
+ typename AssignPolicy = assign_null_policy
>
struct get_turn_info
{
Modified: sandbox/geometry/boost/geometry/algorithms/disjoint.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/disjoint.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/disjoint.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -41,7 +41,7 @@
#include <boost/geometry/algorithms/detail/disjoint.hpp>
#include <boost/geometry/algorithms/detail/point_on_border.hpp>
-#include <boost/geometry/algorithms/overlay/get_intersection_points.hpp>
+#include <boost/geometry/algorithms/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
@@ -55,7 +55,31 @@
#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace disjoint {
+namespace detail { namespace disjoint
+{
+
+
+struct disjoint_interrupt_policy
+{
+ static bool const enabled = true;
+ bool has_intersections;
+
+ inline disjoint_interrupt_policy()
+ : has_intersections(false)
+ {}
+
+ template <typename Range>
+ inline bool apply(Range const& range)
+ {
+ // If there is any IP in the range, it is NOT disjoint
+ if (boost::size(range) > 0)
+ {
+ has_intersections = true;
+ return true;
+ }
+ return false;
+ }
+};
template <typename Geometry1, typename Geometry2>
@@ -63,17 +87,22 @@
{
static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
{
-
typedef typename geometry::point_type<Geometry1>::type point_type;
- typedef detail::intersection::intersection_point<point_type> ip_type;
- std::deque<ip_type> ips; // intersection points
- // Get any intersection
- geometry::get_intersection_points(geometry1, geometry2, ips);
- if (ips.size() > 0)
+ typedef overlay::turn_info<point_type> turn_info;
+ std::deque<turn_info> turns;
+
+ // Get (and stop on) any intersection
+ disjoint_interrupt_policy policy;
+ geometry::get_turns
+ <
+ overlay::assign_null_policy
+ >(geometry1, geometry2, turns, policy);
+ if (policy.has_intersections)
{
return false;
}
+
// If there is no intersection of segments, they might located
// inside each other
point_type p1;
Modified: sandbox/geometry/boost/geometry/algorithms/equals.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/equals.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/equals.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -58,7 +58,8 @@
{
#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace equals {
+namespace detail { namespace equals
+{
template
@@ -90,10 +91,66 @@
}
};
+struct equals_interrupt_policy
+{
+ static bool const enabled = true;
+
+ // As soon as a turn is detected, this flag is set to true
+ // and the process of getting turns (intersection points)
+ // is interrupted
+ bool turns_inside_or_outside;
+
+ inline equals_interrupt_policy()
+ : turns_inside_or_outside(false)
+ {}
+
+ template <typename Range>
+ inline bool apply(Range const& range)
+ {
+ for (typename boost::range_iterator<Range const>::type
+ it = boost::begin(range);
+ it != boost::end(range);
+ ++it)
+ {
+ if (it->method == detail::overlay::method_collinear
+ || it->method == detail::overlay::method_equal
+ )
+ {
+ typedef typename boost::range_value<Range>::type turn_type;
+ // If it is not such that both turns are collinear, the rings are not equal
+ for (typename boost::range_iterator
+ <
+ typename turn_type::container_type const
+ >::type oit = boost::begin(it->operations);
+ oit != boost::end(it->operations);
+ oit++)
+ {
+ if (oit->operation != detail::overlay::operation_continue)
+ {
+ turns_inside_or_outside = true;
+ return true;
+ }
+ }
+ }
+ else
+ {
+ turns_inside_or_outside = true;
+ return true;
+ }
+ }
+ // It is not yet known, so don't interrupt
+ return false;
+ }
+
+};
+
+
template <typename Ring1, typename Ring2>
struct ring_ring
{
+
+
static inline bool apply(Ring1 const& ring1, Ring2 const& ring2, bool check_area = true)
{
// Note: this implementation makes use of getting interections (turns)
@@ -115,45 +172,17 @@
typedef typename geometry::point_type<Ring1>::type point_type;
typedef detail::overlay::traversal_turn_info<point_type> turn_info;
- typedef std::deque<turn_info> container_type;
+ std::vector<turn_info> turns;
- container_type ips;
- boost::geometry::get_turns<detail::overlay::NullPolicy>(ring1, ring2, ips);
+ equals_interrupt_policy policy;
- if (ips.size() == 0)
- {
- return false;
- }
- for (typename boost::range_iterator<container_type const>::type
- it = boost::begin(ips);
- it != boost::end(ips);
- ++it)
- {
- if (it->method == detail::overlay::method_collinear
- || it->method == detail::overlay::method_equal
- )
- {
- // If it is not such that both turns are collinear, the rings are not equal
- for (typename boost::range_iterator
- <
- typename turn_info::container_type const
- >::type oit = boost::begin(it->operations);
- oit != boost::end(it->operations);
- oit++)
- {
- if (oit->operation != detail::overlay::operation_continue)
- {
- return false;
- }
- }
- }
- else
- {
- return false;
- }
- }
+ boost::geometry::get_turns
+ <
+ detail::overlay::assign_null_policy
+ >(ring1, ring2, turns, policy);
- return true;
+ return turns.size() > 0
+ && ! policy.turns_inside_or_outside;
}
};
@@ -183,7 +212,7 @@
{
typedef typename boost::range_value<Collection>::type item_type;
int i = 0;
- for (typename boost::range_iterator<Range const>::type
+ for (typename boost::range_iterator<Range const>::type
it = boost::begin(range);
it != boost::end(range);
++it, ++i)
@@ -202,10 +231,10 @@
}
-template
+template
<
typename Policy,
- typename Range1,
+ typename Range1,
typename Range2
>
inline bool range_range(Range1 const& range1, Range2 const& range2)
@@ -217,7 +246,7 @@
<
equal_sortable<typename geometry::area_result<geometry1>::type>
> collection;
-
+
collection sorted1, sorted2;
fill_equal_sortable(range1, sorted1);
@@ -258,7 +287,7 @@
template <typename Polygon1, typename Polygon2>
struct polygon_polygon
{
- static inline bool apply(Polygon1 const& polygon1, Polygon2 const& polygon2,
+ static inline bool apply(Polygon1 const& polygon1, Polygon2 const& polygon2,
bool compare_area = false)
{
// Check number of rings (area check is done in exterior ring check)
@@ -278,7 +307,7 @@
}
return range_range<compare>(
- interior_rings(polygon1),
+ interior_rings(polygon1),
interior_rings(polygon2));
}
@@ -361,7 +390,7 @@
<
typename Tag1, typename Tag2,
bool IsMulti1, bool IsMulti2,
- typename Geometry1,
+ typename Geometry1,
typename Geometry2,
std::size_t DimensionCount
>
Modified: sandbox/geometry/boost/geometry/algorithms/intersection.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/intersection.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/intersection.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -281,15 +281,12 @@
concept::check<Geometry1 const>();
concept::check<Geometry2 const>();
- typedef typename geometry::point_type<GeometryOut>::type point_type;
- typedef detail::intersection::intersection_point<point_type> ip_type;
-
typedef strategy_intersection
<
- typename cs_tag<point_type>::type,
+ typename cs_tag<GeometryOut>::type,
Geometry1,
Geometry2,
- ip_type
+ typename geometry::point_type<GeometryOut>::type
> strategy;
return intersection_inserter<GeometryOut>(geometry1, geometry2, out,
@@ -327,20 +324,17 @@
typedef typename boost::range_value<Collection>::type geometry_out;
concept::check<geometry_out>();
- typedef typename geometry::point_type<geometry_out>::type point_type;
- typedef detail::intersection::intersection_point<point_type> ip_type;
-
typedef strategy_intersection
<
- typename cs_tag<point_type>::type,
+ typename cs_tag<geometry_out>::type,
Geometry1,
Geometry2,
- ip_type
+ typename geometry::point_type<geometry_out>::type
> strategy;
- intersection_inserter<geometry_out>(geometry1, geometry2,
- std::back_inserter(output_collection),
+ intersection_inserter<geometry_out>(geometry1, geometry2,
+ std::back_inserter(output_collection),
strategy());
}
@@ -348,4 +342,4 @@
}} // namespace boost::geometry
-#endif //GGL_ALGORITHMS_INTERSECTION_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_INTERSECTION_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/intersects.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/intersects.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/intersects.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -33,10 +33,7 @@
#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/algorithms/overlay/get_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/self_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/enrich_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/traverse.hpp>
+#include <boost/geometry/algorithms/overlay/self_turn_points.hpp>
#include <boost/geometry/algorithms/disjoint.hpp>
@@ -58,32 +55,33 @@
template <typename Geometry>
inline bool intersects(Geometry const& geometry)
{
- concept::check<const Geometry>();
+ concept::check<Geometry const>();
- typedef typename boost::remove_const<Geometry>::type ncg_type;
- typedef geometry::detail::intersection::intersection_point
- <typename geometry::point_type<Geometry>::type> ip;
- typedef std::vector<ip> ip_vector;
-
- ip_vector ips;
+ typedef detail::overlay::turn_info
+ <
+ typename geometry::point_type<Geometry>::type
+ > turn_info;
+ std::deque<turn_info> turns;
typedef typename strategy_intersection
<
typename cs_tag<Geometry>::type,
Geometry,
Geometry,
- ip
+ typename geometry::point_type<Geometry>::type
>::segment_intersection_strategy_type segment_intersection_strategy_type;
- dispatch::self_intersection_points
+ detail::disjoint::disjoint_interrupt_policy policy;
+ detail::self_get_turn_points::get_turns
<
- typename tag<ncg_type>::type,
- is_multi<ncg_type>::type::value,
- ncg_type,
- ip_vector, segment_intersection_strategy_type
- >::apply(geometry, true, ips);
- return ips.size() > 0;
+ Geometry,
+ std::deque<turn_info>,
+ segment_intersection_strategy_type,
+ detail::overlay::assign_null_policy,
+ detail::disjoint::disjoint_interrupt_policy
+ >::apply(geometry, turns, policy);
+ return policy.has_intersections;
}
@@ -109,4 +107,4 @@
}} // namespace boost::geometry
-#endif //GGL_ALGORITHMS_INTERSECTS_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_INTERSECTS_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -45,8 +45,8 @@
#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay {
-
+namespace detail { namespace overlay
+{
template<typename Tag>
@@ -611,7 +611,7 @@
typename OutputIterator
>
inline OutputIterator assemble(Rings const& rings, Turns& turn_points,
- Geometry1 const& geometry1,
+ Geometry1 const& geometry1,
Geometry2 const& geometry2,
int direction, bool dissolve,
OutputIterator out)
@@ -642,7 +642,7 @@
tag1,
Geometry1
>::apply(ring_properties_container,
- ring_identifier(0, -1,-1), geometry1,
+ ring_identifier(0, -1,-1), geometry1,
map, dissolve);
if (! dissolve)
{
@@ -651,7 +651,7 @@
tag2,
Geometry2
>::apply(ring_properties_container,
- ring_identifier(1, -1,-1), geometry2,
+ ring_identifier(1, -1,-1), geometry2,
map, dissolve);
}
@@ -726,11 +726,11 @@
std::cout << "assemble.properties sort on parent-id "
<< boost::size(ring_properties_container) << std::endl;
#endif
- std::sort(boost::begin(ring_properties_container),
+ std::sort(boost::begin(ring_properties_container),
boost::end(ring_properties_container),
sort_on_id_or_parent_id
<
- ring_properties<point_type>
+ ring_properties<point_type>
>(direction));
}
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
@@ -751,7 +751,7 @@
struct overlay
{
static inline OutputIterator apply(
- Geometry1 const& geometry1, Geometry2 const& geometry2,
+ Geometry1 const& geometry1, Geometry2 const& geometry2,
OutputIterator out,
Strategy const& strategy)
{
@@ -764,8 +764,8 @@
typedef detail::overlay::traversal_turn_info<point_type> turn_info;
typedef std::deque<turn_info> container_type;
- // "Use" rangetype for ringtype:
- // for polygon, it is the type of the exterior ring.
+ // "Use" rangetype for ringtype:
+ // for polygon, it is the type of the exterior ring.
// for ring, it is the ring itself. That is what is
// for multi-polygon, it is also the type of the ring.
typedef typename geometry::range_type<GeometryOut>::type ring_type;
@@ -773,14 +773,14 @@
container_type turn_points;
std::vector<ring_type> rings;
- // If one input is empty, output the other one for a union.
+ // If one input is empty, output the other one for a union.
// For an intersection, the intersection is empty.
- if (geometry::num_points(geometry1) == 0
+ if (geometry::num_points(geometry1) == 0
|| geometry::num_points(geometry2) == 0)
{
if (Direction == 1)
{
- return assemble<GeometryOut>(rings, turn_points,
+ return assemble<GeometryOut>(rings, turn_points,
geometry1, geometry2, Direction, false, out);
}
return out;
@@ -789,10 +789,11 @@
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "get turns" << std::endl;
#endif
+ detail::get_turns::no_interrupt_policy policy;
boost::geometry::get_turns
<
- detail::overlay::CalculateDistancePolicy
- >(geometry1, geometry2, turn_points);
+ detail::overlay::calculate_distance_policy
+ >(geometry1, geometry2, turn_points, policy);
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "enrich" << std::endl;
@@ -811,7 +812,7 @@
,
turn_points, rings);
- return assemble<GeometryOut>(rings, turn_points,
+ return assemble<GeometryOut>(rings, turn_points,
geometry1, geometry2, Direction, false, out);
}
};
Modified: sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -16,8 +16,6 @@
#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/algorithms/overlay/intersection_point.hpp>
-
#include <boost/geometry/iterators/ever_circling_iterator.hpp>
#include <boost/geometry/iterators/range_type.hpp>
Modified: sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -19,8 +19,6 @@
#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/algorithms/overlay/intersection_point.hpp>
-
#include <boost/geometry/iterators/ever_circling_iterator.hpp>
#include <boost/geometry/iterators/range_type.hpp>
Modified: sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -178,7 +178,7 @@
Geometry1, Geometry2, Strategy
>
{
- sort_on_segment_and_distance(Geometry1 const& geometry1,
+ sort_on_segment_and_distance(Geometry1 const& geometry1,
Geometry2 const& geometry2,
Strategy const& strategy)
: sort_on_distance
@@ -291,10 +291,10 @@
operation_type& op = turn_points[it->index]
.operations[it->operation_index];
if ((prev_op.seg_id == op.seg_id || prev_op.other_id == op.other_id)
- && geometry::math::equals(prev_op.enriched.distance,
+ && geometry::math::equals(prev_op.enriched.distance,
op.enriched.distance))
{
- std::cout << "Equal Distance on "
+ std::cout << "Equal Distance on "
<< " : " << prev_op.seg_id << " / " << prev_op.other_id
<< " and " << op.seg_id << " / " << op.other_id
<< std::endl;
@@ -305,7 +305,7 @@
if (swap_operations
<
- typename point_type<Geometry1>::type
+ typename point_type<Geometry1>::type
>(prev_op, op, geometry1, geometry2))
{
std::cout << "Should be swapped" << std::endl;
@@ -358,7 +358,7 @@
\brief All intersection points are enriched with successor information
\ingroup overlay
\tparam TurnPoints type of intersection container
- (e.g. vector of "intersection_point"'s)
+ (e.g. vector of "intersection/turn point"'s)
\param turn_points container containing intersectionpoints
*/
template
@@ -414,7 +414,7 @@
}
}
- // Note: no const-operator because contents of mapped copy is temporary,
+ // Note: no const-operator because contents of mapped copy is temporary,
// and changed by enrich)
for (typename mapped_vector_type::iterator mit
= mapped_vector.begin();
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/get_intersection_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/get_intersection_points.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
+++ (empty file)
@@ -1,981 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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_OVERLAY_GET_INTERSECTION_POINTS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_GET_INTERSECTION_POINTS_HPP
-
-/*!
-\defgroup overlay overlay helper operations (getting intersection points, etc)
-*/
-
-
-#include <cstddef>
-#include <map>
-
-#include <boost/mpl/if.hpp>
-#include <boost/range/functions.hpp>
-#include <boost/range/metafunctions.hpp>
-#include <boost/tuple/tuple.hpp>
-#include <boost/type_traits/remove_const.hpp>
-
-#include <boost/geometry/core/access.hpp>
-#include <boost/geometry/core/coordinate_dimension.hpp>
-#include <boost/geometry/core/is_multi.hpp>
-#include <boost/geometry/core/reverse_dispatch.hpp>
-
-#include <boost/geometry/core/exterior_ring.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
-#include <boost/geometry/core/ring_type.hpp>
-
-#include <boost/geometry/geometries/concepts/check.hpp>
-
-#include <boost/geometry/util/math.hpp>
-
-#include <boost/geometry/geometries/box.hpp>
-
-#include <boost/geometry/iterators/range_type.hpp>
-
-#include <boost/geometry/strategies/cartesian/cart_intersect.hpp>
-#include <boost/geometry/strategies/intersection.hpp>
-#include <boost/geometry/strategies/intersection_result.hpp>
-
-
-#include <boost/geometry/algorithms/overlay/intersection_point.hpp>
-
-#include <boost/geometry/algorithms/detail/disjoint.hpp>
-
-#include <boost/geometry/algorithms/combine.hpp>
-#include <boost/geometry/algorithms/distance.hpp>
-#include <boost/geometry/algorithms/sectionalize.hpp>
-#include <boost/geometry/algorithms/get_section.hpp>
-#include <boost/geometry/algorithms/within.hpp>
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
-# include <sstream>
-# include <boost/geometry/util/write_dsv.hpp>
-#endif
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace get_intersection_points {
-
-
-template
-<
- typename Segment1,
- typename Segment2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct relate
-{
-private :
- template <typename Segment, typename Point>
- static inline void copy_point(int how, Segment const& segment, Point& point)
- {
- if (how == 1)
- {
- // Arrival
- geometry::copy_coordinates(segment.first, point);
- }
- else
- {
- // Departure
- geometry::copy_coordinates(segment.second, point);
- }
- }
-
- template <typename Info, typename IntersectionPoint, typename Direction, typename Segment>
- static inline void process_one(
- Info& info,
- IntersectionPoint const& ipoint,
- Segment const& segment,
- segment_identifier const& seg_id_first,
- segment_identifier const& seg_id_second,
- Direction const& dir, int arrival, int direction, bool reverse)
- {
- info.how = dir.how;
- info.opposite = dir.opposite;
-
- info.seg_id = seg_id_first;
- info.other_id = seg_id_second;
- copy_point(arrival, segment, info.other_point);
-
- info.distance = geometry::distance(ipoint, segment.first);
-
- info.arrival = arrival;
- info.direction = direction;
- info.sides = dir.sides;
-
- // Seen from B, the first one is B, the second one is A
- if (reverse)
- {
- info.sides.reverse();
- }
- }
-
-
- template <typename IntersectionPoint, typename Direction>
- static inline void process(IntersectionPoint& ipoint,
- Direction const& dir,
- Segment1 const& s1, Segment2 const& s2,
- segment_identifier const& seg_id1,
- segment_identifier const& seg_id2,
- IntersectionPoints& out, bool& trivial)
- {
- typedef typename boost::range_value
- <
- IntersectionPoints
- >::type intersection_point;
-
- typename intersection_point::traversal_type info;
-
- ipoint.info.resize(ipoint.info.size() + 1);
- process_one(ipoint.info.back(), ipoint,
- s1, seg_id1, seg_id2,
- dir, dir.how_a, dir.dir_a, false);
-
- ipoint.info.resize(ipoint.info.size() + 1);
- process_one(ipoint.info.back(), ipoint,
- s2, seg_id2, seg_id1,
- dir, dir.how_b, dir.dir_b, true);
-
-
- if (dir.how != 'i')
- {
- trivial = false;
- ipoint.trivial = false;
- }
-
- out.push_back(ipoint);
- }
-
-
-
-public :
- static inline bool apply(Segment1 const& s1, Segment2 const& s2,
- segment_identifier const& seg_id1,
- segment_identifier const& seg_id2,
- IntersectionPoints& out, bool& trivial)
- {
- typename IntersectionStrategy::return_type result
- = IntersectionStrategy::apply(s1, s2);
-
- for (std::size_t i = 0; i < result.get<0>().count; i++)
- {
- process(
- // Process the tupled result value
- result.get<0>().intersections[i],
- result.get<1>(),
- s1, s2, seg_id1, seg_id2,
- out, trivial);
- }
- return result.get<0>().count > 0;
- }
-};
-
-template
-<
- typename Geometry1, typename Geometry2,
- typename Section1, typename Section2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-class get_ips_in_sections
-{
-public :
- static inline void apply(
- std::size_t source_id1, Geometry1 const& geometry1,
- Section1 const& sec1,
- std::size_t source_id2, Geometry2 const& geometry2,
- Section2 const& sec2,
- bool return_if_found,
- IntersectionPoints& intersection_points,
- bool& trivial)
- {
-
- typedef typename boost::range_const_iterator
- <
- typename geometry::range_type<Geometry1>::type
- >::type range1_iterator;
- typedef typename boost::range_const_iterator
- <
- typename geometry::range_type<Geometry2>::type
- >::type range2_iterator;
-
- int const dir1 = sec1.directions[0];
- int const dir2 = sec2.directions[0];
- int index1 = sec1.begin_index;
- int ndi1 = sec1.non_duplicate_index;
-
- bool const same_source =
- source_id1 == source_id2
- && sec1.multi_index == sec2.multi_index
- && sec1.ring_index == sec2.ring_index;
-
- // Note that it is NOT possible to have section-iterators here
- // because of the logistics of "index" (the section-iterator automatically
- // skips to the begin-point, we loose the index or have to recalculate it)
- // So we mimic it here
- range1_iterator it1, end1;
- get_section(geometry1, sec1, it1, end1);
-
- // Mimic 1: Skip to point such that section interects other box
- range1_iterator prev1 = it1++;
- for(; it1 != end1 && preceding<0>(dir1, *it1, sec2.bounding_box);
- prev1 = it1++, index1++, ndi1++)
- {
- }
- // Go back one step because we want to start completely preceding
- it1 = prev1;
-
- // Walk through section and stop if we exceed the other box
- for (prev1 = it1++;
- it1 != end1 && ! exceeding<0>(dir1, *prev1, sec2.bounding_box);
- prev1 = it1++, index1++, ndi1++)
- {
- segment1_type s1(*prev1, *it1);
-
- int index2 = sec2.begin_index;
- int ndi2 = sec2.non_duplicate_index;
-
- range2_iterator it2, end2;
- get_section(geometry2, sec2, it2, end2);
-
- range2_iterator prev2 = it2++;
-
- // Mimic 2:
- for(; it2 != end2 && preceding<0>(dir2, *it2, sec1.bounding_box);
- prev2 = it2++, index2++, ndi2++)
- {
- }
- it2 = prev2;
-
- for (prev2 = it2++;
- it2 != end2 && ! exceeding<0>(dir2, *prev2, sec1.bounding_box);
- prev2 = it2++, index2++, ndi2++)
- {
- bool skip = same_source;
- if (skip)
- {
- // If sources are the same (possibly self-intersecting):
- // check if it is a neighbouring sement.
- // (including first-last segment
- // and two segments with one or more degenerate/duplicate
- // (zero-length) segments in between)
-
- // Also skip if index1 < index2 to avoid getting all
- // intersections twice (only do this on same source!)
-
- // About n-2:
- // (square: range_count=5, indices 0,1,2,3
- // -> 0-3 are adjacent)
- skip = index2 >= index1
- || ndi1 == ndi2 + 1
- || (index2 == 0 && index1 >= int(sec1.range_count) - 2)
- ;
- }
-
- if (! skip)
- {
- if (relate<segment1_type, segment2_type, IntersectionPoints, IntersectionStrategy>
- ::apply(s1, segment2_type(*prev2, *it2),
- segment_identifier(source_id1,
- sec1.multi_index, sec1.ring_index, index1),
- segment_identifier(source_id2,
- sec2.multi_index, sec2.ring_index, index2),
- intersection_points, trivial)
- && return_if_found)
- {
- return;
- }
- }
- }
- }
- }
-
-
-private :
- typedef typename geometry::point_type<Geometry1>::type point1_type;
- typedef typename geometry::point_type<Geometry2>::type point2_type;
- typedef typename geometry::segment<const point1_type> segment1_type;
- typedef typename geometry::segment<const point2_type> segment2_type;
-
-
- template <size_t Dim, typename Point, typename Box>
- static inline bool preceding(int dir, Point const& point, Box const& box)
- {
- return (dir == 1 && get<Dim>(point) < get<min_corner, Dim>(box))
- || (dir == -1 && get<Dim>(point) > get<max_corner, Dim>(box));
- }
-
- template <size_t Dim, typename Point, typename Box>
- static inline bool exceeding(int dir, Point const& point, Box const& box)
- {
- return (dir == 1 && get<Dim>(point) > get<max_corner, Dim>(box))
- || (dir == -1 && get<Dim>(point) < get<min_corner, Dim>(box));
- }
-
-
-};
-
-
-template
-<
- typename Ring, typename Box,
- typename Section1, typename Section2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-class get_ips_range_box
-{
-public :
- static inline void apply(
- std::size_t source_id1, Ring const& ring,
- std::size_t source_id2, Box const& box,
- Section1 const& sec1, Section2 const& sec2,
- IntersectionPoints& intersection_points, bool& trivial)
- {
- get_ips_in_sections<Ring, Box, Section1, Section2, IntersectionPoints, IntersectionStrategy>
- ::apply(
- source_id1, ring, sec1,
- source_id2, box, sec2,
- false,
- intersection_points, trivial);
- }
-};
-
-template <typename Section, int Dimension, int Index>
-struct compare_section
-{
- inline bool operator()(Section const& left, Section const& right) const
- {
- return
- geometry::get<Index, Dimension>(left.bounding_box)
- < geometry::get<Index, Dimension>(right.bounding_box);
- }
-};
-
-
-
-template
-<
- typename Geometry1,
- typename Geometry2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-class get_ips_generic
-{
- template <typename Box, typename Sections>
- static inline void add_sections(Box& box, Sections const& sections)
- {
- for (typename boost::range_iterator<const Sections>::type
- it = sections.begin();
- it != sections.end();
- ++it)
- {
- geometry::combine(box, it->bounding_box);
- }
- }
-
- template <typename Sections, typename Box>
- static inline void get_sections(Sections const& sections,
- Box const& box, Sections& selection)
- {
- for (typename boost::range_iterator<const Sections>::type
- it = sections.begin();
- it != sections.end();
- ++it)
- {
- if (! geometry::detail::disjoint::disjoint_box_box(box, it->bounding_box))
- {
- selection.push_back(*it);
- }
- }
- }
-
- template <typename Sections1, typename Sections2, typename Map>
- static inline void intersect(
- std::size_t source_id1, Geometry1 const& geometry1,
- std::size_t source_id2, Geometry2 const& geometry2,
- IntersectionPoints& intersection_points,
- Sections1 const& sec1, Sections2 const& sec2,
- Map& map,
- bool &trivial)
- {
- for (typename boost::range_const_iterator<Sections1>::type
- it1 = sec1.begin();
- it1 != sec1.end();
- ++it1)
- {
- for (typename boost::range_const_iterator<Sections2>::type
- it2 = sec2.begin();
- it2 != sec2.end();
- ++it2)
- {
- std::pair<int, int> p = std::make_pair(it1->id, it2->id);
- bool processed = map[p];
- if (! processed)
- {
- map[p] = true;
- if (! geometry::detail::disjoint::disjoint_box_box(
- it1->bounding_box, it2->bounding_box))
- {
- get_ips_in_sections
- <
- Geometry1,
- Geometry2,
- typename boost::range_value<Sections1>::type,
- typename boost::range_value<Sections2>::type,
- IntersectionPoints,
- IntersectionStrategy
- >::apply(
- source_id1, geometry1, *it1,
- source_id2, geometry2, *it2,
- false,
- intersection_points, trivial);
- }
- }
- }
- }
- }
-
-
- // Divide and conquer (suggested by Luke during GGL Formal Review)
- template
- <
- std::size_t Dimension,
- typename Box,
- typename Sections1, typename Sections2,
- typename Map
- >
- static inline void divide_and_conquer(
- std::size_t source_id1, Geometry1 const& geometry1,
- std::size_t source_id2, Geometry2 const& geometry2,
- IntersectionPoints& intersection_points,
-
- Box const& box,
- Sections1 const& sec1, Sections2 const& sec2,
- Map& map,
- bool &trivial,
- std::size_t iteration = 0, std::size_t previous_count = 0)
- {
- // To stop the iteration, fallback to (quadratic) behaviour below certain limits,
- // or if dividing does not give any profit.
- std::size_t n = sec1.size() + sec2.size();
- if (sec1.size() < 5
- || sec2.size() < 5
- || n == previous_count
- || iteration > 100)
- {
- intersect(source_id1, geometry1, source_id2, geometry2,
- intersection_points, sec1, sec2, map, trivial);
- return;
- }
-
- // Divide the complete box in two (alternating) halves
- Box lower = box, upper = box;
- typename geometry::coordinate_type<Box>::type two = 2.0;
- typename geometry::coordinate_type<Box>::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);
-
- Sections1 lower1, upper1;
- Sections2 lower2, upper2;
- get_sections(sec1, lower, lower1);
- get_sections(sec2, lower, lower2);
- get_sections(sec1, upper, upper1);
- get_sections(sec2, upper, upper2);
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION_DIVIDE_AND_CONQUER
- std::cout
- << "Get IP's, iteration: " << iteration
- << " box: " << geometry::dsv(box)
- << " n: " << n
- << " lower: " << lower1.size() << " , " << lower2.size()
- << " upper: " << upper1.size() << " , " << upper2.size()
- << std::endl;
-#endif
-
- // Recursively handle lower and upper half, dividing in other dimension
- divide_and_conquer<1 - Dimension>(source_id1, geometry1,
- source_id2, geometry2, intersection_points,
- lower, lower1, lower2, map, trivial, iteration + 1, n);
-
- divide_and_conquer<1 - Dimension>(source_id1, geometry1,
- source_id2, geometry2, intersection_points,
- upper, upper1, upper2, map, trivial, iteration + 1, n);
- }
-
-public:
- static inline bool apply(
- std::size_t source_id1, Geometry1 const& geometry1,
- std::size_t source_id2, Geometry2 const& geometry2,
- IntersectionPoints& intersection_points)
- {
- // Create monotonic sections in ONE direction
- // - in most cases ONE direction is faster (e.g. ~1% faster for the NLP4 testset)
- // - the sections now have a limit (default 10) so will not be too large
-
- // Note that the sections contain boxes, are dynamic, and therefore
- // are specified using output/intersection-point-type
- // (to enable input-pointer-point-types)
- typedef typename boost::range_value<IntersectionPoints>::type ip_type;
- typedef typename ip_type::point_type point_type;
- typedef typename geometry::sections<geometry::box<point_type>, 1> sections1_type;
- typedef typename geometry::sections<geometry::box<point_type>, 1> sections2_type;
-
- sections1_type sec1;
- sections2_type sec2;
-
- geometry::sectionalize(geometry1, sec1);
- geometry::sectionalize(geometry2, sec2);
-
- // Divide and conquer
- geometry::box<point_type> box;
- geometry::assign_inverse(box);
- add_sections(box, sec1);
- add_sections(box, sec2);
-
- // House-keeping map, to avoid section-pairs being compared twice
- std::map<std::pair<int, int>, bool> map;
-
- bool trivial = true;
- divide_and_conquer<1>(source_id1, geometry1, source_id2, geometry2,
- intersection_points, box, sec1, sec2, map, trivial);
- return trivial;
- }
-};
-
-
-
-template
-<
- typename Range,
- typename Box,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct get_ips_cs
-{
- static inline void apply(std::size_t source_id1, Range const& range,
- int multi_index, int ring_index,
- std::size_t source_id2, Box const& box,
- IntersectionPoints& intersection_points,
- bool& trivial)
- {
- if (boost::size(range) <= 1)
- {
- return;
- }
-
-
- typedef typename geometry::point_type<Box>::type box_point_type;
- typedef typename geometry::point_type<Range>::type point_type;
-
- typedef segment<const box_point_type> box_segment_type;
- typedef segment<const point_type> segment_type;
-
- point_type lower_left, upper_left, lower_right, upper_right;
- assign_box_corners(box, lower_left, lower_right, upper_left, upper_right);
-
- box_segment_type left(lower_left, upper_left);
- box_segment_type top(upper_left, upper_right);
- box_segment_type right(upper_right, lower_right);
- box_segment_type bottom(lower_right, lower_left);
-
-
- typedef typename boost::range_const_iterator<Range>::type iterator_type;
- iterator_type it = boost::begin(range);
-
- bool first = true;
-
- char previous_side[2] = {0, 0};
-
- int index = 0;
-
- for (iterator_type prev = it++;
- it != boost::end(range);
- prev = it++, index++)
- {
- segment_type segment(*prev, *it);
-
- if (first)
- {
- previous_side[0] = get_side<0>(box, *prev);
- previous_side[1] = get_side<1>(box, *prev);
- }
-
- char current_side[2];
- current_side[0] = get_side<0>(box, *it);
- current_side[1] = get_side<1>(box, *it);
-
- // There can NOT be intersections if
- // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
- // 2) OR same in Y-direction
- // 3) OR all points are inside the box (0)
- /*if (! (
- (current_side[0] != 0 && current_side[0] == previous_side[0])
- || (current_side[1] != 0 && current_side[1] == previous_side[1])
- || (current_side[0] == 0
- && current_side[1] == 0
- && previous_side[0] == 0
- && previous_side[1] == 0)
- )
- )*/
- if (true)
- {
- segment_identifier seg_id(source_id1,
- multi_index, ring_index, index);
-
- typedef relate
- <
- segment_type,
- box_segment_type,
- IntersectionPoints,
- IntersectionStrategy
- > relater;
-
- // Depending on code some relations can be left out
- relater::apply(segment, left, seg_id,
- segment_identifier(source_id2, -1, -1, 0),
- intersection_points, trivial);
- relater::apply(segment, top, seg_id,
- segment_identifier(source_id2, -1, -1, 1),
- intersection_points, trivial);
- relater::apply(segment, right, seg_id,
- segment_identifier(source_id2, -1, -1, 2),
- intersection_points, trivial);
- relater::apply(segment, bottom, seg_id,
- segment_identifier(source_id2, -1, -1, 3),
- intersection_points, trivial);
-
- }
- }
- }
-
-private:
- template<std::size_t Index, typename Point>
- static inline int get_side(Box const& box, Point const& point)
- {
- // Inside -> 0
- // Outside -> -1 (left/below) or 1 (right/above)
- // On border -> -2 (left/lower) or 2 (right/upper)
- // The only purpose of the value is to not be the same,
- // and to denote if it is inside (0)
-
- typename coordinate_type<Point>::type const& c = get<Index>(point);
- typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
- typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
-
- if (geometry::math::equals(c, left)) return -2;
- else if (geometry::math::equals(c, right)) return 2;
- else if (c < left) return -1;
- else if (c > right) return 1;
- else return 0;
- }
-
-
-};
-
-
-}} // namespace detail::get_intersection_points
-#endif // DOXYGEN_NO_DETAIL
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-template
-<
- typename GeometryTag1, typename GeometryTag2,
- bool IsMulti1, bool IsMulti2,
- typename Geometry1, typename Geometry2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct get_intersection_points
-{
-};
-
-
-template<typename Polygon, typename Box, typename IntersectionPoints, typename IntersectionStrategy>
-struct get_intersection_points
- <
- polygon_tag, box_tag, false, false,
- Polygon, Box,
- IntersectionPoints,
- IntersectionStrategy
- >
-{
-
- static inline bool apply(
- std::size_t source_id1, Polygon const& polygon,
- std::size_t source_id2, Box const& box,
- IntersectionPoints& intersection_points)
- {
- typedef typename geometry::ring_type<Polygon>::type ring_type;
-
- typedef typename boost::range_const_iterator
- <
- typename interior_type<Polygon>::type
- >::type iterator_type;
-
-
- typedef detail::get_intersection_points::get_ips_cs
- <
- ring_type,
- Box,
- IntersectionPoints,
- IntersectionStrategy
- > intersector_type;
-
- bool trivial = true;
- intersector_type::apply(
- source_id1, geometry::exterior_ring(polygon), -1, -1,
- source_id2, box,
- intersection_points, trivial);
-
- int i = 0;
- for (iterator_type it = boost::begin(interior_rings(polygon));
- it != boost::end(interior_rings(polygon));
- ++it, ++i)
- {
- intersector_type::apply(
- source_id1, *it, -1, i,
- source_id2, box, intersection_points, trivial);
- }
-
- return trivial;
- }
-};
-
-
-template<typename Ring, typename Box, typename IntersectionPoints, typename IntersectionStrategy>
-struct get_intersection_points
- <
- ring_tag, box_tag, false, false,
- Ring, Box,
- IntersectionPoints, IntersectionStrategy
- >
-{
- static inline bool apply(
- std::size_t source_id1, Ring const& ring,
- std::size_t source_id2, Box const& box,
- IntersectionPoints& intersection_points)
- {
- typedef typename boost::range_const_iterator
- <
- Ring
- >::type iterator_type;
-
- typedef detail::get_intersection_points::get_ips_cs
- <Ring, Box, IntersectionPoints, IntersectionStrategy> intersector_type;
-
- bool trivial = true;
- intersector_type::apply(
- source_id1, ring, -1, -1,
- source_id2, box,
- intersection_points, trivial);
-
- return trivial;
- }
-};
-
-
-template
-<
- typename Ring1,
- typename Ring2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct get_intersection_points
- <
- ring_tag, ring_tag, false, false,
- Ring1, Ring2,
- IntersectionPoints, IntersectionStrategy
- >
- : detail::get_intersection_points::get_ips_generic
- <
- Ring1,
- Ring2,
- IntersectionPoints,
- IntersectionStrategy
- >
-{};
-
-
-template
-<
- typename Polygon1,
- typename Polygon2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct get_intersection_points
- <
- polygon_tag, polygon_tag, false, false,
- Polygon1, Polygon2,
- IntersectionPoints, IntersectionStrategy
- >
- : detail::get_intersection_points::get_ips_generic
- <
- Polygon1,
- Polygon2,
- IntersectionPoints,
- IntersectionStrategy
- >
-{};
-
-template
-<
- typename Polygon,
- typename Ring,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct get_intersection_points
- <
- polygon_tag, ring_tag, false, false,
- Polygon, Ring,
- IntersectionPoints, IntersectionStrategy
- >
- : detail::get_intersection_points::get_ips_generic
- <
- Polygon,
- Ring,
- IntersectionPoints,
- IntersectionStrategy
- >
-{};
-
-template
-<
- typename LineString1,
- typename LineString2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct get_intersection_points
- <
- linestring_tag, linestring_tag, false, false,
- LineString1, LineString2,
- IntersectionPoints, IntersectionStrategy
- >
- : detail::get_intersection_points::get_ips_generic
- <
- LineString1,
- LineString2,
- IntersectionPoints,
- IntersectionStrategy
- >
-{};
-
-template
-<
- typename GeometryTag1, typename GeometryTag2,
- bool IsMulti1, bool IsMulti2,
- typename Geometry1, typename Geometry2,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct get_intersection_points_reversed
-{
- static inline bool apply(
- std::size_t source_id1, Geometry1 const& g1,
- std::size_t source_id2, Geometry2 const& g2,
- IntersectionPoints& intersection_points)
- {
- return get_intersection_points
- <
- GeometryTag2, GeometryTag1,
- IsMulti2, IsMulti1,
- Geometry2, Geometry1,
- IntersectionPoints, IntersectionStrategy
- >::apply(source_id2, g2, source_id1, g1, intersection_points);
- }
-};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-
-/*!
- \brief Calculate intersection points of two geometries
- \ingroup overlay
- \tparam Geometry1 first geometry type
- \tparam Geometry2 second geometry type
- \tparam IntersectionPoints type of intersection container (e.g. vector of "intersection_point"'s)
- \param geometry1 first geometry
- \param geometry2 second geometry
- \param intersection_points container which will contain intersection points
- */
-template <typename Geometry1, typename Geometry2, typename IntersectionPoints>
-inline void get_intersection_points(Geometry1 const& geometry1,
- Geometry2 const& geometry2, IntersectionPoints& intersection_points)
-{
- concept::check_concepts_and_equal_dimensions<const Geometry1, const Geometry2>();
-
- typedef typename boost::remove_const<Geometry1>::type ncg1_type;
- typedef typename boost::remove_const<Geometry2>::type ncg2_type;
-
- typedef typename strategy_intersection
- <
- typename cs_tag<Geometry1>::type,
- Geometry1,
- Geometry2,
- typename boost::range_value<IntersectionPoints>::type
- >::segment_intersection_strategy_type segment_intersection_strategy_type;
-
- boost::mpl::if_c
- <
- reverse_dispatch<Geometry1, Geometry2>::type::value,
- dispatch::get_intersection_points_reversed
- <
- typename tag<Geometry1>::type,
- typename tag<Geometry2>::type,
- is_multi<Geometry1>::type::value,
- is_multi<Geometry2>::type::value,
- ncg1_type,
- ncg2_type,
- IntersectionPoints,
- segment_intersection_strategy_type
- >,
- dispatch::get_intersection_points
- <
- typename tag<Geometry1>::type,
- typename tag<Geometry2>::type,
- is_multi<Geometry1>::type::value,
- is_multi<Geometry2>::type::value,
- ncg1_type,
- ncg2_type,
- IntersectionPoints,
- segment_intersection_strategy_type
- >
- >::type::apply(
- 0, geometry1,
- 1, geometry2,
- intersection_points);
-}
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_GET_INTERSECTION_POINTS_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -65,30 +65,43 @@
#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace get_turns {
+namespace detail { namespace get_turns
+{
+
+
+struct no_interrupt_policy
+{
+ static bool const enabled = false;
+ template <typename Range>
+ static inline bool apply(Range const&)
+ {
+ return false;
+ }
+};
template
<
typename Geometry1, typename Geometry2,
typename Section1, typename Section2,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
class get_turns_in_sections
{
public :
- static inline void apply(
+ // Returns true if terminated, false if interrupted
+ static inline bool apply(
int source_id1, Geometry1 const& geometry1,
- Section1 const& sec1,
+ Section1 const& sec1,
int source_id2, Geometry2 const& geometry2,
- Section2 const& sec2,
- bool return_if_found,
- TurnCollection& turns,
- bool& trivial)
+ Section2 const& sec2,
+ Turns& turns,
+ InterruptPolicy& interrupt_policy)
{
typedef typename boost::range_const_iterator
@@ -169,7 +182,7 @@
begin_range_2, end_range_2, next2, true);
advance_to_non_duplicate_next(nd_next2, it2, sec2);
- typedef typename boost::range_value<TurnCollection>::type turn_info;
+ typedef typename boost::range_value<Turns>::type turn_info;
typedef typename turn_info::point_type ip;
turn_info ti;
@@ -181,23 +194,29 @@
ti.operations[0].other_id = ti.operations[1].seg_id;
ti.operations[1].other_id = ti.operations[0].seg_id;
+ std::size_t const size_before = boost::size(turns);
+
detail::overlay::get_turn_info
<
- point1_type,
- point2_type,
+ point1_type, point2_type,
turn_info,
AssignPolicy
>::apply(*prev1, *it1, *nd_next1, *prev2, *it2, *nd_next2,
ti, std::back_inserter(turns));
- if (return_if_found
- && boost::size(turns) > 0)
+ if (InterruptPolicy::enabled)
{
- return;
+ if (interrupt_policy.apply(
+ std::make_pair(boost::begin(turns) + size_before,
+ boost::end(turns))))
+ {
+ return false;
+ }
}
}
}
}
+ return true;
}
@@ -275,61 +294,15 @@
};
-template
-<
- typename Ring, typename Box,
- typename Section1, typename Section2,
- typename TurnCollection,
- typename IntersectionStrategy,
- typename AssignPolicy
->
-class get_turns_range_box
-{
-public :
- static inline void apply(
- int source_id1, Ring const& ring,
- int source_id2, Box const& box,
- Section1 const& sec1, Section2 const& sec2,
- TurnCollection& turns, bool& trivial)
- {
- get_turns_in_sections
- <
- Ring,
- Box,
- Section1,
- Section2,
- TurnCollection,
- IntersectionStrategy,
- AssignPolicy
- >
- ::apply(
- source_id1, ring, sec1,
- source_id2, box, sec2,
- false,
- turns, trivial);
- }
-};
-
-template <typename Section, int Dimension, int Index>
-struct compare_section
-{
- inline bool operator()(Section const& left, Section const& right) const
- {
- return
- geometry::get<Index, Dimension>(left.bounding_box)
- < geometry::get<Index, Dimension>(right.bounding_box);
- }
-};
-
-
template
<
typename Geometry1,
typename Geometry2,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
class get_turns_generic
{
@@ -362,13 +335,13 @@
}
template <typename Sections1, typename Sections2, typename Map>
- static inline void intersect(
+ static inline bool intersect(
int source_id1, Geometry1 const& geometry1,
int source_id2, Geometry2 const& geometry2,
- TurnCollection& turns,
+ Turns& turns,
+ InterruptPolicy& interrupt_policy,
Sections1 const& sec1, Sections2 const& sec2,
- Map& map,
- bool &trivial)
+ Map& map)
{
for (typename boost::range_const_iterator<Sections1>::type
it1 = sec1.begin();
@@ -388,24 +361,28 @@
if (! geometry::detail::disjoint::disjoint_box_box(
it1->bounding_box, it2->bounding_box))
{
- get_turns_in_sections
- <
- Geometry1,
- Geometry2,
- typename boost::range_value<Sections1>::type,
- typename boost::range_value<Sections2>::type,
- TurnCollection,
- IntersectionStrategy,
- AssignPolicy
- >::apply(
- source_id1, geometry1, *it1,
- source_id2, geometry2, *it2,
- false,
- turns, trivial);
+ if (! get_turns_in_sections
+ <
+ Geometry1,
+ Geometry2,
+ typename boost::range_value<Sections1>::type,
+ typename boost::range_value<Sections2>::type,
+ Turns,
+ IntersectionStrategy,
+ AssignPolicy, InterruptPolicy
+ >::apply(
+ source_id1, geometry1, *it1,
+ source_id2, geometry2, *it2,
+ turns, interrupt_policy)
+ )
+ {
+ return false;
+ }
}
}
}
}
+ return true;
}
@@ -417,15 +394,15 @@
typename Sections1, typename Sections2,
typename Map
>
- static inline void divide_and_conquer(
+ static inline bool divide_and_conquer(
int source_id1, Geometry1 const& geometry1,
int source_id2, Geometry2 const& geometry2,
- TurnCollection& turns,
+ Turns& turns,
+ InterruptPolicy& interrupt_policy,
Box const& box,
Sections1 const& sec1, Sections2 const& sec2,
Map& map,
- bool &trivial,
std::size_t iteration = 0, std::size_t previous_count = 0)
{
// To stop the iteration, fallback to (quadratic) behaviour below certain limits,
@@ -436,9 +413,8 @@
|| n == previous_count
|| iteration > 100)
{
- intersect(source_id1, geometry1, source_id2, geometry2,
- turns, sec1, sec2, map, trivial);
- return;
+ return intersect(source_id1, geometry1, source_id2, geometry2,
+ turns, interrupt_policy, sec1, sec2, map);
}
// Divide the complete box in two (alternating) halves
@@ -469,20 +445,19 @@
#endif
// Recursively handle lower and upper half, dividing in other dimension
- divide_and_conquer<1 - Dimension>(source_id1, geometry1,
- source_id2, geometry2, turns,
- lower, lower1, lower2, map, trivial, iteration + 1, n);
-
- divide_and_conquer<1 - Dimension>(source_id1, geometry1,
- source_id2, geometry2, turns,
- upper, upper1, upper2, map, trivial, iteration + 1, n);
+ return divide_and_conquer<1 - Dimension>(source_id1, geometry1,
+ source_id2, geometry2, turns, interrupt_policy,
+ lower, lower1, lower2, map, iteration + 1, n)
+ && divide_and_conquer<1 - Dimension>(source_id1, geometry1,
+ source_id2, geometry2, turns, interrupt_policy,
+ upper, upper1, upper2, map, iteration + 1, n);
}
public:
- static inline bool apply(
+ static inline void apply(
int source_id1, Geometry1 const& geometry1,
int source_id2, Geometry2 const& geometry2,
- TurnCollection& turns)
+ Turns& turns, InterruptPolicy& interrupt_policy)
{
// Create monotonic sections in ONE direction
// - in most cases ONE direction is faster (e.g. ~1% faster for the NLP4 testset)
@@ -491,7 +466,7 @@
// Note that the sections contain boxes, are dynamic, and therefore
// are specified using output/intersection-point-type
// (to enable input-pointer-point-types)
- typedef typename boost::range_value<TurnCollection>::type ip_type;
+ typedef typename boost::range_value<Turns>::type ip_type;
typedef typename ip_type::point_type point_type;
typedef typename geometry::sections<geometry::box<point_type>, 1> sections1_type;
typedef typename geometry::sections<geometry::box<point_type>, 1> sections2_type;
@@ -511,10 +486,8 @@
// House-keeping map, to avoid section-pairs being compared twice
std::map<std::pair<int, int>, bool> map;
- bool trivial = true;
divide_and_conquer<1>(source_id1, geometry1, source_id2, geometry2,
- turns, box, sec1, sec2, map, trivial);
- return trivial;
+ turns, interrupt_policy, box, sec1, sec2, map);
}
};
@@ -524,17 +497,19 @@
<
typename Range,
typename Box,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns_cs
{
- static inline void apply(int source_id1, Range const& range,
- int multi_index, int ring_index,
- int source_id2, Box const& box,
- TurnCollection& turns,
- bool& trivial)
+ static inline void apply(
+ int source_id1, Range const& range,
+ int multi_index, int ring_index,
+ int source_id2, Box const& box,
+ Turns& turns,
+ InterruptPolicy& interrupt_policy)
{
if (boost::size(range) <= 1)
{
@@ -602,7 +577,7 @@
)*/
if (true)
{
- typedef typename boost::range_value<TurnCollection>::type turn_info;
+ typedef typename boost::range_value<Turns>::type turn_info;
typedef detail::overlay::get_turn_info
<
box_point_type,
@@ -640,6 +615,8 @@
lower_right, lower_left, upper_left,
ti, std::back_inserter(turns));
+ // TODO: call the break policy
+
}
}
}
@@ -682,9 +659,10 @@
typename GeometryTag1, typename GeometryTag2,
bool IsMulti1, bool IsMulti2,
typename Geometry1, typename Geometry2,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
{
@@ -695,24 +673,26 @@
<
typename Polygon,
typename Box,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
polygon_tag, box_tag, false, false,
Polygon, Box,
- TurnCollection,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy,
+ InterruptPolicy
>
{
- static inline bool apply(
+ static inline void apply(
int source_id1, Polygon const& polygon,
int source_id2, Box const& box,
- TurnCollection& turns)
+ Turns& turns, InterruptPolicy& interrupt_policy)
{
typedef typename geometry::ring_type<Polygon>::type ring_type;
@@ -726,16 +706,15 @@
<
ring_type,
Box,
- TurnCollection,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
> intersector_type;
- bool trivial = true;
intersector_type::apply(
source_id1, geometry::exterior_ring(polygon), -1, -1,
source_id2, box,
- turns, trivial);
+ turns, interrupt_policy);
int i = 0;
for (iterator_type it = boost::begin(interior_rings(polygon));
@@ -744,10 +723,9 @@
{
intersector_type::apply(
source_id1, *it, -1, i,
- source_id2, box, turns, trivial);
+ source_id2, box, turns, interrupt_policy);
}
- return trivial;
}
};
@@ -756,23 +734,24 @@
<
typename Ring,
typename Box,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
ring_tag, box_tag, false, false,
Ring, Box,
- TurnCollection,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{
- static inline bool apply(
+ static inline void apply(
int source_id1, Ring const& ring,
int source_id2, Box const& box,
- TurnCollection& turns)
+ Turns& turns, InterruptPolicy& interrupt_policy)
{
typedef typename boost::range_const_iterator
<
@@ -783,18 +762,16 @@
<
Ring,
Box,
- TurnCollection,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
> intersector_type;
- bool trivial = true;
intersector_type::apply(
source_id1, ring, -1, -1,
source_id2, box,
- turns, trivial);
+ turns, interrupt_policy);
- return trivial;
}
};
@@ -803,24 +780,25 @@
<
typename Ring1,
typename Ring2,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
ring_tag, ring_tag, false, false,
Ring1, Ring2,
- TurnCollection, IntersectionStrategy,
- AssignPolicy
+ Turns, IntersectionStrategy,
+ AssignPolicy, InterruptPolicy
>
: detail::get_turns::get_turns_generic
<
Ring1,
Ring2,
- TurnCollection,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
@@ -829,24 +807,25 @@
<
typename Polygon1,
typename Polygon2,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
polygon_tag, polygon_tag, false, false,
Polygon1, Polygon2,
- TurnCollection, IntersectionStrategy,
- AssignPolicy
+ Turns, IntersectionStrategy,
+ AssignPolicy, InterruptPolicy
>
: detail::get_turns::get_turns_generic
<
Polygon1,
Polygon2,
- TurnCollection,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
@@ -854,24 +833,25 @@
<
typename Polygon,
typename Ring,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
polygon_tag, ring_tag, false, false,
Polygon, Ring,
- TurnCollection, IntersectionStrategy,
- AssignPolicy
+ Turns, IntersectionStrategy,
+ AssignPolicy, InterruptPolicy
>
: detail::get_turns::get_turns_generic
<
Polygon,
Ring,
- TurnCollection,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
@@ -879,24 +859,25 @@
<
typename LineString1,
typename LineString2,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
linestring_tag, linestring_tag, false, false,
LineString1, LineString2,
- TurnCollection, IntersectionStrategy,
- AssignPolicy
+ Turns, IntersectionStrategy,
+ AssignPolicy, InterruptPolicy
>
: detail::get_turns::get_turns_generic
<
LineString1,
LineString2,
- TurnCollection,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
@@ -905,25 +886,25 @@
typename GeometryTag1, typename GeometryTag2,
bool IsMulti1, bool IsMulti2,
typename Geometry1, typename Geometry2,
- typename TurnCollection,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy, typename InterruptPolicy
>
struct get_turns_reversed
{
- static inline bool apply(
+ static inline void apply(
int source_id1, Geometry1 const& g1,
int source_id2, Geometry2 const& g2,
- TurnCollection& turns)
+ Turns& turns, InterruptPolicy& interrupt_policy)
{
- return get_turns
+ get_turns
<
GeometryTag2, GeometryTag1,
IsMulti2, IsMulti1,
Geometry2, Geometry1,
- TurnCollection, IntersectionStrategy,
- AssignPolicy
- >::apply(source_id2, g2, source_id1, g1, turns);
+ Turns, IntersectionStrategy,
+ AssignPolicy, InterruptPolicy
+ >::apply(source_id2, g2, source_id1, g1, turns, interrupt_policy);
}
};
@@ -938,7 +919,7 @@
\ingroup overlay
\tparam Geometry1 first geometry type
\tparam Geometry2 second geometry type
- \tparam TurnCollection type of turn-container (e.g. vector of "intersection/turn point"'s)
+ \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
\param geometry1 first geometry
\param geometry2 second geometry
\param turns container which will contain intersection points
@@ -948,22 +929,22 @@
typename AssignPolicy,
typename Geometry1,
typename Geometry2,
- typename TurnCollection
+ typename Turns,
+ typename InterruptPolicy
>
inline void get_turns(Geometry1 const& geometry1,
- Geometry2 const& geometry2, TurnCollection& turns)
+ Geometry2 const& geometry2,
+ Turns& turns,
+ InterruptPolicy& interrupt_policy)
{
concept::check_concepts_and_equal_dimensions<const Geometry1, const Geometry2>();
- typedef typename boost::remove_const<Geometry1>::type ncg1_type;
- typedef typename boost::remove_const<Geometry2>::type ncg2_type;
-
typedef typename strategy_intersection
<
typename cs_tag<Geometry1>::type,
Geometry1,
Geometry2,
- typename boost::range_value<TurnCollection>::type
+ typename boost::range_value<Turns>::type
>::segment_intersection_strategy_type segment_intersection_strategy_type;
boost::mpl::if_c
@@ -975,11 +956,11 @@
typename tag<Geometry2>::type,
is_multi<Geometry1>::type::value,
is_multi<Geometry2>::type::value,
- ncg1_type,
- ncg2_type,
- TurnCollection,
+ Geometry1,
+ Geometry2,
+ Turns,
segment_intersection_strategy_type,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>,
dispatch::get_turns
<
@@ -987,16 +968,16 @@
typename tag<Geometry2>::type,
is_multi<Geometry1>::type::value,
is_multi<Geometry2>::type::value,
- ncg1_type,
- ncg2_type,
- TurnCollection,
+ Geometry1,
+ Geometry2,
+ Turns,
segment_intersection_strategy_type,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
>::type::apply(
0, geometry1,
1, geometry2,
- turns);
+ turns, interrupt_policy);
}
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/intersection_point.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/intersection_point.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
+++ (empty file)
@@ -1,359 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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_INTERSECTION_POINT_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_INTERSECTION_POINT_HPP
-
-
-#include <vector>
-
-
-#include <boost/geometry/core/access.hpp>
-#include <boost/geometry/core/coordinate_dimension.hpp>
-
-#include <boost/geometry/strategies/distance.hpp>
-#include <boost/geometry/strategies/distance_result.hpp>
-
-#include <boost/geometry/algorithms/overlay/segment_identifier.hpp>
-
-
-#ifdef BOOST_GEOMETRY_USE_MSM
-# include <boost/geometry/algorithms/overlay/msm_state.hpp>
-#endif
-
-
-namespace boost { namespace geometry
-{
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace intersection {
-
-
-#if ! defined(BOOST_GEOMETRY_USE_MSM)
-
-class visit_info
-{
-private :
- static const int NONE = 0;
- static const int STARTED = 1;
- static const int VISITED = 2;
- static const int FINISHED = 3;
- //static const int WITHIN = 4;
-
- int visit_code;
-
-public:
- inline visit_info()
- : visit_code(0)
- {}
-
- void set_visited() { visit_code = VISITED; }
- void set_started() { visit_code = STARTED; }
- void set_finished() { visit_code = FINISHED; }
-
- bool none() const { return visit_code == NONE; }
- bool visited() const { return visit_code == VISITED; }
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
- friend std::ostream& operator<<(std::ostream &os, visit_info const& v)
- {
- if (v.visit_code != 0)
- {
- os << " VIS: " << int(v.visit_code);
- }
- return os;
- }
-#endif
-
-};
-
-#else
-
-class visit_info
-{
-private :
-#ifndef USE_MSM_MINI
- mutable
-#endif
- traverse_state state;
-
-public :
- inline visit_info()
- {
- state.start();
- }
-
- void set_visited() { state.process_event(visit()); }
- void set_started() { state.process_event(starting()); }
- void set_finished() { state.process_event(finish()); }
-
-#ifdef USE_MSM_MINI
- bool none() const { return state.flag_none(); }
- bool visited() const { return state.flag_visited(); }
-#else
- bool none() const { return state.is_flag_active<is_init>(); }
- bool visited() const { return state.is_flag_active<is_visited>(); }
-#endif
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
- friend std::ostream& operator<<(std::ostream &os, visit_info const& v)
- {
- return os;
- }
-#endif
-};
-#endif
-
-
-
-template<typename P>
-struct intersection_info
-{
- typedef P point_type;
- typedef typename distance_result<P, P>::type distance_type;
-
- inline intersection_info()
- : travels_to_vertex_index(-1)
- , travels_to_ip_index(-1)
- , next_ip_index(-1)
- , distance(geometry::make_distance_result<distance_type>(0))
- , direction(0)
- , how('?')
- , arrival(0)
- , opposite(false)
- , flagged(false)
- {}
-
- // Point to which the segment from IP is directing (TO-point)
- // If they intersect on their "arrival" points, it is the FROM-point.
- P other_point;
-
- // Identifier of this segment (source,segment,ring,multi)
- segment_identifier seg_id;
-
- // Identify the segment where it was intersected with to form this IP
- segment_identifier other_id;
-
-
- // vertex to which is free travel after this IP,
- // so from "segment_index+1" to "travels_to_vertex_index", without IP-s,
- // can be -1
- int travels_to_vertex_index;
-
- // same but now IP index, so "next IP index" but not on THIS segment
- int travels_to_ip_index;
-
- // index of next IP on this segment, -1 if there is no one
- int next_ip_index;
-
- distance_type distance; // distance-measurement from segment.first to IP
-
- // 1: left, -1: right, 0: collinear
- int direction;
-
- // Information about how intersection is done
- char how;
-
- // 1: arrived at IP, -1: departs from IP, 0: crosses IP
- int arrival;
-
- bool opposite;
-
- visit_info visit_state;
- side_info sides;
-
- bool flagged; // flagged for deletion
-
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
-
- static inline std::string dir(int d)
- {
- return d == 0 ? "-" : (d == 1 ? "L" : d == -1 ? "R" : "#");
- }
- static inline std::string how_str(int h)
- {
- return h == 0 ? "-" : (h == 1 ? "A" : "D");
- }
-
- friend std::ostream& operator<<(std::ostream &os, intersection_info<P> const& info)
- {
- typename geometry::coordinate_type<P>::type d = info.distance;
- os << "\t"
- << " src " << info.seg_id.source_index
- << " seg " << info.seg_id.segment_index
- << " (// " << info.other_id.source_index
- << "." << info.other_id.segment_index << ")"
- << " how " << info.how
- << "[" << how_str(info.arrival)
- << " " << dir(info.direction)
- << (info.opposite ? " o" : "")
- << "]"
- << " sd "
- << dir(info.sides.get<0,0>())
- << dir(info.sides.get<0,1>())
- << dir(info.sides.get<1,0>())
- << dir(info.sides.get<1,1>())
- << " nxt seg " << info.travels_to_vertex_index
- << " , ip " << info.travels_to_ip_index
- << " , or " << info.next_ip_index
- << " dst " << double(d)
- << info.visit_state;
- if (info.flagged)
- {
- os << " FLAGGED";
- }
- return os;
- }
-#endif
-};
-
-
-template<typename P>
-struct intersection_point
-{
- public :
- inline intersection_point()
- : trivial(true)
- , shared(false)
- , flagged(false)
- {
- }
-
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
- friend std::ostream& operator<<(std::ostream &os, intersection_point<P> const& p)
- {
- // Convert them to double to make them comparable in DEBUG-files
- typedef double casted;
-
- os
- << std::setprecision(6)
- << "IP (" << casted(geometry::get<0>(p.point))
- << "," << casted(geometry::get<1>(p.point)) << ")"
- << p.visit_state
- << (p.shared ? " SHARED" : "")
- << (p.flagged ? " FLAGGED" : "")
- << std::endl;
-
- for (unsigned int i = 0; i < p.info.size(); i++)
- {
- os << p.info[i] << std::endl;
- }
- if (! p.report.empty())
- {
- os << p.report << std::endl;
- }
- return os;
- }
- std::string report;
-#endif
- typedef intersection_info<P> traversal_type;
- typedef std::vector<traversal_type> traversal_vector;
-
- typedef P point_type;
-
- P point;
-
- visit_info visit_state;
-
- bool trivial; // FALSE if there is an collinearity, touch or so.
- bool shared; // shared with more IP's
- bool flagged; // flagged for deletion afterwards
-
- // info about the two intersecting segments
- // usually two, but often more if IP's are merged
- traversal_vector info;
-
- inline void clone_except_info(intersection_point& other) const
- {
- other.point = point;
- other.trivial = trivial;
- other.shared = shared;
- other.flagged = flagged;
- // Probably not necessary:
- other.visit_state = visit_state;
- }
-};
-
-
-
-
-}} // namespace detail::intersection
-#endif //DOXYGEN_NO_DETAIL
-
-
-// Register the intersection point as being a point fulfilling the Point Concept
-namespace traits
-{
-
- template <typename P>
- struct coordinate_type<geometry::detail::intersection::intersection_point<P> >
- {
- typedef typename geometry::coordinate_type<P>::type type;
- };
-
- template <typename P>
- struct coordinate_system<geometry::detail::intersection::intersection_point<P> >
- {
- typedef typename geometry::coordinate_system<P>::type type;
- };
-
- template <typename P>
- struct dimension<geometry::detail::intersection::intersection_point<P> >
- : geometry::dimension<P>
- {};
-
- template <typename P>
- struct tag<geometry::detail::intersection::intersection_point<P> >
- {
- typedef point_tag type;
- };
-
- template <typename P, std::size_t Dimension>
- struct access<geometry::detail::intersection::intersection_point<P>, Dimension>
- {
- static inline typename coordinate_type<P>::type get(
- geometry::detail::intersection::intersection_point<P> const& p)
- {
- return geometry::get<Dimension>(p.point);
- }
-
- static inline void set(geometry::detail::intersection::intersection_point<P>& p,
- typename coordinate_type<P>::type const& value)
- {
- geometry::set<Dimension>(p.point, value);
- }
- };
-
-}
-
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
-
-template <typename V>
-inline void report_ip(V const& intersection_points)
-{
- typedef typename V::const_iterator iterator_type;
-
- for (iterator_type it = intersection_points.begin();
- it != intersection_points.end();
- ++it)
- {
- if (! it->flagged)
- {
- std::cout << *it;
- }
- }
-}
-#endif // BOOST_GEOMETRY_DEBUG_INTERSECTION
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_INTERSECTION_POINT_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/self_intersection_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/self_intersection_points.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
+++ (empty file)
@@ -1,185 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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_OVERLAY_SELF_INTERSECTION_POINTS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SELF_INTERSECTION_POINTS_HPP
-
-#include <cstddef>
-
-#include <boost/range/functions.hpp>
-#include <boost/range/metafunctions.hpp>
-#include <boost/type_traits/remove_const.hpp>
-
-#include <boost/geometry/core/access.hpp>
-#include <boost/geometry/core/coordinate_dimension.hpp>
-#include <boost/geometry/core/is_multi.hpp>
-
-#include <boost/geometry/geometries/concepts/check.hpp>
-
-#include <boost/geometry/algorithms/detail/disjoint.hpp>
-#include <boost/geometry/algorithms/overlay/get_intersection_points.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace self_intersection_points {
-
-template
-<
- typename Geometry,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct check_ips
-{
- static inline bool apply(
- Geometry const& geometry,
- bool return_if_found,
- IntersectionPoints& intersection_points)
- {
- typedef typename geometry::sections
- <
- geometry::box < typename geometry::point_type<Geometry>::type >, 1
- > sections_type;
-
- sections_type sec;
- geometry::sectionalize(geometry, sec);
-
- bool trivial = true;
- for (typename boost::range_const_iterator<sections_type>::type
- it1 = sec.begin();
- it1 != sec.end();
- ++it1)
- {
- for (typename boost::range_const_iterator<sections_type>::type
- it2 = sec.begin();
- it2 != sec.end();
- ++it2)
- {
- if (! geometry::detail::disjoint::disjoint_box_box(
- it1->bounding_box, it2->bounding_box)
- && ! it1->duplicate
- && ! it2->duplicate
- )
- {
- geometry::detail::get_intersection_points::get_ips_in_sections
- <
- Geometry, Geometry,
- typename boost::range_value<sections_type>::type,
- typename boost::range_value<sections_type>::type,
- IntersectionPoints, IntersectionStrategy
- >::apply(
- 0, geometry, *it1,
- 0, geometry, *it2,
- return_if_found,
- intersection_points, trivial);
- }
- }
- }
- return trivial;
- }
-};
-
-
-}} // namespace detail::self_intersection_points
-#endif // DOXYGEN_NO_DETAIL
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-template
-<
- typename GeometryTag,
- bool IsMulti,
- typename Geometry,
- typename IntersectionPoints,
- typename IntersectionStrategy
->
-struct self_intersection_points
-{
-};
-
-
-template<typename Ring, typename IntersectionPoints, typename IntersectionStrategy>
-struct self_intersection_points
- <
- ring_tag, false, Ring,
- IntersectionPoints,
- IntersectionStrategy
- >
- : detail::self_intersection_points::check_ips
- <
- Ring,
- IntersectionPoints,
- IntersectionStrategy
- >
-{};
-
-
-template<typename Polygon, typename IntersectionPoints, typename IntersectionStrategy>
-struct self_intersection_points
- <
- polygon_tag, false, Polygon,
- IntersectionPoints, IntersectionStrategy
- >
- : detail::self_intersection_points::check_ips
- <
- Polygon,
- IntersectionPoints,
- IntersectionStrategy
- >
-{};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-/*!
- \brief Calculate self intersections of a geometry
- \ingroup overlay
- \tparam Geometry geometry type
- \tparam IntersectionPoints type of intersection container (e.g. vector of "intersection_point"'s)
- \param geometry geometry
- \param intersection_points container which will contain intersection points
- \return TRUE if it is trivial, else FALSE
- */
-template <typename Geometry, typename IntersectionPoints>
-inline bool get_intersection_points(Geometry const& geometry,
- IntersectionPoints& intersection_points)
-{
- concept::check<Geometry>();
-
- typedef typename strategy_intersection
- <
- typename cs_tag<Geometry>::type,
- Geometry,
- Geometry,
- typename boost::range_value<IntersectionPoints>::type
- >::segment_intersection_strategy_type segment_intersection_strategy_type;
-
- typedef typename boost::remove_const<Geometry>::type ncg_type;
-
- return dispatch::self_intersection_points
- <
- typename tag<ncg_type>::type,
- is_multi<ncg_type>::type::value,
- ncg_type,
- IntersectionPoints, segment_intersection_strategy_type
- >::apply(geometry, false, intersection_points);
-}
-
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SELF_INTERSECTION_POINTS_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -33,16 +33,17 @@
template
<
typename Geometry,
- typename IntersectionPoints,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
{
static inline bool apply(
Geometry const& geometry,
- bool return_if_found,
- IntersectionPoints& intersection_points)
+ Turns& turns,
+ InterruptPolicy& interrupt_policy)
{
typedef typename geometry::sections
<
@@ -53,7 +54,6 @@
sections_type sec;
geometry::sectionalize(geometry, sec);
- bool trivial = true;
for (typename boost::range_const_iterator<sections_type>::type
it1 = sec.begin();
it1 != sec.end();
@@ -70,27 +70,24 @@
&& ! it2->duplicate
)
{
- geometry::detail::get_turns::get_turns_in_sections
- <
- Geometry, Geometry,
- typename boost::range_value<sections_type>::type,
- typename boost::range_value<sections_type>::type,
- IntersectionPoints, IntersectionStrategy,
- AssignPolicy
- >::apply(
-#ifdef BG_SELF_NEGATIVE
- -2, geometry, *it1,
- -1, geometry, *it2,
-#else
- 0, geometry, *it1,
- 0, geometry, *it2,
-#endif
- return_if_found,
- intersection_points, trivial);
+ if (! geometry::detail::get_turns::get_turns_in_sections
+ <
+ Geometry, Geometry,
+ typename boost::range_value<sections_type>::type,
+ typename boost::range_value<sections_type>::type,
+ Turns, IntersectionStrategy,
+ AssignPolicy, InterruptPolicy
+ >::apply(
+ 0, geometry, *it1,
+ 0, geometry, *it2,
+ turns, interrupt_policy))
+ {
+ return false;
+ }
}
}
}
- return trivial;
+ return true;
}
};
@@ -108,9 +105,10 @@
typename GeometryTag,
bool IsMulti,
typename Geometry,
- typename IntersectionPoints,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct self_get_turn_points
{
@@ -120,23 +118,24 @@
template
<
typename Ring,
- typename IntersectionPoints,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct self_get_turn_points
<
ring_tag, false, Ring,
- IntersectionPoints,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
: detail::self_get_turn_points::get_turns
<
Ring,
- IntersectionPoints,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
@@ -144,22 +143,23 @@
template
<
typename Polygon,
- typename IntersectionPoints,
+ typename Turns,
typename IntersectionStrategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct self_get_turn_points
<
polygon_tag, false, Polygon,
- IntersectionPoints, IntersectionStrategy,
- AssignPolicy
+ Turns, IntersectionStrategy,
+ AssignPolicy, InterruptPolicy
>
: detail::self_get_turn_points::get_turns
<
Polygon,
- IntersectionPoints,
+ Turns,
IntersectionStrategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
@@ -172,14 +172,20 @@
\brief Calculate self intersections of a geometry
\ingroup overlay
\tparam Geometry geometry type
- \tparam IntersectionPoints type of intersection container
- (e.g. vector of "intersection_point"'s)
+ \tparam Turns type of intersection container
+ (e.g. vector of "intersection/turn point"'s)
\param geometry geometry
- \param intersection_points container which will contain intersection points
+ \param turns container which will contain intersection points
*/
-template <typename AssignPolicy, typename Geometry, typename IntersectionPoints>
+template
+<
+ typename AssignPolicy,
+ typename Geometry,
+ typename Turns,
+ typename InterruptPolicy
+>
inline void get_turns(Geometry const& geometry,
- IntersectionPoints& intersection_points)
+ Turns& turns, InterruptPolicy& interrupt_policy)
{
concept::check<Geometry>();
@@ -188,7 +194,7 @@
typename cs_tag<Geometry>::type,
Geometry,
Geometry,
- typename boost::range_value<IntersectionPoints>::type
+ typename boost::range_value<Turns>::type
>::segment_intersection_strategy_type strategy_type;
typedef typename boost::remove_const<Geometry>::type ncg_type;
@@ -198,9 +204,9 @@
typename tag<ncg_type>::type,
is_multi<ncg_type>::type::value,
ncg_type,
- IntersectionPoints, strategy_type,
- AssignPolicy
- >::apply(geometry, false, intersection_points);
+ Turns, strategy_type,
+ AssignPolicy, InterruptPolicy
+ >::apply(geometry, turns, interrupt_policy);
}
Modified: sandbox/geometry/boost/geometry/algorithms/union.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/union.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/union.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -176,15 +176,12 @@
concept::check<const Geometry1>();
concept::check<const Geometry2>();
- typedef typename geometry::point_type<GeometryOut>::type point_type;
- typedef detail::intersection::intersection_point<point_type> ip_type;
-
typedef strategy_intersection
<
- typename cs_tag<point_type>::type,
+ typename cs_tag<GeometryOut>::type,
Geometry1,
Geometry2,
- ip_type
+ typename geometry::point_type<GeometryOut>::type
> strategy;
return union_inserter<GeometryOut>(geometry1, geometry2, out, strategy());
@@ -194,4 +191,4 @@
}} // namespace boost::geometry
-#endif //GGL_ALGORITHMS_UNION_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/within.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/within.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/within.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -49,7 +49,6 @@
#include <boost/range/functions.hpp>
#include <boost/range/metafunctions.hpp>
-#include <boost/geometry/algorithms/distance.hpp>
#include <boost/geometry/algorithms/make.hpp>
#include <boost/geometry/core/access.hpp>
Modified: sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -91,4 +91,4 @@
}} // namespace boost::geometry
-#endif //GGL_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
+#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
Deleted: sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_intersection_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_intersection_points.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
+++ (empty file)
@@ -1,67 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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_GET_INTERSECTION_POINTS_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_GET_INTERSECTION_POINTS_HPP
-
-#include <boost/geometry/multi/core/is_multi.hpp>
-
-#include <boost/geometry/multi/algorithms/distance.hpp>
-#include <boost/geometry/multi/algorithms/get_section.hpp>
-#include <boost/geometry/multi/algorithms/sectionalize.hpp>
-
-#include <boost/geometry/multi/iterators/range_type.hpp>
-
-#include <boost/geometry/algorithms/overlay/get_intersection_points.hpp>
-
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename MultiTag1,
- typename MultiTag2,
- typename MultiGeometry1,
- typename MultiGeometry2,
- typename IntersectionPoints,
- typename Strategy
->
-struct get_intersection_points
- <
- MultiTag1, MultiTag2,
- true, true,
- MultiGeometry1, MultiGeometry2,
- IntersectionPoints,
- Strategy
- >
- : detail::get_intersection_points::get_ips_generic
- <
- MultiGeometry1,
- MultiGeometry2,
- IntersectionPoints,
- Strategy
- >
-{};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_GET_INTERSECTION_POINTS_HPP
Modified: sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -35,7 +35,8 @@
typename MultiGeometry2,
typename IntersectionPoints,
typename Strategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
@@ -44,7 +45,7 @@
MultiGeometry1, MultiGeometry2,
IntersectionPoints,
Strategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
: detail::get_turns::get_turns_generic
<
@@ -52,7 +53,7 @@
MultiGeometry2,
IntersectionPoints,
Strategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
@@ -65,7 +66,8 @@
typename MultiGeometry,
typename IntersectionPoints,
typename Strategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
@@ -74,7 +76,7 @@
SingleGeometry, MultiGeometry,
IntersectionPoints,
Strategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
: detail::get_turns::get_turns_generic
<
@@ -82,7 +84,7 @@
MultiGeometry,
IntersectionPoints,
Strategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
@@ -96,7 +98,8 @@
typename SingleGeometry,
typename IntersectionPoints,
typename Strategy,
- typename AssignPolicy
+ typename AssignPolicy,
+ typename InterruptPolicy
>
struct get_turns
<
@@ -105,7 +108,7 @@
MultiGeometry, SingleGeometry,
IntersectionPoints,
Strategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
: detail::get_turns::get_turns_generic
<
@@ -113,7 +116,7 @@
SingleGeometry,
IntersectionPoints,
Strategy,
- AssignPolicy
+ AssignPolicy, InterruptPolicy
>
{};
Modified: sandbox/geometry/boost/geometry/multi/multi.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/multi.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/multi.hpp 2010-02-14 16:51:08 EST (Sun, 14 Feb 2010)
@@ -45,7 +45,6 @@
#include <boost/geometry/multi/algorithms/detail/multi_sum.hpp>
#include <boost/geometry/multi/algorithms/overlay/copy_segments.hpp>
#include <boost/geometry/multi/algorithms/overlay/self_turn_points.hpp>
-#include <boost/geometry/multi/algorithms/overlay/get_intersection_points.hpp>
#include <boost/geometry/multi/geometries/multi_point.hpp>