[Boost-commit] svn:boost r65892 - in sandbox/geometry: boost/geometry/algorithms boost/geometry/core boost/geometry/multi/algorithms boost/geometry/multi/core libs/geometry/test/multi/algorithms

Subject: [Boost-commit] svn:boost r65892 - in sandbox/geometry: boost/geometry/algorithms boost/geometry/core boost/geometry/multi/algorithms boost/geometry/multi/core libs/geometry/test/multi/algorithms
From: barend.gehrels_at_[hidden]
Date: 2010-10-10 15:47:32

Author: barendgehrels
Date: 2010-10-10 15:47:31 EDT (Sun, 10 Oct 2010)
New Revision: 65892
URL: http://svn.boost.org/trac/boost/changeset/65892

Log:
Added multi_linestring of intersections
Changed intersection dispatching using is_areal
Added:
   sandbox/geometry/boost/geometry/core/is_areal.hpp   (contents, props changed)
   sandbox/geometry/boost/geometry/multi/core/is_areal.hpp   (contents, props changed)
Text files modified: 
   sandbox/geometry/boost/geometry/algorithms/intersection.hpp                 |    50 ++++++++-------                         
   sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp           |   129 ++++++++++++++++++++++++++++++++++----- 
   sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp |    33 ++++++++++                              
   3 files changed, 171 insertions(+), 41 deletions(-)

Modified: sandbox/geometry/boost/geometry/algorithms/intersection.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/intersection.hpp	(original)
+++ sandbox/geometry/boost/geometry/algorithms/intersection.hpp	2010-10-10 15:47:31 EDT (Sun, 10 Oct 2010)
@@ -18,6 +18,7 @@
 
 
 #include <boost/geometry/core/reverse_dispatch.hpp>
+#include <boost/geometry/core/is_areal.hpp>
 #include <boost/geometry/geometries/concepts/check.hpp>
 #include <boost/geometry/algorithms/detail/overlay/clip_linestring.hpp>
 #include <boost/geometry/algorithms/detail/overlay/assemble.hpp>
@@ -101,7 +102,7 @@
 
 
 
-}} // namespace detail::disjoint
+}} // namespace detail::intersection
 #endif // DOXYGEN_NO_DETAIL
 
 
@@ -112,7 +113,11 @@
 
 template
 <
+    // tag dispatching:
     typename TagIn1, typename TagIn2, typename TagOut,
+    // metafunction finetuning helpers:
+    bool Areal1, bool Areal2, bool ArealOut, 
+    // real types
     typename Geometry1, typename Geometry2,
     typename OutputIterator,
     typename GeometryOut,
@@ -130,39 +135,24 @@
 
 template
 <
-    typename Polygon1, typename Polygon2,
+    typename TagIn1, typename TagIn2, typename TagOut,
+    typename Geometry1, typename Geometry2,
     typename OutputIterator,
-    typename PolygonOut,
+    typename GeometryOut,
     typename Strategy
 >
 struct intersection_inserter
     <
-        polygon_tag, polygon_tag, polygon_tag,
-        Polygon1, Polygon2,
-        OutputIterator, PolygonOut,
+        TagIn1, TagIn2, TagOut,
+        true, true, true,
+        Geometry1, Geometry2,
+        OutputIterator, GeometryOut,
         Strategy
     > : detail::overlay::overlay
-        <Polygon1, Polygon2, OutputIterator, PolygonOut, -1, Strategy>
+        <Geometry1, Geometry2, OutputIterator, GeometryOut, -1, Strategy>
 {};
 
 
-template
-<
-    typename Polygon, typename Box,
-    typename OutputIterator,
-    typename PolygonOut,
-    typename Strategy
->
-struct intersection_inserter
-    <
-        polygon_tag, box_tag, polygon_tag,
-        Polygon, Box,
-        OutputIterator, PolygonOut,
-        Strategy
-    > : detail::overlay::overlay
-        <Polygon, Box, OutputIterator, PolygonOut, -1, Strategy>
-{};
-
 
 template
 <
