|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r66449 - in sandbox/geometry/boost/geometry: . algorithms algorithms/detail algorithms/detail/overlay algorithms/detail/sections extensions/algorithms/buffer extensions/contrib extensions/gis/geographic/strategies geometries iterators multi multi/algorithms multi/algorithms/detail/overlay multi/algorithms/detail/sections multi/strategies multi/strategies/cartesian strategies strategies/agnostic strategies/cartesian strategies/concepts strategies/spherical strategies/transform
From: barend.gehrels_at_[hidden]
Date: 2010-11-08 05:18:46
Author: barendgehrels
Date: 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
New Revision: 66449
URL: http://svn.boost.org/trac/boost/changeset/66449
Log:
Assemble/traverse/enrich: complete update for handling self tangencies
Strategies area, within, centroid, transform adapted to new conventions using services
Centroid: removed underscore
Correct: support for open polygons
Get turns: support for open polygons
Sectionalize/segments: support for open polygons
Closing iterator: complete new implementation to support open polygons better
Numpoints: added boolean parameter to add one for open polygons
Within: bugfix for point-on-border-of-interior ring, this needed returning three values -1,0,1 instead of boolean
polygon/ring: added a copy in namespace model:: as agreed long ago, with other default template parameters
Added:
sandbox/geometry/boost/geometry/algorithms/detail/overlay/check_enrich.hpp (contents, props changed)
sandbox/geometry/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp (contents, props changed)
sandbox/geometry/boost/geometry/strategies/within.hpp
- copied, changed from r66116, /sandbox/geometry/boost/geometry/strategies/point_in_poly.hpp
Removed:
sandbox/geometry/boost/geometry/strategies/point_in_poly.hpp
Text files modified:
sandbox/geometry/boost/geometry/algorithms/area.hpp | 11
sandbox/geometry/boost/geometry/algorithms/centroid.hpp | 2
sandbox/geometry/boost/geometry/algorithms/correct.hpp | 20
sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp | 99 ++++++
sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segments.hpp | 24
sandbox/geometry/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp | 583 +++++++++++++++++++++++----------------
sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp | 69 ++-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/overlay.hpp | 6
sandbox/geometry/boost/geometry/algorithms/detail/overlay/ring_properties.hpp | 2
sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp | 2
sandbox/geometry/boost/geometry/algorithms/detail/overlay/traverse.hpp | 95 +++++-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp | 38 ++
sandbox/geometry/boost/geometry/algorithms/detail/ring_identifier.hpp | 3
sandbox/geometry/boost/geometry/algorithms/detail/sections/get_full_section.hpp | 89 ++---
sandbox/geometry/boost/geometry/algorithms/detail/sections/get_section.hpp | 137 +--------
sandbox/geometry/boost/geometry/algorithms/detail/sections/sectionalize.hpp | 43 +-
sandbox/geometry/boost/geometry/algorithms/dissolve.hpp | 14
sandbox/geometry/boost/geometry/algorithms/num_points.hpp | 37 +
sandbox/geometry/boost/geometry/algorithms/transform.hpp | 18
sandbox/geometry/boost/geometry/algorithms/within.hpp | 62 ++-
sandbox/geometry/boost/geometry/extensions/algorithms/buffer/sectionalizing_buffer.hpp | 8
sandbox/geometry/boost/geometry/extensions/algorithms/buffer/traversing_buffer.hpp | 2
sandbox/geometry/boost/geometry/extensions/contrib/ttmath_stub.hpp | 87 +++++
sandbox/geometry/boost/geometry/extensions/gis/geographic/strategies/area_huiller_earth.hpp | 19
sandbox/geometry/boost/geometry/geometries/linear_ring.hpp | 98 ++++++
sandbox/geometry/boost/geometry/geometries/polygon.hpp | 175 +++++++++++
sandbox/geometry/boost/geometry/geometry.hpp | 4
sandbox/geometry/boost/geometry/iterators/closing_iterator.hpp | 117 +++++--
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp | 3
sandbox/geometry/boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp | 24
sandbox/geometry/boost/geometry/multi/algorithms/detail/sections/get_section.hpp | 3
sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp | 1
sandbox/geometry/boost/geometry/multi/algorithms/num_points.hpp | 6
sandbox/geometry/boost/geometry/multi/algorithms/union.hpp | 1
sandbox/geometry/boost/geometry/multi/algorithms/within.hpp | 9
sandbox/geometry/boost/geometry/multi/multi.hpp | 1
sandbox/geometry/boost/geometry/multi/strategies/cartesian/centroid_average.hpp | 16
sandbox/geometry/boost/geometry/multi/strategies/centroid.hpp | 10
sandbox/geometry/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp | 88 ++++-
sandbox/geometry/boost/geometry/strategies/area.hpp | 19 +
sandbox/geometry/boost/geometry/strategies/area_result.hpp | 6
sandbox/geometry/boost/geometry/strategies/cartesian/area_by_triangles.hpp | 22
sandbox/geometry/boost/geometry/strategies/cartesian/cart_intersect.hpp | 9
sandbox/geometry/boost/geometry/strategies/cartesian/centroid_bashein_detmer.hpp | 26 +
sandbox/geometry/boost/geometry/strategies/cartesian/point_in_poly_crossings_multiply.hpp | 4
sandbox/geometry/boost/geometry/strategies/cartesian/point_in_poly_franklin.hpp | 4
sandbox/geometry/boost/geometry/strategies/centroid.hpp | 47 +++
sandbox/geometry/boost/geometry/strategies/concepts/within_concept.hpp | 4
sandbox/geometry/boost/geometry/strategies/spherical/area_huiller.hpp | 21
sandbox/geometry/boost/geometry/strategies/strategies.hpp | 2
sandbox/geometry/boost/geometry/strategies/strategy_transform.hpp | 54 ++-
sandbox/geometry/boost/geometry/strategies/transform.hpp | 16
sandbox/geometry/boost/geometry/strategies/transform/map_transformer.hpp | 5
sandbox/geometry/boost/geometry/strategies/within.hpp | 56 +++
54 files changed, 1581 insertions(+), 740 deletions(-)
Modified: sandbox/geometry/boost/geometry/algorithms/area.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/area.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/area.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -84,9 +84,10 @@
// Ignore warning (because using static method sometimes) on strategy
boost::ignore_unused_variable_warning(strategy);
+ // An open linear_ring has at least three points,
// A closed linear_ring has at least four points,
// if not, there is no (zero) area
- if (boost::size(ring) < 4)
+ if (boost::size(ring) < (Closure == open ? 3 : 4))
{
return type();
}
@@ -123,7 +124,6 @@
#endif // DOXYGEN_NO_DETAIL
-
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
@@ -229,7 +229,12 @@
{
concept::check<Geometry const>();
- typedef typename area_result<Geometry>::strategy_type strategy_type;
+ typedef typename point_type<Geometry>::type point_type;
+ typedef typename strategy::area::services::default_strategy
+ <
+ typename cs_tag<point_type>::type,
+ point_type
+ >::type strategy_type;
return dispatch::area
<
Modified: sandbox/geometry/boost/geometry/algorithms/centroid.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/centroid.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/centroid.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -408,7 +408,7 @@
{
concept::check_concepts_and_equal_dimensions<Point, Geometry const>();
- typedef typename strategy_centroid
+ typedef typename strategy::centroid::services::default_strategy
<
typename cs_tag<Geometry>::type,
typename tag<Geometry>::type,
Modified: sandbox/geometry/boost/geometry/algorithms/correct.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/correct.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/correct.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -102,7 +102,7 @@
{
typedef typename point_type<Ring>::type point_type;
- typedef typename strategy_area
+ typedef typename strategy::area::services::default_strategy
<
typename cs_tag<point_type>::type,
point_type
@@ -124,7 +124,7 @@
{
// check if closed, if not, close it
bool const disjoint = geometry::disjoint(*boost::begin(r), *(boost::end(r) - 1));
- closure_selector s = geometry::closure<Ring>::value;
+ closure_selector const s = geometry::closure<Ring>::value;
if (disjoint && (s == closed))
{
@@ -132,8 +132,8 @@
}
if (! disjoint && geometry::closure<Ring>::value != closed)
{
- // Open it, TODO!
- std::cout << "TODO";
+ // Open it by removing last point
+ r.resize(boost::size(r) - 1);
}
}
// Check area
@@ -178,7 +178,7 @@
{
template <typename Tag, typename Geometry>
-struct correct
+struct correct
{
BOOST_MPL_ASSERT_MSG
(
@@ -188,18 +188,18 @@
};
template <typename Point>
-struct correct<point_tag, Point>
- : detail::correct::correct_nop<Point>
+struct correct<point_tag, Point>
+ : detail::correct::correct_nop<Point>
{};
template <typename LineString>
-struct correct<linestring_tag, LineString>
+struct correct<linestring_tag, LineString>
: detail::correct::correct_nop<LineString>
{};
template <typename Segment>
-struct correct<segment_tag, Segment>
- : detail::correct::correct_nop<Segment>
+struct correct<segment_tag, Segment>
+ : detail::correct::correct_nop<Segment>
{};
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -19,6 +19,7 @@
#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/ring_properties.hpp>
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
//#include <boost/geometry/strategies/intersection_result.hpp>
@@ -29,6 +30,8 @@
#include <boost/geometry/util/math.hpp>
#include <boost/geometry/strategies/intersection.hpp>
+#include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp>
+
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
# include <boost/geometry/util/write_dsv.hpp>
@@ -44,6 +47,81 @@
{
+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)
{
@@ -56,7 +134,7 @@
it != boost::end(turn_points);
++it, ++index)
{
- if (! it->ignore())
+ if (! skip(*it))
{
int op_index = 0;
for (typename boost::range_iterator<container_type const>::type
@@ -137,22 +215,27 @@
Geometry1 const& geometry1, Geometry2 const& geometry2,
RingCollection const& collection)
{
+ int code = -1;
if (item1.ring_id.source_index == 0)
{
- return geometry::within(item2.point,
+ code = point_in_ring(item2.point,
get_ring<tag1>::apply(item1.ring_id, geometry1));
}
else if (item1.ring_id.source_index == 1)
{
- return geometry::within(item2.point,
+ code = point_in_ring(item2.point,
get_ring<tag2>::apply(item1.ring_id, geometry2));
}
else if (item1.ring_id.source_index == 2)
{
- return geometry::within(item2.point,
+ code = point_in_ring(item2.point,
get_ring<tag3>::apply(item1.ring_id, collection));
}
- return false;
+ else
+ {
+ return false;
+ }
+ return code == 0 ? item1.area < 0 : code == 1;
}
template <typename Selection, typename Map>
@@ -255,12 +338,16 @@
item_type& item1 = *it1;
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << item1.ring_id << " area: " << item1.area << std::endl;
+if (item1.area < 0)
+{
+ std::cout << "(negative ";
+}
#endif
iterator it2 = it1;
for (it2++; it2 != boost::end(container); ++it2)
{
item_type& item2 = *it2;
- if (geometry::within(item2.point, item1.box)
+ if (within_or_touch(item2.point, item1.box)
&& geometry::math::abs(item2.area)
< geometry::math::abs(item1.area)
&& contains(item1, item2, geometry1, geometry2, collection)
Added: sandbox/geometry/boost/geometry/algorithms/detail/overlay/check_enrich.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/check_enrich.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -0,0 +1,171 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CHECK_ENRICH_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CHECK_ENRICH_HPP
+
+
+#include <cstddef>
+
+
+#include <boost/assert.hpp>
+#include <boost/range.hpp>
+
+
+
+#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+template<typename Turn>
+struct meta_turn
+{
+ int index;
+ Turn const* turn;
+ bool handled[2];
+
+ inline meta_turn(int i, Turn const& t)
+ : index(i), turn(&t)
+ {
+ handled[0] = false;
+ handled[1] = false;
+ }
+};
+
+
+template <typename MetaTurn>
+inline void display(MetaTurn const& meta_turn, std::string const& reason = "")
+{
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << meta_turn.index
+ << "\tMethods: " << method_char(meta_turn.turn->method)
+ << " operations: " << operation_char(meta_turn.turn->operations[0].operation)
+ << operation_char(meta_turn.turn->operations[1].operation)
+ << " travels to " << meta_turn.turn->operations[0].enriched.travels_to_ip_index
+ << " and " << meta_turn.turn->operations[1].enriched.travels_to_ip_index
+ //<< " -> " << op_index
+ << " " << reason
+ << std::endl;
+#endif
+}
+
+
+template <typename MetaTurns, typename MetaTurn>
+inline void check_detailed(MetaTurns& meta_turns, MetaTurn const& meta_turn,
+ int op_index, int cycle, int start, operation_type for_operation,
+ bool& error)
+{
+ display(meta_turn);
+ int const ip_index = meta_turn.turn->operations[op_index].enriched.travels_to_ip_index;
+ if (ip_index >= 0)
+ {
+ bool found = false;
+
+ if (ip_index == start)
+ {
+ display(meta_turns[ip_index], " FINISH");
+ return;
+ }
+
+ // check on continuing, or on same-operation-on-same-geometry
+ if (! meta_turns[ip_index].handled[op_index]
+ && (meta_turns[ip_index].turn->operations[op_index].operation == operation_continue
+ || meta_turns[ip_index].turn->operations[op_index].operation == for_operation)
+ )
+ {
+ meta_turns[ip_index].handled[op_index] = true;
+ check_detailed(meta_turns, meta_turns[ip_index], op_index, cycle, start, for_operation, error);
+ found = true;
+ }
+ // check on other geometry
+ if (! found)
+ {
+ int const other_index = 1 - op_index;
+ if (! meta_turns[ip_index].handled[other_index]
+ && meta_turns[ip_index].turn->operations[other_index].operation == for_operation)
+ {
+ meta_turns[ip_index].handled[other_index] = true;
+ check_detailed(meta_turns, meta_turns[ip_index], other_index, cycle, start, for_operation, error);
+ found = true;
+ }
+ }
+
+ if (! found)
+ {
+ display(meta_turns[ip_index], " STOP");
+ error = true;
+#ifndef BOOST_GEOMETRY_DEBUG_ENRICH
+ //std::cout << " STOP";
+#endif
+ }
+ }
+}
+
+
+template <typename TurnPoints>
+inline bool check_graph(TurnPoints& turn_points, operation_type for_operation)
+{
+ typedef typename boost::range_value<TurnPoints>::type turn_point_type;
+
+ bool error = false;
+ int index = 0;
+
+ std::vector<meta_turn<turn_point_type> > meta_turns;
+ for (typename boost::range_iterator<TurnPoints const>::type
+ it = boost::begin(turn_points);
+ it != boost::end(turn_points);
+ ++it, ++index)
+ {
+ meta_turns.push_back(meta_turn<turn_point_type>(index, *it));
+ }
+
+ int cycle = 0;
+ for (typename boost::range_iterator<std::vector<meta_turn<turn_point_type> > > ::type
+ it = boost::begin(meta_turns);
+ it != boost::end(meta_turns);
+ ++it)
+ {
+ if (! (it->turn->blocked() || it->turn->is_discarded()))
+ {
+ for (int i = 0 ; i < 2; i++)
+ {
+ if (! it->handled[i]
+ && it->turn->operations[i].operation == for_operation)
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << "CYCLE " << cycle << std::endl;
+#endif
+ it->handled[i] = true;
+ check_detailed(meta_turns, *it, i, cycle++, it->index, for_operation, error);
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout <<" END CYCLE " << it->index << std::endl;
+#endif
+ }
+ }
+ }
+ }
+ return error;
+}
+
+
+
+}} // namespace detail::overlay
+#endif //DOXYGEN_NO_DETAIL
+
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CHECK_ENRICH_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segments.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segments.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segments.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -42,11 +42,18 @@
template <typename Ring, typename SegmentIdentifier, typename RangeOut>
struct copy_segments_ring
{
+ typedef closeable_view
+ <
+ Ring const,
+ closure<Ring>::value == open
+ > view_type;
+
static inline void apply(Ring const& ring,
SegmentIdentifier const& seg_id, int to_index,
RangeOut& current_output)
{
- typedef typename boost::range_iterator<Ring const>::type iterator;
+ view_type view(ring);
+ typedef typename boost::range_iterator<view_type const>::type iterator;
typedef geometry::ever_circling_iterator<iterator> ec_iterator;
@@ -59,10 +66,10 @@
int const from_index = seg_id.segment_index + 1;
// Sanity check
- BOOST_ASSERT(from_index < boost::size(ring));
+ BOOST_ASSERT(from_index < boost::size(view));
- ec_iterator it(boost::begin(ring), boost::end(ring),
- boost::begin(ring) + from_index);
+ ec_iterator it(boost::begin(view), boost::end(view),
+ boost::begin(view) + from_index);
// [2..4] -> 4 - 2 + 1 = 3 -> {2,3,4} -> OK
// [4..2],size=6 -> 6 - 4 + 2 + 1 = 5 -> {4,5,0,1,2} -> OK
@@ -70,7 +77,7 @@
typedef typename boost::range_difference<Ring>::type size_type;
size_type const count = from_index <= to_index
? to_index - from_index + 1
- : boost::size(ring) - from_index + to_index + 1;
+ : boost::size(view) - from_index + to_index + 1;
for (size_type i = 0; i < count; ++i, ++it)
{
@@ -158,8 +165,6 @@
};
-
-
}} // namespace detail::copy_segments
#endif // DOXYGEN_NO_DETAIL
@@ -201,6 +206,7 @@
>
{};
+
template
<
typename Polygon,
@@ -236,9 +242,6 @@
#endif // DOXYGEN_NO_DISPATCH
-
-
-
/*!
\brief Copy segments from a geometry, starting with the specified segment (seg_id)
until the specified index (to_index)
@@ -270,4 +273,5 @@
}} // namespace boost::geometry
+
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -12,12 +12,15 @@
#include <cstddef>
#include <algorithm>
#include <map>
+#include <set>
#include <vector>
-//#ifdef BOOST_GEOMETRY_DEBUG_OVERLAY
-#include <iostream>
-#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
-//#endif
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+# include <iostream>
+# include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
+# include <boost/geometry/extensions/gis/io/wkt/wkt.hpp>
+# define BOOST_GEOMETRY_DEBUG_IDENTIFIER
+#endif
#include <boost/assert.hpp>
#include <boost/range.hpp>
@@ -28,6 +31,12 @@
#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_relative_order.hpp>
+#include <boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp>
+
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+# include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
+#endif
+
namespace boost { namespace geometry
{
@@ -36,210 +45,146 @@
namespace detail { namespace overlay
{
-
-template <typename Operation>
-struct indexed_operation
+// Wraps "turn_operation" from turn_info.hpp,
+// giving it extra information
+template <typename TurnOperation>
+struct indexed_turn_operation
{
- typedef Operation type;
+ typedef TurnOperation type;
int index;
int operation_index;
- Operation subject;
+ bool discarded;
+ TurnOperation subject;
- inline indexed_operation(int i, int oi, Operation const& s)
+ inline indexed_turn_operation(int i, int oi, TurnOperation const& s)
: index(i)
, operation_index(oi)
+ , discarded(false)
, subject(s)
{}
};
+template <typename IndexedTurnOperation>
+struct remove_discarded
+{
+ inline bool operator()(IndexedTurnOperation const& operation) const
+ {
+ return operation.discarded;
+ }
+};
+
template
<
+ typename TurnPoints,
typename Indexed,
typename Geometry1,
typename Geometry2,
typename Strategy
>
-struct sort_on_distance
+struct sort_on_segment_and_distance
{
-private :
- Geometry1 const& m_geometry1;
- Geometry2 const& m_geometry2;
- Strategy const& m_strategy;
-
- typedef typename Indexed::type operation_type;
- typedef typename point_type<Geometry1>::type point_type;
-
-
- inline bool normal_compare_distances(operation_type const& left,
- operation_type const& right) const
+ inline sort_on_segment_and_distance(TurnPoints const& turn_points
+ , Geometry1 const& geometry1
+ , Geometry2 const& geometry2
+ , Strategy const& strategy
+ , bool& clustered)
+ : m_turn_points(turn_points)
+ , m_geometry1(geometry1)
+ , m_geometry2(geometry2)
+ , m_strategy(strategy)
+ , m_clustered(clustered)
{
- return left.enriched.distance < right.enriched.distance;
}
-protected :
+private :
+ TurnPoints const& m_turn_points;
+ Geometry1 const& m_geometry1;
+ Geometry2 const& m_geometry2;
+ Strategy const& m_strategy;
+ mutable bool& m_clustered;
- // Note that left/right do NOT correspond to m_geometry1/m_geometry2
- inline bool compare_distances(operation_type const& left,
- operation_type const& right) const
+ inline bool consider_relative_order(Indexed const& left,
+ Indexed const& right) const
{
- // TODO: change this, it gives non-consequent behaviour resulting in
- // an assertion within sort.
- // SOLUTION: first sort on distance, then check if the sorted vector
- // has distances close to zero, swap them mutually if there is a reason
- // (reason by sides)
- //if (fuzzy_equals(left.enriched.distance, right.enriched.distance))
- if (false)
- {
+ typedef typename geometry::point_type<Geometry1>::type point_type;
+ point_type pi, pj, ri, rj, si, sj;
- // Distances are the same, or quite close.
- // We sort now using sides instead of using distance
- // In most cases, this is possible. Else we fallback to distance
- // (--> very rare cases, when both methods fail)
-
-#ifdef BOOST_GEOMETRY_DEBUG_OVERLAY
- std::cout << "Equal Distance"
- << " : " << left.seg_id << " / " << left.other_id
- << " and " << right.seg_id << " / " << right.other_id
- << std::endl;
-#endif
-
- point_type pi, pj, ri, rj, si, sj;
- if (left.seg_id == right.seg_id)
- {
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- left.seg_id,
- pi, pj);
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- left.other_id,
- ri, rj);
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- right.other_id,
- si, sj);
- }
- else if (left.other_id == right.other_id)
- {
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- left.other_id,
- pi, pj);
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- left.seg_id,
- ri, rj);
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- right.seg_id,
- si, sj);
- }
- else
- {
- return normal_compare_distances(left, right);
- }
-
- int const order = get_relative_order<point_type>::apply(pi, pj,
- ri, rj, si, sj);
- if (order != 0)
- {
- // If order == -1, r is the first segment along p
- // So then return true;
- return order == -1;
- }
- }
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ left.subject.seg_id,
+ pi, pj);
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ left.subject.other_id,
+ ri, rj);
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ right.subject.other_id,
+ si, sj);
- return normal_compare_distances(left, right);
+ int const order = get_relative_order
+ <
+ point_type
+ >::apply(pi, pj,ri, rj, si, sj);
+ //debug("r/o", order == -1);
+ return order == -1;
}
public :
- sort_on_distance(Geometry1 const& geometry1, Geometry2 const& geometry2,
- Strategy const& strategy)
- : m_geometry1(geometry1)
- , m_geometry2(geometry2)
- , m_strategy(strategy)
- {}
+ // Note that left/right do NOT correspond to m_geometry1/m_geometry2
+ // but to the "indexed_turn_operation"
inline bool operator()(Indexed const& left, Indexed const& right) const
{
- return compare_distances(left.subject, right.subject);
- }
-};
+ segment_identifier const& sl = left.subject.seg_id;
+ segment_identifier const& sr = right.subject.seg_id;
+ if (sl == sr
+ && geometry::math::equals(left.subject.enriched.distance
+ , right.subject.enriched.distance))
+ {
+ // Both left and right are located on the SAME segment.
-template
-<
- typename Indexed,
- typename Geometry1,
- typename Geometry2,
- typename Strategy
->
-struct sort_on_segment_and_distance
- : public sort_on_distance
- <
- Indexed,
- Geometry1, Geometry2, Strategy
- >
-{
- sort_on_segment_and_distance(Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- Strategy const& strategy)
- : sort_on_distance
- <
- Indexed,
- Geometry1, Geometry2, Strategy
- >(geometry1, geometry2, strategy)
- {}
+ // First check "real" intersection (crosses)
+ // -> distance zero due to precision, solve it by sorting
+ if (m_turn_points[left.index].method == method_crosses
+ && m_turn_points[right.index].method == method_crosses)
+ {
+ return consider_relative_order(left, right);
+ }
- inline bool operator()(Indexed const& left, Indexed const& right) const
- {
- segment_identifier const& sl = left.subject.seg_id;
- segment_identifier const& sr = right.subject.seg_id;
+ // If that is not the case, cluster it later on.
+ // Indicate that this is necessary.
+ m_clustered = true;
+ return left.index < right.index;
+ }
return sl == sr
- ? this->compare_distances(left.subject, right.subject)
+ ? left.subject.enriched.distance < right.subject.enriched.distance
: sl < sr;
+
}
};
-template <typename Point, typename Operation, typename Geometry1, typename Geometry2>
-inline bool swap_operations(Operation const& left, Operation const& right,
- Geometry1 const& geometry1, Geometry2 const& geometry2)
+template<typename Turns, typename Operations>
+inline void update_discarded(Turns& turn_points, Operations& operations)
{
- Point pi, pj, ri, rj, si, sj;
- if (left.seg_id == right.seg_id)
- {
- geometry::copy_segment_points(geometry1, geometry2,
- left.seg_id,
- pi, pj);
- geometry::copy_segment_points(geometry1, geometry2,
- left.other_id,
- ri, rj);
- geometry::copy_segment_points(geometry1, geometry2,
- right.other_id,
- si, sj);
- std::cout << "Considering seg" << std::endl;
- }
- else if (left.other_id == right.other_id)
- {
- geometry::copy_segment_points(geometry1, geometry2,
- left.other_id,
- pi, pj);
- geometry::copy_segment_points(geometry1, geometry2,
- left.seg_id,
- ri, rj);
- geometry::copy_segment_points(geometry1, geometry2,
- right.seg_id,
- si, sj);
- std::cout << "Considering other" << std::endl;
- }
- else
+ // Vice-versa, set discarded to true for discarded operations;
+ // AND set discarded points to true
+ for (typename boost::range_iterator<Operations>::type it = boost::begin(operations);
+ it != boost::end(operations);
+ ++it)
{
- return false;
+ if (turn_points[it->index].discarded)
+ {
+ it->discarded = true;
+ }
+ else if (it->discarded)
+ {
+ turn_points[it->index].discarded = true;
+ }
}
-
- int const order = get_relative_order<Point>::apply(pi, pj,
- ri, rj, si, sj);
- std::cout << "Order: " << order << std::endl;
- return order == 1;
}
@@ -257,96 +202,210 @@
typename Geometry2,
typename Strategy
>
-static inline bool enrich(Container& operations,
+inline void enrich_sort(Container& operations,
TurnPoints& turn_points,
+ operation_type for_operation,
Geometry1 const& geometry1, Geometry2 const& geometry2,
Strategy const& strategy)
{
+ typedef typename IndexType::type operations_type;
+
+ bool clustered = false;
std::sort(boost::begin(operations),
boost::end(operations),
sort_on_segment_and_distance
<
+ TurnPoints,
IndexType,
Geometry1, Geometry2,
Strategy
- >(geometry1, geometry2, strategy));
+ >(turn_points, geometry1, geometry2, strategy, clustered));
+ // DONT'T discard xx / (for union) ix / ii / (for intersection) ux / uu here
+ // It would give way to "lonely" ui turn points, traveling all
+ // the way round. See #105
- typedef typename IndexType::type operation_type;
- typedef typename boost::range_iterator<Container const>::type iterator_type;
-
-//#ifdef BOOST_GEOMETRY_DEBUG_OVERLAY
- /***
- // Check if it is really sorted.
- if (operations.size() > 1)
+ if (clustered)
{
typedef typename boost::range_iterator<Container>::type nc_iterator;
nc_iterator it = boost::begin(operations);
+ nc_iterator begin_cluster = boost::end(operations);
for (nc_iterator prev = it++;
it != boost::end(operations);
prev = it++)
{
- operation_type& prev_op = turn_points[prev->index]
+ operations_type& prev_op = turn_points[prev->index]
.operations[prev->operation_index];
- operation_type& op = turn_points[it->index]
+ operations_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,
- op.enriched.distance))
- {
- std::cout << "Equal Distance on "
- << " : " << prev_op.seg_id << " / " << prev_op.other_id
- << " and " << op.seg_id << " / " << op.other_id
- << std::endl;
- std::cout << "\tType of intersections: "
- << operation_char(prev_op.operation)
- << " , " << operation_char(op.operation)
- << std::endl;
- if (swap_operations
- <
- typename point_type<Geometry1>::type
- >(prev_op, op, geometry1, geometry2))
+ if (prev_op.seg_id == op.seg_id
+ && (turn_points[prev->index].method != method_crosses
+ || turn_points[it->index].method != method_crosses)
+ && geometry::math::equals(prev_op.enriched.distance,
+ op.enriched.distance))
+ {
+ if (begin_cluster == boost::end(operations))
{
- std::cout << "Should be swapped" << std::endl;
-
- std::swap(*prev, *it);
+ begin_cluster = prev;
}
- }
+ }
+ else if (begin_cluster != boost::end(operations))
+ {
+ handle_cluster<IndexType>(begin_cluster, it, turn_points,
+ for_operation, geometry1, geometry2, strategy);
+ begin_cluster = boost::end(operations);
+ }
+ }
+ if (begin_cluster != boost::end(operations))
+ {
+ handle_cluster<IndexType>(begin_cluster, it, turn_points,
+ for_operation, geometry1, geometry2, strategy);
}
}
- ***/
-//#endif
+ update_discarded(turn_points, operations);
+}
- // Assign travel-to-vertex/ip index for each turning point.
- // Because IP's are circular, PREV starts at the very last one,
- // being assigned from the first one.
- // For "next ip on same segment" it should not be considered circular.
- bool first = true;
- iterator_type it = boost::begin(operations);
- for (iterator_type prev = it + (boost::size(operations) - 1);
- it != boost::end(operations);
- prev = it++)
- {
- operation_type& prev_op = turn_points[prev->index]
- .operations[prev->operation_index];
- prev_op.enriched.travels_to_ip_index = it->index;
- prev_op.enriched.travels_to_vertex_index
+template
+<
+ typename IndexType,
+ typename Container,
+ typename TurnPoints
+>
+inline void enrich_discard(Container& operations, TurnPoints& turn_points)
+{
+ update_discarded(turn_points, operations);
+
+ // Then delete discarded operations from vector
+ remove_discarded<IndexType> predicate;
+ operations.erase(
+ std::remove_if(boost::begin(operations),
+ boost::end(operations),
+ predicate),
+ boost::end(operations));
+}
+
+template
+<
+ typename IndexType,
+ typename Container,
+ typename TurnPoints,
+ typename Geometry1,
+ typename Geometry2,
+ typename Strategy
+>
+inline void enrich_assign(Container& operations,
+ TurnPoints& turn_points,
+ operation_type for_operation,
+ Geometry1 const& geometry1, Geometry2 const& geometry2,
+ Strategy const& strategy)
+{
+ typedef typename IndexType::type operations_type;
+ typedef typename boost::range_iterator<Container const>::type iterator_type;
+
+
+ if (operations.size() > 0)
+ {
+ // Assign travel-to-vertex/ip index for each turning point.
+ // Because IP's are circular, PREV starts at the very last one,
+ // being assigned from the first one.
+ // "next ip on same segment" should not be considered circular.
+ bool first = true;
+ iterator_type it = boost::begin(operations);
+ for (iterator_type prev = it + (boost::size(operations) - 1);
+ it != boost::end(operations);
+ prev = it++)
+ {
+ operations_type& prev_op
+ = turn_points[prev->index].operations[prev->operation_index];
+ operations_type& op
+ = turn_points[it->index].operations[it->operation_index];
+
+ prev_op.enriched.travels_to_ip_index
+ = it->index;
+ prev_op.enriched.travels_to_vertex_index
= it->subject.seg_id.segment_index;
- operation_type& op = turn_points[it->index]
- .operations[it->operation_index];
+ if (! first
+ && prev_op.seg_id.segment_index == op.seg_id.segment_index)
+ {
+ prev_op.enriched.next_ip_index = it->index;
+ }
+ first = false;
+ }
+ }
- if (! first && prev_op.seg_id.segment_index == op.seg_id.segment_index)
+ // DEBUG
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ {
+ for (iterator_type it = boost::begin(operations);
+ it != boost::end(operations);
+ ++it)
{
- prev_op.enriched.next_ip_index = it->index;
+ operations_type& op = turn_points[it->index]
+ .operations[it->operation_index];
+
+ std::cout << it->index
+ << " meth: " << method_char(turn_points[it->index].method)
+ << " seg: " << op.seg_id
+ << " dst: " << boost::numeric_cast<double>(op.enriched.distance)
+ << " op: " << operation_char(turn_points[it->index].operations[0].operation)
+ << operation_char(turn_points[it->index].operations[1].operation)
+ << " dsc: " << (turn_points[it->index].discarded ? "T" : "F")
+ << " ->vtx " << op.enriched.travels_to_vertex_index
+ << " ->ip " << op.enriched.travels_to_ip_index
+ << " ->nxt ip " << op.enriched.next_ip_index
+ //<< " vis: " << visited_char(op.visited)
+ << std::endl;
+ ;
}
- first = false;
}
+#endif
+ // END DEBUG
- return true;
+}
+
+
+template <typename IndexedType, typename TurnPoints, typename MappedVector>
+inline void create_map(TurnPoints const& turn_points, MappedVector& mapped_vector)
+{
+ 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)
+ {
+ // Add operations on this ring, but skip discarded ones
+ if (! it->discarded)
+ {
+ 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)
+ {
+ // We should NOT skip blocked operations here
+ // because they can be relevant for "the other side"
+ // NOT if (op_it->operation != operation_blocked)
+
+ ring_identifier ring_id
+ (
+ op_it->seg_id.source_index,
+ op_it->seg_id.multi_index,
+ op_it->seg_id.ring_index
+ );
+ mapped_vector[ring_id].push_back
+ (
+ IndexedType(index, op_index, *op_it)
+ );
+ }
+ }
+ }
}
@@ -354,6 +413,7 @@
#endif //DOXYGEN_NO_DETAIL
+
/*!
\brief All intersection points are enriched with successor information
\ingroup overlay
@@ -361,7 +421,7 @@
(e.g. vector of "intersection/turn point"'s)
\tparam Geometry1 \tparam_geometry
\tparam Geometry2 \tparam_geometry
-\tparam Strategy point-point-distance strategy type
+\tparam Strategy side strategy type
\param turn_points container containing intersectionpoints
\param geometry1 \param_geometry
\param geometry2 \param_geometry
@@ -375,61 +435,90 @@
typename Strategy
>
inline void enrich_intersection_points(TurnPoints& turn_points,
+ detail::overlay::operation_type for_operation,
Geometry1 const& geometry1, Geometry2 const& geometry2,
Strategy const& strategy)
{
typedef typename boost::range_value<TurnPoints>::type turn_point_type;
- typedef typename turn_point_type::container_type container_type;
- typedef typename boost::range_value<container_type>::type operation_type;
- typedef detail::overlay::indexed_operation<operation_type> indexed_type;
+ typedef typename turn_point_type::turn_operation_type turn_operation_type;
+ typedef detail::overlay::indexed_turn_operation
+ <
+ turn_operation_type
+ > indexed_turn_operation;
+
typedef std::map
<
ring_identifier,
- std::vector<indexed_type>
+ std::vector<indexed_turn_operation>
> mapped_vector_type;
- // Create a map of vectors of indexed operation-types to be able
- // to sort per ring, later on.
- mapped_vector_type mapped_vector;
-
- int index = 0;
- for (typename boost::range_iterator<TurnPoints const>::type
+ // DISCARD ALL UU
+ // #76 is the reason that this is necessary...
+ // With uu, at all points there is the risk that rings are being traversed twice or more.
+ // Without uu, all rings having only uu will be untouched and gathered by assemble
+ for (typename boost::range_iterator<TurnPoints>::type
it = boost::begin(turn_points);
it != boost::end(turn_points);
- ++it, ++index)
+ ++it)
{
- if (! it->ignore())
+ if (it->both(detail::overlay::operation_union))
{
- 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
- );
- mapped_vector[ring_id].push_back
- (
- indexed_type(index, op_index, *op_it)
- );
- }
+ it->discarded = true;
}
}
- // Note: no const-operator because contents of mapped copy is temporary,
- // and changed by enrich)
+
+ // Create a map of vectors of indexed operation-types to be able
+ // to sort intersection points PER RING
+ mapped_vector_type mapped_vector;
+
+ detail::overlay::create_map<indexed_turn_operation>(turn_points, mapped_vector);
+
+
+ // No const-iterator; contents of mapped copy is temporary,
+ // and changed by enrich
+ for (typename mapped_vector_type::iterator mit
+ = mapped_vector.begin();
+ mit != mapped_vector.end();
+ ++mit)
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << "ENRICH-sort Ring "
+ << mit->first << std::endl;
+#endif
+ detail::overlay::enrich_sort<indexed_turn_operation>(mit->second, turn_points, for_operation,
+ geometry1, geometry2, strategy);
+ }
+
+ for (typename mapped_vector_type::iterator mit
+ = mapped_vector.begin();
+ mit != mapped_vector.end();
+ ++mit)
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << "ENRICH-discard Ring "
+ << mit->first << std::endl;
+#endif
+ detail::overlay::enrich_discard<indexed_turn_operation>(mit->second, turn_points);
+ }
+
for (typename mapped_vector_type::iterator mit
= mapped_vector.begin();
mit != mapped_vector.end();
++mit)
{
- detail::overlay::enrich<indexed_type>(mit->second, turn_points,
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << "ENRICH-assign Ring "
+ << mit->first << std::endl;
+#endif
+ detail::overlay::enrich_assign<indexed_turn_operation>(mit->second, turn_points, for_operation,
geometry1, geometry2, strategy);
}
+
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ //detail::overlay::check_graph(turn_points, for_operation);
+#endif
+
}
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -50,7 +50,6 @@
#include <boost/geometry/algorithms/combine.hpp>
#include <boost/geometry/algorithms/distance.hpp>
#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
-#include <boost/geometry/algorithms/detail/sections/get_section.hpp>
#include <boost/geometry/algorithms/within.hpp>
#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
@@ -90,6 +89,28 @@
>
class get_turns_in_sections
{
+ typedef closeable_view
+ <
+ typename range_type<Geometry1>::type const,
+ closure<Geometry1>::value == open
+ > view_type1;
+ typedef closeable_view
+ <
+ typename range_type<Geometry2>::type const,
+ closure<Geometry2>::value == open
+ > view_type2;
+
+ typedef typename boost::range_iterator
+ <
+ view_type1 const
+ >::type range1_iterator;
+
+ typedef typename boost::range_iterator
+ <
+ view_type2 const
+ >::type range2_iterator;
+
+
public :
// Returns true if terminated, false if interrupted
@@ -99,22 +120,14 @@
Turns& turns,
InterruptPolicy& interrupt_policy)
{
+ view_type1 view1 = get_full_section<view_type1>(geometry1, sec1);
+ view_type2 view2 = get_full_section<view_type2>(geometry2, sec2);
- typedef typename boost::range_iterator
- <
- typename geometry::range_type<Geometry1>::type const
- >::type range1_iterator;
-
- typedef typename boost::range_iterator
- <
- typename geometry::range_type<Geometry2>::type const
- >::type range2_iterator;
-
- range1_iterator begin_range_1, end_range_1;
- get_full_section(geometry1, sec1, begin_range_1, end_range_1);
+ range1_iterator begin_range_1 = boost::begin(view1);
+ range1_iterator end_range_1 = boost::end(view1);
- range2_iterator begin_range_2, end_range_2;
- get_full_section(geometry2, sec2, begin_range_2, end_range_2);
+ range2_iterator begin_range_2 = boost::begin(view2);
+ range2_iterator end_range_2 = boost::end(view2);
int const dir1 = sec1.directions[0];
int const dir2 = sec2.directions[0];
@@ -128,8 +141,8 @@
range1_iterator prev1, it1, end1;
- get_start_point_iterator(sec1, prev1, it1, end1,
- index1, ndi1, geometry1, dir1, sec2.bounding_box);
+ get_start_point_iterator(sec1, view1, prev1, it1, end1,
+ index1, ndi1, dir1, sec2.bounding_box);
// We need a circular iterator because it might run through the closing point.
// One circle is actually enough but this one is just convenient.
@@ -141,7 +154,7 @@
// section 1: |----|---|---|---|---|
for (prev1 = it1++, next1++;
it1 != end1 && ! exceeding<0>(dir1, *prev1, sec2.bounding_box);
- prev1 = it1++, index1++, next1++, ndi1++)
+ ++prev1, ++it1, ++index1, ++next1, ++ndi1)
{
ever_circling_iterator<range1_iterator> nd_next1(
begin_range_1, end_range_1, next1, true);
@@ -152,14 +165,14 @@
range2_iterator prev2, it2, end2;
- get_start_point_iterator(sec2, prev2, it2, end2,
- index2, ndi2, geometry2, dir2, sec1.bounding_box);
+ get_start_point_iterator(sec2, view2, prev2, it2, end2,
+ index2, ndi2, dir2, sec1.bounding_box);
ever_circling_iterator<range2_iterator> next2(begin_range_2, end_range_2, it2, true);
next2++;
for (prev2 = it2++, next2++;
it2 != end2 && ! exceeding<0>(dir2, *prev2, sec1.bounding_box);
- prev2 = it2++, index2++, next2++, ndi2++)
+ ++prev2, ++it2, ++index2, ++next2, ++ndi2)
{
bool skip = same_source;
if (skip)
@@ -268,14 +281,17 @@
// 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
- template <typename RangeIterator, typename Section, typename Geometry, typename Box>
- static inline RangeIterator get_start_point_iterator(Section & section,
- RangeIterator& it, RangeIterator& prev, RangeIterator& end,
+ template <typename Range, typename Section, typename Box>
+ static inline void get_start_point_iterator(Section & section,
+ Range const& range,
+ typename boost::range_iterator<Range const>::type& it,
+ typename boost::range_iterator<Range const>::type& prev,
+ typename boost::range_iterator<Range const>::type& end,
int& index, int& ndi,
- Geometry const& geometry,
int dir, Box const& other_bounding_box)
{
- get_section(geometry, section, it, end);
+ it = boost::begin(range) + section.begin_index;
+ end = boost::begin(range) + section.end_index + 1;
// Mimic section-iterator:
// Skip to point such that section interects other box
@@ -285,7 +301,6 @@
{}
// Go back one step because we want to start completely preceding
it = prev;
- return it;
}
};
Added: sandbox/geometry/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -0,0 +1,620 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_TANGENCIES_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_TANGENCIES_HPP
+
+#include <algorithm>
+
+
+#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
+#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+template
+<
+ typename TurnPoints,
+ typename Indexed,
+ typename Geometry1,
+ typename Geometry2,
+ typename Strategy
+>
+struct sort_in_cluster
+{
+ inline sort_in_cluster(TurnPoints const& turn_points
+ , Geometry1 const& geometry1
+ , Geometry2 const& geometry2
+ , Strategy const& strategy)
+ : m_turn_points(turn_points)
+ , m_geometry1(geometry1)
+ , m_geometry2(geometry2)
+ , m_strategy(strategy)
+ {}
+
+private :
+
+ TurnPoints const& m_turn_points;
+ Geometry1 const& m_geometry1;
+ Geometry2 const& m_geometry2;
+ Strategy const& m_strategy;
+
+ typedef typename Indexed::type turn_operation_type;
+ typedef typename geometry::point_type<Geometry1> point_type;
+
+
+ inline void debug_consider(int order, Indexed const& left,
+ Indexed const& right, std::string const& header,
+ bool skip = true,
+ std::string const& extra = "", bool ret = false
+ ) const
+ {
+ //if (skip) return;
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ typedef typename geometry::point_type<Geometry1>::type point_type;
+ point_type pi, pj, ri, rj, si, sj;
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ left.subject.seg_id,
+ pi, pj);
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ left.subject.other_id,
+ ri, rj);
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ right.subject.other_id,
+ si, sj);
+
+ std::cout << "Case: " << header << " for " << left.index << " / " << right.index << std::endl;
+ std::cout << " Segment p:" << geometry::wkt(pi) << " .. " << geometry::wkt(pj) << std::endl;
+ std::cout << " Segment r:" << geometry::wkt(ri) << " .. " << geometry::wkt(rj) << std::endl;
+ std::cout << " Segment s:" << geometry::wkt(si) << " .. " << geometry::wkt(sj) << std::endl;
+
+ int const side_ri_p = m_strategy.apply(pi, pj, ri);
+ int const side_rj_p = m_strategy.apply(pi, pj, rj);
+ int const side_si_p = m_strategy.apply(pi, pj, si);
+ int const side_sj_p = m_strategy.apply(pi, pj, sj);
+ int const side_si_r = m_strategy.apply(ri, rj, si);
+ int const side_sj_r = m_strategy.apply(ri, rj, sj);
+ std::cout << " r//p: " << side_ri_p << " / " << side_rj_p << std::endl;
+ std::cout << " s//p: " << side_si_p << " / " << side_sj_p << std::endl;
+ std::cout << " s//r: " << side_si_r << " / " << side_sj_r << std::endl;
+
+ std::cout << header << " order: " << order
+ << " ops: " << operation_char(left.subject.operation)
+ << "/" << operation_char(right.subject.operation)
+ << " ri//p: " << side_ri_p
+ << " si//p: " << side_si_p
+ << " si//r: " << side_si_r
+ << " idx: " << left.index << "/" << right.index;
+
+ if (! extra.empty())
+ {
+ std::cout << " " << extra << " " << (ret ? "true" : "false");
+ }
+ std::cout << std::endl;
+#endif
+ }
+
+
+ // ux/ux
+ inline bool consider_ux_ux(Indexed const& left,
+ Indexed const& right
+ , std::string const& header
+ ) const
+ {
+ bool ret = left.index < right.index;
+
+ // In combination of u/x, x/u: take first union, then blocked.
+ // Solves #88, #61, #56, #80
+ if (left.subject.operation == operation_union
+ && right.subject.operation == operation_blocked)
+ {
+ ret = true;
+ }
+ else if (left.subject.operation == operation_blocked
+ && right.subject.operation == operation_union)
+ {
+ ret = false;
+ }
+ else
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << "ux/ux unhandled" << std::endl;
+#endif
+ }
+
+ debug_consider(0, left, right, header, false, "-> return ", ret);
+
+ return ret;
+ }
+
+ inline bool consider_iu_ux(Indexed const& left,
+ Indexed const& right,
+ int order // 1: iu first, -1: ux first
+ , std::string const& header
+ ) const
+ {
+ bool ret = false;
+
+ if (left.subject.operation == operation_union
+ && right.subject.operation == operation_union)
+ {
+ ret = order == 1;
+ }
+ else if (left.subject.operation == operation_union
+ && right.subject.operation == operation_blocked)
+ {
+ ret = true;
+ }
+ else if (right.subject.operation == operation_union
+ && left.subject.operation == operation_blocked)
+ {
+ ret = false;
+ }
+ else if (left.subject.operation == operation_union)
+ {
+ ret = true;
+ }
+ else if (right.subject.operation == operation_union)
+ {
+ ret = false;
+ }
+ else
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << " iu/ux unhandled";
+#endif
+ ret = order == 1;
+ }
+
+ debug_consider(0, left, right, header, false, "-> return", ret);
+ return ret;
+ }
+
+ inline bool consider_iu_ix(Indexed const& left,
+ Indexed const& right,
+ int order // 1: iu first, -1: ix first
+ , std::string const& header
+ ) const
+ {
+ debug_consider(order, left, right, header, false, "iu/ix");
+
+ return left.subject.operation == operation_intersection
+ && right.subject.operation == operation_intersection ? order == 1
+ : left.subject.operation == operation_intersection ? false
+ : right.subject.operation == operation_intersection ? true
+ : order == 1;
+ }
+
+
+ inline bool consider_iu_iu(Indexed const& left, Indexed const& right,
+ std::string const& header) const
+ {
+ debug_consider(0, left, right, header);
+
+ typedef typename geometry::point_type<Geometry1>::type point_type;
+ point_type pi, pj, ri, rj, si, sj;
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ left.subject.seg_id,
+ pi, pj);
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ left.subject.other_id,
+ ri, rj);
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ right.subject.other_id,
+ si, sj);
+
+ int const side_ri_p = m_strategy.apply(pi, pj, ri);
+ int const side_si_p = m_strategy.apply(pi, pj, si);
+ int const side_si_r = m_strategy.apply(ri, rj, si);
+
+ // Both located right (#58)
+ if (side_ri_p == -1 && side_si_p == -1 && side_si_r != 0)
+ {
+ // Take the most left one
+ // Solves #58
+ bool const ret = side_si_r != 1;
+ return ret;
+ }
+
+
+ // Coming from opposite sides (#59, #99)
+ if (side_ri_p * side_si_p == -1)
+ {
+ bool ret = false;
+
+ if (left.subject.operation == operation_intersection
+ && right.subject.operation == operation_union)
+ {
+ // #55_iet_iet: reverse this
+ ret = false;
+ }
+ else if (left.subject.operation == operation_union
+ && right.subject.operation == operation_intersection)
+ {
+ // #55_iet_iet: also.
+ ret = true;
+ }
+ else if (left.subject.operation == operation_union
+ && right.subject.operation == operation_union)
+ {
+ ret = side_ri_p == 1; // #100
+ }
+ else
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << " iu/iu coming from opposite unhandled";
+#endif
+ ret = left.index < right.index;
+ }
+
+ debug_consider(0, left, right, header, false, "coming from opposite", ret);
+ return ret;
+ }
+
+
+ if (side_si_r != 0)
+ {
+ // One coming from right (#83,#90)
+ if ((side_ri_p == 0 && side_si_p == -1)
+ || (side_ri_p == -1 && side_si_p == 0))
+ {
+ bool const ret = side_si_r != 1;
+ return ret;
+ }
+
+ // One coming from left (#90, #94, #95)
+ if ((side_ri_p == 0 && side_si_p == 1)
+ || (side_ri_p == 1 && side_si_p == 0))
+ {
+ bool const ret = side_si_r != -1;
+ return ret;
+ }
+ }
+
+ // All aligned (#92, #96)
+ if (side_ri_p == 0 && side_si_p == 0 && side_si_r == 0)
+ {
+ // Determine how p/r and p/s are located.
+ // One of them is coming from opposite direction.
+ typedef geometry::segment<const point_type> segment_type;
+
+ typedef strategy::intersection::relate_cartesian_segments
+ <
+ policies::relate::segments_intersection_points
+ <
+ segment_type,
+ segment_type,
+ segment_intersection_points<point_type>
+ >
+ > policy;
+
+ segment_type p(pi, pj);
+ segment_type r(ri, rj);
+ segment_type s(si, sj);
+
+ // Get the intersection point (or two points)
+ segment_intersection_points<point_type> pr = policy::apply(p, r);
+ segment_intersection_points<point_type> ps = policy::apply(p, s);
+
+ // Take the one NOT being collinear
+ if (pr.count == 2 && ps.count == 1) return true;
+ if (pr.count == 1 && ps.count == 2) return false;
+
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << "iu/iu all collinear unhandled" << std::endl;
+#endif
+
+ }
+
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << " iu/iu unhandled";
+#endif
+ return left.index < right.index;
+ }
+
+ inline bool consider_ii(Indexed const& left, Indexed const& right,
+ std::string const& header) const
+ {
+ debug_consider(0, left, right, header);
+
+ typedef typename geometry::point_type<Geometry1>::type point_type;
+ point_type pi, pj, ri, rj, si, sj;
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ left.subject.seg_id,
+ pi, pj);
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ left.subject.other_id,
+ ri, rj);
+ geometry::copy_segment_points(m_geometry1, m_geometry2,
+ right.subject.other_id,
+ si, sj);
+
+ int const side_ri_p = m_strategy.apply(pi, pj, ri);
+ int const side_si_p = m_strategy.apply(pi, pj, si);
+
+ // Two other points are (mostly) lying both right of the considered segment
+ // Take the most left one
+ int const side_si_r = m_strategy.apply(ri, rj, si);
+ if (side_ri_p == -1
+ && side_si_p == -1
+ && side_si_r != 0)
+ {
+ bool const ret = side_si_r != 1;
+ return ret;
+ }
+ return left.index < right.index;
+ }
+
+
+public :
+ inline bool operator()(Indexed const& left, Indexed const& right) const
+ {
+ bool const default_order = left.index < right.index;
+
+ if ((m_turn_points[left.index].discarded || left.discarded)
+ && (m_turn_points[right.index].discarded || right.discarded))
+ {
+ return default_order;
+ }
+ else if (m_turn_points[left.index].discarded || left.discarded)
+ {
+ // Be careful to sort discarded first, then all others
+ return true;
+ }
+ else if (m_turn_points[right.index].discarded || right.discarded)
+ {
+ // See above so return false here such that right (discarded)
+ // is sorted before left (not discarded)
+ return false;
+ }
+ else if (m_turn_points[left.index].combination(operation_blocked, operation_union)
+ && m_turn_points[right.index].combination(operation_blocked, operation_union))
+ {
+ // ux/ux
+ return consider_ux_ux(left, right, "ux/ux");
+ }
+ else if (m_turn_points[left.index].both(operation_union)
+ && m_turn_points[right.index].both(operation_union))
+ {
+ // uu/uu, Order is arbitrary
+ // Note: uu/uu is discarded now before so this point will
+ // not be reached.
+ return default_order;
+ }
+ else if (m_turn_points[left.index].combination(operation_intersection, operation_union)
+ && m_turn_points[right.index].combination(operation_intersection, operation_union))
+ {
+ return consider_iu_iu(left, right, "iu/iu");
+ }
+ else if (m_turn_points[left.index].both(operation_intersection)
+ && m_turn_points[right.index].both(operation_intersection))
+ {
+ return consider_ii(left, right, "ii/ii");
+ }
+ else if (m_turn_points[left.index].combination(operation_union, operation_blocked)
+ && m_turn_points[right.index].combination(operation_intersection, operation_union))
+ {
+ return consider_iu_ux(left, right, -1, "ux/iu");
+ }
+ else if (m_turn_points[left.index].combination(operation_intersection, operation_union)
+ && m_turn_points[right.index].combination(operation_union, operation_blocked))
+ {
+ return consider_iu_ux(left, right, 1, "iu/ux");
+ }
+ else if (m_turn_points[left.index].combination(operation_intersection, operation_blocked)
+ && m_turn_points[right.index].combination(operation_intersection, operation_union))
+ {
+ return consider_iu_ix(left, right, 1, "ix/iu");
+ }
+ else if (m_turn_points[left.index].combination(operation_intersection, operation_union)
+ && m_turn_points[right.index].combination(operation_intersection, operation_blocked))
+ {
+ return consider_iu_ix(left, right, -1, "iu/ix");
+ }
+ else if (m_turn_points[left.index].method != method_equal
+ && m_turn_points[right.index].method == method_equal
+ )
+ {
+ // If one of them was EQUAL or CONTINUES, it should always come first
+ return false;
+ }
+ else if (m_turn_points[left.index].method == method_equal
+ && m_turn_points[right.index].method != method_equal
+ )
+ {
+ return true;
+ }
+
+ // Now we have no clue how to sort.
+
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << " Consider: " << operation_char(m_turn_points[left.index].operations[0].operation)
+ << operation_char(m_turn_points[left.index].operations[1].operation)
+ << "/" << operation_char(m_turn_points[right.index].operations[0].operation)
+ << operation_char(m_turn_points[right.index].operations[1].operation)
+ << " " << " Take " << left.index << " < " << right.index;
+#endif
+
+ return default_order;
+ }
+};
+
+
+
+template
+<
+ typename IndexType,
+ typename Iterator,
+ typename TurnPoints,
+ typename Geometry1,
+ typename Geometry2,
+ typename Strategy
+>
+inline void inspect_cluster(Iterator begin_cluster, Iterator end_cluster,
+ TurnPoints& turn_points,
+ operation_type for_operation,
+ Geometry1 const& geometry1, Geometry2 const& geometry2,
+ Strategy const& strategy)
+{
+ int count = 0;
+
+ // Make an analysis about all occuring cases here.
+ std::map<std::pair<operation_type, operation_type>, int> inspection;
+ for (Iterator it = begin_cluster; it != end_cluster; ++it)
+ {
+ operation_type first = turn_points[it->index].operations[0].operation;
+ operation_type second = turn_points[it->index].operations[1].operation;
+ if (first > second)
+ {
+ std::swap(first, second);
+ }
+ inspection[std::make_pair(first, second)]++;
+ count++;
+ }
+
+
+ bool keep_cc = false;
+
+ // Decide about which is going to be discarded here.
+ if (inspection[std::make_pair(operation_union, operation_union)] == 1
+ && inspection[std::make_pair(operation_continue, operation_continue)] == 1)
+ {
+ // In case of uu/cc, discard the uu, that indicates a tangency and
+ // inclusion would disturb the (e.g.) cc-cc-cc ordering
+ // NOTE: uu is now discarded anyhow.
+ keep_cc = true;
+ }
+ else if (count == 2
+ && inspection[std::make_pair(operation_intersection, operation_intersection)] == 1
+ && inspection[std::make_pair(operation_union, operation_intersection)] == 1)
+ {
+ // In case of ii/iu, discard the iu. The ii should always be visited,
+ // Because (in case of not discarding iu) correctly ordering of ii/iu appears impossible
+ for (Iterator it = begin_cluster; it != end_cluster; ++it)
+ {
+ if (turn_points[it->index].combination(operation_intersection, operation_union))
+ {
+ it->discarded = true;
+ }
+ }
+ }
+
+ // Discard any continue turn, unless it is the only thing left
+ // (necessary to avoid cc-only rings, all being discarded
+ // e.g. traversal case #75)
+ int nd_count= 0, cc_count = 0;
+ for (Iterator it = begin_cluster; it != end_cluster; ++it)
+ {
+ if (! it->discarded)
+ {
+ nd_count++;
+ if (turn_points[it->index].both(operation_continue))
+ {
+ cc_count++;
+ }
+ }
+ }
+
+ if (nd_count == cc_count)
+ {
+ keep_cc = true;
+ }
+
+ if (! keep_cc)
+ {
+ for (Iterator it = begin_cluster; it != end_cluster; ++it)
+ {
+ if (turn_points[it->index].both(operation_continue))
+ {
+ it->discarded = true;
+ }
+ }
+ }
+}
+
+
+template
+<
+ typename IndexType,
+ typename Iterator,
+ typename TurnPoints,
+ typename Geometry1,
+ typename Geometry2,
+ typename Strategy
+>
+inline void handle_cluster(Iterator begin_cluster, Iterator end_cluster,
+ TurnPoints& turn_points,
+ operation_type for_operation,
+ Geometry1 const& geometry1, Geometry2 const& geometry2,
+ Strategy const& strategy)
+{
+ // First inspect and (possibly) discard rows
+ inspect_cluster<IndexType>(begin_cluster, end_cluster, turn_points,
+ for_operation, geometry1, geometry2, strategy);
+
+
+ // Then sort this range (discard rows will be ordered first and will be removed in enrich_assign)
+ std::sort(begin_cluster, end_cluster,
+ sort_in_cluster
+ <
+ TurnPoints,
+ IndexType,
+ Geometry1, Geometry2,
+ Strategy
+ >(turn_points, geometry1, geometry2, strategy));
+
+
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ typedef typename IndexType::type operations_type;
+ operations_type const& op = turn_points[begin_cluster->index].operations[begin_cluster->operation_index];
+ std::cout << "Clustered points on equal distance " << op.enriched.distance << std::endl;
+ std::cout << "->Indexes ";
+
+ for (Iterator it = begin_cluster; it != end_cluster; ++it)
+ {
+ std::cout << " " << it->index;
+ }
+ std::cout << std::endl << "->Methods: ";
+ for (Iterator it = begin_cluster; it != end_cluster; ++it)
+ {
+ std::cout << " " << method_char(turn_points[it->index].method);
+ }
+ std::cout << std::endl << "->Operations: ";
+ for (Iterator it = begin_cluster; it != end_cluster; ++it)
+ {
+ std::cout << " " << operation_char(turn_points[it->index].operations[0].operation)
+ << operation_char(turn_points[it->index].operations[1].operation);
+ }
+ std::cout << std::endl << "->Discarded: ";
+ for (Iterator it = begin_cluster; it != end_cluster; ++it)
+ {
+ std::cout << " " << (it->discarded ? "true" : "false");
+ }
+ std::cout << std::endl;
+ //<< "\tOn segments: " << prev_op.seg_id << " / " << prev_op.other_id
+ //<< " and " << op.seg_id << " / " << op.other_id
+ //<< geometry::distance(turn_points[prev->index].point, turn_points[it->index].point)
+#endif
+
+}
+
+
+}} // namespace detail::overlay
+#endif //DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_TANGENCIES_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/overlay.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/overlay.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/overlay.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -112,7 +112,11 @@
std::cout << "enrich" << std::endl;
#endif
typename Strategy::side_strategy_type side_strategy;
- geometry::enrich_intersection_points(turn_points, geometry1, geometry2,
+ geometry::enrich_intersection_points(turn_points,
+ Direction == -1
+ ? boost::geometry::detail::overlay::operation_intersection
+ : boost::geometry::detail::overlay::operation_union,
+ geometry1, geometry2,
side_strategy);
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/ring_properties.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/ring_properties.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/ring_properties.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -69,7 +69,7 @@
{
has_point = geometry::point_on_border(point, geometry, true);
typedef typename coordinate_type<Geometry>::type coordinate_type;
- coordinate_type zero = coordinate_type();
+ coordinate_type const zero = coordinate_type();
signum = area > zero ? 1 : area < zero ? -1 : 0;
parent_ring_id.source_index = -1;
}
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -24,11 +24,9 @@
#include <boost/geometry/core/interior_rings.hpp>
#include <boost/geometry/util/math.hpp>
-
#include <boost/geometry/algorithms/intersects.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
-#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/traverse.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/traverse.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/traverse.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -36,6 +36,25 @@
namespace detail { namespace overlay
{
+template <typename Turn, typename Operation>
+inline void debug_traverse(Turn const& turn, Operation op, std::string const& header)
+{
+#ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
+ std::cout << header
+ << " at " << op.seg_id
+ << " op: " << operation_char(op.operation)
+ << " vis: " << visited_char(op.visited)
+ << " of: " << operation_char(turn.operations[0].operation)
+ << operation_char(turn.operations[1].operation)
+ << std::endl;
+
+ if (boost::contains(header, "Finished"))
+ {
+ std::cout << std::endl;
+ }
+#endif
+}
+
template <typename Turns>
inline void clear_visit_info(Turns& turns)
@@ -56,6 +75,7 @@
{
op_it->visited.clear();
}
+ it->discarded = false;
}
}
@@ -91,11 +111,11 @@
typename Turns,
typename IntersectionInfo
>
-inline void assign_next_ip(G1 const& g1, G2 const& g2,
+inline bool assign_next_ip(G1 const& g1, G2 const& g2,
Turns& turns,
- typename boost::range_iterator<Turns>::type & ip,
+ typename boost::range_iterator<Turns>::type& ip,
GeometryOut& current_output,
- IntersectionInfo & info,
+ IntersectionInfo& info,
segment_identifier& seg_id)
{
info.visited.set_visited();
@@ -104,6 +124,11 @@
// If there is no next IP on this segment
if (info.enriched.next_ip_index < 0)
{
+ if (info.enriched.travels_to_vertex_index < 0 || info.enriched.travels_to_ip_index < 0) return false;
+
+ BOOST_ASSERT(info.enriched.travels_to_vertex_index >= 0);
+ BOOST_ASSERT(info.enriched.travels_to_ip_index >= 0);
+
if (info.seg_id.source_index == 0)
{
geometry::copy_segments<Order>(g1, info.seg_id,
@@ -116,8 +141,8 @@
info.enriched.travels_to_vertex_index,
current_output);
}
- ip = boost::begin(turns) + info.enriched.travels_to_ip_index;
seg_id = info.seg_id;
+ ip = boost::begin(turns) + info.enriched.travels_to_ip_index;
}
else
{
@@ -126,12 +151,15 @@
}
geometry::append(current_output, ip->point);
+ return true;
}
inline bool select_source(operation_type operation, int source1, int source2)
{
- return operation == operation_intersection && source1 != source2;
+ return (operation == operation_intersection && source1 != source2)
+ || (operation == operation_union && source1 == source2)
+ ;
}
@@ -145,23 +173,35 @@
segment_identifier const& seg_id,
Iterator& selected)
{
+ if (turn.discarded)
+ {
+ return false;
+ }
bool has_tp = false;
selected = boost::end(turn.operations);
for (Iterator it = boost::begin(turn.operations);
it != boost::end(turn.operations);
++it)
{
+ if (it->visited.started())
+ {
+ selected = it;
+ //std::cout << " RETURN";
+ return true;
+ }
+
// In some cases there are two alternatives.
// For "ii", take the other one (alternate)
+ // UNLESS the other one is already visited
// For "uu", take the same one (see above);
// For "cc", take either one, but if there is a starting one,
// take that one.
if ( (it->operation == operation_continue
- && (! has_tp
- || it->visited.started()
+ && (! has_tp || it->visited.started()
)
)
|| (it->operation == operation
+ && ! it->visited.finished()
&& (! has_tp
|| select_source(operation,
it->seg_id.source_index, seg_id.source_index)
@@ -170,16 +210,17 @@
)
{
selected = it;
+ debug_traverse(turn, *it, " Candidate");
has_tp = true;
}
+ }
- if (it->visited.started())
- {
- selected = it;
- return true;
- }
+ if (has_tp)
+ {
+ debug_traverse(turn, *selected, " Accepted");
}
+
return has_tp;
}
@@ -208,6 +249,9 @@
#endif
)
{
+#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+ std::cout << " REJECT " << reason << std::endl;
+#endif
fail = true;
// Make bad output clean
@@ -287,8 +331,8 @@
! fail && it != boost::end(turns);
++it)
{
- // Skip the self-tangent ones (uu)
- if (! it->ignore())
+ // Skip discarded ones
+ if (! (it->is_discarded() || it->blocked()))
{
for (turn_operation_iterator_type iit = boost::begin(it->operations);
! fail && iit != boost::end(it->operations);
@@ -309,16 +353,22 @@
turn_operation_iterator_type current_iit = iit;
segment_identifier current_seg_id;
- detail::overlay::assign_next_ip<Order>(geometry1, geometry2,
+ if (! detail::overlay::assign_next_ip<Order>(geometry1, geometry2,
turns,
current, current_output,
- *iit, current_seg_id);
+ *iit, current_seg_id))
+ {
+ detail::overlay::backtrack(
+ size_at_start, fail,
+ rings, current_output, turns, *current_iit,
+ "No next IP",
+ geometry1, geometry2);
+ }
if (! detail::overlay::select_next_ip(
operation,
*current,
current_seg_id,
-
current_iit))
{
detail::overlay::backtrack(
@@ -331,6 +381,9 @@
{
iit->visited.set_started();
+ detail::overlay::debug_traverse(*it, *iit, "-> Started");
+ detail::overlay::debug_traverse(*current, *current_iit, "Selected ");
+
unsigned int i = 0;
@@ -368,7 +421,6 @@
operation,
*current,
current_seg_id,
-
current_iit))
{
// Should not occur in valid (non-self-intersecting) polygons
@@ -380,11 +432,13 @@
"Dead end",
geometry1, geometry2);
}
+ detail::overlay::debug_traverse(*current, *current_iit, "Selected ");
- if (i++ > turns.size())
+ if (i++ > 2 + 2 * turns.size())
{
// Sanity check: there may be never more loops
- // than intersection points.
+ // than turn points.
+ // Turn points marked as "ii" can be visited twice.
detail::overlay::backtrack(
size_at_start, fail,
rings, current_output, turns, *iit,
@@ -397,6 +451,7 @@
if (! fail)
{
iit->visited.set_finished();
+ detail::overlay::debug_traverse(*current, *iit, "->Finished");
rings.push_back(current_output);
}
}
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -58,7 +58,7 @@
segment_identifier seg_id;
segment_identifier other_id;
- turn_operation()
+ inline turn_operation()
: operation(operation_none)
{}
};
@@ -82,22 +82,50 @@
struct turn_info
{
typedef Point point_type;
- typedef Operation operation_type;
+ typedef Operation turn_operation_type;
typedef Container container_type;
Point point;
method_type method;
+ bool discarded;
+
Container operations;
inline turn_info()
: method(method_none)
+ , discarded(false)
{}
- inline bool ignore() const
+ inline bool both(operation_type type) const
+ {
+ return has12(type, type);
+ }
+
+ inline bool combination(operation_type type1, operation_type type2) const
+ {
+ return has12(type1, type2) || has12(type2, type1);
+ }
+
+
+ inline bool is_discarded() const { return discarded; }
+ inline bool blocked() const
+ {
+ return both(operation_blocked);
+ }
+ inline bool any_blocked() const
+ {
+ return this->operations[0].operation == operation_blocked
+ || this->operations[1].operation == operation_blocked;
+ }
+
+
+private :
+ inline bool has12(operation_type type1, operation_type type2) const
{
- return this->operations[0].operation == operation_union
- && this->operations[1].operation == operation_union;
+ return this->operations[0].operation == type1
+ && this->operations[1].operation == type2
+ ;
}
};
Modified: sandbox/geometry/boost/geometry/algorithms/detail/ring_identifier.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/ring_identifier.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/ring_identifier.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -27,8 +27,7 @@
: source_index(src)
, multi_index(mul)
, ring_index(rin)
- {
- }
+ {}
inline bool operator<(ring_identifier const& other) const
{
Modified: sandbox/geometry/boost/geometry/algorithms/detail/sections/get_full_section.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/sections/get_full_section.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/sections/get_full_section.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -8,17 +8,16 @@
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_GET_FULL_SECTION_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_GET_FULL_SECTION_HPP
+// TODO rename to "range_by_section"
#include <boost/mpl/assert.hpp>
#include <boost/range.hpp>
#include <boost/geometry/core/access.hpp>
+#include <boost/geometry/core/closure.hpp>
#include <boost/geometry/core/exterior_ring.hpp>
#include <boost/geometry/core/interior_rings.hpp>
-
-#include <boost/geometry/iterators/range_type.hpp>
-
-#include <boost/geometry/geometries/segment.hpp>
+#include <boost/geometry/util/closeable_view.hpp>
@@ -30,31 +29,42 @@
{
-template <typename Range, typename Section, typename Iterator>
+
+
+template <typename Range, typename Section>
struct full_section_range
{
- static inline void apply(Range const& range, Section const& section,
- Iterator& begin, Iterator& end)
+ typedef closeable_view
+ <
+ Range const,
+ closure<Range>::value == open // close it if it is open
+ > view_type;
+
+ static inline view_type apply(Range const& range, Section const& section)
{
- begin = boost::begin(range);
- end = boost::end(range);
+ return view_type(range);
}
};
-template <typename Polygon, typename Section, typename Iterator>
+template <typename Polygon, typename Section>
struct full_section_polygon
{
- static inline void apply(Polygon const& polygon, Section const& section,
- Iterator& begin, Iterator& end)
+ typedef typename geometry::ring_type<Polygon>::type ring_type;
+ typedef closeable_view
+ <
+ ring_type const,
+ closure<ring_type>::value == open // close it if it is open
+ > view_type;
+
+ static inline view_type apply(Polygon const& polygon, Section const& section)
{
- typedef typename geometry::ring_type<Polygon>::type ring_type;
+
ring_type const& ring = section.ring_index < 0
? geometry::exterior_ring(polygon)
: geometry::interior_rings(polygon)[section.ring_index];
- begin = boost::begin(ring);
- end = boost::end(ring);
+ return view_type(ring);
}
};
@@ -72,8 +82,7 @@
<
typename Tag,
typename Geometry,
- typename Section,
- typename Iterator
+ typename Section
>
struct get_full_section
{
@@ -85,21 +94,21 @@
};
-template <typename LineString, typename Section, typename Iterator>
-struct get_full_section<linestring_tag, LineString, Section, Iterator>
- : detail::section::full_section_range<LineString, Section, Iterator>
+template <typename LineString, typename Section>
+struct get_full_section<linestring_tag, LineString, Section>
+ : detail::section::full_section_range<LineString, Section>
{};
-template <typename Ring, typename Section, typename Iterator>
-struct get_full_section<ring_tag, Ring, Section, Iterator>
- : detail::section::full_section_range<Ring, Section, Iterator>
+template <typename Ring, typename Section>
+struct get_full_section<ring_tag, Ring, Section>
+ : detail::section::full_section_range<Ring, Section>
{};
-template <typename Polygon, typename Section, typename Iterator>
-struct get_full_section<polygon_tag, Polygon, Section, Iterator>
- : detail::section::full_section_polygon<Polygon, Section, Iterator>
+template <typename Polygon, typename Section>
+struct get_full_section<polygon_tag, Polygon, Section>
+ : detail::section::full_section_polygon<Polygon, Section>
{};
@@ -108,42 +117,28 @@
/*!
- \brief Get iterators for a specified section
+ \brief Get a closeable view indicated by the specified section
\ingroup sectionalize
\tparam Geometry type
\tparam Section type of section to get from
- \param geometry geometry which might be located in the neighborhood
+ \param geometry geometry to take section of
\param section structure with section
\param begin begin-iterator (const iterator over points of section)
\param end end-iterator (const iterator over points of section)
\todo Create non-const version as well
*/
-template <typename Geometry, typename Section>
-inline void get_full_section(Geometry const& geometry, Section const& section,
- typename boost::range_iterator
- <
- typename geometry::range_type<Geometry>::type const
- >::type& begin,
- typename boost::range_iterator
- <
- typename geometry::range_type<Geometry>::type const
- >::type& end)
+template <typename Range, typename Geometry, typename Section>
+inline Range get_full_section(Geometry const& geometry, Section const& section)
{
concept::check<Geometry const>();
- typedef typename boost::range_iterator
- <
- typename geometry::range_type<Geometry>::type const
- >::type iterator_type;
-
- dispatch::get_full_section
+ return dispatch::get_full_section
<
typename tag<Geometry>::type,
Geometry,
- Section,
- iterator_type
- >::apply(geometry, section, begin, end);
+ Section
+ >::apply(geometry, section);
}
Modified: sandbox/geometry/boost/geometry/algorithms/detail/sections/get_section.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/sections/get_section.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/sections/get_section.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -9,14 +9,11 @@
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_GET_SECTION_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_GET_SECTION_HPP
+// OBSOLETE
-#include <boost/range.hpp>
+/***
-#include <boost/geometry/core/access.hpp>
-#include <boost/geometry/core/exterior_ring.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
-#include <boost/geometry/iterators/range_type.hpp>
-#include <boost/geometry/util/add_const_if_c.hpp>
+#include <boost/range.hpp>
@@ -24,134 +21,38 @@
{
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-// Generic case (linestring/linear ring)
-template <typename Tag, typename Geometry, typename Section, bool IsConst>
-struct get_section
-{
- typedef typename add_const_if_c
- <
- IsConst,
- Geometry
- >::type geometry_type;
-
- typedef typename boost::range_iterator
- <
- typename add_const_if_c
- <
- IsConst,
- typename geometry::range_type<Geometry>::type
- >::type
- >::type iterator_type;
-
- static inline void apply(geometry_type& geometry, Section const& section,
- iterator_type& begin, iterator_type& end)
- {
- begin = boost::begin(geometry) + section.begin_index;
- end = boost::begin(geometry) + section.end_index + 1;
- }
-};
-
-template <typename Polygon, typename Section, bool IsConst>
-struct get_section<polygon_tag, Polygon, Section, IsConst>
-{
- typedef typename add_const_if_c
- <
- IsConst,
- Polygon
- >::type polygon_type;
-
- typedef typename boost::range_iterator
- <
- typename add_const_if_c
- <
- IsConst,
- typename geometry::range_type<Polygon>::type
- >::type
- >::type iterator_type;
-
- static inline void apply(polygon_type& polygon, Section const& section,
- iterator_type& begin, iterator_type& end)
- {
- typename add_const_if_c
- <
- IsConst,
- typename geometry::ring_type<Polygon>::type
- >::type& ring = section.ring_index < 0
- ? geometry::exterior_ring(polygon)
- : geometry::interior_rings(polygon)[section.ring_index];
-
- begin = boost::begin(ring) + section.begin_index;
- end = boost::begin(ring) + section.end_index + 1;
- }
-};
-
-
-} // namespace dispatch
-#endif
-
-/*!
\brief Get iterators for a specified section
\ingroup sectionalize
- \tparam Geometry type
+ \tparam Range type
\tparam Section type of section to get from
- \param geometry geometry which might be located in the neighborhood
+ \param range range (retrieved by "range_by_section") to take section of
\param section structure with section
\param begin begin-iterator (const iterator over points of section)
\param end end-iterator (const iterator over points of section)
- */
-template <typename Geometry, typename Section>
-inline void get_section(Geometry const& geometry, Section const& section,
- typename boost::range_iterator
- <
- typename geometry::range_type<Geometry>::type const
- >::type& begin,
- typename boost::range_iterator
- <
- typename geometry::range_type<Geometry>::type const
- >::type& end)
-{
- concept::check<Geometry const>();
- dispatch::get_section
- <
- typename tag<Geometry>::type,
- Geometry,
- Section,
- true
- >::apply(geometry, section, begin, end);
+template <typename Range, typename Section>
+inline void get_section(Range const& range, Section const& section,
+ typename boost::range_iterator<Range const>::type& begin,
+ typename boost::range_iterator<Range const>::type& end)
+{
+ begin = boost::begin(range) + section.begin_index;
+ end = boost::begin(range) + section.end_index + 1;
}
// non const version
-template <typename Geometry, typename Section>
-inline void get_section(Geometry& geometry, Section const& section,
- typename boost::range_iterator
- <
- typename geometry::range_type<Geometry>::type
- >::type& begin,
- typename boost::range_iterator
- <
- typename geometry::range_type<Geometry>::type
- >::type& end)
+template <typename Range, typename Section>
+inline void get_section(Range& range, Section const& section,
+ typename boost::range_iterator<Range>::type& begin,
+ typename boost::range_iterator<Range>::type& end)
{
- concept::check<Geometry>();
-
- dispatch::get_section
- <
- typename tag<Geometry>::type,
- Geometry,
- Section,
- false
- >::apply(geometry, section, begin, end);
+ begin = boost::begin(range) + section.begin_index;
+ end = boost::begin(range) + section.end_index + 1;
}
-
}} // namespace boost::geometry
+****/
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_GET_SECTION_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/sections/sectionalize.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/sections/sectionalize.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/sections/sectionalize.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -19,12 +19,14 @@
#include <boost/geometry/algorithms/combine.hpp>
#include <boost/geometry/core/access.hpp>
+#include <boost/geometry/core/closure.hpp>
#include <boost/geometry/core/exterior_ring.hpp>
+#include <boost/geometry/core/point_order.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
-
#include <boost/geometry/util/math.hpp>
+#include <boost/geometry/util/closeable_view.hpp>
#include <boost/geometry/geometries/segment.hpp>
@@ -186,7 +188,8 @@
coordinate_type const diff =
geometry::get<1, Dimension>(seg) - geometry::get<0, Dimension>(seg);
- if (! geometry::math::equals(diff, 0))
+ coordinate_type const zero = 0;
+ if (! geometry::math::equals(diff, zero))
{
return false;
}
@@ -228,7 +231,7 @@
/// @brief Helper class to create sections of a part of a range, on the fly
template
<
- typename Range,
+ typename Range, // Can be closeable_view
typename Point,
typename Sections,
std::size_t DimensionCount,
@@ -238,6 +241,7 @@
{
typedef geometry::segment<Point const> segment_type;
typedef typename boost::range_value<Sections>::type section_type;
+
typedef typename boost::range_iterator<Range const>::type iterator_type;
static inline void apply(Sections& sections, section_type& section,
@@ -260,7 +264,7 @@
for(iterator_type previous = it++;
it != boost::end(range);
- previous = it++, index++)
+ ++previous, ++it, index++)
{
segment_type segment(*previous, *it);
@@ -341,7 +345,7 @@
template
<
- typename Range,
+ typename Range, closure_selector Closure,
typename Point,
typename Sections,
std::size_t DimensionCount,
@@ -349,12 +353,20 @@
>
struct sectionalize_range
{
+ typedef closeable_view
+ <
+ Range const,
+ Closure == open // close it if it is open
+ > view_type;
+
static inline void apply(Range const& range, Sections& sections,
int ring_index = -1, int multi_index = -1)
{
typedef segment<Point const> segment_type;
- std::size_t const n = boost::size(range);
+ view_type view(range);
+
+ std::size_t const n = boost::size(view);
if (n == 0)
{
// Zero points, no section
@@ -375,10 +387,10 @@
sectionalize_part
<
- Range, Point, Sections,
+ view_type, Point, Sections,
DimensionCount, MaxCount
>::apply(sections, section, index, ndi,
- range, ring_index, multi_index);
+ view, ring_index, multi_index);
// Add last section if applicable
if (section.count > 0)
@@ -404,7 +416,8 @@
typedef typename ring_type<Polygon>::type ring_type;
typedef sectionalize_range
<
- ring_type, point_type, Sections, DimensionCount, MaxCount
+ ring_type, closure<Polygon>::value,
+ point_type, Sections, DimensionCount, MaxCount
> sectionalizer_type;
typedef typename boost::range_iterator
@@ -457,7 +470,7 @@
sectionalize_range
<
- std::vector<point_type>,
+ std::vector<point_type>, closed,
point_type,
Sections,
DimensionCount,
@@ -539,7 +552,7 @@
>
: detail::sectionalize::sectionalize_range
<
- LineString,
+ LineString, closed,
typename point_type<LineString>::type,
Sections,
DimensionCount,
@@ -549,16 +562,16 @@
template
<
- typename Range,
+ typename Ring,
typename Sections,
std::size_t DimensionCount,
std::size_t MaxCount
>
-struct sectionalize<ring_tag, Range, Sections, DimensionCount, MaxCount>
+struct sectionalize<ring_tag, Ring, Sections, DimensionCount, MaxCount>
: detail::sectionalize::sectionalize_range
<
- Range,
- typename point_type<Range>::type,
+ Ring, geometry::closure<Ring>::value,
+ typename point_type<Ring>::type,
Sections,
DimensionCount,
MaxCount
Modified: sandbox/geometry/boost/geometry/algorithms/dissolve.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/dissolve.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/dissolve.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -76,18 +76,26 @@
typename cs_tag<Geometry>::type
>::type side_strategy_type;
- enrich_intersection_points(turns, geometry, geometry,
+ enrich_intersection_points(turns,
+ detail::overlay::operation_union,
+ geometry, geometry,
side_strategy_type());
// Traverse the polygons twice in two different directions
- traverse<point_order<Geometry>::value>(geometry, geometry,
+ traverse<point_order<Geometry>::value>(geometry, geometry,
detail::overlay::operation_union,
turns, rings);
clear_visit_info(turns);
- traverse<point_order<Geometry>::value>(geometry, geometry,
+ enrich_intersection_points(turns,
+ detail::overlay::operation_intersection,
+ geometry, geometry,
+ side_strategy_type());
+
+
+ traverse<point_order<Geometry>::value>(geometry, geometry,
detail::overlay::operation_intersection,
turns, rings);
Modified: sandbox/geometry/boost/geometry/algorithms/num_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/num_points.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/num_points.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -14,9 +14,13 @@
#include <boost/mpl/assert.hpp>
#include <boost/range.hpp>
+#include <boost/geometry/core/closure.hpp>
#include <boost/geometry/core/is_linear.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/algorithms/disjoint.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
@@ -31,16 +35,29 @@
template <typename Range>
struct range_count
{
- static inline std::size_t apply(Range const& range)
+ static inline std::size_t apply(Range const& range, bool add_for_open)
{
- return boost::size(range);
+ std::size_t n = boost::size(range);
+ if (add_for_open)
+ {
+ closure_selector const s = geometry::closure<Range>::value;
+
+ if (s == open)
+ {
+ if (geometry::disjoint(*boost::begin(range), *(boost::begin(range) + n - 1)))
+ {
+ return n + 1;
+ }
+ }
+ }
+ return n;
}
};
template <typename Geometry, std::size_t D>
struct other_count
{
- static inline std::size_t apply(Geometry const& )
+ static inline std::size_t apply(Geometry const&, bool)
{
return D;
}
@@ -49,9 +66,13 @@
template <typename Polygon>
struct polygon_count
{
- static inline std::size_t apply(Polygon const& poly)
+ static inline std::size_t apply(Polygon const& poly, bool add_for_open)
{
- std::size_t n = boost::size(exterior_ring(poly));
+ typedef typename geometry::ring_type<Polygon>::type ring_type;
+
+ std::size_t n = range_count<ring_type>::apply(
+ exterior_ring(poly), add_for_open);
+
typedef typename boost::range_iterator
<
typename interior_type<Polygon>::type const
@@ -61,7 +82,7 @@
it != boost::end(interior_rings(poly));
++it)
{
- n += boost::size(*it);
+ n += range_count<ring_type>::apply(*it, add_for_open);
}
return n;
@@ -138,7 +159,7 @@
\qbk{compliance,__ogc__}
*/
template <typename Geometry>
-inline std::size_t num_points(Geometry const& geometry)
+inline std::size_t num_points(Geometry const& geometry, bool add_for_open = false)
{
concept::check<Geometry const>();
@@ -147,7 +168,7 @@
typename tag<Geometry>::type,
is_linear<Geometry>::value,
Geometry
- >::apply(geometry);
+ >::apply(geometry, add_for_open);
}
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/algorithms/transform.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/transform.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/transform.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -167,16 +167,16 @@
template <typename Point1, typename Point2>
struct select_strategy
{
- typedef typename strategy_transform
+ typedef typename strategy::transform::services::default_strategy
<
- typename cs_tag<Point1>::type,
- typename cs_tag<Point2>::type,
- typename coordinate_system<Point1>::type,
- typename coordinate_system<Point2>::type,
- dimension<Point1>::type::value,
- dimension<Point2>::type::value,
- typename point_type<Point1>::type,
- typename point_type<Point2>::type
+ typename cs_tag<Point1>::type,
+ typename cs_tag<Point2>::type,
+ typename coordinate_system<Point1>::type,
+ typename coordinate_system<Point2>::type,
+ dimension<Point1>::type::value,
+ dimension<Point2>::type::value,
+ typename point_type<Point1>::type,
+ typename point_type<Point2>::type
>::type type;
};
Modified: sandbox/geometry/boost/geometry/algorithms/within.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/within.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/within.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -25,7 +25,7 @@
#include <boost/geometry/core/point_order.hpp>
#include <boost/geometry/core/ring_type.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/strategies/point_in_poly.hpp>
+#include <boost/geometry/strategies/within.hpp>
#include <boost/geometry/strategies/concepts/within_concept.hpp>
#include <boost/geometry/util/order_as_direction.hpp>
#include <boost/geometry/util/closeable_view.hpp>
@@ -55,14 +55,14 @@
>
struct point_in_box
{
- static inline bool apply(Point const& p, Box const& b, Strategy const& s)
+ static inline int apply(Point const& p, Box const& b, Strategy const& s)
{
assert_dimension_equal<Point, Box>();
if (get<Dimension>(p) <= get<min_corner, Dimension>(b)
|| get<Dimension>(p) >= get<max_corner, Dimension>(b))
{
- return false;
+ return -1;
}
return point_in_box
@@ -85,9 +85,9 @@
>
struct point_in_box<Point, Box, Strategy, DimensionCount, DimensionCount>
{
- static inline bool apply(Point const& , Box const& , Strategy const& )
+ static inline int apply(Point const& , Box const& , Strategy const& )
{
- return true;
+ return 1;
}
};
@@ -102,14 +102,14 @@
>
struct box_in_box
{
- static inline bool apply(Box1 const& b1, Box2 const& b2, Strategy const& s)
+ static inline int apply(Box1 const& b1, Box2 const& b2, Strategy const& s)
{
assert_dimension_equal<Box1, Box2>();
if (get<min_corner, Dimension>(b1) <= get<min_corner, Dimension>(b2)
|| get<max_corner, Dimension>(b1) >= get<max_corner, Dimension>(b2))
{
- return false;
+ return -1;
}
return box_in_box
@@ -132,9 +132,9 @@
>
struct box_in_box<Box1, Box2, Strategy, DimensionCount, DimensionCount>
{
- static inline bool apply(Box1 const& , Box2 const& , Strategy const&)
+ static inline int apply(Box1 const& , Box2 const& , Strategy const&)
{
- return true;
+ return 1;
}
};
@@ -151,12 +151,12 @@
{
BOOST_CONCEPT_ASSERT( (geometry::concept::WithinStrategy<Strategy>) );
- static inline bool apply(Point const& point, Ring const& ring,
+ static inline int apply(Point const& point, Ring const& ring,
Strategy const& strategy)
{
if (boost::size(ring) < 4)
{
- return false;
+ return -1;
}
typedef reversible_view<Ring const, Direction> rev_view_type;
@@ -182,10 +182,13 @@
return false;
}
}
+
return strategy.result(state);
}
};
+
+
// Polygon: in exterior ring, and if so, not within interior ring(s)
template
<
@@ -199,22 +202,20 @@
{
BOOST_CONCEPT_ASSERT( (geometry::concept::WithinStrategy<Strategy>) );
- static inline bool apply(Point const& point, Polygon const& poly,
+ static inline int apply(Point const& point, Polygon const& poly,
Strategy const& strategy)
{
-
- typedef point_in_ring
+ int const code = point_in_ring
<
Point,
typename ring_type<Polygon>::type,
Direction,
Closure,
Strategy
- > per_ring;
+ >::apply(point, exterior_ring(poly), strategy);
- if (per_ring::apply(point, exterior_ring(poly), strategy))
+ if (code == 1)
{
-
for (typename boost::range_iterator
<
typename interior_type<Polygon>::type const
@@ -222,14 +223,25 @@
it != boost::end(interior_rings(poly));
++it)
{
- if (per_ring::apply(point, *it, strategy))
+ int const interior_code = point_in_ring
+ <
+ Point,
+ typename ring_type<Polygon>::type,
+ Direction,
+ Closure,
+ Strategy
+ >::apply(point, *it, strategy);
+
+ if (interior_code != -1)
{
- return false;
+ // If 0, return 0 (touch)
+ // If 1 (inside hole) return -1 (outside polygon)
+ // If -1 (outside hole) check other holes if any
+ return -interior_code;
}
}
- return true;
}
- return false;
+ return code;
}
};
@@ -335,8 +347,10 @@
typedef typename point_type<Geometry1>::type point_type1;
typedef typename point_type<Geometry2>::type point_type2;
- typedef typename strategy_within
+ typedef typename strategy::within::services::default_strategy
<
+ typename tag<Geometry1>::type,
+ typename tag<Geometry2>::type,
typename cs_tag<point_type1>::type,
typename cs_tag<point_type2>::type,
point_type1,
@@ -350,7 +364,7 @@
Geometry1,
Geometry2,
strategy_type
- >::apply(geometry1, geometry2, strategy_type());
+ >::apply(geometry1, geometry2, strategy_type()) == 1;
}
/*!
@@ -387,7 +401,7 @@
Geometry1,
Geometry2,
Strategy
- >::apply(geometry1, geometry2, strategy);
+ >::apply(geometry1, geometry2, strategy) == 1;
}
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/extensions/algorithms/buffer/sectionalizing_buffer.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/extensions/algorithms/buffer/sectionalizing_buffer.hpp (original)
+++ sandbox/geometry/boost/geometry/extensions/algorithms/buffer/sectionalizing_buffer.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -23,7 +23,7 @@
#include <boost/geometry/algorithms/detail/buffer/linestring_buffer.hpp>
#include <boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp>
-#include <boost/geometry/algorithms/detail/sections/get_section.hpp>
+#include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
#include <boost/geometry/algorithms/dissolve.hpp>
@@ -91,7 +91,11 @@
iterator_type begin, end;
typedef std::pair<iterator_type, iterator_type> section_range;
- geometry::get_section(geometry, section, begin, end);
+
+TODO: UPDATE: get _ section IS OBSOLETE NOW AND DISCARDED.
+TAKE range_by_section AND ADD section.begin_index/section.end_index
+
+ geometry::get _ section(geometry, section, begin, end); // get_section is DISCARDED
geometry::detail::buffer::linestring_buffer
<
section_range, ring_type, DistanceStrategy, JoinStrategy
Modified: sandbox/geometry/boost/geometry/extensions/algorithms/buffer/traversing_buffer.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/extensions/algorithms/buffer/traversing_buffer.hpp (original)
+++ sandbox/geometry/boost/geometry/extensions/algorithms/buffer/traversing_buffer.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -23,8 +23,6 @@
#include <boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp>
#include <boost/geometry/extensions/algorithms/buffer/line_line_intersection.hpp>
-#include <boost/geometry/algorithms/detail/sections/get_section.hpp>
-#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
#include <boost/geometry/algorithms/dissolve.hpp>
Modified: sandbox/geometry/boost/geometry/extensions/contrib/ttmath_stub.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/extensions/contrib/ttmath_stub.hpp (original)
+++ sandbox/geometry/boost/geometry/extensions/contrib/ttmath_stub.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -2,10 +2,11 @@
#define TTMATH_STUB
#include <boost/math/constants/constants.hpp>
+#include <boost/numeric/conversion/cast.hpp>
#include <boost/geometry/util/math.hpp>
-#include <ttmath/ttmath.h>
+#include <ttmath.h>
namespace ttmath
{
template <uint Exponent, uint Mantissa>
@@ -143,4 +144,88 @@
+
+// Support for boost::numeric_cast to int and to double (necessary for SVG-mapper)
+namespace boost { namespace numeric
+{
+
+template
+<
+ ttmath::uint Exponent, ttmath::uint Mantissa,
+ typename Traits,
+ typename OverflowHandler,
+ typename Float2IntRounder,
+ typename RawConverter,
+ typename UserRangeChecker
+>
+struct converter<int, ttmath::Big<Exponent, Mantissa>, Traits, OverflowHandler, Float2IntRounder, RawConverter, UserRangeChecker>
+{
+ static inline int convert(ttmath::Big<Exponent, Mantissa> arg)
+ {
+ int v;
+ arg.ToInt(v);
+ return v;
+ }
+};
+
+template
+<
+ ttmath::uint Exponent, ttmath::uint Mantissa,
+ typename Traits,
+ typename OverflowHandler,
+ typename Float2IntRounder,
+ typename RawConverter,
+ typename UserRangeChecker
+>
+struct converter<double, ttmath::Big<Exponent, Mantissa>, Traits, OverflowHandler, Float2IntRounder, RawConverter, UserRangeChecker>
+{
+ static inline double convert(ttmath::Big<Exponent, Mantissa> arg)
+ {
+ double v;
+ arg.ToDouble(v);
+ return v;
+ }
+};
+
+
+template
+<
+ typename Traits,
+ typename OverflowHandler,
+ typename Float2IntRounder,
+ typename RawConverter,
+ typename UserRangeChecker
+>
+struct converter<int, ttmath_big, Traits, OverflowHandler, Float2IntRounder, RawConverter, UserRangeChecker>
+{
+ static inline int convert(ttmath_big arg)
+ {
+ int v;
+ arg.ToInt(v);
+ return v;
+ }
+};
+
+template
+<
+ typename Traits,
+ typename OverflowHandler,
+ typename Float2IntRounder,
+ typename RawConverter,
+ typename UserRangeChecker
+>
+struct converter<double, ttmath_big, Traits, OverflowHandler, Float2IntRounder, RawConverter, UserRangeChecker>
+{
+ static inline double convert(ttmath_big arg)
+ {
+ double v;
+ arg.ToDouble(v);
+ return v;
+ }
+};
+
+
+}}
+
+
#endif
Modified: sandbox/geometry/boost/geometry/extensions/gis/geographic/strategies/area_huiller_earth.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/extensions/gis/geographic/strategies/area_huiller_earth.hpp (original)
+++ sandbox/geometry/boost/geometry/extensions/gis/geographic/strategies/area_huiller_earth.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -32,28 +32,33 @@
public :
// By default the average earth radius.
// Uses can specify another radius.
- // Note that the earth is still spherical
+ // Note that the earth is still handled spherically
inline huiller_earth(double radius = 6372795.0)
: huiller<PointOfSegment, CalculationType>(radius)
{}
};
-
-}} // namespace strategy::area
-
-
#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+namespace services
+{
+
template <typename Point>
-struct strategy_area<geographic_tag, Point>
+struct default_strategy<geographic_tag, Point>
{
- typedef strategy::area::huiller_earth<Point> type;
+ typedef huiller_earth<Point> type;
};
+} // namespace services
+
+
#endif
+}} // namespace strategy::area
+
+
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/geometries/linear_ring.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/geometries/linear_ring.hpp (original)
+++ sandbox/geometry/boost/geometry/geometries/linear_ring.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -114,6 +114,104 @@
} // namespace traits
#endif // DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+
+
+// NEW APPROACH
+namespace model
+{
+/*!
+ \brief A linear_ring (linear linear_ring) is a closed line which should not be selfintersecting
+ \ingroup geometries
+ \tparam Point point type
+ \tparam Container optional container type, for example std::vector, std::list, std::deque
+ \tparam Allocator optional container-allocator-type
+*/
+template
+<
+ typename Point,
+ bool ClockWise = true, bool Closed = true,
+ template<typename, typename> class Container = std::vector,
+ template<typename> class Allocator = std::allocator
+>
+class linear_ring : public Container<Point, Allocator<Point> >
+{
+ BOOST_CONCEPT_ASSERT( (concept::Point<Point>) );
+};
+
+} // namespace model
+
+
+#ifndef DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+namespace traits
+{
+
+template
+<
+ typename Point,
+ bool ClockWise, bool Closed,
+ template<typename, typename> class Container,
+ template<typename> class Allocator
+>
+struct tag<model::linear_ring<Point, ClockWise, Closed, Container, Allocator> >
+{
+ typedef ring_tag type;
+};
+
+
+template
+<
+ typename Point,
+ bool Closed,
+ template<typename, typename> class Container,
+ template<typename> class Allocator
+>
+struct point_order<model::linear_ring<Point, false, Closed, Container, Allocator> >
+{
+ static const order_selector value = counterclockwise;
+};
+
+
+template
+<
+ typename Point,
+ bool Closed,
+ template<typename, typename> class Container,
+ template<typename> class Allocator
+>
+struct point_order<model::linear_ring<Point, true, Closed, Container, Allocator> >
+{
+ static const order_selector value = clockwise;
+};
+
+template
+<
+ typename Point,
+ bool PointOrder,
+ template<typename, typename> class Container,
+ template<typename> class Allocator
+>
+struct closure<model::linear_ring<Point, PointOrder, true, Container, Allocator> >
+{
+ static const closure_selector value = closed;
+};
+
+template
+<
+ typename Point,
+ bool PointOrder,
+ template<typename, typename> class Container,
+ template<typename> class Allocator
+>
+struct closure<model::linear_ring<Point, PointOrder, false, Container, Allocator> >
+{
+ static const closure_selector value = open;
+};
+
+
+} // namespace traits
+#endif // DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+
+
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_GEOMETRIES_LINEAR_RING_HPP
Modified: sandbox/geometry/boost/geometry/geometries/polygon.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/geometries/polygon.hpp (original)
+++ sandbox/geometry/boost/geometry/geometries/polygon.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -139,7 +139,7 @@
typename Point,
template<typename, typename> class PointList,
template<typename, typename> class RingList,
- bool ClockWise, bool Closed,
+ bool ClockWise, bool Closed,
template<typename> class PointAlloc,
template<typename> class RingAlloc
>
@@ -187,6 +187,179 @@
} // namespace traits
#endif // DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+
+// NEW APPROACH
+namespace model
+{
+
+/*!
+\brief The \b polygon contains an outer ring and zero or more inner rings.
+\ingroup geometries
+\tparam P point type
+\tparam PointList optional container type for points,
+ for example std::vector, std::list, std::deque
+\tparam RingList optional container type for inner rings,
+ for example std::vector, std::list, std::deque
+\tparam ClockWise optional parameter, true for clockwise direction,
+ false for CounterClockWise direction
+\tparam Closed optional parameter, true for closed polygons (last point == first point),
+ false open points
+\tparam PointAlloc container-allocator-type
+\tparam RingAlloc container-allocator-type
+\note The container collecting the points in the rings can be different
+ from the container collecting the inner rings. They all default to vector.
+*/
+template
+<
+ typename Point,
+ bool ClockWise = true,
+ bool Closed = true,
+ template<typename, typename> class PointList = std::vector,
+ template<typename, typename> class RingList = std::vector,
+ template<typename> class PointAlloc = std::allocator,
+ template<typename> class RingAlloc = std::allocator
+>
+class polygon
+{
+ BOOST_CONCEPT_ASSERT( (concept::Point<Point>) );
+
+public:
+
+ // Member types
+ typedef Point point_type;
+ typedef linear_ring<Point, ClockWise, Closed, PointList, PointAlloc> ring_type;
+ typedef RingList<ring_type , RingAlloc<ring_type > > inner_container_type;
+
+ inline ring_type const& outer() const { return m_outer; }
+ inline inner_container_type const& inners() const { return m_inners; }
+
+ inline ring_type& outer() { return m_outer; }
+ inline inner_container_type & inners() { return m_inners; }
+
+ /// Utility method, clears outer and inner rings
+ inline void clear()
+ {
+ m_outer.clear();
+ m_inners.clear();
+ }
+
+private:
+
+ ring_type m_outer;
+ inner_container_type m_inners;
+};
+
+
+} // namespace model
+
+
+#ifndef DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+namespace traits
+{
+
+template
+<
+ typename Point,
+ bool ClockWise, bool Closed,
+ template<typename, typename> class PointList,
+ template<typename, typename> class RingList,
+ template<typename> class PointAlloc,
+ template<typename> class RingAlloc
+>
+struct tag<model::polygon<Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc> >
+{
+ typedef polygon_tag type;
+};
+
+template
+<
+ typename Point,
+ bool ClockWise, bool Closed,
+ template<typename, typename> class PointList,
+ template<typename, typename> class RingList,
+ template<typename> class PointAlloc,
+ template<typename> class RingAlloc
+>
+struct ring_type<model::polygon<Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc> >
+{
+ typedef typename model::polygon
+ <
+ Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc
+ >::ring_type type;
+};
+
+template
+<
+ typename Point,
+ bool ClockWise, bool Closed,
+ template<typename, typename> class PointList,
+ template<typename, typename> class RingList,
+ template<typename> class PointAlloc,
+ template<typename> class RingAlloc
+>
+struct interior_type<model::polygon<Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc> >
+{
+ typedef typename model::polygon
+ <
+ Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc
+ >::inner_container_type type;
+};
+
+template
+<
+ typename Point,
+ bool ClockWise, bool Closed,
+ template<typename, typename> class PointList,
+ template<typename, typename> class RingList,
+ template<typename> class PointAlloc,
+ template<typename> class RingAlloc
+>
+struct exterior_ring<model::polygon<Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc> >
+{
+ typedef model::polygon<Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc> polygon_type;
+
+ static inline typename polygon_type::ring_type& get(polygon_type& p)
+ {
+ return p.outer();
+ }
+
+ static inline typename polygon_type::ring_type const & get(polygon_type const& p)
+ {
+ return p.outer();
+ }
+};
+
+template
+<
+ typename Point,
+ bool ClockWise, bool Closed,
+ template<typename, typename> class PointList,
+ template<typename, typename> class RingList,
+ template<typename> class PointAlloc,
+ template<typename> class RingAlloc
+>
+struct interior_rings<model::polygon<Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc> >
+{
+ typedef model::polygon<Point, ClockWise, Closed, PointList, RingList, PointAlloc, RingAlloc> polygon_type;
+
+ static inline typename polygon_type::inner_container_type& get(
+ polygon_type& p)
+ {
+ return p.inners();
+ }
+
+ static inline typename polygon_type::inner_container_type const& get(
+ polygon_type const& p)
+ {
+ return p.inners();
+ }
+};
+
+} // namespace traits
+#endif // DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+
+
+
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_GEOMETRIES_POLYGON_HPP
Modified: sandbox/geometry/boost/geometry/geometry.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/geometry.hpp (original)
+++ sandbox/geometry/boost/geometry/geometry.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -58,10 +58,6 @@
#include <boost/geometry/algorithms/unique.hpp>
#include <boost/geometry/algorithms/within.hpp>
-#include <boost/geometry/algorithms/detail/sections/get_section.hpp>
-#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
-
-
// check includes all concepts
#include <boost/geometry/geometries/concepts/check.hpp>
Modified: sandbox/geometry/boost/geometry/iterators/closing_iterator.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/iterators/closing_iterator.hpp (original)
+++ sandbox/geometry/boost/geometry/iterators/closing_iterator.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -10,7 +10,7 @@
#include <boost/range.hpp>
#include <boost/iterator.hpp>
-#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/iterator_categories.hpp>
@@ -28,65 +28,120 @@
*/
template <typename Range>
struct closing_iterator
- : public boost::iterator_adaptor
+ : public boost::iterator_facade
<
closing_iterator<Range>,
- typename boost::range_iterator<Range>::type,
- boost::use_default,
- boost::forward_traversal_tag
+ typename boost::range_value<Range>::type const,
+ boost::random_access_traversal_tag
>
{
/// Constructor including the range it is based on
explicit inline closing_iterator(Range& range)
- : m_range(range)
- , m_beyond(false)
- , m_end(boost::end(m_range))
- {
- this->base_reference() = boost::begin(m_range);
- }
+ : m_range(&range)
+ , m_iterator(boost::begin(range))
+ , m_end(boost::end(range))
+ , m_size(boost::size(range))
+ , m_index(0)
+ {}
/// Constructor to indicate the end of a range
explicit inline closing_iterator(Range& range, bool)
- : m_range(range)
- , m_beyond(true)
- , m_end(boost::end(m_range))
+ : m_range(&range)
+ , m_iterator(boost::end(range))
+ , m_end(boost::end(range))
+ , m_size(boost::size(range))
+ , m_index(m_size + 1)
+ {}
+
+ /// Default constructor
+ explicit inline closing_iterator()
+ : m_range(NULL)
+ , m_size(0)
+ , m_index(0)
+ {}
+
+ inline closing_iterator<Range>& operator=(closing_iterator<Range> const& source)
{
- this->base_reference() = m_end;
+ m_range = source.m_range;
+ m_iterator = source.m_iterator;
+ m_end = source.m_end;
+ m_size = source.m_size;
+ m_index = source.m_index;
+ return *this;
}
+ typedef std::ptrdiff_t difference_type;
+
private:
friend class boost::iterator_core_access;
+ inline typename boost::range_value<Range>::type const& dereference() const
+ {
+ return *m_iterator;
+ }
+
+ inline difference_type distance_to(closing_iterator<Range> const& other) const
+ {
+ return other.m_index - this->m_index;
+ }
+
inline bool equal(closing_iterator<Range> const& other) const
{
- return this->base() == other.base()
- && this->m_beyond == other.m_beyond;
+ return this->m_range == other.m_range
+ && this->m_index == other.m_index;
}
inline void increment()
{
- if (m_beyond)
+ if (++m_index < m_size)
+ {
+ ++m_iterator;
+ }
+ else
+ {
+ update_iterator();
+ }
+ }
+
+ inline void decrement()
+ {
+ if (m_index-- < m_size)
{
- this->base_reference() = m_end;
+ --m_iterator;
}
- else if (this->base() != m_end)
+ else
{
- (this->base_reference())++;
+ update_iterator();
+ }
+ }
- if (this->base() == m_end)
- {
- // Now beyond last position -> set to "begin" again
- // and set flag "beyond" such that next increment
- // will finish traversal
- this->base_reference() = boost::begin(m_range);
- m_beyond = true;
- }
+ inline void advance(difference_type n)
+ {
+ if (m_index < m_size && m_index + n < m_size)
+ {
+ m_index += n;
+ m_iterator += n;
+ }
+ else
+ {
+ m_index += n;
+ update_iterator();
}
}
- Range& m_range;
- bool m_beyond;
+ inline void update_iterator()
+ {
+ this->m_iterator = m_index <= m_size
+ ? boost::begin(*m_range) + (m_index % m_size)
+ : boost::end(*m_range)
+ ;
+ }
+
+ Range* m_range;
+ typename boost::range_iterator<Range>::type m_iterator;
typename boost::range_iterator<Range>::type m_end;
+ difference_type m_size;
+ difference_type m_index;
};
Modified: sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -15,7 +15,6 @@
#include <boost/geometry/multi/algorithms/distance.hpp>
#include <boost/geometry/multi/iterators/range_type.hpp>
-#include <boost/geometry/multi/algorithms/detail/sections/get_section.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
@@ -58,7 +57,7 @@
typename boost::range_value<Multi>::type,
Box,
Turns, TurnPolicy, InterruptPolicy
- >::apply(source_id1, *it, source_id2, box,
+ >::apply(source_id1, *it, source_id2, box,
turns, interrupt_policy, i);
}
}
Modified: sandbox/geometry/boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -13,6 +13,7 @@
#include <boost/range.hpp>
#include <boost/geometry/multi/core/tags.hpp>
+#include <boost/geometry/multi/core/ring_type.hpp>
#include <boost/geometry/algorithms/detail/sections/get_full_section.hpp>
@@ -29,14 +30,19 @@
<
typename MultiGeometry,
typename Section,
- typename Iterator,
typename Policy
>
struct full_section_multi
{
- static inline void apply(MultiGeometry const& multi,
- Section const& section,
- Iterator& begin, Iterator& end)
+ typedef typename geometry::ring_type<MultiGeometry>::type ring_type;
+ typedef closeable_view
+ <
+ ring_type const,
+ closure<MultiGeometry>::value == open // close it if it is open
+ > view_type;
+
+ static inline view_type apply(MultiGeometry const& multi,
+ Section const& section)
{
BOOST_ASSERT
(
@@ -44,7 +50,7 @@
&& section.multi_index < boost::size(multi)
);
- Policy::apply(multi[section.multi_index], section, begin, end);
+ return Policy::apply(multi[section.multi_index], section);
}
};
@@ -59,18 +65,16 @@
{
-template <typename MultiPolygon, typename Section, typename Iterator>
-struct get_full_section<multi_polygon_tag, MultiPolygon, Section, Iterator>
+template <typename MultiPolygon, typename Section>
+struct get_full_section<multi_polygon_tag, MultiPolygon, Section>
: detail::section::full_section_multi
<
MultiPolygon,
Section,
- Iterator,
detail::section::full_section_polygon
<
typename boost::range_value<MultiPolygon>::type,
- Section,
- Iterator
+ Section
>
>
{};
Modified: sandbox/geometry/boost/geometry/multi/algorithms/detail/sections/get_section.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/detail/sections/get_section.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/sections/get_section.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -10,6 +10,8 @@
#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_SECTIONS_GET_SECTION_HPP
+// OBSOLETE
+/*
#include <boost/assert.hpp>
#include <boost/concept/requires.hpp>
#include <boost/range.hpp>
@@ -71,5 +73,6 @@
}} // namespace boost::geometry
+*/
#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_SECTIONS_GET_SECTION_HPP
Modified: sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -20,7 +20,6 @@
#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/sections/get_section.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
Modified: sandbox/geometry/boost/geometry/multi/algorithms/num_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/num_points.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/num_points.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -28,7 +28,7 @@
template <typename MultiGeometry>
struct multi_count
{
- static inline size_t apply(MultiGeometry const& geometry)
+ static inline size_t apply(MultiGeometry const& geometry, bool add_for_open)
{
typedef typename boost::range_value<MultiGeometry>::type geometry_type;
typedef typename boost::range_iterator
@@ -36,7 +36,7 @@
MultiGeometry const
>::type iterator_type;
- size_t n = 0;
+ std::size_t n = 0;
for (iterator_type it = boost::begin(geometry);
it != boost::end(geometry);
++it)
@@ -46,7 +46,7 @@
typename tag<geometry_type>::type,
geometry::is_linear<geometry_type>::value,
geometry_type
- >::apply(*it);
+ >::apply(*it, add_for_open);
}
return n;
}
Modified: sandbox/geometry/boost/geometry/multi/algorithms/union.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/union.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/union.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -20,7 +20,6 @@
#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/sections/get_section.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
Modified: sandbox/geometry/boost/geometry/multi/algorithms/within.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/within.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/within.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -32,7 +32,7 @@
>
struct geometry_in_multi
{
- static inline bool apply(Geometry const& geometry,
+ static inline int apply(Geometry const& geometry,
MultiGeometry const& multi,
Strategy const& strategy)
{
@@ -42,12 +42,13 @@
++it)
{
// Geometry within a multi: true if within one of them
- if (Policy::apply(geometry, *it, strategy))
+ int const code = Policy::apply(geometry, *it, strategy);
+ if (code != -1)
{
- return true;
+ return code;
}
}
- return false;
+ return -1;
}
};
Modified: sandbox/geometry/boost/geometry/multi/multi.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/multi.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/multi.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -43,7 +43,6 @@
#include <boost/geometry/multi/algorithms/detail/modify_with_predicate.hpp>
#include <boost/geometry/multi/algorithms/detail/multi_sum.hpp>
-#include <boost/geometry/multi/algorithms/detail/sections/get_section.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
#include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp>
Modified: sandbox/geometry/boost/geometry/multi/strategies/cartesian/centroid_average.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/strategies/cartesian/centroid_average.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/strategies/cartesian/centroid_average.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -23,7 +23,7 @@
namespace boost { namespace geometry
{
-namespace strategy { namespace centroid_
+namespace strategy { namespace centroid
{
@@ -71,26 +71,30 @@
};
-}} // namespace strategy::centroid
-
-
#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+namespace services
+{
template <typename Point, typename Geometry>
-struct strategy_centroid<cartesian_tag, multi_point_tag, 2, Point, Geometry>
+struct default_strategy<cartesian_tag, multi_point_tag, 2, Point, Geometry>
{
- typedef strategy::centroid_::centroid_average
+ typedef centroid_average
<
Point,
typename point_type<Geometry>::type
> type;
};
+} // namespace services
+
#endif
+}} // namespace strategy::centroid
+
+
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/multi/strategies/centroid.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/strategies/centroid.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/strategies/centroid.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -18,19 +18,23 @@
#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+namespace strategy { namespace centroid { namespace services
+{
template <typename Point, typename Geometry>
-struct strategy_centroid<cartesian_tag, multi_polygon_tag, 2, Point, Geometry>
+struct default_strategy<cartesian_tag, multi_polygon_tag, 2, Point, Geometry>
{
- typedef strategy::centroid_::bashein_detmer
+ typedef bashein_detmer
<
Point,
typename point_type<Geometry>::type
> type;
};
-#endif
+}}} // namespace strategy::centroid::services
+
+#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -9,13 +9,16 @@
#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>
-#include <boost/geometry/strategies/point_in_poly.hpp>
-
+#include <boost/geometry/strategies/side.hpp>
+#include <boost/geometry/strategies/within.hpp>
+// TEMP!
+#include <boost/geometry/multi/core/tags.hpp>
namespace boost { namespace geometry
{
@@ -57,19 +60,20 @@
/*! subclass to keep state */
class counter
{
- int count;
- bool touches;
+ int m_count;
+ bool m_touches;
- inline bool within_no_touch() const
+ inline int code() const
{
- return ! touches && count != 0;
+ return m_touches ? 0 : m_count == 0 ? -1 : 1;
}
+
public :
friend class winding;
inline counter()
- : count(0)
- , touches(false)
+ : m_count(0)
+ , m_touches(false)
{}
};
@@ -85,7 +89,7 @@
calculation_type const s2 = get<D>(seg2);
if ((s1 <= p && s2 >= p) || (s2 <= p && s1 >= p))
{
- state.touches = true;
+ state.m_touches = true;
}
return 0;
}
@@ -140,8 +144,8 @@
if (side == 0)
{
// Point is lying on segment
- state.touches = true;
- state.count = 0;
+ state.m_touches = true;
+ state.m_count = 0;
return false;
}
@@ -151,39 +155,77 @@
// See accompagnying figure (TODO)
if (side * count > 0)
{
- state.count += count;
+ state.m_count += count;
}
-
}
- return ! state.touches;
+ return ! state.m_touches;
}
- static inline bool result(counter const& state)
+ static inline int result(counter const& state)
{
- return state.within_no_touch();
+ return state.code();
}
};
-}} // namespace strategy::within
-
#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+namespace services
+{
+
+template <typename Point, typename PointOfSegment>
+struct default_strategy<point_tag, polygon_tag, cartesian_tag, cartesian_tag, Point, PointOfSegment>
+{
+ typedef winding<Point, PointOfSegment> type;
+};
+
+template <typename Point, typename PointOfSegment>
+struct default_strategy<point_tag, ring_tag, cartesian_tag, cartesian_tag, Point, PointOfSegment>
+{
+ typedef winding<Point, PointOfSegment> type;
+};
+
template <typename Point, typename PointOfSegment>
-struct strategy_within<cartesian_tag, cartesian_tag, Point, PointOfSegment>
+struct default_strategy<point_tag, polygon_tag, spherical_tag, spherical_tag, Point, PointOfSegment>
{
- typedef strategy::within::winding<Point, PointOfSegment> type;
+ typedef winding<Point, PointOfSegment> type;
};
+// TEMP!
+// register it even for the multi here, and for the box
+// future: use tag inheritance, see elsewhere
template <typename Point, typename PointOfSegment>
-struct strategy_within<geographic_tag, geographic_tag, Point, PointOfSegment>
+struct default_strategy<point_tag, multi_polygon_tag, cartesian_tag, cartesian_tag, Point, PointOfSegment>
{
- typedef strategy::within::winding<Point, PointOfSegment> type;
+ typedef winding<Point, PointOfSegment> type;
};
+template <typename Point, typename PointOfSegment>
+struct default_strategy<point_tag, multi_polygon_tag, spherical_tag, spherical_tag, Point, PointOfSegment>
+{
+ typedef winding<Point, PointOfSegment> type;
+};
+
+template <typename Point, typename PointOfSegment>
+struct default_strategy<point_tag, box_tag, cartesian_tag, cartesian_tag, Point, PointOfSegment>
+{
+ typedef winding<Point, PointOfSegment> type;
+};
+
+template <typename Point, typename PointOfSegment>
+struct default_strategy<point_tag, box_tag, spherical_tag, spherical_tag, Point, PointOfSegment>
+{
+ typedef winding<Point, PointOfSegment> type;
+};
+
+} // namespace services
+
#endif
+}} // namespace strategy::within
+
+
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/strategies/area.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/area.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/area.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -9,26 +9,37 @@
#ifndef BOOST_GEOMETRY_STRATEGIES_AREA_HPP
#define BOOST_GEOMETRY_STRATEGIES_AREA_HPP
-#include <boost/geometry/strategies/tags.hpp>
+#include <boost/mpl/assert.hpp>
+#include <boost/geometry/strategies/tags.hpp>
namespace boost { namespace geometry
{
+namespace strategy { namespace area { namespace services
+{
+
/*!
- \brief Traits class binding an area strategy to a coordinate system
+ \brief Traits class binding a default area strategy to a coordinate system
\ingroup area
\tparam Tag tag of coordinate system
\tparam PointOfSegment point-type
*/
template <typename Tag, typename PointOfSegment>
-struct strategy_area
+struct default_strategy
{
- typedef strategy::not_implemented type;
+ BOOST_MPL_ASSERT_MSG
+ (
+ false, NOT_IMPLEMENTED_FOR_THIS_POINT_TYPE
+ , (types<PointOfSegment>)
+ );
};
+}}} // namespace strategy::area::services
+
+
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_STRATEGIES_AREA_HPP
Modified: sandbox/geometry/boost/geometry/strategies/area_result.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/area_result.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/area_result.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -25,11 +25,15 @@
from length, where distance is sqr/sqrt, but length always squared)
*/
+
+// TODO: rename to "default_area_result" or services::default_result
+
+
template <typename Geometry>
struct area_result
{
typedef typename point_type<Geometry>::type point_type;
- typedef typename strategy_area
+ typedef typename strategy::area::services::default_strategy
<
typename cs_tag<point_type>::type,
point_type
Modified: sandbox/geometry/boost/geometry/strategies/cartesian/area_by_triangles.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/cartesian/area_by_triangles.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/cartesian/area_by_triangles.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -92,18 +92,24 @@
};
-}} // namespace strategy::area
-
-
#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
-template <typename Point>
-struct strategy_area<cartesian_tag, Point>
+namespace services
{
- typedef strategy::area::by_triangles<Point> type;
-};
+ template <typename Point>
+ struct default_strategy<cartesian_tag, Point>
+ {
+ typedef strategy::area::by_triangles<Point> type;
+ };
+
+} // namespace services
+
+#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+
+
+}} // namespace strategy::area
+
-#endif
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/strategies/cartesian/cart_intersect.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/cartesian/cart_intersect.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/cartesian/cart_intersect.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -152,11 +152,12 @@
}
// Degenerate cases: segments of single point, lying on other segment, non disjoint
- if (math::equals(dx_a, 0) && math::equals(dy_a, 0))
+ coordinate_type const zero = 0;
+ if (math::equals(dx_a, zero) && math::equals(dy_a, zero))
{
return Policy::degenerate(a, true);
}
- if (math::equals(dx_b, 0) && math::equals(dy_b, 0))
+ if (math::equals(dx_b, zero) && math::equals(dy_b, zero))
{
return Policy::degenerate(b, false);
}
@@ -174,7 +175,7 @@
// Determinant d should be nonzero.
// If it is zero, we have an robustness issue here,
// (and besides that we cannot divide by it)
- if(math::equals(d, 0) && ! collinear)
+ if(math::equals(d, zero) && ! collinear)
//if(! collinear && sides.as_collinear())
{
#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
@@ -208,7 +209,7 @@
if(collinear)
{
// Segments are collinear. We'll find out how.
- if (math::equals(dx_b, 0))
+ if (math::equals(dx_b, zero))
{
// Vertical -> Check y-direction
return relate_collinear(a, b,
Modified: sandbox/geometry/boost/geometry/strategies/cartesian/centroid_bashein_detmer.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/cartesian/centroid_bashein_detmer.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/cartesian/centroid_bashein_detmer.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -27,7 +27,7 @@
// Note: when calling the namespace "centroid", it sometimes,
// somehow, in gcc, gives compilation problems (confusion with function centroid).
-namespace strategy { namespace centroid_
+namespace strategy { namespace centroid
{
@@ -204,17 +204,16 @@
};
-
-}} // namespace strategy::centroid
-
-
#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+namespace services
+{
+
// Register this strategy for rings and polygons, in two dimensions
template <typename Point, typename Geometry>
-struct strategy_centroid<cartesian_tag, ring_tag, 2, Point, Geometry>
+struct default_strategy<cartesian_tag, ring_tag, 2, Point, Geometry>
{
- typedef strategy::centroid_::bashein_detmer
+ typedef bashein_detmer
<
Point,
typename point_type<Geometry>::type
@@ -222,16 +221,23 @@
};
template <typename Point, typename Geometry>
-struct strategy_centroid<cartesian_tag, polygon_tag, 2, Point, Geometry>
+struct default_strategy<cartesian_tag, polygon_tag, 2, Point, Geometry>
{
- typedef strategy::centroid_::bashein_detmer
+ typedef bashein_detmer
<
Point,
typename point_type<Geometry>::type
> type;
};
-#endif
+
+} // namespace services
+
+
+#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+
+
+}} // namespace strategy::centroid
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/strategies/cartesian/point_in_poly_crossings_multiply.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/cartesian/point_in_poly_crossings_multiply.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/cartesian/point_in_poly_crossings_multiply.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -93,9 +93,9 @@
return true;
}
- static inline bool result(flags const& state)
+ static inline int result(flags const& state)
{
- return state.inside_flag;
+ return state.inside_flag ? 1 : -1;
}
};
Modified: sandbox/geometry/boost/geometry/strategies/cartesian/point_in_poly_franklin.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/cartesian/point_in_poly_franklin.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/cartesian/point_in_poly_franklin.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -85,9 +85,9 @@
return true;
}
- static inline bool result(crossings const& state)
+ static inline int result(crossings const& state)
{
- return state.crosses;
+ return state.crosses ? 1 : -1;
}
};
Modified: sandbox/geometry/boost/geometry/strategies/centroid.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/centroid.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/centroid.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -12,6 +12,9 @@
#include <cstddef>
+#include <boost/mpl/assert.hpp>
+
+#include <boost/geometry/core/tags.hpp>
#include <boost/geometry/strategies/tags.hpp>
@@ -19,6 +22,17 @@
{
+namespace strategy { namespace centroid
+{
+
+struct not_applicable_strategy
+{
+};
+
+
+namespace services
+{
+
/*!
\brief Traits class binding a centroid calculation strategy to a coordinate system
\ingroup centroid
@@ -36,11 +50,40 @@
typename Point,
typename Geometry
>
-struct strategy_centroid
+struct default_strategy
+{
+ BOOST_MPL_ASSERT_MSG
+ (
+ false, NOT_IMPLEMENTED_FOR_THIS_TYPES
+ , (types<Point, Geometry>)
+ );
+};
+
+// Register NA-strategy for all where not applicable
+template <typename Point, typename Geometry, std::size_t Dimension>
+struct default_strategy<cartesian_tag, point_tag, Dimension, Point, Geometry>
+{
+ typedef not_applicable_strategy type;
+};
+
+template <typename Point, typename Geometry, std::size_t Dimension>
+struct default_strategy<cartesian_tag, box_tag, Dimension, Point, Geometry>
{
- typedef strategy::not_implemented type;
+ typedef not_applicable_strategy type;
};
+template <typename Point, typename Geometry, std::size_t Dimension>
+struct default_strategy<cartesian_tag, linestring_tag, Dimension, Point, Geometry>
+{
+ typedef not_applicable_strategy type;
+};
+
+
+} // namespace services
+
+
+}} // namespace strategy::centroid
+
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/strategies/concepts/within_concept.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/concepts/within_concept.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/concepts/within_concept.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -50,8 +50,8 @@
// having a point, two segment-points, and state
str->apply(*p, *sp, *sp, *st);
- // 5) must implement a method result
- bool r = str->result(*st);
+ // 5) must implement a method result returning int
+ int r = str->result(*st);
boost::ignore_unused_variable_warning(r);
boost::ignore_unused_variable_warning(str);
Deleted: sandbox/geometry/boost/geometry/strategies/point_in_poly.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/point_in_poly.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
+++ (empty file)
@@ -1,36 +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_STRATEGIES_POINT_IN_POLY_HPP
-#define BOOST_GEOMETRY_STRATEGIES_POINT_IN_POLY_HPP
-
-#include <boost/geometry/strategies/tags.hpp>
-
-namespace boost { namespace geometry
-{
-
-
-/*!
- \brief Traits class binding a within determination strategy to a coordinate system
- \ingroup within
- \tparam TagPoint tag of coordinate system of point-type
- \tparam TagSegment tag of coordinate system of segment-type
- \tparam Point point-type of input points
- \tparam PointOfSegment point-type of input segment-points
-*/
-template <typename TagPoint, typename TagSegment, typename Point, typename PointOfSegment>
-struct strategy_within
-{
- typedef strategy::not_implemented type;
-};
-
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_STRATEGIES_POINT_IN_POLY_HPP
Modified: sandbox/geometry/boost/geometry/strategies/spherical/area_huiller.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/spherical/area_huiller.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/spherical/area_huiller.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -143,20 +143,25 @@
double m_radius;
};
+#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
-}} // namespace strategy::area
+namespace services
+{
+ template <typename Point>
+ struct default_strategy<spherical_tag, Point>
+ {
+ typedef strategy::area::huiller<Point> type;
+ };
+} // namespace services
+#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+
+
+}} // namespace strategy::area
-#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
-template <typename Point>
-struct strategy_area<spherical_tag, Point>
-{
- typedef strategy::area::huiller<Point> type;
-};
-#endif
}} // namespace boost::geometry
Modified: sandbox/geometry/boost/geometry/strategies/strategies.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/strategies.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/strategies.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -19,9 +19,9 @@
#include <boost/geometry/strategies/distance.hpp>
#include <boost/geometry/strategies/intersection.hpp>
#include <boost/geometry/strategies/parse.hpp>
-#include <boost/geometry/strategies/point_in_poly.hpp>
#include <boost/geometry/strategies/side.hpp>
#include <boost/geometry/strategies/transform.hpp>
+#include <boost/geometry/strategies/within.hpp>
#include <boost/geometry/strategies/cartesian/area_by_triangles.hpp>
#include <boost/geometry/strategies/cartesian/centroid_bashein_detmer.hpp>
Modified: sandbox/geometry/boost/geometry/strategies/strategy_transform.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/strategy_transform.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/strategy_transform.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -277,84 +277,92 @@
}
};
-}} // namespace strategy::transform
-
-
#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+namespace services
+{
+
/// Specialization for same coordinate system family, same system, same dimension, same point type, can be copied
template <typename CoordSysTag, typename CoordSys, std::size_t D, typename P>
-struct strategy_transform<CoordSysTag, CoordSysTag, CoordSys, CoordSys, D, D, P, P>
+struct default_strategy<CoordSysTag, CoordSysTag, CoordSys, CoordSys, D, D, P, P>
{
- typedef strategy::transform::copy_direct<P> type;
+ typedef copy_direct<P> type;
};
/// Specialization for same coordinate system family and system, same dimension, different point type, copy per coordinate
template <typename CoordSysTag, typename CoordSys, std::size_t D, typename P1, typename P2>
-struct strategy_transform<CoordSysTag, CoordSysTag, CoordSys, CoordSys, D, D, P1, P2>
+struct default_strategy<CoordSysTag, CoordSysTag, CoordSys, CoordSys, D, D, P1, P2>
{
- typedef strategy::transform::copy_per_coordinate<P1, P2> type;
+ typedef copy_per_coordinate<P1, P2> type;
};
/// Specialization to convert from degree to radian for any coordinate system / point type combination
template <typename CoordSysTag, template<typename> class CoordSys, typename P1, typename P2>
-struct strategy_transform<CoordSysTag, CoordSysTag, CoordSys<degree>, CoordSys<radian>, 2, 2, P1, P2>
+struct default_strategy<CoordSysTag, CoordSysTag, CoordSys<degree>, CoordSys<radian>, 2, 2, P1, P2>
{
- typedef strategy::transform::degree_radian_vv<P1, P2, std::multiplies> type;
+ typedef degree_radian_vv<P1, P2, std::multiplies> type;
};
/// Specialization to convert from radian to degree for any coordinate system / point type combination
template <typename CoordSysTag, template<typename> class CoordSys, typename P1, typename P2>
-struct strategy_transform<CoordSysTag, CoordSysTag, CoordSys<radian>, CoordSys<degree>, 2, 2, P1, P2>
+struct default_strategy<CoordSysTag, CoordSysTag, CoordSys<radian>, CoordSys<degree>, 2, 2, P1, P2>
{
- typedef strategy::transform::degree_radian_vv<P1, P2, std::divides> type;
+ typedef degree_radian_vv<P1, P2, std::divides> type;
};
/// Specialization degree->radian in 3D
template <typename CoordSysTag, template<typename> class CoordSys, typename P1, typename P2>
-struct strategy_transform<CoordSysTag, CoordSysTag, CoordSys<degree>, CoordSys<radian>, 3, 3, P1, P2>
+struct default_strategy<CoordSysTag, CoordSysTag, CoordSys<degree>, CoordSys<radian>, 3, 3, P1, P2>
{
- typedef strategy::transform::degree_radian_vv_3<P1, P2, std::multiplies> type;
+ typedef degree_radian_vv_3<P1, P2, std::multiplies> type;
};
/// Specialization radian->degree in 3D
template <typename CoordSysTag, template<typename> class CoordSys, typename P1, typename P2>
-struct strategy_transform<CoordSysTag, CoordSysTag, CoordSys<radian>, CoordSys<degree>, 3, 3, P1, P2>
+struct default_strategy<CoordSysTag, CoordSysTag, CoordSys<radian>, CoordSys<degree>, 3, 3, P1, P2>
{
- typedef strategy::transform::degree_radian_vv_3<P1, P2, std::divides> type;
+ typedef degree_radian_vv_3<P1, P2, std::divides> type;
};
/// Specialization to convert from unit sphere(phi,theta) to XYZ
template <typename CoordSys1, typename CoordSys2, typename P1, typename P2>
-struct strategy_transform<spherical_tag, cartesian_tag, CoordSys1, CoordSys2, 2, 3, P1, P2>
+struct default_strategy<spherical_tag, cartesian_tag, CoordSys1, CoordSys2, 2, 3, P1, P2>
{
- typedef strategy::transform::from_spherical_2_to_cartesian_3<P1, P2> type;
+ typedef from_spherical_2_to_cartesian_3<P1, P2> type;
};
/// Specialization to convert from sphere(phi,theta,r) to XYZ
template <typename CoordSys1, typename CoordSys2, typename P1, typename P2>
-struct strategy_transform<spherical_tag, cartesian_tag, CoordSys1, CoordSys2, 3, 3, P1, P2>
+struct default_strategy<spherical_tag, cartesian_tag, CoordSys1, CoordSys2, 3, 3, P1, P2>
{
- typedef strategy::transform::from_spherical_3_to_cartesian_3<P1, P2> type;
+ typedef from_spherical_3_to_cartesian_3<P1, P2> type;
};
/// Specialization to convert from XYZ to unit sphere(phi,theta)
template <typename CoordSys1, typename CoordSys2, typename P1, typename P2>
-struct strategy_transform<cartesian_tag, spherical_tag, CoordSys1, CoordSys2, 3, 2, P1, P2>
+struct default_strategy<cartesian_tag, spherical_tag, CoordSys1, CoordSys2, 3, 2, P1, P2>
{
- typedef strategy::transform::from_cartesian_3_to_spherical_2<P1, P2> type;
+ typedef from_cartesian_3_to_spherical_2<P1, P2> type;
};
/// Specialization to convert from XYZ to sphere(phi,theta,r)
template <typename CoordSys1, typename CoordSys2, typename P1, typename P2>
-struct strategy_transform<cartesian_tag, spherical_tag, CoordSys1, CoordSys2, 3, 3, P1, P2>
+struct default_strategy<cartesian_tag, spherical_tag, CoordSys1, CoordSys2, 3, 3, P1, P2>
{
- typedef strategy::transform::from_cartesian_3_to_spherical_3<P1, P2> type;
+ typedef from_cartesian_3_to_spherical_3<P1, P2> type;
};
+
+} // namespace services
+
+
#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+
+}} // namespace strategy::transform
+
+
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_STRATEGIES_STRATEGY_TRANSFORM_HPP
Modified: sandbox/geometry/boost/geometry/strategies/transform.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/transform.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/transform.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -11,11 +11,16 @@
#include <cstddef>
+#include <boost/mpl/assert.hpp>
+
#include <boost/geometry/strategies/tags.hpp>
namespace boost { namespace geometry
{
+namespace strategy { namespace transform { namespace services
+{
+
/*!
\brief Traits class binding a transformation strategy to a coordinate system
\ingroup transform
@@ -36,11 +41,18 @@
std::size_t Dimension1, std::size_t Dimension2,
typename Point1, typename Point2
>
-struct strategy_transform
+struct default_strategy
{
- typedef strategy::not_implemented type;
+ BOOST_MPL_ASSERT_MSG
+ (
+ false, NOT_IMPLEMENTED_FOR_THIS_POINT_TYPES
+ , (types<Point1, Point2>)
+ );
};
+}}} // namespace strategy::transform::services
+
+
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_STRATEGIES_TRANSFORM_HPP
Modified: sandbox/geometry/boost/geometry/strategies/transform/map_transformer.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/transform/map_transformer.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/transform/map_transformer.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -60,7 +60,10 @@
private :
- void set_transformation_point(double wx, double wy, double px, double py, double scalex, double scaley)
+ template <typename W, typename P, typename S>
+ inline void set_transformation_point(W const& wx, W const& wy,
+ P const& px, P const& py,
+ S const& scalex, S const& scaley)
{
// Translate to a coordinate system centered on world coordinates (-wx, -wy)
Copied: sandbox/geometry/boost/geometry/strategies/within.hpp (from r66116, /sandbox/geometry/boost/geometry/strategies/point_in_poly.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/strategies/point_in_poly.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/within.hpp 2010-11-08 05:18:33 EST (Mon, 08 Nov 2010)
@@ -6,31 +6,69 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_STRATEGIES_POINT_IN_POLY_HPP
-#define BOOST_GEOMETRY_STRATEGIES_POINT_IN_POLY_HPP
+#ifndef BOOST_GEOMETRY_STRATEGIES_WITHIN_HPP
+#define BOOST_GEOMETRY_STRATEGIES_WITHIN_HPP
+
+#include <boost/mpl/assert.hpp>
#include <boost/geometry/strategies/tags.hpp>
namespace boost { namespace geometry
{
+namespace strategy { namespace within
+{
+
+struct not_applicable_strategy
+{
+};
+
+
+namespace services
+{
/*!
\brief Traits class binding a within determination strategy to a coordinate system
\ingroup within
- \tparam TagPoint tag of coordinate system of point-type
- \tparam TagSegment tag of coordinate system of segment-type
+ \tparam CsTagContained tag of coordinate system of point-type
+ \tparam CsTagContained tag of coordinate system of segment-type
\tparam Point point-type of input points
- \tparam PointOfSegment point-type of input segment-points
+ \tparam PointContaining point-type of input segment-points
*/
-template <typename TagPoint, typename TagSegment, typename Point, typename PointOfSegment>
-struct strategy_within
+template
+<
+ typename TagContained,
+ typename TagContaining,
+ typename CsTagContained,
+ typename CsTagContaining,
+ typename Point,
+ typename PointContaining
+>
+struct default_strategy
{
- typedef strategy::not_implemented type;
+ // If we would assert here, we would have to implement
+ // default strategies for all combinations, all CS, etc.
+ // This explosion is not convenient.
+ // Another option is tag inheritance / grouping (so point-in-polygon will apply for point-in-ring, point-in-polygon, point-in-multi-polygon but not for point-in-box...)
+ // TODO: decide about this.
+
+ BOOST_MPL_ASSERT_MSG
+ (
+ false, NOT_IMPLEMENTED_FOR_THIS_TYPES
+ , (types<Point, PointContaining>)
+ );
+
+
+ //typedef strategy::not_implemented type;
};
+} // namespace services
+
+
+}} // namespace strategy::within
+
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_STRATEGIES_POINT_IN_POLY_HPP
+#endif // BOOST_GEOMETRY_STRATEGIES_WITHIN_HPP
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk