Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r62175 - in sandbox/geometry: boost/geometry/algorithms boost/geometry/multi/algorithms libs/geometry/test/algorithms
From: barend.gehrels_at_[hidden]
Date: 2010-05-24 13:03:42


Author: barendgehrels
Date: 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
New Revision: 62175
URL: http://svn.boost.org/trac/boost/changeset/62175

Log:
Moved order/closure outside dispatches, not necessary there / more overhead
Implemented order/closure in within

Text files modified:
   sandbox/geometry/boost/geometry/algorithms/area.hpp | 41 ++++++++++++++-----------
   sandbox/geometry/boost/geometry/algorithms/centroid.hpp | 41 +++++++++++++------------
   sandbox/geometry/boost/geometry/algorithms/within.hpp | 63 +++++++++++++++++++++++++++++++++------
   sandbox/geometry/boost/geometry/multi/algorithms/area.hpp | 5 +-
   sandbox/geometry/boost/geometry/multi/algorithms/centroid.hpp | 7 +---
   sandbox/geometry/boost/geometry/multi/algorithms/within.hpp | 2 +
   sandbox/geometry/libs/geometry/test/algorithms/test_within.hpp | 54 ++++++++++++++++++++++-----------
   sandbox/geometry/libs/geometry/test/algorithms/within.cpp | 2
   8 files changed, 140 insertions(+), 75 deletions(-)

Modified: sandbox/geometry/boost/geometry/algorithms/area.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/area.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/area.hpp 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
@@ -116,7 +116,6 @@
             return type();
         }
 
-
         typedef reversible_view<Ring const, Direction> rview_type;
         typedef closeable_view
             <
@@ -158,8 +157,6 @@
 <
     typename Tag,
     typename Geometry,
- order_selector Order,
- closure_selector Closure,
     typename Strategy
>
 struct area
@@ -171,26 +168,38 @@
> {};
 
 
-template <typename Geometry, order_selector Order, closure_selector Closure, typename Strategy>
-struct area<box_tag, Geometry, Order, Closure, Strategy>
+template
+<
+ typename Geometry,
+ typename Strategy
+>
+struct area<box_tag, Geometry, Strategy>
     : detail::area::box_area<Geometry, Strategy>
 {};
 
 
-template <typename Geometry, order_selector Order, closure_selector Closure, typename Strategy>
-struct area<ring_tag, Geometry, Order, Closure, Strategy>
+template
+<
+ typename Ring,
+ typename Strategy
+>
+struct area<ring_tag, Ring, Strategy>
     : detail::area::ring_area
         <
- Geometry,
- order_as_direction<Order>::value,
- Closure, //closure_as_bool<Closure>::value,
+ Ring,
+ order_as_direction<geometry::point_order<Ring>::value>::value,
+ geometry::closure<Ring>::value,
             Strategy
>
 {};
 
 
-template <typename Polygon, order_selector Order, closure_selector Closure, typename Strategy>
-struct area<polygon_tag, Polygon, Order, Closure, Strategy>
+template
+<
+ typename Polygon,
+ typename Strategy
+>
+struct area<polygon_tag, Polygon, Strategy>
     : detail::calculate_polygon_sum
         <
             typename Strategy::return_type,
@@ -199,8 +208,8 @@
             detail::area::ring_area
                 <
                     typename ring_type<Polygon>::type,
- order_as_direction<Order>::value,
- Closure, //closure_as_bool<Closure>::value,
+ order_as_direction<geometry::point_order<Polygon>::value>::value,
+ geometry::closure<Polygon>::value,
                     Strategy
>
>
@@ -234,8 +243,6 @@
         <
             typename tag<Geometry>::type,
             Geometry,
- geometry::point_order<Geometry>::value,
- geometry::closure<Geometry>::value,
             strategy_type
>::apply(geometry, strategy_type());
 }
@@ -259,8 +266,6 @@
         <
             typename tag<Geometry>::type,
             Geometry,
- geometry::point_order<Geometry>::value,
- geometry::closure<Geometry>::value,
             Strategy
>::apply(geometry, strategy);
 }

Modified: sandbox/geometry/boost/geometry/algorithms/centroid.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/centroid.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/centroid.hpp 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
@@ -276,16 +276,18 @@
     \note Because outer ring is clockwise, inners are counter clockwise,
     triangle approach is OK and works for polygons with rings.
 */
-template<typename Polygon, closure_selector Closure, typename Strategy>
+template<typename Polygon, typename Strategy>
 struct centroid_polygon_state
 {
+ typedef typename ring_type<Polygon>::type ring_type;
+
     static inline void apply(Polygon const& poly,
             Strategy const& strategy, typename Strategy::state_type& state)
     {
         typedef centroid_ring_state
             <
- typename ring_type<Polygon>::type,
- Closure,
+ ring_type,
+ geometry::closure<ring_type>::value,
                 Strategy
> per_ring;
 
@@ -303,7 +305,7 @@
     }
 };
 