@@ -173,6 +163,7 @@
 struct intersection_inserter
     <
         segment_tag, segment_tag, point_tag,
+        false, false, false,
         Segment1, Segment2,
         OutputIterator, GeometryOut,
         Strategy
@@ -194,6 +185,7 @@
 struct intersection_inserter
     <
         linestring_tag, linestring_tag, point_tag,
+        false, false, false,
         Linestring1, Linestring2,
         OutputIterator, GeometryOut,
         Strategy
@@ -215,6 +207,7 @@
 struct intersection_inserter
     <
         linestring_tag, box_tag, linestring_tag,
+        false, true, false,
         Linestring, Box,
         OutputIterator, GeometryOut,
         Strategy
@@ -239,6 +232,7 @@
 struct intersection_inserter
     <
         segment_tag, box_tag, linestring_tag,
+        false, true, false,
         Segment, Box,
         OutputIterator, GeometryOut,
         Strategy
@@ -261,6 +255,7 @@
 template
 <
     typename GeometryTag1, typename GeometryTag2, typename GeometryTag3,
+    bool Areal1, bool Areal2, bool ArealOut, 
     typename Geometry1, typename Geometry2,
     typename OutputIterator, typename GeometryOut,
     typename Strategy
@@ -274,6 +269,7 @@
         return intersection_inserter
             <
                 GeometryTag2, GeometryTag1, GeometryTag3,
+                Areal2, Areal1, ArealOut, 
                 Geometry2, Geometry1,
                 OutputIterator, GeometryOut,
                 Strategy
@@ -331,6 +327,9 @@
                 typename tag<Geometry1>::type,
                 typename tag<Geometry2>::type,
                 typename tag<GeometryOut>::type,
+                is_areal<Geometry1>::value,
+                is_areal<Geometry2>::value,
+                is_areal<GeometryOut>::value,
                 Geometry1,
                 Geometry2,
                 OutputIterator, GeometryOut,
@@ -341,6 +340,9 @@
                 typename tag<Geometry1>::type,
                 typename tag<Geometry2>::type,
                 typename tag<GeometryOut>::type,
+                is_areal<Geometry1>::value,
+                is_areal<Geometry2>::value,
+                is_areal<GeometryOut>::value,
                 Geometry1,
                 Geometry2,
                 OutputIterator, GeometryOut,

Added: sandbox/geometry/boost/geometry/core/is_areal.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/core/is_areal.hpp	2010-10-10 15:47:31 EDT (Sun, 10 Oct 2010)
@@ -0,0 +1,54 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+
+#ifndef BOOST_GEOMETRY_CORE_IS_AREAL_HPP
+#define BOOST_GEOMETRY_CORE_IS_AREAL_HPP
+
+
+#include <boost/type_traits.hpp>
+
+
+#include <boost/geometry/core/tag.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace core_dispatch
+{
+
+template <typename GeometryTag> struct is_areal : boost::false_type {};
+
+template <> struct is_areal<ring_tag> : boost::true_type {};
+template <> struct is_areal<box_tag> : boost::true_type {};
+template <> struct is_areal<polygon_tag> : boost::true_type {};
+
+
+} // namespace core_dispatch
+#endif
+
+
+
+/*!
+    \brief Meta-function defining "true" for areal types (box, (multi)polygon, ring),
+    \note Used for tag dispatching and meta-function finetuning
+    \note Even though linear_ring is called linear, it has areal properties.
+    \ingroup core
+*/
+template <typename Geometry>
+struct is_areal : core_dispatch::is_areal<typename tag<Geometry>::type>
+{};
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_CORE_IS_AREAL_HPP

