diff options
Diffstat (limited to 'libs/geometry/test/algorithms/set_operations/intersection')
8 files changed, 3406 insertions, 0 deletions
diff --git a/libs/geometry/test/algorithms/set_operations/intersection/Jamfile.v2 b/libs/geometry/test/algorithms/set_operations/intersection/Jamfile.v2 new file mode 100644 index 000000000..b21302819 --- /dev/null +++ b/libs/geometry/test/algorithms/set_operations/intersection/Jamfile.v2 @@ -0,0 +1,23 @@ +# Boost.Geometry (aka GGL, Generic Geometry Library) +# +# Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +# Copyright (c) 2008-2014 Bruno Lalande, Paris, France. +# Copyright (c) 2009-2014 Mateusz Loskot, London, UK. +# +# This file was modified by Oracle on 2014. +# Modifications copyright (c) 2014, Oracle and/or its affiliates. +# +# Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +# Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +# +# 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) + +test-suite boost-geometry-algorithms-intersection + : + [ run intersection.cpp : : : <define>BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE ] + [ run intersection_linear_linear.cpp ] + [ run intersection_pl_pl.cpp ] + [ run multi_intersection.cpp : : : <define>BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE ] + ; diff --git a/libs/geometry/test/algorithms/set_operations/intersection/intersection.cpp b/libs/geometry/test/algorithms/set_operations/intersection/intersection.cpp new file mode 100644 index 000000000..e15c3ee54 --- /dev/null +++ b/libs/geometry/test/algorithms/set_operations/intersection/intersection.cpp @@ -0,0 +1,693 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) +// Unit Test + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-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) + +#include <climits> +#include <iostream> +#include <string> + +// If defined, tests are run without rescaling-to-integer or robustness policy +// Test which would fail then are disabled automatically +// #define BOOST_GEOMETRY_NO_ROBUSTNESS + +#include <boost/config.hpp> +#include <boost/core/ignore_unused.hpp> + +#include <boost/geometry/geometries/point_xy.hpp> +#include <boost/geometry/geometries/register/linestring.hpp> + +#include <boost/geometry/util/condition.hpp> +#include <boost/geometry/util/rational.hpp> + +#include "test_intersection.hpp" +#include <algorithms/test_overlay.hpp> + +#include <algorithms/overlay/overlay_cases.hpp> + +#include <test_common/test_point.hpp> +#include <test_common/with_pointer.hpp> +#include <test_geometries/custom_segment.hpp> + + +BOOST_GEOMETRY_REGISTER_LINESTRING_TEMPLATED(std::vector) + + +template <typename Polygon> +void test_areal() +{ + typedef typename bg::coordinate_type<Polygon>::type ct; + bool const ccw = bg::point_order<Polygon>::value == bg::counterclockwise; + bool const open = bg::closure<Polygon>::value == bg::open; + + test_one<Polygon, Polygon, Polygon>("simplex_with_empty_1", + simplex_normal[0], polygon_empty, + 0, 0, 0.0); + test_one<Polygon, Polygon, Polygon>("simplex_with_empty_2", + polygon_empty, simplex_normal[0], + 0, 0, 0.0); + + test_one<Polygon, Polygon, Polygon>("simplex_normal", + simplex_normal[0], simplex_normal[1], + 1, 7, 5.47363293); + 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, + 1, 0, // CLN: 23 points, other types: 22 point (one is merged) + 2.5020508); + 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", + first_within_second[1], first_within_second[0], + 1, 5, 1.0); + + 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", + new_hole[0], new_hole[1], + 2, 10, 2.0); + + // Two identical + test_one<Polygon, Polygon, Polygon>("identical", + identical[0], identical[1], + 1, 5, 1.0); + + 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); + + test_one<Polygon, Polygon, Polygon>("intersect_holes_disjoint", + intersect_holes_disjoint[0], intersect_holes_disjoint[1], + 1, 15, 18.0); + + 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", + 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", + 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", + intersect_holes_new_ring[0], intersect_holes_new_ring[1], + 2, 23, 122.1039); + + test_one<Polygon, Polygon, Polygon>("winded", + winded[0], winded[1], + 1, 22, 40.0); + + test_one<Polygon, Polygon, Polygon>("within_holes_disjoint", + within_holes_disjoint[0], within_holes_disjoint[1], + 1, 15, 23.0); + + test_one<Polygon, Polygon, Polygon>("side_side", + side_side[0], side_side[1], + 0, 0, 0.0); + + 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", + star_comb_15[0], star_comb_15[1], + 28, 150, 189.952883); + + test_one<Polygon, Polygon, Polygon>("simplex_normal", + simplex_normal[0], simplex_normal[1], + 1, 7, 5.47363293); + + test_one<Polygon, Polygon, Polygon>("distance_zero", + distance_zero[0], distance_zero[1], + 1, 0 /* f: 4, other: 5 */, 0.29516139, 0.01); + + test_one<Polygon, Polygon, Polygon>("equal_holes_disjoint", + equal_holes_disjoint[0], equal_holes_disjoint[1], + 1, 20, 81 - 2 * 3 * 3 - 3 * 7); + + 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", + only_hole_intersections[0], only_hole_intersections[2], + 1, 21, 149.090909); + + test_one<Polygon, Polygon, Polygon>("fitting", + fitting[0], fitting[1], + 0, 0, 0); + + test_one<Polygon, Polygon, Polygon>("crossed", + crossed[0], crossed[1], + 3, 0, 1.5); + + test_one<Polygon, Polygon, Polygon>("pie_2_3_23_0", + pie_2_3_23_0[0], pie_2_3_23_0[1], + 1, 4, 163292.679042133, 0.1); + + test_one<Polygon, Polygon, Polygon>("isovist", + isovist1[0], isovist1[1], + 1, 19, 88.19203, + if_typed_tt<ct>(0.01, 0.1)); + + // SQL Server gives: 88.1920416352664 + // PostGIS gives: 88.19203677911 + + test_one<Polygon, Polygon, Polygon>("geos_1", + geos_1[0], geos_1[1], + 1, -1, 3461.0214843, 0.005); // MSVC 14 reports 3461.025390625 + + test_one<Polygon, Polygon, Polygon>("geos_2", + geos_2[0], geos_2[1], + 0, 0, 0.0); + test_one<Polygon, Polygon, Polygon>("geos_3", + geos_3[0], geos_3[1], + 0, -0, 0.0); + test_one<Polygon, Polygon, Polygon>("geos_4", + geos_4[0], geos_4[1], + 1, -1, 0.08368849); + + + if ( BOOST_GEOMETRY_CONDITION(! ccw && open) ) + { + // Pointcount for ttmath/double (both 5) or float (4) + // double returns 5 (since method append_no_dups_or_spikes) + // but not for ccw/open. Those cases has to be adapted once, anyway, + // because for open always one point too much is generated... + test_one<Polygon, Polygon, Polygon>("ggl_list_20110306_javier", + ggl_list_20110306_javier[0], ggl_list_20110306_javier[1], + 1, if_typed<ct, float>(4, 5), + 0.6649875, + if_typed<ct, float>(1.0, 0.01)); + } + + test_one<Polygon, Polygon, Polygon>("ggl_list_20110307_javier", + ggl_list_20110307_javier[0], ggl_list_20110307_javier[1], + 1, 4, 0.4, 0.01); + + test_one<Polygon, Polygon, Polygon>("ggl_list_20110627_phillip", + ggl_list_20110627_phillip[0], ggl_list_20110627_phillip[1], + 1, if_typed_tt<ct>(6, 5), 11151.6618); + + test_one<Polygon, Polygon, Polygon>("ggl_list_20110716_enrico", + ggl_list_20110716_enrico[0], ggl_list_20110716_enrico[1], + 3, 16, 35723.8506317139); + + test_one<Polygon, Polygon, Polygon>("ggl_list_20131119_james", + ggl_list_20131119_james[0], ggl_list_20131119_james[1], + 1, 4, 6.6125873045, 0.1); + + test_one<Polygon, Polygon, Polygon>("ggl_list_20140223_shalabuda", + ggl_list_20140223_shalabuda[0], ggl_list_20140223_shalabuda[1], + 1, 4, 3.77106); + +#if 0 + // TODO: fix this testcase, it should give 0 but instead it gives one of the input polygons + // Mailed to the Boost.Geometry list on 2014/03/21 by 7415963@gmail.com + test_one<Polygon, Polygon, Polygon>("ggl_list_20140321_7415963", + ggl_list_20140321_7415963[0], ggl_list_20140321_7415963[1], + 0, 0, 0, 0.1); +#endif + +#if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS) + test_one<Polygon, Polygon, Polygon>("buffer_rt_f", buffer_rt_f[0], buffer_rt_f[1], + 1, 4, 0.00029437899183903937, 0.01); +#endif + + test_one<Polygon, Polygon, Polygon>("buffer_rt_g", buffer_rt_g[0], buffer_rt_g[1], + 1, 0, 2.914213562373); + +#if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS) + test_one<Polygon, Polygon, Polygon>("ticket_8254", ticket_8254[0], ticket_8254[1], + 1, 4, 3.6334e-08, 0.01); +#endif + + test_one<Polygon, Polygon, Polygon>("ticket_6958", ticket_6958[0], ticket_6958[1], + 1, 4, 4.34355e-05, 0.01); + +#if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS) + test_one<Polygon, Polygon, Polygon>("ticket_8652", ticket_8652[0], ticket_8652[1], + 1, 4, 0.0003); +#endif + + test_one<Polygon, Polygon, Polygon>("ticket_8310a", ticket_8310a[0], ticket_8310a[1], + 1, 5, 0.3843747); + test_one<Polygon, Polygon, Polygon>("ticket_8310b", ticket_8310b[0], ticket_8310b[1], + 1, 5, 0.3734379); + test_one<Polygon, Polygon, Polygon>("ticket_8310c", ticket_8310c[0], ticket_8310c[1], + 1, 5, 0.4689541); + + test_one<Polygon, Polygon, Polygon>("ticket_9081_15", + ticket_9081_15[0], ticket_9081_15[1], + 1, 4, 0.0068895780745301394); + + test_one<Polygon, Polygon, Polygon>("ticket_10108_a", + ticket_10108_a[0], ticket_10108_a[1], + 0, 0, 0.0); + test_one<Polygon, Polygon, Polygon>("ticket_10108_b", + ticket_10108_b[0], ticket_10108_b[1], + 0, 0, 0.0); + + test_one<Polygon, Polygon, Polygon>("ticket_10747_a", + ticket_10747_a[0], ticket_10747_a[1], + 1, 4, 70368744177664); + test_one<Polygon, Polygon, Polygon>("ticket_10747_b", + ticket_10747_b[0], ticket_10747_b[1], + 1, 4, 7036874417766400); + test_one<Polygon, Polygon, Polygon>("ticket_10747_c", + ticket_10747_c[0], ticket_10747_c[1], + 1, 4, 17592186044416); + test_one<Polygon, Polygon, Polygon>("ticket_10747_d", + ticket_10747_d[0], ticket_10747_d[1], + 1, 4, 703687777321); + test_one<Polygon, Polygon, Polygon>("ticket_10747_e", + ticket_10747_e[0], ticket_10747_e[1], + 1, 4, 7.0368748575710959e-15); + +#if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS) + test_one<Polygon, Polygon, Polygon>("ticket_9563", ticket_9563[0], ticket_9563[1], + 1, 8, 129.90381); +#endif + +#if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS) + test_one<Polygon, Polygon, Polygon>("buffer_mp1", buffer_mp1[0], buffer_mp1[1], + 1, 31, 2.271707796); +#endif + + test_one<Polygon, Polygon, Polygon>("buffer_mp2", buffer_mp2[0], buffer_mp2[1], + 1, 29, 0.457126); + + return; + + + 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))", + 5, 22, 1.1901714); +} + +template <typename Polygon, typename Box> +void test_areal_clip() +{ + test_one<Polygon, Box, Polygon>("boxring", example_box, example_ring, + 2, 12, 1.09125); + test_one<Polygon, Polygon, Box>("boxring2", example_ring,example_box, + 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); +} + + +template <typename Box> +void test_boxes(std::string const& wkt1, std::string const& wkt2, double expected_area, bool expected_result) +{ + Box box1, box2; + bg::read_wkt(wkt1, box1); + bg::read_wkt(wkt2, box2); + + Box box_out; + bool detected = bg::intersection(box1, box2, box_out); + typename bg::default_area_result<Box>::type area = bg::area(box_out); + + BOOST_CHECK_EQUAL(detected, expected_result); + if (detected && expected_result) + { + BOOST_CHECK_CLOSE(area, expected_area, 0.01); + } +} + +template <typename P> +void test_point_output() +{ + typedef bg::model::linestring<P> linestring; + typedef bg::model::polygon<P> polygon; + typedef bg::model::box<P> box; + //typedef bg::model::segment<P> segment; + + test_point_output<polygon, polygon>(simplex_normal[0], simplex_normal[1], 6); + test_point_output<box, polygon>("box(1 1,6 4)", simplex_normal[0], 4); + test_point_output<linestring, polygon>("linestring(0 2,6 2)", simplex_normal[0], 2); + // NYI because of sectionize: + // test_point_output<segment, polygon>("linestring(0 2,6 2)", simplex_normal[0], 2); + // NYI because needs special treatment: + // test_point_output<box, box>("box(0 0,4 4)", "box(2 2,6 6)", 2); +} + + +template <typename Polygon, typename LineString> +void test_areal_linear() +{ + std::string const poly_simplex = "POLYGON((1 1,1 3,3 3,3 1,1 1))"; + + test_one_lp<LineString, Polygon, LineString>("simplex", poly_simplex, "LINESTRING(0 2,4 2)", 1, 2, 2.0); + test_one_lp<LineString, Polygon, LineString>("case2", poly_simplex, "LINESTRING(0 1,4 3)", 1, 2, sqrt(5.0)); + test_one_lp<LineString, Polygon, LineString>("case3", "POLYGON((2 0,2 5,5 5,5 0,2 0))", "LINESTRING(0 1,1 2,3 2,4 3,6 3,7 4)", 1, 4, 2 + sqrt(2.0)); + test_one_lp<LineString, Polygon, LineString>("case4", "POLYGON((0 0,0 4,2 4,2 0,0 0))", "LINESTRING(1 1,3 2,1 3)", 2, 4, sqrt(5.0)); + + test_one_lp<LineString, Polygon, LineString>("case5", poly_simplex, "LINESTRING(0 1,3 4)", 1, 2, sqrt(2.0)); + test_one_lp<LineString, Polygon, LineString>("case6", "POLYGON((2 0,2 4,3 4,3 1,4 1,4 3,5 3,5 1,6 1,6 3,7 3,7 1,8 1,8 3,9 3,9 0,2 0))", "LINESTRING(1 1,10 3)", 4, 8, + // Pieces are 1 x 2/9: + 4.0 * sqrt(1.0 + 4.0/81.0)); + test_one_lp<LineString, Polygon, LineString>("case7", poly_simplex, "LINESTRING(1.5 1.5,2.5 2.5)", 1, 2, sqrt(2.0)); + test_one_lp<LineString, Polygon, LineString>("case8", poly_simplex, "LINESTRING(1 0,2 0)", 0, 0, 0.0); + + std::string const poly_9 = "POLYGON((1 1,1 4,4 4,4 1,1 1))"; + test_one_lp<LineString, Polygon, LineString>("case9", poly_9, "LINESTRING(0 1,1 2,2 2)", 1, 2, 1.0); + test_one_lp<LineString, Polygon, LineString>("case10", poly_9, "LINESTRING(0 1,1 2,0 2)", 0, 0, 0.0); + test_one_lp<LineString, Polygon, LineString>("case11", poly_9, "LINESTRING(2 2,4 2,3 3)", 1, 3, 2.0 + sqrt(2.0)); + test_one_lp<LineString, Polygon, LineString>("case12", poly_9, "LINESTRING(2 3,4 4,5 6)", 1, 2, sqrt(5.0)); + + test_one_lp<LineString, Polygon, LineString>("case13", poly_9, "LINESTRING(3 2,4 4,2 3)", 1, 3, 2.0 * sqrt(5.0)); + test_one_lp<LineString, Polygon, LineString>("case14", poly_9, "LINESTRING(5 6,4 4,6 5)", 0, 0, 0.0); + test_one_lp<LineString, Polygon, LineString>("case15", poly_9, "LINESTRING(0 2,1 2,1 3,0 3)", 1, 2, 1.0); + test_one_lp<LineString, Polygon, LineString>("case16", poly_9, "LINESTRING(2 2,1 2,1 3,2 3)", 1, 4, 3.0); + + std::string const angly = "LINESTRING(2 2,2 1,4 1,4 2,5 2,5 3,4 3,4 4,5 4,3 6,3 5,2 5,2 6,0 4)"; + // PROPERTIES CHANGED BY switch_to_integer + // TODO test_one_lp<LineString, Polygon, LineString>("case17", "POLYGON((1 1,1 5,4 5,4 1,1 1))", angly, 3, 8, 6.0); + test_one_lp<LineString, Polygon, LineString>("case18", "POLYGON((1 1,1 5,5 5,5 1,1 1))", angly, 2, 12, 10.0 + sqrt(2.0)); + test_one_lp<LineString, Polygon, LineString>("case19", poly_9, "LINESTRING(1 2,1 3,0 3)", 1, 2, 1.0); + test_one_lp<LineString, Polygon, LineString>("case20", poly_9, "LINESTRING(1 2,1 3,2 3)", 1, 3, 2.0); + + // PROPERTIES CHANGED BY switch_to_integer + // TODO test_one_lp<LineString, Polygon, LineString>("case21", poly_9, "LINESTRING(1 2,1 4,4 4,4 1,2 1,2 2)", 1, 6, 11.0); + + // Compile test - arguments in any order: + test_one<LineString, Polygon, LineString>("simplex", poly_simplex, "LINESTRING(0 2,4 2)", 1, 2, 2.0); + test_one<LineString, LineString, Polygon>("simplex", "LINESTRING(0 2,4 2)", poly_simplex, 1, 2, 2.0); + + typedef typename bg::point_type<Polygon>::type Point; + test_one<LineString, bg::model::ring<Point>, LineString>("simplex", poly_simplex, "LINESTRING(0 2,4 2)", 1, 2, 2.0); + +} + +template <typename P> +void test_all() +{ + typedef bg::model::linestring<P> linestring; + typedef bg::model::polygon<P> polygon; + typedef bg::model::box<P> box; + typedef bg::model::segment<P> segment; + + typedef bg::model::polygon<P, false> polygon_ccw; + typedef bg::model::polygon<P, true, false> polygon_open; + typedef bg::model::polygon<P, false, false> polygon_ccw_open; + boost::ignore_unused<polygon_ccw, polygon_open, polygon_ccw_open>(); + + std::string clip = "box(2 2,8 8)"; + + test_areal_linear<polygon, linestring>(); +#if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE) + test_areal_linear<polygon_open, linestring>(); + test_areal_linear<polygon_ccw, linestring>(); + test_areal_linear<polygon_ccw_open, linestring>(); +#endif + + // Test polygons clockwise and counter clockwise + test_areal<polygon>(); + +#if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE) + test_areal<polygon_ccw>(); + test_areal<polygon_open>(); + test_areal<polygon_ccw_open>(); +#endif + + test_areal_clip<polygon, box>(); +#if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE) + test_areal_clip<polygon_ccw, box>(); +#endif + +#if defined(TEST_FAIL_DIFFERENT_ORIENTATIONS) + // Should NOT compile + // NOTE: this can probably be relaxed later on. + test_one<polygon, polygon_ccw, polygon>("simplex_normal", + simplex_normal[0], simplex_normal[1], + 1, 7, 5.47363293); + // Output ccw, nyi (should be just reversing afterwards) + test_one<polygon, polygon, polygon_ccw>("simplex_normal", + simplex_normal[0], simplex_normal[1], + 1, 7, 5.47363293); +#endif + + // 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); + + // 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_boxes<box>("box(2 2,8 8)", "box(4 4,10 10)", 16, true); + test_boxes<box>("box(2 2,8 7)", "box(4 4,10 10)", 12, true); + test_boxes<box>("box(2 2,8 7)", "box(14 4,20 10)", 0, false); + test_boxes<box>("box(2 2,4 4)", "box(4 4,8 8)", 0, true); + + test_point_output<P>(); + + + /* + test_one<polygon, box, polygon>(99, "box(115041.10 471900.10, 118334.60 474523.40)", + "POLYGON ((115483.40 474533.40, 116549.40 474059.20, 117199.90 473762.50, 117204.90 473659.50, 118339.40 472796.90, 118334.50 472757.90, 118315.10 472604.00, 118344.60 472520.90, 118277.90 472419.10, 118071.40 472536.80, 118071.40 472536.80, 117943.10 472287.70, 117744.90 472248.40, 117708.00 472034.50, 117481.90 472056.90, 117481.90 472056.90, 117272.30 471890.10, 117077.90 472161.20, 116146.60 473054.50, 115031.10 473603.30, 115483.40 474533.40))", + 1, 26, 3727690.74); + */ + +} + +void test_pointer_version() +{ + std::vector<test::test_point_xy*> ln; + test::test_point_xy* p; + p = new test::test_point_xy; p->x = 0; p->y = 0; ln.push_back(p); + p = new test::test_point_xy; p->x = 10; p->y = 10; ln.push_back(p); + + bg::model::box<bg::model::d2::point_xy<double> > box; + bg::assign_values(box, 2, 2, 8, 8); + + typedef bg::model::linestring<bg::model::d2::point_xy<double> > output_type; + std::vector<output_type> clip; + bg::detail::intersection::intersection_insert<output_type>(box, ln, std::back_inserter(clip)); + + double length = 0; + int n = 0; + for (std::vector<output_type>::const_iterator it = clip.begin(); + it != clip.end(); ++it) + { + length += bg::length(*it); + n += bg::num_points(*it); + } + + BOOST_CHECK_EQUAL(clip.size(), 1u); + BOOST_CHECK_EQUAL(n, 2); + BOOST_CHECK_CLOSE(length, sqrt(2.0 * 6.0 * 6.0), 0.001); + + for (unsigned int i = 0; i < ln.size(); i++) + { + delete ln[i]; + } +} + + +template <typename P> +void test_exception() +{ + typedef bg::model::polygon<P> polygon; + + try + { + // Define polygon with a spike (= invalid) + std::string spike = "POLYGON((0 0,0 4,2 4,2 6,2 4,4 4,4 0,0 0))"; + + test_one<polygon, polygon, polygon>("with_spike", + simplex_normal[0], spike, + 0, 0, 0); + } + catch(bg::overlay_invalid_input_exception const& ) + { + return; + } + BOOST_CHECK_MESSAGE(false, "No exception thrown"); +} + +template <typename Point> +void test_rational() +{ + typedef bg::model::polygon<Point> polygon; + test_one<polygon, polygon, polygon>("simplex_normal", + simplex_normal[0], simplex_normal[1], + 1, 7, 5.47363293); +} + + +template <typename P> +void test_boxes_per_d(P const& min1, P const& max1, P const& min2, P const& max2, bool expected_result) +{ + typedef bg::model::box<P> box; + + box box_out; + bool detected = bg::intersection(box(min1, max1), box(min2, max2), box_out); + + BOOST_CHECK_EQUAL(detected, expected_result); + if ( detected && expected_result ) + { + BOOST_CHECK( bg::equals(box_out, box(min2,max1)) ); + } +} + +template <typename CoordinateType> +void test_boxes_nd() +{ + typedef bg::model::point<CoordinateType, 1, bg::cs::cartesian> p1; + typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> p2; + typedef bg::model::point<CoordinateType, 3, bg::cs::cartesian> p3; + + test_boxes_per_d(p1(0), p1(5), p1(3), p1(6), true); + test_boxes_per_d(p2(0,0), p2(5,5), p2(3,3), p2(6,6), true); + test_boxes_per_d(p3(0,0,0), p3(5,5,5), p3(3,3,3), p3(6,6,6), true); +} + +template <typename CoordinateType> +void test_ticket_10868(std::string const& wkt_out) +{ + typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type; + typedef bg::model::polygon + < + point_type, /*ClockWise*/false, /*Closed*/false + > polygon_type; + typedef bg::model::multi_polygon<polygon_type> multipolygon_type; + + polygon_type polygon1; + bg::read_wkt(ticket_10868[0], polygon1); + polygon_type polygon2; + bg::read_wkt(ticket_10868[1], polygon2); + + multipolygon_type multipolygon_out; + bg::intersection(polygon1, polygon2, multipolygon_out); + std::stringstream stream; + stream << bg::wkt(multipolygon_out); + + BOOST_CHECK_EQUAL(stream.str(), wkt_out); + + test_one<polygon_type, polygon_type, polygon_type>("ticket_10868", + ticket_10868[0], ticket_10868[1], + 1, 7, 20266195244586); +} + +int test_main(int, char* []) +{ + test_all<bg::model::d2::point_xy<double> >(); + +#if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE) + test_all<bg::model::d2::point_xy<float> >(); + +#if defined(HAVE_TTMATH) + std::cout << "Testing TTMATH" << std::endl; + test_all<bg::model::d2::point_xy<ttmath_big> >(); +#endif + +#endif + + test_exception<bg::model::d2::point_xy<double> >(); + test_pointer_version(); +#if ! defined(BOOST_GEOMETRY_RESCALE_TO_ROBUST) + test_rational<bg::model::d2::point_xy<boost::rational<int> > >(); +#endif + + test_boxes_nd<double>(); + +#ifdef BOOST_GEOMETRY_TEST_INCLUDE_FAILING_TESTS + // ticket #10868 still fails for 32-bit integers + test_ticket_10868<int32_t>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))"); + +#if !defined(BOOST_NO_INT64) || defined(BOOST_HAS_INT64_T) || defined(BOOST_HAS_MS_INT64) + test_ticket_10868<int64_t>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))"); +#endif + + if (BOOST_GEOMETRY_CONDITION(sizeof(long) * CHAR_BIT >= 64)) + { + test_ticket_10868<long>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))"); + } + +#if defined(BOOST_HAS_LONG_LONG) + test_ticket_10868<boost::long_long_type>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))"); +#endif +#endif + + return 0; +} diff --git a/libs/geometry/test/algorithms/set_operations/intersection/intersection_linear_linear.cpp b/libs/geometry/test/algorithms/set_operations/intersection/intersection_linear_linear.cpp new file mode 100644 index 000000000..0102edc5c --- /dev/null +++ b/libs/geometry/test/algorithms/set_operations/intersection/intersection_linear_linear.cpp @@ -0,0 +1,1617 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014-2015, Oracle and/or its affiliates. + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +#include <iostream> + +#ifndef BOOST_TEST_MODULE +#define BOOST_TEST_MODULE test_intersection_linear_linear +#endif + +#ifdef BOOST_GEOMETRY_TEST_DEBUG +#define BOOST_GEOMETRY_DEBUG_TURNS +#define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER +#endif + +#include <boost/test/included/unit_test.hpp> + +#include "test_intersection_linear_linear.hpp" + +#include <boost/geometry/geometries/linestring.hpp> +#include <boost/geometry/multi/geometries/multi_linestring.hpp> +#include <boost/geometry/algorithms/intersection.hpp> + +typedef bg::model::point<double,2,bg::cs::cartesian> point_type; +typedef bg::model::segment<point_type> segment_type; +typedef bg::model::linestring<point_type> linestring_type; +typedef bg::model::multi_linestring<linestring_type> multi_linestring_type; + + + +//=========================================================================== +//=========================================================================== +//=========================================================================== + + +BOOST_AUTO_TEST_CASE( test_intersection_linestring_linestring ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** LINESTRING / LINESTRING INTERSECTION ***" << std::endl; + std::cout << std::endl; +#endif + + typedef linestring_type L; + typedef multi_linestring_type ML; + + typedef test_intersection_of_geometries<L, L, ML> tester; + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 1,2 1,3 2)"), + from_wkt<L>("LINESTRING(0 2,1 1,2 1,3 0)"), + from_wkt<ML>("MULTILINESTRING((1 1,2 1))"), + "lli00"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,5 0)"), + from_wkt<L>("LINESTRING(3 0,4 0)"), + from_wkt<ML>("MULTILINESTRING((3 0,4 0))"), + "lli01"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,4 0)"), + from_wkt<L>("LINESTRING(3 0,6 0)"), + from_wkt<ML>("MULTILINESTRING((3 0,4 0))"), + "lli01-2"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,6 0)"), + from_wkt<L>("LINESTRING(0 0,4 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,4 0))"), + "lli01-4"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,20 0)"), + from_wkt<L>("LINESTRING(0 0,1 1,2 0,3 1,4 0,5 0,6 1,7 -1,8 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((4 0,5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(2 0),(4 0,5 0),(6.5 0),(8 0))"), +#endif + "lli01-6"); + + tester::apply + (from_wkt<L>("LINESTRING(-20 0,20 0)"), + from_wkt<L>("LINESTRING(0 0,1 1,2 0,3 1,4 0,5 0,6 1,7 -1,8 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((4 0,5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(2 0),(4 0,5 0),(6.5 0),(8 0))"), +#endif + "lli01-7"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,4 0)"), + from_wkt<L>("LINESTRING(2 0,4 0)"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0))"), + "lli01-8"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,2 0)"), + from_wkt<L>("LINESTRING(4 0,5 0)"), + from_wkt<ML>("MULTILINESTRING()"), + "lli01-10"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,2 0)"), + from_wkt<L>("LINESTRING(2 0,5 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((2 0))"), +#endif + "lli01-11"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,4 0)"), + from_wkt<L>("LINESTRING(3 0,5 0)"), + from_wkt<ML>("MULTILINESTRING((3 0,4 0))"), + "lli01-11a"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,4 0)"), + from_wkt<L>("LINESTRING(3 0,4 0,5 0)"), + from_wkt<ML>("MULTILINESTRING((3 0,4 0))"), + "lli01-11b"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,5 0,10 0)"), + from_wkt<L>("LINESTRING(2 0,6 0,8 0)"), + from_wkt<ML>("MULTILINESTRING((2 0,5 0,8 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,6 0,8 0))"), + "lli01-11c"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,6 0)"), + from_wkt<L>("LINESTRING(2 0,4 0,5 0)"), + from_wkt<ML>("MULTILINESTRING((2 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0,5 0))"), + "lli01-12"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,5 5,10 5,15 0)"), + from_wkt<L>("LINESTRING(-1 6,0 5,15 5)"), + from_wkt<ML>("MULTILINESTRING((5 5,10 5))"), + "lli02"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0)"), + from_wkt<L>("LINESTRING(-1 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0))"), + "lli03"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,5 5,10 5,15 0,20 0)"), + from_wkt<L>("LINESTRING(-1 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0))"), + "lli04"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,25 1)"), + from_wkt<L>("LINESTRING(-1 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0)(15 0,20 0))"), + "lli05"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0)"), + from_wkt<L>("LINESTRING(-1 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,30 0))"), + "lli05-1"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"), + from_wkt<L>("LINESTRING(-1 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,30 0))"), + "lli06"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"), + from_wkt<L>("LINESTRING(-1 0,25 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,25 0,30 0))"), + "lli07"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"), + from_wkt<L>("LINESTRING(-1 0,19 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,19 0,30 0))"), + "lli08"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0,31 1)"), + from_wkt<L>("LINESTRING(-1 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,30 0))"), + "lli09"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0,31 1)"), + from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 1,3 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,30 0))"), + "lli10"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,4 0,5 5,10 5,15 0,20 0,\ + 30 0,31 1)"), + from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 0,2.5 1,3 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0),(3 0,4 0),\ + (15 0,20 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0),(3 0,4 0),\ + (15 0,30 0))"), + "lli11"); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,4 0,5 5,10 5,15 0,31 0)"), + from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 0,2.5 1,3 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0),\ + (3 0,4 0),(15 0,30 0))"), + "lli11-1"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,2 0,3 1)"), + from_wkt<L>("LINESTRING(0 0,2 0,3 1)"), + from_wkt<ML>("MULTILINESTRING((0 0,2 0,3 1))"), + "lli12"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,2 0,3 1)"), + from_wkt<L>("LINESTRING(3 1,2 0,0 0)"), + from_wkt<ML>("MULTILINESTRING((0 0,2 0,3 1))"), + from_wkt<ML>("MULTILINESTRING((3 1,2 0,0 0))"), + "lli12-1"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 5,4 0)"), + from_wkt<L>("LINESTRING(1 0,2 1,3 5,4 0,5 10)"), + from_wkt<ML>("MULTILINESTRING((1 0,2 1,3 5,4 0))"), + "lli13"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,2 0,2.5 0,3 1)"), + from_wkt<L>("LINESTRING(0 0,2 0,2.5 0,3 1)"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0,2.5 0,3 1))"), + from_wkt<ML>("MULTILINESTRING((0 0,2 0,2.5 0,3 1))"), + "lli14"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 5,4 0)"), + from_wkt<L>("LINESTRING(1 0,2 1,3 5)"), + from_wkt<ML>("MULTILINESTRING((1 0,2 1,3 5))"), + "lli15"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 2)"), + from_wkt<L>("LINESTRING(0.5 0,1 0,3 2,4 5)"), + from_wkt<ML>("MULTILINESTRING((0.5 0,1 0,2 1,3 2))"), + from_wkt<ML>("MULTILINESTRING((0.5 0,1 0,3 2))"), + "lli16"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 2)"), + from_wkt<L>("LINESTRING(4 5,3 2,1 0,0.5 0)"), + from_wkt<ML>("MULTILINESTRING((0.5 0,1 0,2 1,3 2))"), + from_wkt<ML>("MULTILINESTRING((0.5 0,1 0,3 2))"), + "lli16-r"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,10 0,20 1,30 1)"), + from_wkt<L>("LINESTRING(1 1,2 0,3 1,20 1,25 1)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((20 1,25 1))"), +#else + from_wkt<ML>("MULTILINESTRING((2 0),(20 1,25 1))"), +#endif + "lli17"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,10 0,20 1,21 0,30 0)"), + from_wkt<L>("LINESTRING(1 1,2 0,3 1,20 1,25 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((2 0),(20 1),(25 0))"), +#endif + "lli18"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 1)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0))"), +#endif + "lli19"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(5 1,4 0,4 1,20 1,5 0,1 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0))"), +#endif + "lli19-r"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0))"), +#endif + "lli19a"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(4 0,4 1,20 1,5 0,1 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0))"), +#endif + "lli19a-r"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0)"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,5 0))"), + "lli19b"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0,6 1)"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,5 0))"), + "lli19c"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,3 0)"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,3 0))"), + "lli19d"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,3 0,3 1)"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,3 0))"), + "lli19e"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0,5 1)"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,5 0))"), + "lli19f"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(5 1,5 0,4 0,4 1,20 1,5 0,1 0)"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,4 0),(5 0,1 0))"), + "lli19f-r"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,5 0,5 1)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(5 0))"), +#endif + "lli19g"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<L>("LINESTRING(5 1,5 0,4 1,20 1,5 0,1 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0),(5 0))"), +#endif + "lli19g-r"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0,30 30,10 30,10 -10,15 0,40 0)"), + from_wkt<L>("LINESTRING(5 5,10 0,10 30,20 0,25 0,25 25,50 0,35 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((20 0,25 0),(10 30,10 0),\ + (35 0,40 0),(20 0,25 0))"), + from_wkt<ML>("MULTILINESTRING((20 0,25 0),(10 0,10 30),\ + (40 0,35 0))"), +#else + from_wkt<ML>("MULTILINESTRING((10 0),(20 0,25 0),(10 30,10 0),\ + (30 20),(35 0,40 0),(20 0,25 0))"), + from_wkt<ML>("MULTILINESTRING((10 0),(20 0,25 0),(10 0,10 30),\ + (30 20),(40 0,35 0))"), +#endif + "lli20"); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0,30 30,10 30,10 -10,15 0,40 0)"), + from_wkt<L>("LINESTRING(5 5,10 0,10 30,20 0,25 0,25 25,50 0,15 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((15 0,30 0),(10 30,10 0),\ + (15 0,40 0))"), + from_wkt<ML>("MULTILINESTRING((10 0,10 30),(20 0,25 0),(40 0,15 0))"), +#else + from_wkt<ML>("MULTILINESTRING((10 0),(15 0,30 0),(10 30,10 0),\ + (30 20),(15 0,40 0))"), + from_wkt<ML>("MULTILINESTRING((10 0),(10 0,10 30),(20 0,25 0),\ + (30 20),(40 0,15 0))"), +#endif + "lli20a"); + + + tester::apply + (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"), + from_wkt<L>("LINESTRING(2 2,5 -1,15 2,18 0,20 0)"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((18 0,19 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((18 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((4 0),(8.33333333333333333 0),\ + (18 0,19 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((4 0),(8.33333333333333333 0),\ + (18 0,20 0))"), +#endif + "lli21" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,10 0)"), + from_wkt<L>("LINESTRING(1 0,4 0,2 1,5 1,4 0,8 0)"), + from_wkt<ML>("MULTILINESTRING((1 0,4 0),(4 0,8 0))"), + "lli22" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,10 0)"), + from_wkt<L>("LINESTRING(4 0,5 0,5 1,1 1,1 0,4 0)"), + from_wkt<ML>("MULTILINESTRING((1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,4 0),(4 0,5 0))"), + "lli23" + ); + + // the following two tests have been discussed with by Adam + tester::apply + (from_wkt<L>("LINESTRING(1 0,1 1,2 1)"), + from_wkt<L>("LINESTRING(2 1,1 1,1 0)"), + from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"), + "lli24" + ); + + tester::apply + (from_wkt<L>("LINESTRING(1 0,1 1,2 1)"), + from_wkt<L>("LINESTRING(1 2,1 1,1 0)"), + from_wkt<ML>("MULTILINESTRING((1 0,1 1))"), + "lli25" + ); +} + + + + +BOOST_AUTO_TEST_CASE( test_intersection_linestring_multilinestring ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** LINESTRING / MULTILINESTRING INTERSECTION ***" + << std::endl; + std::cout << std::endl; +#endif + + typedef linestring_type L; + typedef multi_linestring_type ML; + + typedef test_intersection_of_geometries<L, ML, ML> tester; + + // the inertsection code automatically reverses the order of the + // geometries according to the geometry IDs. + // all calls below are actually reversed, and internally the + // intersection of the linestring with the multi-linestring is + // computed. + + // disjoint linestrings + tester::apply + (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"), + from_wkt<ML>("MULTILINESTRING((1 1,2 2,4 3),(1 1,2 2,5 3))"), + from_wkt<ML>("MULTILINESTRING()"), + "lmli01" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"), + from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,4 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0))"), + "lmli02" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"), + from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,5 0))"), + "lmli03" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"), + from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0))"), + "lmli04" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,101 0)"), + from_wkt<ML>("MULTILINESTRING((-1 -1,1 0,101 0,200 -1))"), + from_wkt<ML>("MULTILINESTRING((1 0,101 0))"), + "lmli07" + ); + + tester::apply + (from_wkt<L>("LINESTRING(-1 1,0 0,101 0)"), + from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\ + (19 -1,20 0,101 0,200 -1))"), + from_wkt<ML>("MULTILINESTRING((0 0,101 0))"), + "lmli07a" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,101 0)"), + from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\ + (19 -1,20 0,101 0,200 -1))"), + from_wkt<ML>("MULTILINESTRING((0 0,101 0))"), + "lmli07b" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,101 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0),\ + (-1 -1,1 0,101 0,200 -1))"), + from_wkt<ML>("MULTILINESTRING((1 0,101 0))"), + "lmli08" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,2 0.5,3 0,101 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0.5),\ + (-1 -1,1 0,101 0,200 -1))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((3 0,101 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0),(2 0.5),(3 0,101 0))"), +#endif + "lmli09" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,1 0,1.5 0,2 0.5,3 0,101 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 1,1 0,2 0.5),\ + (-1 -1,1 0,101 0,200 -1))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,1.5 0),(3 0,101 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0),(2 0.5),(1 0,1.5 0),(3 0,101 0))"), +#endif + "lmli10" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,20 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (1 1,2 0,18 0,19 1),(2 1,3 0,17 0,18 1),\ + (3 1,4 0,16 0,17 1))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + "lmli12" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,20 0)"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0,20 1),\ + (2 0,18 0,19 1),(3 0,17 0,18 1),\ + (4 0,16 0,17 1))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + "lmli13" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,20 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1,19 1,18 0,2 0,\ + 1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + "lmli14" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,20 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,4 2,6 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + "lmli15" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,20 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (6 0,4 2,2 2))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + "lmli15a" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,20 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,4 2,5 0,6 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + "lmli16" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,20 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (6 0,5 0,4 2,2 2))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + "lmli16a" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,4 0,5 2,20 2,25 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(25 0))"), +#endif + "lmli17" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,4 0,5 2,20 2,25 0,26 2))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(25 0))"), +#endif + "lmli17a" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,5 -1,15 2,18 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + "lmli18" + ); + + tester::apply + (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,5 -1,15 2,18 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,18 0,19 0))"), + "lmli18a" + ); +} + + + + + + +#ifndef BOOST_GEOMETRY_TEST_NO_DEGENERATE +BOOST_AUTO_TEST_CASE( test_intersection_l_ml_degenerate ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** LINESTRING / MULTILINESTRING INTERSECTION" + << " (DEGENERATE) ***" + << std::endl; + std::cout << std::endl; +#endif + + typedef linestring_type L; + typedef multi_linestring_type ML; + + typedef test_intersection_of_geometries<L, ML, ML> tester; + + // the following test cases concern linestrings with duplicate + // points and possibly linestrings with zero length. + + // no unique: (3 0) appears twice + tester::apply + (from_wkt<L>("LINESTRING(0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (4 0,4 10,4 10))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),(4 0),\ + (5 0,18 0,19 0,20 0))"), +#endif + "lmli20a" + ); + + // no unique: (3 0) appears twice + tester::apply + (from_wkt<L>("LINESTRING(0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (4 0,4 0,4 10,4 10))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),(4 0),\ + (5 0,18 0,19 0,20 0))"), +#endif + "lmli20b" + ); + + // no unique: (3 0) appears twice + tester::apply + (from_wkt<L>("LINESTRING(0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (30 0,30 0,30 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\ + (5 0,18 0,19 0,20 0),(30 0))"), +#endif + "lmli20c" + ); + + // no unique: (3 0) appears twice + tester::apply + (from_wkt<L>("LINESTRING(0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0)"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (30 0,30 0,31 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\ + (5 0,18 0,19 0,20 0),(30 0))"), +#endif + "lmli20d" + ); +} +#endif // BOOST_GEOMETRY_TEST_NO_DEGENERATE + + + + +BOOST_AUTO_TEST_CASE( test_intersection_multilinestring_linestring ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** MULTILINESTRING / LINESTRING INTERSECTION ***" + << std::endl; + std::cout << std::endl; +#endif + + typedef linestring_type L; + typedef multi_linestring_type ML; + + typedef test_intersection_of_geometries<ML, L, ML> tester; + + // the intersection code automatically reverses the order of the + // geometries according to the geometry IDs. + // all calls below are actually reversed, and internally the + // intersection of the linestring with the multi-linestring is + // computed. + + // disjoint linestrings + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"), + from_wkt<L>("LINESTRING(1 1,2 2,4 3)"), + from_wkt<ML>("MULTILINESTRING()"), + "mlli01" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"), + from_wkt<L>("LINESTRING(1 1,2 0,4 0)"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0))"), + "mlli02" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"), + from_wkt<L>("LINESTRING(-1 -1,1 0,101 0,200 -1)"), + from_wkt<ML>("MULTILINESTRING((1 0,101 0))"), + "mlli03" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"), + from_wkt<L>("LINESTRING(0 1,1 0,19 0,20 1,19 1,18 0,2 0,\ + 1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1)"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(18 0,2 0),\ + (3 0,17 0),(16 0,4 0))"), + "mlli04" + ); +} + + + + + + +BOOST_AUTO_TEST_CASE( test_intersection_multilinestring_multilinestring ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** MULTILINESTRING / MULTILINESTRING INTERSECTION ***" + << std::endl; + std::cout << std::endl; +#endif + + typedef multi_linestring_type ML; + + typedef test_intersection_of_geometries<ML, ML, ML> tester; + + // disjoint linestrings + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"), + from_wkt<ML>("MULTILINESTRING((1 1,2 2,4 3),(1 1,2 2,5 3))"), + from_wkt<ML>("MULTILINESTRING()"), + "mlmli01" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"), + from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,4 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0),(2 0,4 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0),(3 0,4 0))"), + "mlmli02" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"), + from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,5 0),(2 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0),(3 0,5 0))"), + "mlmli03" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"), + from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0),(2 0,4 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0))"), + "mlmli04" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0),\ + (10 10,20 10,30 20))"), + from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),\ + (10 20,15 10,25 10,30 15))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0),(2 0,4 0),(15 10,20 10))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0),(15 10,20 10))"), + "mlmli05" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 10),(1 0,7 0),\ + (10 10,20 10,30 20))"), + from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),\ + (-1 -1,0 0,9 0,11 10,12 10,13 3,14 4,15 5),\ + (10 20,15 10,25 10,30 15))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((0 0,9 0),(13 3,15 5),\ + (1 0,7 0),(11 10,12 10),(15 10,20 10))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0),(0 0,9 0),(13 3,14 4,15 5),\ + (11 10,12 10),(15 10,20 10))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0,9 0),(13 3,15 5),(20 10),\ + (1 0,7 0),(11 10,12 10),(15 10,20 10))"), + from_wkt<ML>("MULTILINESTRING((2 0,4 0),(0 0,9 0),(13 3,14 4,15 5),\ + (11 10,12 10),(15 10,20 10))"), +#endif + "mlmli06" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((-1 -1,1 0,101 0,200 -1))"), + from_wkt<ML>("MULTILINESTRING((1 0,101 0))"), + "mlmli07" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((-1 1,0 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\ + (19 -1,20 0,101 0,200 -1))"), + from_wkt<ML>("MULTILINESTRING((0 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,50 0),(20 0,101 0))"), + "mlmli07a" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\ + (19 -1,20 0,101 0,200 -1))"), + from_wkt<ML>("MULTILINESTRING((0 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,50 0),(20 0,101 0))"), + "mlmli07b" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0),\ + (-1 -1,1 0,101 0,200 -1))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,101 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((2 0),(1 0,101 0))"), +#endif + "mlmli08" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0.5,3 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0.5),\ + (-1 -1,1 0,101 0,200 -1))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((3 0,101 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0),(2 0.5),(3 0,101 0))"), +#endif + "mlmli09" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,1 0,1.5 0,2 0.5,3 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 1,1 0,2 0.5),\ + (-1 -1,1 0,101 0,200 -1))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,1.5 0),(3 0,101 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,1.5 0),(2 0.5),(3 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((1 0),(1 0,1.5 0),(2 0.5),(3 0,101 0))"), +#endif + "mlmli10" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,1 1,100 1,101 0),\ + (0 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1,3 0,4 0,5 1,6 1,\ + 7 0,8 0,9 1,10 1,11 0,12 0,13 1,14 1,15 0),\ + (-1 -1,1 0,101 0,200 -1))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 1,2 1),(5 1,6 1),(9 1,10 1),\ + (13 1,14 1),(1 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((1 1,2 1),(5 1,6 1),(9 1,10 1),\ + (13 1,14 1),(3 0,4 0),(7 0,8 0),(11 0,12 0),\ + (1 0,101 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 1,2 1),(5 1,6 1),(9 1,10 1),\ + (13 1,14 1),(101 0),(1 0),(1 0,101 0))"), + from_wkt<ML>("MULTILINESTRING((1 0),(1 1,2 1),(5 1,6 1),(9 1,10 1),\ + (13 1,14 1),(3 0,4 0),(7 0,8 0),(11 0,12 0),(15 0),\ + (1 0,101 0))"), +#endif + "mlmli11" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (1 1,2 0,18 0,19 1),(2 1,3 0,17 0,18 1),\ + (3 1,4 0,16 0,17 1))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(2 0,18 0),(3 0,17 0),\ + (4 0,16 0))"), + "mlmli12" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0,20 1),\ + (2 0,18 0,19 1),(3 0,17 0,18 1),\ + (4 0,16 0,17 1))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(2 0,18 0),(3 0,17 0),\ + (4 0,16 0))"), + "mlmli13" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1,19 1,18 0,2 0,\ + 1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(18 0,2 0),\ + (3 0,17 0),(16 0,4 0))"), + "mlmli14" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,4 2,6 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(6 0))"), +#endif + "mlmli15" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (6 0,4 2,2 2))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(6 0))"), +#endif + "mlmli15a" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,4 2,5 0,6 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(5 0,6 0))"), + "mlmli16" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (6 0,5 0,4 2,2 2))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(6 0,5 0))"), + "mlmli16a" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,4 0,5 2,20 2,25 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(25 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(4 0),(25 0))"), +#endif + "mlmli17" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,4 0,5 2,20 2,25 0,26 2))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(25 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(4 0),(25 0))"), +#endif + "mlmli17a" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,5 -1,15 2,18 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(4 0),\ + (8.3333333333333333333 0),(18 0))"), +#endif + "mlmli18" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,18 0,19 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\ + (2 2,5 -1,15 2,18 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,18 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,18 0,19 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,19 0),(4 0),\ + (8.3333333333333333333 0),(18 0))"), +#endif + "mlmli18a" + ); +} + + + + + + +#ifndef BOOST_GEOMETRY_TEST_NO_DEGENERATE +BOOST_AUTO_TEST_CASE( test_intersection_ml_ml_degenerate ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** MULTILINESTRING / MULTILINESTRING INTERSECTION" + << " (DEGENERATE) ***" + << std::endl; + std::cout << std::endl; +#endif + + typedef multi_linestring_type ML; + + typedef test_intersection_of_geometries<ML, ML, ML> tester; + + // the following test cases concern linestrings with duplicate + // points and possibly linestrings with zero length. + + // no unique: (3 0) appears twice + tester::apply + (from_wkt<ML>("MULTILINESTRING((5 5,5 5),(0 0,18 0,18 0,\ + 19 0,19 0,19 0,30 0),(2 0,2 0),(4 10,4 10))"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 10),\ + (4 0,4 10),(5 5,5 5))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((5 5),(0 0),(1 0),(2 0),(3 0),\ + (4 0),(5 0,18 0,19 0,20 0),(2 0),(4 10))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(2 0),(3 0),\ + (0 0),(4 0),(4 10),(5 5))"), +#endif + "mlmli20a" + ); + + // no unique: (3 0) appears three times + tester::apply + (from_wkt<ML>("MULTILINESTRING((5 5,5 5),(0 0,0 0,18 0,18 0,\ + 19 0,19 0,19 0,30 0,30 0),(2 0,2 0),(4 10,4 10))"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (4 0,4 10,4 10),(5 5,5 5))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((5 5),(0 0),(1 0),(2 0),(3 0),(4 0),\ + (5 0,18 0,19 0,20 0),(2 0),(4 10))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(2 0),\ + (3 0),(0 0),(4 0),(4 10),(5 5))"), +#endif + "mlmli20aa" + ); + + // no unique: (3 0) appears twice + tester::apply + (from_wkt<ML>("MULTILINESTRING((5 5,5 5),(0 0,0 0,18 0,18 0,\ + 19 0,19 0,19 0,30 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (4 0,4 0,4 10,4 10),(0 5,15 5))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((5 5),(0 0),(1 0),(2 0),(3 0),(4 0),\ + (5 0,18 0,19 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(3 0),\ + (0 0),(4 0),(5 5))"), +#endif + "mlmli20b" + ); + + // no unique: (3 0) and (30 0) appear twice + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,0 0,18 0,18 0,\ + 19 0,19 0,19 0,30 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (30 0,30 0,30 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\ + (5 0,18 0,19 0,20 0),(30 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(3 0),\ + (0 0),(30 0))"), +#endif + "mlmli20c" + ); + + // no unique: (3 0) appears twice + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,0 0,18 0,18 0,\ + 19 0,19 0,19 0,30 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\ + (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (30 0,30 0,31 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\ + (5 0,18 0,19 0,20 0),(30 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(3 0),\ + (0 0),(30 0))"), +#endif + "mlmli20d" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,0 0,18 0,18 0,\ + 19 0,19 0,19 0,30 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((0 10,5 0,20 0,20 0,30 0),\ + (1 10,1 10,1 0,1 0,1 -10),\ + (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\ + (30 0,30 0,31 0,31 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,30 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0,30 0))"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\ + (5 0,18 0,19 0,30 0),(30 0))"), + from_wkt<ML>("MULTILINESTRING((5 0,20 0,30 0),(1 0),(2 0),(3 0),\ + (0 0),(30 0))"), +#endif + "mlmli20e" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((1 5, -4.3 -.1), (0 6, 8.6 6, 189.7654 5, 1 3, 6 3, 3 5, 6 2.232432, 0 4), (-6 5, 1 2.232432), (3 -1032.34324, 9 0, 189.7654 1, -1.4 3, 3 189.7654, +.3 10.0002, 1 5, 6 3, 5 1, 9 1, 10.0002 -1032.34324, -0.7654 0, 5 3, 3 4), (2.232432 2.232432, 8.6 +.4, 0.0 2.232432, 4 0, -8.8 10.0002), (1 0, 6 6, 7 2, -0 8.4), (-0.7654 3, +.6 8, 4 -1032.34324, 1 6, 0 4), (0 7, 2 1, 8 -7, 7 -.7, -1032.34324 9), (5 0, 10.0002 4, 8 7, 3 3, -8.1 5))"), + from_wkt<ML>("MULTILINESTRING((5 10.0002, 2 7, -0.7654 0, 5 3), (0 -0.7654, 4 10.0002, 4 +.1, -.8 3, -.1 8, 10.0002 2, +.9 -1032.34324))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((-0.7654 8.88178e-16,-0.7654 0,5 3))"), +#else + from_wkt<ML>("MULTILINESTRING((-0.756651 3.30964),(1.60494 6),\ + (2.51371 6),(3.26673 6),(4 6),(8.18862 3.07616),\ + (4 3.03179),(1.40063 3.00424),(1.39905 3),\ + (4 3),(5 3),(4 4.33333),(4 4.07748),\ + (4.41962 2.698),(4 2.82162),(1.59592 3.52985),\ + (0.729883 3.78498),(-0.532243 2.83823),\ + (0.235887 2.53454),(7.08745 -329.0674155),\ + (9.98265 0.00543606),(8.49103 2.89652),\ + (4.87386 2.93436),(4 2.9435),(1.38821 2.97083)\ + (0.412281 2.98104),(-0.789427 2.99361),\ + (0.641699 7.5594),(1.18124 4.9275),\ + (1.99437 4.60225),(4 3.8),(9.09826 -100.515944),\ + (5.06428 -559.024344),\ + (4 3.5),(3.06464 1.99294),(4 1.72377),\ + (4 1.38014),(2.50083 1.69957),(1.03214 2.01251),\ + (0.72677 2.07758),(0.10749 2.20953),\ + (0.0954852 2.17914),(0.92255 1.71755),\ + (1.70073 1.28324),(3.43534 0.441146),\ + (2.09493 1.48836),(1.12031 2.2498),\ + (0.358522 2.84496),(-0.705343 3.67612),\ + (2.06005 1.27206),(2.3516 1.62191),(4 3.6),\ + (5.09496 4.91395),(6.47672 4.09311),(4 4.74286),\ + (2.54193 6.07595),(1.87562 6.68515),\ + (1.43457 7.08839),(0.502294 7.64221),\ + (0.601362 7.58336),(0.614728 3.49349),\ + (0.619143 2.1426),(0.623165 0.911787),\ + (0.623783 0.722855),(3.16036 -775.427199),\ + (3.23365 -767.0972558),(1.01466 0.926246),\ + (1.01183 1.90535),(1.01168 1.95744),\ + (1.00439 4.47984),(0.91526 4.25422),\ + (1.36441 2.90677),(1.8713 1.38609),\ + (1.87531 1.37408),(0.0484053 -0.635122),\ + (8.5655 2.85228),(5.26567 4.81254),(4 3.8),\ + (1.4995 3.27036),(0.591231 3.43401),\ + (-0.706503 3.66784),\ + (-0.7654 8.88178e-16,-0.7654 0,5 3))"), + from_wkt<ML>("MULTILINESTRING((1.87562 6.68515),(1.60494 6),\ + (1.18124 4.9275),(1.00439 4.47984),(0.91526 4.25422),\ + (0.729883 3.78498),(0.614728 3.49349),\ + (0.591231 3.43401),(0.412281 2.98104),\ + (0.358522 2.84496),(0.235887 2.53454),\ + (0.10749 2.20953),(0.0954852 2.17914),\ + (5 3),(0.0484053 -0.635122),(0.535994 0.677175),\ + (0.623165 0.911787),(0.92255 1.71755),\ + (1.01168 1.95744),(1.03214 2.01251),\ + (1.12031 2.2498),(1.36441 2.90677),\ + (1.38821 2.97083),(1.39905 3),(1.40063 3.00424),\ + (1.4995 3.27036),(1.59592 3.52985),\ + (1.99437 4.60225),(2.51371 6),(2.54193 6.07595),\ + (4 6),(4 4.74286),(4 4.33333),(4 4.07748),(4 3.8),\ + (4 3.8),(4 3.6),(4 3.5),(4 3.03179),(4 3),\ + (4 2.9435),(4 2.82162),(4 2.47965),(4 1.72377),\ + (4 1.38014),(3.43534 0.441146),(2.06005 1.27206),\ + (1.88383 1.37852),(1.8713 1.38609),\ + (1.01183 1.90535),(0.72677 2.07758),\ + (0.619143 2.1426),(-0.532243 2.83823),\ + (-0.789427 2.99361),(-0.756651 3.30964),\ + (-0.706503 3.66784),(-0.705343 3.67612),\ + (0.502294 7.64221),(0.601362 7.58336),\ + (0.641699 7.5594),(1.43457 7.08839),\ + (3.26673 6),(5.09496 4.91395),(5.26567 4.81254),\ + (6.47672 4.09311),(8.18862 3.07616),\ + (8.49103 2.89652),(8.5655 2.85228),\ + (9.98265 0.00543606),(9.09826 -100.515944),\ + (7.08745 -329.0674155),(5.06428 -559.024344),\ + (3.23365 -767.0972558),(3.16036 -775.427199),\ + (-0.7654 8.88178e-16,-0.7654 0,5 3))"), +#endif + "mlmli21", + 1e-4 + ); +} +#endif // BOOST_GEOMETRY_TEST_NO_DEGENERATE + + + + +BOOST_AUTO_TEST_CASE( test_intersection_ml_ml_spikes ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** MULTILINESTRING / MULTILINESTRING INTERSECTION" + << " (WITH SPIKES) ***" + << std::endl; + std::cout << std::endl; +#endif + + typedef multi_linestring_type ML; + + typedef test_intersection_of_geometries<ML, ML, ML> tester; + + // the following test cases concern linestrings with spikes + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0,5 0))"), + "mlmli-spikes-01" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((9 0,1 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0))"), + from_wkt<ML>("MULTILINESTRING((9 0,1 0,5 0))"), + "mlmli-spikes-02" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0,2 0,8 0,3 0,7 0,4 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0,2 0,8 0,3 0,7 0,4 0,5 0))"), + "mlmli-spikes-03" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,3 0,2 0,4 0,3 0,5 0,4 0,6 0,\ + 5 0,7 0,6 0,8 0,7 0,9 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,3 0,2 0,4 0,3 0,5 0,4 0,6 0,\ + 5 0,7 0,6 0,8 0,7 0,9 0))"), + "mlmli-spikes-04" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),\ + (9 1,9 0,9 2))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,6 0),(7 0,8 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,6 0),(7 0,8 0),(9 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),(9 0))"), +#endif + "mlmli-spikes-05" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),\ + (9 0,9 2,9 1))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,6 0),(7 0,8 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,6 0),(7 0,8 0),(9 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),(9 0))"), +#endif + "mlmli-spikes-05a" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(9 0,6 0,8 0),\ + (11 0,8 0,12 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0),(6 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(9 0,6 0,8 0),\ + (10 0,8 0,10 0))"), + "mlmli-spikes-06" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((-1 0,0 0,-2 0),(11 0,10 0,12 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(10 0))"), +#endif + "mlmli-spikes-07" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,-2 -2),(11 1,10 0,12 2))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((0 0),(10 0))"), +#endif + "mlmli-spikes-07a" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(11 0,10 0,12 0),\ + (7 5,7 0,8 0,6.5 0,8.5 0,8.5 5))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING((1 0,6 0),(6.5 0,8.5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,6.5 0,8.5 0))"), +#else + from_wkt<ML>("MULTILINESTRING((1 0,6 0),(6.5 0,8.5 0),(10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,6.5 0,8.5 0),(10 0))"), +#endif + "mlmli-spikes-08" + ); + + // now the first geometry has a spike + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,8 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,7 0,4 0,8 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,8 0))"), + "mlmli-spikes-09" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"), + "mlmli-spikes-09a" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,5 0),(9 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,5 0),(5 0,4 0,5 0),(9 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,5 0),(9 0,10 0))"), + "mlmli-spikes-09b" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,5 0),(6 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,5 0),(6 0,7 0,6 0),(5 0,4 0,5 0),\ + (6 0,10 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,5 0),(6 0,10 0))"), + "mlmli-spikes-09c" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,8 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,8 0),(8 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,8 0))"), + "mlmli-spikes-10" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,8 0,4 0),(2 0,9 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,9 0),(9 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((1 0,8 0,4 0),(2 0,9 0,5 0))"), + "mlmli-spikes-11" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((11 1,10 0,12 2))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((10 0))"), +#endif + "mlmli-spikes-12" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((11 -1,10 0,12 -2))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((10 0))"), +#endif + "mlmli-spikes-12a" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"), + from_wkt<ML>("MULTILINESTRING((11 0,10 0,12 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((10 0))"), +#endif + "mlmli-spikes-13" + ); + + // the following three tests have been discussed with Adam + tester::apply + (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"), + from_wkt<ML>("MULTILINESTRING((1 2,1 1,1 2))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((1 1))"), +#endif + "mlmli-spikes-14" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,1 0,0 0))"), + from_wkt<ML>("MULTILINESTRING((2 0,1 0,2 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((1 0))"), +#endif + "mlmli-spikes-15" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"), + from_wkt<ML>("MULTILINESTRING((2 0,1 1,2 0))"), +#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS + from_wkt<ML>("MULTILINESTRING()"), +#else + from_wkt<ML>("MULTILINESTRING((1 1))"), +#endif + "mlmli-spikes-16" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"), + from_wkt<ML>("MULTILINESTRING((2 1,1 1,2 1))"), + from_wkt<ML>("MULTILINESTRING((1 1,2 1))"), + from_wkt<ML>("MULTILINESTRING((2 1,1 1,2 1))"), + "mlmli-spikes-17" + ); + + // test cases sent by Adam on the mailing list (equal slikes) + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"), + "mlmli-spikes-18" + ); + + tester::apply + (from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"), + from_wkt<ML>("MULTILINESTRING((1 1,0 0,1 1))"), + from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"), + from_wkt<ML>("MULTILINESTRING((1 1,0 0,1 1))"), + "mlmli-spikes-19" + ); +} diff --git a/libs/geometry/test/algorithms/set_operations/intersection/intersection_pl_pl.cpp b/libs/geometry/test/algorithms/set_operations/intersection/intersection_pl_pl.cpp new file mode 100644 index 000000000..212f914af --- /dev/null +++ b/libs/geometry/test/algorithms/set_operations/intersection/intersection_pl_pl.cpp @@ -0,0 +1,185 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014-2015, Oracle and/or its affiliates. + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +#include <iostream> + +#ifndef BOOST_TEST_MODULE +#define BOOST_TEST_MODULE test_intersection_pointlike_pointlike +#endif + +#ifdef BOOST_GEOMETRY_TEST_DEBUG +#define BOOST_GEOMETRY_DEBUG_TURNS +#define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER +#endif + +#include <boost/test/included/unit_test.hpp> + +#include "../test_set_ops_pl_pl.hpp" + +#include <boost/geometry/geometries/multi_point.hpp> + +typedef bg::model::point<double,2,bg::cs::cartesian> point_type; +typedef bg::model::multi_point<point_type> multi_point_type; + + + +//=========================================================================== +//=========================================================================== +//=========================================================================== + + +BOOST_AUTO_TEST_CASE( test_intersection_point_point ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** POINT / POINT INTERSECTION ***" << std::endl; + std::cout << std::endl; +#endif + + typedef point_type P; + typedef multi_point_type MP; + + typedef test_set_op_of_pointlike_geometries + < + P, P, MP, bg::overlay_intersection + > tester; + + tester::apply + (from_wkt<P>("POINT(0 0)"), + from_wkt<P>("POINT(1 1)"), + from_wkt<MP>("MULTIPOINT()"), + "ppi01"); + + tester::apply + (from_wkt<P>("POINT(0 0)"), + from_wkt<P>("POINT(0 0)"), + from_wkt<MP>("MULTIPOINT(0 0)"), + "ppi02"); +} + + +BOOST_AUTO_TEST_CASE( test_intersection_multipoint_point ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** MULTIPOINT / POINT INTERSECTION ***" << std::endl; + std::cout << std::endl; +#endif + + typedef point_type P; + typedef multi_point_type MP; + + typedef test_set_op_of_pointlike_geometries + < + MP, P, MP, bg::overlay_intersection + > tester; + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0)"), + from_wkt<P>("POINT(1 1)"), + from_wkt<MP>("MULTIPOINT()"), + "mppi01"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0)"), + from_wkt<P>("POINT(0 0)"), + from_wkt<MP>("MULTIPOINT(0 0)"), + "mppi02"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0,0 0)"), + from_wkt<P>("POINT(1 1)"), + from_wkt<MP>("MULTIPOINT()"), + "mppi03"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0,0 0)"), + from_wkt<P>("POINT(0 0)"), + from_wkt<MP>("MULTIPOINT(0 0)"), + "mppi04"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0,0 0,1 0)"), + from_wkt<P>("POINT(1 1)"), + from_wkt<MP>("MULTIPOINT()"), + "mppi05"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0,0 0,1 0)"), + from_wkt<P>("POINT(1 0)"), + from_wkt<MP>("MULTIPOINT(1 0)"), + "mppi06"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0,0 0,1 0)"), + from_wkt<P>("POINT(0 0)"), + from_wkt<MP>("MULTIPOINT(0 0)"), + "mppi07"); + + tester::apply + (from_wkt<MP>("MULTIPOINT()"), + from_wkt<P>("POINT(0 0)"), + from_wkt<MP>("MULTIPOINT()"), + "mppi08"); +} + + +BOOST_AUTO_TEST_CASE( test_intersection_multipoint_multipoint ) +{ +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl << std::endl << std::endl; + std::cout << "*** MULTIPOINT / MULTIPOINT INTERSECTION ***" << std::endl; + std::cout << std::endl; +#endif + + typedef multi_point_type MP; + + typedef test_set_op_of_pointlike_geometries + < + MP, MP, MP, bg::overlay_intersection + > tester; + + tester::apply + (from_wkt<MP>("MULTIPOINT(2 2,3 3,0 0,0 0,2 2,1 1,1 1,1 0,1 0)"), + from_wkt<MP>("MULTIPOINT(1 0,1 1,1 1,1 1)"), + from_wkt<MP>("MULTIPOINT(1 0,1 1,1 1,1 1)"), + "mpmpi01"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0,1 1,1 0,1 1)"), + from_wkt<MP>("MULTIPOINT(1 0,0 0,1 1,0 0)"), + from_wkt<MP>("MULTIPOINT(0 0,1 1,1 0,1 1)"), + from_wkt<MP>("MULTIPOINT(1 0,0 0,1 1,0 0)"), + "mpmpi02"); + + tester::apply + (from_wkt<MP>("MULTIPOINT()"), + from_wkt<MP>("MULTIPOINT(1 0,0 0,1 1,0 0)"), + from_wkt<MP>("MULTIPOINT()"), + "mpmpi03"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0,1 1,1 0,1 1)"), + from_wkt<MP>("MULTIPOINT()"), + from_wkt<MP>("MULTIPOINT()"), + "mpmpi04"); + + tester::apply + (from_wkt<MP>("MULTIPOINT()"), + from_wkt<MP>("MULTIPOINT()"), + from_wkt<MP>("MULTIPOINT()"), + "mpmpi05"); + + tester::apply + (from_wkt<MP>("MULTIPOINT(0 0,1 0,2 0,3 0,0 0,1 0,2 0)"), + from_wkt<MP>("MULTIPOINT(0 1,0 2,1 0,0 0,2 0)"), + from_wkt<MP>("MULTIPOINT(1 0,0 0,2 0)"), + "mpmpi06"); +} + diff --git a/libs/geometry/test/algorithms/set_operations/intersection/intersection_segment.cpp b/libs/geometry/test/algorithms/set_operations/intersection/intersection_segment.cpp new file mode 100644 index 000000000..664d37c9b --- /dev/null +++ b/libs/geometry/test/algorithms/set_operations/intersection/intersection_segment.cpp @@ -0,0 +1,134 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2012 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2012 Mateusz Loskot, London, UK. + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-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) + +#include <algorithm> +#include <ostream> +#include <sstream> +#include <string> +#include <vector> + +#include <boost/config.hpp> +#include <geometry_test_common.hpp> + +#include <boost/geometry/algorithms/correct.hpp> +#include <boost/geometry/algorithms/within.hpp> +#include <boost/geometry/algorithms/intersection_segment.hpp> +#include <boost/geometry/io/wkt/aswkt.hpp> + +static std::ostream & operator<<(std::ostream &s, const bg::intersection_result& r) +{ + switch(r) + { + case bg::is_intersect_no : s << "is_intersect_no"; break; + case bg::is_intersect : s << "is_intersect"; break; + case bg::is_parallel : s << "is_parallel"; break; + case bg::is_collinear_no : s << "is_collinear_no"; break; + case bg::is_collinear_one : s << "is_collinear_one"; break; + case bg::is_collinear_connect : s << "is_collinear_connect"; break; + case bg::is_collinear_overlap : s << "is_collinear_overlap"; break; + case bg::is_collinear_overlap_opposite : s << "is_collinear_overlap_opposite"; break; + case bg::is_collinear_connect_opposite : s << "is_collinear_connect_opposite"; break; + + // detailed connection results: + case bg::is_intersect_connect_s1p1 : s << "is_intersect_connect_s1p1"; break; + case bg::is_intersect_connect_s1p2 : s << "is_intersect_connect_s1p2"; break; + case bg::is_intersect_connect_s2p1 : s << "is_intersect_connect_s2p1"; break; + case bg::is_intersect_connect_s2p2 : s << "is_intersect_connect_s2p2"; break; + } + return s; +} + +static std::string as_string(const bg::intersection_result& r) +{ + std::stringstream out; + out << r; + return out.str(); +} + +typedef bg::model::point<double> P; +typedef bg::const_segment<P> S; + + +static void test_intersection(double s1x1, double s1y1, double s1x2, double s1y2, + double s2x1, double s2y1, double s2x2, double s2y2, + // Expected results + bg::intersection_result expected_result, + int exptected_count, const P& exp_p1, const P& exp_p2) +{ + S s1(P(s1x1, s1y1), P(s1x2, s1y2)); + S s2(P(s2x1, s2y1), P(s2x2, s2y2)); + std::vector<P> ip; + double ra, rb; + bg::intersection_result r = bg::intersection_s(s1, s2, ra, rb, ip); + r = bg::intersection_connect_result(r, ra, rb); + + BOOST_CHECK_EQUAL(ip.size(), exptected_count); + BOOST_CHECK_EQUAL(as_string(expected_result), as_string(r)); + + if (ip.size() == 2 && ip[0] != exp_p1) + { + // Swap results, second point is not as expected, swap results, order is not prescribed, + // it might be OK. + std::reverse(ip.begin(), ip.end()); + } + + if (ip.size() >= 1) + { + BOOST_CHECK_EQUAL(ip[0], exp_p1); + } + if (ip.size() >= 2) + { + BOOST_CHECK_EQUAL(ip[1], exp_p2); + } + + + /* + std::cout << exptected_count << " " << r; + if (exptected_count >= 1) std::cout << " " << ip[0]; + if (exptected_count >= 2) std::cout << " " << ip[1]; + std::cout << std::endl; + */ +} + +//BOOST_AUTO_TEST_CASE( test1 ) +int test_main( int , char* [] ) +{ + // Identical cases + test_intersection(0,0, 1,1, 0,0, 1,1, bg::is_collinear_overlap, 2, P(0,0), P(1,1)); + test_intersection(1,1, 0,0, 0,0, 1,1, bg::is_collinear_overlap_opposite, 2, P(1,1), P(0,0)); + test_intersection(0,1, 0,2, 0,1, 0,2, bg::is_collinear_overlap, 2, P(0,1), P(0,2)); // Vertical + test_intersection(0,2, 0,1, 0,1, 0,2, bg::is_collinear_overlap_opposite, 2, P(0,2), P(0,1)); // Vertical + // Overlap cases + test_intersection(0,0, 1,1, -0.5,-0.5, 2,2, bg::is_collinear_overlap, 2, P(0,0), P(1,1)); + test_intersection(0,0, 1,1, 0.5,0.5, 1.5,1.5, bg::is_collinear_overlap, 2, P(0.5,0.5), P(1,1)); + test_intersection(0,0, 0,1, 0,-10, 0,10, bg::is_collinear_overlap, 2, P(0,0), P(0,1)); // Vertical + test_intersection(0,0, 0,1, 0,10, 0,-10, bg::is_collinear_overlap_opposite, 2, P(0,0), P(0,1)); // Vertical + test_intersection(0,0, 1,1, 1,1, 2,2, bg::is_collinear_connect, 1, P(1,1), P(0,0)); // Single point + // Colinear, non overlap cases + test_intersection(0,0, 1,1, 1.5,1.5, 2.5,2.5, bg::is_collinear_no, 0, P(0,0), P(0,0)); + test_intersection(0,0, 0,1, 0,5, 0,6, bg::is_collinear_no, 0, P(0,0), P(0,0)); // Vertical + // Parallel cases + test_intersection(0,0, 1,1, 1,0, 2,1, bg::is_parallel, 0, P(0,0), P(0,1)); + // Intersect cases + test_intersection(0,2, 4,2, 3,0, 3,4, bg::is_intersect, 1, P(3,2), P(0,0)); + // Non intersect cases + + // Single point cases + test_intersection(0,0, 0,0, 1,1, 2,2, bg::is_collinear_no, 0, P(1,1), P(0,0)); // Colinear/no + test_intersection(2,2, 2,2, 1,1, 3,3, bg::is_collinear_one, 1, P(2,2.01), P(0,0)); // On segment + test_intersection(1,1, 3,3, 2,2, 2,2, bg::is_collinear_one, 1, P(2,2), P(0,0)); // On segment + test_intersection(1,1, 3,3, 1,1, 1,1, bg::is_collinear_one, 1, P(1,1), P(0,0)); // On segment, start + test_intersection(1,1, 3,3, 3,3, 3,3, bg::is_collinear_one, 1, P(3,3), P(0,0)); // On segment, end + + return 0; +} diff --git a/libs/geometry/test/algorithms/set_operations/intersection/multi_intersection.cpp b/libs/geometry/test/algorithms/set_operations/intersection/multi_intersection.cpp new file mode 100644 index 000000000..46106022d --- /dev/null +++ b/libs/geometry/test/algorithms/set_operations/intersection/multi_intersection.cpp @@ -0,0 +1,240 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) +// Unit Test + +// Copyright (c) 2010-2012 Barend Gehrels, 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) + +#include <iostream> +#include <string> + +// If defined, tests are run without rescaling-to-integer or robustness policy +// This multi_intersection currently contains no tests for double then failing +// #define BOOST_GEOMETRY_NO_ROBUSTNESS + +// #define BOOST_GEOMETRY_DEBUG_ASSEMBLE + +#include "test_intersection.hpp" +#include <algorithms/test_overlay.hpp> +#include <algorithms/overlay/multi_overlay_cases.hpp> + +#include <boost/geometry/multi/algorithms/correct.hpp> +#include <boost/geometry/multi/algorithms/intersection.hpp> +#include <boost/geometry/multi/algorithms/within.hpp> // only for testing #77 + +#include <boost/geometry/geometries/point_xy.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> + +#include <boost/geometry/multi/io/wkt/read.hpp> + +template <typename Ring, typename Polygon, typename MultiPolygon> +void test_areal() +{ + test_one<Polygon, MultiPolygon, MultiPolygon>("simplex_multi", + case_multi_simplex[0], case_multi_simplex[1], + 2, 12, 6.42); + + 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, MultiPolygon, MultiPolygon>("case_multi_2", + case_multi_2[0], case_multi_2[1], + 3, 12, 5.9); + + test_one<Polygon, MultiPolygon, Polygon>("simplex_multi_mp_p", + case_multi_simplex[0], case_single_simplex, + 2, 12, 6.42); + + test_one<Polygon, Ring, MultiPolygon>("simplex_multi_r_mp", + case_single_simplex, case_multi_simplex[0], + 2, 12, 6.42); + test_one<Ring, MultiPolygon, Polygon>("simplex_multi_mp_r", + case_multi_simplex[0], case_single_simplex, + 2, 12, 6.42); + + // Constructed cases for multi/touch/equal/etc + test_one<Polygon, MultiPolygon, MultiPolygon>("case_61_multi", + case_61_multi[0], case_61_multi[1], + 0, 0, 0.0); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_62_multi", + case_62_multi[0], case_62_multi[1], + 1, 5, 1.0); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_63_multi", + case_63_multi[0], case_63_multi[1], + 1, 5, 1.0); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_64_multi", + case_64_multi[0], case_64_multi[1], + 1, 5, 1.0); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_65_multi", + case_65_multi[0], case_65_multi[1], + 1, 5, 1.0); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_72_multi", + case_72_multi[0], case_72_multi[1], + 3, 14, 2.85); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_77_multi", + case_77_multi[0], case_77_multi[1], + 5, 33, 9); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_78_multi", + case_78_multi[0], case_78_multi[1], + 1, 0, 22); // In "get_turns" using partitioning, #points went from 17 to 16 + test_one<Polygon, MultiPolygon, MultiPolygon>("case_101_multi", + case_101_multi[0], case_101_multi[1], + 4, 22, 4.75); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_102_multi", + case_102_multi[0], case_102_multi[1], + 3, 26, 19.75); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_107_multi", + case_107_multi[0], case_107_multi[1], + 2, 10, 1.5); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_recursive_boxes_1", + case_recursive_boxes_1[0], case_recursive_boxes_1[1], + 10, 97, 47.0); + test_one<Polygon, MultiPolygon, MultiPolygon>("case_recursive_boxes_2", + case_recursive_boxes_2[0], case_recursive_boxes_2[1], + 1, 47, 90.0); // Area from SQL Server + + test_one<Polygon, MultiPolygon, MultiPolygon>("case_recursive_boxes_3", + case_recursive_boxes_3[0], case_recursive_boxes_3[1], + 19, 87, 12.5); // Area from SQL Server + + test_one<Polygon, MultiPolygon, MultiPolygon>("case_recursive_boxes_4", + case_recursive_boxes_4[0], case_recursive_boxes_4[1], + 13, 157, 67.0); // Area from SQL Server + + test_one<Polygon, MultiPolygon, MultiPolygon>("ggl_list_20120915_h2_a", + ggl_list_20120915_h2[0], ggl_list_20120915_h2[1], + 2, 10, 6.0); // Area from SQL Server + test_one<Polygon, MultiPolygon, MultiPolygon>("ggl_list_20120915_h2_b", + ggl_list_20120915_h2[0], ggl_list_20120915_h2[2], + 2, 10, 6.0); // Area from SQL Server + + test_one<Polygon, MultiPolygon, MultiPolygon>("ticket_9081", + ticket_9081[0], ticket_9081[1], + 2, 10, 0.0019812556); +} + +template <typename Polygon, typename MultiPolygon, typename Box> +void test_areal_clip() +{ + 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 typename bg::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)); +} + +template <typename P> +void test_point_output() +{ + typedef bg::model::box<P> box; + typedef bg::model::linestring<P> linestring; + typedef bg::model::polygon<P> polygon; + typedef bg::model::multi_polygon<polygon> multi_polygon; + + test_point_output<multi_polygon, multi_polygon>(case_multi_simplex[0], case_multi_simplex[1], 10); + test_point_output<linestring, multi_polygon>("linestring(4 0,0 4)", case_multi_simplex[0], 4); + test_point_output<box, multi_polygon>("box(3 0,4 6)", case_multi_simplex[0], 8); +} + +template <typename MultiPolygon, typename MultiLineString> +void test_areal_linear() +{ + typedef typename boost::range_value<MultiPolygon>::type Polygon; + typedef typename boost::range_value<MultiLineString>::type LineString; + typedef typename bg::point_type<Polygon>::type Point; + typedef bg::model::ring<Point> Ring; + + test_one_lp<LineString, MultiPolygon, LineString>("case_mp_ls_1", case_multi_simplex[0], "LINESTRING(2 0,2 5)", 2, 4, 3.70); + test_one_lp<LineString, Polygon, MultiLineString>("case_p_mls_1", case_single_simplex, "MULTILINESTRING((2 0,2 5),(3 0,3 5))", 2, 4, 7.5); + test_one_lp<LineString, MultiPolygon, MultiLineString>("case_mp_mls_1", case_multi_simplex[0], "MULTILINESTRING((2 0,2 5),(3 0,3 5))", 4, 8, 6.8333333); + test_one_lp<LineString, Ring, MultiLineString>("case_r_mls_1", case_single_simplex, "MULTILINESTRING((2 0,2 5),(3 0,3 5))", 2, 4, 7.5); +} + +template <typename P> +void test_all() +{ + //typedef bg::model::box<P> box; + typedef bg::model::ring<P> ring; + typedef bg::model::polygon<P> polygon; + typedef bg::model::multi_polygon<polygon> multi_polygon; + test_areal<ring, polygon, multi_polygon>(); + +#if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE) + + typedef bg::model::ring<P, false> ring_ccw; + typedef bg::model::polygon<P, false> polygon_ccw; + typedef bg::model::multi_polygon<polygon_ccw> multi_polygon_ccw; + test_areal<ring_ccw, polygon_ccw, multi_polygon_ccw>(); + + typedef bg::model::ring<P, true, false> ring_open; + typedef bg::model::polygon<P, true, false> polygon_open; + typedef bg::model::multi_polygon<polygon_open> multi_polygon_open; + test_areal<ring_open, polygon_open, multi_polygon_open>(); + + typedef bg::model::ring<P, false, false> ring_open_ccw; + typedef bg::model::polygon<P, false, false> polygon_open_ccw; + typedef bg::model::multi_polygon<polygon_open_ccw> multi_polygon_open_ccw; + test_areal<ring_open_ccw, polygon_open_ccw, multi_polygon_open_ccw>(); + + test_areal_clip<polygon, multi_polygon, box>(); + test_areal_clip<polygon_ccw, multi_polygon_ccw, box>(); + + typedef bg::model::linestring<P> linestring; + typedef bg::model::multi_linestring<linestring> multi_linestring; + + test_linear<linestring, multi_linestring, box>(); + test_areal_linear<multi_polygon, multi_linestring>(); +#endif + + test_point_output<P>(); + // linear + +} + + +int test_main(int, char* []) +{ + test_all<bg::model::d2::point_xy<double> >(); + +#if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE) + test_all<bg::model::d2::point_xy<float> >(); + +#if defined(HAVE_TTMATH) + std::cout << "Testing TTMATH" << std::endl; + test_all<bg::model::d2::point_xy<ttmath_big> >(); +#endif + +#endif + + return 0; +} diff --git a/libs/geometry/test/algorithms/set_operations/intersection/test_intersection.hpp b/libs/geometry/test/algorithms/set_operations/intersection/test_intersection.hpp new file mode 100644 index 000000000..4a7cc645c --- /dev/null +++ b/libs/geometry/test/algorithms/set_operations/intersection/test_intersection.hpp @@ -0,0 +1,285 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) +// Unit Test + +// Copyright (c) 2007-2012 Barend Gehrels, 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_TEST_INTERSECTION_HPP +#define BOOST_GEOMETRY_TEST_INTERSECTION_HPP + +#include <fstream> +#include <iomanip> + +#include <boost/foreach.hpp> +#include <boost/variant/variant.hpp> + +#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/geometries/geometries.hpp> + +#include <boost/geometry/strategies/strategies.hpp> + +#include <boost/geometry/io/wkt/wkt.hpp> + + +#if defined(TEST_WITH_SVG) +# include <boost/geometry/io/svg/svg_mapper.hpp> +#endif + +#include <geometry_test_common.hpp> + +template <typename G1, typename G2, typename OutputType> +typename bg::default_area_result<G1>::type +check_result( + std::vector<OutputType> const& intersection_output, + std::string const& caseid, + std::size_t expected_count = 0, int expected_point_count = 0, + double expected_length_or_area = 0, + double percentage = 0.0001, + bool debug = false) +{ + bool const is_line = bg::geometry_id<OutputType>::type::value == 2; + + typename bg::default_area_result<G1>::type length_or_area = 0; + int n = 0; + for (typename std::vector<OutputType>::const_iterator it = intersection_output.begin(); + it != intersection_output.end(); + ++it) + { + if (expected_point_count > 0) + { + n += bg::num_points(*it, true); + } + + // instead of specialization we check it run-time here + length_or_area += is_line + ? bg::length(*it) + : bg::area(*it); + + if (debug) + { + std::cout << std::setprecision(20) << bg::wkt(*it) << std::endl; + } + } + +#if ! defined(BOOST_GEOMETRY_NO_BOOST_TEST) +#if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS) + if (expected_point_count > 0) + { + BOOST_CHECK_MESSAGE(bg::math::abs(n - expected_point_count) < 3, + "intersection: " << caseid + << " #points expected: " << expected_point_count + << " detected: " << n + << " type: " << (type_for_assert_message<G1, G2>()) + ); + } +#endif + + if (expected_count > 0) + { + BOOST_CHECK_MESSAGE(intersection_output.size() == expected_count, + "intersection: " << caseid + << " #outputs expected: " << expected_count + << " detected: " << intersection_output.size() + << " type: " << (type_for_assert_message<G1, G2>()) + ); + } + + double const detected_length_or_area = boost::numeric_cast<double>(length_or_area); + BOOST_CHECK_CLOSE(detected_length_or_area, expected_length_or_area, percentage); +#endif + + return length_or_area; +} + + +template <typename OutputType, typename CalculationType, typename G1, typename G2> +typename bg::default_area_result<G1>::type test_intersection(std::string const& caseid, + G1 const& g1, G2 const& g2, + std::size_t expected_count = 0, int expected_point_count = 0, + double expected_length_or_area = 0, + double percentage = 0.0001, + bool debug = false) +{ + if (debug) + { + std::cout << std::endl << "case " << caseid << std::endl; + } + + typedef typename bg::point_type<G1>::type point_type; + + if (! debug) + { + // Check _inserter behaviour with stratey + typedef bg::strategy_intersection + < + typename bg::cs_tag<point_type>::type, + G1, + G2, + point_type, + typename bg::rescale_policy_type<point_type>::type, + CalculationType + > strategy; + std::vector<OutputType> clip; + bg::detail::intersection::intersection_insert<OutputType>(g1, g2, std::back_inserter(clip), strategy()); + } + + typename bg::default_area_result<G1>::type length_or_area = 0; + + // Check normal behaviour + std::vector<OutputType> intersection_output; + bg::intersection(g1, g2, intersection_output); + + check_result<G1, G2>(intersection_output, caseid, expected_count, expected_point_count, + expected_length_or_area, percentage, debug); + + // Check variant behaviour + intersection_output.clear(); + bg::intersection(boost::variant<G1>(g1), g2, intersection_output); + + check_result<G1, G2>(intersection_output, caseid, expected_count, expected_point_count, + expected_length_or_area, percentage, debug); + + intersection_output.clear(); + bg::intersection(g1, boost::variant<G2>(g2), intersection_output); + + check_result<G1, G2>(intersection_output, caseid, expected_count, expected_point_count, + expected_length_or_area, percentage, debug); + + intersection_output.clear(); + bg::intersection(boost::variant<G1>(g1), boost::variant<G2>(g2), intersection_output); + + check_result<G1, G2>(intersection_output, caseid, expected_count, expected_point_count, + expected_length_or_area, percentage, debug); + +#if defined(TEST_WITH_SVG) + { + bool const is_line = bg::geometry_id<OutputType>::type::value == 2; + typedef typename bg::coordinate_type<G1>::type coordinate_type; + + bool const ccw = + bg::point_order<G1>::value == bg::counterclockwise + || bg::point_order<G2>::value == bg::counterclockwise; + bool const open = + bg::closure<G1>::value == bg::open + || bg::closure<G2>::value == bg::open; + + std::ostringstream filename; + filename << "intersection_" + << caseid << "_" + << string_from_type<coordinate_type>::name() + << string_from_type<CalculationType>::name() + << (ccw ? "_ccw" : "") + << (open ? "_open" : "") +#if defined(BOOST_GEOMETRY_NO_ROBUSTNESS) + << "_no_rob" +#endif + << ".svg"; + + std::ofstream svg(filename.str().c_str()); + + bg::svg_mapper<point_type> mapper(svg, 500, 500); + + mapper.add(g1); + mapper.add(g2); + + mapper.map(g1, is_line + ? "opacity:0.6;stroke:rgb(0,255,0);stroke-width:5" + : "fill-opacity:0.5;fill:rgb(153,204,0);" + "stroke:rgb(153,204,0);stroke-width:3"); + mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);" + "stroke:rgb(51,51,153);stroke-width:3"); + + for (typename std::vector<OutputType>::const_iterator it = intersection_output.begin(); + it != intersection_output.end(); ++it) + { + mapper.map(*it, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);" + "stroke:rgb(255,0,255);stroke-width:8"); + } + } +#endif + + + if (debug) + { + std::cout << "end case " << caseid << std::endl; + } + + return length_or_area; +} + +template <typename OutputType, typename G1, typename G2> +typename bg::default_area_result<G1>::type test_one(std::string const& caseid, + std::string const& wkt1, std::string const& wkt2, + std::size_t expected_count = 0, int expected_point_count = 0, + double expected_length_or_area = 0, + double percentage = 0.0001, + bool debug = false) +{ + G1 g1; + bg::read_wkt(wkt1, g1); + + G2 g2; + bg::read_wkt(wkt2, g2); + + // Reverse if necessary + bg::correct(g1); + bg::correct(g2); + + return test_intersection<OutputType, void>(caseid, g1, g2, + expected_count, expected_point_count, + expected_length_or_area, percentage, + debug); +} + +template <typename OutputType, typename Areal, typename Linear> +void test_one_lp(std::string const& caseid, + std::string const& wkt_areal, std::string const& wkt_linear, + std::size_t expected_count = 0, int expected_point_count = 0, + double expected_length = 0, + double percentage = 0.0001, + bool debug1 = false, bool debug2 = false) +{ + Areal areal; + bg::read_wkt(wkt_areal, areal); + bg::correct(areal); + + Linear linear; + bg::read_wkt(wkt_linear, linear); + + test_intersection<OutputType, void>(caseid, areal, linear, + expected_count, expected_point_count, + expected_length, percentage, debug1); + + // A linestring reversed should deliver exactly the same. + bg::reverse(linear); + + test_intersection<OutputType, void>(caseid + "_rev", areal, linear, + expected_count, expected_point_count, + expected_length, percentage, debug2); +} + +template <typename Geometry1, typename Geometry2> +void test_point_output(std::string const& wkt1, std::string const& wkt2, unsigned int expected_count) +{ + Geometry1 g1; + bg::read_wkt(wkt1, g1); + bg::correct(g1); + + Geometry2 g2; + bg::read_wkt(wkt2, g2); + bg::correct(g2); + + std::vector<typename bg::point_type<Geometry1>::type> points; + bg::intersection(g1, g2, points); + BOOST_CHECK_EQUAL(points.size(), expected_count); +} + + +#endif diff --git a/libs/geometry/test/algorithms/set_operations/intersection/test_intersection_linear_linear.hpp b/libs/geometry/test/algorithms/set_operations/intersection/test_intersection_linear_linear.hpp new file mode 100644 index 000000000..8e9254040 --- /dev/null +++ b/libs/geometry/test/algorithms/set_operations/intersection/test_intersection_linear_linear.hpp @@ -0,0 +1,229 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014-2015, Oracle and/or its affiliates. + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +#ifndef BOOST_GEOMETRY_TEST_INTERSECTION_LINEAR_LINEAR_HPP +#define BOOST_GEOMETRY_TEST_INTERSECTION_LINEAR_LINEAR_HPP + +#include <limits> + +#include <boost/geometry/multi/geometries/multi_point.hpp> +#include <boost/geometry/geometry.hpp> +#include "../test_set_ops_linear_linear.hpp" +#include <from_wkt.hpp> +#include <to_svg.hpp> + + +//================================================================== +//================================================================== +// intersection of (linear) geometries +//================================================================== +//================================================================== + +template +< + typename Geometry1, typename Geometry2, + typename MultiLineString +> +class test_intersection_of_geometries +{ +private: + static inline void base_test(Geometry1 const& geometry1, + Geometry2 const& geometry2, + MultiLineString const& mls_int1, + MultiLineString const& mls_int2, + std::string const& case_id, + double tolerance, + bool test_vector_and_deque = false) + { + static bool vector_deque_already_tested = false; + + typedef typename boost::range_value<MultiLineString>::type LineString; + typedef std::vector<LineString> linestring_vector; + typedef std::deque<LineString> linestring_deque; + + MultiLineString mls_output; + + linestring_vector ls_vector_output; + linestring_deque ls_deque_output; + + bg::intersection(geometry1, geometry2, mls_output); + + BOOST_CHECK_MESSAGE( equals::apply(mls_int1, mls_output, tolerance) + || equals::apply(mls_int2, mls_output, tolerance), + "case id: " << case_id + << ", intersection L/L: " << bg::wkt(geometry1) + << " " << bg::wkt(geometry2) + << " -> Expected: " << bg::wkt(mls_int1) + << " or: " << bg::wkt(mls_int2) + << " computed: " << bg::wkt(mls_output) ); + + set_operation_output("intersection", case_id, + geometry1, geometry2, mls_output); +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << "Geometry #1: " << bg::wkt(geometry1) << std::endl; + std::cout << "Geometry #2: " << bg::wkt(geometry2) << std::endl; + std::cout << "intersection : " << bg::wkt(mls_output) << std::endl; + std::cout << "expected intersection : " << bg::wkt(mls_int1) + << std::endl; + std::cout << std::endl; + std::cout << "************************************" << std::endl; + std::cout << std::endl; + std::cout << std::endl; +#endif + + if ( !vector_deque_already_tested && test_vector_and_deque ) + { + vector_deque_already_tested = true; +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl; + std::cout << "Testing with vector and deque as output container..." + << std::endl; +#endif + bg::intersection(geometry1, geometry2, ls_vector_output); + bg::intersection(geometry1, geometry2, ls_deque_output); + + BOOST_CHECK(multilinestring_equals + < + false + >::apply(mls_int1, ls_vector_output, tolerance)); + + BOOST_CHECK(multilinestring_equals + < + false + >::apply(mls_int1, ls_deque_output, tolerance)); + +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << "Done!" << std::endl << std::endl; +#endif + } + + // check the intersection where the order of the two + // geometries is reversed + bg::clear(mls_output); + bg::intersection(geometry2, geometry1, mls_output); + + BOOST_CHECK_MESSAGE( equals::apply(mls_int1, mls_output, tolerance) + || equals::apply(mls_int2, mls_output, tolerance), + "case id: " << case_id + << ", intersection L/L: " << bg::wkt(geometry1) + << " " << bg::wkt(geometry2) + << " -> Expected: " << bg::wkt(mls_int1) + << " or: " << bg::wkt(mls_int2) + << " computed: " << bg::wkt(mls_output) ); + +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << "Geometry #1: " << bg::wkt(geometry2) << std::endl; + std::cout << "Geometry #2: " << bg::wkt(geometry1) << std::endl; + std::cout << "intersection : " << bg::wkt(mls_output) << std::endl; + std::cout << "expected intersection : " << bg::wkt(mls_int2) + << std::endl; + std::cout << std::endl; + std::cout << "************************************" << std::endl; + std::cout << std::endl; + std::cout << std::endl; +#endif + } + +#ifdef BOOST_GEOMETRY_TEST_DEBUG + static inline void base_test_all(Geometry1 const& geometry1, + Geometry2 const& geometry2) + { + typedef typename bg::point_type<MultiLineString>::type Point; + typedef bg::model::multi_point<Point> multi_point; + + MultiLineString mls12_output, mls21_output; + multi_point mp12_output, mp21_output; + + bg::intersection(geometry1, geometry2, mls12_output); + bg::intersection(geometry1, geometry2, mp12_output); + bg::intersection(geometry2, geometry1, mls21_output); + bg::intersection(geometry2, geometry1, mp21_output); + + std::cout << "************************************" << std::endl; + std::cout << "Geometry #1: " << bg::wkt(geometry1) << std::endl; + std::cout << "Geometry #2: " << bg::wkt(geometry2) << std::endl; + std::cout << "intersection(1,2) [MLS]: " << bg::wkt(mls12_output) + << std::endl; + std::cout << "intersection(2,1) [MLS]: " << bg::wkt(mls21_output) + << std::endl; + std::cout << std::endl; + std::cout << "intersection(1,2) [MP]: " << bg::wkt(mp12_output) + << std::endl; + std::cout << "intersection(2,1) [MP]: " << bg::wkt(mp21_output) + << std::endl; + std::cout << std::endl; + std::cout << "************************************" << std::endl; + std::cout << std::endl; + std::cout << std::endl; + } +#else + static inline void base_test_all(Geometry1 const&, Geometry2 const&) + { + } +#endif + + +public: + static inline void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + MultiLineString const& mls_int1, + MultiLineString const& mls_int2, + std::string const& case_id, + double tolerance + = std::numeric_limits<double>::epsilon()) + { +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << "test case: " << case_id << std::endl; + std::stringstream sstr; + sstr << "svgs/" << case_id << ".svg"; +#ifdef TEST_WITH_SVG + to_svg(geometry1, geometry2, sstr.str()); +#endif +#endif + + Geometry1 rg1(geometry1); + bg::reverse<Geometry1>(rg1); + + Geometry2 rg2(geometry2); + bg::reverse<Geometry2>(rg2); + + test_get_turns_ll_invariance<>::apply(geometry1, geometry2); +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl + << "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%" + << std::endl << std::endl; +#endif + test_get_turns_ll_invariance<>::apply(rg1, geometry2); + + + base_test(geometry1, geometry2, mls_int1, mls_int2, case_id, tolerance); + // base_test(rg1, rg2, mls_int1, mls_int2); + base_test_all(geometry1, geometry2); + +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::cout << std::endl; + std::cout << std::endl; +#endif + } + + + + static inline void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + MultiLineString const& mls_int, + std::string const& case_id, + double tolerance + = std::numeric_limits<double>::epsilon()) + { + apply(geometry1, geometry2, mls_int, mls_int, case_id, tolerance); + } +}; + + +#endif // BOOST_GEOMETRY_TEST_INTERSECTION_LINEAR_LINEAR_HPP |