|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r65920 - in sandbox/geometry: boost/geometry/algorithms boost/geometry/algorithms/detail/overlay boost/geometry/multi/algorithms boost/geometry/multi/core libs/geometry/test/algorithms libs/geometry/test/algorithms/overlay libs/geometry/test/multi/algorithms
From: barend.gehrels_at_[hidden]
Date: 2010-10-12 06:39:12
Author: barendgehrels
Date: 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
New Revision: 65920
URL: http://svn.boost.org/trac/boost/changeset/65920
Log:
Finished ccw implementation of intersection
Added mpl assert for correct, if not implemented
Restructured intersection.cpp unit test to support cw
Added:
sandbox/geometry/boost/geometry/algorithms/detail/overlay/reverse_operations.hpp (contents, props changed)
sandbox/geometry/boost/geometry/multi/core/point_order.hpp (contents, props changed)
Text files modified:
sandbox/geometry/boost/geometry/algorithms/correct.hpp | 33 ++++
sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp | 30 ++-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp | 2
sandbox/geometry/boost/geometry/algorithms/intersection.hpp | 36 +++++
sandbox/geometry/boost/geometry/algorithms/union.hpp | 2
sandbox/geometry/boost/geometry/multi/algorithms/correct.hpp | 14 +
sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp | 3
sandbox/geometry/libs/geometry/test/algorithms/intersection.cpp | 266 ++++++++++++++++++---------------------
sandbox/geometry/libs/geometry/test/algorithms/overlay/ccw_traverse.cpp | 24 ---
sandbox/geometry/libs/geometry/test/algorithms/overlay/overlay.sln | 12 -
sandbox/geometry/libs/geometry/test/algorithms/test_intersection.hpp | 5
sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp | 49 ++++--
12 files changed, 255 insertions(+), 221 deletions(-)
Modified: sandbox/geometry/boost/geometry/algorithms/correct.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/correct.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/correct.hpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -14,6 +14,7 @@
#include <cstddef>
#include <functional>
+#include <boost/mpl/assert.hpp>
#include <boost/range.hpp>
#include <boost/geometry/core/closure.hpp>
@@ -36,6 +37,13 @@
namespace detail { namespace correct
{
+template <typename Geometry>
+struct correct_nop
+{
+ static inline void apply(Geometry& )
+ {}
+};
+
template <typename Box, std::size_t Dimension, std::size_t DimensionCount>
struct correct_box_loop
@@ -172,12 +180,29 @@
template <typename Tag, typename Geometry>
struct correct
{
- static inline void apply(Geometry& geometry)
- {
- // Default: no action necessary
- }
+ BOOST_MPL_ASSERT_MSG
+ (
+ false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
+ , (types<Geometry>)
+ );
};
+template <typename Point>
+struct correct<point_tag, Point>
+ : detail::correct::correct_nop<Point>
+{};
+
+template <typename LineString>
+struct correct<linestring_tag, LineString>
+ : detail::correct::correct_nop<LineString>
+{};
+
+template <typename Segment>
+struct correct<segment_tag, Segment>
+ : detail::correct::correct_nop<Segment>
+{};
+
+
template <typename Box>
struct correct<box_tag, Box>
: detail::correct::correct_box<Box>
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -17,18 +17,18 @@
#include <boost/mpl/assert.hpp>
-#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
-#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
-#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp>
-
-#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
-
-
-#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
+#include <boost/geometry/algorithms/detail/overlay/reverse_operations.hpp>
+//#include <boost/geometry/strategies/intersection_result.hpp>
#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
+#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/algorithms/detail/point_on_border.hpp>
#include <boost/geometry/algorithms/convert.hpp>
#include <boost/geometry/algorithms/combine.hpp>
@@ -36,18 +36,16 @@
#include <boost/geometry/algorithms/num_points.hpp>
#include <boost/geometry/algorithms/within.hpp>
-#include <boost/geometry/algorithms/detail/point_on_border.hpp>
-
#include <boost/geometry/iterators/range_type.hpp>
#include <boost/geometry/util/math.hpp>
-
#include <boost/geometry/strategies/intersection.hpp>
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
# include <boost/geometry/util/write_dsv.hpp>
#endif
+
namespace boost { namespace geometry
{
@@ -625,7 +623,7 @@
template
<
- typename GeometryOut,
+ typename GeometryOut,
typename Rings, typename Map,
typename Geometry1, typename Geometry2,
typename OutputIterator
@@ -764,7 +762,7 @@
<
typename Geometry1, typename Geometry2,
typename OutputIterator, typename GeometryOut,
- int Direction,
+ int Direction, bool ClockWise,
typename Strategy
>
struct overlay
@@ -815,6 +813,11 @@
detail::overlay::calculate_distance_policy
>(geometry1, geometry2, turn_points, policy);
+ if (! ClockWise)
+ {
+ detail::overlay::reverse_operations(turn_points);
+ }
+
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "enrich" << std::endl;
#endif
@@ -847,4 +850,5 @@
}} // namespace boost::geometry
+
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -11,6 +11,8 @@
#include <boost/geometry/algorithms/distance.hpp>
+#include <boost/geometry/strategies/intersection.hpp>
+
namespace boost { namespace geometry
{
Added: sandbox/geometry/boost/geometry/algorithms/detail/overlay/reverse_operations.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/reverse_operations.hpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -0,0 +1,52 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_REVERSE_OPERATIONS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_REVERSE_OPERATIONS_HPP
+
+
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
+
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+template <typename Turns>
+void reverse_operations(Turns& turns)
+{
+ for(typename boost::range_iterator<Turns>::type it
+ = boost::begin(turns); it != boost::end(turns); ++it)
+ {
+ for (unsigned int i = 0; i < it->operations.size(); i++)
+ {
+ operation_type& op = it->operations[i].operation;
+ switch(op)
+ {
+ case operation_union : op = operation_intersection; break;
+ case operation_intersection : op = operation_union; break;
+ }
+ }
+ }
+}
+
+
+}} // namespace detail::overlay
+#endif //DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_REVERSE_OPERATIONS_HPP
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-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -115,6 +115,8 @@
<
// tag dispatching:
typename TagIn1, typename TagIn2, typename TagOut,
+ // orientation
+ order_selector Order1, order_selector Order2, order_selector OrderOut,
// metafunction finetuning helpers:
bool Areal1, bool Areal2, bool ArealOut,
// real types
@@ -144,14 +146,34 @@
struct intersection_inserter
<
TagIn1, TagIn2, TagOut,
+ clockwise, clockwise, clockwise,
true, true, true,
Geometry1, Geometry2,
OutputIterator, GeometryOut,
Strategy
> : detail::overlay::overlay
- <Geometry1, Geometry2, OutputIterator, GeometryOut, -1, Strategy>
+ <Geometry1, Geometry2, OutputIterator, GeometryOut, -1, true, Strategy>
{};
+template
+<
+ typename TagIn1, typename TagIn2, typename TagOut,
+ typename Geometry1, typename Geometry2,
+ typename OutputIterator,
+ typename GeometryOut,
+ typename Strategy
+>
+struct intersection_inserter
+ <
+ TagIn1, TagIn2, TagOut,
+ counterclockwise, counterclockwise, counterclockwise,
+ true, true, true,
+ Geometry1, Geometry2,
+ OutputIterator, GeometryOut,
+ Strategy
+ > : detail::overlay::overlay
+ <Geometry1, Geometry2, OutputIterator, GeometryOut, -1, false, Strategy>
+{};
template
@@ -163,6 +185,7 @@
struct intersection_inserter
<
segment_tag, segment_tag, point_tag,
+ clockwise, clockwise, clockwise,
false, false, false,
Segment1, Segment2,
OutputIterator, GeometryOut,
@@ -185,6 +208,7 @@
struct intersection_inserter
<
linestring_tag, linestring_tag, point_tag,
+ clockwise, clockwise, clockwise,
false, false, false,
Linestring1, Linestring2,
OutputIterator, GeometryOut,
@@ -207,6 +231,7 @@
struct intersection_inserter
<
linestring_tag, box_tag, linestring_tag,
+ clockwise, clockwise, clockwise,
false, true, false,
Linestring, Box,
OutputIterator, GeometryOut,
@@ -232,6 +257,7 @@
struct intersection_inserter
<
segment_tag, box_tag, linestring_tag,
+ clockwise, clockwise, clockwise,
false, true, false,
Segment, Box,
OutputIterator, GeometryOut,
@@ -255,6 +281,7 @@
template
<
typename GeometryTag1, typename GeometryTag2, typename GeometryTag3,
+ order_selector Order1, order_selector Order2, order_selector OrderOut,
bool Areal1, bool Areal2, bool ArealOut,
typename Geometry1, typename Geometry2,
typename OutputIterator, typename GeometryOut,
@@ -269,6 +296,7 @@
return intersection_inserter
<
GeometryTag2, GeometryTag1, GeometryTag3,
+ Order2, Order1, OrderOut,
Areal2, Areal1, ArealOut,
Geometry2, Geometry1,
OutputIterator, GeometryOut,
@@ -327,6 +355,9 @@
typename tag<Geometry1>::type,
typename tag<Geometry2>::type,
typename tag<GeometryOut>::type,
+ point_order<Geometry1>::value,
+ point_order<Geometry2>::value,
+ point_order<GeometryOut>::value,
is_areal<Geometry1>::value,
is_areal<Geometry2>::value,
is_areal<GeometryOut>::value,
@@ -340,6 +371,9 @@
typename tag<Geometry1>::type,
typename tag<Geometry2>::type,
typename tag<GeometryOut>::type,
+ point_order<Geometry1>::value,
+ point_order<Geometry2>::value,
+ point_order<GeometryOut>::value,
is_areal<Geometry1>::value,
is_areal<Geometry2>::value,
is_areal<GeometryOut>::value,
Modified: sandbox/geometry/boost/geometry/algorithms/union.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/union.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/union.hpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -38,7 +38,7 @@
>
struct union_inserter
: detail::overlay::overlay
- <G1, G2, OutputIterator, GeometryOut, 1, Strategy>
+ <G1, G2, OutputIterator, GeometryOut, 1, true, Strategy>
{
};
Modified: sandbox/geometry/boost/geometry/multi/algorithms/correct.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/correct.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/correct.hpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -18,16 +18,26 @@
#include <boost/geometry/multi/core/tags.hpp>
-
namespace boost { namespace geometry
{
-
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
+template <typename MultiPoint>
+struct correct<multi_point_tag, MultiPoint>
+ : detail::correct::correct_nop<MultiPoint>
+{};
+
+
+template <typename MultiLineString>
+struct correct<multi_linestring_tag, MultiLineString>
+ : detail::correct::correct_nop<MultiLineString>
+{};
+
+
template <typename Geometry>
struct correct<multi_polygon_tag, Geometry>
: detail::multi_modify
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-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -11,6 +11,7 @@
#include <boost/geometry/algorithms/intersection.hpp>
#include <boost/geometry/multi/core/is_areal.hpp>
+#include <boost/geometry/multi/core/point_order.hpp>
#include <boost/geometry/multi/algorithms/detail/overlay/assemble.hpp>
@@ -119,6 +120,7 @@
struct intersection_inserter
<
multi_linestring_tag, multi_linestring_tag, point_tag,
+ clockwise, clockwise, clockwise,
false, false, false,
MultiLinestring1, MultiLinestring2,
OutputIterator, GeometryOut,
@@ -140,6 +142,7 @@
struct intersection_inserter
<
linestring_tag, multi_linestring_tag, point_tag,
+ clockwise, clockwise, clockwise,
false, false, false,
Linestring, MultiLinestring,
OutputIterator, GeometryOut,
Added: sandbox/geometry/boost/geometry/multi/core/point_order.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/multi/core/point_order.hpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -0,0 +1,43 @@
+// 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_POINT_ORDER_HPP
+#define BOOST_GEOMETRY_MULTI_CORE_POINT_ORDER_HPP
+
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/point_order.hpp>
+#include <boost/geometry/core/tag.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace core_dispatch
+{
+
+// Specialization for multi_polygon: the order is the order of its polygons
+template <typename MultiPolygon>
+struct point_order<multi_polygon_tag, MultiPolygon>
+{
+ static const order_selector value = core_dispatch::point_order
+ <
+ polygon_tag,
+ typename boost::range_value<MultiPolygon>::type
+ >::value ;
+};
+
+} // namespace core_dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_MULTI_CORE_POINT_ORDER_HPP
Modified: sandbox/geometry/libs/geometry/test/algorithms/intersection.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/intersection.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/intersection.cpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -20,218 +20,116 @@
#include <test_geometries/custom_segment.hpp>
-
-template <typename P>
-void test_all()
+template <typename Polygon>
+void test_polygons()
{
- typedef boost::geometry::linestring<P> linestring;
- typedef boost::geometry::polygon<P> polygon;
- typedef boost::geometry::box<P> box;
- typedef boost::geometry::model::segment<P> segment;
-
- std::string clip = "box(2 2,8 8)";
-
- test_one<polygon, polygon, polygon>("simplex_normal",
+ test_one<Polygon, Polygon, Polygon>("simplex_normal",
simplex_normal[0], simplex_normal[1],
1, 7, 5.47363293);
-
-
- // Basic check: box/linestring, is clipping OK? should compile in any order
- test_one<linestring, linestring, box>("llb", "LINESTRING(0 0,10 10)", clip, 1, 2, sqrt(2.0 * 6.0 * 6.0));
- test_one<linestring, box, linestring>("lbl", clip, "LINESTRING(0 0,10 10)", 1, 2, sqrt(2.0 * 6.0 * 6.0));
-
- // Box/segment
- test_one<linestring, segment, box>("lsb", "LINESTRING(0 0,10 10)", clip, 1, 2, sqrt(2.0 * 6.0 * 6.0));
- test_one<linestring, box, segment>("lbs", clip, "LINESTRING(0 0,10 10)", 1, 2, sqrt(2.0 * 6.0 * 6.0));
-
- // Completely inside
- test_one<linestring, linestring, box>("llbi", "LINESTRING(3 3,7 7)", clip, 1, 2, sqrt(2.0 * 4.0 * 4.0));
-
- // Completely outside
- test_one<linestring, linestring, box>("llbo", "LINESTRING(9 9,10 10)", clip, 0, 0, 0);
-
- // Touching with point (-> output linestring with ONE point)
- //std::cout << "Note: the output line is degenerate! Might be removed!" << std::endl;
- test_one<linestring, linestring, box>("llb_touch", "LINESTRING(8 8,10 10)", clip, 1, 1, 0.0);
-
- // Along border
- test_one<linestring, linestring, box>("llb_along", "LINESTRING(2 2,2 8)", clip, 1, 2, 6);
-
- // Outputting two lines (because of 3-4-5 constructions (0.3,0.4,0.5)
- // which occur 4 times, the length is expected to be 2.0)
- test_one<linestring, linestring, box>("llb_2", "LINESTRING(1.7 1.6,2.3 2.4,2.9 1.6,3.5 2.4,4.1 1.6)", clip, 2, 6, 4 * 0.5);
-
-
- test_one<polygon, box, polygon>("boxring", example_box, example_ring,
- 2, 12, 1.09125);
-
- test_one<polygon, box, polygon>("boxpoly", example_box, example_polygon,
- 3, 19, 0.840166);
-
- test_one<polygon, polygon, polygon>("star_ring", example_star, example_ring,
+ test_one<Polygon, Polygon, Polygon>("star_ring", example_star, example_ring,
1, 18, 2.80983);
- test_one<polygon, polygon, polygon>("star_poly", example_star, example_polygon,
+ test_one<Polygon, Polygon, Polygon>("star_poly", example_star, example_polygon,
1, 0, // CLN: 23 points, other types: 22 point (one is merged)
2.5020508);
-
-
- test_one<polygon, box, polygon>("poly1", example_box,
- "POLYGON((3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2))",
- 2, 12, 1.09125);
-
- test_one<polygon, box, polygon>("clip_poly2", example_box,
- "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,5.3 2.5,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3))",
- 2, 12, 1.00375);
- test_one<polygon, box, polygon>("clip_poly3", example_box,
- "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 2.5,4.5 1.2,4.9 0.8,2.9 0.7,2 1.3))",
- 2, 12, 1.00375);
- test_one<polygon, box, polygon>("clip_poly4", example_box,
- "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 2.5,4.5 2.3,5.0 2.3,5.0 2.1,4.5 2.1,4.5 1.9,4.0 1.9,4.5 1.2,4.9 0.8,2.9 0.7,2 1.3))",
- 2, 16, 0.860892);
-
- test_one<polygon, box, polygon>("clip_poly5", example_box,
- "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 1.2,2.9 0.7,2 1.3))",
- 2, 11, 0.7575961);
-
- test_one<polygon, box, polygon>("clip_poly6", example_box,
- "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.0 3.0,5.0 2.0,2.9 0.7,2 1.3))",
- 2, 13, 1.0744456);
-
- test_one<polygon, box, polygon>("clip_poly7", "box(0 0, 3 3)",
- "POLYGON((2 2, 1 4, 2 4, 3 3, 2 2))", 1, 4, 0.75);
-
- test_one<polygon, polygon, polygon>("first_within_second1",
+ test_one<Polygon, Polygon, Polygon>("first_within_second1",
first_within_second[0], first_within_second[1],
1, 5, 1.0);
- test_one<polygon, polygon, polygon>("first_within_second2",
+ test_one<Polygon, Polygon, Polygon>("first_within_second2",
first_within_second[1], first_within_second[0],
1, 5, 1.0);
- test_one<polygon, polygon, polygon>("first_within_hole_of_second",
+ test_one<Polygon, Polygon, Polygon>("first_within_hole_of_second",
first_within_hole_of_second[0], first_within_hole_of_second[1],
0, 0, 0.0);
// Two forming new hole
- test_one<polygon, polygon, polygon>("new_hole",
+ test_one<Polygon, Polygon, Polygon>("new_hole",
new_hole[0], new_hole[1],
2, 10, 2.0);
// Two identical
- test_one<polygon, polygon, polygon>("identical",
+ test_one<Polygon, Polygon, Polygon>("identical",
identical[0], identical[1],
1, 5, 1.0);
// Two, inside each other, having intersections but holes are disjoint
- test_one<polygon, polygon, polygon>("intersect_holes_disjoint",
+ test_one<Polygon, Polygon, Polygon>("intersect_holes_disjoint",
intersect_holes_disjoint[0], intersect_holes_disjoint[1],
1, 15, 18.0);
// Two, inside each other, having intersections; holes separate intersections
- test_one<polygon, polygon, polygon>("intersect_holes_intersect",
+ test_one<Polygon, Polygon, Polygon>("intersect_holes_intersect",
intersect_holes_intersect[0], intersect_holes_intersect[1],
1, 14, 18.25);
- test_one<polygon, polygon, polygon>("intersect_holes_intersect_and_disjoint",
+ test_one<Polygon, Polygon, Polygon>("intersect_holes_intersect_and_disjoint",
intersect_holes_intersect_and_disjoint[0], intersect_holes_intersect_and_disjoint[1],
1, 19, 17.25);
- test_one<polygon, polygon, polygon>("intersect_holes_intersect_and_touch",
+ test_one<Polygon, Polygon, Polygon>("intersect_holes_intersect_and_touch",
intersect_holes_intersect_and_touch[0], intersect_holes_intersect_and_touch[1],
1, 23, 17.25);
- test_one<polygon, polygon, polygon>("intersect_holes_new_ring",
+ test_one<Polygon, Polygon, Polygon>("intersect_holes_new_ring",
intersect_holes_new_ring[0], intersect_holes_new_ring[1],
2, 23, 122.1039);
- test_one<polygon, polygon, polygon>("winded",
+ test_one<Polygon, Polygon, Polygon>("winded",
winded[0], winded[1],
1, 22, 40.0);
- test_one<polygon, polygon, polygon>("two_bends",
+ test_one<Polygon, Polygon, Polygon>("two_bends",
two_bends[0], two_bends[1],
1, 7, 24.0);
- test_one<polygon, polygon, polygon>("star_comb_15",
+ test_one<Polygon, Polygon, Polygon>("star_comb_15",
star_15, comb_15,
28, 150, 189.952883);
- test_one<polygon, polygon, polygon>("simplex_normal",
+ test_one<Polygon, Polygon, Polygon>("simplex_normal",
simplex_normal[0], simplex_normal[1],
1, 7, 5.47363293);
- test_one<polygon, polygon, polygon>("fitting",
+ test_one<Polygon, Polygon, Polygon>("fitting",
fitting[0], fitting[1],
0, 0, 0);
- test_one<polygon, polygon, polygon>("dist_zero",
+ test_one<Polygon, Polygon, Polygon>("dist_zero",
distance_zero[0], distance_zero[1],
1, 0 /* f: 4, other: 5 */, 0.29516139, 0.01);
- test_one<polygon, polygon, polygon>("ehd",
+ test_one<Polygon, Polygon, Polygon>("ehd",
equal_holes_disjoint[0], equal_holes_disjoint[1],
1, 20, 81 - 2 * 3 * 3 - 3 * 7);
- test_one<polygon, polygon, polygon>("only_hole_intersections1",
+ test_one<Polygon, Polygon, Polygon>("only_hole_intersections1",
only_hole_intersections[0], only_hole_intersections[1],
1, 21, 178.090909);
- test_one<polygon, polygon, polygon>("only_hole_intersection2",
+ test_one<Polygon, Polygon, Polygon>("only_hole_intersection2",
only_hole_intersections[0], only_hole_intersections[2],
1, 21, 149.090909);
- test_one<polygon, polygon, polygon>("intersect_exterior_and_interiors_winded",
+ test_one<Polygon, Polygon, Polygon>("intersect_exterior_and_interiors_winded",
intersect_exterior_and_interiors_winded[0], intersect_exterior_and_interiors_winded[1],
1, 14, 25.2166667);
- // linear
- test_one<P, linestring, linestring>("llp1", "LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", 1, 1, 0);
- test_one<P, segment, segment>("ssp1", "LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", 1, 1, 0);
- test_one<P, linestring, linestring>("llp2", "LINESTRING(0 0,1 1)", "LINESTRING(0 0,2 2)", 2, 2, 0);
-
- // polygons outputing points
- //test_one<P, polygon, polygon>("ppp1", simplex_normal[0], simplex_normal[1], 1, 7, 5.47363293);
-
-
return;
- test_one<polygon, polygon, polygon>(
+ test_one<Polygon, Polygon, Polygon>(
"polygon_pseudo_line",
- "POLYGON((0 0,0 4,4 4,4 0,0 0))",
- "POLYGON((2 -2,2 -1,2 6,2 -2))",
+ "Polygon((0 0,0 4,4 4,4 0,0 0))",
+ "Polygon((2 -2,2 -1,2 6,2 -2))",
5, 22, 1.1901714);
- test_one<polygon, polygon, polygon>(
- "reverse",
- "POLYGON((0 0,4 0,4 4,0 4,0 0))",
- "POLYGON((2 2,2 3,6 3,6 2,2 2))",
- 5, 22, 1.190171);
-
-
-
-
- /*
- REVERSED cases (should be handled/tested differently)
- test_one<polygon, polygon, polygon>(102,
- simplex_normal[0], simplex_reversed[1],
- 1, 7, 24.0);
-
- test_one<polygon, polygon, polygon>(103,
- simplex_reversed[0], simplex_normal[1],
- 1, 7, 24.0);
-
- test_one<polygon, polygon, polygon>(104,
- simplex_reversed[0], simplex_reversed[1],
- 1, 7, 24.0);
- */
-
// Icovist (submitted by Brandon during Formal Review)
// Test the FORWARD case
{
- std::string tn = string_from_type<typename boost::geometry::coordinate_type<P>::type>::name();
- test_one<polygon, polygon, polygon>("isovist",
+ std::string tn = string_from_type<typename boost::geometry::coordinate_type<Polygon>::type>::name();
+ test_one<Polygon, Polygon, Polygon>("isovist",
isovist[0], isovist[1],
1,
tn == std::string("f") ? 19 : tn == std::string("d") ? 21 : 20,
@@ -242,11 +140,100 @@
// Test the REVERSE case - does not give correct results yet
/*
- test_one<polygon, polygon, polygon>("icovist_r",
+ test_one<Polygon, Polygon, Polygon>("icovist_r",
isovist[0], isovist[2],
1, 4, 0.29516139, 0.01);
*/
+}
+
+
+template <typename P>
+void test_all()
+{
+ typedef boost::geometry::linestring<P> linestring;
+ typedef boost::geometry::polygon<P> polygon;
+ typedef boost::geometry::box<P> box;
+ typedef boost::geometry::model::segment<P> segment;
+
+ std::string clip = "box(2 2,8 8)";
+
+ // Test clockwise polygons
+ test_polygons<polygon>();
+
+ // Test counter-clockwise polygons
+ test_polygons<boost::geometry::polygon<P, std::vector, std::vector, false> >();
+
+
+ // Basic check: box/linestring, is clipping OK? should compile in any order
+ test_one<linestring, linestring, box>("llb", "LINESTRING(0 0,10 10)", clip, 1, 2, sqrt(2.0 * 6.0 * 6.0));
+ test_one<linestring, box, linestring>("lbl", clip, "LINESTRING(0 0,10 10)", 1, 2, sqrt(2.0 * 6.0 * 6.0));
+
+ // Box/segment
+ test_one<linestring, segment, box>("lsb", "LINESTRING(0 0,10 10)", clip, 1, 2, sqrt(2.0 * 6.0 * 6.0));
+ test_one<linestring, box, segment>("lbs", clip, "LINESTRING(0 0,10 10)", 1, 2, sqrt(2.0 * 6.0 * 6.0));
+
+ // Completely inside
+ test_one<linestring, linestring, box>("llbi", "LINESTRING(3 3,7 7)", clip, 1, 2, sqrt(2.0 * 4.0 * 4.0));
+
+ // Completely outside
+ test_one<linestring, linestring, box>("llbo", "LINESTRING(9 9,10 10)", clip, 0, 0, 0);
+
+ // Touching with point (-> output linestring with ONE point)
+ //std::cout << "Note: the output line is degenerate! Might be removed!" << std::endl;
+ test_one<linestring, linestring, box>("llb_touch", "LINESTRING(8 8,10 10)", clip, 1, 1, 0.0);
+
+ // Along border
+ test_one<linestring, linestring, box>("llb_along", "LINESTRING(2 2,2 8)", clip, 1, 2, 6);
+
+ // Outputting two lines (because of 3-4-5 constructions (0.3,0.4,0.5)
+ // which occur 4 times, the length is expected to be 2.0)
+ test_one<linestring, linestring, box>("llb_2", "LINESTRING(1.7 1.6,2.3 2.4,2.9 1.6,3.5 2.4,4.1 1.6)", clip, 2, 6, 4 * 0.5);
+
+
+ test_one<polygon, box, polygon>("boxring", example_box, example_ring,
+ 2, 12, 1.09125);
+
+ test_one<polygon, box, polygon>("boxpoly", example_box, example_polygon,
+ 3, 19, 0.840166);
+
+
+
+ test_one<polygon, box, polygon>("poly1", example_box,
+ "POLYGON((3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2))",
+ 2, 12, 1.09125);
+
+ test_one<polygon, box, polygon>("clip_poly2", example_box,
+ "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,5.3 2.5,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3))",
+ 2, 12, 1.00375);
+ test_one<polygon, box, polygon>("clip_poly3", example_box,
+ "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 2.5,4.5 1.2,4.9 0.8,2.9 0.7,2 1.3))",
+ 2, 12, 1.00375);
+ test_one<polygon, box, polygon>("clip_poly4", example_box,
+ "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 2.5,4.5 2.3,5.0 2.3,5.0 2.1,4.5 2.1,4.5 1.9,4.0 1.9,4.5 1.2,4.9 0.8,2.9 0.7,2 1.3))",
+ 2, 16, 0.860892);
+
+ test_one<polygon, box, polygon>("clip_poly5", example_box,
+ "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 1.2,2.9 0.7,2 1.3))",
+ 2, 11, 0.7575961);
+
+ test_one<polygon, box, polygon>("clip_poly6", example_box,
+ "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.0 3.0,5.0 2.0,2.9 0.7,2 1.3))",
+ 2, 13, 1.0744456);
+
+ test_one<polygon, box, polygon>("clip_poly7", "box(0 0, 3 3)",
+ "POLYGON((2 2, 1 4, 2 4, 3 3, 2 2))", 1, 4, 0.75);
+
+
+ // linear
+ test_one<P, linestring, linestring>("llp1", "LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", 1, 1, 0);
+ test_one<P, segment, segment>("ssp1", "LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", 1, 1, 0);
+ test_one<P, linestring, linestring>("llp2", "LINESTRING(0 0,1 1)", "LINESTRING(0 0,2 2)", 2, 2, 0);
+
+ // polygons outputing points
+ //test_one<P, polygon, polygon>("ppp1", simplex_normal[0], simplex_normal[1], 1, 7, 5.47363293);
+
+
/*
test_one<polygon, box, polygon>(99, "box(115041.10 471900.10, 118334.60 474523.40)",
@@ -292,25 +279,12 @@
-template <typename P>
-void test_ccw()
-{
- typedef boost::geometry::polygon<P, std::vector, std::vector, true> polygon;
-
- test_one<polygon, polygon, polygon>("simplex_normal",
- simplex_normal[0], simplex_normal[1],
- 1, 7, 5.47363293);
-}
-
int test_main(int, char* [])
{
test_all<boost::geometry::point_xy<float> >();
test_all<boost::geometry::point_xy<double> >();
- //test_ccw<boost::geometry::point_xy<double> >();
-
-
#if defined(HAVE_CLN)
test_all<boost::geometry::point_xy<boost::numeric_adaptor::cln_value_type> >();
#endif
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/ccw_traverse.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/ccw_traverse.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/ccw_traverse.cpp 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -18,28 +18,6 @@
namespace bg = boost::geometry;
-template <typename Vector>
-void reverse_operations(Vector& v)
-{
- using namespace bg::detail::overlay;
-
- typedef typename boost::range_value<Vector>::type item;
- BOOST_FOREACH(item& it, v)
- {
- for (int i = 0; i < 2; i++)
- {
- operation_type& op = it.operations[i].operation;
- switch(op)
- {
- case operation_none : op = operation_none; break;
- case operation_union : op = operation_intersection; break;
- case operation_intersection : op = operation_union; break;
- case operation_blocked : op = operation_blocked; break;
- case operation_continue : op = operation_continue; break;
- }
- }
- }
-}
template <typename Geometry>
inline typename bg::coordinate_type<Geometry>::type intersect(Geometry const& g1, Geometry const& g2, std::string const& name,
@@ -63,7 +41,7 @@
bool const reverse = bg::point_order<Geometry>::value == bg::counterclockwise;
if (reverse)
{
- reverse_operations(turns);
+ bg::detail::overlay::reverse_operations(turns);
}
bg::enrich_intersection_points(turns, g1, g2, side_strategy_type());
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/overlay.sln
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/overlay.sln (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/overlay.sln 2010-10-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -1,7 +1,5 @@
Microsoft Visual Studio Solution File, Format Version 9.00
# Visual C++ Express 2005
-Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "enrich_intersection_points", "enrich_intersection_points.vcproj", "{20FE798A-E4EE-4C87-A988-7317E774D28A}"
-EndProject
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "traverse", "traverse.vcproj", "{6260214E-DB6F-4934-ADF7-DD2B1666171B}"
EndProject
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "self_intersection_points", "self_intersection_points.vcproj", "{06B6DCBB-AEDA-49FA-81D9-EA8959958EFC}"
@@ -14,8 +12,6 @@
EndProject
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "assemble", "assemble.vcproj", "{306E829F-ACEC-42D5-B1D4-2531B2F56EA3}"
EndProject
-Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "split_rings", "split_rings.vcproj", "{271231F9-F7DA-4218-8538-0E9DCD688D09}"
-EndProject
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "dissolver", "dissolver.vcproj", "{6CCB145C-C682-4B9F-8672-6D04DB5C76DD}"
EndProject
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "ccw_traverse", "ccw_traverse.vcproj", "{BA789719-B2FC-405A-9258-E9E4ABCE1791}"
@@ -26,10 +22,6 @@
Release|Win32 = Release|Win32
EndGlobalSection
GlobalSection(ProjectConfigurationPlatforms) = postSolution
- {20FE798A-E4EE-4C87-A988-7317E774D28A}.Debug|Win32.ActiveCfg = Debug|Win32
- {20FE798A-E4EE-4C87-A988-7317E774D28A}.Debug|Win32.Build.0 = Debug|Win32
- {20FE798A-E4EE-4C87-A988-7317E774D28A}.Release|Win32.ActiveCfg = Release|Win32
- {20FE798A-E4EE-4C87-A988-7317E774D28A}.Release|Win32.Build.0 = Release|Win32
{6260214E-DB6F-4934-ADF7-DD2B1666171B}.Debug|Win32.ActiveCfg = Debug|Win32
{6260214E-DB6F-4934-ADF7-DD2B1666171B}.Debug|Win32.Build.0 = Debug|Win32
{6260214E-DB6F-4934-ADF7-DD2B1666171B}.Release|Win32.ActiveCfg = Release|Win32
@@ -54,10 +46,6 @@
{306E829F-ACEC-42D5-B1D4-2531B2F56EA3}.Debug|Win32.Build.0 = Debug|Win32
{306E829F-ACEC-42D5-B1D4-2531B2F56EA3}.Release|Win32.ActiveCfg = Release|Win32
{306E829F-ACEC-42D5-B1D4-2531B2F56EA3}.Release|Win32.Build.0 = Release|Win32
- {271231F9-F7DA-4218-8538-0E9DCD688D09}.Debug|Win32.ActiveCfg = Debug|Win32
- {271231F9-F7DA-4218-8538-0E9DCD688D09}.Debug|Win32.Build.0 = Debug|Win32
- {271231F9-F7DA-4218-8538-0E9DCD688D09}.Release|Win32.ActiveCfg = Release|Win32
- {271231F9-F7DA-4218-8538-0E9DCD688D09}.Release|Win32.Build.0 = Release|Win32
{6CCB145C-C682-4B9F-8672-6D04DB5C76DD}.Debug|Win32.ActiveCfg = Debug|Win32
{6CCB145C-C682-4B9F-8672-6D04DB5C76DD}.Debug|Win32.Build.0 = Debug|Win32
{6CCB145C-C682-4B9F-8672-6D04DB5C76DD}.Release|Win32.ActiveCfg = Release|Win32
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-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -16,6 +16,7 @@
#include <boost/geometry/algorithms/intersection.hpp>
#include <boost/geometry/algorithms/area.hpp>
+#include <boost/geometry/algorithms/correct.hpp>
#include <boost/geometry/algorithms/length.hpp>
#include <boost/geometry/algorithms/num_points.hpp>
#include <boost/geometry/algorithms/unique.hpp>
@@ -164,6 +165,10 @@
G2 g2;
boost::geometry::read_wkt(wkt2, g2);
+ // Reverse if necessary
+ boost::geometry::correct(g1);
+ boost::geometry::correct(g2);
+
return test_intersection<OutputType, void>(caseid, g1, g2,
expected_count, expected_point_count,
expected_length_or_area, percentage, make_unique);
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-12 06:39:09 EDT (Tue, 12 Oct 2010)
@@ -13,6 +13,7 @@
#include <algorithms/test_overlay.hpp>
#include <multi/algorithms/overlay/multi_overlay_cases.hpp>
+#include <boost/geometry/multi/algorithms/correct.hpp>
#include <boost/geometry/multi/algorithms/intersection.hpp>
#include <boost/geometry/multi/geometries/multi_point.hpp>
@@ -21,41 +22,51 @@
#include <boost/geometry/extensions/gis/io/wkt/read_wkt_multi.hpp>
-
-template <typename P>
-void test_all()
+template <typename Ring, typename Polygon, typename MultiPolygon>
+void test_areal()
{
- // 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",
+ test_one<Polygon, MultiPolygon, MultiPolygon>("simplex_multi",
case_multi_simplex[0], case_multi_simplex[1],
2, 12, 6.42);
- test_one<polygon, multi_polygon, multi_polygon>("case_multi_no_ip",
+ test_one<Polygon, MultiPolygon, MultiPolygon>("case_multi_no_ip",
case_multi_no_ip[0], case_multi_no_ip[1],
2, 8, 8.5);
- test_one<polygon, multi_polygon, multi_polygon>("case_multi_2",
+ test_one<Polygon, MultiPolygon, MultiPolygon>("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",
+ test_one<Polygon, MultiPolygon, Polygon>("simplex_multi_mp_p",
case_multi_simplex[0], case_single_simplex,
2, 12, 6.42);
- test_one<polygon, ring, multi_polygon>("simplex_multi_r_mp",
+ test_one<Polygon, Ring, MultiPolygon>("simplex_multi_r_mp",
case_single_simplex, case_multi_simplex[0],
2, 12, 6.42);
- test_one<ring, multi_polygon, polygon>("simplex_multi_mp_r",
+ test_one<Ring, MultiPolygon, Polygon>("simplex_multi_mp_r",
case_multi_simplex[0], case_single_simplex,
2, 12, 6.42);
+}
+
+
+template <typename P>
+void test_all()
+{
+ namespace bg = boost::geometry;
+
+
+ typedef bg::linear_ring<P> ring;
+ typedef bg::polygon<P> polygon;
+ typedef bg::multi_polygon<polygon> multi_polygon;
+ test_areal<ring, polygon, multi_polygon>();
+
+ typedef bg::linear_ring<P, std::vector, false> ring_ccw;
+ typedef bg::polygon<P, std::vector, std::vector, false> polygon_ccw;
+ typedef bg::multi_polygon<polygon_ccw> multi_polygon_ccw;
+ test_areal<ring_ccw, polygon_ccw, multi_polygon_ccw>();
+
+ typedef bg::linestring<P> linestring;
+ typedef bg::multi_linestring<linestring> multi_linestring;
// linear
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