-template<typename Polygon, typename Point, closure_selector Closure, typename Strategy>
+template<typename Polygon, typename Point, typename Strategy>
 struct centroid_polygon
 {
     static inline void apply(Polygon const& poly, Point& centroid,
@@ -315,7 +317,6 @@
             centroid_polygon_state
                 <
                     Polygon,
- Closure,
                     Strategy
>::apply(poly, strategy, state);
             Strategy::result(state, centroid);
@@ -337,7 +338,6 @@
     typename Tag,
     typename Geometry,
     typename Point,
- closure_selector Closure,
     typename Strategy
>
 struct centroid {};
@@ -346,10 +346,9 @@
 <
     typename Geometry,
     typename Point,
- closure_selector Closure,
     typename Strategy
>
-struct centroid<point_tag, Geometry, Point, Closure, Strategy>
+struct centroid<point_tag, Geometry, Point, Strategy>
     : detail::centroid::centroid_point<Geometry, Point, Strategy>
 {};
 
@@ -357,26 +356,31 @@
 <
     typename Box,
     typename Point,
- closure_selector Closure,
     typename Strategy
>
-struct centroid<box_tag, Box, Point, Closure, Strategy>
+struct centroid<box_tag, Box, Point, Strategy>
     : detail::centroid::centroid_box<Box, Point, Strategy>
 {};
 
-template <typename Ring, typename Point, closure_selector Closure, typename Strategy>
-struct centroid<ring_tag, Ring, Point, Closure, Strategy>
- : detail::centroid::centroid_ring<Ring, Point, Closure, Strategy>
+template <typename Ring, typename Point, typename Strategy>
+struct centroid<ring_tag, Ring, Point, Strategy>
+ : detail::centroid::centroid_ring
+ <
+ Ring,
+ Point,
+ geometry::closure<Ring>::value,
+ Strategy
+ >
 {};
 
-template <typename Linestring, typename Point, closure_selector Closure, typename Strategy>
-struct centroid<linestring_tag, Linestring, Point, Closure, Strategy>
+template <typename Linestring, typename Point, typename Strategy>
+struct centroid<linestring_tag, Linestring, Point, Strategy>
     : detail::centroid::centroid_linestring<Linestring, Point, Strategy>
  {};
 
-template <typename Polygon, typename Point, closure_selector Closure, typename Strategy>
-struct centroid<polygon_tag, Polygon, Point, Closure, Strategy>
- : detail::centroid::centroid_polygon<Polygon, Point, Closure, Strategy>
+template <typename Polygon, typename Point, typename Strategy>
+struct centroid<polygon_tag, Polygon, Point, Strategy>
+ : detail::centroid::centroid_polygon<Polygon, Point, Strategy>
  {};
 
 } // namespace dispatch
@@ -407,7 +411,6 @@
             typename tag<Geometry>::type,
             Geometry,
             Point,
- geometry::closure<Geometry>::value,
             Strategy
>::apply(geometry, c, strategy);
 }

Modified: sandbox/geometry/boost/geometry/algorithms/within.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/within.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/within.hpp 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
@@ -51,14 +51,18 @@
 #include <boost/geometry/algorithms/make.hpp>
 
 #include <boost/geometry/core/access.hpp>
+#include <boost/geometry/core/closure.hpp>
+#include <boost/geometry/core/cs.hpp>
 #include <boost/geometry/core/exterior_ring.hpp>
 #include <boost/geometry/core/interior_rings.hpp>
-#include <boost/geometry/core/cs.hpp>
-
+#include <boost/geometry/core/point_order.hpp>
+#include <boost/geometry/core/ring_type.hpp>
 #include <boost/geometry/geometries/concepts/check.hpp>
-
 #include <boost/geometry/strategies/point_in_poly.hpp>
 #include <boost/geometry/strategies/concepts/within_concept.hpp>
+#include <boost/geometry/util/order_as_direction.hpp>
+#include <boost/geometry/util/closeable_view.hpp>
+#include <boost/geometry/util/reversible_view.hpp>
 
 
 namespace boost { namespace geometry
@@ -168,7 +172,14 @@
 };
 
 
-template<typename Point, typename Ring, typename Strategy>
+template
+<
+ typename Point,
+ typename Ring,
+ iterate_direction Direction,
+ closure_selector Closure,
+ typename Strategy
+>
 struct point_in_ring
 {
     BOOST_CONCEPT_ASSERT( (geometry::concept::WithinStrategy<Strategy>) );
@@ -181,14 +192,23 @@
             return false;
         }
 
