diff options
Diffstat (limited to 'libs/geometry/test/algorithms/overlay')
15 files changed, 1343 insertions, 55 deletions
diff --git a/libs/geometry/test/algorithms/overlay/Jamfile.v2 b/libs/geometry/test/algorithms/overlay/Jamfile.v2 index 9319330e9..fc27dbf59 100644 --- a/libs/geometry/test/algorithms/overlay/Jamfile.v2 +++ b/libs/geometry/test/algorithms/overlay/Jamfile.v2 @@ -16,11 +16,13 @@ test-suite boost-geometry-algorithms-overlay : [ run assemble.cpp ] - [ run ccw_traverse.cpp : : : <toolset>msvc:<cxxflags>/bigobj ] + [ run ccw_traverse.cpp ] [ run get_turn_info.cpp ] [ run get_turns.cpp ] + [ run get_turns_areal_areal.cpp ] [ run get_turns_linear_linear.cpp ] [ run get_turns_linear_areal.cpp ] + [ run multi_traverse.cpp : : : <define>BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE <define>BOOST_GEOMETRY_RESCALE_TO_ROBUST ] [ run relative_order.cpp ] [ run select_rings.cpp ] [ run self_intersection_points.cpp ] diff --git a/libs/geometry/test/algorithms/overlay/ccw_traverse.cpp b/libs/geometry/test/algorithms/overlay/ccw_traverse.cpp index 944f3937c..55d2d5894 100644 --- a/libs/geometry/test/algorithms/overlay/ccw_traverse.cpp +++ b/libs/geometry/test/algorithms/overlay/ccw_traverse.cpp @@ -36,9 +36,12 @@ struct rev : boost::mpl::if_c<bg::point_order<Geometry>::value == bg::counterclo {}; template <typename Geometry1, typename Geometry2> -inline typename bg::coordinate_type<Geometry1>::type intersect(Geometry1 const& g1, Geometry2 const& g2, std::string const& name, - bg::detail::overlay::operation_type op) +inline typename bg::coordinate_type<Geometry1>::type +intersect(Geometry1 const& g1, Geometry2 const& g2, std::string const& name, + bg::detail::overlay::operation_type op) { + boost::ignore_unused(name); + typedef typename bg::strategy::side::services::default_strategy < typename bg::cs_tag<Geometry1>::type diff --git a/libs/geometry/test/algorithms/overlay/get_turns.cpp b/libs/geometry/test/algorithms/overlay/get_turns.cpp index 3a3ab3620..504052df0 100644 --- a/libs/geometry/test/algorithms/overlay/get_turns.cpp +++ b/libs/geometry/test/algorithms/overlay/get_turns.cpp @@ -56,7 +56,7 @@ struct test_get_turns template<typename G1, typename G2> static void apply(std::string const& id, std::size_t expected_count, - G1 const& g1, G2 const& g2, double precision) + G1 const& g1, G2 const& g2, double /*precision*/) { typedef typename bg::point_type<G2>::type point_type; typedef typename bg::rescale_policy_type<point_type>::type diff --git a/libs/geometry/test/algorithms/overlay/get_turns_areal_areal.cpp b/libs/geometry/test/algorithms/overlay/get_turns_areal_areal.cpp new file mode 100644 index 000000000..f84c8d0bf --- /dev/null +++ b/libs/geometry/test/algorithms/overlay/get_turns_areal_areal.cpp @@ -0,0 +1,62 @@ +// Boost.Geometry +// Unit Test + +// 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. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015 Oracle and/or its affiliates. + +// 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) + +#include "test_get_turns.hpp" +#include <boost/geometry/geometries/geometries.hpp> + +//TEST +//#include <to_svg.hpp> + +template <typename T> +void test_all() +{ + typedef bg::model::point<T, 2, bg::cs::cartesian> pt; + //typedef bg::model::ring<pt> ring; + typedef bg::model::polygon<pt> poly; + //typedef bg::model::multi_polygon<polygon> mpoly; + + // mailing list report 17.03.2015 + // operations ok but wrong IPs for int + // (the coordinates are generates at endpoints only) + { + // cw(duplicated point) + test_geometry<poly, poly>("POLYGON((-8042 -1485,-8042 250,-8042 250,15943 254,15943 -1485,-8042 -1485))", + "POLYGON((-7901 -1485,-7901 529,-7901 529, 15802 544, 15802 -1485, -7901 -1485))", + expected_pusher<0>()("iiu")("iui")("mcc")("cui")); + //to_svg<poly, poly>("POLYGON((-8042 -1485,-8042 250,15943 254,15943 -1485,-8042 -1485))", + // "POLYGON((-7901 -1485,-7901 529,15802 544, 15802 -1485, -7901 -1485))", + // "poly_poly_1.svg"); + test_geometry<poly, poly>("POLYGON((-7901 -1485,-7901 529,-7901 529, 15802 544, 15802 -1485, -7901 -1485))", + "POLYGON((-8042 -1485,-8042 250,-8042 250,15943 254,15943 -1485,-8042 -1485))", + expected_pusher<0>()("iui")("iiu")("mcc")("ciu")); + } +} + +int test_main(int, char* []) +{ + test_all<int>(); + test_all<float>(); + test_all<double>(); + +#if ! defined(_MSC_VER) + test_all<long double>(); +#endif + +#if defined(HAVE_TTMATH) + test_all<ttmath_big>(); +#endif + return 0; +} diff --git a/libs/geometry/test/algorithms/overlay/get_turns_linear_areal.cpp b/libs/geometry/test/algorithms/overlay/get_turns_linear_areal.cpp index 202eb28ed..1ac88bff1 100644 --- a/libs/geometry/test/algorithms/overlay/get_turns_linear_areal.cpp +++ b/libs/geometry/test/algorithms/overlay/get_turns_linear_areal.cpp @@ -5,8 +5,10 @@ // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. -// This file was modified by Oracle on 2014. -// Modifications copyright (c) 2014 Oracle and/or its affiliates. +// This file was modified by Oracle on 2014, 2015. +// Modifications copyright (c) 2014-2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, 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. @@ -15,13 +17,11 @@ // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) -// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle - #include "test_get_turns.hpp" #include <boost/geometry/geometries/geometries.hpp> //TEST -//#include "to_svg.hpp" +//#include <to_svg.hpp> template <typename T> void test_all() @@ -158,6 +158,64 @@ void test_all() test_geometry<ls, poly>("LINESTRING(2 1,1 1,2 1)", "POLYGON((1 0,1 1,2 1,1 0))", expected("tcu+")("txc=")("tcc=")("txu=")); + + // 21.01.2015 + test_geometry<ls, poly>("LINESTRING(1 3,3 1)", + "POLYGON((0 0,0 4,4 4,4 0,2 2,0 0))", + expected("mcu+")("mxc=")); + // extended + test_geometry<ls, poly>("LINESTRING(1 7,4 4,7 1)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("tcu+")("mxc=")); + test_geometry<ls, poly>("LINESTRING(1 7,3 5,7 1)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcu+")("mxc=")); + test_geometry<ls, poly>("LINESTRING(1 7,5 3,7 1)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcu+")("mxc=")); + test_geometry<ls, poly>("LINESTRING(4 4,7 1)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("tcu+")("mxc=")); + test_geometry<ls, poly>("LINESTRING(5 3,7 1)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcu+")("mxc=")); + // reversed + test_geometry<ls, poly>("LINESTRING(7 1,4 4,1 7)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcc+")("tiu=")); + test_geometry<ls, poly>("LINESTRING(7 1,3 5,1 7)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcc+")("miu=")); + test_geometry<ls, poly>("LINESTRING(7 1,5 3,1 7)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcc+")("ccc=")("miu=")); + test_geometry<ls, poly>("LINESTRING(7 1,4 4)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcc+")("txu=")); + test_geometry<ls, poly>("LINESTRING(7 1,5 3)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcc+")("mxu=")); + test_geometry<ls, poly>("LINESTRING(7 1,3 5)", + "POLYGON((0 0,0 8,8 8,8 0,4 4,0 0))", + expected("mcc+")("miu=")); + + // 23.01.2015 - spikes + test_geometry<ls, poly>("LINESTRING(3 10, 1 5, 1 10, 3 4, 7 8, 6 10, 10 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + expected("miu+")("miu+")("miu+")("mxu+")); + // extended + test_geometry<ls, poly>("LINESTRING(7 8, 6 10, 11 0)", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + expected("miu+")("iuu+")); + + // 25.01.2015 + test_geometry<ls, poly>("LINESTRING(2 3, 4 5, 0 6, 5 6)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(4 4,6 4,6 6,4 6,4 4))", + expected("miu+")("miu+")("mcu+")("mxc=")); + test_geometry<ls, poly>("LINESTRING(0 6, 5 6)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(4 4,6 4,6 6,4 6,4 4))", + expected("miu+")("mcu+")("mxc=")); + } int test_main(int, char* []) diff --git a/libs/geometry/test/algorithms/overlay/get_turns_linear_linear.cpp b/libs/geometry/test/algorithms/overlay/get_turns_linear_linear.cpp index 5bb8c0a0d..cc7003f8e 100644 --- a/libs/geometry/test/algorithms/overlay/get_turns_linear_linear.cpp +++ b/libs/geometry/test/algorithms/overlay/get_turns_linear_linear.cpp @@ -5,8 +5,10 @@ // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. -// This file was modified by Oracle on 2014. -// Modifications copyright (c) 2014 Oracle and/or its affiliates. +// This file was modified by Oracle on 2014, 2015. +// Modifications copyright (c) 2014-2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, 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. @@ -15,8 +17,6 @@ // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) -// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle - #include "test_get_turns.hpp" #include <boost/geometry/geometries/geometries.hpp> @@ -214,6 +214,144 @@ void test_all() test_geometry<ls, ls>("LINESTRING(0 0,4 4,2 2)", "LINESTRING(0 4,5 4)", expected("muu++")); + // 29.01.2015 + if ( BOOST_GEOMETRY_CONDITION((boost::is_same<T, double>::value)) ) + { + // FAILING - possibly wrong IPs + test_geometry<ls, ls>("LINESTRING(3 -0.6,0 -0.9)", + "LINESTRING(4 2.232432,1 -0.8,9 0)", + expected("mui=+")("miu+=")); + + test_geometry<ls, ls>("LINESTRING(3 -0.6,1 -0.8,0 -0.9)", + "LINESTRING(4 2.232432,1 -0.8,9 0)", + expected("tui=+")("miu+=")); + + test_geometry<ls, ls>("LINESTRING(3 -0.6, 0 -0.9, -1 -1)", + "LINESTRING(4 2.232432, 0 -0.9, 9 0)", + expected("tui=+")("miu+=")); + + test_geometry<ls, ls>("LINESTRING(3 -0.6, 0 -0.9, -1 -1, -2 -2)", + "LINESTRING(4 2.232432,-1 -1, 0 -0.9, 9 0)", + expected("tui=+")("ecc==")("miu+=")); + } + + test_geometry<ls, ls>("LINESTRING(3 0,0 0)", + "LINESTRING(4 2,1 0,9 0)", + expected("mui=+")("miu+=")); + + + // 01.02.2015 + test_geometry<ls, ls>("LINESTRING(6 0,0 0,5 0)", + "LINESTRING(2 0,0 0,-10 0)", + expected("mii++")("txu==")("tiu==")("mui=+")); + // the reversal could be automatic... + test_geometry<ls, ls>("LINESTRING(2 0,0 0,-10 0)", + "LINESTRING(6 0,0 0,5 0)", + expected("mii++")("tux==")("tui==")("miu+=")); + // sanity check + test_geometry<ls, ls>("LINESTRING(6 0,0 0)", + "LINESTRING(2 0,0 0,-10 0)", + expected("mii++")("txu==")); + test_geometry<ls, ls>("LINESTRING(0 0,5 0)", + "LINESTRING(2 0,0 0,-10 0)", + expected("tiu+=")("mui=+")); + + // 03.02.2015 + test_geometry<ls, ls>("LINESTRING(-7 -8,3 0,4 -1,-7 10)", + "LINESTRING(-5 -4,3 0,4 -1,7 -4,2 -1)", + expected("tii++")("txu==")("tiu==")("mui=+")); + test_geometry<ls, ls>("LINESTRING(-7 -8,3 0,4 -1,-7 10)", + "LINESTRING(-5 -4,3 0,7 -4,2 -1)", + expected("tii++")("mxu==")("miu==")("mui=+")); + + if ( BOOST_GEOMETRY_CONDITION((boost::is_same<T, double>::value)) ) + { + // BUG - the operations are correct but IP coordinates are wrong + // ok now also the 3rd turn is wrong +#ifdef BOOST_GEOMETRY_TEST_ENABLE_FAILING + test_geometry<ls, ls>("LINESTRING(8 5,5 1,-2 3,1 10)", + "LINESTRING(1.9375 1.875, 1.7441860465116283 1.9302325581395348, -0.7692307692307692 2.6483516483516487, -2 3, -1.0071942446043165 5.316546762589928)", + expected("mii++")("ccc==")("ccc==")("mux==")); + // Now tii++ is generated instead of ccc== + + test_geometry<ls, ls>("LINESTRING(8 5,5 1,-2 3,1 10)", + "LINESTRING(1.9375 1.875, 1.7441860465116283 1.9302325581395348, -0.7692307692307692 2.6483516483516487, -2 3, -0.5 6.5)", + expected("mii++")("ccc==")("ccc==")("mux==")); + // Now tii++ is generated instead of ccc== + +#endif + + test_geometry<ls, ls>("LINESTRING(-0.5 7,8 1,0 -0.2)", + "LINESTRING(2 8,4 0.4,8 1,0 5)", + expected("iuu++")("mui=+")("tiu+=")); + + // assertion failure in 1.57 + // FAILING - no assertion failure but the result is not very good + test_geometry<ls, ls>("LINESTRING(-2305843009213693956 4611686018427387906, -33 -92, 78 83)", + "LINESTRING(31 -97, -46 57, -20 -4)", + expected("")("")); + test_geometry<ls, ls>("LINESTRING(31 -97, -46 57, -20 -4)", + "LINESTRING(-2305843009213693956 4611686018427387906, -33 -92, 78 83)", + expected("")("")); + } + + // In 1.57 the results of those combinations was different for MinGW + // (probably also QCC and GCC5.0) and MSVC/GCC. The results was depending + // on the instructions generated by the compiler when calculating the + // determinants. + // See also: https://svn.boost.org/trac/boost/ticket/8379 + // https://github.com/boostorg/geometry/pull/259 + if ( BOOST_GEOMETRY_CONDITION((boost::is_same<T, double>::value)) ) + { + test_geometry<ls, ls>("LINESTRING(0 0, 10 0, 20 1)", + "LINESTRING(12 10, 13 0.3, 14 0.4, 15 0.5)", + expected("mii++")("ccc==")("mux==")); + test_geometry<ls, ls>("LINESTRING(0 0, 10 0, 110 1)", + "LINESTRING(12 10, 13 0.03, 14 0.04, 15 0.05)", + expected("mii++")("ccc==")("mux==")); + test_geometry<ls, ls>("LINESTRING(0 0, 10 0, 110 1)", + "LINESTRING(102 10, 103 0.93, 104 0.94, 105 0.95)", + expected("mii++")("ccc==")("mux==")); + test_geometry<ls, ls>("LINESTRING(100 0, 110 0, 120 1)", + "LINESTRING(112 10, 113 0.3, 114 0.4, 115 0.5)", + expected("mii++")("ccc==")("mux==")); + test_geometry<ls, ls>("LINESTRING(0 0, 10 0, 20 1)", + "LINESTRING(15 0.5, 14 0.4, 13 0.3, 12 10)", + expected("miu+=")("mui=+")); + test_geometry<ls, ls>("LINESTRING(20 1, 10 0, 0 0)", + "LINESTRING(12 10, 13 0.3, 14 0.4, 15 0.5)", + expected("mui=+")("mix+=")); + test_geometry<ls, ls>("LINESTRING(20 1, 10 0, 0 0)", + "LINESTRING(15 0.5, 14 0.4, 13 0.3, 12 10)", + expected("muu==")("ccc==")("mii++")); + + test_geometry<ls, ls>("LINESTRING(0 0, 10 0, 20 1)", + "LINESTRING(13 0.3, 14 0.4, 15 0.5)", + expected("mii++")("ccc==")("mux==")); + test_geometry<ls, ls>("LINESTRING(0 0, 10 0, 20 1)", + "LINESTRING(15 0.5, 14 0.4, 13 0.3)", + expected("mix+=")("mui=+")); + test_geometry<ls, ls>("LINESTRING(20 1, 10 0, 0 0)", + "LINESTRING(13 0.3, 14 0.4, 15 0.5)", + expected("mui=+")("mix+=")); + test_geometry<ls, ls>("LINESTRING(20 1, 10 0, 0 0)", + "LINESTRING(15 0.5, 14 0.4, 13 0.3)", + expected("mux==")("ccc==")("mii++")); + + test_geometry<ls, ls>("LINESTRING(0 0, 10 0, 20 1)", + "LINESTRING(12 10, 13 0.3, 14 0.4)", + expected("mii++")("mux==")); + test_geometry<ls, ls>("LINESTRING(0 0, 10 0, 20 1)", + "LINESTRING(14 0.4, 13 0.3, 12 10)", + expected("miu+=")("mui=+")); + test_geometry<ls, ls>("LINESTRING(20 1, 10 0, 0 0)", + "LINESTRING(12 10, 13 0.3, 14 0.4)", + expected("mui=+")("mix+=")); + test_geometry<ls, ls>("LINESTRING(20 1, 10 0, 0 0)", + "LINESTRING(14 0.4, 13 0.3, 12 10)", + expected("muu==")("mii++")); + } + // TODO: //test_geometry<ls, ls>("LINESTRING(0 0,2 0,1 0)", "LINESTRING(0 1,0 0,2 0)", "1FF00F102"); //test_geometry<ls, ls>("LINESTRING(2 0,0 0,1 0)", "LINESTRING(0 1,0 0,2 0)", "1FF00F102"); diff --git a/libs/geometry/test/algorithms/overlay/multi_overlay_cases.hpp b/libs/geometry/test/algorithms/overlay/multi_overlay_cases.hpp new file mode 100644 index 000000000..c44b17adb --- /dev/null +++ b/libs/geometry/test/algorithms/overlay/multi_overlay_cases.hpp @@ -0,0 +1,458 @@ +// 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) + +#ifndef BOOST_GEOMETRY_TEST_MULTI_OVERLAY_CASES_HPP +#define BOOST_GEOMETRY_TEST_MULTI_OVERLAY_CASES_HPP + + +#include <string> + + +static std::string case_multi_simplex[2] = { + "MULTIPOLYGON(((0 1,2 5,5 3,0 1)),((1 1,5 2,5 0,1 1)))", + "MULTIPOLYGON(((3 0,0 3,4 5,3 0)))" }; + +// To mix multi/single +static std::string case_single_simplex = "POLYGON((3 0,0 3,4 5,3 0))"; + +static std::string case_multi_no_ip[2] = +{ + "MULTIPOLYGON(((4 1,0 7,7 9,4 1)),((8 1,6 3,10 4,8 1)),((12 6,10 7,13 8,12 6)))", + "MULTIPOLYGON(((14 4,8 8,15 10,14 4)),((15 3,18 9,20 2,15 3)),((3 4,1 7,5 7,3 4)))" +}; + +static std::string case_multi_2[2] = +{ + "MULTIPOLYGON(((4 3,2 7,10 9,4 3)),((8 1,6 3,10 4,8 1)),((12 6,10 7,13 8,12 6)))", + "MULTIPOLYGON(((14 4,8 8,15 10,14 4)),((15 3,18 9,20 2,15 3)),((5 5,4 7,7 7,5 5)))" +}; + +static std::string case_61_multi[2] = +{ + // extracted from recursive boxes + "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((2 2,2 3,3 3,3 2,2 2)))", + "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 3,2 4,3 4,3 3,2 3)))" +}; + +static std::string case_62_multi[2] = +{ + // extracted from recursive boxes + "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)))", + "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 3,2 4,3 4,3 3,2 3)))" +}; + +static std::string case_63_multi[2] = +{ + // extracted from recursive boxes + "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)))", + "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 1,2 2,3 2,3 1,2 1)))" +}; + +static std::string case_64_multi[3] = +{ + // extracted from recursive boxes + "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((2 2,2 3,3 3,3 2,2 2)))", + "MULTIPOLYGON(((1 1,1 2,2 2,3 2,3 1,2 1,1 1)))" , + // same but omitting not-necessary form-points at x=2 (==simplified) + "MULTIPOLYGON(((1 1,1 2,3 2,3 1,1 1)))" +}; + +static std::string case_65_multi[2] = +{ + "MULTIPOLYGON(((2 2,2 3,3 3,3 2,2 2)))", + "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((2 2,2 3,3 3,3 2,2 2)),((3 1,3 2,5 2,5 1,3 1)))" +}; + +static std::string case_66_multi[2] = +{ + "MULTIPOLYGON(((3 5,2 5,2 6,3 6,4 6,4 5,3 5)),((1 6,0 6,0 7,1 7,2 7,2 6,1 6)))", + "MULTIPOLYGON(((1 4,1 5,2 5,2 4,1 4)),((1 7,2 7,2 6,1 6,1 7)),((0 8,0 9,1 9,1 8,1 7,0 7,0 8)))" +}; + +static std::string case_67_multi[2] = +{ + "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 1,2 2,3 2,3 1,2 1)))", + "MULTIPOLYGON(((1 1,1 2,3 2,3 1,1 1)))" +}; + +static std::string case_68_multi[2] = +{ + "MULTIPOLYGON(((2 1,2 2,4 2,4 1,2 1)),((4 2,4 3,5 3,5 2,4 2)))", + "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 1,2 2,3 2,3 1,2 1)),((3 2,3 3,5 3,5 2,3 2)))" +}; + +static std::string case_69_multi[2] = +{ + "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((3 2,3 3,4 3,4 2,3 2)))", + "MULTIPOLYGON(((2 0,2 1,3 1,3 0,2 0)),((1 1,1 3,2 3,2 1,1 1)),((2 3,2 4,3 4,3 3,2 3)))" +}; + +static std::string case_71_multi[2] = +{ + "MULTIPOLYGON(((0 0,0 3,1 3,1 1,3 1,3 2,4 2,4 0,0 0)),((2 2,2 3,3 3,3 2,2 2)))", + "MULTIPOLYGON(((0 2,0 3,3 3,3 2,0 2)))" +}; + +static std::string case_72_multi[2] = +{ + // cluster with ii, done by both traverse and assemble + "MULTIPOLYGON(((0 3,4 4,3 0,3 3,0 3)),((3 3,2 1,1 2,3 3)))", + "MULTIPOLYGON(((0 0,1 4,3 3,4 1,0 0)))" +}; + +static std::string case_73_multi[2] = +{ + "MULTIPOLYGON(((2 2,2 3,3 3,3 2,2 2)),((1 1,1 2,2 2,2 1,1 1)))", + "MULTIPOLYGON(((1 1,1 2,2 2,2 3,3 3,3 1,1 1)))" +}; + +static std::string case_74_multi[2] = +{ + "MULTIPOLYGON(((3 0,2 0,2 1,3 1,3 3,1 3,1 2,2 2,2 1,0 1,0 5,4 5,4 0,3 0)))", + "MULTIPOLYGON(((0 2,0 3,1 3,1 1,2 1,2 0,0 0,0 2)),((2 3,1 3,1 4,2 4,2 3)))" +}; + +static std::string case_75_multi[2] = +{ + // cc/uu turns on all corners of second box + "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((1 3,1 4,2 4,2 3,1 3)),((2 2,2 3,3 3,3 2,2 2)),((3 1,3 2,4 2,4 1,3 1)),((3 3,3 4,4 4,4 3,3 3)))", + "MULTIPOLYGON(((2 2,2 3,3 3,3 2,2 2)))" +}; + +static std::string case_76_multi[2] = +{ + // cc/uu turns on all corners of second box, might generate TWO OVERLAPPING union polygons! + // therefore, don't follow uu. + "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1 0)),((3 2,4 2,4 1,3 1,3 2)),((2 2,2 3,3 3,3 2,2 2)),((2 3,1 3,1 4,2 4,2 3)),((3 3,3 4,4 4,4 3,3 3)))", + "MULTIPOLYGON(((0 2,0 3,1 3,1 2,2 2,2 0,1 0,1 1,0 1,0 2)),((2 2,2 3,3 3,3 2,2 2)))" +}; + +static std::string case_77_multi[2] = +{ + // with a point on interior-ring-border of enclosing + // -> went wrong in the assemble phase for intersection (traversal is OK) + // -> fixed + "MULTIPOLYGON(((3 3,3 4,4 4,4 3,3 3)),((5 3,5 4,4 4,4 5,3 5,3 6,5 6,5 5,7 5,7 6,8 6,8 5,9 5,9 2,8 2,8 1,7 1,7 2,5 2,5 3),(6 3,8 3,8 4,6 4,6 3)))", + "MULTIPOLYGON(((6 3,6 4,7 4,7 3,6 3)),((2 3,1 3,1 4,3 4,3 5,4 5,4 6,5 6,5 7,9 7,9 4,7 4,7 5,8 5,8 6,7 6,7 5,6 5,6 4,4 4,4 3,3 3,3 2,2 2,2 3)),((5 2,4 2,4 3,6 3,6 2,5 2)),((7 2,7 3,8 3,8 2,8 1,7 1,7 2)))" +}; + +static std::string case_78_multi[2] = +{ + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(2 2,4 2,4 3,2 3,2 2)))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(3 2,4 2,4 3,3 3,3 2),(1 1,2 1,2 2,1 2,1 1)))" + +}; + +static std::string case_80_multi[2] = +{ + // Many ux-clusters -> needs correct cluster-sorting + // Fixed now + "MULTIPOLYGON(((3 1,3 2,4 2,3 1)),((1 5,0 4,0 5,1 6,1 5)),((3 3,4 3,3 2,2 2,2 3,3 3)),((4 5,5 6,5 5,4 5)),((4 2,4 3,5 3,4 2)),((2.5 5.5,3 5,2 5,2 7,3 6,2.5 5.5)),((1 6,0 6,0 7,1 7,2 6,1 6)))", + "MULTIPOLYGON(((3 5,3 6,4 6,4 5,3 5)),((4 4,5 5,5 4,4 4)),((3 3,4 4,4 3,3 3)),((1 5,1 6,2 6,2 5,1 5)),((0 6,1 7,1 6,0 6)),((1 4,1 3,0 3,0 4,1 4)),((3 5,4 4,3 4,3 3,2 3,2 5,3 5)))" +}; + +static std::string case_81_multi[2] = +{ + "MULTIPOLYGON(((1 1,2 2,2 1,1 1)),((2 2,2 3,3 2,2 2)),((3 1,4 2,4 1,3 1)))", + "MULTIPOLYGON(((2 1,2 2,3 3,3 2,4 2,3 1,2 1)))" +}; + +static std::string case_82_multi[2] = +{ + "MULTIPOLYGON(((4 0,5 1,5 0,4 0)),((2 1,3 2,3 1,2 1)),((3 0,4 1,4 0,3 0)),((1 0,1 1,2 1,2 0,1 0)))", + "MULTIPOLYGON(((3 2,4 3,4 2,3 2)),((3 1,3 2,4 1,3 1)),((0 0,1 1,1 0,0 0)),((5 1,5 0,4 0,4 1,5 1)))" +}; + +static std::string case_83_multi[2] = +{ + // iu/iu + "MULTIPOLYGON(((1 0,1 1,2 1,1 0)),((0 1,0 4,1 4,1 1,0 1)),((2 1,2 2,3 2,3 1,2 1)),((2 3,3 4,3 3,2 3)))", + "MULTIPOLYGON(((1 0,2 1,2 0,1 0)),((0 3,1 4,1 3,0 3)),((2 3,2 4,3 3,2 3)),((1 3,2 3,2 2,0 2,1 3)))" +}; + +static std::string case_84_multi[2] = +{ + // iu/ux + "MULTIPOLYGON(((2 2,3 3,3 2,2 2)),((2 1,2 2,3 1,2 1)),((2 3,3 4,3 3,2 3)),((1 3,2 4,2 2,1 2,1 3)))", + "MULTIPOLYGON(((2 3,3 3,3 1,2 1,2 2,1 2,1 3,2 3)))" +}; + +static std::string case_85_multi[2] = +{ + // iu/ux (and ux/ux) + "MULTIPOLYGON(((0 1,0 2,1 2,0 1)),((1 1,1 2,2 1,1 1)),((0 3,1 3,0 2,0 3)))", + "MULTIPOLYGON(((1 3,2 3,2 1,1 1,1 2,0 2,1 3)))" +}; + +static std::string case_86_multi[2] = +{ + // iu/ux + "MULTIPOLYGON(((4 2,4 3,5 3,4 2)),((5 2,6 3,6 2,5 2)),((5 1,4 1,4 2,5 2,6 1,5 1)))", + "MULTIPOLYGON(((5 1,5 2,6 2,6 1,5 1)),((4 2,5 3,5 2,4 2)),((3 2,4 3,4 2,3 2)))" +}; + +static std::string case_87_multi[2] = +{ + // iu/ux where iu crosses, no touch + "MULTIPOLYGON(((5 0,5 1,6 0,5 0)),((6 2,7 3,7 2,6 2)),((5 1,5 3,6 3,6 1,5 1)))", + "MULTIPOLYGON(((5 1,5 2,7 2,7 1,6 1,6 0,5 0,5 1)),((4 3,5 3,5 2,3 2,4 3)))" +}; + + +static std::string case_88_multi[2] = +{ + "MULTIPOLYGON(((0 0,0 1,1 0,0 0)),((1 1,1 2,2 1,1 1)),((0 2,0 3,1 3,2 3,2 2,1 2,0 1,0 2)))", + "MULTIPOLYGON(((0 0,0 1,1 0,0 0)),((0 1,1 2,1 1,0 1)),((0 2,0 3,1 3,1 2,0 2)))" +}; + +static std::string case_89_multi[2] = +{ + // Extract from rec.boxes_3 + "MULTIPOLYGON(((8 1,7 1,8 2,8 3,9 4,9 2,8.5 1.5,9 1,8 0,8 1)),((9 1,9 2,10 2,10 1,9 0,9 1)))", + "MULTIPOLYGON(((8 3,9 4,9 3,8 3)),((7 0,7 1,8 1,8 0,7 0)),((9 2,9 1,8 1,8 3,8.5 2.5,9 3,9 2)))" +}; + +static std::string case_90_multi[2] = +{ + // iu/iu for Union; see ppt + "MULTIPOLYGON(((1 8,0 8,0 10,1 10,1 9,2 8,2 7,1 7,1 8)),((2 9,2 10,4 10,4 9,3 9,3 8,2 8,2 9)))", + "MULTIPOLYGON(((2 8,1 8,1 9,2 9,2 10,3 10,3 8,2 8)),((0 10,2 10,0 8,0 10)))" +}; + +static std::string case_91_multi[2] = +{ + // iu/xi for Intersection + "MULTIPOLYGON(((3 3,3 4,4 4,3 3)),((2 2,1 2,1 4,2 4,2 3,3 3,2 2)))", + "MULTIPOLYGON(((2 2,2 3,3 2,2 2)),((2 3,1 3,1 4,1.5 3.5,2 4,2.5 3.5,3 4,3 3,2 3)))" +}; + +static std::string case_92_multi[2] = +{ + // iu/iu all aligned (for union) + "MULTIPOLYGON(((7 2,7 3,8 2,7 2)),((8 4,9 5,9 4,8 4)),((8 2,8 3,9 2,8 2)),((7 3,7 4,8 4,8 3,7 3)),((9 3,9 4,10 4,10 3,9 3)))", + "MULTIPOLYGON(((9 2,8 2,8 3,9 3,10 2,9 2)),((7 5,8 5,9 6,9 4,8 4,7 3,6 3,6 4,6.5 3.5,7 4,6 4,7 5)))" +}; + +static std::string case_93_multi[2] = +{ + // iu/xi for intersection + "MULTIPOLYGON(((6 2,7 2,7 1,5 1,6 2)),((7 3,8 3,7.5 2.5,8 2,7 2,7 3)))", + "MULTIPOLYGON(((7 1,6 0,6 2,7 3,7 2,8 3,8 2,7 1)))" +}; + + +static std::string case_94_multi[2] = +{ + // iu/iu for union + "MULTIPOLYGON(((9 2,9 3,10 3,10 2,9 2)),((7 3,8 4,9 3,8 3,9 2,7 2,7 3)),((8 6,9 5,9 4,8 4,8 6)))", + "MULTIPOLYGON(((6 2,6 3,7 3,8 2,6 2)),((9 3,10 3,9 2,9 1,8 0,7 0,8 1,8 3,8.5 2.5,9 3)),((7 4,7 5,8 5,9 6,9 4,8 4,8 3,7 3,7 4)))" +}; + +static std::string case_95_multi[2] = +{ + // iu/iu for union + "MULTIPOLYGON(((0 8,1 8,1 7,0 7,0 8)),((2 8,2 9,2.5 8.5,3 9,3 7,2 7,2 8)),((1 9,1 10,2 9,1 8,1 9)))", + "MULTIPOLYGON(((1 7,0 7,0 8,1 8,2 7,1 7)),((2 9,1 9,1 10,2 10,3 9,4 9,4 8,2 8,2 9)))" +}; + +static std::string case_96_multi[2] = +{ + // iu/iu all collinear, for intersection/union + "MULTIPOLYGON(((8 2,9 3,9 2,8 2)),((8 1,9 2,9 1,10 1,10 0,8 0,8 1)))", + "MULTIPOLYGON(((9 0,9 1,10 0,9 0)),((8 1,8 2,9 2,9 1,8 1)))" +}; + +static std::string case_97_multi[2] = +{ + // ux/ux for union + "MULTIPOLYGON(((4 4,4 5,4.5 4.5,5 5,6 5,5 4,5 3,4 3,4 4)))", + "MULTIPOLYGON(((5 3,5 4,6 3,5 3)),((6 5,7 5,6 4,5 4,6 5)))" +}; + + +static std::string case_98_multi[2] = +{ + // ii/iu for intersection, solved by discarding iu (ordering not possible) + "MULTIPOLYGON(((2 0,3 1,3 0,2 0)),((2 2,2 3,1 3,1 4,2 4,3 3,3 4,5 2,4 2,4 1,3 1,3 2,2.5 1.5,3 1,2 1,2 2)))", + "MULTIPOLYGON(((4 2,4 3,5 2,4 2)),((1 0,0 0,0 2,4 2,4 1,2 1,2 0,1 0)),((3 3,4 4,4 3,3 2,3 3)))" +}; + +static std::string case_99_multi[2] = +{ + // iu/iu for intersection + "MULTIPOLYGON(((1 0,2 1,2 0,1 0)),((1 2,2 2,1.5 1.5,2 1,1 1,1 0,0 0,0 1,1 2)))", + "MULTIPOLYGON(((1 1,2 0,0 0,1 1)),((1 1,0 1,0 2,1 2,2 3,2 2,1 1)))" +}; + +static std::string case_100_multi[2] = +{ + // for intersection + "MULTIPOLYGON(((0 0,0 1,1 0,0 0)),((2 2,2 1,0 1,0 2,1 2,2 3,2 2)))", + "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((1 2,0 1,0 3,1 4,1 2)))" +}; + +static std::string case_101_multi[2] = +{ + // interior ring / union + "MULTIPOLYGON(((7 2,7 3,8 2,7 2)),((9 3,9 4,10 3,9 3)),((10 1,10 0,8 0,8 1,9 2,10 2,10 1)),((9 3,9 2,8 2,8 3,7 3,7 4,8 4,9 3)),((8 4,8 7,9 6,9 4,8 4)))", + "MULTIPOLYGON(((6 1,5 1,5 2,6 3,6 4,7 5,6 5,7 6,8 6,8 5,9 5,8 4,9 4,9 5,10 5,10 1,8 1,8 3,7 3,7 2,6 2,7 1,8 1,7 0,5 0,5 1,5.5 0.5,6 1),(8.5 2.5,9 2,9 3,8.5 2.5)))" +}; + +static std::string case_102_multi[2] = +{ + // interior ring 'fit' / union + "MULTIPOLYGON(((0 2,0 7,5 7,5 2,0 2),(4 3,4 6,1 6,2 5,1 5,1 4,3 4,4 3)),((3 4,3 5,4 5,3 4)),((2 5,3 6,3 5,2 4,2 5)))", + "MULTIPOLYGON(((0 2,0 7,5 7,5 2,0 2),(2 4,3 5,2 5,2 4),(4 4,3 4,3 3,4 4),(4 5,4 6,3 6,4 5)))" +}; + +static std::string case_103_multi[2] = +{ + // interior ring 'fit' (ix) / union / assemble + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,2 0,2 1,3 1,3 2,2 2,2 3,1 2,2 2,2 1,1 0,0 0)))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(2 1,2 2,1 1,2 1)))" +}; + +static std::string case_104_multi[2] = +{ + // interior ring 'fit' (ii) / union / assemble + "MULTIPOLYGON(((1 0,1 1,0 1,0 5,5 5,5 0,2 0,2 1,1 0),(2 2,3 3,2 3,2 2)))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(1 1,3 1,3 2,1 2,1 1)))" +}; + +static std::string case_105_multi[2] = +{ + // interior ring 'fit' () / union / assemble + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(2 2,3 2,3 3,1 3,2 2)))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(1 1,2 1,2 2,1 1),(2 1,3 1,3 2,2 1),(1 3,3 3,3 4,2 3,2 4,1 4,1 3)))" +}; + +static std::string case_106_multi[2] = +{ + // interior ring 'fit' () / union / assemble + "MULTIPOLYGON(((0 0,0 3,1 2,1 3,2 3,2 1,3 2,2 2,3 3,2 3,3 4,1 4,1 3,0 3,0 5,5 5,5 0,0 0)))", + "MULTIPOLYGON(((0 0,0 5,1 5,1 4,2 4,2 5,3 5,3 3,4 4,5 4,5 0,2 0,3 1,2 1,2 3,1 3,2 2,1.5 1.5,2 1,1 1,0 0)),((1 0,2 1,2 0,1 0)))" +}; + +static std::string case_107_multi[2] = +{ + // For CCW polygon reports a iu/iu problem. + "MULTIPOLYGON(((6 8,7 9,7 7,8 7,7 6,6 6,6 8)),((6.5 9.5,7 10,7 9,6 9,6 10,6.5 9.5)))", + "MULTIPOLYGON(((5 7,6 8,6 10,7 9,8 10,8 8,7 8,6 7,6 6,5 7)))" +}; + + +static std::string case_recursive_boxes_1[2] = +{ + // == 70 + // Used in blog. KEEP + "MULTIPOLYGON(((1 0,0 0,0 1,1 1,1 2,0 2,0 4,2 4,2 5,3 5,3 6,1 6,1 5,0 5,0 10,9 10,9 9,7 9,7 8,6 8,6 7,8 7,8 6,9 6,9 4,8 4,8 5,7 5,7 6,6 6,6 5,5 5,5 4,4 4,4 3,5 3,5 2,7 2,7 3,6 3,6 4,8 4,8 3,10 3,10 0,6 0,6 1,5 1,5 0,1 0),(4 7,4 9,3 9,3 7,4 7),(8 1,9 1,9 2,8 2,8 1)),((10 7,10 6,9 6,9 7,8 7,8 8,9 8,9 9,10 9,10 7)))", + "MULTIPOLYGON(((1 0,0 0,0 7,2 7,2 6,5 6,5 5,4 5,4 4,5 4,5 3,7 3,7 2,6 2,6 0,1 0),(2 1,2 2,3 2,3 3,1 3,1 1,2 1)),((7 0,7 2,10 2,10 0,9 0,9 1,8 1,8 0,7 0)),((6 4,6 6,5 6,5 7,6 7,6 8,5 8,5 7,3 7,3 9,2 9,2 8,1 8,1 10,4 10,4 9,6 9,6 10,10 10,10 9,9 9,9 8,10 8,10 6,9 6,9 5,10 5,10 3,7 3,7 4,6 4),(7 7,7 6,8 6,8 7,7 7)))" +}; + +static std::string case_recursive_boxes_2[2] = +{ + // Traversal problem; Many ii-cases -> formerly caused "Endless loop" + // So it appears that there might be more decisions than intersection points + "MULTIPOLYGON(((1 0,0 0,0 4,1 4,1 5,0 5,0 10,3 10,3 9,4 9,4 10,6 10,6 9,5 9,5 8,6 8,6 9,7 9,7 10,10 10,10 0,1 0),(7 6,8 6,8 7,9 7,9 8,8 8,8 7,7 7,7 6),(9 1,9 2,8 2,8 1,9 1)))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,8 0,8 1,7 1,7 0,0 0),(7 3,6 3,6 2,7 2,7 3),(6 7,7 7,7 8,6 8,6 7)))" +}; + + +static std::string case_recursive_boxes_3[2] = +{ + // Previously a iu/ux problem causing union to fail. + // For CCW polygon it also reports a iu/iu problem. + // KEEP + "MULTIPOLYGON(((8 3,9 4,9 3,8 3)),((5 9,5 10,6 10,5 9)),((2 0,2 1,3 0,2 0)),((2 5,2 6,3 6,3 5,2 5)),((2 2,1 2,1 3,2 3,3 2,3 1,2 1,2 2)),((6 8,7 9,7 7,8 7,7 6,6 6,6 8)),((4 6,5 7,5 6,4 6)),((4 8,4 9,5 9,5 8,4 8)),((0 3,1 4,1 3,0 3)),((8 7,9 8,9 7,8 7)),((9 6,9 7,10 7,9 6)),((7 0,8 1,8 0,7 0)),((0 4,0 5,1 5,1 4,0 4)),((4 2,5 3,5 2,4 1,4 2)),((4 10,4 9,2 9,3 10,4 10)),((5 2,6 3,7 3,7 2,6 2,6 1,5 0,5 2)),((5 3,4 3,4 4,2 4,4 6,4 5,4.5 4.5,6 6,6 5,7 4,5 4,5 3)),((10 2,9 1,9 3,10 2)),((8 4,7 4,8 5,7 5,7 6,9 6,9 5,10 5,10 4,8 4)),((1 7,0 7,0 8,1 8,1 7)),((1 10,2 10,1 9,0 9,0 10,1 10)),((6.5 9.5,7 10,7 9,6 9,6 10,6.5 9.5)),((8 8,8 9,10 9,9 8,8 8)))", + "MULTIPOLYGON(((0 7,0 8,1 8,1 7,0 7)),((5 3,4 3,4 4,6 4,6 3,7 3,6 2,5 2,5 3)),((8 2,8 3,9 2,8 2)),((1 1,2 2,2 1,1 1)),((2 1,3 1,2 0,1 0,2 1)),((2 3,3 4,3 3,2 3)),((1 9,2 8,1 8,1 9)),((2 10,2 9,1 9,1 10,2 10)),((9 7,9 8,10 8,10 7,9 7)),((6 0,6 1,7 1,7 0,6 0)),((8 0,9 1,9 0,8 0)),((1 6,1 5,0 5,1 6)),((0 2,1 1,0 1,0 2)),((1 3,2 3,2 2,1 2,1 3)),((5 1,5 0,4 0,4 1,3 1,4 2,5 2,6 1,5 1)),((1 3,0 3,0 4,1 4,1 3)),((3 6,4 5,2 5,3 6)),((9 2,10 2,10 1,9 1,9 2)),((7 5,6 4,6 5,7 6,8 6,8 5,7 5)),((7 4,8 5,8.5 4.5,9 5,9 4,8 4,8.5 3.5,9 4,10 3,7 3,7 4)),((1 6,1 7,3 7,3 8,4 7,5 7,6 8,6 10,7 9,8 10,9 10,9 9,8 9,8 8,7 8,6 7,6 6,1 6)))" +}; + + +static std::string case_recursive_boxes_4[2] = +{ + // Occurred after refactoring assemble + "MULTIPOLYGON(((9 3,10 4,10 3,9 3)),((9 9,10 10,10 9,9 9)),((0 1,0 3,1 4,0 4,0 5,1 6,0 6,0 8,1 9,1 8,2 9,2 7,1.5 6.5,2.5 5.5,3 6,3 5,4 6,2 6,2 7,3 8,2 8,3 9,0 9,0 10,6 10,5.5 9.5,6 9,6 10,7 10,7.5 9.5,8 10,8 9,7 9,7 8,6 8,6.5 7.5,7 8,8 8,8 9,9 9,9.5 8.5,10 9,10 8,9.5 7.5,10 7,10 5,8 5,8 4,7 3,7 2,8 3,8 4,9 5,9 3,10 2,10 1,8 1,8.5 0.5,9 1,10 0,4 0,4 1,3 1,3 0,1 0,1 1,0 0,0 1),(4 2,4.5 1.5,5 2,5 4,4.5 3.5,5 3,4 3,4 2),(3 3,4 4,2 4,2.5 3.5,3 4,3 3),(6 4,6.5 3.5,7 4,6 4),(5 7,5 9,4 9,4 8,5 7)))", + "MULTIPOLYGON(((1 0,2 1,2 0,1 0)),((7 9,7 10,8 10,7 9)),((1 0,0 0,0 3,1 3,2 2,2 3,1 3,1 4,2 4,2 5,1 4,0 4,0 8,1 7,1 6,2 7,1 7,1 9,0 9,0 10,7 10,6 9,6.5 8.5,7 9,8 9,9 8,8 8,9 7,9 6,10 7,10 5,9 5,9 4,10 5,10 0,7 0,8 1,7 1,6 0,3 0,3 1,1 1,1 0),(5 1,5.5 0.5,6 1,6 2,6.5 1.5,7 2,8 2,8 4,7 3,6 3,6 2,5 2,6 1,5 1),(4 4,5 4,5 5,4 4),(4 6,4 7,3 7,2 6,3 6,3 7,4 6),(6 5,6.5 4.5,7 5,6 5,7 6,7 7,6 7,6 5),(3.5 7.5,4 8,4 9,3 8,3.5 7.5)),((9 8,9 9,8 9,9 10,10 10,10 8,9 8)))" +}; + +static std::string pie_21_7_21_0_3[2] = +{ + "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,3828 2144,3690 1812,3472 1527,3187 1309,2855 1171,2499 1125,2144 1171,1812 1309,1527 1527,1309 1812,1171 2144,1125 2499,1171 2855,1309 3187,2500 2500)))", + "MULTIPOLYGON(((2500 2500,1704 3295,1937 3474,2208 3586,2499 3625,2791 3586,3062 3474,3295 3295,2500 2500)),((2500 2500,3586 2791,3625 2500,3586 2208,2500 2500)))" +}; + +static std::string pie_23_19_5_0_2[2] = +{ + "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,3828 2144,3690 1812,3472 1527,3187 1309,2855 1171,2499 1125,2144 1171,1812 1309,1527 1527,1309 1812,1171 2144,1125 2499,1171 2855,1309 3187,1527 3472,1812 3690,2500 2500)))", + "MULTIPOLYGON(((2500 2500,3586 2791,3625 2500,3586 2208,3474 1937,3295 1704,3062 1525,2791 1413,2499 1375,2208 1413,1937 1525,1704 1704,1525 1937,1413 2208,1375 2500,1413 2791,1525 3062,1704 3295,1937 3474,2208 3586,2500 2500)),((2500 2500,2791 3586,3062 3474,2500 2500)))" +}; + +static std::string pie_7_14_5_0_7[2] = +{ + "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,2500 2500)))", + "MULTIPOLYGON(((2500 2500,3586 2791,3625 2500,3586 2208,3474 1937,3295 1704,3062 1525,2791 1413,2499 1375,2208 1413,1937 1525,1704 1704,1525 1937,1413 2208,1375 2500,2500 2500)),((2500 2500,1525 3062,1704 3295,1937 3474,2208 3586,2499 3625,2791 3586,3062 3474,2500 2500)))" +}; + +static std::string pie_16_16_9_0_2[2] = +{ + "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,3828 2144,3690 1812,3472 1527,3187 1309,2855 1171,2499 1125,2144 1171,1812 1309,1527 1527,2500 2500)))", + "MULTIPOLYGON(((2500 2500,3295 1704,3062 1525,2791 1413,2499 1375,2208 1413,1937 1525,1704 1704,1525 1937,1413 2208,1375 2500,1413 2791,1525 3062,1704 3295,1937 3474,2208 3586,2499 3625,2500 2500)),((2500 2500,3062 3474,3295 3295,2500 2500)))" +}; + +static std::string pie_7_2_1_0_15[2] = +{ + "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,2500 2500)))", + "MULTIPOLYGON(((2500 2500,2791 3586,3062 3474,2500 2500)),((2500 2500,3474 3062,3586 2791,3625 2500,3586 2208,3474 1937,3295 1704,3062 1525,2791 1413,2499 1375,2208 1413,1937 1525,1704 1704,1525 1937,1413 2208,1375 2500,2500 2500)))" +}; + +// Case, not literally on this list but derived, to mix polygon/multipolygon in call to difference +static std::string ggl_list_20111025_vd[4] = + { + "POLYGON((0 0,0 4,4 0,0 0))", + "POLYGON((10 0,10 5,15 0,10 0))", + "MULTIPOLYGON(((0 0,0 4,4 0,0 0)))", + "MULTIPOLYGON(((10 0,10 5,15 0,10 0)))" + }; + +// Same, mail with other case with text "Say the MP is the 2 squares below and P is the blue-ish rectangle." +static std::string ggl_list_20111025_vd_2[2] = + { + "POLYGON((5 0,5 4,8 4,8 0,5 0))", + "MULTIPOLYGON(((0 0,0 2,2 2,2 0,0 0)),((4 0,4 2,6 2,6 0,4 0)))" + }; + +// Mail of h2 indicating that reversed order (in second polygon) has ix/ix problems +static std::string ggl_list_20120915_h2[3] = + { + "MULTIPOLYGON(((-2 5, -1 5, 0 5, 2 5, 2 -2, 1 -2, 1 -1, 0 -1,0 0, -1 0, -2 0, -2 5)))", + "MULTIPOLYGON(((0 0, 1 0, 1 -1, 0 -1, 0 0)), ((-1 5, 0 5, 0 0, -1 0, -1 5)))", + "MULTIPOLYGON(((-1 5, 0 5, 0 0, -1 0, -1 5)), ((0 0, 1 0, 1 -1, 0 -1, 0 0)))" + }; + +// Mail of volker, about another problem, but this specific example is causing two-point inner rings polygons which should be discarded +// (condition of num_points in detail/overlay/convert_ring.hpp) +static std::string ggl_list_20120221_volker[2] = + { + "MULTIPOLYGON(((1032 2130,1032 1764,2052 2712,1032 2130)),((3234 2580,2558 2690,3234 2532,3234 2580)),((2558 2690,2136 2790,2052 2712,2136 2760,2558 2690)))", + "MULTIPOLYGON(((3232 2532.469945355191,2136 2790,1032 1764,1032 1458,1032 1212,2136 2328,3232 2220.196721311475,3232 1056,1031 1056,1031 2856,3232 2856,3232 2532.469945355191),(3232 2412.426229508197,2136 2646,3232 2412.426229508197)))" + }; + +static std::string ggl_list_20140212_sybren[2] = + { + "MULTIPOLYGON(((0.494062 0.659354,0.471383 0.64654,0.446639 0.616561,0.47291 0.61171,0.495396 0.625263,0.494964 0.679709,0.494062 0.659354)))", + "MULTIPOLYGON(((0.4951091661995328 0.6614133543986973,0.495396 0.625263,0.50092 0.6492750000000001,0.494964 0.679709,0.477258 0.698703,0.4951091661995328 0.6614133543986973)),((0.452167 0.706562,0.433379 0.696888,0.442673 0.65792,0.464729 0.671387,0.452167 0.706562)))" + }; + +static std::string ticket_9081[2] = + { + "MULTIPOLYGON(((0.5489109414010371 0.5774835110050927,0.4099611282054447 0.4644351568071598,0.4294011278595494 0.4843224236729239,0.4205359995313906 0.5115225580860201,0.4441572412013468 0.5184999851878852,0.5489109414010371 0.5774835110050927)),((0.562085028126843 0.5882018328808966,0.5644349663154944 0.591180348361206,0.568218114394707 0.5970364466647042,0.5838690879677763 0.6212632646137447,0.5873787029417971 0.6412877041753083,0.468699602592386 0.5866280231830688,0.4171010902425981 0.5220616039851281,0.4059124592966251 0.5563907478354578,0.3909547828925878 0.6022841397455458,0.520859401226844 0.9508041627246925,0.8595233008819849 0.8301950132755517,0.562085028126843 0.5882018328808966)))", + "MULTIPOLYGON(((0.2099392122251989 0.492066865490789,0.1124301889095737 0.5124668111209448,0.3306914939102383 0.6126684490171914,0.2099392122251989 0.492066865490789)),((0.5885369465145437 0.6478961722242873,0.5342320718598281 0.6686303269145104,0.5619623880692838 0.7033299168703926,0.5945761233023867 0.6823532655194001,0.5885369465145437 0.6478961722242873)),((0.5570738195183501 0.6001870087680015,0.5429714753344335 0.6231021858940831,0.5880357506342242 0.6450365518134291,0.5838690879677763 0.6212632646137447,0.568218114394707 0.5970364466647042,0.5570738195183501 0.6001870087680015)),((0.5498478321815098 0.5029279381860542,0.608691671498764 0.5163121433149205,0.5636607291345047 0.5894838094559455,0.8595233008819849 0.8301950132755517,0.8285440738598029 0.8412277162756114,0.9591357158116398 0.9011810663167211,0.8572649311807611 0.3566393017365032,0.5965816668471951 0.4111770689940296,0.5498478321815098 0.5029279381860542)),((0.3984249865018206 0.4526335964808558,0.3621206996557855 0.4602288471829723,0.4183516736935784 0.4730187483833363,0.4099611282054451 0.4644351568071601,0.3984249865018206 0.4526335964808558)))" + }; + + +#endif // BOOST_GEOMETRY_TEST_MULTI_OVERLAY_CASES_HPP diff --git a/libs/geometry/test/algorithms/overlay/multi_overlay_common.hpp b/libs/geometry/test/algorithms/overlay/multi_overlay_common.hpp new file mode 100644 index 000000000..6a49c300d --- /dev/null +++ b/libs/geometry/test/algorithms/overlay/multi_overlay_common.hpp @@ -0,0 +1,40 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) +// Unit Test + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2012 Bruno Lalande, Paris, France. +// 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 GEOMETRY_TEST_MULTI_OVERLAY_COMMON_HPP +#define GEOMETRY_TEST_MULTI_OVERLAY_COMMON_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> +//#include <boost/geometry/multi/io/svg/write_svg.hpp> + + + +template <typename P, typename Functor, typename T> +void test_all(std::vector<T> const& expected, double precision = 0.01) +{ + typename boost::range_const_iterator<std::vector<T> >::type iterator + = boost::begin(expected); + + typedef bg::model::multi_polygon<bg::model::polygon<P> > mp; + typedef bg::model::box<P> box; + + BOOST_ASSERT(iterator != boost::end(expected)); + test_overlay<mp, mp, Functor>("1", *iterator, + "MULTIPOLYGON(((0 1,2 5,5 3,0 1)),((1 1,5 2,5 0,1 1)))", + "MULTIPOLYGON(((3 0,0 3,4 5,3 0)))", precision); + iterator++; +} + + +#endif // GEOMETRY_TEST_MULTI_OVERLAY_COMMON_HPP diff --git a/libs/geometry/test/algorithms/overlay/multi_traverse.cpp b/libs/geometry/test/algorithms/overlay/multi_traverse.cpp new file mode 100644 index 000000000..7cab06c96 --- /dev/null +++ b/libs/geometry/test/algorithms/overlay/multi_traverse.cpp @@ -0,0 +1,448 @@ +// 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) + + +//#define BOOST_GEOMETRY_DEBUG_ENRICH +//#define BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER + +// Include the single-geometry version +#define BOOST_GEOMETRY_TEST_MULTI +#include <algorithms/overlay/traverse.cpp> + + + +#include <boost/geometry/multi/core/closure.hpp> +#include <boost/geometry/multi/core/geometry_id.hpp> +#include <boost/geometry/multi/core/point_order.hpp> +#include <boost/geometry/multi/core/ring_type.hpp> + +#include <boost/geometry/multi/algorithms/correct.hpp> +#include <boost/geometry/multi/algorithms/envelope.hpp> +#include <boost/geometry/multi/algorithms/num_points.hpp> +#include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp> +#include <boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp> +#include <boost/geometry/multi/algorithms/detail/sections/range_by_section.hpp> +#include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp> + +#include <boost/geometry/multi/geometries/multi_linestring.hpp> +#include <boost/geometry/multi/geometries/multi_polygon.hpp> + +#include <boost/geometry/multi/views/detail/range_type.hpp> + +#include <boost/geometry/multi/io/wkt/read.hpp> + + +#include "multi_overlay_cases.hpp" + + + +template <typename MultiPolygon, bool Reverse> +void test_geometries() +{ + namespace ov = bg::detail::overlay; + + typedef test_traverse + < + MultiPolygon, MultiPolygon, + ov::operation_intersection, Reverse, Reverse + > test_traverse_intersection; + typedef test_traverse + < + MultiPolygon, MultiPolygon, + ov::operation_union, Reverse, Reverse + > test_traverse_union; + + // Intersections: + test_traverse_intersection::apply + ( + "simplex", 2, 6.42, + case_multi_simplex[0], case_multi_simplex[1] + ); + + test_traverse_intersection::apply + ( + "case_65_multi", 1, 1, + case_65_multi[0], case_65_multi[1] + ); + test_traverse_intersection::apply + ( + "case_66_multi", 1, 1, + case_66_multi[0], case_66_multi[1] + ); + + test_traverse_intersection::apply + ( + "case_67_multi", 1, 1, + case_67_multi[0], case_67_multi[1] + ); + test_traverse_intersection::apply + ( + "case_69_multi", 1, 1, + case_69_multi[0], case_69_multi[1] + ); + + test_traverse_intersection::apply + ( + "case_71_multi", 2, 2, + case_71_multi[0], case_71_multi[1] + ); + + // #72, note that it intersects into 2 shapes, + // the third one is done by assemble (see intersection #72) + test_traverse_intersection::apply + ( + "case_72_multi", 2, 1.35, + case_72_multi[0], case_72_multi[1] + ); + + test_traverse_intersection::apply + ( + "case_73_multi", 2, 2, + case_73_multi[0], case_73_multi[1] + ); + test_traverse_intersection::apply + ( + "case_74_multi", 2, 3, + case_74_multi[0], case_74_multi[1] + ); + test_traverse_intersection::apply + ( + "case_75_multi", 1, 1, + case_75_multi[0], case_75_multi[1] + ); + test_traverse_intersection::apply + ( + "case_77_multi", 5, 9, + case_77_multi[0], case_77_multi[1] + ); + test_traverse_intersection::apply + ( + "case_78_multi", 2, 22, // Went from 3 to 2 by get_turns / partition + case_78_multi[0], case_78_multi[1] + ); + + test_traverse_intersection::apply + ( + "case_80_multi", 1, 0.5, + case_80_multi[0], case_80_multi[1] + ); + test_traverse_intersection::apply + ( + "case_81_multi", 1, 0.25, + case_81_multi[0], case_81_multi[1] + ); + test_traverse_intersection::apply + ( + "case_83_multi", 3, 1.25, + case_83_multi[0], case_83_multi[1] + ); + + test_traverse_intersection::apply + ( + "case_91_multi", 2, 1.0, + case_91_multi[0], case_91_multi[1] + ); + test_traverse_intersection::apply + ( + "case_92_multi", 3, 1.5, + case_92_multi[0], case_92_multi[1] + ); + test_traverse_intersection::apply + ( + "case_93_multi", 2, 1.25, + case_93_multi[0], case_93_multi[1] + ); + test_traverse_intersection::apply + ( + "case_96_multi", 1, 0.5, + case_96_multi[0], case_96_multi[1] + ); + test_traverse_intersection::apply + ( + "case_98_multi", 4, 3.0, + case_98_multi[0], case_98_multi[1] + ); + + test_traverse_intersection::apply + ( + "case_99_multi", 3, 1.75, + case_99_multi[0], case_99_multi[1] + ); + test_traverse_intersection::apply + ( + "case_100_multi", 2, 1.5, + case_100_multi[0], case_100_multi[1] + ); + + + test_traverse_intersection::apply + ( + "case_recursive_boxes_2", 1, 91, + case_recursive_boxes_2[0], case_recursive_boxes_2[1] + ); + test_traverse_intersection::apply + ( + "case_107_multi", 2, 1.5, + case_107_multi[0], case_107_multi[1] + ); + test_traverse_intersection::apply + ( + "case_recursive_boxes_3", 19, 12.5, + case_recursive_boxes_3[0], case_recursive_boxes_3[1] + ); + + // Unions + + + test_traverse_union::apply + ( + "simplex", 1, 14.58, + case_multi_simplex[0], case_multi_simplex[1] + ); + + test_traverse_union::apply + ( + "case_61_multi", 1, 4, + case_61_multi[0], case_61_multi[1] + ); + test_traverse_union::apply + ( + "case_62_multi", 1, 1 /*UU 2, 2 */, + case_62_multi[0], case_62_multi[1] + ); + test_traverse_union::apply + ( + "case_63_multi", 1, 1 /*UU 2, 2 */, + case_63_multi[0], case_63_multi[1] + ); + test_traverse_union::apply + ( + "case_64_multi", 1, 3, + case_64_multi[0], case_64_multi[1] + ); + + test_traverse_union::apply + ( + "case_66_multi", 1, 4 /*UU 3, 7 */, + case_66_multi[0], case_66_multi[1] + ); + test_traverse_union::apply + ( + "case_68_multi", 1, 4 /*UU 2, 5 */, + case_68_multi[0], case_68_multi[1] + ); + // 71: single-polygon generates 2 shapes, multi-polygon + // generates 1 shape, both are self-tangent and OK + test_traverse_union::apply + ( + "case_71_multi", 1, 9, + case_71_multi[0], case_71_multi[1] + ); + + test_traverse_union::apply + ( + "case_72_multi", 1, 10.65, + case_72_multi[0], case_72_multi[1] + ); + + test_traverse_union::apply + ( + "case_73_multi", 1, 3, + case_73_multi[0], case_73_multi[1] + ); + test_traverse_union::apply + ( + "case_74_multi", 2, 17, + case_74_multi[0], case_74_multi[1] + ); + test_traverse_union::apply + ( + "case_75_multi", 1, 1 /*UU 5, 5 */, + case_75_multi[0], case_75_multi[1] + ); + test_traverse_union::apply + ( + "case_76_multi", 2, 5 /*UU 6, 6 */, + case_76_multi[0], case_76_multi[1] + ); + + test_traverse_union::apply + ( + "case_80_multi", 1, 9.25, + case_80_multi[0], case_80_multi[1] + ); + test_traverse_union::apply + ( + "case_81_multi", 1, 3.25, + case_81_multi[0], case_81_multi[1] + ); + test_traverse_union::apply + ( + "case_82_multi", 3, 4, + case_82_multi[0], case_82_multi[1] + ); + test_traverse_union::apply + ( + "case_84_multi", 1, 4, + case_84_multi[0], case_84_multi[1] + ); + test_traverse_union::apply + ( + "case_85_multi", 1, 3.5, + case_85_multi[0], case_85_multi[1] + ); + test_traverse_union::apply + ( + "case_86_multi", 1, 4, + case_86_multi[0], case_86_multi[1] + ); + test_traverse_union::apply + ( + "case_87_multi", 1, 6, + case_87_multi[0], case_87_multi[1] + ); + test_traverse_union::apply + ( + "case_88_multi", 2, 4, + case_88_multi[0], case_88_multi[1] + ); + test_traverse_union::apply + ( + "case_89_multi", 1, 6, + case_89_multi[0], case_89_multi[1] + ); + test_traverse_union::apply + ( + "case_90_multi", 1, 7.5, + case_90_multi[0], case_90_multi[1] + ); + test_traverse_union::apply + ( + "case_92_multi", 2, 6.25, + case_92_multi[0], case_92_multi[1] + ); + test_traverse_union::apply + ( + "case_94_multi", 1, 10.0, + case_94_multi[0], case_94_multi[1] + ); + test_traverse_union::apply + ( + "case_95_multi", 2, 6.5, + case_95_multi[0], case_95_multi[1] + ); + test_traverse_union::apply + ( + "case_96_multi", 1, 3.5, + case_96_multi[0], case_96_multi[1] + ); + test_traverse_union::apply + ( + "case_97_multi", 1, 3.75, + case_97_multi[0], case_97_multi[1] + ); + test_traverse_union::apply + ( + "case_101_multi", 1, 22.25, + case_101_multi[0], case_101_multi[1] + ); + test_traverse_union::apply + ( + "case_102_multi", 3, 24.25, + case_102_multi[0], case_102_multi[1] + ); + test_traverse_union::apply + ( + "case_103_multi", 1, 25, + case_103_multi[0], case_103_multi[1] + ); + test_traverse_union::apply + ( + "case_104_multi", 1, 25, + case_104_multi[0], case_104_multi[1] + ); + test_traverse_union::apply + ( + "case_105_multi", 1, 25, + case_105_multi[0], case_105_multi[1] + ); + test_traverse_union::apply + ( + "case_106_multi", 1, 25, + case_106_multi[0], case_106_multi[1] + ); + + + test_traverse_union::apply + ( + "case_recursive_boxes_1", 2, 97, + case_recursive_boxes_1[0], case_recursive_boxes_1[1] + ); + + test_traverse_union::apply + ( + "case_recursive_boxes_3", 7, 49.5, + case_recursive_boxes_3[0], case_recursive_boxes_3[1] + ); + + test_traverse_intersection::apply + ( + "pie_21_7_21_0_3", 2, 818824.56678, + pie_21_7_21_0_3[0], pie_21_7_21_0_3[1] + ); + + test_traverse_intersection::apply + ( + "pie_23_19_5_0_2", 2, 2948602.3911823, + pie_23_19_5_0_2[0], pie_23_19_5_0_2[1] + ); + test_traverse_intersection::apply + ( + "pie_7_14_5_0_7", 2, 490804.56678, + pie_7_14_5_0_7[0], pie_7_14_5_0_7[1] + ); + test_traverse_intersection::apply + ( + "pie_16_16_9_0_2", 2, 1146795, + pie_16_16_9_0_2[0], pie_16_16_9_0_2[1] + ); + test_traverse_intersection::apply + ( + "pie_7_2_1_0_15", 2, 490585.5, + pie_7_2_1_0_15[0], pie_7_2_1_0_15[1] + ); + +} + +template <typename T> +void test_all() +{ + typedef bg::model::point<T, 2, bg::cs::cartesian> point_type; + + typedef bg::model::multi_polygon + < + bg::model::polygon<point_type> + > multi_polygon; + + typedef bg::model::multi_polygon + < + bg::model::polygon<point_type, false> + > multi_polygon_ccw; + + test_geometries<multi_polygon, false>(); + test_geometries<multi_polygon_ccw, true>(); +} + + +int test_main(int, char* []) +{ + test_all<double>(); + + return 0; +} diff --git a/libs/geometry/test/algorithms/overlay/overlay_cases.hpp b/libs/geometry/test/algorithms/overlay/overlay_cases.hpp index 9951f7d70..1a28e0c06 100644 --- a/libs/geometry/test/algorithms/overlay/overlay_cases.hpp +++ b/libs/geometry/test/algorithms/overlay/overlay_cases.hpp @@ -1,7 +1,13 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) // Unit Test // -// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. + +// 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 + // 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) @@ -795,6 +801,67 @@ static std::string ticket_9563[2] = "POLYGON((16.4030230586814020 21.414709848078967, 17.7828326880709360 18.936596729241124, 17.3451877762964410 14.867777311013885, 15.2073549240394820 10.298488470659295, 11.9421647176150340 6.4530674629349125, 8.4245222359685457 4.3618917414181650, 5.5969769413185944 4.5852901519210292, 4.2171673119290620 7.0634032707588670, 4.6548122237035567 11.132222688986115, 6.7926450759605128 15.701511529340699, 10.0578352823849570 19.546932537065082, 13.5754777640314510 21.638108258581831, 16.4030230586814020 21.414709848078967))" }; +static std::string ticket_10108_a[2] = + { + "POLYGON((-0.85012528418186883439 0.66468648958045217778 , -1.0190633474909247536 0.58375169123203618504 , -0.81735787096893253167 0.85208889314502478385 , -0.85012528418186883439 0.66468648958045217778))", + "POLYGON((-1.0898104946524889147 1.0651111163194444398 , -1.0543813205484939832 0.82438792455048248708 , -0.81735787088719669136 0.8520888930811181261 , -1.0898104946524889147 1.0651111163194444398))" + }; +static std::string ticket_10108_b[2] = + { + "POLYGON((818.61020100991334 686.40744987236633, 818.94520828641623 714.37814489343316, 857.67308553468195 713.83138513092547, 857.33807828316174 685.94987141847253, 818.61020100991334 686.40744987236633))", + "POLYGON((857.33807828316174 685.94987141847253, 857.64395373587263 711.40684463430682, 910.49336536223325 710.67130033421233, 910.18750000000000 685.32544378698219, 857.33807828316174 685.94987141847253))" + }; +// Rescaling problem (fixed in 1.58) +static std::string ticket_10747_a[2] = + { + "POLYGON((0 33554432,0 0,33554432 0,33554432 33554432,0 33554432))", + "POLYGON((25165824 25165824,41943040 25165824,41943040 41943040,25165824 41943040,25165824 25165824))" + }; +static std::string ticket_10747_b[2] = + { + "POLYGON((0 335544320,0 0,335544320 0,335544320 335544320,0 335544320))", + "POLYGON((251658240 251658240,419430400 251658240,419430400 419430400,251658240 419430400,251658240 251658240))" + }; +static std::string ticket_10747_c[2] = + { + "POLYGON((0 16777216,0 0,16777216 0,16777216 16777216,0 16777216))", + "POLYGON((12582912 12582912,20971520 12582912,20971520 20971520,12582912 20971520,12582912 12582912))" + }; +static std::string ticket_10747_d[2] = + { + "POLYGON((0 3355443,0 0,3355443 0,3355443 3355443,0 3355443))", + "POLYGON((2516582 2516582,4194304 2516582,4194304 4194304,2516582 4194304,2516582 2516582))" + }; +static std::string ticket_10747_e[2] = + { + "POLYGON((0 0.00000033554432,0 0,0.00000033554432 0,0.00000033554432 0.00000033554432,0 0.00000033554432))", + "POLYGON((0.00000025165824 0.00000025165824,0.00000041943040 0.00000025165824,0.00000041943040 0.00000041943040,0.00000025165824 0.00000041943040,0.00000025165824 0.00000025165824))" + }; + +static std::string ticket_10658[2] = + { + "POLYGON((516 1608,1308 1932,2094 2466,2094 32767,516 32767,516 1608))", + "POLYGON((516 2484,1308 3066,2094 3150,2094 32767,516 32767,516 2484))" + }; + +static std::string ticket_10835[3] = + { + "MULTILINESTRING((5239 2113,1020 2986))", + "POLYGON((5233 2113,5200 2205,1020 2205,1020 2022,5200 2022))", + "POLYGON((5233 2986,5200 3078,1020 3078,1020 2895,5200 2895))" + }; + +static std::string ticket_10868[2] = + { + "POLYGON((42817136 -3774506,43029074 -3929862,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575,35332375 2413654,35725796 2024148))", + "POLYGON((-33386239 -33721784,33721785 -33386239,33386240 33721785,-33721784 33386240))" + }; + +static std::string ticket_11121[2] = + { + "POLYGON((-8042 -1485,-8042 250,-8042 250,15943 254,15943 -1485,-8042 -1485))", + "POLYGON((-7901 -1485,-7901 529,-7901 529,15802 544,15802 -1485,-7901 -1485))" + }; #endif // BOOST_GEOMETRY_TEST_OVERLAY_CASES_HPP diff --git a/libs/geometry/test/algorithms/overlay/relative_order.cpp b/libs/geometry/test/algorithms/overlay/relative_order.cpp index 18c51e2b3..c9c200d85 100644 --- a/libs/geometry/test/algorithms/overlay/relative_order.cpp +++ b/libs/geometry/test/algorithms/overlay/relative_order.cpp @@ -28,7 +28,7 @@ template <typename P, typename T> -void test_with_point(std::string const& caseid, +void test_with_point(std::string const& /*caseid*/, T pi_x, T pi_y, T pj_x, T pj_y, T ri_x, T ri_y, T rj_x, T rj_y, T si_x, T si_y, T sj_x, T sj_y, diff --git a/libs/geometry/test/algorithms/overlay/select_rings.cpp b/libs/geometry/test/algorithms/overlay/select_rings.cpp index acc3e5011..89b58ff51 100644 --- a/libs/geometry/test/algorithms/overlay/select_rings.cpp +++ b/libs/geometry/test/algorithms/overlay/select_rings.cpp @@ -31,12 +31,10 @@ template typename Geometry1, typename Geometry2, bg::overlay_type OverlayType, - typename RingIdVector, - typename WithinVector + typename RingIdVector > void test_geometry(std::string const& wkt1, std::string const& wkt2, - RingIdVector const& expected_ids, - WithinVector const& expected_withins) + RingIdVector const& expected_ids) { typedef bg::detail::overlay::ring_properties<typename bg::point_type<Geometry1>::type> properties; @@ -48,24 +46,21 @@ void test_geometry(std::string const& wkt1, std::string const& wkt2, typedef std::map<bg::ring_identifier, properties> map_type; map_type selected; - std::map<bg::ring_identifier, int> empty; + std::map<bg::ring_identifier, bg::detail::overlay::ring_turn_info> empty; - bg::detail::overlay::select_rings<OverlayType>(geometry1, geometry2, empty, selected, true); + bg::detail::overlay::select_rings<OverlayType>(geometry1, geometry2, empty, selected); BOOST_CHECK_EQUAL(selected.size(), expected_ids.size()); - BOOST_CHECK_EQUAL(selected.size(), expected_withins.size()); if (selected.size() <= expected_ids.size()) { BOOST_AUTO(eit, expected_ids.begin()); - BOOST_AUTO(wit, expected_withins.begin()); - for(typename map_type::const_iterator it = selected.begin(); it != selected.end(); ++it, ++eit, ++wit) + for(typename map_type::const_iterator it = selected.begin(); it != selected.end(); ++it, ++eit) { bg::ring_identifier const ring_id = it->first; BOOST_CHECK_EQUAL(ring_id.source_index, eit->source_index); BOOST_CHECK_EQUAL(ring_id.multi_index, eit->multi_index); BOOST_CHECK_EQUAL(ring_id.ring_index, eit->ring_index); - BOOST_CHECK_EQUAL(it->second.within_code, *wit); } } } @@ -87,18 +82,7 @@ void test_all() (rid(0,-1, 1)) (rid(0,-1, 3)) (rid(1,-1, 1)) - (rid(1,-1, 2)), - - boost::assign::list_of - (-1) - (-1) - (-1) - (-1) - (-1) - (-1) - ); - - //boost::assign::tuple_list_of(0,-1,-1,-1)(0,-1,0,-1)(0,-1,1,-1)(0,-1,3,-1)(1,-1,1,-1)(1,-1,2,-1)); + (rid(1,-1, 2))); test_geometry<bg::model::polygon<P>, bg::model::polygon<P>, bg::overlay_intersection>( winded[0], winded[1], @@ -106,17 +90,7 @@ void test_all() (rid(0,-1, 2)) (rid(1,-1,-1)) (rid(1,-1, 0)) - (rid(1,-1, 3)), - - boost::assign::list_of - (1) - (1) - (1) - (1) - ); - - - //boost::assign::tuple_list_of(0,-1,2,1)(1,-1,-1,1)(1,-1,0,1)(1,-1,3,1)); + (rid(1,-1, 3))); } diff --git a/libs/geometry/test/algorithms/overlay/self_intersection_points.cpp b/libs/geometry/test/algorithms/overlay/self_intersection_points.cpp index 24c51df57..9825018bf 100644 --- a/libs/geometry/test/algorithms/overlay/self_intersection_points.cpp +++ b/libs/geometry/test/algorithms/overlay/self_intersection_points.cpp @@ -47,7 +47,7 @@ static void test_self_intersection_points(std::string const& case_id, int expected_count, Geometry const& geometry, bool check_has_intersections, - double precision = 0.001) + double /*precision*/ = 0.001) { typedef typename bg::point_type<Geometry>::type point_type; //typedef typename bg::rescale_policy_type<point_type>::type rescale_policy_type; diff --git a/libs/geometry/test/algorithms/overlay/test_get_turns.hpp b/libs/geometry/test/algorithms/overlay/test_get_turns.hpp index 0950ebfe1..314c5c8c4 100644 --- a/libs/geometry/test/algorithms/overlay/test_get_turns.hpp +++ b/libs/geometry/test/algorithms/overlay/test_get_turns.hpp @@ -87,9 +87,11 @@ struct equal_turn<1> template <typename T> bool operator()(T const& t) const { - unsigned count = turn_ptr->size(); - BOOST_ASSERT(turn_ptr && count >= 1); - return bg::method_char(t.method) == (*turn_ptr)[0] + std::string::size_type count = turn_ptr->size(); + //BOOST_ASSERT(turn_ptr && count >= 1); + return ( count > 0 + ? bg::method_char(t.method) == (*turn_ptr)[0] + : true ) && ( count > 1 ? bg::operation_char(t.operations[0].operation) == (*turn_ptr)[1] : true ) @@ -154,6 +156,10 @@ void check_geometry_range( bool ok = boost::size(expected) == turns.size(); +#ifdef BOOST_GEOMETRY_TEST_DEBUG + std::vector<turn_info> turns_dbg = turns; +#endif + BOOST_CHECK_MESSAGE(ok, "get_turns: " << wkt1 << " and " << wkt2 << " -> Expected turns #: " << boost::size(expected) << " detected turns #: " << turns.size()); @@ -168,11 +174,43 @@ void check_geometry_range( turns.erase(it); else { + ok = false; BOOST_CHECK_MESSAGE(false, "get_turns: " << wkt1 << " and " << wkt2 << " -> Expected turn: " << *sit << " not found"); } } + +#ifdef BOOST_GEOMETRY_TEST_DEBUG + if ( !ok ) + { + std::cout << "Coordinates: " + << typeid(typename bg::coordinate_type<Geometry1>::type).name() + << ", " + << typeid(typename bg::coordinate_type<Geometry2>::type).name() + << std::endl; + std::cout << "Detected: "; + if ( turns_dbg.empty() ) + { + std::cout << "{empty}"; + } + else + { + for ( typename std::vector<turn_info>::const_iterator it = turns_dbg.begin() ; + it != turns_dbg.end() ; ++it ) + { + if ( it != turns_dbg.begin() ) + std::cout << ", "; + std::cout << bg::method_char(it->method); + std::cout << bg::operation_char(it->operations[0].operation); + std::cout << bg::operation_char(it->operations[1].operation); + std::cout << equal_turn<1>::is_colinear_char(it->operations[0].is_collinear); + std::cout << equal_turn<1>::is_colinear_char(it->operations[1].is_collinear); + } + } + std::cout << std::endl; + } +#endif } template <typename Geometry1, typename Geometry2, typename Expected> diff --git a/libs/geometry/test/algorithms/overlay/traverse.cpp b/libs/geometry/test/algorithms/overlay/traverse.cpp index 1fb7123b2..0ae6bfd0a 100644 --- a/libs/geometry/test/algorithms/overlay/traverse.cpp +++ b/libs/geometry/test/algorithms/overlay/traverse.cpp @@ -774,7 +774,7 @@ void test_all(bool test_self_tangencies = true, bool test_mixed = false) test_traverse<polygon, polygon, operation_intersection>::apply("hv3", 1, 1623.8265057282042, hv_3[0], hv_3[1], deviation); - if (! is_float) + if ( BOOST_GEOMETRY_CONDITION(! is_float) ) { test_traverse<polygon, polygon, operation_union>::apply("hv4", 1, 1626.5146964146334, hv_4[0], hv_4[1], deviation); test_traverse<polygon, polygon, operation_intersection>::apply("hv4", 1, 1626.2580370864305, hv_4[0], hv_4[1], deviation); @@ -798,7 +798,7 @@ void test_all(bool test_self_tangencies = true, bool test_mixed = false) // the chance is 50% that the segments are not sorted correctly and the wrong // decision is taken. // Solved now (by sorting on sides in those cases) - if (! is_float_on_non_msvc) + if ( BOOST_GEOMETRY_CONDITION(! is_float_on_non_msvc) ) { test_traverse<polygon, polygon, operation_intersection>::apply("dz_1", 2, 16.887537949472005, dz_1[0], dz_1[1]); @@ -844,7 +844,7 @@ void test_all(bool test_self_tangencies = true, bool test_mixed = false) float_might_deviate_more); } - if (! is_float) + if ( BOOST_GEOMETRY_CONDITION(! is_float) ) { /* TODO check this BSG 2013-09-24 |