|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r57036 - in sandbox/ggl/formal_review_request/boost/ggl: algorithms algorithms/overlay core geometries multi/algorithms strategies strategies/agnostic strategies/cartesian strategies/concepts strategies/spherical strategies/transform util
From: barend.gehrels_at_[hidden]
Date: 2009-10-21 05:15:20
Author: barendgehrels
Date: 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
New Revision: 57036
URL: http://svn.boost.org/trac/boost/changeset/57036
Log:
Added (planned) point-order (of ring/polygon) to design, and reflected area, convex_hull, correct
Updated / cleaned up simplify
Added boolean flag Clockwise to provided geometries linear_ring and polygon
Commented operator< in point_xy because it should not be used (not part of concept)
Added (planned) concept for some strategies (distance, simplify)
Fixed math::equals for big numbers (CLN/GMP)
Added:
sandbox/ggl/formal_review_request/boost/ggl/core/point_order.hpp (contents, props changed)
sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/simplify_douglas_peucker.hpp
- copied, changed from r56825, /sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_simplify.hpp
sandbox/ggl/formal_review_request/boost/ggl/strategies/concepts/
sandbox/ggl/formal_review_request/boost/ggl/strategies/concepts/distance_concept.hpp (contents, props changed)
sandbox/ggl/formal_review_request/boost/ggl/strategies/concepts/simplify_concept.hpp (contents, props changed)
sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/distance_cross_track.hpp (contents, props changed)
sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/distance_haversine.hpp
- copied, changed from r56825, /sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/haversine.hpp
Removed:
sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_simplify.hpp
sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/haversine.hpp
Text files modified:
sandbox/ggl/formal_review_request/boost/ggl/algorithms/area.hpp | 95 ++++++--
sandbox/ggl/formal_review_request/boost/ggl/algorithms/convert.hpp | 49 ++-
sandbox/ggl/formal_review_request/boost/ggl/algorithms/convex_hull.hpp | 180 ++++++++++++++--
sandbox/ggl/formal_review_request/boost/ggl/algorithms/correct.hpp | 166 +++++++++------
sandbox/ggl/formal_review_request/boost/ggl/algorithms/disjoint.hpp | 2
sandbox/ggl/formal_review_request/boost/ggl/algorithms/equals.hpp | 4
sandbox/ggl/formal_review_request/boost/ggl/algorithms/overlay/merge_intersection_points.hpp | 2
sandbox/ggl/formal_review_request/boost/ggl/algorithms/simplify.hpp | 429 +++++++++++++++++++++------------------
sandbox/ggl/formal_review_request/boost/ggl/core/point_type.hpp | 2
sandbox/ggl/formal_review_request/boost/ggl/core/radian_access.hpp | 4
sandbox/ggl/formal_review_request/boost/ggl/geometries/linear_ring.hpp | 32 ++
sandbox/ggl/formal_review_request/boost/ggl/geometries/point_xy.hpp | 8
sandbox/ggl/formal_review_request/boost/ggl/geometries/polygon.hpp | 38 ++-
sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/area.hpp | 6
sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/convex_hull.hpp | 80 ++++++-
sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/correct.hpp | 51 ++-
sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/simplify.hpp | 119 +++++++---
sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_convex_hull.hpp | 89 +++++--
sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/simplify_douglas_peucker.hpp | 309 +++++++++++++++-------------
sandbox/ggl/formal_review_request/boost/ggl/strategies/cartesian/cart_distance.hpp | 6
sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/distance_haversine.hpp | 145 -------------
sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/sph_area.hpp | 8
sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/sph_envelope.hpp | 1
sandbox/ggl/formal_review_request/boost/ggl/strategies/strategies.hpp | 6
sandbox/ggl/formal_review_request/boost/ggl/strategies/transform/inverse_transformer.hpp | 5
sandbox/ggl/formal_review_request/boost/ggl/strategies/transform/matrix_transformers.hpp | 3
sandbox/ggl/formal_review_request/boost/ggl/util/as_range.hpp | 40 +++
sandbox/ggl/formal_review_request/boost/ggl/util/copy.hpp | 18 +
sandbox/ggl/formal_review_request/boost/ggl/util/math.hpp | 45 +++
29 files changed, 1161 insertions(+), 781 deletions(-)
Modified: sandbox/ggl/formal_review_request/boost/ggl/algorithms/area.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/algorithms/area.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/algorithms/area.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -14,12 +14,16 @@
#include <boost/range/metafunctions.hpp>
#include <ggl/algorithms/detail/calculate_null.hpp>
+
+#include <ggl/core/point_order.hpp>
#include <ggl/core/exterior_ring.hpp>
#include <ggl/core/interior_rings.hpp>
#include <ggl/core/ring_type.hpp>
#include <ggl/core/concepts/point_concept.hpp>
#include <ggl/core/concepts/nsphere_concept.hpp>
+
#include <ggl/strategies/strategies.hpp>
+
#include <ggl/util/loop.hpp>
#include <ggl/util/math.hpp>
@@ -98,16 +102,28 @@
};
-// Area of a linear linear_ring, assuming a closed linear_ring
-template<typename R, typename S>
+// Area of a linear linear_ring
+template
+<
+ typename R,
+ order_selector Order,
+ // closing_selector Closed -- for now assuming CLOSED, p(0) == p(n-1)
+ typename S
+>
struct ring_area
+{};
+
+
+template<typename R, typename S>
+struct ring_area<R, clockwise, S>
{
typedef typename S::return_type type;
static inline type apply(R const& ring, S const& strategy)
{
assert_dimension<R, 2>();
- // A closed linear_ring has at least four points, if not there is no area
+ // A closed linear_ring has at least four points,
+ // if not, there is no (zero) area
if (boost::size(ring) >= 4)
{
typename S::state_type state_type;
@@ -121,19 +137,23 @@
}
};
+template<typename R, typename S>
+struct ring_area<R, counterclockwise, S>
+{
+ typedef typename S::return_type type;
+ static inline type apply(R const& ring, S const& strategy)
+ {
+ // Counter clockwise rings negate the area result
+ return -ring_area<R, clockwise, S>::apply(ring, strategy);
+ }
+};
+
+
// Area of a polygon, either clockwise or anticlockwise
-template<typename Polygon, typename Strategy>
+template<typename Polygon, order_selector Order, typename Strategy>
class polygon_area
{
typedef typename Strategy::return_type type;
- static inline type call_abs(type const& v)
- {
-#if defined(NUMERIC_ADAPTOR_INCLUDED)
- return boost::abs(v);
-#else
- return std::abs(v);
-#endif
- }
public:
static inline type apply(Polygon const& poly,
@@ -141,19 +161,26 @@
{
assert_dimension<Polygon, 2>();
- typedef typename ring_type<Polygon>::type ring_type;
+ typedef ring_area
+ <
+ typename ring_type<Polygon>::type,
+ Order,
+ Strategy
+ > ring_area_type;
+
typedef typename boost::range_const_iterator
<
typename interior_type<Polygon>::type
>::type iterator_type;
- type a = call_abs(
- ring_area<ring_type, Strategy>::apply(exterior_ring(poly), strategy));
+ type a = ring_area_type::apply(exterior_ring(poly), strategy);
for (iterator_type it = boost::begin(interior_rings(poly));
it != boost::end(interior_rings(poly)); ++it)
{
- a -= call_abs(ring_area<ring_type, Strategy>::apply(*it, strategy));
+ // Add ring-area (area of hole should be negative
+ // (because other order))
+ a += ring_area_type::apply(*it, strategy);
}
return a;
}
@@ -166,25 +193,35 @@
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch {
-template <typename Tag, typename G, typename S>
-struct area : detail::calculate_null<typename S::return_type, G, S> {};
+template <typename Tag, typename Geometry, order_selector Order, typename Strategy>
+struct area
+ : detail::calculate_null
+ <
+ typename Strategy::return_type,
+ Geometry,
+ Strategy
+ > {};
-template <typename G, typename S>
-struct area<box_tag, G, S> : detail::area::box_area<G, S> {};
+template <typename Geometry, order_selector Order, typename Strategy>
+struct area<box_tag, Geometry, Order, Strategy>
+ : detail::area::box_area<Geometry, Strategy> {};
-template <typename G, typename S>
-struct area<nsphere_tag, G, S> : detail::area::circle_area<G, S> {};
+template <typename Geometry, order_selector Order, typename Strategy>
+struct area<nsphere_tag, Geometry, Order, Strategy>
+ : detail::area::circle_area<Geometry, Strategy> {};
// Area of ring currently returns area of closed rings but it might be argued
// that it is 0.0, because a ring is just a line.
-template <typename G, typename S>
-struct area<ring_tag, G, S> : detail::area::ring_area<G, S> {};
-
-template <typename G, typename S>
-struct area<polygon_tag, G, S> : detail::area::polygon_area<G, S> {};
+template <typename Geometry, order_selector Order, typename Strategy>
+struct area<ring_tag, Geometry, Order, Strategy>
+ : detail::area::ring_area<Geometry, Order, Strategy> {};
+
+template <typename Geometry, order_selector Order, typename Strategy>
+struct area<polygon_tag, Geometry, Order, Strategy>
+ : detail::area::polygon_area<Geometry, Order, Strategy> {};
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
@@ -207,7 +244,7 @@
\ingroup area
\details The function area returns the area of a polygon, ring, box or circle,
using the default area-calculation strategy. Strategies are
- provided for cartesian ans spherical points
+ provided for cartesian and spherical coordinate systems
The geometries should correct, polygons should be closed and orientated clockwise, holes,
if any, must be orientated counter clockwise
\param geometry a geometry
@@ -222,6 +259,7 @@
<
typename tag<Geometry>::type,
Geometry,
+ ggl::point_order<Geometry>::value,
strategy_type
>::apply(geometry, strategy_type());
}
@@ -243,6 +281,7 @@
<
typename tag<Geometry>::type,
Geometry,
+ ggl::point_order<Geometry>::value,
Strategy
>::apply(geometry, strategy);
}
Modified: sandbox/ggl/formal_review_request/boost/ggl/algorithms/convert.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/algorithms/convert.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/algorithms/convert.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -59,19 +59,29 @@
namespace dispatch
{
-template <typename T1, typename T2, typename G1, typename G2>
+template
+<
+ typename T1, typename T2,
+ std::size_t Dimensions,
+ typename G1, typename G2
+>
struct convert
{
};
-template <typename T, typename G1, typename G2>
-struct convert<T, T, G1, G2>
+template
+<
+ typename T,
+ std::size_t Dimensions,
+ typename G1, typename G2
+>
+struct convert<T, T, Dimensions, G1, G2>
{
// Same geometry type -> copy coordinates from G1 to G2
};
-template <typename T, typename G>
-struct convert<T, T, G, G>
+template <typename T, std::size_t Dimensions, typename G>
+struct convert<T, T, Dimensions, G, G>
{
// Same geometry -> can be copied
};
@@ -79,14 +89,11 @@
// Partial specializations
template <typename B, typename R>
-struct convert<box_tag, ring_tag, B, R>
+struct convert<box_tag, ring_tag, 2, B, R>
{
static inline void apply(B const& box, R& ring)
{
// go from box to ring -> add coordinates in correct order
- // only valid for 2D
- assert_dimension<B, 2>();
-
ring.clear();
typename point_type<B>::type point;
@@ -108,26 +115,29 @@
};
template <typename B, typename P>
-struct convert<box_tag, polygon_tag, B, P>
+struct convert<box_tag, polygon_tag, 2, B, P>
{
static inline void apply(B const& box, P& polygon)
{
typedef typename ring_type<P>::type ring_type;
- convert<box_tag, ring_tag, B, ring_type>::apply(box, exterior_ring(polygon));
+ convert<box_tag, ring_tag, 2, B, ring_type>::apply(box, exterior_ring(polygon));
}
};
-template <typename P, typename B>
-struct convert<point_tag, box_tag, P, B>
+template <typename P, std::size_t Dimensions, typename B>
+struct convert<point_tag, box_tag, Dimensions, P, B>
{
static inline void apply(P const& point, B& box)
{
- // go from point to box -> box with volume of zero, 2D or 3D
- static const std::size_t N = dimension<P>::value;
-
- detail::convert::point_to_box<P, B, min_corner, 0, N>::apply(point, box);
- detail::convert::point_to_box<P, B, max_corner, 0, N>::apply(point, box);
+ detail::convert::point_to_box
+ <
+ P, B, min_corner, 0, Dimensions
+ >::apply(point, box);
+ detail::convert::point_to_box
+ <
+ P, B, max_corner, 0, Dimensions
+ >::apply(point, box);
}
};
@@ -147,10 +157,13 @@
template <typename G1, typename G2>
inline void convert(G1 const& geometry1, G2& geometry2)
{
+ assert_dimension_equal<G1, G2>();
+
dispatch::convert
<
typename tag<G1>::type,
typename tag<G2>::type,
+ dimension<G1>::type::value,
G1,
G2
>::apply(geometry1, geometry2);
Modified: sandbox/ggl/formal_review_request/boost/ggl/algorithms/convex_hull.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/algorithms/convex_hull.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/algorithms/convex_hull.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -10,11 +10,12 @@
#define GGL_ALGORITHMS_CONVEX_HULL_HPP
-#include <boost/concept/requires.hpp>
#include <boost/type_traits/remove_const.hpp>
#include <ggl/core/cs.hpp>
#include <ggl/core/is_multi.hpp>
+#include <ggl/core/point_order.hpp>
+#include <ggl/core/exterior_ring.hpp>
#include <ggl/core/concepts/point_concept.hpp>
@@ -32,7 +33,7 @@
\see http://en.wikipedia.org/wiki/Convex_hull
\par Performance
-2776 counties of US are "hulled" in 0.52 seconds (other libraries: 2.8 seconds, 2.4 seconds, 3.4 seconds, 1.1 seconds)
+2776 counties of US are "hulled" in 0.9 seconds (other libraries: 0.9, 4.1, 3.3, 1.4 seconds)
\note The convex hull is always a ring, holes are not possible. Therefore it is modelled as an output iterator.
This gives the most flexibility, the user can decide what to do with it.
@@ -46,9 +47,16 @@
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace convex_hull {
-template <typename Geometry, typename OutputIterator>
-struct hull
+template
+<
+ typename Geometry,
+ order_selector Order
+>
+struct hull_inserter
{
+ // Member template function, to avoid inconvenient declaration
+ // of output-iterator-type
+ template <typename OutputIterator>
static inline OutputIterator apply(Geometry const& geometry,
OutputIterator out)
{
@@ -60,12 +68,39 @@
point_type
>::type strategy_type;
- strategy_type s(as_range<typename as_range_type<Geometry>::type>(geometry));
- s.get(out);
+ strategy_type s(as_range
+ <
+ typename as_range_type<Geometry>::type
+ >(geometry));
+ s.get(out, Order == clockwise);
return out;
}
};
+template
+<
+ typename Geometry,
+ typename OutputGeometry
+>
+struct hull_to_geometry
+{
+ static inline void apply(Geometry const& geometry, OutputGeometry& out)
+ {
+ hull_inserter
+ <
+ Geometry,
+ ggl::point_order<OutputGeometry>::value
+ >::apply(geometry,
+ std::back_inserter(
+ ggl::as_range
+ <
+ typename ggl::as_range_type<OutputGeometry>::type
+ >(out)));
+ }
+};
+
+
+
}} // namespace detail::convex_hull
#endif // DOXYGEN_NO_DETAIL
@@ -76,52 +111,143 @@
template
<
+ typename Tag1,
+ bool IsMulti,
+ typename Polygon, typename Output
+>
+struct convex_hull
+{};
+
+
+template <typename Polygon, typename Output>
+struct convex_hull
+<
+ polygon_tag, false,
+ Polygon, Output
+>
+ : detail::convex_hull::hull_to_geometry<Polygon, Output>
+{};
+
+template <typename Polygon, typename Output>
+struct convex_hull
+<
+ ring_tag, false,
+ Polygon, Output
+>
+ : detail::convex_hull::hull_to_geometry<Polygon, Output>
+{};
+
+template <typename Polygon, typename Output>
+struct convex_hull
+<
+ linestring_tag, false,
+ Polygon, Output
+>
+ : detail::convex_hull::hull_to_geometry<Polygon, Output>
+{};
+
+
+
+template
+<
typename GeometryTag,
+ order_selector Order,
bool IsMulti,
- typename Geometry,
- typename OutputIterator
+ typename GeometryIn
>
-struct convex_hull {};
+struct convex_hull_inserter {};
-template <typename Linestring, typename OutputIterator>
-struct convex_hull<linestring_tag, false, Linestring, OutputIterator>
- : detail::convex_hull::hull<Linestring, OutputIterator>
+template <typename Linestring, order_selector Order>
+struct convex_hull_inserter
+<
+ linestring_tag,
+ Order, false,
+ Linestring
+>
+ : detail::convex_hull::hull_inserter<Linestring, Order>
{};
-template <typename Ring, typename OutputIterator>
-struct convex_hull<ring_tag, false, Ring, OutputIterator>
- : detail::convex_hull::hull<Ring, OutputIterator>
+
+template <typename Ring, order_selector Order>
+struct convex_hull_inserter
+<
+ ring_tag,
+ Order, false,
+ Ring
+>
+ : detail::convex_hull::hull_inserter<Ring, Order>
{};
-template <typename Polygon, typename OutputIterator>
-struct convex_hull<polygon_tag, false, Polygon, OutputIterator>
- : detail::convex_hull::hull<Polygon, OutputIterator>
+
+template <typename Polygon, order_selector Order>
+struct convex_hull_inserter
+<
+ polygon_tag,
+ Order, false,
+ Polygon
+>
+ : detail::convex_hull::hull_inserter<Polygon, Order>
{};
+
+
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
+
+
/*!
\brief Calculate the convex hull of a geometry
\ingroup convex_hull
+ \tparam Geometry1 the input geometry type
+ \tparam Geometry2: the output geometry type
+ \param geometry the geometry to calculate convex hull from
+ \param out a geometry receiving points of the convex hull
+ \note the output may be:
+ - a polygon
+ - a ring
+
+ */
+template<typename Geometry1, typename Geometry2>
+inline void convex_hull(Geometry1 const& geometry,
+ Geometry2& out)
+{
+ dispatch::convex_hull
+ <
+ typename tag<Geometry1>::type,
+ is_multi<Geometry1>::type::value,
+ Geometry1,
+ Geometry2
+ >::apply(geometry, out);
+}
+
+
+/*!
+ \brief Calculate the convex hull of a geometry, output-iterator version
+ \ingroup convex_hull
+ \tparam Geometry the input geometry type
+ \tparam OutputIterator: an output-iterator
\param geometry the geometry to calculate convex hull from
\param out an output iterator outputing points of the convex hull
- \return the output iterator
+ \note This overloaded version outputs to an output iterator.
+ In this case, nothing is known about its point-type or
+ about its clockwise order. Therefore, the input point-type and order are copied
+
*/
template<typename Geometry, typename OutputIterator>
-inline OutputIterator convex_hull(Geometry const& geometry, OutputIterator out)
+inline OutputIterator convex_hull_inserter(Geometry const& geometry,
+ OutputIterator out)
{
- typedef typename boost::remove_const<Geometry>::type ncg_type;
-
- return dispatch::convex_hull
+ return dispatch::convex_hull_inserter
<
- typename tag<ncg_type>::type,
- is_multi<ncg_type>::type::value,
- Geometry,
- OutputIterator
+ typename tag<Geometry>::type,
+ ggl::point_order<Geometry>::value,
+ is_multi<Geometry>::type::value,
+ Geometry
>::apply(geometry, out);
}
+
} // namespace ggl
#endif // GGL_ALGORITHMS_CONVEX_HULL_HPP
Modified: sandbox/ggl/formal_review_request/boost/ggl/algorithms/correct.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/algorithms/correct.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/algorithms/correct.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -10,6 +10,7 @@
#define GGL_ALGORITHMS_CORRECT_HPP
#include <algorithm>
+#include <functional>
#include <boost/range/functions.hpp>
#include <boost/range/metafunctions.hpp>
@@ -31,84 +32,122 @@
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace correct {
-// correct an box: make min/max are correct
-template <typename B>
-inline void correct_box(B& b)
+
+template <typename Box, int Dimension, int DimensionCount>
+struct correct_box_loop
{
- // Currently only for Cartesian coordinates
- // TODO: adapt using strategies
- // TODO: adapt using traits
- typedef typename coordinate_type<B>::type coordinate_type;
+ typedef typename coordinate_type<Box>::type coordinate_type;
- if (get<min_corner, 0>(b) > get<max_corner, 0>(b))
+ static inline void apply(Box& box)
{
- coordinate_type max_value = get<min_corner, 0>(b);
- coordinate_type min_value = get<max_corner, 0>(b);
- set<min_corner, 0>(b, min_value);
- set<max_corner, 0>(b, max_value);
- }
+ if (get<min_corner, Dimension>(box) > get<max_corner, Dimension>(box))
+ {
+ // Swap the coordinates
+ coordinate_type max_value = get<min_corner, Dimension>(box);
+ coordinate_type min_value = get<max_corner, Dimension>(box);
+ set<min_corner, Dimension>(box, min_value);
+ set<max_corner, Dimension>(box, max_value);
+ }
- if (get<min_corner, 1>(b) > get<max_corner, 1>(b))
- {
- coordinate_type max_value = get<min_corner, 1>(b);
- coordinate_type min_value = get<max_corner, 1>(b);
- set<min_corner, 1>(b, min_value);
- set<max_corner, 1>(b, max_value);
+ correct_box_loop
+ <
+ Box, Dimension + 1, DimensionCount
+ >::apply(box);
}
-}
+};
-// close a linear_ring, if not closed
-template <typename R>
-inline void ensure_closed_ring(R& r)
+
+
+template <typename Box, int DimensionCount>
+struct correct_box_loop<Box, DimensionCount, DimensionCount>
+{
+ static inline void apply(Box& box)
+ {}
+
+};
+
+
+// correct an box: make min/max are correct
+template <typename Box>
+struct correct_box
{
- if (boost::size(r) > 2)
+
+ static inline void apply(Box& box)
{
- // check if closed, if not, close it
- if (ggl::disjoint(r.front(), r.back()))
- {
- r.push_back(r.front());
- }
+ // Currently only for Cartesian coordinates
+ // TODO: adapt using strategies
+ correct_box_loop
+ <
+ Box, 0, dimension<Box>::type::value
+ >::apply(box);
}
-}
+};
-// correct a polygon: normalizes all rings, sets outer linear_ring clockwise, sets all
-// inner rings counter clockwise
-template <typename Y>
-inline void correct_polygon(Y& poly)
+
+// close a linear_ring, if not closed
+template <typename Ring, typename Predicate>
+struct correct_ring
{
- typename ring_type<Y>::type& outer = exterior_ring(poly);
- ensure_closed_ring(outer);
+ typedef typename point_type<Ring>::type point_type;
- typedef typename point_type<Y>::type point_type;
- typedef typename ring_type<Y>::type ring_type;
typedef typename strategy_area
<
typename cs_tag<point_type>::type,
point_type
>::type strategy_type;
- strategy_type strategy;
+ typedef detail::area::ring_area
+ <
+ Ring,
+ ggl::point_order<Ring>::value,
+ strategy_type
+ > ring_area_type;
- if (detail::area::ring_area<ring_type, strategy_type>::apply(outer, strategy) < 0)
+
+ static inline void apply(Ring& r)
{
- std::reverse(boost::begin(outer), boost::end(outer));
+ // Check close-ness
+ if (boost::size(r) > 2)
+ {
+ // check if closed, if not, close it
+ if (ggl::disjoint(r.front(), r.back()))
+ {
+ r.push_back(r.front());
+ }
+ }
+ // Check area
+ Predicate predicate;
+ if (predicate(ring_area_type::apply(r, strategy_type()), 0))
+ {
+ std::reverse(boost::begin(r), boost::end(r));
+ }
}
+};
- typedef typename boost::range_iterator
- <
- typename interior_type<Y>::type
- >::type iterator_type;
+// correct a polygon: normalizes all rings, sets outer linear_ring clockwise, sets all
+// inner rings counter clockwise
+template <typename Polygon>
+struct correct_polygon
+{
+ typedef typename ring_type<Polygon>::type ring_type;
- for (iterator_type it = boost::begin(interior_rings(poly));
- it != boost::end(interior_rings(poly)); ++it)
+ static inline void apply(Polygon& poly)
{
- ensure_closed_ring(*it);
- if (detail::area::ring_area<ring_type, strategy_type>::apply(*it, strategy) > 0)
+ correct_ring<ring_type, std::less<double> >::apply(exterior_ring(poly));
+
+ typedef typename boost::range_iterator
+ <
+ typename interior_type<Polygon>::type
+ >::type iterator_type;
+
+ for (iterator_type it = boost::begin(interior_rings(poly));
+ it != boost::end(interior_rings(poly)); ++it)
{
- std::reverse(boost::begin(*it), boost::end(*it));
+ correct_ring<ring_type, std::greater<double> >::apply(*it);
}
}
-}
+};
+
}} // namespace detail::correct
#endif // DOXYGEN_NO_DETAIL
@@ -122,30 +161,19 @@
template <typename B>
struct correct<box_tag, B>
-{
- static inline void apply(B& box)
- {
- detail::correct::correct_box(box);
- }
-};
+ : detail::correct::correct_box<B>
+{};
template <typename R>
struct correct<ring_tag, R>
-{
- static inline void apply(R& ring)
- {
- detail::correct::ensure_closed_ring(ring);
- }
-};
+ : detail::correct::correct_ring<R, std::less<double> >
+{};
template <typename P>
struct correct<polygon_tag, P>
-{
- static inline void apply(P& poly)
- {
- detail::correct::correct_polygon(poly);
- }
-};
+ : detail::correct::correct_polygon<P>
+{};
+
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
Modified: sandbox/ggl/formal_review_request/boost/ggl/algorithms/disjoint.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/algorithms/disjoint.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/algorithms/disjoint.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -36,7 +36,7 @@
static inline bool apply(P1 const& p1, P2 const& p2)
{
- if (! math::equals(get<D>(p1), get<D>(p2)))
+ if (! ggl::math::equals(get<D>(p1), get<D>(p2)))
{
return true;
}
Modified: sandbox/ggl/formal_review_request/boost/ggl/algorithms/equals.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/algorithms/equals.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/algorithms/equals.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -39,8 +39,8 @@
{
static inline bool apply(B1 const& box1, B2 const& box2)
{
- if (!math::equals(get<min_corner, D>(box1), get<min_corner, D>(box2))
- || !math::equals(get<max_corner, D>(box1), get<max_corner, D>(box2)))
+ if (!ggl::math::equals(get<min_corner, D>(box1), get<min_corner, D>(box2))
+ || !ggl::math::equals(get<max_corner, D>(box1), get<max_corner, D>(box2)))
{
return false;
}
Modified: sandbox/ggl/formal_review_request/boost/ggl/algorithms/overlay/merge_intersection_points.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/algorithms/overlay/merge_intersection_points.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/algorithms/overlay/merge_intersection_points.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -38,7 +38,7 @@
coordinate_type const& left0 = ggl::get<0>(lhs);
coordinate_type const& right0 = ggl::get<0>(rhs);
- return math::equals(left0, right0)
+ return ggl::math::equals(left0, right0)
? ggl::get<1>(lhs) < ggl::get<1>(rhs)
: left0 < right0;
}
Modified: sandbox/ggl/formal_review_request/boost/ggl/algorithms/simplify.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/algorithms/simplify.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/algorithms/simplify.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -12,12 +12,20 @@
#include <boost/range/functions.hpp>
#include <boost/range/metafunctions.hpp>
-#include <ggl/algorithms/distance.hpp>
+#include <boost/concept/requires.hpp>
+#include <boost/concept_check.hpp>
+
#include <ggl/core/cs.hpp>
#include <ggl/core/ring_type.hpp>
#include <ggl/core/exterior_ring.hpp>
#include <ggl/core/interior_rings.hpp>
-#include <ggl/strategies/agnostic/agn_simplify.hpp>
+
+#include <ggl/strategies/strategies.hpp>
+#include <ggl/strategies/agnostic/simplify_douglas_peucker.hpp>
+#include <ggl/strategies/concepts/simplify_concept.hpp>
+
+#include <ggl/algorithms/clear.hpp>
+
/*!
@@ -49,115 +57,107 @@
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace simplify {
-template<typename R, typename OutputIterator, typename S>
-inline void simplify_range_strategy(R const& range, OutputIterator out, double max_distance, S const& strategy)
+template<typename Range, typename Strategy>
+struct simplify_range_inserter
{
- if (boost::begin(range) == boost::end(range) || max_distance < 0)
- {
- std::copy(boost::begin(range), boost::end(range), out);
- }
- else
+ template <typename OutputIterator>
+ static inline void apply(Range const& range, OutputIterator out,
+ double max_distance, Strategy const& strategy)
{
- typename boost::range_const_iterator<R>::type it = boost::begin(range) + 1;
- if (it == boost::end(range) || it + 1 == boost::end(range))
+ if (boost::size(range) <= 2 || max_distance < 0)
{
std::copy(boost::begin(range), boost::end(range), out);
}
else
{
- strategy.simplify(range, out, max_distance);
+ strategy.apply(range, out, max_distance);
}
}
-}
+};
-template<typename R, typename OutputIterator>
-inline void simplify_range(R const& range, OutputIterator out, double max_distance)
-{
- // Define default strategy
- typedef typename point_type<R>::type point_type;
- typedef typename cs_tag<point_type>::type cs_tag;
- typedef typename strategy_distance_segment
- <
- cs_tag,
- cs_tag,
- point_type,
- segment<const point_type>
- >::type strategy_type;
- strategy::simplify::douglas_peucker<R, OutputIterator, strategy_type> douglas;
+template<typename Range, typename Strategy>
+struct simplify_copy
+{
+ static inline void apply(Range const& range, Range& out,
+ double max_distance, Strategy const& strategy)
+ {
+ std::copy
+ (
+ boost::begin(range), boost::end(range), std::back_inserter(out)
+ );
+ }
+};
- simplify_range_strategy(range, out, max_distance, douglas);
-}
-template<typename R, typename OutputIterator, typename S>
-inline void simplify_ring(R const& r_in, OutputIterator out, double max_distance, S const& strategy)
+template<typename Range, typename Strategy, std::size_t Minimum>
+struct simplify_range
{
- // Call do_container for a ring
+ static inline void apply(Range const& range, Range& out,
+ double max_distance, Strategy const& strategy)
+ {
+ // Call do_container for a linestring / ring
- // The first/last point (the closing point of the ring) should maybe be excluded because it
- // lies on a line with second/one but last. Here it is never excluded.
+ // For a RING:
+ // The first/last point (the closing point of the ring) should maybe be excluded because it
+ // lies on a line with second/one but last. Here it is never excluded.
- // Note also that, especially if max_distance is too large, the output ring might be self intersecting
- // while the input ring is not, although chances are low in normal polygons
+ // Note also that, especially if max_distance is too large, the output ring might be self intersecting
+ // while the input ring is not, although chances are low in normal polygons
- // Finally the inputring might have 4 points (=correct), the output < 4(=wrong)
- if (boost::size(r_in) <= 4 || max_distance < 0)
- {
- std::copy(boost::begin(r_in), boost::end(r_in), out);
- }
- else
- {
- simplify_range_strategy(r_in, out, max_distance, strategy);
+ // Finally the inputring might have 4 points (=correct), the output < 4(=wrong)
+
+ if (boost::size(range) <= int(Minimum) || max_distance < 0.0)
+ {
+ simplify_copy<Range, Strategy>::apply
+ (
+ range, out, max_distance, strategy
+ );
+ }
+ else
+ {
+ simplify_range_inserter<Range, Strategy>::apply
+ (
+ range, std::back_inserter(out), max_distance, strategy
+ );
+ }
}
-}
+};
-template<typename Y, typename S>
-inline void simplify_polygon(Y const& poly_in, Y& poly_out, double max_distance, S const& strategy)
+template<typename Polygon, typename Strategy>
+struct simplify_polygon
{
- typedef typename boost::range_iterator
- <typename interior_type<Y>::type>::type iterator_type;
- typedef typename boost::range_const_iterator
- <typename interior_type<Y>::type>::type const_iterator_type;
+ static inline void apply(Polygon const& poly_in, Polygon& poly_out,
+ double max_distance, Strategy const& strategy)
+ {
+ typedef typename ring_type<Polygon>::type ring_type;
- poly_out.clear();
+ typedef typename boost::range_iterator
+ <typename interior_type<Polygon>::type>::type iterator_type;
+ typedef typename boost::range_const_iterator
+ <typename interior_type<Polygon>::type>::type const_iterator_type;
- // Note that if there are inner rings, and distance is too large, they might intersect with the
- // outer ring in the output, while it didn't in the input.
- simplify_ring(exterior_ring(poly_in), std::back_inserter(exterior_ring(poly_out)),
- max_distance, strategy);
+ // Note that if there are inner rings, and distance is too large,
+ // they might intersect with the outer ring in the output,
+ // while it didn't in the input.
+ simplify_range<ring_type, Strategy, 4>::apply(exterior_ring(poly_in),
+ exterior_ring(poly_out),
+ max_distance, strategy);
- interior_rings(poly_out).resize(boost::size(interior_rings(poly_in)));
+ interior_rings(poly_out).resize(boost::size(interior_rings(poly_in)));
- const_iterator_type it_in = boost::begin(interior_rings(poly_in));
- iterator_type it_out = boost::begin(interior_rings(poly_out));
+ iterator_type it_out = boost::begin(interior_rings(poly_out));
- for (; it_in != boost::end(interior_rings(poly_in)); it_in++, it_out++)
- {
- simplify_ring(*it_in, std::back_inserter(*it_out), max_distance, strategy);
+ for (const_iterator_type it_in = boost::begin(interior_rings(poly_in));
+ it_in != boost::end(interior_rings(poly_in));
+ ++it_in, ++it_out)
+ {
+ simplify_range<ring_type, Strategy, 4>::apply(*it_in,
+ *it_out, max_distance, strategy);
+ }
}
-}
-
-template<typename Y>
-inline void simplify_polygon(Y const& poly_in, Y& poly_out, double max_distance)
-{
- // Define default strategy
- typedef typename ring_type<Y>::type ring_type;
- typedef std::back_insert_iterator<ring_type> iterator_type;
-
- typedef typename point_type<Y>::type point_type;
- typedef typename cs_tag<point_type>::type cs_tag;
- typedef typename strategy_distance_segment
- <
- cs_tag,
- cs_tag,
- point_type,
- segment<const point_type>
- >::type strategy_type;
+};
- strategy::simplify::douglas_peucker<ring_type, iterator_type, strategy_type> douglas;
-
- simplify_polygon(poly_in, poly_out, max_distance, douglas);
-}
}} // namespace detail::simplify
#endif // DOXYGEN_NO_DETAIL
@@ -167,118 +167,142 @@
namespace dispatch
{
-template <typename Tag, typename G>
+template <typename Tag, typename Geometry, typename Strategy>
struct simplify
{
};
-// Partial specializations
-template <typename R>
-struct simplify<linestring_tag, R>
+template <typename Point, typename Strategy>
+struct simplify<point_tag, Point, Strategy>
{
- template<typename OutputIterator, typename S>
- static inline void apply(R const& range, OutputIterator out, double max_distance, S const& strategy)
+ static inline void apply(Point const& point, Point& out,
+ double max_distance, Strategy const& strategy)
{
- strategy.simplify(range, out, max_distance);
+ copy_coordinates(point, out);
}
+};
- template<typename OutputIterator>
- static inline void apply(R const& range, OutputIterator out, double max_distance)
- {
- // Define default strategy
- typedef typename point_type<R>::type point_type;
- typedef typename cs_tag<point_type>::type cs_tag;
- typedef typename strategy_distance_segment
+
+template <typename Linestring, typename Strategy>
+struct simplify<linestring_tag, Linestring, Strategy>
+ : detail::simplify::simplify_range
+ <
+ Linestring,
+ Strategy,
+ 2
+ >
+{};
+
+template <typename Ring, typename Strategy>
+struct simplify<ring_tag, Ring, Strategy>
+ : detail::simplify::simplify_range
<
- cs_tag,
- cs_tag,
- point_type,
- segment<const point_type>
- >::type strategy_type;
+ Ring,
+ Strategy,
+ 4
+ >
+{};
+
+template <typename Polygon, typename Strategy>
+struct simplify<polygon_tag, Polygon, Strategy>
+ : detail::simplify::simplify_polygon
+ <
+ Polygon,
+ Strategy
+ >
+{};
- strategy::simplify::douglas_peucker<R, OutputIterator, strategy_type> douglas;
- detail::simplify::simplify_range_strategy(range, out, max_distance, douglas);
- }
+template <typename Tag, typename Geometry, typename Strategy>
+struct simplify_inserter
+{
};
-template <typename R>
-struct simplify<ring_tag, R>
-{
- /// Simplify a ring, using a strategy
- template<typename S>
- static inline void apply(R const& ring_in, R& ring_out, double max_distance, S const& strategy)
- {
- using detail::simplify::simplify_ring;
- simplify_ring(ring_in, std::back_inserter(ring_out), max_distance, strategy);
- }
- /// Simplify a ring
- static inline void apply(R const& ring_in, R& ring_out, double max_distance)
- {
- // Define default strategy
- typedef typename point_type<R>::type point_type;
- typedef typename cs_tag<point_type>::type cs_tag;
- typedef typename strategy_distance_segment
+template <typename Linestring, typename Strategy>
+struct simplify_inserter<linestring_tag, Linestring, Strategy>
+ : detail::simplify::simplify_range_inserter
<
- cs_tag,
- cs_tag,
- point_type,
- segment<const point_type>
- >::type strategy_type;
- typedef std::back_insert_iterator<R> iterator_type;
+ Linestring,
+ Strategy
+ >
+{};
+
+template <typename Ring, typename Strategy>
+struct simplify_inserter<ring_tag, Ring, Strategy>
+ : detail::simplify::simplify_range_inserter
+ <
+ Ring,
+ Strategy
+ >
+{};
- strategy::simplify::douglas_peucker<R, iterator_type, strategy_type> douglas;
- detail::simplify::simplify_ring(ring_in, std::back_inserter(ring_out), max_distance, douglas);
- }
-};
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
-template <typename P>
-struct simplify<polygon_tag, P>
+/*!
+ \brief Simplify a geometry
+ \ingroup simplify
+ \details This version of simplify simplifies a geometry using a specified strategy
+ where the output is of the same geometry type as the input.
+ \param geometry input geometry, to be simplified
+ \param out output geometry, simplified version of the input geometry
+ \param max_distance distance (in units of input coordinates) of a vertex to other segments to be removed
+ \param strategy simplify strategy to be used for simplification, might include point-distance strategy
+ */
+template<typename Geometry, typename Strategy>
+inline void simplify(Geometry const& geometry, Geometry& out,
+ double max_distance, Strategy const& strategy)
{
- /// Simplify a polygon, using a strategy
- template<typename S>
- static inline void apply(P const& poly_in, P& poly_out, double max_distance, S const& strategy)
- {
- detail::simplify::simplify_polygon(poly_in, poly_out, max_distance, strategy);
- }
+ BOOST_CONCEPT_ASSERT( (ggl::concept::SimplifyStrategy<Strategy>) );
- /// Simplify a polygon
- static inline void apply(P const& poly_in, P& poly_out, double max_distance)
- {
- detail::simplify::simplify_polygon(poly_in, poly_out, max_distance);
- }
-};
+ ggl::clear(out);
+
+ dispatch::simplify
+ <
+ typename tag<Geometry>::type,
+ Geometry,
+ Strategy
+ >::apply(geometry, out, max_distance, strategy);
+}
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-// Model 1, using output iterator
/*!
\brief Simplify a geometry
\ingroup simplify
- \details The simplify algorithm removes points, keeping the shape as much as possible.
- This version of simplify uses an output iterator
- \param geometry the geometry to be simplified, being a ggl::linestring, vector, iterator pair, or any other boost compatible range
- \param out output iterator, outputs all simplified points
+ \details This version of simplify simplifies a geometry using the default strategy (Douglas Peucker),
+ where the output is of the same geometry type as the input.
+ \param geometry input geometry, to be simplified
+ \param out output geometry, simplified version of the input geometry
\param max_distance distance (in units of input coordinates) of a vertex to other segments to be removed
- \par Example:
- The simplify algorithm can be used as following:
- \dontinclude doxygen_examples.cpp
- \skip example_simplify_linestring1
- \line {
- \until }
*/
-template<typename G, typename O>
-inline void simplify(const G& geometry, O out, double max_distance)
+template<typename Geometry>
+inline void simplify(Geometry const& geometry, Geometry& out,
+ double max_distance)
{
- typedef dispatch::simplify<typename tag<G>::type, G> simplify_type;
- simplify_type::apply(geometry, out, max_distance);
+ typedef typename point_type<Geometry>::type point_type;
+ typedef typename cs_tag<point_type>::type cs_tag;
+ typedef typename strategy_distance_segment
+ <
+ cs_tag,
+ cs_tag,
+ point_type,
+ ggl::segment<const point_type>
+ >::type ds_strategy_type;
+
+ typedef strategy::simplify::douglas_peucker
+ <
+ point_type, ds_strategy_type
+ > strategy_type;
+
+ simplify(geometry, out, max_distance, strategy_type());
}
+
/*!
\brief Simplify a geometry
\ingroup simplify
@@ -295,48 +319,65 @@
\line {
\until }
*/
-template<typename G, typename O, typename S>
-inline void simplify(const G& geometry, O out, double max_distance, S const& strategy)
+template<typename Geometry, typename OutputIterator, typename Strategy>
+inline void simplify_inserter(Geometry const& geometry, OutputIterator out,
+ double max_distance, Strategy const& strategy)
{
- typedef dispatch::simplify<typename tag<G>::type, G> simplify_type;
- simplify_type::apply(geometry, out, max_distance, strategy);
-}
+ BOOST_CONCEPT_ASSERT( (ggl::concept::SimplifyStrategy<Strategy>) );
-// Model 2, where output is same type as input
-
-/*!
- \brief Simplify a geometry
- \ingroup simplify
- \details This version of simplify simplifies a geometry using the default strategy (Douglas Peucker),
- where the output is of the same geometry type as the input.
- \param geometry input geometry, to be simplified
- \param out output geometry, simplified version of the input geometry
- \param max_distance distance (in units of input coordinates) of a vertex to other segments to be removed
- */
-template<typename G>
-inline void simplify(const G& geometry, G& out, double max_distance)
-{
- typedef dispatch::simplify<typename tag<G>::type, G> simplify_type;
- simplify_type::apply(geometry, out, max_distance);
+ dispatch::simplify_inserter
+ <
+ typename tag<Geometry>::type,
+ Geometry,
+ Strategy
+ >::apply(geometry, out, max_distance, strategy);
}
/*!
\brief Simplify a geometry
\ingroup simplify
- \details This version of simplify simplifies a geometry using a specified strategy
- where the output is of the same geometry type as the input.
- \param geometry input geometry, to be simplified
- \param out output geometry, simplified version of the input geometry
+ \details The simplify algorithm removes points, keeping the shape as much as possible.
+ This version of simplify uses an output iterator
+ \param geometry the geometry to be simplified, being a ggl::linestring, vector, iterator pair, or any other boost compatible range
+ \param out output iterator, outputs all simplified points
\param max_distance distance (in units of input coordinates) of a vertex to other segments to be removed
- \param strategy simplify strategy to be used for simplification, might include point-distance strategy
+ \par Example:
+ The simplify algorithm can be used as following:
+ \dontinclude doxygen_examples.cpp
+ \skip example_simplify_linestring1
+ \line {
+ \until }
*/
-template<typename G, typename S>
-inline void simplify(const G& geometry, G& out, double max_distance, S const& strategy)
+template<typename Geometry, typename OutputIterator>
+inline void simplify_inserter(Geometry const& geometry, OutputIterator out,
+ double max_distance)
{
- typedef dispatch::simplify<typename tag<G>::type, G> simplify_type;
- simplify_type::apply(geometry, out, max_distance, strategy);
+ typedef typename point_type<Geometry>::type point_type;
+ typedef typename cs_tag<point_type>::type cs_tag;
+ typedef typename strategy_distance_segment
+ <
+ cs_tag,
+ cs_tag,
+ point_type,
+ ggl::segment<const point_type>
+ >::type ds_strategy_type;
+
+ //typedef typename ggl::as_range_type<Geometry>::type range_type;
+
+ typedef strategy::simplify::douglas_peucker
+ <
+ point_type, ds_strategy_type
+ > strategy_type;
+
+ dispatch::simplify_inserter
+ <
+ typename tag<Geometry>::type,
+ Geometry,
+ strategy_type
+ >::apply(geometry, out, max_distance, strategy_type());
}
+
} // namespace ggl
#endif // GGL_ALGORITHMS_SIMPLIFY_HPP
Added: sandbox/ggl/formal_review_request/boost/ggl/core/point_order.hpp
==============================================================================
--- (empty file)
+++ sandbox/ggl/formal_review_request/boost/ggl/core/point_order.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -0,0 +1,98 @@
+// Generic Geometry Library
+//
+// Copyright Barend Gehrels 1995-2009, Geodan Holding B.V. 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 GGL_CORE_POINT_ORDER_HPP
+#define GGL_CORE_POINT_ORDER_HPP
+
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
+#include <boost/type_traits/remove_const.hpp>
+
+#include <ggl/core/ring_type.hpp>
+#include <ggl/core/tag.hpp>
+#include <ggl/core/tags.hpp>
+
+namespace ggl {
+
+
+enum order_selector { clockwise = 1, counterclockwise = 2, order_undetermined = 0 };
+
+namespace traits {
+
+/*!
+ \brief Traits class indicating the order of contained points within a
+ ring or (multi)polygon, clockwise, counter clockwise or not known.
+ \ingroup traits
+ \par Geometries:
+ - ring
+ - polygon
+ - multi polygon
+ \par Specializations should provide:
+ - typedef P type (where P should fulfil the Point concept)
+ \tparam G geometry
+*/
+template <typename G>
+struct point_order
+{
+ static const order_selector value = clockwise;
+};
+
+
+} // namespace traits
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace core_dispatch
+{
+
+template <typename Tag, typename Geometry>
+struct point_order
+{
+ static const order_selector value = clockwise;
+};
+
+
+
+template <typename Ring>
+struct point_order<ring_tag, Ring>
+{
+ static const order_selector value = ggl::traits::point_order<Ring>::value;
+};
+
+// Specialization for polygon: the order is the order of its rings
+template <typename Polygon>
+struct point_order<polygon_tag, Polygon>
+{
+ static const order_selector value = core_dispatch::point_order
+ <
+ ring_tag,
+ typename ring_type<polygon_tag, Polygon>::type
+ >::value ;
+};
+
+} // namespace core_dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+
+/*!
+ \brief Meta-function which defines point type of any geometry
+ \ingroup core
+*/
+template <typename Geometry>
+struct point_order
+{
+ typedef typename boost::remove_const<Geometry>::type ncg;
+ static const order_selector value = core_dispatch::point_order
+ <
+ typename tag<Geometry>::type,
+ ncg
+ >::value;
+};
+
+} // namespace ggl
+
+#endif // GGL_CORE_POINT_ORDER_HPP
Modified: sandbox/ggl/formal_review_request/boost/ggl/core/point_type.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/core/point_type.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/core/point_type.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -73,7 +73,7 @@
typedef typename boost::range_value<Ring>::type type;
};
-// Specialization for polygon: the point-type is the point-type of its rinsg
+// Specialization for polygon: the point-type is the point-type of its rings
template <typename Polygon>
struct point_type<polygon_tag, Polygon>
{
Modified: sandbox/ggl/formal_review_request/boost/ggl/core/radian_access.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/core/radian_access.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/core/radian_access.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -59,7 +59,7 @@
return boost::numeric_cast
<
coordinate_type
- >(ggl::get<D>(geometry) * math::d2r);
+ >(ggl::get<D>(geometry) * ggl::math::d2r);
}
static inline void set(G& geometry, coordinate_type const& radians)
@@ -67,7 +67,7 @@
ggl::set<D>(geometry, boost::numeric_cast
<
coordinate_type
- >(radians * math::r2d));
+ >(radians * ggl::math::r2d));
}
};
Modified: sandbox/ggl/formal_review_request/boost/ggl/geometries/linear_ring.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/geometries/linear_ring.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/geometries/linear_ring.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -16,6 +16,7 @@
#include <ggl/core/tag.hpp>
#include <ggl/core/tags.hpp>
+#include <ggl/core/point_order.hpp>
#include <ggl/core/concepts/point_concept.hpp>
@@ -34,6 +35,7 @@
<
typename P,
template<typename, typename> class V = std::vector,
+ bool ClockWise = true,
template<typename> class A = std::allocator
>
class linear_ring : public V<P, A<P> >
@@ -49,13 +51,41 @@
<
typename P,
template<typename, typename> class V,
+ bool ClockWise,
template<typename> class A
>
-struct tag< linear_ring<P, V, A> >
+struct tag< linear_ring<P, V, ClockWise, A> >
{
typedef ring_tag type;
};
+
+template
+<
+ typename P,
+ template<typename, typename> class V,
+ template<typename> class A
+>
+struct point_order< linear_ring<P, V, false, A> >
+{
+ static const order_selector value = counterclockwise;
+};
+
+
+template
+<
+ typename P,
+ template<typename, typename> class V,
+ template<typename> class A
+>
+struct point_order< linear_ring<P, V, true, A> >
+{
+ static const order_selector value = clockwise;
+};
+
+
+
+
} // namespace traits
#endif // DOXYGEN_NO_TRAITS_SPECIALIZATIONS
Modified: sandbox/ggl/formal_review_request/boost/ggl/geometries/point_xy.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/geometries/point_xy.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/geometries/point_xy.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -52,10 +52,10 @@
{ this->template set<1>(v); }
/// Compare two points
- inline bool operator<(point_xy const& other) const
- {
- return math::equals(x(), other.x()) ? y() < other.y() : x() < other.x();
- }
+ //inline bool operator<(point_xy const& other) const
+ //{
+ // return math::equals(x(), other.x()) ? y() < other.y() : x() < other.x();
+ //}
};
Modified: sandbox/ggl/formal_review_request/boost/ggl/geometries/polygon.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/geometries/polygon.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/geometries/polygon.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -28,18 +28,23 @@
\brief The \b polygon contains an outer ring and zero or more inner rings.
\ingroup Geometry
\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 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 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.
+ \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,
template<typename, typename> class PointList = std::vector,
template<typename, typename> class RingList = std::vector,
+ bool ClockWise = true,
template<typename> class PointAlloc = std::allocator,
template<typename> class RingAlloc = std::allocator
>
@@ -51,7 +56,7 @@
// Member types
typedef Point point_type;
- typedef linear_ring<Point, PointList, PointAlloc> ring_type;
+ typedef linear_ring<Point, PointList, ClockWise, PointAlloc> ring_type;
typedef RingList<ring_type , RingAlloc<ring_type > > inner_container_type;
inline ring_type const& outer() const { return m_outer; }
@@ -83,10 +88,11 @@
typename Point,
template<typename, typename> class PointList,
template<typename, typename> class RingList,
+ bool ClockWise,
template<typename> class PointAlloc,
template<typename> class RingAlloc
>
-struct tag<polygon<Point, PointList, RingList, PointAlloc, RingAlloc> >
+struct tag<polygon<Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc> >
{
typedef polygon_tag type;
};
@@ -96,14 +102,15 @@
typename Point,
template<typename, typename> class PointList,
template<typename, typename> class RingList,
+ bool ClockWise,
template<typename> class PointAlloc,
template<typename> class RingAlloc
>
-struct ring_type<polygon<Point, PointList, RingList, PointAlloc, RingAlloc> >
+struct ring_type<polygon<Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc> >
{
typedef typename polygon
<
- Point, PointList, RingList, PointAlloc, RingAlloc
+ Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc
>::ring_type type;
};
@@ -112,14 +119,15 @@
typename Point,
template<typename, typename> class PointList,
template<typename, typename> class RingList,
+ bool ClockWise,
template<typename> class PointAlloc,
template<typename> class RingAlloc
>
-struct interior_type< polygon<Point, PointList, RingList, PointAlloc, RingAlloc> >
+struct interior_type< polygon<Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc> >
{
typedef typename polygon
<
- Point, PointList, RingList, PointAlloc, RingAlloc
+ Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc
>::inner_container_type type;
};
@@ -128,12 +136,13 @@
typename Point,
template<typename, typename> class PointList,
template<typename, typename> class RingList,
+ bool ClockWise,
template<typename> class PointAlloc,
template<typename> class RingAlloc
>
-struct exterior_ring< polygon<Point, PointList, RingList, PointAlloc, RingAlloc> >
+struct exterior_ring< polygon<Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc> >
{
- typedef polygon<Point, PointList, RingList, PointAlloc, RingAlloc> polygon_type;
+ typedef polygon<Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc> polygon_type;
static inline typename polygon_type::ring_type& get(polygon_type& p)
{
@@ -151,12 +160,13 @@
typename Point,
template<typename, typename> class PointList,
template<typename, typename> class RingList,
+ bool ClockWise,
template<typename> class PointAlloc,
template<typename> class RingAlloc
>
-struct interior_rings< polygon<Point, PointList, RingList, PointAlloc, RingAlloc> >
+struct interior_rings< polygon<Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc> >
{
- typedef polygon<Point, PointList, RingList, PointAlloc, RingAlloc> polygon_type;
+ typedef polygon<Point, PointList, RingList, ClockWise, PointAlloc, RingAlloc> polygon_type;
static inline typename polygon_type::inner_container_type& get(
polygon_type& p)
Modified: sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/area.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/area.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/area.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -19,11 +19,11 @@
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
- template <typename MultiGeometry, typename Strategy>
- struct area<multi_polygon_tag, MultiGeometry, Strategy>
+ template <typename MultiGeometry, order_selector Order, typename Strategy>
+ struct area<multi_polygon_tag, MultiGeometry, Order, Strategy>
: detail::multi_sum<double, MultiGeometry, Strategy,
detail::area::polygon_area<
- typename boost::range_value<MultiGeometry>::type, Strategy> >
+ typename boost::range_value<MultiGeometry>::type, Order, Strategy> >
{};
Modified: sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/convex_hull.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/convex_hull.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/convex_hull.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -26,9 +26,14 @@
namespace detail { namespace convex_hull {
-template <typename MultiGeometry, typename OutputIterator>
-struct convex_hull_multi
+template
+<
+ typename MultiGeometry,
+ order_selector Order
+>
+struct multi_inserter
{
+ template <typename OutputIterator>
static inline OutputIterator apply(MultiGeometry const& multi,
OutputIterator out)
{
@@ -50,12 +55,36 @@
}
strategy.handle_input();
- strategy.get(out);
+ strategy.get(out, Order == clockwise);
return out;
}
};
+
+template
+<
+ typename Geometry,
+ typename OutputGeometry
+>
+struct multi_hull_to_geometry
+{
+ static inline void apply(Geometry const& geometry, OutputGeometry& out)
+ {
+ multi_inserter
+ <
+ Geometry,
+ ggl::point_order<OutputGeometry>::value
+ >::apply(geometry,
+ std::back_inserter(
+ ggl::as_range
+ <
+ typename ggl::as_range_type<OutputGeometry>::type
+ >(out)));
+ }
+};
+
+
}} // namespace detail::convex_hull
#endif
@@ -66,25 +95,54 @@
namespace dispatch
{
+
// Specialize for multi's
template
<
typename MultiTag,
- typename MultiGeometry,
- typename OutputIterator
+ order_selector Order,
+ typename MultiGeometry
>
-struct convex_hull<MultiTag, true, MultiGeometry, OutputIterator>
- : detail::convex_hull::convex_hull_multi<MultiGeometry, OutputIterator>
+struct convex_hull_inserter<MultiTag, Order, true, MultiGeometry>
+ : detail::convex_hull::multi_inserter<MultiGeometry, Order>
{};
-// Specialize more for point
-template <typename MultiPoint, typename OutputIterator>
-struct convex_hull<multi_point_tag, true, MultiPoint, OutputIterator>
- : detail::convex_hull::hull<MultiPoint, OutputIterator>
+// Specialize for point
+template
+<
+ order_selector Order,
+ typename MultiPoint
+>
+struct convex_hull_inserter<multi_point_tag, Order, true, MultiPoint>
+ : detail::convex_hull::hull_inserter<MultiPoint, Order>
+{};
+
+
+// Versions outputting to a ring or polygon
+template <typename MultiTag, typename MultiGeometry, typename Output>
+struct convex_hull
+<
+ MultiTag, true,
+ MultiGeometry, Output
+>
+ : detail::convex_hull::multi_hull_to_geometry<MultiGeometry, Output>
+{};
+
+
+template <typename MultiGeometry, typename Output>
+struct convex_hull
+<
+ multi_point_tag, true,
+ MultiGeometry, Output
+>
+ : detail::convex_hull::hull_to_geometry<MultiGeometry, Output>
{};
+
+
+
} // namespace dispatch
#endif
Modified: sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/correct.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/correct.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/correct.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -6,48 +6,59 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef GGL_MULTI_CORRECT_HPP
-#define GGL_MULTI_CORRECT_HPP
+#ifndef GGL_MULTI_ALGORITHMS_CORRECT_HPP
+#define GGL_MULTI_ALGORITHMS_CORRECT_HPP
+
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
-#include <vector>
#include <ggl/algorithms/correct.hpp>
+#include <ggl/multi/core/tags.hpp>
-//FIX ME it is not yet adapted to tag-dispatching
namespace ggl
{
#ifndef DOXYGEN_NO_DETAIL
-namespace detail
+namespace detail { namespace correct {
+
+template <typename MultiPolygon>
+struct correct_multi_polygon
{
- namespace correct
+ static inline void apply(MultiPolygon& mp)
{
- // correct a multi-polygon
- template <typename O>
- inline void correct_multi_polygon(O& o)
+ typedef typename boost::range_value<MultiPolygon>::type polygon_type;
+ for (typename boost::range_iterator<MultiPolygon>::type it
+ = boost::begin(mp);
+ it != boost::end(mp);
+ ++it)
{
- for (typename O::iterator it = o.begin(); it != o.end(); it++)
- {
- correct_polygon(*it);
- }
+ correct_polygon<polygon_type>::apply(*it);
}
}
-}
+};
+
+}} // namespace detail::correct
#endif
-template<typename Y,
- template<typename,typename> class V, template<typename> class A>
-void correct(multi_polygon<Y, V, A>& mp)
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
{
- detail::correct::correct_multi_polygon(mp);
-}
+template <typename Geometry>
+struct correct<multi_polygon_tag, Geometry>
+ : detail::correct::correct_multi_polygon<Geometry>
+{};
+
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
} // namespace ggl
-#endif // GGL_MULTI_CORRECT_HPP
+#endif // GGL_MULTI_ALGORITHMS_CORRECT_HPP
Modified: sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/simplify.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/simplify.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/multi/algorithms/simplify.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -6,64 +6,107 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef GGL_MULTI_SIMPLIFY_HPP
-#define GGL_MULTI_SIMPLIFY_HPP
+#ifndef GGL_MULTI_ALGORITHMS_SIMPLIFY_HPP
+#define GGL_MULTI_ALGORITHMS_SIMPLIFY_HPP
-#include <vector>
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
+
+#include <ggl/multi/core/tags.hpp>
+#include <ggl/multi/core/is_multi.hpp>
+
+#include <ggl/multi/util/as_range.hpp>
#include <ggl/algorithms/simplify.hpp>
-FIX ME it is not yet adapted to tag-dispatching
namespace ggl
{
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace simplify {
- template<typename ML>
- inline void simplify_multi_linestring(const ML& ml_in, ML& ml_out, double max_distance)
+template<typename MultiGeometry, typename Strategy, typename Policy>
+struct simplify_multi
+{
+ static inline void apply(MultiGeometry const& multi, MultiGeometry& out,
+ double max_distance, Strategy const& strategy)
+ {
+ out.resize(boost::size(multi));
+
+ typename boost::range_iterator<MultiGeometry>::type it_out
+ = boost::begin(out);
+ for (typename boost::range_const_iterator<MultiGeometry>::type it_in
+ = boost::begin(multi);
+ it_in != boost::end(multi);
+ ++it_in, ++it_out)
{
- ml_out.resize(ml_in.size());
- typename ML::const_iterator it_in = ml_in.begin();
- typename ML::iterator it_out = ml_out.begin();
- for (; it_in != ml_in.end(); it_in++, it_out++)
- {
- simplify_linestring(*it_in, *it_out, max_distance);
- }
+ Policy::apply(*it_in, *it_out, max_distance, strategy);
}
+ }
+};
- template<typename MY>
- inline void simplify_multi_polygon(const MY& mp_in, MY& mp_out, double max_distance)
- {
- mp_out.resize(mp_in.size());
- typename MY::const_iterator it_in = mp_in.begin();
- typename MY::iterator it_out = mp_out.begin();
- for (; it_in != mp_in.end(); it_in++, it_out++)
- {
- simplify(*it_in, *it_out, max_distance);
- }
- }
+}} // namespace detail::simplify
+#endif // DOXYGEN_NO_DETAIL
-template<typename L,
- template<typename,typename> class V, template<typename> class A>
-inline void simplify(const multi_linestring<L, V, A>& ml_in,
- multi_linestring<L, V, A>& ml_out, double max_distance)
-{
- simplify_multi_linestring(ml_in, ml_out, max_distance);
-}
-template<typename Y,
- template<typename,typename> class V, template<typename> class A>
-inline void simplify(const multi_polygon<Y, V, A>& mp_in,
- multi_polygon<Y, V, A>& mp_out, double max_distance)
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
{
- simplify_multi_polygon(mp_in, mp_out, max_distance);
-}
+
+template <typename MultiPoint, typename Strategy>
+struct simplify<multi_point_tag, MultiPoint, Strategy>
+ : detail::simplify::simplify_copy
+ <
+ MultiPoint,
+ Strategy
+ >
+
+{};
+
+
+template <typename MultiLinestring, typename Strategy>
+struct simplify<multi_linestring_tag, MultiLinestring, Strategy>
+ : detail::simplify::simplify_multi
+ <
+ MultiLinestring,
+ Strategy,
+ detail::simplify::simplify_range
+ <
+ typename boost::range_value<MultiLinestring>::type,
+ Strategy,
+ 2
+ >
+ >
+
+{};
+
+
+template <typename MultiPolygon, typename Strategy>
+struct simplify<multi_polygon_tag, MultiPolygon, Strategy>
+ : detail::simplify::simplify_multi
+ <
+ MultiPolygon,
+ Strategy,
+ detail::simplify::simplify_polygon
+ <
+ typename boost::range_value<MultiPolygon>::type,
+ Strategy
+ >
+ >
+
+{};
+
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
} // namespace ggl
-#endif // GGL_MULTI_SIMPLIFY_HPP
+#endif // GGL_MULTI_ALGORITHMS_SIMPLIFY_HPP
Modified: sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_convex_hull.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_convex_hull.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_convex_hull.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -9,19 +9,21 @@
#ifndef GGL_STRATEGIES_AGNOSTIC_CONVEX_HULL_HPP
#define GGL_STRATEGIES_AGNOSTIC_CONVEX_HULL_HPP
-#ifdef _MSC_VER
-#pragma warning( disable : 4101 )
-#endif
#include <cstddef>
#include <algorithm>
#include <vector>
#include <boost/range/functions.hpp>
+#include <boost/concept_check.hpp> // for ignore-variable
#include <ggl/core/cs.hpp>
#include <ggl/strategies/strategy_traits.hpp>
+#include <ggl/util/less.hpp>
+
+
+
// TODO: Temporary, comparing tests, this can be removed in the end
#if defined(GGL_USE_SMOOTH_SORT)
# include "SmoothSort.hpp"
@@ -64,13 +66,17 @@
template <typename R>
static inline void sort(R& range)
{
- #if defined(USE_SMOOTH_SORT)
- smoothsort::sort(boost::begin(range), boost::end(range));
- #elif defined(USE_MERGE_SORT)
- comparing::merge_sort<thread_count>(boost::begin(range), boost::end(range), std::less<P>());
- #else
- std::sort(boost::begin(range), boost::end(range));
- #endif
+ typedef typename boost::range_value<R>::type point_type;
+
+#if defined(USE_SMOOTH_SORT)
+ smoothsort::sort
+#elif defined(USE_MERGE_SORT)
+ comparing::merge_sort<thread_count>
+#else
+ std::sort
+#endif
+
+ (boost::begin(range), boost::end(range), ggl::less<point_type>());
}
} // namespace detail
@@ -111,27 +117,21 @@
template <typename OutputIterator>
- inline void get(OutputIterator out)
+ inline void get(OutputIterator out, bool clockwise)
{
- for (iterator it = m_upper_hull.begin(); it != m_upper_hull.end(); ++it, ++out)
+ if (clockwise)
{
- *out = *it;
+ get_range_forward(m_upper_hull, out);
+ get_range_reverse(m_lower_hull, out);
}
-
- // STL Port does not accept iterating from rbegin+1 to rend
- std::size_t size = m_lower_hull.size();
- if (size > 0)
+ else
{
- rev_iterator it = m_lower_hull.rbegin() + 1;
- for (std::size_t i = 1; i < size; ++i, ++it, ++out)
- {
- *out = *it;
- }
+ get_range_forward(m_lower_hull, out);
+ get_range_reverse(m_upper_hull, out);
}
}
- // Note /
// TODO:
// Consider if it is better to create an iterator over a multi, which is then used here,
// instead of copying the range
@@ -181,8 +181,8 @@
detail::sort(lower_points);
detail::sort(upper_points);
- build_half_hull<1>(lower_points, m_lower_hull, *left_it, *right_it);
- build_half_hull<-1>(upper_points, m_upper_hull, *left_it, *right_it);
+ build_half_hull<-1>(lower_points, m_lower_hull, *left_it, *right_it);
+ build_half_hull<1>(upper_points, m_upper_hull, *left_it, *right_it);
}
@@ -195,6 +195,7 @@
container& upper_points)
{
typename strategy_side<cs_tag, P>::type side;
+ boost::ignore_unused_variable_warning(side);
// Put points in one of the two output sequences
for (RangeIterator it = boost::begin(range);
@@ -204,13 +205,15 @@
if (it != left_it && it != right_it)
{
int dir = side.side(*left_it, *right_it, *it);
- if ( dir < 0 )
- {
- upper_points.push_back(*it);
- }
- else
+ switch(dir)
{
- lower_points.push_back(*it);
+ case 1 : // left
+ upper_points.push_back(*it);
+ break;
+ case -1 : // right
+ lower_points.push_back(*it);
+ break;
+ // zero: on line left-right, never part of hull
}
}
}
@@ -233,6 +236,7 @@
inline void add_to_hull(const P& p, container& output)
{
typename strategy_side<cs_tag, P>::type side;
+ boost::ignore_unused_variable_warning(side);
output.push_back(p);
register std::size_t output_size = output.size();
@@ -258,6 +262,29 @@
}
}
+ template <typename Range, typename OutputIterator>
+ inline void get_range_forward(Range const& range, OutputIterator out)
+ {
+ for (iterator it = range.begin(); it != range.end(); ++it, ++out)
+ {
+ *out = *it;
+ }
+ }
+
+ template <typename Range, typename OutputIterator>
+ inline void get_range_reverse(Range const& range, OutputIterator out)
+ {
+ // STL Port does not accept iterating from rbegin+1 to rend
+ std::size_t size = range.size();
+ if (size > 0)
+ {
+ rev_iterator it = range.rbegin() + 1;
+ for (std::size_t i = 1; i < size; ++i, ++it, ++out)
+ {
+ *out = *it;
+ }
+ }
+ }
};
Deleted: sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_simplify.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_simplify.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
+++ (empty file)
@@ -1,196 +0,0 @@
-// Generic Geometry Library
-//
-// Copyright Barend Gehrels 1995-2009, Geodan Holding B.V. 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 GGL_STRATEGY_AGNOSTIC_SIMPLIFY_HPP
-#define GGL_STRATEGY_AGNOSTIC_SIMPLIFY_HPP
-
-#include <boost/range/functions.hpp>
-
-#include <ggl/core/cs.hpp>
-
-
-//#define GL_DEBUG_SIMPLIFY
-
-#ifdef GL_DEBUG_SIMPLIFY
-#include <ggl/extensions/gis/io/wkt/write_wkt.hpp>
-#include <ggl/extensions/gis/io/wkt/stream_wkt.hpp>
-#include <iostream>
-#endif
-
-
-namespace ggl
-{
-namespace strategy
-{
- namespace simplify
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail
- {
-
- /*!
- \brief Small wrapper around a point, with an extra member "included"
- \details
- - We could implement a complete point as well but that is not necessary
- - We could derive from ggl::point but we need the original later on, including extra members;
- besides that it is not necessary to copy points during the algorithm
- \tparam the enclosed point type
- */
- template<typename P>
- struct douglas_peucker_point
- {
- const P& p;
- bool included;
-
- inline douglas_peucker_point(const P& ap)
- : p(ap)
- , included(false)
- {}
-
- inline douglas_peucker_point<P> operator=(const douglas_peucker_point<P>& other)
- {
- return douglas_peucker_point<P>(*this);
- }
- };
- }
- #endif // DOXYGEN_NO_DETAIL
-
-
- /*!
- \brief Implements the simplify algorithm.
- \ingroup simplify
- \details The douglas_peucker strategy simplifies a linestring, ring or vector of points
- using the well-known Douglas-Peucker algorithm. For the algorithm, see for example:
- \see http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
- \see http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html
- \tparam R boost range
- \tparam O_IT output iterator
- \tparam PSDS point-segment distance strategy to be used
- \note This strategy uses itself a point-segment-distance strategy which can be specified
- \author Barend and Maarten, 1995/1996
- \author Barend, revised for Generic Geometry Library, 2008
- */
- template<typename R, typename O_IT, typename PSDS>
- class douglas_peucker
- {
- typedef typename point_type<R>::type P;
- typedef detail::douglas_peucker_point<P> DP;
- typedef typename std::vector<DP>::iterator DIT;
-
- typedef typename PSDS::return_type RET;
-
- inline void consider(DIT begin, DIT end, const RET& max_dist, int& n,
- const PSDS& ps_distance_strategy) const
- {
- size_t size = end - begin;
- // size must be at least 3 here: we want to consider a candidate point between begin and end
- if (size <= 2)
- {
-#ifdef GL_DEBUG_SIMPLIFY
- if (begin != end)
- {
- std::cout << "ignore between " << begin->p << " and " << (end - 1)->p << " size=" << size << std::endl;
- }
- std::cout << "return because size=" << size << std::endl;
-#endif
- return;
- }
-
- DIT last = end - 1;
-
-#ifdef GL_DEBUG_SIMPLIFY
- std::cout << "find between " << begin->p << " and " << last->p << " size=" << size << std::endl;
-#endif
-
-
- // Find most distance point, compare to the current segment
- ggl::segment<const P> s(begin->p, last->p);
- RET md(-1.0); // any value < 0
- DIT candidate;
- for(DIT it = begin + 1; it != last; it++)
- {
- RET dist = ps_distance_strategy(it->p, s);
-
-#ifdef GL_DEBUG_SIMPLIFY
- std::cout << "consider " << it->p << " at " << dist.value() << (dist.value() > max_dist.value() ? " maybe" : " no") << std::endl;
-#endif
- if (dist > md)
- {
- md = dist;
- candidate = it;
- }
- }
-
- // If a point is found, set the include flag and handle segments in between recursively
- if (md > max_dist)
- {
-#ifdef GL_DEBUG_SIMPLIFY
- std::cout << "use " << candidate->p << std::endl;
-#endif
-
- candidate->included = true;
- n++;
-
- consider(begin, candidate + 1, max_dist, n, ps_distance_strategy);
- consider(candidate, end, max_dist, n, ps_distance_strategy);
- }
- }
-
-
- public :
-
- typedef PSDS distance_strategy_type;
-
- /*!
- \brief Call simplification on an iterator pair
- */
- inline void simplify(const R& range, O_IT out, double max_distance) const
- {
- PSDS strategy;
- // Init the output, a vector of references to all points
-
- // Note Geometry Algorithms suggest here
- // http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm
- // to "STAGE 1: Vertex Reduction within max_distance of prior vertex cluster"
- // However, that is not correct: a vertex within the specified distance might be
- // excluded here, but might be a better candidate for final inclusion than the point before.
-
- std::vector<DP> ref_candidates(boost::begin(range), boost::end(range));
-
- // Include first and last point of line, they are always part of the line
- int n = 2;
- ref_candidates.front().included = true;
- ref_candidates.back().included = true;
-
- // Get points, recursively, including them if they are further away than the specified distance
- typedef typename PSDS::return_type RET;
-
- consider(boost::begin(ref_candidates), boost::end(ref_candidates),
- make_distance_result<RET>(max_distance), n, strategy);
-
- // Copy included elements to the output (might be changed using copy_if)
- for(typename std::vector<DP>::const_iterator it = boost::begin(ref_candidates);
- it != boost::end(ref_candidates); it++)
- {
- if (it->included)
- {
- *out = it->p;
- out++;
- }
- }
- }
-
- };
-
- }
-}
-
-
-} // namespace ggl
-
-#endif // GGL_STRATEGY_AGNOSTIC_SIMPLIFY_HPP
Copied: sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/simplify_douglas_peucker.hpp (from r56825, /sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_simplify.hpp)
==============================================================================
--- /sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/agn_simplify.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/agnostic/simplify_douglas_peucker.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -6,191 +6,212 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef GGL_STRATEGY_AGNOSTIC_SIMPLIFY_HPP
-#define GGL_STRATEGY_AGNOSTIC_SIMPLIFY_HPP
+#ifndef GGL_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
+#define GGL_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
+#include <vector>
#include <boost/range/functions.hpp>
#include <ggl/core/cs.hpp>
+#include <ggl/geometries/segment.hpp>
+#include <ggl/strategies/distance_result.hpp>
+#include <ggl/util/copy.hpp>
-//#define GL_DEBUG_SIMPLIFY
+//#define GL_DEBUG_DOUGLAS_PEUCKER
-#ifdef GL_DEBUG_SIMPLIFY
-#include <ggl/extensions/gis/io/wkt/write_wkt.hpp>
-#include <ggl/extensions/gis/io/wkt/stream_wkt.hpp>
-#include <iostream>
+#ifdef GL_DEBUG_DOUGLAS_PEUCKER
+#include <ggl/util/write_dsv.hpp>
#endif
namespace ggl
{
-namespace strategy
+
+namespace strategy { namespace simplify {
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail
{
- namespace simplify
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail
- {
- /*!
- \brief Small wrapper around a point, with an extra member "included"
- \details
- - We could implement a complete point as well but that is not necessary
- - We could derive from ggl::point but we need the original later on, including extra members;
- besides that it is not necessary to copy points during the algorithm
- \tparam the enclosed point type
- */
- template<typename P>
- struct douglas_peucker_point
- {
- const P& p;
- bool included;
+ /*!
+ \brief Small wrapper around a point, with an extra member "included"
+ \details
+ It has a const-reference to the original point (so no copy here)
+ \tparam the enclosed point type
+ */
+ template<typename Point>
+ struct douglas_peucker_point
+ {
+ Point const& p;
+ bool included;
- inline douglas_peucker_point(const P& ap)
- : p(ap)
- , included(false)
- {}
-
- inline douglas_peucker_point<P> operator=(const douglas_peucker_point<P>& other)
- {
- return douglas_peucker_point<P>(*this);
- }
- };
+ inline douglas_peucker_point(Point const& ap)
+ : p(ap)
+ , included(false)
+ {}
+
+ // Necessary for proper compilation
+ inline douglas_peucker_point<Point> operator=(
+ douglas_peucker_point<Point> const& other)
+ {
+ return douglas_peucker_point<Point>(*this);
}
- #endif // DOXYGEN_NO_DETAIL
+ };
+}
+#endif // DOXYGEN_NO_DETAIL
- /*!
- \brief Implements the simplify algorithm.
- \ingroup simplify
- \details The douglas_peucker strategy simplifies a linestring, ring or vector of points
- using the well-known Douglas-Peucker algorithm. For the algorithm, see for example:
- \see http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
- \see http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html
- \tparam R boost range
- \tparam O_IT output iterator
- \tparam PSDS point-segment distance strategy to be used
- \note This strategy uses itself a point-segment-distance strategy which can be specified
- \author Barend and Maarten, 1995/1996
- \author Barend, revised for Generic Geometry Library, 2008
- */
- template<typename R, typename O_IT, typename PSDS>
- class douglas_peucker
- {
- typedef typename point_type<R>::type P;
- typedef detail::douglas_peucker_point<P> DP;
- typedef typename std::vector<DP>::iterator DIT;
+/*!
+ \brief Implements the simplify algorithm.
+ \ingroup simplify
+ \details The douglas_peucker strategy simplifies a linestring, ring or
+ vector of points using the well-known Douglas-Peucker algorithm.
+ For the algorithm, see for example:
+ \see http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
+ \see http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html
+ \tparam Point the point type
+ \tparam PointDistanceStrategy point-segment distance strategy to be used
+ \note This strategy uses itself a point-segment-distance strategy which
+ can be specified
+ \author Barend and Maarten, 1995/1996
+ \author Barend, revised for Generic Geometry Library, 2008
+*/
+template
+<
+ typename Point,
+ typename PointDistanceStrategy
+>
+class douglas_peucker
+{
+ typedef detail::douglas_peucker_point<Point> dp_point_type;
+ typedef typename std::vector<dp_point_type>::iterator iterator_type;
- typedef typename PSDS::return_type RET;
+ typedef typename PointDistanceStrategy::return_type return_type;
- inline void consider(DIT begin, DIT end, const RET& max_dist, int& n,
- const PSDS& ps_distance_strategy) const
+ static inline void consider(iterator_type begin,
+ iterator_type end,
+ return_type const& max_dist, int& n,
+ PointDistanceStrategy const& ps_distance_strategy)
+ {
+ std::size_t size = end - begin;
+
+ // size must be at least 3
+ // because we want to consider a candidate point in between
+ if (size <= 2)
+ {
+#ifdef GL_DEBUG_DOUGLAS_PEUCKER
+ if (begin != end)
{
- size_t size = end - begin;
- // size must be at least 3 here: we want to consider a candidate point between begin and end
- if (size <= 2)
- {
-#ifdef GL_DEBUG_SIMPLIFY
- if (begin != end)
- {
- std::cout << "ignore between " << begin->p << " and " << (end - 1)->p << " size=" << size << std::endl;
- }
- std::cout << "return because size=" << size << std::endl;
+ std::cout << "ignore between " << dsv(begin->p)
+ << " and " << dsv((end - 1)->p)
+ << " size=" << size << std::endl;
+ }
+ std::cout << "return because size=" << size << std::endl;
#endif
- return;
- }
+ return;
+ }
- DIT last = end - 1;
+ iterator_type last = end - 1;
-#ifdef GL_DEBUG_SIMPLIFY
- std::cout << "find between " << begin->p << " and " << last->p << " size=" << size << std::endl;
+#ifdef GL_DEBUG_DOUGLAS_PEUCKER
+ std::cout << "find between " << dsv(begin->p)
+ << " and " << dsv(last->p)
+ << " size=" << size << std::endl;
#endif
- // Find most distance point, compare to the current segment
- ggl::segment<const P> s(begin->p, last->p);
- RET md(-1.0); // any value < 0
- DIT candidate;
- for(DIT it = begin + 1; it != last; it++)
- {
- RET dist = ps_distance_strategy(it->p, s);
+ // Find most distance point, compare to the current segment
+ ggl::segment<const Point> s(begin->p, last->p);
+ return_type md(-1.0); // any value < 0
+ iterator_type candidate;
+ for(iterator_type it = begin + 1; it != last; ++it)
+ {
+ return_type dist = ps_distance_strategy(it->p, s);
+
+#ifdef GL_DEBUG_DOUGLAS_PEUCKER
+ std::cout << "consider " << dsv(it->p)
+ << " at " << double(dist)
+ << ((dist > max_dist) ? " maybe" : " no")
+ << std::endl;
-#ifdef GL_DEBUG_SIMPLIFY
- std::cout << "consider " << it->p << " at " << dist.value() << (dist.value() > max_dist.value() ? " maybe" : " no") << std::endl;
#endif
- if (dist > md)
- {
- md = dist;
- candidate = it;
- }
- }
-
- // If a point is found, set the include flag and handle segments in between recursively
- if (md > max_dist)
- {
-#ifdef GL_DEBUG_SIMPLIFY
- std::cout << "use " << candidate->p << std::endl;
+ if (dist > md)
+ {
+ md = dist;
+ candidate = it;
+ }
+ }
+
+ // If a point is found, set the include flag
+ // and handle segments in between recursively
+ if (md > max_dist)
+ {
+#ifdef GL_DEBUG_DOUGLAS_PEUCKER
+ std::cout << "use " << dsv(candidate->p) << std::endl;
#endif
- candidate->included = true;
- n++;
+ candidate->included = true;
+ n++;
- consider(begin, candidate + 1, max_dist, n, ps_distance_strategy);
- consider(candidate, end, max_dist, n, ps_distance_strategy);
- }
- }
+ consider(begin, candidate + 1, max_dist, n, ps_distance_strategy);
+ consider(candidate, end, max_dist, n, ps_distance_strategy);
+ }
+ }
- public :
+public :
- typedef PSDS distance_strategy_type;
+ typedef PointDistanceStrategy distance_strategy_type;
- /*!
- \brief Call simplification on an iterator pair
- */
- inline void simplify(const R& range, O_IT out, double max_distance) const
- {
- PSDS strategy;
- // Init the output, a vector of references to all points
- // Note Geometry Algorithms suggest here
- // http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm
- // to "STAGE 1: Vertex Reduction within max_distance of prior vertex cluster"
- // However, that is not correct: a vertex within the specified distance might be
- // excluded here, but might be a better candidate for final inclusion than the point before.
-
- std::vector<DP> ref_candidates(boost::begin(range), boost::end(range));
-
- // Include first and last point of line, they are always part of the line
- int n = 2;
- ref_candidates.front().included = true;
- ref_candidates.back().included = true;
-
- // Get points, recursively, including them if they are further away than the specified distance
- typedef typename PSDS::return_type RET;
-
- consider(boost::begin(ref_candidates), boost::end(ref_candidates),
- make_distance_result<RET>(max_distance), n, strategy);
-
- // Copy included elements to the output (might be changed using copy_if)
- for(typename std::vector<DP>::const_iterator it = boost::begin(ref_candidates);
- it != boost::end(ref_candidates); it++)
- {
- if (it->included)
- {
- *out = it->p;
- out++;
- }
- }
+ template <typename Range, typename OutputIterator>
+ static inline OutputIterator apply(Range const& range,
+ OutputIterator out, double max_distance)
+ {
+ PointDistanceStrategy strategy;
+
+ // Copy coordinates, a vector of references to all points
+ std::vector<dp_point_type> ref_candidates(boost::begin(range),
+ boost::end(range));
+
+ // Include first and last point of line,
+ // they are always part of the line
+ int n = 2;
+ ref_candidates.front().included = true;
+ ref_candidates.back().included = true;
+
+ // Get points, recursively, including them if they are further away
+ // than the specified distance
+ typedef typename PointDistanceStrategy::return_type return_type;
+
+ consider(boost::begin(ref_candidates), boost::end(ref_candidates),
+ make_distance_result<return_type>(max_distance), n, strategy);
+
+ // Copy included elements to the output
+ for(typename std::vector<dp_point_type>::const_iterator it
+ = boost::begin(ref_candidates);
+ it != boost::end(ref_candidates);
+ ++it)
+ {
+ if (it->included)
+ {
+ // copy-coordinates does not work because OutputIterator
+ // does not model Point (??)
+ //ggl::copy_coordinates(it->p, *out);
+ *out = it->p;
+ out++;
}
+ }
+ return out;
+ }
- };
+};
- }
-}
+}} // namespace strategy::simplify
} // namespace ggl
-#endif // GGL_STRATEGY_AGNOSTIC_SIMPLIFY_HPP
+#endif // GGL_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
Modified: sandbox/ggl/formal_review_request/boost/ggl/strategies/cartesian/cart_distance.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/cartesian/cart_distance.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/cartesian/cart_distance.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -90,6 +90,7 @@
CalculationType
>::type calculation_type;
+ typedef P1 point_type;
typedef cartesian_distance<calculation_type> return_type;
@@ -133,9 +134,10 @@
>
struct xy_point_segment
{
+ typedef P point_type;
typedef typename select_coordinate_type<P, Segment>::type coordinate_type;
typedef cartesian_distance<coordinate_type> return_type;
- typedef Strategy distance_strategy_type; // OBSOLETE!
+
typedef Strategy point_strategy_type;
@@ -154,7 +156,7 @@
typedef typename boost::remove_const
<
- typename point_type<Segment>::type
+ typename ggl::point_type<Segment>::type
>::type segment_point_type;
segment_point_type v, w;
Added: sandbox/ggl/formal_review_request/boost/ggl/strategies/concepts/distance_concept.hpp
==============================================================================
--- (empty file)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/concepts/distance_concept.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -0,0 +1,115 @@
+// Generic Geometry Library
+//
+// Copyright Barend Gehrels 1995-2009, Geodan Holding B.V. 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 GGL_STRATEGIES_CONCEPTS_DISTANCE_CONCEPT_HPP
+#define GGL_STRATEGIES_CONCEPTS_DISTANCE_CONCEPT_HPP
+
+#include <vector>
+#include <iterator>
+
+#include <boost/concept_check.hpp>
+
+#include <ggl/core/concepts/point_concept.hpp>
+#include <ggl/geometries/segment.hpp>
+
+
+namespace ggl { namespace concept {
+
+
+/*!
+ \brief Checks strategy for point-segment-distance
+ \ingroup concepts
+*/
+template <typename Strategy>
+struct PointDistanceStrategy
+{
+ private :
+
+ // 1) must define point_type
+ typedef typename Strategy::point_type ptype;
+ BOOST_CONCEPT_ASSERT
+ (
+ (concept::ConstPoint<ptype>)
+ );
+
+ // 2) must define return_type
+ typedef typename Strategy::return_type rtype;
+
+ // 3) must implement static method () with arguments
+ struct apply_checker
+ {
+ static void check()
+ {
+ Strategy s;
+ ptype *p1;
+ ptype *p2;
+ rtype r = s(*p1, *p2);
+
+ boost::ignore_unused_variable_warning(r);
+ }
+ };
+
+ public :
+ BOOST_CONCEPT_USAGE(PointDistanceStrategy)
+ {
+ apply_checker::check();
+ }
+};
+
+
+/*!
+ \brief Checks strategy for point-segment-distance
+ \ingroup concepts
+*/
+template <typename Strategy>
+struct PointSegmentDistanceStrategy
+{
+ private :
+
+ // 1) must define point_type
+ typedef typename Strategy::point_type ptype;
+ BOOST_CONCEPT_ASSERT
+ (
+ (concept::ConstPoint<ptype>)
+ );
+
+ // 2) must define return_type
+ typedef typename Strategy::return_type rtype;
+
+ // 3) must define underlying point-distance-strategy
+ typedef typename Strategy::point_strategy_type stype;
+ BOOST_CONCEPT_ASSERT
+ (
+ (concept::PointDistanceStrategy<stype>)
+ );
+
+
+ // 4) must implement static method () with arguments
+ struct apply_checker
+ {
+ static void check()
+ {
+ Strategy s;
+ ptype *p1;
+ ptype *p2;
+ rtype r = s(*p1, ggl::segment<const ptype>(*p1, *p2));
+ boost::ignore_unused_variable_warning(r);
+ }
+ };
+
+ public :
+ BOOST_CONCEPT_USAGE(PointSegmentDistanceStrategy)
+ {
+ apply_checker::check();
+ }
+};
+
+
+
+}} // namespace ggl::concept
+
+#endif // GGL_STRATEGIES_CONCEPTS_DISTANCE_CONCEPT_HPP
Added: sandbox/ggl/formal_review_request/boost/ggl/strategies/concepts/simplify_concept.hpp
==============================================================================
--- (empty file)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/concepts/simplify_concept.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -0,0 +1,65 @@
+// Generic Geometry Library
+//
+// Copyright Barend Gehrels 1995-2009, Geodan Holding B.V. 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 GGL_STRATEGIES_CONCEPTS_SIMPLIFY_CONCEPT_HPP
+#define GGL_STRATEGIES_CONCEPTS_SIMPLIFY_CONCEPT_HPP
+
+#include <vector>
+#include <iterator>
+
+#include <boost/concept_check.hpp>
+
+#include <ggl/strategies/concepts/distance_concept.hpp>
+
+
+namespace ggl { namespace concept {
+
+
+/*!
+ \brief Checks strategy for simplify
+ \ingroup concepts
+*/
+template <typename Strategy>
+struct SimplifyStrategy
+{
+ private :
+
+ // 1) must define distance_strategy_type,
+ // defining point-segment distance strategy (to be checked)
+ typedef typename Strategy::distance_strategy_type ds_type;
+
+ BOOST_CONCEPT_ASSERT
+ (
+ (concept::PointSegmentDistanceStrategy<ds_type>)
+ );
+
+ // 2) must implement static method apply with arguments
+ // - Range
+ // - OutputIterator
+ // - floating point value
+ struct apply_checker
+ {
+ static void check()
+ {
+ std::vector<typename ds_type::point_type> *v;
+ Strategy::apply(*v, std::back_inserter(*v), 1.0);
+ }
+ };
+
+ public :
+ BOOST_CONCEPT_USAGE(SimplifyStrategy)
+ {
+ apply_checker::check();
+
+ }
+};
+
+
+
+}} // namespace ggl::concept
+
+#endif // GGL_STRATEGIES_CONCEPTS_SIMPLIFY_CONCEPT_HPP
Added: sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/distance_cross_track.hpp
==============================================================================
--- (empty file)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/distance_cross_track.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -0,0 +1,159 @@
+// Generic Geometry Library
+//
+// Copyright Barend Gehrels 1995-2009, Geodan Holding B.V. 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 GGL_STRATEGY_SPHERICAL_DISTANCE_CROSS_TRACK_HPP
+#define GGL_STRATEGY_SPHERICAL_DISTANCE_CROSS_TRACK_HPP
+
+
+#include <ggl/core/cs.hpp>
+#include <ggl/core/concepts/point_concept.hpp>
+#include <ggl/core/access.hpp>
+#include <ggl/core/radian_access.hpp>
+
+
+#include <ggl/strategies/strategy_traits.hpp>
+
+#include <ggl/strategies/distance_result.hpp>
+
+#include <ggl/util/math.hpp>
+//#include <ggl/util/write_dsv.hpp>
+
+
+
+namespace ggl
+{
+namespace strategy
+{
+
+ namespace distance
+ {
+
+ /*!
+ \brief Strategy functor for distance point to segment calculation
+ \ingroup distance
+ \details Class which calculates the distance of a point to a segment, using latlong points
+ \see http://williams.best.vwh.net/avform.htm
+ \tparam P point type
+ \tparam S segment type
+ */
+ template <typename P, typename S>
+ class cross_track
+ {
+ public :
+ typedef double return_type;
+ typedef P point_type;
+ typedef typename strategy_distance
+ <
+ typename ggl::cs_tag<P>::type,
+ typename ggl::cs_tag<P>::type,
+ P, P
+ >::type point_strategy_type;
+
+
+ inline cross_track(double r = 1.0)
+ : m_radius(r)
+ , m_strategy(1.0) // Keep this 1.0 and not r
+ {}
+
+
+ // It might be useful in the future
+ // to overload constructor with strategy info.
+
+
+ inline return_type operator()(P const& p, S const& s) const
+ {
+ // ASSUMPTION: segment
+ // However, this is normally called from internal functions
+ // Future: solve this using other functions using get<,>
+ return calc(p, s.first, s.second);
+ }
+
+ private :
+ double m_radius;
+
+ // Point-point distances are calculated in radians, on the unit sphere
+ point_strategy_type m_strategy;
+
+ /// Calculate course (bearing) between two points. Might be moved to a "course formula" ...
+ inline double course(P const& p1, P const& p2) const
+ {
+ // http://williams.best.vwh.net/avform.htm#Crs
+ double dlon = get_as_radian<0>(p2) - get_as_radian<0>(p1);
+ double cos_p2lat = cos(get_as_radian<1>(p2));
+
+ // "An alternative formula, not requiring the pre-computation of d"
+ return atan2(sin(dlon) * cos_p2lat,
+ cos(get_as_radian<1>(p1)) * sin(get_as_radian<1>(p2))
+ - sin(get_as_radian<1>(p1)) * cos_p2lat * cos(dlon));
+ }
+
+ inline return_type calc(P const& p, P const& sp1, P const& sp2) const
+ {
+ // http://williams.best.vwh.net/avform.htm#XTE
+
+ double d1 = m_strategy(sp1, p);
+
+ // Actually, calculation of d2 not necessary if we know that the projected point is on the great circle...
+ double d2 = m_strategy(sp2, p);
+
+ double crs_AD = course(sp1, p);
+ double crs_AB = course(sp1, sp2);
+ double XTD = std::abs(asin(sin(d1) * sin(crs_AD - crs_AB)));
+
+//std::cout << "Course " << dsv(sp1) << " to " << dsv(p) << " " << crs_AD * ggl::math::r2d << std::endl;
+//std::cout << "Course " << dsv(sp1) << " to " << dsv(sp2) << " " << crs_AB * ggl::math::r2d << std::endl;
+//std::cout << "XTD: " << (XTD * 6373.0) << " d1: " << (d1 * 6373.0) << " d2: " << (d2 * 6373.0) << std::endl;
+
+
+ // Return shortest distance, either to projected point on segment sp1-sp2, or to sp1, or to sp2
+ return return_type(m_radius * (std::min)((std::min)(d1, d2), XTD));
+ }
+ };
+
+ } // namespace distance
+
+} // namespace strategy
+
+
+#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
+
+
+template <typename Point, typename Segment>
+struct strategy_distance_segment<spherical_tag, spherical_tag, Point, Segment>
+{
+ typedef strategy::distance::cross_track<Point, Segment> type;
+};
+
+
+// Use this point-segment for geographic as well. TODO: change this, extension!
+template <typename Point, typename Segment>
+struct strategy_distance_segment<geographic_tag, geographic_tag, Point, Segment>
+{
+ typedef strategy::distance::cross_track<Point, Segment> type;
+};
+
+
+template <typename Point, typename Segment>
+struct strategy_tag<strategy::distance::cross_track<Point, Segment> >
+{
+ typedef strategy_tag_distance_point_segment type;
+};
+
+
+
+#endif
+
+
+
+
+
+
+} // namespace ggl
+
+
+#endif // GGL_STRATEGY_SPHERICAL_DISTANCE_CROSS_TRACK_HPP
Copied: sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/distance_haversine.hpp (from r56825, /sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/haversine.hpp)
==============================================================================
--- /sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/haversine.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/distance_haversine.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -48,14 +48,14 @@
class haversine
{
public :
- //typedef spherical_distance return_type;
typedef double return_type;
+ typedef P1 point_type;
inline haversine(double r = 1.0)
: m_radius(r)
{}
- inline return_type operator()(const P1& p1, const P2& p2) const
+ inline return_type operator()(P1 const& p1, P2 const& p2) const
{
return calc(get_as_radian<0>(p1), get_as_radian<1>(p1),
get_as_radian<0>(p2), get_as_radian<1>(p2));
@@ -66,7 +66,7 @@
typedef typename coordinate_type<P1>::type T1;
typedef typename coordinate_type<P2>::type T2;
- inline return_type calc(const T1& lon1, const T1& lat1, const T2& lon2, const T2& lat2) const
+ inline return_type calc(T1 const& lon1, T1 const& lat1, T2 const& lon2, T2 const& lat2) const
{
double a = math::hav(lat2 - lat1) + cos(lat1) * cos(lat2) * math::hav(lon2 - lon1);
double c = 2.0 * asin(sqrt(a));
@@ -76,127 +76,6 @@
- /*!
- \brief Strategy functor for distance point to segment calculation
- \ingroup distance
- \details Class which calculates the distance of a point to a segment, using latlong points
- \tparam P point type
- \tparam S segment type
- */
- template <typename P, typename S>
- class ll_point_segment
- {
- public :
- typedef double return_type;
-
- inline ll_point_segment(double r = 1.0) : m_radius(r)
- {}
-
- inline return_type operator()(P const& p, S const& s) const
- {
- PR pr, ps1, ps2;
-
- // Select transformation strategy and transform to radians (if necessary)
- typename strategy_transform<
- typename cs_tag<P>::type,
- typename cs_tag<PR>::type,
- typename coordinate_system<P>::type,
- typename coordinate_system<PR>::type,
- dimension<P>::value,
- dimension<PR>::value,
- P, PR>::type transform_strategy;
-
-
- // TODO
- // ASSUMPTION: segment
- // SOLVE THIS USING OTHER FUNCTIONS using get<,>
- transform_strategy(p, pr);
- transform_strategy(s.first, ps1);
- transform_strategy(s.second, ps2);
- return calc(pr, ps1, ps2);
- }
-
- private :
- typedef point
- <
- typename coordinate_type<P>::type,
- ggl::dimension<P>::type::value,
- typename ggl::detail::get_cs_as_radian
- <
- typename coordinate_system<P>::type
- >::type
- > PR;
- double m_radius;
-
- /// Calculate course (bearing) between two points. Might be moved to a "course formula" ...
- inline double course(PR const& p1, PR const& p2) const
- {
- /***
- Course between points
-
- We obtain the initial course, tc1, (at point 1) from point 1 to point 2 by the following. The formula fails if the initial point is a pole. We can special case this with:
-
- IF (cos(lat1) < EPS) // EPS a small number ~ machine precision
- IF (lat1 > 0): tc1= pi // starting from N pole
- ELSE: tc1= 2*pi // starting from S pole
- ENDIF
- ENDIF
-
- For starting points other than the poles:
- IF sin(lon2-lon1)<0: tc1=acos((sin(lat2)-sin(lat1)*cos(d))/(sin(d)*cos(lat1)))
- ELSE: tc1=2*pi-acos((sin(lat2)-sin(lat1)*cos(d))/(sin(d)*cos(lat1)))
- ENDIF
-
- An alternative formula, not requiring the pre-computation of d, the distance between the points, is:
- tc1=mod(atan2(sin(lon1-lon2)*cos(lat2),
- cos(lat1)*sin(lat2)-sin(lat1)*cos(lat2)*cos(lon1-lon2))
- , 2*pi)
- ***/
- double dlon = get<0>(p2) - get<0>(p1);
- double cos_p2lat = cos(get<1>(p2));
- return atan2(sin(dlon) * cos_p2lat,
- cos(get<1>(p1)) * sin(get<1>(p2))
- - sin(get<1>(p1)) * cos_p2lat * cos(dlon));
- }
-
- inline return_type calc(PR const& p, PR const& sp1, PR const& sp2) const
- {
- /***
- Cross track error:
- Suppose you are proceeding on a great circle route from A to B (course =crs_AB) and end up at D, perhaps off course.
- (We presume that A is ot a pole!) You can calculate the course from A to D (crs_AD) and the distance from A to D (dist_AD)
- using the formulae above. In shifteds of these the cross track error, XTD, (distance off course) is given by
-
- XTD =asin(sin(dist_AD)*sin(crs_AD-crs_AB))
-
- (positive XTD means right of course, negative means left)
- (If the point A is the N. or S. Pole replace crs_AD-crs_AB with
- lon_D-lon_B or lon_B-lon_D, respectively.)
- ***/
-
- // Calculate distances, in radians, on the unit sphere
- // It seems not useful to let this strategy be templatized, it should be in radians and on the unit sphere
- strategy::distance::haversine<PR, PR> strategy(1.0);
- double d1 = strategy(sp1, p);
-
- // Actually, calculation of d2 not necessary if we know that the projected point is on the great circle...
- double d2 = strategy(sp2, p);
-
- // Source: http://williams.best.vwh.net/avform.htm
-
- double crs_AD = course(sp1, p);
- double crs_AB = course(sp1, sp2);
- double XTD = fabs(asin(sin(d1) * sin(crs_AD - crs_AB)));
-
- // Return shortest distance, either to projected point on segment sp1-sp2, or to sp1, or to sp2
- return return_type(m_radius * (std::min)((std::min)(d1, d2), XTD));
- }
- };
-
-
-
-
-
} // namespace distance
@@ -213,19 +92,6 @@
};
-template <typename Point, typename Segment>
-struct strategy_distance_segment<spherical_tag, spherical_tag, Point, Segment>
-{
- typedef strategy::distance::ll_point_segment<Point, Segment> type;
-};
-
-
-// Use this point-segment for geographic as well. TODO: change this, extension!
-template <typename Point, typename Segment>
-struct strategy_distance_segment<geographic_tag, geographic_tag, Point, Segment>
-{
- typedef strategy::distance::ll_point_segment<Point, Segment> type;
-};
@@ -236,11 +102,6 @@
typedef strategy_tag_distance_point_point type;
};
-template <typename Point, typename Segment>
-struct strategy_tag<strategy::distance::ll_point_segment<Point, Segment> >
-{
- typedef strategy_tag_distance_point_segment type;
-};
Deleted: sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/haversine.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/haversine.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
+++ (empty file)
@@ -1,257 +0,0 @@
-// Generic Geometry Library
-//
-// Copyright Barend Gehrels 1995-2009, Geodan Holding B.V. 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 GGL_STRATEGY_SPHERICAL_DISTANCE_HPP
-#define GGL_STRATEGY_SPHERICAL_DISTANCE_HPP
-
-
-#include <ggl/core/cs.hpp>
-#include <ggl/core/concepts/point_concept.hpp>
-#include <ggl/core/access.hpp>
-#include <ggl/core/radian_access.hpp>
-
-
-#include <ggl/strategies/strategy_traits.hpp>
-
-#include <ggl/strategies/distance_result.hpp>
-
-#include <ggl/util/get_cs_as_radian.hpp>
-
-
-
-namespace ggl
-{
-namespace strategy
-{
-
- namespace distance
- {
-
- /*!
- \brief Distance calculation for spherical coordinates on a perfect sphere using haversine
- \ingroup distance
- \tparam P1 first point type
- \tparam P2 optional second point type
- \author Adapted from: http://williams.best.vwh.net/avform.htm
- \see http://en.wikipedia.org/wiki/Great-circle_distance
- \note It says: <em>The great circle distance d between two points with coordinates {lat1,lon1} and {lat2,lon2} is given by:
- d=acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))
- A mathematically equivalent formula, which is less subject to rounding error for short distances is:
- d=2*asin(sqrt((sin((lat1-lat2)/2))^2 + cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))</em>
- */
- template <typename P1, typename P2 = P1>
- class haversine
- {
- public :
- //typedef spherical_distance return_type;
- typedef double return_type;
-
- inline haversine(double r = 1.0)
- : m_radius(r)
- {}
-
- inline return_type operator()(const P1& p1, const P2& p2) const
- {
- return calc(get_as_radian<0>(p1), get_as_radian<1>(p1),
- get_as_radian<0>(p2), get_as_radian<1>(p2));
- }
-
- private :
- double m_radius;
- typedef typename coordinate_type<P1>::type T1;
- typedef typename coordinate_type<P2>::type T2;
-
- inline return_type calc(const T1& lon1, const T1& lat1, const T2& lon2, const T2& lat2) const
- {
- double a = math::hav(lat2 - lat1) + cos(lat1) * cos(lat2) * math::hav(lon2 - lon1);
- double c = 2.0 * asin(sqrt(a));
- return return_type(m_radius * c);
- }
- };
-
-
-
- /*!
- \brief Strategy functor for distance point to segment calculation
- \ingroup distance
- \details Class which calculates the distance of a point to a segment, using latlong points
- \tparam P point type
- \tparam S segment type
- */
- template <typename P, typename S>
- class ll_point_segment
- {
- public :
- typedef double return_type;
-
- inline ll_point_segment(double r = 1.0) : m_radius(r)
- {}
-
- inline return_type operator()(P const& p, S const& s) const
- {
- PR pr, ps1, ps2;
-
- // Select transformation strategy and transform to radians (if necessary)
- typename strategy_transform<
- typename cs_tag<P>::type,
- typename cs_tag<PR>::type,
- typename coordinate_system<P>::type,
- typename coordinate_system<PR>::type,
- dimension<P>::value,
- dimension<PR>::value,
- P, PR>::type transform_strategy;
-
-
- // TODO
- // ASSUMPTION: segment
- // SOLVE THIS USING OTHER FUNCTIONS using get<,>
- transform_strategy(p, pr);
- transform_strategy(s.first, ps1);
- transform_strategy(s.second, ps2);
- return calc(pr, ps1, ps2);
- }
-
- private :
- typedef point
- <
- typename coordinate_type<P>::type,
- ggl::dimension<P>::type::value,
- typename ggl::detail::get_cs_as_radian
- <
- typename coordinate_system<P>::type
- >::type
- > PR;
- double m_radius;
-
- /// Calculate course (bearing) between two points. Might be moved to a "course formula" ...
- inline double course(PR const& p1, PR const& p2) const
- {
- /***
- Course between points
-
- We obtain the initial course, tc1, (at point 1) from point 1 to point 2 by the following. The formula fails if the initial point is a pole. We can special case this with:
-
- IF (cos(lat1) < EPS) // EPS a small number ~ machine precision
- IF (lat1 > 0): tc1= pi // starting from N pole
- ELSE: tc1= 2*pi // starting from S pole
- ENDIF
- ENDIF
-
- For starting points other than the poles:
- IF sin(lon2-lon1)<0: tc1=acos((sin(lat2)-sin(lat1)*cos(d))/(sin(d)*cos(lat1)))
- ELSE: tc1=2*pi-acos((sin(lat2)-sin(lat1)*cos(d))/(sin(d)*cos(lat1)))
- ENDIF
-
- An alternative formula, not requiring the pre-computation of d, the distance between the points, is:
- tc1=mod(atan2(sin(lon1-lon2)*cos(lat2),
- cos(lat1)*sin(lat2)-sin(lat1)*cos(lat2)*cos(lon1-lon2))
- , 2*pi)
- ***/
- double dlon = get<0>(p2) - get<0>(p1);
- double cos_p2lat = cos(get<1>(p2));
- return atan2(sin(dlon) * cos_p2lat,
- cos(get<1>(p1)) * sin(get<1>(p2))
- - sin(get<1>(p1)) * cos_p2lat * cos(dlon));
- }
-
- inline return_type calc(PR const& p, PR const& sp1, PR const& sp2) const
- {
- /***
- Cross track error:
- Suppose you are proceeding on a great circle route from A to B (course =crs_AB) and end up at D, perhaps off course.
- (We presume that A is ot a pole!) You can calculate the course from A to D (crs_AD) and the distance from A to D (dist_AD)
- using the formulae above. In shifteds of these the cross track error, XTD, (distance off course) is given by
-
- XTD =asin(sin(dist_AD)*sin(crs_AD-crs_AB))
-
- (positive XTD means right of course, negative means left)
- (If the point A is the N. or S. Pole replace crs_AD-crs_AB with
- lon_D-lon_B or lon_B-lon_D, respectively.)
- ***/
-
- // Calculate distances, in radians, on the unit sphere
- // It seems not useful to let this strategy be templatized, it should be in radians and on the unit sphere
- strategy::distance::haversine<PR, PR> strategy(1.0);
- double d1 = strategy(sp1, p);
-
- // Actually, calculation of d2 not necessary if we know that the projected point is on the great circle...
- double d2 = strategy(sp2, p);
-
- // Source: http://williams.best.vwh.net/avform.htm
-
- double crs_AD = course(sp1, p);
- double crs_AB = course(sp1, sp2);
- double XTD = fabs(asin(sin(d1) * sin(crs_AD - crs_AB)));
-
- // Return shortest distance, either to projected point on segment sp1-sp2, or to sp1, or to sp2
- return return_type(m_radius * (std::min)((std::min)(d1, d2), XTD));
- }
- };
-
-
-
-
-
- } // namespace distance
-
-
-
-
-} // namespace strategy
-
-
-#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
-template <typename P1, typename P2>
-struct strategy_distance<spherical_tag, spherical_tag, P1, P2>
-{
- typedef strategy::distance::haversine<P1, P2> type;
-};
-
-
-template <typename Point, typename Segment>
-struct strategy_distance_segment<spherical_tag, spherical_tag, Point, Segment>
-{
- typedef strategy::distance::ll_point_segment<Point, Segment> type;
-};
-
-
-// Use this point-segment for geographic as well. TODO: change this, extension!
-template <typename Point, typename Segment>
-struct strategy_distance_segment<geographic_tag, geographic_tag, Point, Segment>
-{
- typedef strategy::distance::ll_point_segment<Point, Segment> type;
-};
-
-
-
-
-template <typename P1, typename P2>
-struct strategy_tag<strategy::distance::haversine<P1, P2> >
-{
- typedef strategy_tag_distance_point_point type;
-};
-
-template <typename Point, typename Segment>
-struct strategy_tag<strategy::distance::ll_point_segment<Point, Segment> >
-{
- typedef strategy_tag_distance_point_segment type;
-};
-
-
-
-#endif
-
-
-
-
-
-
-} // namespace ggl
-
-
-#endif // GGL_STRATEGY_SPHERICAL_DISTANCE_HPP
Modified: sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/sph_area.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/sph_area.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/sph_area.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -6,11 +6,11 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef GGL_GEOMETRY_STRATEGIES_SPHERICAL_SPH_AREA_HPP
-#define GGL_GEOMETRY_STRATEGIES_SPHERICAL_SPH_AREA_HPP
+#ifndef GGL_STRATEGIES_SPHERICAL_SPH_AREA_HPP
+#define GGL_STRATEGIES_SPHERICAL_SPH_AREA_HPP
#include <ggl/geometries/segment.hpp>
-#include <ggl/strategies/spherical/haversine.hpp>
+#include <ggl/strategies/spherical/distance_haversine.hpp>
#include <ggl/strategies/strategy_transform.hpp>
#include <ggl/util/get_cs_as_radian.hpp>
@@ -164,4 +164,4 @@
} // namespace ggl
-#endif // GGL_GEOMETRY_STRATEGIES_SPHERICAL_SPH_AREA_HPP
+#endif // GGL_STRATEGIES_SPHERICAL_SPH_AREA_HPP
Modified: sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/sph_envelope.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/sph_envelope.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/spherical/sph_envelope.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -15,7 +15,6 @@
// NOTE: maybe evaluate/rework this using new "compare" strategy
// - implement "compare" for latlong (e.g. return true if distance-difference < 90 deg, so 170 < -170 but 90 > -180)
-#include <ggl/strategies/spherical/haversine.hpp>
namespace ggl
{
Modified: sandbox/ggl/formal_review_request/boost/ggl/strategies/strategies.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/strategies.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/strategies.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -20,12 +20,14 @@
#include <ggl/strategies/cartesian/cart_side.hpp>
#include <ggl/strategies/cartesian/cart_within.hpp>
+#include <ggl/strategies/spherical/distance_haversine.hpp>
+#include <ggl/strategies/spherical/distance_cross_track.hpp>
+
#include <ggl/strategies/spherical/sph_area.hpp>
-#include <ggl/strategies/spherical/haversine.hpp>
#include <ggl/strategies/spherical/sph_envelope.hpp>
#include <ggl/strategies/agnostic/agn_convex_hull.hpp>
-#include <ggl/strategies/agnostic/agn_simplify.hpp>
+#include <ggl/strategies/agnostic/simplify_douglas_peucker.hpp>
#include <ggl/strategies/agnostic/agn_within.hpp>
#include <ggl/strategies/strategy_transform.hpp>
Modified: sandbox/ggl/formal_review_request/boost/ggl/strategies/transform/inverse_transformer.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/transform/inverse_transformer.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/transform/inverse_transformer.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -9,8 +9,13 @@
#ifndef GGL_STRATEGIES_TRANSFORM_INVERSE_TRANSFORMER_HPP
#define GGL_STRATEGIES_TRANSFORM_INVERSE_TRANSFORMER_HPP
+// Remove the ublas checking, otherwise the inverse might fail
+// (while nothing seems to be wrong)
+#define BOOST_UBLAS_TYPE_CHECK 0
+
#include <boost/numeric/ublas/lu.hpp>
#include <boost/numeric/ublas/io.hpp>
+
#include <ggl/strategies/transform/matrix_transformers.hpp>
namespace ggl
Modified: sandbox/ggl/formal_review_request/boost/ggl/strategies/transform/matrix_transformers.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/strategies/transform/matrix_transformers.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/strategies/transform/matrix_transformers.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -10,7 +10,8 @@
#define GGL_STRATEGIES_MATRIX_TRANSFORMERS_HPP
-// Remove the ublas checking, otherwise the inverse might fail (while nothing seems to be wrong)
+// Remove the ublas checking, otherwise the inverse might fail
+// (while nothing seems to be wrong)
#define BOOST_UBLAS_TYPE_CHECK 0
#include <boost/numeric/conversion/cast.hpp>
Modified: sandbox/ggl/formal_review_request/boost/ggl/util/as_range.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/util/as_range.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/util/as_range.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -10,8 +10,10 @@
#define GGL_UTIL_AS_RANGE_HPP
#include <boost/type_traits.hpp>
+#include <boost/type_traits/remove_const.hpp>
#include <ggl/core/exterior_ring.hpp>
+#include <ggl/core/is_multi.hpp>
#include <ggl/core/ring_type.hpp>
#include <ggl/core/tag.hpp>
#include <ggl/core/tags.hpp>
@@ -22,14 +24,15 @@
namespace dispatch
{
-template <typename GeometryTag, typename Geometry>
+template <typename GeometryTag, bool IsMulti, typename Geometry>
struct as_range_type
{
typedef Geometry type;
};
+
template <typename Geometry>
-struct as_range_type<polygon_tag, Geometry>
+struct as_range_type<polygon_tag, false, Geometry>
{
typedef typename ring_type<Geometry>::type type;
};
@@ -39,7 +42,7 @@
template <typename GeometryTag, typename Geometry, typename Range>
struct as_range
{
- static inline Range const& get(Geometry const& input)
+ static inline Range & get(Geometry & input)
{
return input;
}
@@ -48,6 +51,25 @@
template <typename Geometry, typename Range>
struct as_range<polygon_tag, Geometry, Range>
{
+ static inline Range & get(Geometry & input)
+ {
+ return exterior_ring(input);
+ }
+};
+
+
+template <typename GeometryTag, typename Geometry, typename Range>
+struct as_range_const
+{
+ static inline Range const& get(Geometry const& input)
+ {
+ return input;
+ }
+};
+
+template <typename Geometry, typename Range>
+struct as_range_const<polygon_tag, Geometry, Range>
+{
static inline Range const& get(Geometry const& input)
{
return exterior_ring(input);
@@ -69,6 +91,7 @@
typedef typename dispatch::as_range_type
<
typename tag<Geometry>::type,
+ is_multi<Geometry>::type::value,
Geometry
>::type type;
};
@@ -82,6 +105,17 @@
template <typename Range, typename Geometry>
inline Range const& as_range(Geometry const& input)
{
+ return dispatch::as_range_const
+ <
+ typename tag<Geometry>::type,
+ Geometry,
+ Range
+ >::get(input);
+}
+
+template <typename Range, typename Geometry>
+inline Range& as_range(Geometry& input)
+{
return dispatch::as_range
<
typename tag<Geometry>::type,
Modified: sandbox/ggl/formal_review_request/boost/ggl/util/copy.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/util/copy.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/util/copy.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -12,11 +12,11 @@
#include <cstddef>
#include <boost/concept/requires.hpp>
-#include <boost/numeric/conversion/cast.hpp>
#include <boost/concept_check.hpp>
#include <ggl/core/concepts/point_concept.hpp>
+#include <boost/numeric/conversion/cast.hpp>
namespace ggl
@@ -28,7 +28,7 @@
template <typename Src, typename Dst, std::size_t D, std::size_t N>
struct copy_coordinates
{
- static inline void copy(const Src& source, Dst& dest)
+ static inline void copy(Src const& source, Dst& dest)
{
typedef typename coordinate_type<Dst>::type coordinate_type;
@@ -40,10 +40,8 @@
template <typename Src, typename Dst, std::size_t N>
struct copy_coordinates<Src, Dst, N, N>
{
- static inline void copy(const Src& source, Dst& dest)
+ static inline void copy(Src const& , Dst& )
{
- boost::ignore_unused_variable_warning(source);
- boost::ignore_unused_variable_warning(dest);
}
};
@@ -61,14 +59,20 @@
\note If destination type differs from source type, they must have the same coordinate count
*/
template <typename Src, typename Dst>
-inline void copy_coordinates(const Src& source, Dst& dest)
+inline void copy_coordinates(Src const& source, Dst& dest)
{
BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Src>) );
BOOST_CONCEPT_ASSERT( (concept::Point<Dst>) );
//assert_dimension_equal<Dst, Src>();
- detail::copy::copy_coordinates<Src, Dst, 0, dimension<Src>::value>::copy(source, dest);
+ detail::copy::copy_coordinates
+ <
+ Src,
+ Dst,
+ 0,
+ dimension<Src>::type::value
+ >::copy(source, dest);
}
} // namespace ggl
Modified: sandbox/ggl/formal_review_request/boost/ggl/util/math.hpp
==============================================================================
--- sandbox/ggl/formal_review_request/boost/ggl/util/math.hpp (original)
+++ sandbox/ggl/formal_review_request/boost/ggl/util/math.hpp 2009-10-21 05:15:16 EDT (Wed, 21 Oct 2009)
@@ -19,9 +19,39 @@
namespace ggl
{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace math {
+
+
+template <typename T, bool Floating>
+struct equals
+{
+ static inline bool apply(T const& a, T const& b)
+ {
+ return a == b;
+ }
+};
+
+template <typename T>
+struct equals<T, true>
+{
+ static inline bool apply(T const& a, T const& b)
+ {
+ // See http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.17,
+ // FUTURE: replace by some boost tool or boost::test::close_at_tolerance
+ return std::abs(a - b) <= std::numeric_limits<T>::epsilon() * std::abs(a);
+ }
+};
+
+
+}} // namespace detail::math
+#endif
+
namespace math
{
+
// Maybe replace this by boost equals or boost ublas numeric equals or so
/*!
@@ -39,16 +69,11 @@
inline bool equals(T1 const& a, T2 const& b)
{
typedef typename select_most_precise<T1, T2>::type select_type;
-
- // TODO: select on is_fundemental. Otherwise (non-fundamental), take == operator
- if (std::numeric_limits<select_type>::is_exact)
- {
- return a == b;
- }
- else
- {
- return std::abs(a - b) < std::numeric_limits<select_type>::epsilon();
- }
+ return detail::math::equals
+ <
+ select_type,
+ boost::is_floating_point<select_type>::type::value
+ >::apply(a, b);
}
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