Modified: sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp	(original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp	2010-10-10 15:47:31 EDT (Sun, 10 Oct 2010)
@@ -10,51 +10,146 @@
 
 
 #include <boost/geometry/algorithms/intersection.hpp>
+#include <boost/geometry/multi/core/is_areal.hpp>
 #include <boost/geometry/multi/algorithms/detail/overlay/assemble.hpp>
 
 
 namespace boost { namespace geometry
 {
 
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace intersection
+{
+
+
+template
+<
+    typename MultiLinestring1, typename MultiLinestring2,
+    typename OutputIterator, typename PointOut,
+    typename Strategy
+>
+struct intersection_multi_linestring_multi_linestring_point
+{
+    static inline OutputIterator apply(MultiLinestring1 const& ml1,
+            MultiLinestring2 const& ml2, OutputIterator out,
+            Strategy const& strategy)
+    {
+        // Note, this loop is quadratic w.r.t. number of linestrings per input.
+        // Future Enhancement: first do the sections of each, then intersect.
+        for (typename boost::range_iterator
+                <
+                    MultiLinestring1 const
+                >::type it1 = boost::begin(ml1);
+            it1 != boost::end(ml1);
+            ++it1)
+        {
+            for (typename boost::range_iterator
+                    <
+                        MultiLinestring2 const
+                    >::type it2 = boost::begin(ml2);
+                it2 != boost::end(ml2);
+                ++it2)
+            {
+                out = intersection_linestring_linestring_point
+                    <
+                        typename boost::range_value<MultiLinestring1>::type,
+                        typename boost::range_value<MultiLinestring2>::type,
+                        OutputIterator, PointOut, Strategy
+                    >::apply(*it1, *it2, out, strategy);
+            }
+        }
+
+        return out;
+    }
+};
+
+
+template
+<
+    typename Linestring, typename MultiLinestring,
+    typename OutputIterator, typename PointOut,
+    typename Strategy
+>
+struct intersection_linestring_multi_linestring_point
+{
+    static inline OutputIterator apply(Linestring const& linestring,
+            MultiLinestring const& ml, OutputIterator out,
+            Strategy const& strategy)
+    {
+        for (typename boost::range_iterator
+                <
+                    MultiLinestring const
+                >::type it = boost::begin(ml);
+            it != boost::end(ml);
+            ++it)
+        {
+            out = intersection_linestring_linestring_point
+                <
+                    Linestring,
+                    typename boost::range_value<MultiLinestring>::type,
+                    OutputIterator, PointOut, Strategy
+                >::apply(linestring, *it, out, strategy);
+        }
+
+        return out;
+    }
+};
+
+
+
+
+
+}} // namespace detail::intersection
+#endif // DOXYGEN_NO_DETAIL
+
+
 
 #ifndef DOXYGEN_NO_DISPATCH
 namespace dispatch
 {
 
 
+// Linear
 template
 <
-    typename Polygon, typename MultiPolygon,
-    typename OutputIterator,
-    typename PolygonOut,
+    typename MultiLinestring1, typename MultiLinestring2,
+    typename OutputIterator, typename GeometryOut,
     typename Strategy
 >
 struct intersection_inserter
     <
-        polygon_tag, multi_polygon_tag, polygon_tag,
-        Polygon, MultiPolygon,
-        OutputIterator, PolygonOut,
+        multi_linestring_tag, multi_linestring_tag, point_tag,
+        false, false, false,
+        MultiLinestring1, MultiLinestring2,
+        OutputIterator, GeometryOut,
         Strategy
-    > : detail::overlay::overlay
-        <Polygon, MultiPolygon, OutputIterator, PolygonOut, -1, Strategy>
+    > : detail::intersection::intersection_multi_linestring_multi_linestring_point
+            <
+                MultiLinestring1, MultiLinestring2,
+                OutputIterator, GeometryOut,
+                Strategy
+            >
 {};
 
-
 template
 <
-    typename MultiPolygon1, typename MultiPolygon2,
-    typename OutputIterator,
-    typename PolygonOut,
+    typename Linestring, typename MultiLinestring,
+    typename OutputIterator, typename GeometryOut,
     typename Strategy
 >
 struct intersection_inserter
     <
-        multi_polygon_tag, multi_polygon_tag, polygon_tag,
-        MultiPolygon1, MultiPolygon2,
-        OutputIterator, PolygonOut,
+        linestring_tag, multi_linestring_tag, point_tag,
+        false, false, false,
+        Linestring, MultiLinestring,
+        OutputIterator, GeometryOut,
         Strategy
-    > : detail::overlay::overlay
-        <MultiPolygon1, MultiPolygon2, OutputIterator, PolygonOut, -1, Strategy>
+    > : detail::intersection::intersection_linestring_multi_linestring_point
+            <
+                Linestring, MultiLinestring,
+                OutputIterator, GeometryOut,
+                Strategy
+            >
 {};
 
 

Added: sandbox/geometry/boost/geometry/multi/core/is_areal.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/multi/core/is_areal.hpp	2010-10-10 15:47:31 EDT (Sun, 10 Oct 2010)
@@ -0,0 +1,37 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+
+#ifndef BOOST_GEOMETRY_MULTI_CORE_IS_AREAL_HPP
+#define BOOST_GEOMETRY_MULTI_CORE_IS_AREAL_HPP
+
+
+#include <boost/type_traits.hpp>
+
+
+#include <boost/geometry/core/is_areal.hpp>
+#include <boost/geometry/multi/core/tags.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace core_dispatch
+{
+
+template <> struct is_areal<multi_polygon_tag> : boost::true_type {};
+
+} // namespace core_dispatch
+#endif
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_MULTI_CORE_IS_AREAL_HPP

Modified: sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp	(original)
+++ sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp	2010-10-10 15:47:31 EDT (Sun, 10 Oct 2010)
@@ -15,6 +15,7 @@
 
 #include <boost/geometry/multi/algorithms/intersection.hpp>
 
+#include <boost/geometry/multi/geometries/multi_point.hpp>
 #include <boost/geometry/multi/geometries/multi_linestring.hpp>
 #include <boost/geometry/multi/geometries/multi_polygon.hpp>
 
@@ -27,9 +28,13 @@
     // polygon/multi polygon and ring/multi polygon are tested in union
 
     namespace bg = boost::geometry;
+    typedef bg::linear_ring<P> ring;
     typedef bg::polygon<P> polygon;
     typedef bg::multi_polygon<polygon> multi_polygon;
 
+    typedef bg::linestring<P> linestring;
+    typedef bg::multi_linestring<linestring> multi_linestring;
+
     test_one<polygon, multi_polygon, multi_polygon>("simplex_multi",
         case_multi_simplex[0], case_multi_simplex[1],
         2, 12, 6.42);
@@ -40,6 +45,34 @@
     test_one<polygon, multi_polygon, multi_polygon>("case_multi_2",
         case_multi_2[0], case_multi_2[1],
         3, 12, 5.9);
+
+    test_one<polygon, multi_polygon, polygon>("simplex_multi_mp_p",
+        case_multi_simplex[0], case_single_simplex,
+        1, 20, 14.58);
+
+    test_one<polygon, ring, multi_polygon>("simplex_multi_r_mp",
+        case_single_simplex, case_multi_simplex[0],
+        1, 20, 14.58);
+    /*test_one<ring, multi_polygon, polygon>("simplex_multi_mp_r",
+        case_multi_simplex[0], case_single_simplex,
+        1, 20, 14.58);*/
+
+
+    // linear
+    test_one<P, multi_linestring, multi_linestring>("case_multi_linear_1",
+        "MULTILINESTRING((0 0,1 1))", "MULTILINESTRING((0 1,1 0))",
+        1, 1, 0);
+    test_one<P, multi_linestring, multi_linestring>("case_multi_linear_2",
+        "MULTILINESTRING((0 0,1 1),(0.5 0,1.5 1))", "MULTILINESTRING((0 1,1 0),(0.5 1,1.5 0))",
+        4, 4, 0);
+
+    test_one<P, linestring, multi_linestring>("case_multi_linear_3",
+        "LINESTRING(0 0,1 1)", "MULTILINESTRING((0 1,1 0),(0.5 1,1.5 0))",
+        2, 2, 0);
+    test_one<P, multi_linestring, linestring>("case_multi_linear_4",
+        "MULTILINESTRING((0 1,1 0),(0.5 1,1.5 0))", "LINESTRING(0 0,1 1)", 
+        2, 2, 0);
+
 }