- typedef typename boost::range_iterator<Ring const>::type iterator_type;
+ typedef reversible_view<Ring const, Direction> rev_view_type;
+ typedef closeable_view
+ <
+ rev_view_type const,
+ Closure == open // close it if it is open
+ > cl_view_type;
+ typedef typename boost::range_iterator<cl_view_type const>::type iterator_type;
 
+ rev_view_type rev_view(ring);
+ cl_view_type view(rev_view);
         typename Strategy::state_type state;
+ iterator_type it = boost::begin(view);
+ iterator_type end = boost::end(view);
 
- iterator_type it = boost::begin(ring);
         for (iterator_type previous = it++;
- it != boost::end(ring);
- previous = it++)
+ it != end;
+ ++previous, ++it)
         {
             if (! strategy.apply(point, *previous, *it, state))
             {
@@ -200,7 +220,14 @@
 };
 
 // Polygon: in exterior ring, and if so, not within interior ring(s)
-template<typename Point, typename Polygon, typename Strategy>
+template
+<
+ typename Point,
+ typename Polygon,
+ iterate_direction Direction,
+ closure_selector Closure,
+ typename Strategy
+>
 struct point_in_polygon
 {
     BOOST_CONCEPT_ASSERT( (geometry::concept::WithinStrategy<Strategy>) );
@@ -213,6 +240,8 @@
             <
                 Point,
                 typename ring_type<Polygon>::type,
+ Direction,
+ Closure,
                 Strategy
> per_ring;
 
@@ -286,13 +315,25 @@
 template <typename Point, typename Ring, typename Strategy>
 struct within<point_tag, ring_tag, Point, Ring, Strategy>
     : detail::within::point_in_ring
- <Point, Ring, Strategy>
+ <
+ Point,
+ Ring,
+ order_as_direction<geometry::point_order<Ring>::value>::value,
+ geometry::closure<Ring>::value,
+ Strategy
+ >
 {};
 
 template <typename Point, typename Polygon, typename Strategy>
 struct within<point_tag, polygon_tag, Point, Polygon, Strategy>
     : detail::within::point_in_polygon
- <Point, Polygon, Strategy>
+ <
+ Point,
+ Polygon,
+ order_as_direction<geometry::point_order<Polygon>::value>::value,
+ geometry::closure<Polygon>::value,
+ Strategy
+ >
 {};
 
 } // namespace dispatch

Modified: sandbox/geometry/boost/geometry/multi/algorithms/area.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/area.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/area.hpp 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
@@ -24,8 +24,8 @@
 #ifndef DOXYGEN_NO_DISPATCH
 namespace dispatch
 {
-template <typename MultiGeometry, order_selector Order, closure_selector Closure, typename Strategy>
-struct area<multi_polygon_tag, MultiGeometry, Order, Closure, Strategy>
+template <typename MultiGeometry, typename Strategy>
+struct area<multi_polygon_tag, MultiGeometry, Strategy>
     : detail::multi_sum
         <
             typename Strategy::return_type,
@@ -35,7 +35,6 @@
                 <
                     polygon_tag,
                     typename boost::range_value<MultiGeometry>::type,
- Order, Closure,
                     Strategy
>
>

Modified: sandbox/geometry/boost/geometry/multi/algorithms/centroid.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/centroid.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/centroid.hpp 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
@@ -103,10 +103,9 @@
 <
     typename MultiPolygon,
     typename Point,
- closure_selector Closure,
     typename Strategy
>
-struct centroid<multi_polygon_tag, MultiPolygon, Point, Closure, Strategy>
+struct centroid<multi_polygon_tag, MultiPolygon, Point, Strategy>
     : detail::centroid::centroid_multi
         <
             MultiPolygon,
@@ -115,7 +114,6 @@
             detail::centroid::centroid_polygon_state
                 <
                     typename boost::range_value<MultiPolygon>::type,
- Closure,
                     Strategy
>
>
@@ -126,10 +124,9 @@
 <
     typename MultiPoint,
     typename Point,
- closure_selector Closure,
     typename Strategy
>
-struct centroid<multi_point_tag, MultiPoint, Point, Closure, Strategy>
+struct centroid<multi_point_tag, MultiPoint, Point, Strategy>
     : detail::centroid::centroid_multi
         <
             MultiPoint,

Modified: sandbox/geometry/boost/geometry/multi/algorithms/within.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/within.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/within.hpp 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
@@ -71,6 +71,8 @@
                     <
                         Point,
                         typename boost::range_value<MultiPolygon>::type,
+ order_as_direction<geometry::point_order<MultiPolygon>::value>::value,
+ geometry::closure<MultiPolygon>::value,
                         Strategy
>
>

Modified: sandbox/geometry/libs/geometry/test/algorithms/test_within.hpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/test_within.hpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/test_within.hpp 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
@@ -24,13 +24,14 @@
 void test_geometry(std::string const& wkt1,
         std::string const& wkt2, bool expected)
 {
+ namespace bg = boost::geometry;
     Geometry1 geometry1;
     Geometry2 geometry2;
 
- boost::geometry::read_wkt(wkt1, geometry1);
- boost::geometry::read_wkt(wkt2, geometry2);
+ bg::read_wkt(wkt1, geometry1);
+ bg::read_wkt(wkt2, geometry2);
 
- bool detected = boost::geometry::within(geometry1, geometry2);
+ bool detected = bg::within(geometry1, geometry2);
 
     BOOST_CHECK_MESSAGE(detected == expected,
         "within: " << wkt1
@@ -40,53 +41,68 @@
 }
 
 
-template <typename Point, bool CW>
+template <typename Point, bool Clockwise, bool Closed>
 void test_ordered_ring(std::string const& wkt_point,
         std::string const& wkt_geometry, bool expected, bool on_border)
 {
- typedef boost::geometry::linear_ring<Point, std::vector, CW> ring_type;
+ namespace bg = boost::geometry;
+ typedef bg::linear_ring<Point, std::vector, Clockwise, Closed> ring_type;
     ring_type ring;
     Point point;
 
- boost::geometry::read_wkt(wkt_geometry, ring);
- if (! CW)
+ bg::read_wkt(wkt_geometry, ring);
+ if (! Clockwise)
     {
         std::reverse(boost::begin(ring), boost::end(ring));
     }
- boost::geometry::read_wkt(wkt_point, point);
+ if (! Closed)
+ {
+ ring.resize(ring.size() - 1);
+ }
 
- bool detected = boost::geometry::within(point, ring);
+ bg::read_wkt(wkt_point, point);
+
+ bool detected = bg::within(point, ring);
 
     BOOST_CHECK_MESSAGE(detected == expected,
         "within: " << wkt_point
         << " in " << wkt_geometry
         << " -> Expected: " << expected
- << " detected: " << detected);
+ << " detected: " << detected
+ << " clockwise: " << int(Clockwise)
+ << " closed: " << int(Closed)
+ );
 
     // other strategy (note that this one cannot detect OnBorder
     // (without modifications)
 
- boost::geometry::strategy::within::franklin<Point> franklin;
- detected = boost::geometry::within(point, ring, franklin);
+ bg::strategy::within::franklin<Point> franklin;
+ detected = bg::within(point, ring, franklin);
     if (! on_border)
     {
         BOOST_CHECK_MESSAGE(detected == expected,
             "within: " << wkt_point
             << " in " << wkt_geometry
             << " -> Expected: " << expected
- << " detected: " << detected);
+ << " detected: " << detected
+ << " clockwise: " << int(Clockwise)
+ << " closed: " << int(Closed)
+ );
     }
 
 
- boost::geometry::strategy::within::crossings_multiply<Point> cm;
- detected = boost::geometry::within(point, ring, cm);
+ bg::strategy::within::crossings_multiply<Point> cm;
+ detected = bg::within(point, ring, cm);
     if (! on_border)
     {
         BOOST_CHECK_MESSAGE(detected == expected,
             "within: " << wkt_point
             << " in " << wkt_geometry
             << " -> Expected: " << expected
- << " detected: " << detected);
+ << " detected: " << detected
+ << " clockwise: " << int(Clockwise)
+ << " closed: " << int(Closed)
+ );
     }
 }
 
@@ -95,8 +111,10 @@
         std::string const& wkt_geometry,
         bool expected, bool on_border)
 {
- test_ordered_ring<Point, true>(wkt_point, wkt_geometry, expected, on_border);
- test_ordered_ring<Point, false>(wkt_point, wkt_geometry, expected, on_border);
+ test_ordered_ring<Point, true, true>(wkt_point, wkt_geometry, expected, on_border);
+ test_ordered_ring<Point, false, true>(wkt_point, wkt_geometry, expected, on_border);
+ test_ordered_ring<Point, true, false>(wkt_point, wkt_geometry, expected, on_border);
+ test_ordered_ring<Point, false, false>(wkt_point, wkt_geometry, expected, on_border);
     test_geometry<Point, boost::geometry::polygon<Point> >(wkt_point, wkt_geometry, expected);
 }
 

Modified: sandbox/geometry/libs/geometry/test/algorithms/within.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/within.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/within.cpp 2010-05-24 13:03:41 EDT (Mon, 24 May 2010)
@@ -77,5 +77,5 @@
     test_all<boost::geometry::point_xy<boost::numeric_adaptor::gmp_value_type> >();
 #endif
 
- return 0;
+ return 0;
 }


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