Subject: [Boost-commit] svn:boost r65938 - in sandbox/geometry: boost/geometry/algorithms boost/geometry/algorithms/detail/overlay boost/geometry/multi/algorithms boost/geometry/multi/algorithms/detail/overlay libs/geometry/test/algorithms libs/geometry/test/multi/algorithms
From: barend.gehrels_at_[hidden]
Date: 2010-10-13 09:45:55
Author: barendgehrels
Date: 2010-10-13 09:45:54 EDT (Wed, 13 Oct 2010)
New Revision: 65938
URL: http://svn.boost.org/trac/boost/changeset/65938
Log:
Refreshed get_turns: removed is_multi, moved pieces to implementation, shared things, implemented for multi
Made orientation for linear intersections flexible (because doesn't care)
There is now clipping (intersection box/geometry) for multi_polygon and multi_linestring
Text files modified:
sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp | 4 -
sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp | 144 ++++++++++++++++++---------------------
sandbox/geometry/boost/geometry/algorithms/intersection.hpp | 12 +-
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp | 108 ++++++++++++-----------------
sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp | 57 ++++++++++++++-
sandbox/geometry/libs/geometry/test/algorithms/test_intersection.hpp | 6 +
sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp | 51 +++++++++----
7 files changed, 208 insertions(+), 174 deletions(-)
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp 2010-10-13 09:45:54 EDT (Wed, 13 Oct 2010)
@@ -111,8 +111,6 @@
<
typename tag<Geometry1>::type,
typename tag<Geometry2>::type,
- is_multi<Geometry1>::type::value,
- is_multi<Geometry2>::type::value,
Geometry1,
Geometry2,
Turns, TurnPolicy,
@@ -123,8 +121,6 @@
<
typename tag<Geometry1>::type,
typename tag<Geometry2>::type,
- is_multi<Geometry1>::type::value,
- is_multi<Geometry2>::type::value,
Geometry1,
Geometry2,
Turns, TurnPolicy,
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp 2010-10-13 09:45:54 EDT (Wed, 13 Oct 2010)
@@ -20,7 +20,6 @@
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/coordinate_dimension.hpp>
-#include <boost/geometry/core/is_multi.hpp>
#include <boost/geometry/core/reverse_dispatch.hpp>
#include <boost/geometry/core/exterior_ring.hpp>
@@ -505,10 +504,10 @@
static inline void apply(
int source_id1, Range const& range,
- int multi_index, int ring_index,
int source_id2, Box const& box,
Turns& turns,
- InterruptPolicy& )
+ InterruptPolicy& ,
+ int multi_index = -1, int ring_index = -1)
{
if (boost::size(range) <= 1)
{
@@ -647,6 +646,57 @@
};
+template
+<
+ typename Polygon,
+ typename Box,
+ typename Turns,
+ typename TurnPolicy,
+ typename InterruptPolicy
+>
+struct get_turns_polygon_cs
+{
+ static inline void apply(
+ int source_id1, Polygon const& polygon,
+ int source_id2, Box const& box,
+ Turns& turns, InterruptPolicy& interrupt_policy,
+ int multi_index = -1)
+ {
+ typedef typename geometry::ring_type<Polygon>::type ring_type;
+
+ typedef typename boost::range_iterator
+ <
+ typename interior_type<Polygon>::type const
+ >::type iterator_type;
+
+ typedef detail::get_turns::get_turns_cs
+ <
+ ring_type,
+ Box,
+ Turns,
+ TurnPolicy,
+ InterruptPolicy
+ > intersector_type;
+
+ intersector_type::apply(
+ source_id1, geometry::exterior_ring(polygon),
+ source_id2, box, turns, interrupt_policy,
+ multi_index, -1);
+
+ int i = 0;
+ for (iterator_type it = boost::begin(interior_rings(polygon));
+ it != boost::end(interior_rings(polygon));
+ ++it, ++i)
+ {
+ intersector_type::apply(
+ source_id1, *it,
+ source_id2, box, turns, interrupt_policy,
+ multi_index, i);
+ }
+
+ }
+};
+
}} // namespace detail::get_turns
#endif // DOXYGEN_NO_DETAIL
@@ -660,7 +710,6 @@
template
<
typename GeometryTag1, typename GeometryTag2,
- bool IsMulti1, bool IsMulti2,
typename Geometry1, typename Geometry2,
typename Turns,
typename TurnPolicy,
@@ -688,53 +737,17 @@
>
struct get_turns
<
- polygon_tag, box_tag, false, false,
+ polygon_tag, box_tag,
Polygon, Box,
Turns,
TurnPolicy,
InterruptPolicy
- >
-{
-
- static inline void apply(
- int source_id1, Polygon const& polygon,
- int source_id2, Box const& box,
- Turns& turns, InterruptPolicy& interrupt_policy)
- {
- typedef typename geometry::ring_type<Polygon>::type ring_type;
-
- typedef typename boost::range_iterator
+ > : detail::get_turns::get_turns_polygon_cs
<
- typename interior_type<Polygon>::type const
- >::type iterator_type;
-
-
- typedef detail::get_turns::get_turns_cs
- <
- ring_type,
- Box,
- Turns,
- TurnPolicy,
- InterruptPolicy
- > intersector_type;
-
- intersector_type::apply(
- source_id1, geometry::exterior_ring(polygon), -1, -1,
- source_id2, box,
- turns, interrupt_policy);
-
- int i = 0;
- for (iterator_type it = boost::begin(interior_rings(polygon));
- it != boost::end(interior_rings(polygon));
- ++it, ++i)
- {
- intersector_type::apply(
- source_id1, *it, -1, i,
- source_id2, box, turns, interrupt_policy);
- }
-
- }
-};
+ Polygon, Box,
+ Turns, TurnPolicy, InterruptPolicy
+ >
+{};
template
@@ -747,45 +760,23 @@
>
struct get_turns
<
- ring_tag, box_tag, false, false,
+ ring_tag, box_tag,
Ring, Box,
Turns,
TurnPolicy,
InterruptPolicy
- >
-{
- static inline void apply(
- int source_id1, Ring const& ring,
- int source_id2, Box const& box,
- Turns& turns, InterruptPolicy& interrupt_policy)
- {
- typedef typename boost::range_iterator
+ > : detail::get_turns::get_turns_cs
<
- Ring const
- >::type iterator_type;
-
- typedef detail::get_turns::get_turns_cs
- <
- Ring,
- Box,
- Turns,
- TurnPolicy,
- InterruptPolicy
- > intersector_type;
-
- intersector_type::apply(
- source_id1, ring, -1, -1,
- source_id2, box,
- turns, interrupt_policy);
+ Ring, Box,
+ Turns, TurnPolicy, InterruptPolicy
+ >
- }
-};
+{};
template
<
typename GeometryTag1, typename GeometryTag2,
- bool IsMulti1, bool IsMulti2,
typename Geometry1, typename Geometry2,
typename Turns,
typename TurnPolicy,
@@ -801,7 +792,6 @@
get_turns
<
GeometryTag2, GeometryTag1,
- IsMulti2, IsMulti1,
Geometry2, Geometry1,
Turns, TurnPolicy,
InterruptPolicy
@@ -865,8 +855,6 @@
<
typename tag<Geometry1>::type,
typename tag<Geometry2>::type,
- is_multi<Geometry1>::type::value,
- is_multi<Geometry2>::type::value,
Geometry1,
Geometry2,
Turns, TurnPolicy,
@@ -876,8 +864,6 @@
<
typename tag<Geometry1>::type,
typename tag<Geometry2>::type,
- is_multi<Geometry1>::type::value,
- is_multi<Geometry2>::type::value,
Geometry1,
Geometry2,
Turns, TurnPolicy,
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-13 09:45:54 EDT (Wed, 13 Oct 2010)
@@ -228,12 +228,12 @@
<
typename Linestring1, typename Linestring2,
typename OutputIterator, typename GeometryOut,
- typename Strategy
+ typename Strategy, order_selector Order
>
struct intersection_inserter
<
linestring_tag, linestring_tag, point_tag,
- clockwise, clockwise, clockwise,
+ Order, Order, Order,
false, false, false,
Linestring1, Linestring2,
OutputIterator, GeometryOut,
@@ -251,12 +251,12 @@
<
typename Linestring, typename Box,
typename OutputIterator, typename GeometryOut,
- typename Strategy
+ typename Strategy, order_selector Order
>
struct intersection_inserter
<
linestring_tag, box_tag, linestring_tag,
- clockwise, clockwise, clockwise,
+ Order, Order, Order,
false, true, false,
Linestring, Box,
OutputIterator, GeometryOut,
@@ -277,12 +277,12 @@
<
typename Segment, typename Box,
typename OutputIterator, typename GeometryOut,
- typename Strategy
+ typename Strategy, order_selector Order
>
struct intersection_inserter
<
segment_tag, box_tag, linestring_tag,
- clockwise, clockwise, clockwise,
+ Order, Order, Order,
false, true, false,
Segment, Box,
OutputIterator, GeometryOut,
Modified: sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp 2010-10-13 09:45:54 EDT (Wed, 13 Oct 2010)
@@ -8,7 +8,7 @@
#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
-#include <boost/geometry/multi/core/is_multi.hpp>
+#include <boost/geometry/multi/core/ring_type.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
@@ -23,96 +23,80 @@
{
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace get_turns
{
-
template
<
- typename MultiTag1,
- typename MultiTag2,
- typename MultiGeometry1,
- typename MultiGeometry2,
+ typename Multi,
+ typename Box,
typename Turns,
typename TurnPolicy,
typename InterruptPolicy
>
-struct get_turns
- <
- MultiTag1, MultiTag2,
- true, true,
- MultiGeometry1, MultiGeometry2,
- Turns,
- TurnPolicy, InterruptPolicy
- >
- : detail::get_turns::get_turns_generic
- <
- MultiGeometry1,
- MultiGeometry2,
- Turns,
- TurnPolicy, InterruptPolicy
- >
-{};
+struct get_turns_multi_polygon_cs
+{
+ static inline void apply(
+ int source_id1, Multi const& multi,
+ int source_id2, Box const& box,
+ Turns& turns, InterruptPolicy& interrupt_policy)
+ {
+ typedef typename boost::range_iterator
+ <
+ Multi const
+ >::type iterator_type;
+
+ int i = 0;
+ for (iterator_type it = boost::begin(multi);
+ it != boost::end(multi);
+ ++it, ++i)
+ {
+ // Call its single version
+ get_turns_polygon_cs
+ <
+ typename boost::range_value<Multi>::type,
+ Box,
+ Turns, TurnPolicy, InterruptPolicy
+ >::apply(source_id1, *it, source_id2, box,
+ turns, interrupt_policy, i);
+ }
+ }
+};
+}} // namespace detail::get_turns
+#endif // DOXYGEN_NO_DETAIL
-template
-<
- typename SingleTag,
- typename MultiTag,
- typename SingleGeometry,
- typename MultiGeometry,
- typename Turns,
- typename TurnPolicy,
- typename InterruptPolicy
->
-struct get_turns
- <
- SingleTag, MultiTag,
- false, true,
- SingleGeometry, MultiGeometry,
- Turns,
- TurnPolicy, InterruptPolicy
- >
- : detail::get_turns::get_turns_generic
- <
- SingleGeometry,
- MultiGeometry,
- Turns,
- TurnPolicy, InterruptPolicy
- >
-{};
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
-// Version for multi/single, necessary for multi_polygon/ring
template
<
- typename MultiTag,
- typename SingleTag,
- typename MultiGeometry,
- typename SingleGeometry,
+ typename MultiPolygon,
+ typename Box,
typename Turns,
typename TurnPolicy,
typename InterruptPolicy
>
struct get_turns
<
- MultiTag, SingleTag,
- true, false,
- MultiGeometry, SingleGeometry,
+ multi_polygon_tag, box_tag,
+ MultiPolygon, Box,
Turns,
TurnPolicy, InterruptPolicy
>
- : detail::get_turns::get_turns_generic
+ : detail::get_turns::get_turns_multi_polygon_cs
<
- MultiGeometry,
- SingleGeometry,
+ MultiPolygon,
+ Box,
Turns,
TurnPolicy, InterruptPolicy
>
{};
-
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
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-13 09:45:54 EDT (Wed, 13 Oct 2010)
@@ -107,14 +107,35 @@
};
-
+template
+<
+ typename MultiLinestring, typename Box,
+ typename OutputIterator, typename LinestringOut,
+ typename Strategy
+>
+struct clip_multi_linestring
+{
+ static inline OutputIterator apply(MultiLinestring const& multi_linestring,
+ Box const& box, OutputIterator out, Strategy const& strategy)
+ {
+ typedef typename point_type<LinestringOut>::type point_type;
+ strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
+ for (typename boost::range_iterator<MultiLinestring const>::type it
+ = boost::begin(multi_linestring);
+ it != boost::end(multi_linestring); ++it)
+ {
+ out = detail::intersection::clip_range_with_box
+ <LinestringOut>(box, *it, out, lb_strategy);
+ }
+ return out;
+ }
+};
}} // namespace detail::intersection
#endif // DOXYGEN_NO_DETAIL
-
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
@@ -125,12 +146,12 @@
<
typename MultiLinestring1, typename MultiLinestring2,
typename OutputIterator, typename GeometryOut,
- typename Strategy
+ typename Strategy, order_selector Order
>
struct intersection_inserter
<
multi_linestring_tag, multi_linestring_tag, point_tag,
- clockwise, clockwise, clockwise,
+ Order, Order, Order,
false, false, false,
MultiLinestring1, MultiLinestring2,
OutputIterator, GeometryOut,
@@ -143,16 +164,17 @@
>
{};
+
template
<
typename Linestring, typename MultiLinestring,
typename OutputIterator, typename GeometryOut,
- typename Strategy
+ typename Strategy, order_selector Order
>
struct intersection_inserter
<
linestring_tag, multi_linestring_tag, point_tag,
- clockwise, clockwise, clockwise,
+ Order, Order, Order,
false, false, false,
Linestring, MultiLinestring,
OutputIterator, GeometryOut,
@@ -166,6 +188,29 @@
{};
+template
+<
+ typename MultiLinestring, typename Box,
+ typename OutputIterator, typename GeometryOut,
+ typename Strategy, order_selector Order
+>
+struct intersection_inserter
+ <
+ multi_linestring_tag, box_tag, linestring_tag,
+ Order, Order, Order,
+ false, true, false,
+ MultiLinestring, Box,
+ OutputIterator, GeometryOut,
+ Strategy
+ > : detail::intersection::clip_multi_linestring
+ <
+ MultiLinestring, Box,
+ OutputIterator, GeometryOut,
+ Strategy
+ >
+{};
+
+
} // namespace dispatch
#endif
Modified: sandbox/geometry/libs/geometry/test/algorithms/test_intersection.hpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/test_intersection.hpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/test_intersection.hpp 2010-10-13 09:45:54 EDT (Wed, 13 Oct 2010)
@@ -60,6 +60,7 @@
boost::geometry::intersection_inserter<OutputType>(g1, g2, std::back_inserter(clip), strategy());
+
double length_or_area = 0;
std::size_t n = 0;
for (typename std::vector<OutputType>::iterator it = clip.begin();
@@ -122,11 +123,16 @@
#if defined(TEST_WITH_SVG)
{
+ bool const ccw =
+ boost::geometry::point_order<G1>::value == boost::geometry::counterclockwise
+ || boost::geometry::point_order<G2>::value == boost::geometry::counterclockwise;
+
std::ostringstream filename;
filename << "intersection_"
<< caseid << "_"
<< string_from_type<coordinate_type>::name()
<< string_from_type<CalculationType>::name()
+ << (ccw ? "_ccw" : "")
<< ".svg";
std::ofstream svg(filename.str().c_str());
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-13 09:45:54 EDT (Wed, 13 Oct 2010)
@@ -51,8 +51,37 @@
template <typename Polygon, typename MultiPolygon, typename Box>
void test_areal_clip()
{
- test_one<Polygon, Box, MultiPolygon>("simplex_multi_mp_b", "POLYGON((1 1,4 4))", case_multi_simplex[0],
- 2, 12, 6.42);
+ static std::string const clip = "POLYGON((1 1,4 4))";
+ test_one<Polygon, Box, MultiPolygon>("simplex_multi_mp_b", clip, case_multi_simplex[0],
+ 2, 11, 6.791666);
+ test_one<Polygon, MultiPolygon, Box>("simplex_multi_b_mp", case_multi_simplex[0], clip,
+ 2, 11, 6.791666);
+}
+
+template <typename LineString, typename MultiLineString, typename Box>
+void test_linear()
+{
+ typedef boost::geometry::point_type<MultiLineString>::type point;
+ test_one<point, MultiLineString, MultiLineString>("case_multi_ml_ml_1",
+ "MULTILINESTRING((0 0,1 1))", "MULTILINESTRING((0 1,1 0))",
+ 1, 1, 0);
+ test_one<point, MultiLineString, MultiLineString>("case_multi_ml_ml_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<point, LineString, MultiLineString>("case_multi_l_ml",
+ "LINESTRING(0 0,1 1)", "MULTILINESTRING((0 1,1 0),(0.5 1,1.5 0))",
+ 2, 2, 0);
+ test_one<point, MultiLineString, LineString>("case_multi_ml_l",
+ "MULTILINESTRING((0 1,1 0),(0.5 1,1.5 0))", "LINESTRING(0 0,1 1)",
+ 2, 2, 0);
+
+ test_one<LineString, MultiLineString, Box>("case_multi_ml_b",
+ "MULTILINESTRING((0 0,3 3)(1 0,4 3))", "POLYGON((1 1,3 2))",
+ 2, 4, 2 * std::sqrt(2.0));
+ test_one<LineString, Box, MultiLineString>("case_multi_b_ml",
+ "POLYGON((1 1,3 2))", "MULTILINESTRING((0 0,3 3)(1 0,4 3))",
+ 2, 4, 2 * std::sqrt(2.0));
}
@@ -74,28 +103,16 @@
test_areal<ring_ccw, polygon_ccw, multi_polygon_ccw>();
// multi/box: was NOT implemented, next step TODO.
- //test_areal_clip<polygon, multi_polygon, box>();
- //test_areal_clip<polygon_ccw, multi_polygon_ccw, box>();
+ test_areal_clip<polygon, multi_polygon, box>();
+ test_areal_clip<polygon_ccw, multi_polygon_ccw, box>();
typedef bg::linestring<P> linestring;
typedef bg::multi_linestring<linestring> multi_linestring;
+ test_linear<linestring, multi_linestring, box>();
// 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);
}