diff options
Diffstat (limited to 'src/boost/libs/geometry/test/algorithms/relate')
10 files changed, 3043 insertions, 0 deletions
diff --git a/src/boost/libs/geometry/test/algorithms/relate/Jamfile.v2 b/src/boost/libs/geometry/test/algorithms/relate/Jamfile.v2 new file mode 100644 index 00000000..bcc306da --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/Jamfile.v2 @@ -0,0 +1,26 @@ +# Boost.Geometry (aka GGL, Generic Geometry Library) +# +# 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 2014, 2015, 2016. +# Modifications copyright (c) 2014-2016, 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-relate + : + [ run relate_areal_areal.cpp : : : : algorithms_relate_areal_areal ] + [ run relate_areal_areal_sph.cpp : : : : algorithms_relate_areal_areal_sph ] + [ run relate_linear_areal.cpp : : : : algorithms_relate_linear_areal ] + [ run relate_linear_areal_sph.cpp : : : : algorithms_relate_linear_areal_sph ] + [ run relate_linear_linear.cpp : : : : algorithms_relate_linear_linear ] + [ run relate_linear_linear_sph.cpp : : : : algorithms_relate_linear_linear_sph ] + [ run relate_pointlike_geometry.cpp : : : : algorithms_relate_pointlike_geometry ] + ; diff --git a/src/boost/libs/geometry/test/algorithms/relate/nan_cases.hpp b/src/boost/libs/geometry/test/algorithms/relate/nan_cases.hpp new file mode 100644 index 00000000..24306202 --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/nan_cases.hpp @@ -0,0 +1,130 @@ +// Boost.Geometry + +// 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 <geometry_test_common.hpp> + +#include <boost/geometry/geometries/geometries.hpp> +#include <boost/geometry/geometries/point_xy.hpp> + +#include <boost/range/value_type.hpp> +#include <boost/type_traits/is_same.hpp> + +template <typename Container> +struct pusher + : public Container +{ + typedef typename Container::value_type value_type; + pusher(value_type const& val) + { + this->push_back(val); + } + + pusher & operator()(value_type const& val) + { + this->push_back(val); + return *this; + } +}; + +template <typename Geometry, + typename Tag = typename bg::tag<Geometry>::type, + typename Coord = typename bg::coordinate_type<Geometry>::type> +struct nan_case_generator +{ + static void apply(Geometry & , std::string & ) + {} +}; + +template <typename Geometry> +struct nan_case_generator<Geometry, bg::multi_linestring_tag, double> +{ + static void apply(Geometry & geometry, std::string & wkt) + { + typedef typename boost::range_value<Geometry>::type ls; + typedef typename bg::point_type<Geometry>::type P; + typedef typename bg::coordinate_type<Geometry>::type coord_t; + coord_t nan = std::numeric_limits<coord_t>::quiet_NaN(); + + wkt = "MULTILINESTRING((3.1e+307 1,-nan -nan),(3.1e+307 1,-nan -nan),(3.1e+307 1,5.1e+307 6e+307,nan nan),(-nan -nan,nan nan),(-nan -nan,-1 -3.97843,-1 3.28571,-1 47.6364),(3 78.5455,3 2),(nan nan,3 12.9689),(3 -2,-nan -nan),(3 2,3 12.9689,3 78.5455),(-1 4.29497e+09,-1 7,-nan -nan),(9 5,-nan -nan),(-nan -nan,9 60.8755,9 124.909),(nan nan,1 6.87195e+10,-nan -nan),(nan nan,4 86.2727,4 20.9533),(4 -5,-nan -nan),(4 -5,-nan -nan),(4 -5,-nan -nan),(4 -5,1.1e+308 2.1e+307,nan nan),(-nan -nan,-1 -8),(-nan -nan,-9 -4))"; + + typedef pusher<Geometry> ml; + typedef pusher<ls> l; + geometry = ml(l(P(3.1e+307, 1))(P(-nan, -nan))) + (l(P(3.1e+307, 1))(P(-nan, -nan))) + (l(P(3.1e+307, 1))(P(5.1e+307, 6e+307))(P(nan, nan))) + (l(P(-nan, -nan))(P(nan, nan))) + (l(P(-nan, -nan))(P(-1, -3.97843))(P(-1, 3.28571))(P(-1, 47.6364))) + (l(P(3, 78.5455))(P(3, 2))) + (l(P(nan, nan))(P(3, 12.9689))) + (l(P(3, -2))(P(-nan, -nan))) + (l(P(3, 2))(P(3, 12.9689))(P(3, 78.5455))) + (l(P(-1, 4.29497e+09))(P(-1, 7))(P(-nan, -nan))) + (l(P(9, 5))(P(-nan, -nan))) + (l(P(-nan, -nan))(P(9, 60.8755))(P(9, 124.909))) + (l(P(nan, nan))(P(1, 6.87195e+10))(P(-nan, -nan))) + (l(P(nan, nan))(P(4, 86.2727))(P(4, 20.9533))) + (l(P(4, -5))(P(-nan, -nan))) + (l(P(4, -5))(P(-nan, -nan))) + (l(P(4, -5))(P(-nan, -nan))) + (l(P(4, -5))(P(1.1e+308, 2.1e+307))(P(nan, nan))) + (l(P(-nan, -nan))(P(-1, -8))) + (l(P(-nan, -nan))(P(-9, -4))); + } +}; + +template <typename Geometry> +struct nan_case_generator<Geometry, bg::multi_point_tag, double> +{ + static void apply(Geometry & geometry, std::string & wkt) + { + typedef typename bg::point_type<Geometry>::type P; + typedef typename bg::coordinate_type<Geometry>::type coord_t; + coord_t nan = std::numeric_limits<coord_t>::quiet_NaN(); + + wkt = "MULTIPOINT((3.1e+307 1),(-nan -nan),(3.1e+307 1),(-nan -nan),(3.1e+307 1),(5.1e+307 6e+307),(nan nan),(-nan -nan),(nan nan),(-nan -nan),(-1 -3.97843),(-1 3.28571),(-1 47.6364),(3 78.5455),(3 2),(nan nan),(3 12.9689),(3 -2),(-nan -nan),(3 2),(3 12.9689),(3 78.5455),(-1 4.29497e+09),(-1 7),(-nan -nan),(9 5),(-nan -nan),(-nan -nan),(9 60.8755),(9 124.909),(nan nan),(1 6.87195e+10),(-nan -nan),(nan nan),(4 86.2727),(4 20.9533),(4 -5),(-nan -nan),(4 -5),(-nan -nan),(4 -5),(-nan -nan),(4 -5),(1.1e+308 2.1e+307),(nan nan),(-nan -nan),(-1 -8),(-nan -nan),(-9 -4))"; + + typedef pusher<Geometry> mp; + geometry = mp(P(3.1e+307, 1))(P(-nan, -nan)) + (P(3.1e+307, 1))(P(-nan, -nan)) + (P(3.1e+307, 1))(P(5.1e+307, 6e+307))(P(nan, nan)) + (P(-nan, -nan))(P(nan, nan)) + (P(-nan, -nan))(P(-1, -3.97843))(P(-1, 3.28571))(P(-1, 47.6364)) + (P(3, 78.5455))(P(3, 2)) + (P(nan, nan))(P(3, 12.9689)) + (P(3, -2))(P(-nan, -nan)) + (P(3, 2))(P(3, 12.9689))(P(3, 78.5455)) + (P(-1, 4.29497e+09))(P(-1, 7))(P(-nan, -nan)) + (P(9, 5))(P(-nan, -nan)) + (P(-nan, -nan))(P(9, 60.8755))(P(9, 124.909)) + (P(nan, nan))(P(1, 6.87195e+10))(P(-nan, -nan)) + (P(nan, nan))(P(4, 86.2727))(P(4, 20.9533)) + (P(4, -5))(P(-nan, -nan)) + (P(4, -5))(P(-nan, -nan)) + (P(4, -5))(P(-nan, -nan)) + (P(4, -5))(P(1.1e+308, 2.1e+307))(P(nan, nan)) + (P(-nan, -nan))(P(-1, -8)) + (P(-nan, -nan))(P(-9, -4)); + } +}; + +template <typename Geometry> +void nan_case(Geometry & geometry, std::string & wkt) +{ + nan_case_generator<Geometry>::apply(geometry, wkt); +} + +template <typename Geometry> +struct is_nan_case_supported +{ + typedef typename bg::coordinate_type<Geometry>::type coord_t; + + static const bool value = boost::is_same<coord_t, double>::value + && std::numeric_limits<coord_t>::has_quiet_NaN; +}; diff --git a/src/boost/libs/geometry/test/algorithms/relate/relate_areal_areal.cpp b/src/boost/libs/geometry/test/algorithms/relate/relate_areal_areal.cpp new file mode 100644 index 00000000..81ced941 --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/relate_areal_areal.cpp @@ -0,0 +1,434 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. + +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-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_relate.hpp" + +//#include <to_svg.hpp> + +template <typename P> +void test_polygon_polygon() +{ + typedef bg::model::polygon<P> poly; + typedef bg::model::ring<P> ring; + + // touching + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((10 0,10 10,20 10,20 0,10 0))", + "FF2F11212"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((0 -10,0 0,10 0,10 -10,0 -10))", + "FF2F11212"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((10 0,15 10,20 10,20 0,10 0))", + "FF2F01212"); + + // containing + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((5 5,5 10,6 10,6 5,5 5))", + "212F11FF2"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((5 5,5 10,6 5,5 5))", + "212F01FF2"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((5 5,5 6,6 6,6 5,5 5))", + "212FF1FF2"); + + // fully containing + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((5 5,5 9,6 9,6 5,5 5))", + "212FF1FF2"); + // fully containing, with a hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(3 3,7 3,7 7,3 7,3 3))", + "POLYGON((1 1,1 9,9 9,9 1,1 1))", + "2121F12F2"); + // fully containing, both with holes + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(3 3,7 3,7 7,3 7,3 3))", + "POLYGON((1 1,1 9,9 9,9 1,1 1),(2 2,8 2,8 8,2 8,2 2))", + "212FF1FF2"); + // fully containing, both with holes + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(3 3,7 3,7 7,3 7,3 3))", + "POLYGON((1 1,1 9,9 9,9 1,1 1),(4 4,6 4,6 6,4 6,4 4))", + "2121F1212"); + + // overlapping + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((5 0,5 10,20 10,20 0,5 0))", + "212111212"); + test_geometry<ring, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((5 0,5 10,20 10,20 0,5 0))", + "212111212"); + test_geometry<ring, ring>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((5 0,5 10,20 10,20 0,5 0))", + "212111212"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,15 5,10 0,0 0))", + "POLYGON((10 0,5 5,10 10,20 10,20 0,10 0))", + "212101212"); + + // equal + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((10 10,10 5,10 0,5 0,0 0,0 10,5 10,10 10))", + "2FFF1FFF2"); + // hole-sized + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(5 5,6 5,6 6,5 6,5 5))", + "POLYGON((5 5,5 6,6 6,6 5,5 5))", + "FF2F112F2"); + + // disjoint + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((0 20,0 30,10 30,10 20,0 20))", + "FF2FF1212"); + // disjoint + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(3 3,7 3,7 7,3 7,3 3))", + "POLYGON((0 20,0 30,10 30,10 20,0 20))", + "FF2FF1212"); + + // equal non-simple / non-simple hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(5 5,10 5,5 6,5 5))", + "POLYGON((0 0,0 10,10 10,10 5,5 6,5 5,10 5,10 0,0 0))", + "2FFF1FFF2"); + + // within non-simple / simple + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 5,5 6,5 5,10 5,10 0,0 0))", + "POLYGON((0 0,5 5,10 5,10 0,0 0))", + "212F11FF2"); + // within non-simple hole / simple + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(5 5,10 5,5 6,5 5))", + "POLYGON((0 0,5 5,10 5,10 0,0 0))", + "212F11FF2"); + + + // not within non-simple / simple + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 5,5 6,5 5,10 5,10 0,0 0))", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "2FF11F2F2"); + // not within non-simple hole / simple + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(5 5,10 5,5 6,5 5))", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "2FF11F2F2"); + // not within simple hole / simple + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(5 5,9 5,5 6,5 5))", + "POLYGON((0 0,0 10,10 10,9 5,10 0,0 0))", + "2121112F2"); + + // within non-simple fake hole / simple + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 5,4 7,4 3,10 5,10 0,0 0))", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "2FF11F2F2"); + // within non-simple fake hole / non-simple fake hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 5,4 7,4 3,10 5,10 0,0 0))", + "POLYGON((0 0,0 10,10 10,10 5,5 6,5 4,10 5,10 0,0 0))", + "2FF11F212"); + // within non-simple fake hole / non-simple hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 5,4 7,4 3,10 5,10 0,0 0))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,5 6,5 4,10 5))", + "2FF11F212"); + // containing non-simple fake hole / non-simple hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 5,4 7,4 3,10 5,10 0,0 0))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,3 8,3 2,10 5))", + "212F11FF2"); + + // within non-simple hole / simple + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,4 7,4 3,10 5))", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "2FF11F2F2"); + // within non-simple hole / non-simple fake hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,4 7,4 3,10 5))", + "POLYGON((0 0,0 10,10 10,10 5,5 6,5 4,10 5,10 0,0 0))", + "2FF11F212"); + // containing non-simple hole / non-simple fake hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,4 7,4 3,10 5))", + "POLYGON((0 0,0 10,10 10,10 5,3 8,3 2,10 5,10 0,0 0))", + "212F11FF2"); + // equal non-simple hole / non-simple fake hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,4 7,4 3,10 5))", + "POLYGON((0 0,0 10,10 10,10 5,4 7,4 3,10 5,10 0,0 0))", + "2FFF1FFF2"); + // within non-simple hole / non-simple hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,4 7,4 3,10 5))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,5 6,5 4,10 5))", + "2FF11F212"); + // containing non-simple hole / non-simple hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,4 7,4 3,10 5))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,3 8,3 2,10 5))", + "212F11FF2"); + // equal non-simple hole / non-simple hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,4 7,4 3,10 5))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,4 7,4 3,10 5))", + "2FFF1FFF2"); + + // intersecting non-simple hole / non-simple hole - touching holes + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(5 5,10 5,5 6,5 5))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(0 5,5 4,5 5,0 5))", + "21211F2F2"); + // intersecting non-simple fake hole / non-simple hole - touching holes + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 5,5 6,5 5,10 5,10 0,0 0))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(0 5,5 4,5 5,0 5))", + "21211F2F2"); + // intersecting non-simple fake hole / non-simple fake hole - touching holes + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 5,5 6,5 5,10 5,10 0,0 0))", + "POLYGON((0 0,0 5,5 4,5 5,0 5,0 10,10 10,10 0,0 0))", + "21211F2F2"); + + // intersecting simple - i/i + test_geometry<poly, poly>("POLYGON((0 0,0 10,4 10,6 8,5 5,6 2,4 0,0 0))", + "POLYGON((5 5,4 8,6 10,10 10,10 0,6 0,4 2,5 5))", + "212101212"); + // intersecting non-simple hole / non-simple hole - i/i + test_geometry<poly, poly>("POLYGON((0 0,0 10,4 10,6 8,5 5,6 2,4 0,0 0),(5 5,2 6,2 4,5 5))", + "POLYGON((5 5,4 8,6 10,10 10,10 0,6 0,4 2,5 5),(5 5,8 4,8 6,5 5))", + "212101212"); + // intersecting non-simple hole / simple - i/i + test_geometry<poly, poly>("POLYGON((0 0,0 10,4 10,6 8,5 5,6 2,4 0,0 0),(5 5,2 6,2 4,5 5))", + "POLYGON((5 5,4 8,6 10,10 10,10 0,6 0,4 2,5 5))", + "212101212"); + + // no turns - disjoint inside a hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(1 1,9 1,9 9,1 9,1 1))", + "POLYGON((3 3,3 7,7 7,7 3,3 3))", + "FF2FF1212"); + // no turns - within + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(1 1,9 1,9 9,1 9,1 1))", + "POLYGON((-1 -1,-1 11,11 11,11 -1,-1 -1))", + "2FF1FF212"); + // no-turns - intersects + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,8 2,8 8,2 8,2 2))", + "POLYGON((1 1,1 9,9 9,9 1,1 1))", + "2121F12F2"); + // no-turns - intersects, hole in a hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,8 2,8 8,2 8,2 2))", + "POLYGON((1 1,1 9,9 9,9 1,1 1),(3 3,7 3,7 7,3 7,3 3))", + "2121F1212"); + + // no-turns ring - for exteriors + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,8 2,8 8,2 8,2 2))", + "POLYGON((1 1,1 9,9 9,9 1,1 1),(2 2,8 2,8 8,2 8,2 2))", + "212F11FF2"); + // no-turns ring - for interiors + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(3 3,7 3,7 7,3 7,3 3))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,8 2,8 8,2 8,2 2))", + "212F11FF2"); + + { + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((5 5,5 10,6 10,6 5,5 5))", + "212F11FF2"); + + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((10 0,10 10,20 10,20 0,10 0))", + "FF2F11212"); + + namespace bgdr = bg::detail::relate; + poly p1, p2, p3; + bg::read_wkt("POLYGON((0 0,0 10,10 10,10 0,0 0))", p1); + bg::read_wkt("POLYGON((10 0,10 10,20 10,20 0,10 0))", p2); + bg::read_wkt("POLYGON((5 5,5 10,6 10,6 5,5 5))", p3); + BOOST_CHECK(bg::relate(p1, p2, bg::de9im::mask("FT*******") + || bg::de9im::mask("F**T*****") + || bg::de9im::mask("F***T****"))); // touches() + BOOST_CHECK(bg::relate(p1, p3, bg::de9im::mask("T*****FF*"))); // contains() + BOOST_CHECK(bg::relate(p2, p3, bg::de9im::mask("FF*FF****"))); // disjoint() + + BOOST_CHECK(bg::relate(p1, p2, bg::de9im::static_mask<'F','T'>() + || bg::de9im::static_mask<'F','*','*','T'>() + || bg::de9im::static_mask<'F','*','*','*','T'>())); + } + + // CCW + { + typedef bg::model::polygon<P, false> poly; + // within non-simple hole / simple + test_geometry<poly, poly>("POLYGON((0 0,10 0,10 10,0 10,0 0),(5 5,5 6,10 5,5 5))", + "POLYGON((0 0,10 0,10 5,5 5,0 0))", + "212F11FF2"); + } + // OPEN + { + typedef bg::model::polygon<P, true, false> poly; + // within non-simple hole / simple + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0),(5 5,10 5,5 6))", + "POLYGON((0 0,5 5,10 5,10 0))", + "212F11FF2"); + } + // CCW, OPEN + { + typedef bg::model::polygon<P, false, false> poly; + // within non-simple hole / simple + test_geometry<poly, poly>("POLYGON((0 0,10 0,10 10,0 10),(5 5,5 6,10 5))", + "POLYGON((0 0,10 0,10 5,5 5))", + "212F11FF2"); + } + + // https://svn.boost.org/trac/boost/ticket/10912 + { + // external rings touches and G2's hole is inside G1 + test_geometry<poly, poly>("POLYGON((0 0,0 5,5 5,5 0,0 0))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,4 2,4 4,2 4,2 2),(6 6,8 6,8 8,6 8,6 6))", + "21211F212"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,2 4,4 4,4 2,2 2))", + "212F1FFF2"); + // extended + // external rings touches and G1's hole is inside G2 + test_geometry<poly, poly>("POLYGON((0 0,0 9,9 9,9 0,0 0),(2 2,7 2,7 7,2 7,2 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "2FF11F212"); + // external rings touches, holes doesn't + test_geometry<poly, poly>("POLYGON((0 0,0 9,9 9,9 0,0 0),(2 2,7 2,7 7,2 7,2 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(1 1,8 1,8 8,1 8,1 1))", + "212111212"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,7 2,7 7,2 7,2 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(1 1,8 1,8 8,1 8,1 1))", + "212F11FF2"); + // holes touches, external rings doesn't + test_geometry<poly, poly>("POLYGON((1 1,1 9,9 9,9 1,1 1),(2 2,8 2,8 8,2 8,2 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,7 2,7 7,2 7,2 2))", + "2FF11F212"); + test_geometry<poly, poly>("POLYGON((1 1,1 9,9 9,9 1,1 1),(2 2,7 2,7 7,2 7,2 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,8 2,8 8,2 8,2 2))", + "212111212"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,8 2,8 8,2 8,2 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,7 2,7 7,2 7,2 2))", + "2FF11F212"); + + test_geometry<poly, poly>("POLYGON((3 3,3 9,9 9,9 3,3 3))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,4 2,4 4,2 4,2 2))", + "212101212"); + } + + if ( BOOST_GEOMETRY_CONDITION(( + boost::is_same<typename bg::coordinate_type<P>::type, double>::value )) ) + { + // original - assertion for CCW + //"POLYGON((-0.593220338983050821113352 -8.05084745762711939676137,1.14285714285714279370154 -4,1.50731707317073171381594 1.10243902439024443751237,1.73758865248226967992196 1.37588652482269591104114,1.21739130434782616418943 -3.82608695652173924628414,2 -2,2 1.68750000000000044408921,2.35384615384615436539661 2.10769230769230775379697,2 2.16666666666666651863693,2 4,1.81967213114754100544701 2.1967213114754100544701,1.5882352941176469673934 2.2352941176470588757752,1.8148148148148146585612 5.4074074074074074403029,-0.538461538461538546940233 4.23076923076923083755219,-1.76510067114094004736558 2.89261744966443012927471,-1.64864864864864868465588 2.7567567567567570208098,-1.83962264150943455298659 2.81132075471698161805989,-1.84337349397590433142113 2.80722891566265086993326,-2.14285714285714279370154 2.85714285714285720629846,-2.11111111111111116045436 2.88888888888888883954564,-2.87234042553191448732264 3.10638297872340407579372,-2.91803278688524558859285 3.4262295081967208965068,-3.1733333333333324510761 3.26666666666666660745477,-2.99999999999999822364316 3.14285714285714234961233,-3.25490196078431326398572 3.21568627450980359938626,-3.47368421052631504153396 3.07894736842105265495206,-7.32000000000000028421709 3.72000000000000019539925,-7.54716981132075481752963 3.62264150943396234794136,-7.75 3.79166666666666651863693,-7.79999999999999982236432 3.79999999999999982236432,-7.59999999999999964472863 3.60000000000000008881784,-8.8556701030927822415606 3.06185567010309300783888,-8.82945736434108674473009 2.8914728682170549589614,-7.73333333333333339254523 2.193939393939393855959,-8 2,-5.94736842105263185942476 -1.42105263157894645686952,-5.32558139534883689947264 -0.488372093023255016142059,-5.85714285714285765038767 1.00000000000000066613381,-4.78723404255319184841255 0.319148936170212838003835,-5.32558139534883689947264 -0.488372093023255016142059,-4.74019607843137258385013 -2.12745098039215774221589,-3.17647058823529437887601 -0.705882352941176627325603,-2.93103448275862055183438 -0.862068965517241436735674,-3 -1,-4.57894736842105309904127 -2.57894736842105265495206,-4.47887323943661996850096 -2.85915492957746497637572,-7.58620689655172419918472 -5.18965517241379359347775,-7.52525252525252508206677 -5.5858585858585865224768,-4.18644067796610119813749 -3.67796610169491522412955,-3.44041450777202051369841 -5.76683937823834202873741,-3.73611111111111116045436 -6.56944444444444464181743,-2.8823529411764705621124 -7.7647058823529411242248,-2.88235294117647100620161 -7.7647058823529411242248,-0.593220338983050821113352 -8.05084745762711939676137),(1.66666666666666696272614 1.59999999999999875655021,1.43749999999999911182158 1.8750000000000002220446,0.0869565217391310429917439 2.26086956521739113057379,0.466666666666667118157363 2.60606060606060552231611,1.04878048780487764801705 2.34146341463414664474385,1.43749999999999911182158 1.8750000000000002220446,1.56756756756756754356275 1.83783783783783771781373,1.66666666666666696272614 1.59999999999999875655021))" + //"POLYGON((-2.33333333333333303727386 -8.66666666666666607454772,-2.26315789473684203514381 -8.63157894736842123961651,-2.88235294117647100620161 -7.7647058823529411242248,-2.8823529411764705621124 -7.7647058823529411242248,-4.11949685534591125701809 -7.61006289308176064878353,-4.32530120481927671249878 -8.16867469879518104391991,-2.33333333333333303727386 -8.66666666666666607454772))" + + // assertion failure in 1.57 + test_geometry<poly, poly>("POLYGON((-0.59322033898305082 -8.0508474576271194,-2.882352941176471 -7.7647058823529411,-2.8823529411764706 -7.7647058823529411,-3.7361111111111112 -6.5694444444444446,-3.4404145077720205 -5.766839378238342,-4.1864406779661012 -3.6779661016949152,-7.5252525252525251 -5.5858585858585865,-7.5862068965517242 -5.1896551724137936,-4.47887323943662 -2.859154929577465,-4.5789473684210531 -2.5789473684210527,-3 -1,-2.9310344827586206 -0.86206896551724144,-3.1764705882352944 -0.70588235294117663,-4.7401960784313726 -2.1274509803921577,-5.3255813953488369 -0.48837209302325502,-4.7872340425531918 0.31914893617021284,-5.8571428571428577 1.0000000000000007,-5.3255813953488369 -0.48837209302325502,-5.9473684210526319 -1.4210526315789465,-8 2,-7.7333333333333334 2.1939393939393939,-8.8294573643410867 2.891472868217055,-8.8556701030927822 3.061855670103093,-7.5999999999999996 3.6000000000000001,-7.7999999999999998 3.7999999999999998,-7.75 3.7916666666666665,-7.5471698113207548 3.6226415094339623,-7.3200000000000003 3.7200000000000002,-3.473684210526315 3.0789473684210527,-3.2549019607843133 3.2156862745098036,-2.9999999999999982 3.1428571428571423,-3.1733333333333325 3.2666666666666666,-2.9180327868852456 3.4262295081967209,-2.8723404255319145 3.1063829787234041,-2.1111111111111112 2.8888888888888888,-2.1428571428571428 2.8571428571428572,-1.8433734939759043 2.8072289156626509,-1.8396226415094346 2.8113207547169816,-1.6486486486486487 2.756756756756757,-1.76510067114094 2.8926174496644301,-0.53846153846153855 4.2307692307692308,1.8148148148148147 5.4074074074074074,1.588235294117647 2.2352941176470589,1.819672131147541 2.1967213114754101,2 4,2 2.1666666666666665,2.3538461538461544 2.1076923076923078,2 1.6875000000000004,2 -2,1.2173913043478262 -3.8260869565217392,1.7375886524822697 1.3758865248226959,1.5073170731707317 1.1024390243902444,1.1428571428571428 -4,-0.59322033898305082 -8.0508474576271194),(1.666666666666667 1.5999999999999988,1.5675675675675675 1.8378378378378377,1.4374999999999991 1.8750000000000002,1.0487804878048776 2.3414634146341466,0.46666666666666712 2.6060606060606055,0.086956521739131043 2.2608695652173911,1.4374999999999991 1.8750000000000002,1.666666666666667 1.5999999999999988))", + "POLYGON((-2.333333333333333 -8.6666666666666661,-4.3253012048192767 -8.168674698795181,-4.1194968553459113 -7.6100628930817606,-2.8823529411764706 -7.7647058823529411,-2.882352941176471 -7.7647058823529411,-2.263157894736842 -8.6315789473684212,-2.333333333333333 -8.6666666666666661))", + "*********"); + // simpler case + test_geometry<poly, poly>("POLYGON((0 0, -0.59322033898305082 -8.0508474576271194, -2.8823529411764710 -7.7647058823529411, -3.7361111111111112 -6.5694444444444446, 0 0))", + "POLYGON((-10 -10, -4.1194968553459113 -7.6100628930817606, -2.8823529411764706 -7.7647058823529411, -2.2631578947368420 -8.6315789473684212, -10 -10))", + "FF2F01212"); + // sanity check + test_geometry<poly, poly>("POLYGON((0 0, -0.59322033898305082 -8.0508474576271194, -2.8823529411764710 -7.7647058823529411, -3.7361111111111112 -6.5694444444444446, 0 0))", + "POLYGON((-10 -10, -4.1194968553459113 -7.6100628930817606, -2.8823529411764710 -7.7647058823529411, -2.2631578947368420 -8.6315789473684212, -10 -10))", + "FF2F01212"); + + // compatibility check + /*test_geometry<poly, poly>("POLYGON((0 0,0 1,1 1,1 0,0 0))", + "POLYGON((1 1,1 2,2 2,2 1,1 1))", + "****0****"); + test_geometry<P, P>("POINT(0.9999999999999998 0.9999999999999998)", + "POINT(1 1)", + "0********"); + test_geometry<P, P>("POINT(0.9999999999999995 0.9999999999999995)", + "POINT(1 1)", + "F********"); + test_geometry<poly, poly>("POLYGON((0 0,0 1,0.9999999999999998 0.9999999999999998,1 0,0 0))", + "POLYGON((1 1,1 2,2 2,2 1,1 1))", + "****0****"); + test_geometry<poly, poly>("POLYGON((0 0,0 1,0.9999999999999995 0.9999999999999995,1 0,0 0))", + "POLYGON((1 1,1 2,2 2,2 1,1 1))", + "****F****");*/ + } + + // mysql 21872795 (overlaps) + test_geometry<poly, poly>("POLYGON((2 2,2 8,8 8,8 2,2 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(8 8,4 6,4 4,8 8))", + "21210F212"); + test_geometry<poly, poly>("POLYGON((2 2,2 8,8 8,8 2,2 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,4 4,4 6,2 2))", + "21210F212"); + // mysql 21873343 (touches) + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0), (0 8, 8 5, 8 8, 0 8))", + "POLYGON((0 8,-8 5,-8 8,0 8))", + "FF2F01212"); + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0), (0 6, 6 3, 6 6, 0 6))", + "POLYGON((0 6,-6 3,-6 6,0 6))", + "FF2F01212"); + // similar but touching from the inside of the hole + test_geometry<poly, poly>("POLYGON((0 0,0 10,10 10,10 0,0 0), (0 8, 8 5, 8 8, 0 8))", + "POLYGON((0 8,7 7, 7 6,0 8))", + "FF2F01212"); +} + +template <typename P> +void test_polygon_multi_polygon() +{ + typedef bg::model::polygon<P> poly; + typedef bg::model::ring<P> ring; + typedef bg::model::multi_polygon<poly> mpoly; + + test_geometry<poly, mpoly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "MULTIPOLYGON(((5 5,5 10,6 10,6 5,5 5)),((0 20,0 30,10 30,10 20,0 20)))", + "212F11212"); + test_geometry<ring, mpoly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "MULTIPOLYGON(((5 5,5 10,6 10,6 5,5 5)),((0 20,0 30,10 30,10 20,0 20)))", + "212F11212"); + + test_geometry<mpoly, poly>("MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "POLYGON((0 0,0 5,5 5,5 0,0 0))", + "212F11FF2"); + test_geometry<poly, mpoly>("POLYGON((0 0,0 5,5 5,5 0,0 0))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "2FF11F212"); + test_geometry<poly, mpoly>("POLYGON((0 0,0 5,5 5,5 0,0 0))", + "MULTIPOLYGON(((0 0,0 -10,-10 -10,-10 0,0 0)),((0 0,0 10,10 10,10 0,0 0)))", + "2FF11F212"); + test_geometry<poly, mpoly>("POLYGON((0 0,0 10,10 10,10 0,0 0))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "2FFF1F212"); +} + +template <typename P> +void test_multi_polygon_multi_polygon() +{ + typedef bg::model::polygon<P> poly; + typedef bg::model::multi_polygon<poly> mpoly; + + test_geometry<mpoly, mpoly>("MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "MULTIPOLYGON(((5 5,5 10,6 10,6 5,5 5)),((0 20,0 30,10 30,10 20,0 20)))", + "212F11212"); + test_geometry<mpoly, mpoly>("MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 20,0 30,10 30,10 20,0 20)))", + "MULTIPOLYGON(((5 5,5 10,6 10,6 5,5 5)))", + "212F11FF2"); + + test_geometry<mpoly, mpoly>("MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "MULTIPOLYGON(((5 5,5 6,6 6,6 5,5 5)),((0 20,0 30,10 30,10 20,0 20)))", + "212FF1212"); + test_geometry<mpoly, mpoly>("MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 20,0 30,10 30,10 20,0 20)))", + "MULTIPOLYGON(((5 5,5 6,6 6,6 5,5 5)))", + "212FF1FF2"); +} + +template <typename P> +void test_all() +{ + test_polygon_polygon<P>(); + test_polygon_multi_polygon<P>(); + test_multi_polygon_multi_polygon<P>(); +} + +int test_main( int , char* [] ) +{ + test_all<bg::model::d2::point_xy<int> >(); + test_all<bg::model::d2::point_xy<double> >(); + +#if defined(HAVE_TTMATH) + test_all<bg::model::d2::point_xy<ttmath_big> >(); +#endif + + return 0; +} diff --git a/src/boost/libs/geometry/test/algorithms/relate/relate_areal_areal_sph.cpp b/src/boost/libs/geometry/test/algorithms/relate/relate_areal_areal_sph.cpp new file mode 100644 index 00000000..5475a8fe --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/relate_areal_areal_sph.cpp @@ -0,0 +1,115 @@ +// Boost.Geometry +// Unit Test + +// Copyright (c) 2016, 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_relate.hpp" + +#include <algorithms/overlay/overlay_cases.hpp> +#include <algorithms/overlay/multi_overlay_cases.hpp> + + +template <typename P> +void test_polygon_polygon() +{ + typedef bg::model::polygon<P> poly; + typedef bg::model::ring<P> ring; + + test_geometry<ring, ring>(case_1[0], case_1[1], + "212101212"); + test_geometry<ring, poly>(case_1[0], case_1[1], + "212101212"); + + test_geometry<poly, poly>(case_1[0], case_1[1], + "212101212"); + test_geometry<poly, poly>(case_2[0], case_2[1], + "212101212"); + test_geometry<poly, poly>(case_3_sph[0], case_3_sph[1], + "2FF10F212"); + test_geometry<poly, poly>(case_3_2_sph[0], case_3_2_sph[1], + "2FFF1FFF2"); + test_geometry<poly, poly>(case_4[0], case_4[1], + "212101212"); + test_geometry<poly, poly>(case_5[0], case_5[1], + "212101212"); + test_geometry<poly, poly>(case_6_sph[0], case_6_sph[1], + "212F11FF2"); + + test_geometry<poly, poly>(case_7[0], case_7[1], + "FF2F11212"); + test_geometry<poly, poly>(case_8_sph[0], case_8_sph[1], + "FF2F11212"); + test_geometry<poly, poly>(case_9_sph[0], case_9_sph[1], + "FF2F01212"); + test_geometry<poly, poly>(case_10_sph[0], case_10_sph[1], + "FF2F11212"); + test_geometry<poly, poly>(case_11_sph[0], case_11_sph[1], + "212F01FF2"); + test_geometry<poly, poly>(case_12[0], case_12[1], + "212101212"); + + test_geometry<poly, poly>(case_13_sph[0], case_13_sph[1], + "FF2F11212"); + test_geometry<poly, poly>(case_14_sph[0], case_14_sph[1], + "FF2F11212"); + test_geometry<poly, poly>(case_15_sph[0], case_15_sph[1], + "FF2F11212"); + test_geometry<poly, poly>(case_16_sph[0], case_16_sph[1], + "FF2F11212"); + test_geometry<poly, poly>(case_17_sph[0], case_17_sph[1], + "212F11FF2"); + test_geometry<poly, poly>(case_18_sph[0], case_18_sph[1], + "212F11FF2"); +} + +template <typename P> +void test_polygon_multi_polygon() +{ + typedef bg::model::polygon<P> poly; + typedef bg::model::ring<P> ring; + typedef bg::model::multi_polygon<poly> mpoly; + + test_geometry<ring, mpoly>(case_1[0], case_multi_2[0], + "212101212"); + test_geometry<poly, mpoly>(case_2[0], case_multi_2[0], + "212101212"); +} + +template <typename P> +void test_multi_polygon_multi_polygon() +{ + typedef bg::model::polygon<P> poly; + typedef bg::model::multi_polygon<poly> mpoly; + + test_geometry<mpoly, mpoly>(case_multi_2[0], case_multi_2[1], + "212101212"); +} + + +template <typename P> +void test_all() +{ + test_polygon_polygon<P>(); + test_polygon_multi_polygon<P>(); + test_multi_polygon_multi_polygon<P>(); +} + +int test_main( int , char* [] ) +{ + typedef bg::cs::spherical_equatorial<bg::degree> cs_t; + test_all<bg::model::point<float, 2, cs_t> >(); + test_all<bg::model::point<double, 2, cs_t> >(); + +#if defined(HAVE_TTMATH) + test_all<bg::model::point<ttmath_big, 2, cs_t> >(); +#endif + + return 0; +} diff --git a/src/boost/libs/geometry/test/algorithms/relate/relate_linear_areal.cpp b/src/boost/libs/geometry/test/algorithms/relate/relate_linear_areal.cpp new file mode 100644 index 00000000..56017f6d --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/relate_linear_areal.cpp @@ -0,0 +1,536 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2018 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-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_relate.hpp" +#include "nan_cases.hpp" + +//TEST +//#include <to_svg.hpp> + +template <typename P> +void test_linestring_polygon() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::polygon<P> poly; + typedef bg::model::ring<P> ring; + + // LS disjoint + test_geometry<ls, poly>("LINESTRING(11 0,11 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212"); + test_geometry<ls, ring>("LINESTRING(11 0,11 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212"); + + // II BB + test_geometry<ls, poly>("LINESTRING(0 0,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1FFF0F212"); + test_geometry<ls, poly>("LINESTRING(5 0,5 5,10 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1FFF0F212"); + test_geometry<ls, poly>("LINESTRING(5 1,5 5,9 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1FF0FF212"); + + // IE + test_geometry<ls, poly>("LINESTRING(11 1,11 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212"); + // IE IB0 + test_geometry<ls, poly>("LINESTRING(11 1,10 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1F00212"); + // IE IB1 + test_geometry<ls, poly>("LINESTRING(11 1,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + test_geometry<ls, poly>("LINESTRING(11 1,10 10,0 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + test_geometry<ls, poly>("LINESTRING(11 1,10 0,0 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + test_geometry<ls, poly>("LINESTRING(0 -1,1 0,2 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + // IE IB0 II + test_geometry<ls, poly>("LINESTRING(11 1,10 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212"); + // IE IB0 lring + test_geometry<ls, poly>("LINESTRING(11 1,10 5,11 5,11 1)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F01FFF212"); + // IE IB1 lring + test_geometry<ls, poly>("LINESTRING(11 1,10 5,10 10,11 5,11 1)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11FFF212"); + + // IB1 II + test_geometry<ls, poly>("LINESTRING(0 0,5 0,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212"); + // BI0 II IB1 + test_geometry<ls, poly>("LINESTRING(5 0,5 5,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11FF0F212"); + + // IB1 II IB1 + test_geometry<ls, poly>("LINESTRING(1 0,2 0,3 1,4 0,5 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11FF0F212"); + // IB1 IE IB1 + test_geometry<ls, poly>("LINESTRING(1 0,2 0,3 -1,4 0,5 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F0F212"); + + // II IB1 + test_geometry<ls, poly>("LINESTRING(5 5,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212"); + // IB1 II + test_geometry<ls, poly>("LINESTRING(10 10,10 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212"); + // IE IB1 + test_geometry<ls, poly>("LINESTRING(15 5,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + // IB1 IE + test_geometry<ls, poly>("LINESTRING(10 10,10 5,15 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + + // duplicated points + { + // II IB0 IE + test_geometry<ls, poly>("LINESTRING(5 5,10 5,15 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212"); + test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5,10 5,10 5,10 5,15 10,15 10,15 10)", + "POLYGON((0 0,0 0,0 0,0 10,0 10,0 10,10 10,10 10,10 10,10 0,10 0,10 0,0 0,0 0,0 0))", + "1010F0212"); + test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5,10 0,10 0,10 0,15 10,15 10,15 10)", + "POLYGON((0 0,0 0,0 0,0 10,0 10,0 10,10 10,10 10,10 10,10 0,10 0,10 0,0 0,0 0,0 0))", + "1010F0212"); + // IE IB0 II + test_geometry<ls, poly>("LINESTRING(15 10,15 10,15 10,10 5,10 5,10 5,5 5,5 5,5 5)", + "POLYGON((0 0,0 0,0 0,0 10,0 10,0 10,10 10,10 10,10 10,10 0,10 0,10 0,0 0,0 0,0 0))", + "1010F0212"); + test_geometry<ls, poly>("LINESTRING(15 10,15 10,15 10,10 0,10 0,10 0,5 5,5 5,5 5)", + "POLYGON((0 0,0 0,0 0,0 10,0 10,0 10,10 10,10 10,10 10,10 0,10 0,10 0,0 0,0 0,0 0))", + "1010F0212"); + + // TEST + //test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212"); + test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5,15 5,15 5,15 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212"); + } + + // non-simple polygon with hole + test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "10F0FF212"); + test_geometry<ls, poly>("LINESTRING(10 1,10 5,10 9)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(2 8,10 5,2 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(10 1,10 5,2 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(10 1,10 5,2 8)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F1FF0F212"); + + // non-simple polygon with hole, linear ring + test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9,1 9,1 1,9 1)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "10FFFF212"); + test_geometry<ls, poly>("LINESTRING(10 5,10 9,11 5,10 1,10 5)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F11FFF212"); + test_geometry<ls, poly>("LINESTRING(11 5,10 1,10 5,10 9,11 5)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F11FFF212"); + + // non-simple polygon with self-touching holes + test_geometry<ls, poly>("LINESTRING(7 1,8 5,7 9)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(8 1,9 1,9 9,8 9,8 1),(2 2,8 5,2 8,2 2))", + "10F0FF212"); + test_geometry<ls, poly>("LINESTRING(8 2,8 5,8 8)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(8 1,9 1,9 9,8 9,8 1),(2 2,8 5,2 8,2 2))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(2 8,8 5,2 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(8 1,9 1,9 9,8 9,8 1),(2 2,8 5,2 8,2 2))", + "F1FF0F212"); + + // non-simple polygon self-touching + test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "10F0FF212"); + test_geometry<ls, poly>("LINESTRING(10 1,10 5,10 9)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(2 8,10 5,2 2)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "F1FF0F212"); + + // non-simple polygon self-touching, linear ring + test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9,1 9,1 1,9 1)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "10FFFF212"); + test_geometry<ls, poly>("LINESTRING(10 5,10 9,11 5,10 1,10 5)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "F11FFF212"); + test_geometry<ls, poly>("LINESTRING(11 5,10 1,10 5,10 9,11 5)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "F11FFF212"); + + // polygons with some ring equal to the linestring + test_geometry<ls, poly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "F1FFFF2F2"); + test_geometry<ls, poly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2))", + "F1FFFF212"); + test_geometry<ls, poly>("LINESTRING(2 2,5 5,2 8,2 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2))", + "F1FFFF212"); + + // self-IP going on the boundary then into the exterior and to the boundary again + test_geometry<ls, poly>("LINESTRING(2 10,5 10,5 15,6 15,5 10,8 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "F11F0F212"); + // self-IP going on the boundary then into the interior and to the boundary again + test_geometry<ls, poly>("LINESTRING(2 10,5 10,5 5,6 5,5 10,8 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "11FF0F212"); + + // self-IP with a hole -> B to I to B to E + test_geometry<ls, poly>("LINESTRING(0 0,3 3)", "POLYGON((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 9,1 9,0 0))", + "FF1F00212"); + + // ccw + { + typedef bg::model::polygon<P, false> ccwpoly; + + // IE IB0 II + test_geometry<ls, ccwpoly>("LINESTRING(11 1,10 5,5 5)", "POLYGON((0 0,10 0,10 10,0 10,0 0))", "1010F0212"); + // IE IB1 II + test_geometry<ls, ccwpoly>("LINESTRING(11 1,10 1,10 5,5 5)", "POLYGON((0 0,10 0,10 10,0 10,0 0))", "1110F0212"); + test_geometry<ls, ccwpoly>("LINESTRING(11 1,10 5,10 1,5 5)", "POLYGON((0 0,10 0,10 10,0 10,0 0))", "1110F0212"); + // II IB0 IE + test_geometry<ls, ccwpoly>("LINESTRING(5 1,10 5,11 1)", "POLYGON((0 0,10 0,10 10,0 10,0 0))", "1010F0212"); + // IE IB1 II + test_geometry<ls, ccwpoly>("LINESTRING(5 5,10 1,10 5,11 5)", "POLYGON((0 0,10 0,10 10,0 10,0 0))", "1110F0212"); + test_geometry<ls, ccwpoly>("LINESTRING(5 5,10 5,10 1,11 5)", "POLYGON((0 0,10 0,10 10,0 10,0 0))", "1110F0212"); + + } + + { + // SPIKES + + test_geometry<ls, poly>("LINESTRING(0 0,2 2,3 3,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(0 0,3 3,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(0 0,2 2,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(1 1,3 3,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(1 1,2 2,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FFFF212"); + + test_geometry<ls, poly>("LINESTRING(3 3,1 1,0 0,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(3 3,0 0,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(2 2,0 0,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(3 3,1 1,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(2 2,1 1,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FFFF212"); + + test_geometry<ls, poly>("LINESTRING(0 0,2 2,4 4,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F11F0F212"); + + test_geometry<ls, poly>("LINESTRING(0 1,1 1,0 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F01FFF212"); + test_geometry<ls, poly>("LINESTRING(0 1,3 3,0 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F01FFF212"); + test_geometry<ls, poly>("LINESTRING(0 1,0 0,0 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F01FFF212"); + + test_geometry<ls, poly>("LINESTRING(0 1,1 1,-1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F01FF0212"); + } + + { + // POLYGON SPIKES + // note that those are invalid Polygons and in general the result is undefined + + // MySQL bug 15.12.2014 (assertion for invalid polygon) + test_geometry<ls, poly>("LINESTRING(6 3,9 0)", + "POLYGON((0 0,5 8,6 1,6 3,8 1,5 4,9 6,2 5,7 4,1 7,0 0))", + "F11F00212"); + test_geometry<ls, poly>("LINESTRING(9 0,2 7)", + "POLYGON((4 1,3 2,5 9,8 4,4 5,3 6,8 1,6 2,2 4,6 0,4 1))", + "F11FF0212"); + + test_geometry<ls, poly>("LINESTRING(6 3,9 0)", + "POLYGON((6 1,6 3,8 1,5 4,6 1))", + "F11F00212"); + test_geometry<ls, poly>("LINESTRING(6 3,8 1,9 0)", + "POLYGON((6 1,6 3,8 1,5 4,6 1))", + "F11F00212"); + + // entry-point spikes are not handled + test_geometry<ls, poly>("LINESTRING(9 0,6 3)", + "POLYGON((6 1,6 3,8 1,5 4,6 1))", + "**1*00212"); + test_geometry<ls, poly>("LINESTRING(9 0,8 1,6 3)", + "POLYGON((6 1,6 3,8 1,5 4,6 1))", + "F11F00212"); + + // Ls going out-in on 2 collinear spikes touching each other + // this works partially, other invalid effect is noticeable here, + // the bottom of a spike shouldn't be there so the algorithm + // thinks the linestring is going into the interior + test_geometry<ls, poly>("LINESTRING(2 2,6 6)", + "POLYGON((0 0,0 2,2 2,4 4,3 3,5 3,5 5,4 4,7 7,7 0,0 0))", + "*1FF0F212"); + // Ls going out-in on 2 collinear spikes NOT touching each other + // This is not supported, plus the same as above + test_geometry<ls, poly>("LINESTRING(2 2,6 6)", + "POLYGON((0 0,0 2,2 2,3 3,2 2,5 3,5 5,4 4,7 7,7 0,0 0))", + "*1*F0*212"); + } + + // 21.01.2015 + test_geometry<ls, poly>("LINESTRING(3 7, 9 1)", + "POLYGON((0 0,0 10,10 10,10 0,5 5,0 0))", + "11F00F212"); + + // inspired by the bug for mls/poly + test_geometry<ls, poly>("LINESTRING(0 0, 7 7)", + "POLYGON((5 5,5 15,15 15,15 5,5 5))", + "1010F0212"); + + // 25.01.2015 + test_geometry<ls, poly>("LINESTRING(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))", + "11FF0F212"); + 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))", + "11F00F212"); + test_geometry<ls, poly>("LINESTRING(2 9, 1 1, 10 1, 10 10, 1 10, 0 6, 5 6)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(4 4,4 6,6 6,6 4,4 4))", + "11F00F212"); +} + +template <typename P> +void test_linestring_multi_polygon() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::polygon<P> poly; + typedef bg::model::multi_polygon<poly> mpoly; + + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,10 9)", + "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,10 9)", + "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0)))", + "F1FF0F212"); + + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)", + "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)", + "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0)))", + "11F00F212"); + + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 8)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,3 3)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,3 7)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,5 5)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "11F00F212"); + + test_geometry<ls, mpoly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((20 0,20 10,30 20,20 0)))", + "F1FFFF212"); + + // degenerated points + test_geometry<ls, mpoly>("LINESTRING(5 5,10 10,10 10,10 10,15 15)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((10 10,10 20,20 20,20 10,10 10)))", + "10F0FF212"); + + // self-IP polygon with a hole and second polygon with a hole -> B to I to B to B to I to B to E + test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 9,1 9,0 0)),((0 0,2 8,8 8,8 2,0 0),(0 0,7 3,7 7,3 7,0 0)))", + "FF1F00212"); + // self-IP polygon with a hole and second polygon -> B to I to B to B to I + test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 9,1 9,0 0)),((0 0,2 8,8 8,8 2,0 0)))", + "1FF00F212"); + test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)", + "MULTIPOLYGON(((0 0,2 8,8 8,8 2,0 0)),((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 9,1 9,0 0)))", + "1FF00F212"); + + // MySQL report 18.12.2014 (https://svn.boost.org/trac/boost/ticket/10887) + test_geometry<ls, mpoly>("LINESTRING(5 -2,5 2)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "10F0FF212"); + test_geometry<ls, mpoly>("LINESTRING(5 -2,5 5)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "10F00F212"); + test_geometry<ls, mpoly>("LINESTRING(5 -2,5 0)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "1FF00F212"); + // MySQL report 18.12.2014 - extended + test_geometry<ls, mpoly>("LINESTRING(5 -2,5 0)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)),((5 0,7 1,7 -1,5 0)))", + "1FF00F212"); + test_geometry<ls, mpoly>("LINESTRING(0 0,5 0)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)),((5 0,7 1,7 -1,5 0)))", + "FF1F00212"); + + // 22.01.2015 + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,10 0)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "11F00F212"); + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,0 10)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "11F00F212"); + // extended + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,2 1)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "10F0FF212"); + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,5 -5)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "1010F0212"); + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,5 -5,5 1)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "1010FF212"); + test_geometry<ls, mpoly>("LINESTRING(-5 5,0 0,5 -5)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "F01FF0212"); +} + +template <typename P> +void test_multi_linestring_polygon() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::multi_linestring<ls> mls; + typedef bg::model::polygon<P> poly; + typedef typename bg::coordinate_type<P>::type coord_t; + + test_geometry<mls, poly>("MULTILINESTRING((11 11, 20 20),(5 7, 4 1))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,4 2,4 4,2 4,2 2))", + "1F10F0212"); + test_geometry<mls, poly>("MULTILINESTRING((10 0, 18 12),(2 2,2 1))", + "POLYGON((5 0,0 -5,-5 0,0 5,5 0))", + "1F10F0212"); + + if ( BOOST_GEOMETRY_CONDITION(( + boost::is_same<coord_t, double>::value )) ) + { + // assertion failure in 1.57 + test_geometry<mls, poly>("MULTILINESTRING((-0.59322033898305082 -8.0508474576271194,-2.882352941176471 -7.7647058823529411,-2.8823529411764706 -7.7647058823529411,-3.7361111111111112 -6.5694444444444446,-3.4404145077720205 -5.766839378238342,-4.1864406779661012 -3.6779661016949152,-7.5252525252525251 -5.5858585858585865,-7.5862068965517242 -5.1896551724137936,-4.47887323943662 -2.859154929577465,-4.5789473684210531 -2.5789473684210527,-3 -1,-2.9310344827586206 -0.86206896551724144,-3.1764705882352944 -0.70588235294117663,-4.7401960784313726 -2.1274509803921577,-5.3255813953488369 -0.48837209302325502,-4.7872340425531918 0.31914893617021284,-5.8571428571428577 1.0000000000000007,-5.3255813953488369 -0.48837209302325502,-5.9473684210526319 -1.4210526315789465,-8 2,-7.7333333333333334 2.1939393939393939,-8.8294573643410867 2.891472868217055,-8.8556701030927822 3.061855670103093,-7.5999999999999996 3.6000000000000001,-7.7999999999999998 3.7999999999999998,-7.75 3.7916666666666665,-7.5471698113207548 3.6226415094339623,-7.3200000000000003 3.7200000000000002,-3.473684210526315 3.0789473684210527,-3.2549019607843133 3.2156862745098036,-2.9999999999999982 3.1428571428571423,-3.1733333333333325 3.2666666666666666,-2.9180327868852456 3.4262295081967209,-2.8723404255319145 3.1063829787234041,-2.1111111111111112 2.8888888888888888,-2.1428571428571428 2.8571428571428572,-1.8433734939759043 2.8072289156626509,-1.8396226415094346 2.8113207547169816,-1.6486486486486487 2.756756756756757,-1.76510067114094 2.8926174496644301,-0.53846153846153855 4.2307692307692308,1.8148148148148147 5.4074074074074074,1.588235294117647 2.2352941176470589,1.819672131147541 2.1967213114754101,2 4,2 2.1666666666666665,2.3538461538461544 2.1076923076923078,2 1.6875000000000004,2 -2,1.2173913043478262 -3.8260869565217392,1.7375886524822697 1.3758865248226959,1.5073170731707317 1.1024390243902444,1.1428571428571428 -4,-0.59322033898305082 -8.0508474576271194),(1.666666666666667 1.5999999999999988,1.5675675675675675 1.8378378378378377,1.4374999999999991 1.8750000000000002,1.0487804878048776 2.3414634146341466,0.46666666666666712 2.6060606060606055,0.086956521739131043 2.2608695652173911,1.4374999999999991 1.8750000000000002,1.666666666666667 1.5999999999999988))", + "POLYGON((-2.333333333333333 -8.6666666666666661,-4.3253012048192767 -8.168674698795181,-4.1194968553459113 -7.6100628930817606,-2.8823529411764706 -7.7647058823529411,-2.882352941176471 -7.7647058823529411,-2.263157894736842 -8.6315789473684212,-2.333333333333333 -8.6666666666666661))", + "*********"); + test_geometry<mls, poly>("MULTILINESTRING((-2.333333333333333 -8.6666666666666661,-4.3253012048192767 -8.168674698795181,-4.1194968553459113 -7.6100628930817606,-2.8823529411764706 -7.7647058823529411,-2.882352941176471 -7.7647058823529411,-2.263157894736842 -8.6315789473684212,-2.333333333333333 -8.6666666666666661))", + "POLYGON((-0.59322033898305082 -8.0508474576271194,-2.882352941176471 -7.7647058823529411,-2.8823529411764706 -7.7647058823529411,-3.7361111111111112 -6.5694444444444446,-3.4404145077720205 -5.766839378238342,-4.1864406779661012 -3.6779661016949152,-7.5252525252525251 -5.5858585858585865,-7.5862068965517242 -5.1896551724137936,-4.47887323943662 -2.859154929577465,-4.5789473684210531 -2.5789473684210527,-3 -1,-2.9310344827586206 -0.86206896551724144,-3.1764705882352944 -0.70588235294117663,-4.7401960784313726 -2.1274509803921577,-5.3255813953488369 -0.48837209302325502,-4.7872340425531918 0.31914893617021284,-5.8571428571428577 1.0000000000000007,-5.3255813953488369 -0.48837209302325502,-5.9473684210526319 -1.4210526315789465,-8 2,-7.7333333333333334 2.1939393939393939,-8.8294573643410867 2.891472868217055,-8.8556701030927822 3.061855670103093,-7.5999999999999996 3.6000000000000001,-7.7999999999999998 3.7999999999999998,-7.75 3.7916666666666665,-7.5471698113207548 3.6226415094339623,-7.3200000000000003 3.7200000000000002,-3.473684210526315 3.0789473684210527,-3.2549019607843133 3.2156862745098036,-2.9999999999999982 3.1428571428571423,-3.1733333333333325 3.2666666666666666,-2.9180327868852456 3.4262295081967209,-2.8723404255319145 3.1063829787234041,-2.1111111111111112 2.8888888888888888,-2.1428571428571428 2.8571428571428572,-1.8433734939759043 2.8072289156626509,-1.8396226415094346 2.8113207547169816,-1.6486486486486487 2.756756756756757,-1.76510067114094 2.8926174496644301,-0.53846153846153855 4.2307692307692308,1.8148148148148147 5.4074074074074074,1.588235294117647 2.2352941176470589,1.819672131147541 2.1967213114754101,2 4,2 2.1666666666666665,2.3538461538461544 2.1076923076923078,2 1.6875000000000004,2 -2,1.2173913043478262 -3.8260869565217392,1.7375886524822697 1.3758865248226959,1.5073170731707317 1.1024390243902444,1.1428571428571428 -4,-0.59322033898305082 -8.0508474576271194),(1.666666666666667 1.5999999999999988,1.5675675675675675 1.8378378378378377,1.4374999999999991 1.8750000000000002,1.0487804878048776 2.3414634146341466,0.46666666666666712 2.6060606060606055,0.086956521739131043 2.2608695652173911,1.4374999999999991 1.8750000000000002,1.666666666666667 1.5999999999999988))", + "*********"); + } + + // 21.01.2015 + test_geometry<mls, poly>("MULTILINESTRING((6 6,15 15),(0 0, 7 7))", + "POLYGON((5 5,5 15,15 15,15 5,5 5))", + "101000212"); + test_geometry<mls, poly>("MULTILINESTRING((15 15,6 6),(0 0, 7 7))", + "POLYGON((5 5,5 15,15 15,15 5,5 5))", + "101000212"); + // extended + test_geometry<mls, poly>("MULTILINESTRING((15 15,6 6),(4 14,6 16))", + "POLYGON((5 5,5 15,15 15,15 5,5 5))", + "101000212"); + + // 23.01.2015 + test_geometry<mls, poly>("MULTILINESTRING((4 10, 3 10, 10 6),(5 0, 7 5, 9 10))", + "POLYGON((0 0,0 10,10 10,10 0,5 5,0 0))", + "111F00212"); + + // 23.01.2015 + test_geometry<mls, poly>("MULTILINESTRING((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))", + "10FF0F212"); + + // mysql bug + // assertion failure in relate->boundary_checker->std::equal_range with msvc + if (BOOST_GEOMETRY_CONDITION(is_nan_case_supported<mls>::value)) + { + mls g1; + std::string wkt1; + nan_case(g1, wkt1); + + std::string wkt2 = "POLYGON((1.1e+308 1.2e+308,-1 -9,1 1e+12,1.1e+308 7.8e+307,1.1e+308 1.2e+308),(3 2,1 1,8e+307 1e+308,3 2),(258 2049,1 -3,1 1,-6 9,258 2049))"; + poly g2; + bg::read_wkt(wkt2, g2); + + check_geometry(g1, g2, wkt1, wkt2, "*********"); + } +} + +template <typename P> +void test_multi_linestring_multi_polygon() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::polygon<P> poly; + typedef bg::model::multi_linestring<ls> mls; + typedef bg::model::multi_polygon<poly> mpoly; + + // polygons with some ring equal to the linestrings + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10,0 10,0 0),(20 20,50 50,20 80,20 20))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "F11FFF2F2"); + + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10,0 10,0 0),(2 2,5 5,2 8,2 2))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2)))", + "F1FFFF2F2"); + + + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10),(10 10,0 10,0 0))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "F1FFFF2F2"); + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10),(10 10,0 10,0 0),(20 20,50 50,20 80,20 20))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "F11FFF2F2"); + + // disjoint + test_geometry<mls, mpoly>("MULTILINESTRING((20 20,30 30),(30 30,40 40))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "FF1FF0212"); + + test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 5),(5 5,5 0),(10 10,10 5,5 5,5 10,10 10))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0)),((5 5,5 10,10 10,10 5,5 5)),((5 5,10 1,10 0,5 5)))", + "F1FF0F212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 5),(5 5,5 0),(0 5,0 0,5 0),(10 10,10 5,5 5,5 10,10 10))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0)),((5 5,5 10,10 10,10 5,5 5)),((5 5,10 1,10 0,5 5)))", + "F1FFFF212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 0),(5 5,5 0),(10 10,10 5,5 5,5 10,10 10))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0)),((5 5,5 10,10 10,10 5,5 5)),((5 5,10 1,10 0,5 5)))", + "11FF0F212"); + + // MySQL report 18.12.2014 - extended + test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,4 -2,5 0),(5 -2,6 -2,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "10FFFF212"); + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,0 1,5 0),(0 0,0 -1,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "F01FFF212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,4 -2,5 0),(6 -2,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "10F0FF212"); + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,0 1,5 0),(0 -1,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "F01FF0212"); + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,5 0),(5 -2,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "1010F0212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,5 0),(0 0,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "1010F0212"); + + // 22.01.2015 - extended + test_geometry<mls, mpoly>("MULTILINESTRING((10 10,0 10),(5 5,0 0,10 0))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "11F00F212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 0,5 -5),(0 0,9 1))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "101000212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 -5,0 0,5 5),(0 0,5 -1))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "101000212"); +} + +template <typename P> +void test_all() +{ + test_linestring_polygon<P>(); + test_linestring_multi_polygon<P>(); + test_multi_linestring_polygon<P>(); + test_multi_linestring_multi_polygon<P>(); +} + +int test_main( int , char* [] ) +{ + test_all<bg::model::d2::point_xy<int> >(); + test_all<bg::model::d2::point_xy<double> >(); + +#if defined(HAVE_TTMATH) + test_all<bg::model::d2::point_xy<ttmath_big> >(); +#endif + + return 0; +} diff --git a/src/boost/libs/geometry/test/algorithms/relate/relate_linear_areal_sph.cpp b/src/boost/libs/geometry/test/algorithms/relate/relate_linear_areal_sph.cpp new file mode 100644 index 00000000..ec7b4173 --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/relate_linear_areal_sph.cpp @@ -0,0 +1,419 @@ +// Boost.Geometry +// Unit Test + +// Copyright (c) 2016, 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_relate.hpp" + + +template <typename P> +void test_linestring_polygon() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::polygon<P> poly; + typedef bg::model::ring<P> ring; + + // LS disjoint + test_geometry<ls, poly>("LINESTRING(11 0,11 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212"); + test_geometry<ls, ring>("LINESTRING(11 0,11 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212"); + + // II BB + test_geometry<ls, poly>("LINESTRING(0 0,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1FFF0F212"); + test_geometry<ls, poly>("LINESTRING(5 0,5 5,10 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1FFF0F212"); + test_geometry<ls, poly>("LINESTRING(5 1,5 5,9 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1FF0FF212"); + + // IE + test_geometry<ls, poly>("LINESTRING(11 1,11 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212"); + // IE IB0 + test_geometry<ls, poly>("LINESTRING(11 1,10 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1F00212"); + // IE IB1 + test_geometry<ls, poly>("LINESTRING(11 1,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + test_geometry<ls, poly>("LINESTRING(11 1,10 10,0 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + test_geometry<ls, poly>("LINESTRING(11 1,10 0,0 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + test_geometry<ls, poly>("LINESTRING(0 -1,1 0,2 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + // IE IB0 II + test_geometry<ls, poly>("LINESTRING(11 1,10 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212"); + // IE IB0 lring + test_geometry<ls, poly>("LINESTRING(11 1,10 5,11 5,11 1)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F01FFF212"); + // IE IB1 lring + test_geometry<ls, poly>("LINESTRING(11 1,10 5,10 10,11 5,11 1)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11FFF212"); + + // IB1 II + test_geometry<ls, poly>("LINESTRING(0 0,5 0,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212"); + // BI0 II IB1 + test_geometry<ls, poly>("LINESTRING(5 0,5 5,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11FF0F212"); + + // IB1 II IB1 + test_geometry<ls, poly>("LINESTRING(1 0,2 0,3 1,4 0,5 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11FF0F212"); + // IB1 IE IB1 + test_geometry<ls, poly>("LINESTRING(1 0,2 0,3 -1,4 0,5 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F0F212"); + + // II IB1 + test_geometry<ls, poly>("LINESTRING(5 5,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212"); + // IB1 II + test_geometry<ls, poly>("LINESTRING(10 10,10 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212"); + // IE IB1 + test_geometry<ls, poly>("LINESTRING(15 5,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + // IB1 IE + test_geometry<ls, poly>("LINESTRING(10 10,10 5,15 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212"); + + // duplicated points + { + // II IB0 IE + test_geometry<ls, poly>("LINESTRING(5 5,10 5,15 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212"); + test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5,10 5,10 5,10 5,15 10,15 10,15 10)", + "POLYGON((0 0,0 0,0 0,0 10,0 10,0 10,10 10,10 10,10 10,10 0,10 0,10 0,0 0,0 0,0 0))", + "1010F0212"); + test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5,10 0,10 0,10 0,15 10,15 10,15 10)", + "POLYGON((0 0,0 0,0 0,0 10,0 10,0 10,10 10,10 10,10 10,10 0,10 0,10 0,0 0,0 0,0 0))", + "1010F0212"); + // IE IB0 II + test_geometry<ls, poly>("LINESTRING(15 10,15 10,15 10,10 5,10 5,10 5,5 5,5 5,5 5)", + "POLYGON((0 0,0 0,0 0,0 10,0 10,0 10,10 10,10 10,10 10,10 0,10 0,10 0,0 0,0 0,0 0))", + "1010F0212"); + test_geometry<ls, poly>("LINESTRING(15 10,15 10,15 10,10 0,10 0,10 0,5 5,5 5,5 5)", + "POLYGON((0 0,0 0,0 0,0 10,0 10,0 10,10 10,10 10,10 10,10 0,10 0,10 0,0 0,0 0,0 0))", + "1010F0212"); + + // TEST + //test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212"); + test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5,15 5,15 5,15 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212"); + } + + // non-simple polygon with hole + test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "10F0FF212"); + test_geometry<ls, poly>("LINESTRING(10 1,10 5,10 9)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(2 8,10 5,2 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(10 1,10 5,2 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(10 1,10 5,2 8)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F1FF0F212"); + + // non-simple polygon with hole, linear ring + test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9,1 9,1 1,9 1)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "10FFFF212"); + test_geometry<ls, poly>("LINESTRING(10 5,10 9,11 5,10 1,10 5)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F11FFF212"); + test_geometry<ls, poly>("LINESTRING(11 5,10 1,10 5,10 9,11 5)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))", + "F11FFF212"); + + // non-simple polygon with self-touching holes + test_geometry<ls, poly>("LINESTRING(7 1,8 5,7 9)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(8 1,9 1,9 9,8 9,8 1),(2 2,8 5,2 8,2 2))", + "10F0FF212"); + test_geometry<ls, poly>("LINESTRING(8 2,8 5,8 8)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(8 1,9 1,9 9,8 9,8 1),(2 2,8 5,2 8,2 2))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(2 8,8 5,2 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(8 1,9 1,9 9,8 9,8 1),(2 2,8 5,2 8,2 2))", + "F1FF0F212"); + + // non-simple polygon self-touching + test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "10F0FF212"); + test_geometry<ls, poly>("LINESTRING(10 1,10 5,10 9)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "F1FF0F212"); + test_geometry<ls, poly>("LINESTRING(2 8,10 5,2 2)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "F1FF0F212"); + + // non-simple polygon self-touching, linear ring + test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9,1 9,1 1,9 1)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "10FFFF212"); + test_geometry<ls, poly>("LINESTRING(10 5,10 9,11 5,10 1,10 5)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "F11FFF212"); + test_geometry<ls, poly>("LINESTRING(11 5,10 1,10 5,10 9,11 5)", + "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))", + "F11FFF212"); + + // polygons with some ring equal to the linestring + test_geometry<ls, poly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "F1FFFF2F2"); + test_geometry<ls, poly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2))", + "F1FFFF212"); + test_geometry<ls, poly>("LINESTRING(2 2,5 5,2 8,2 2)", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2))", + "F1FFFF212"); + + // self-IP going on the boundary then into the exterior and to the boundary again + test_geometry<ls, poly>("LINESTRING(2 10.023946271183535,5 10.037423045910710,5 15,6 15,5 10.037423045910710,8 10.023946271183535)", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "F11F0F212"); + // self-IP going on the boundary then into the interior and to the boundary again + test_geometry<ls, poly>("LINESTRING(2 10.023946271183535,5 10.037423045910710,5 5,6 5,5 10.037423045910710,8 10.023946271183535)", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "11FF0F212"); + + // self-IP with a hole -> B to I to B to E + test_geometry<ls, poly>("LINESTRING(0 0,3 3)", "POLYGON((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 9,1 9,0 0))", + "FF1F00212"); +} + +template <typename P> +void test_linestring_multi_polygon() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::polygon<P> poly; + typedef bg::model::multi_polygon<poly> mpoly; + + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,10 9)", + "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,10 9)", + "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0)))", + "F1FF0F212"); + + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)", + "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)", + "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0)))", + "11F00F212"); + + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 8)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,3 3)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,3 7)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "F1FF0F212"); + test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,5 5)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5)),((10 5,3 3,3 7,10 5)))", + "11F00F212"); + + test_geometry<ls, mpoly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((20 0,20 10,30 20,20 0)))", + "F1FFFF212"); + + // degenerated points + test_geometry<ls, mpoly>("LINESTRING(5 5,10 10,10 10,10 10,15 15)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((10 10,10 20,20 20,20 10,10 10)))", + "10F0FF212"); + + // self-IP polygon with a hole and second polygon with a hole -> B to I to B to B to I to B to E + test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 9,1 9,0 0)),((0 0,2 8,8 8,8 2,0 0),(0 0,7 3,7 7,3 7,0 0)))", + "FF1F00212"); + // self-IP polygon with a hole and second polygon -> B to I to B to B to I + test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 9,1 9,0 0)),((0 0,2 8,8 8,8 2,0 0)))", + "1FF00F212"); + test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)", + "MULTIPOLYGON(((0 0,2 8,8 8,8 2,0 0)),((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 9,1 9,0 0)))", + "1FF00F212"); + + // MySQL report 18.12.2014 (https://svn.boost.org/trac/boost/ticket/10887) + test_geometry<ls, mpoly>("LINESTRING(5 -2,5 2)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "10F0FF212"); + test_geometry<ls, mpoly>("LINESTRING(5 -2,5 5.0190018174896416)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "10F00F212"); + test_geometry<ls, mpoly>("LINESTRING(5 -2,5 0)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "1FF00F212"); + // MySQL report 18.12.2014 - extended + test_geometry<ls, mpoly>("LINESTRING(5 -2,5 0)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)),((5 0,7 1,7 -1,5 0)))", + "1FF00F212"); + test_geometry<ls, mpoly>("LINESTRING(0 0,5 0)", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)),((5 0,7 1,7 -1,5 0)))", + "FF1F00212"); + + // 22.01.2015 + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,10 0)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "11F00F212"); + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,0 10)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "11F00F212"); + // extended + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,2 1)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "10F0FF212"); + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,5 -5)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "1010F0212"); + test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,5 -5,5 1)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "1010FF212"); + test_geometry<ls, mpoly>("LINESTRING(-5 5,0 0,5 -5)", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "F01FF0212"); +} + +template <typename P> +void test_multi_linestring_polygon() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::multi_linestring<ls> mls; + typedef bg::model::polygon<P> poly; + typedef bg::model::ring<P> ring; + typedef typename bg::coordinate_type<P>::type coord_t; + + test_geometry<mls, poly>("MULTILINESTRING((11 11, 20 20),(5 7, 4 1))", + "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,4 2,4 4,2 4,2 2))", + "1F10F0212"); + test_geometry<mls, poly>("MULTILINESTRING((10 0, 18 12),(2 2,2 1))", + "POLYGON((5 0,0 -5,-5 0,0 5,5 0))", + "1F10F0212"); + + if ( BOOST_GEOMETRY_CONDITION(( + boost::is_same<coord_t, double>::value )) ) + { + // assertion failure in 1.57 + test_geometry<mls, poly>("MULTILINESTRING((-0.59322033898305082 -8.0508474576271194,-2.882352941176471 -7.7647058823529411,-2.8823529411764706 -7.7647058823529411,-3.7361111111111112 -6.5694444444444446,-3.4404145077720205 -5.766839378238342,-4.1864406779661012 -3.6779661016949152,-7.5252525252525251 -5.5858585858585865,-7.5862068965517242 -5.1896551724137936,-4.47887323943662 -2.859154929577465,-4.5789473684210531 -2.5789473684210527,-3 -1,-2.9310344827586206 -0.86206896551724144,-3.1764705882352944 -0.70588235294117663,-4.7401960784313726 -2.1274509803921577,-5.3255813953488369 -0.48837209302325502,-4.7872340425531918 0.31914893617021284,-5.8571428571428577 1.0000000000000007,-5.3255813953488369 -0.48837209302325502,-5.9473684210526319 -1.4210526315789465,-8 2,-7.7333333333333334 2.1939393939393939,-8.8294573643410867 2.891472868217055,-8.8556701030927822 3.061855670103093,-7.5999999999999996 3.6000000000000001,-7.7999999999999998 3.7999999999999998,-7.75 3.7916666666666665,-7.5471698113207548 3.6226415094339623,-7.3200000000000003 3.7200000000000002,-3.473684210526315 3.0789473684210527,-3.2549019607843133 3.2156862745098036,-2.9999999999999982 3.1428571428571423,-3.1733333333333325 3.2666666666666666,-2.9180327868852456 3.4262295081967209,-2.8723404255319145 3.1063829787234041,-2.1111111111111112 2.8888888888888888,-2.1428571428571428 2.8571428571428572,-1.8433734939759043 2.8072289156626509,-1.8396226415094346 2.8113207547169816,-1.6486486486486487 2.756756756756757,-1.76510067114094 2.8926174496644301,-0.53846153846153855 4.2307692307692308,1.8148148148148147 5.4074074074074074,1.588235294117647 2.2352941176470589,1.819672131147541 2.1967213114754101,2 4,2 2.1666666666666665,2.3538461538461544 2.1076923076923078,2 1.6875000000000004,2 -2,1.2173913043478262 -3.8260869565217392,1.7375886524822697 1.3758865248226959,1.5073170731707317 1.1024390243902444,1.1428571428571428 -4,-0.59322033898305082 -8.0508474576271194),(1.666666666666667 1.5999999999999988,1.5675675675675675 1.8378378378378377,1.4374999999999991 1.8750000000000002,1.0487804878048776 2.3414634146341466,0.46666666666666712 2.6060606060606055,0.086956521739131043 2.2608695652173911,1.4374999999999991 1.8750000000000002,1.666666666666667 1.5999999999999988))", + "POLYGON((-2.333333333333333 -8.6666666666666661,-4.3253012048192767 -8.168674698795181,-4.1194968553459113 -7.6100628930817606,-2.8823529411764706 -7.7647058823529411,-2.882352941176471 -7.7647058823529411,-2.263157894736842 -8.6315789473684212,-2.333333333333333 -8.6666666666666661))", + "*********"); + test_geometry<mls, poly>("MULTILINESTRING((-2.333333333333333 -8.6666666666666661,-4.3253012048192767 -8.168674698795181,-4.1194968553459113 -7.6100628930817606,-2.8823529411764706 -7.7647058823529411,-2.882352941176471 -7.7647058823529411,-2.263157894736842 -8.6315789473684212,-2.333333333333333 -8.6666666666666661))", + "POLYGON((-0.59322033898305082 -8.0508474576271194,-2.882352941176471 -7.7647058823529411,-2.8823529411764706 -7.7647058823529411,-3.7361111111111112 -6.5694444444444446,-3.4404145077720205 -5.766839378238342,-4.1864406779661012 -3.6779661016949152,-7.5252525252525251 -5.5858585858585865,-7.5862068965517242 -5.1896551724137936,-4.47887323943662 -2.859154929577465,-4.5789473684210531 -2.5789473684210527,-3 -1,-2.9310344827586206 -0.86206896551724144,-3.1764705882352944 -0.70588235294117663,-4.7401960784313726 -2.1274509803921577,-5.3255813953488369 -0.48837209302325502,-4.7872340425531918 0.31914893617021284,-5.8571428571428577 1.0000000000000007,-5.3255813953488369 -0.48837209302325502,-5.9473684210526319 -1.4210526315789465,-8 2,-7.7333333333333334 2.1939393939393939,-8.8294573643410867 2.891472868217055,-8.8556701030927822 3.061855670103093,-7.5999999999999996 3.6000000000000001,-7.7999999999999998 3.7999999999999998,-7.75 3.7916666666666665,-7.5471698113207548 3.6226415094339623,-7.3200000000000003 3.7200000000000002,-3.473684210526315 3.0789473684210527,-3.2549019607843133 3.2156862745098036,-2.9999999999999982 3.1428571428571423,-3.1733333333333325 3.2666666666666666,-2.9180327868852456 3.4262295081967209,-2.8723404255319145 3.1063829787234041,-2.1111111111111112 2.8888888888888888,-2.1428571428571428 2.8571428571428572,-1.8433734939759043 2.8072289156626509,-1.8396226415094346 2.8113207547169816,-1.6486486486486487 2.756756756756757,-1.76510067114094 2.8926174496644301,-0.53846153846153855 4.2307692307692308,1.8148148148148147 5.4074074074074074,1.588235294117647 2.2352941176470589,1.819672131147541 2.1967213114754101,2 4,2 2.1666666666666665,2.3538461538461544 2.1076923076923078,2 1.6875000000000004,2 -2,1.2173913043478262 -3.8260869565217392,1.7375886524822697 1.3758865248226959,1.5073170731707317 1.1024390243902444,1.1428571428571428 -4,-0.59322033898305082 -8.0508474576271194),(1.666666666666667 1.5999999999999988,1.5675675675675675 1.8378378378378377,1.4374999999999991 1.8750000000000002,1.0487804878048776 2.3414634146341466,0.46666666666666712 2.6060606060606055,0.086956521739131043 2.2608695652173911,1.4374999999999991 1.8750000000000002,1.666666666666667 1.5999999999999988))", + "*********"); + } + + // 21.01.2015 + test_geometry<mls, poly>("MULTILINESTRING((6 6,15 15),(0 0, 7 7))", + "POLYGON((5 5,5 15,15 15,15 5,5 5))", + "101000212"); + test_geometry<mls, poly>("MULTILINESTRING((15 15,6 6),(0 0, 7 7))", + "POLYGON((5 5,5 15,15 15,15 5,5 5))", + "101000212"); + + // extended + test_geometry<mls, ring>("MULTILINESTRING((15 15,6 6),(4 14,6 15.986412732589057))", + "POLYGON((5 5,5 15,15 15,15 5,5 5))", + "101000212"); + + // 23.01.2015 + test_geometry<mls, poly>("MULTILINESTRING((4 10.035925377760330, 3 10.031432746397092, 10 6),(5 0, 7 5, 9 10.013467818052765))", + "POLYGON((0 0,0 10,10 10,10 0,5 5,0 0))", + "111F00212"); + + // 23.01.2015 + test_geometry<mls, poly>("MULTILINESTRING((3 10.031432746397092, 1 5, 1 10.013467818052765, 3 4, 7 8, 6 10.035925377760330, 10 2))", + "POLYGON((0 0,0 10,10 10,10 0,0 0))", + "10FF0F212"); +} + +template <typename P> +void test_multi_linestring_multi_polygon() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::polygon<P> poly; + typedef bg::model::multi_linestring<ls> mls; + typedef bg::model::multi_polygon<poly> mpoly; + + // polygons with some ring equal to the linestrings + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10,0 10,0 0),(20 20,50 50,20 80,20 20))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "F11FFF2F2"); + + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10,0 10,0 0),(2 2,5 5,2 8,2 2))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2)))", + "F1FFFF2F2"); + + + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10),(10 10,0 10,0 0))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "F1FFFF2F2"); + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10),(10 10,0 10,0 0),(20 20,50 50,20 80,20 20))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "F11FFF2F2"); + + // disjoint + test_geometry<mls, mpoly>("MULTILINESTRING((20 20,30 30),(30 30,40 40))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))", + "FF1FF0212"); + + test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 5),(5 5,5 0),(10 10,10 5,5 5,5 10,10 10))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0)),((5 5,5 10,10 10,10 5,5 5)),((5 5,10 1,10 0,5 5)))", + "F1FF0F212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 5),(5 5,5 0),(0 5,0 0,5 0),(10 10,10 5,5 5,5 10,10 10))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0)),((5 5,5 10,10 10,10 5,5 5)),((5 5,10 1,10 0,5 5)))", + "F1FFFF212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 0),(5 5,5 0),(10 10,10 5,5 5,5 10,10 10))", + "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0)),((5 5,5 10,10 10,10 5,5 5)),((5 5,10 1,10 0,5 5)))", + "11FF0F212"); + + // MySQL report 18.12.2014 - extended + test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,4 -2,5 0),(5 -2,6 -2,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "10FFFF212"); + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,0 1,5 0),(0 0,0 -1,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "F01FFF212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,4 -2,5 0),(6 -2,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "10F0FF212"); + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,0 1,5 0),(0 -1,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "F01FF0212"); + test_geometry<mls, mpoly>("MULTILINESTRING((0 0,5 0),(5 -2,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "1010F0212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,5 0),(0 0,5 0))", + "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))", + "1010F0212"); + + // 22.01.2015 - extended + test_geometry<mls, mpoly>("MULTILINESTRING((10 10,0 10),(5 5,0 0,10 0))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "11F00F212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 0,5 -5),(0 0,9 1))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "101000212"); + test_geometry<mls, mpoly>("MULTILINESTRING((5 -5,0 0,5 5),(0 0,5 -1))", + "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))", + "101000212"); +} + +template <typename P> +void test_all() +{ + test_linestring_polygon<P>(); + test_linestring_multi_polygon<P>(); + test_multi_linestring_polygon<P>(); + test_multi_linestring_multi_polygon<P>(); +} + +int test_main( int , char* [] ) +{ + typedef bg::cs::spherical_equatorial<bg::degree> cs_t; + + test_all<bg::model::point<float, 2, cs_t> >(); + test_all<bg::model::point<double, 2, cs_t> >(); + +#if defined(HAVE_TTMATH) + test_all<bg::model::point<ttmath_big, 2, cs_t> >(); +#endif + + return 0; +} diff --git a/src/boost/libs/geometry/test/algorithms/relate/relate_linear_linear.cpp b/src/boost/libs/geometry/test/algorithms/relate/relate_linear_linear.cpp new file mode 100644 index 00000000..d2073a87 --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/relate_linear_linear.cpp @@ -0,0 +1,446 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. + +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-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_relate.hpp" + +//TEST +//#include <to_svg.hpp> + +template <typename P> +void test_linestring_linestring() +{ + typedef bg::model::linestring<P> ls; + + test_geometry<ls, ls>("LINESTRING(0 0, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 3 2)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(0 0,3 2)", "LINESTRING(0 0, 2 2, 3 2)", "FF1F0F1F2"); + test_geometry<ls, ls>("LINESTRING(1 0,2 2,2 3)", "LINESTRING(0 0, 2 2, 3 2)", "0F1FF0102"); + + test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(0 0,1 1,2 0,2 -1)", "0F1F00102"); + + test_geometry<ls, ls>("LINESTRING(0 0, 1 1, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 3 2)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(3 2, 2 2, 1 1, 0 0)", "LINESTRING(0 0, 2 2, 3 2)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(0 0, 1 1, 2 2, 3 2)", "LINESTRING(3 2, 2 2, 0 0)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(3 2, 2 2, 1 1, 0 0)", "LINESTRING(3 2, 2 2, 0 0)", "1FFF0FFF2"); + + test_geometry<ls, ls>("LINESTRING(3 1, 2 2, 1 1, 0 0)", "LINESTRING(0 0, 2 2, 3 2)", "1F1F00102"); + test_geometry<ls, ls>("LINESTRING(3 3, 2 2, 1 1, 0 0)", "LINESTRING(0 0, 2 2, 3 2)", "1F1F00102"); + + test_geometry<ls, ls>("LINESTRING(0 0, 1 1, 2 2, 2 3)", "LINESTRING(0 0, 2 2, 2 3)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(2 3, 2 2, 1 1, 0 0)", "LINESTRING(0 0, 2 2, 2 3)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(0 0, 1 1, 2 2, 2 3)", "LINESTRING(2 3, 2 2, 0 0)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(2 3, 2 2, 1 1, 0 0)", "LINESTRING(2 3, 2 2, 0 0)", "1FFF0FFF2"); + + test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", "1FF0FF102"); + + test_geometry<ls, ls>("LINESTRING(3 2, 2 2, 1 1)", "LINESTRING(0 0, 2 2, 4 2)", "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 2)", "LINESTRING(4 2, 2 2, 0 0)", "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(3 2, 2 2, 1 1)", "LINESTRING(4 2, 2 2, 0 0)", "1FF0FF102"); + +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 2 2)", "LINESTRING(0 0, 2 2, 4 2)", true); + +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 3)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 2, 3 3)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 1)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 2, 3 1)", "LINESTRING(0 0, 2 2, 4 2)", false); + +// test_geometry<ls, ls>("LINESTRING(0 1, 1 1, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(0 1, 0 0, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 0, 1 1, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 0, 0 0, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", false); + +// test_geometry<ls, ls>("LINESTRING(0 0)", "LINESTRING(0 0)", false); +// test_geometry<ls, ls>("LINESTRING(1 1)", "LINESTRING(0 0, 2 2)", true); +// test_geometry<ls, ls>("LINESTRING(0 0)", "LINESTRING(0 0, 2 2)", false); +// test_geometry<ls, ls>("LINESTRING(0 0, 1 1)", "LINESTRING(0 0)", false); + +// test_geometry<ls, ls>("LINESTRING(0 0,5 0,3 0,6 0)", "LINESTRING(0 0,6 0)", true); +// test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,1 1)", "LINESTRING(0 0,3 3,6 3)", true); + + // SPIKES! + test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,1 1,5 3)", "LINESTRING(0 0,3 3,6 3)", "1F100F102"); + test_geometry<ls, ls>("LINESTRING(5 3,1 1,3 3,2 2,0 0)", "LINESTRING(0 0,3 3,6 3)", "1F100F102"); + test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,1 1,5 3)", "LINESTRING(6 3,3 3,0 0)", "1F100F102"); + test_geometry<ls, ls>("LINESTRING(5 3,1 1,3 3,2 2,0 0)", "LINESTRING(6 3,3 3,0 0)", "1F100F102"); + + test_geometry<ls, ls>("LINESTRING(6 3,3 3,0 0)", "LINESTRING(0 0,2 2,3 3,1 1,5 3)", "101F001F2"); + + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", "LINESTRING(1 0,9 0,2 0)", "101FF0FF2"); + test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,1 1)", "LINESTRING(0 0,3 3,6 3)", "1FF00F102"); + // TODO: REWRITE MATRICES + // BEGIN + /*test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,1 1)", "LINESTRING(0 0,4 4,6 3)", "1FF00F102"); + + 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"); + + test_geometry<ls, ls>("LINESTRING(0 0,3 3,1 1)", "LINESTRING(3 0,3 3,3 1)", "0F1FF0102"); + test_geometry<ls, ls>("LINESTRING(0 0,3 3,1 1)", "LINESTRING(2 0,2 3,2 1)", "0F1FF0102"); + test_geometry<ls, ls>("LINESTRING(0 0,3 3,1 1)", "LINESTRING(2 0,2 2,2 1)", "0F1FF0102"); + + test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,4 4)", "LINESTRING(0 0,1 1,4 4)", "1FFF0FFF2");*/ + // END + + test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,4 4)", "LINESTRING(0 0,1 1,4 4)", "1FFF0FFF2"); + + // loop i/i i/i u/u u/u + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", + "LINESTRING(1 1,1 0,6 0,6 1,4 1,4 0,9 0,9 1)", "1F1FF0102"); + + // self-intersecting and self-touching equal + test_geometry<ls, ls>("LINESTRING(0 5,5 5,10 5,10 10,5 10,5 5,5 0)", + "LINESTRING(0 5,5 5,5 10,10 10,10 5,5 5,5 0)", "1FFF0FFF2"); + // self-intersecting loop and self-touching equal + test_geometry<ls, ls>("LINESTRING(0 5,5 5,10 5,10 10,5 10,5 5,10 5,10 10,5 10,5 5,5 0)", + "LINESTRING(0 5,5 5,5 10,10 10,10 5,5 5,5 0)", "1FFF0FFF2"); + + test_geometry<ls, ls>("LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", "0F1FF0102"); + test_geometry<ls, ls>("LINESTRING(0 0,1 1)", "LINESTRING(1 1,2 0)", "FF1F00102"); + test_geometry<ls, ls>("LINESTRING(0 0,1 1)", "LINESTRING(2 0,1 1)", "FF1F00102"); + + test_geometry<ls, ls>("LINESTRING(0 0,1 0,2 1,3 5,4 0)", "LINESTRING(1 0,2 1,3 5)", "101FF0FF2"); + test_geometry<ls, ls>("LINESTRING(0 0,1 0,2 1,3 5,4 0)", "LINESTRING(3 5,2 1,1 0)", "101FF0FF2"); + test_geometry<ls, ls>("LINESTRING(1 0,2 1,3 5)", "LINESTRING(4 0,3 5,2 1,1 0,0 0)", "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(3 5,2 1,1 0)", "LINESTRING(4 0,3 5,2 1,1 0,0 0)", "1FF0FF102"); + + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", "LINESTRING(-1 -1,1 0,10 0,20 -1)", "1F10F0102"); + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", "LINESTRING(20 -1,10 0,1 0,-1 -1)", "1F10F0102"); + + test_geometry<ls, ls>("LINESTRING(-1 1,0 0,1 0,5 0,5 5,10 5,15 0,31 0)", + "LINESTRING(-1 -1,0 0,1 0,2 0,3 1,4 0,30 0)", + "101FF0102"); + test_geometry<ls, ls>("LINESTRING(-1 1,0 0,1 0,5 0,5 5,10 5,15 0,31 0)", + "LINESTRING(30 0,4 0,3 1,2 0,1 0,0 0,-1 -1)", + "101FF0102"); + test_geometry<ls, ls>("LINESTRING(31 0,15 0,10 5,5 5,5 0,1 0,0 0,-1 1)", + "LINESTRING(-1 -1,0 0,1 0,2 0,3 1,4 0,30 0)", + "101FF0102"); + test_geometry<ls, ls>("LINESTRING(31 0,15 0,10 5,5 5,5 0,1 0,0 0,-1 1)", + "LINESTRING(30 0,4 0,3 1,2 0,1 0,0 0,-1 -1)", + "101FF0102"); + + // self-IP + test_geometry<ls, ls>("LINESTRING(1 0,9 0)", + "LINESTRING(0 0,10 0,10 10,5 0,0 10)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,5 0,9 0)", + "LINESTRING(0 0,10 0,10 10,5 0,0 10)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,9 0)", + "LINESTRING(0 0,10 0,10 10,5 10,5 -1)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,9 0)", + "LINESTRING(0 0,10 0,5 0,5 5)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,7 0)", "LINESTRING(0 0,10 0,10 10,4 -1)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,5 0,7 0)", "LINESTRING(0 0,10 0,10 10,4 -1)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,7 0,8 1)", "LINESTRING(0 0,10 0,10 10,4 -1)", + "1F10F0102"); + test_geometry<ls, ls>("LINESTRING(1 0,5 0,7 0,8 1)", "LINESTRING(0 0,10 0,10 10,4 -1)", + "1F10F0102"); + + // self-IP going out and in on the same point + test_geometry<ls, ls>("LINESTRING(2 0,5 0,5 5,6 5,5 0,8 0)", "LINESTRING(1 0,9 0)", + "1F10FF102"); + + // duplicated points + test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 2 2)", "LINESTRING(0 0, 2 2, 4 2)", "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 1, 1 1, 2 2)", "LINESTRING(0 0, 2 2, 4 2)", "1FF0FF102"); + + // linear ring + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", "LINESTRING(5 0,9 0,5 5,1 0,5 0)", "1F1FF01F2"); + test_geometry<ls, ls>("LINESTRING(0 0,5 0,10 0)", "LINESTRING(5 0,9 0,5 5,1 0,5 0)", "1F1FF01F2"); + test_geometry<ls, ls>("LINESTRING(0 0,5 0,10 0)", "LINESTRING(5 0,10 0,5 5,1 0,5 0)", "1F10F01F2"); + + test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(5 0,10 0,5 5,0 0,5 0)", "1FF0FF1F2"); + test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(5 0,10 0,5 5,5 0)", "FF10F01F2"); + + test_geometry<ls, ls>("LINESTRING(1 0,1 6)", "LINESTRING(0 0,5 0,5 5,0 5)", "0F10F0102"); + + // point-size Linestring + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(0 0,5 0)", "0FFFFF102"); + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(1 0,5 0)", "F0FFFF102"); + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(0 0,1 0)", "F0FFFF102"); + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(1 0,1 0)", "0FFFFFFF2"); + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(0 0,0 0)", "FF0FFF0F2"); + + //to_svg<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(5 0,10 0,5 5,5 0)", "test_relate_00.svg"); + + // INVALID LINESTRINGS + // 1-point LS (a Point) NOT disjoint + //test_geometry<ls, ls>("LINESTRING(1 0)", "LINESTRING(0 0,5 0)", "0FFFFF102"); + //test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(1 0)", "0F1FF0FF2"); + //test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(1 0,1 0,1 0)", "0F1FF0FF2"); + // Point/Point + //test_geometry<ls, ls>("LINESTRING(0 0)", "LINESTRING(0 0)", "0FFFFFFF2"); + + if ( BOOST_GEOMETRY_CONDITION( + boost::is_floating_point<typename bg::coordinate_type<ls>::type>::value ) ) + { + // https://svn.boost.org/trac/boost/ticket/10904 + // very small segments + test_geometry<ls, ls>("LINESTRING(5.6956521739130430148634331999347 -0.60869565217391330413931882503675,5.5 -0.50000000000000066613381477509392)", + "LINESTRING(5.5 -0.50000000000000066613381477509392,5.5 -0.5)", + "FF1F00102"); + test_geometry<ls, ls>("LINESTRING(-3.2333333333333333925452279800083 5.5999999999999978683717927196994,-3.2333333333333333925452279800083 5.5999999999999996447286321199499)", + "LINESTRING(-3.2333333333333325043668082798831 5.5999999999999996447286321199499,-3.2333333333333333925452279800083 5.5999999999999996447286321199499)", + "FF1F00102", "F0FFFF102"); // on some platforms the first Linestring may be detected as degenerated to Point + } + + if ( BOOST_GEOMETRY_CONDITION(( + boost::is_same<typename bg::coordinate_type<ls>::type, double>::value )) ) + { + // detected as collinear + test_geometry<ls, ls>("LINESTRING(1 -10, 3.069359e+307 3.069359e+307)", + "LINESTRING(1 6, 1 0)", + "*********"); // TODO: be more specific with the result + } + + // OTHER MASKS + { + namespace bgdr = bg::detail::relate; + ls ls1, ls2, ls3, ls4; + bg::read_wkt("LINESTRING(0 0,2 0)", ls1); + bg::read_wkt("LINESTRING(2 0,4 0)", ls2); + bg::read_wkt("LINESTRING(1 0,1 1)", ls3); + bg::read_wkt("LINESTRING(1 0,4 0)", ls4); + BOOST_CHECK(bg::relate(ls1, ls2, bg::de9im::mask("FT*******") + || bg::de9im::mask("F**T*****") + || bg::de9im::mask("F***T****"))); + BOOST_CHECK(bg::relate(ls1, ls3, bg::de9im::mask("FT*******") + || bg::de9im::mask("F**T*****") + || bg::de9im::mask("F***T****"))); + BOOST_CHECK(bg::relate(ls3, ls1, bg::de9im::mask("FT*******") + || bg::de9im::mask("F**T*****") + || bg::de9im::mask("F***T****"))); + BOOST_CHECK(bg::relate(ls2, ls4, bg::de9im::mask("T*F**F***"))); // within + + BOOST_CHECK(bg::relate(ls1, ls2, bg::de9im::static_mask<'F','T'>() + || bg::de9im::static_mask<'F','*','*','T'>() + || bg::de9im::static_mask<'F','*','*','*','T'>())); + BOOST_CHECK(bg::relate(ls1, ls2, bg::de9im::mask("FT") + || bg::de9im::mask("F**T") + || bg::de9im::mask("F***T**************"))); + + BOOST_CHECK_THROW(bg::relate(ls1, ls2, bg::de9im::mask("A")), bg::invalid_input_exception); + } + + // spike - boundary and interior on the same point + test_geometry<ls, ls>("LINESTRING(3 7, 8 8, 2 6)", "LINESTRING(5 7, 10 7, 0 7)", "0010F0102"); + + // 22.01.2015 + test_geometry<ls, ls>("LINESTRING(5 5,10 10)", "LINESTRING(6 6,3 3)", "1010F0102"); + test_geometry<ls, ls>("LINESTRING(5 5,2 8)", "LINESTRING(4 6,7 3)", "1010F0102"); +} + +template <typename P> +void test_linestring_multi_linestring() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::multi_linestring<ls> mls; + + // LS disjoint + test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,2 1))", "101FF0102"); + // linear ring disjoint + test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,2 1,2 2,1 1))", "101FF01F2"); + // 2xLS forming non-simple linear ring disjoint + test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,2 1,2 2),(1 1,2 2))", "101FF01F2"); + + test_geometry<ls, mls>("LINESTRING(0 0,10 0)", + "MULTILINESTRING((1 0,9 0),(9 0,2 0))", + "101FF0FF2"); + + // rings + test_geometry<ls, mls>("LINESTRING(0 0,5 0,5 5,0 5,0 0)", + "MULTILINESTRING((5 5,0 5,0 0),(0 0,5 0,5 5))", + "1FFFFFFF2"); + test_geometry<ls, mls>("LINESTRING(0 0,5 0,5 5,0 5,0 0)", + "MULTILINESTRING((5 5,5 0,0 0),(0 0,0 5,5 5))", + "1FFFFFFF2"); + // overlapping rings + test_geometry<ls, mls>("LINESTRING(0 0,5 0,5 5,0 5,0 0)", + "MULTILINESTRING((5 5,0 5,0 0),(0 0,5 0,5 5,0 5))", + "10FFFFFF2"); + test_geometry<ls, mls>("LINESTRING(0 0,5 0,5 5,0 5,0 0)", + "MULTILINESTRING((5 5,5 0,0 0),(0 0,0 5,5 5,5 0))", + "10FFFFFF2"); + + // INVALID LINESTRINGS + // 1-point LS (a Point) disjoint + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1))", "101FF00F2"); + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,1 1))", "101FF00F2"); + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,1 1,1 1))", "101FF00F2"); + // 1-point LS (a Point) NOT disjoint + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,9 0),(2 0))", "101FF0FF2"); + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,9 0),(2 0,2 0))", "101FF0FF2"); + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,9 0),(2 0,2 0,2 0))", "101FF0FF2"); + + // point-like + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 1 0),(2 0, 2 0))", // |------| * + "101F00FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 1 0),(1 0, 1 0))", // |------* + "101F00FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((5 0, 1 0),(1 0, 1 0))", // *-------| + "101F00FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 1 0),(5 0, 5 0))", // |------| * + "10100FFF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 1 0),(0 0, 0 0))", // *------| + "101000FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((4 0, 5 0),(5 0, 5 0))", // |------* + "101000FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((1 0, 2 0),(0 0, 0 0))", // * |------| + "1010F0FF2"); + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((2 0, 2 0),(2 0, 2 2))", // * + "001FF0102"); // | + + // for consistency + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(0 0, 2 0))", // |--------------| + "10F00FFF2"); // |------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(3 0, 5 0))", // |--------------| + "10F00FFF2"); // |------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(0 0, 6 0))", // |--------------| + "1FF00F102"); // |----------------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(-1 0, 5 0))", // |--------------| + "1FF00F102"); // |----------------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(-1 0, 6 0))", // |--------------| + "1FF00F102"); // |------------------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(-1 0, 2 0))", // |--------------| + "10F00F102"); // |-------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(2 0, 6 0))", // |--------------| + "10F00F102"); // |-------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(2 0, 2 2))", // |--------------| + "10FF0F102"); // | + // | + + if ( BOOST_GEOMETRY_CONDITION(boost::is_floating_point<typename bg::coordinate_type<ls>::type>::value) ) + { + // related to https://svn.boost.org/trac/boost/ticket/10904 + test_geometry<ls, mls>("LINESTRING(-2305843009213693956 4611686018427387906, -33 -92, 78 83)", + "MULTILINESTRING((20 100, 31 -97, -46 57, -20 -4),(-71 -4))", + "*********"); // TODO: be more specific with the result + } + + // 22.01.2015 + // inspired by L/A and A/A + test_geometry<ls, mls>("LINESTRING(1 1,2 2)", "MULTILINESTRING((0 0,1 1),(1 1,3 3))", "1FF0FF102"); + + // 25.01.2015 + test_geometry<ls, mls>("LINESTRING(1 1, 5 5, 4 4)", + "MULTILINESTRING((2 5, 7 5, 8 3, 6 3, 4 0),(0 0,10 10))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(4 1, 4 5, 4 4)", + "MULTILINESTRING((2 5, 7 5, 8 3, 6 3, 4 0),(4 0, 4 8, 0 4))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(1 1,5 5,4 4)", + "MULTILINESTRING((5 0,5 5,5 10),(0 0,10 10))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(1 1,5 5,1 0)", + "MULTILINESTRING((5 0,5 5,5 10),(0 0,5 5,1 0))", + "1FF00F102"); + test_geometry<ls, mls>("LINESTRING(5 5,4 4)", + "MULTILINESTRING((5 0,5 5,5 10),(0 0,10 10))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(6 6,5 5,4 4)", + "MULTILINESTRING((5 0,5 5,5 10),(0 0,10 10))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(5 5,4 4)", + "MULTILINESTRING((5 0,5 5,5 10))", + "FF10F0102"); +} + +template <typename P> +void test_multi_linestring_multi_linestring() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::multi_linestring<ls> mls; + + test_geometry<mls, mls>("MULTILINESTRING((0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0))", + "MULTILINESTRING((0 10,5 0,20 0,20 0,30 0))", + "1F1F00102"); + test_geometry<mls, mls>("MULTILINESTRING((0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0))", + //"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))", + "MULTILINESTRING((0 10,5 0,20 0,20 0,30 0),(1 10,1 10,1 0,1 0,1 -10),(0 0,0 0,0 10,0 10),(30 0,30 0,31 0,31 0))", + "1F100F102"); + test_geometry<mls, mls>("MULTILINESTRING((0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0))", + "MULTILINESTRING((0 10,5 0,20 0,20 0,30 0),(0 0,0 0,0 10,0 10))", + "1F1F0F1F2"); + + // point-like + test_geometry<mls, mls>("MULTILINESTRING((0 0, 0 0),(1 1, 1 1))", + "MULTILINESTRING((0 0, 0 0))", + "0F0FFFFF2"); + test_geometry<mls, mls>("MULTILINESTRING((0 0, 0 0),(1 1, 1 1))", + "MULTILINESTRING((0 0, 0 0),(1 1, 1 1))", + "0FFFFFFF2"); + test_geometry<mls, mls>("MULTILINESTRING((0 0, 0 0),(1 1, 1 1))", + "MULTILINESTRING((2 2, 2 2),(3 3, 3 3))", + "FF0FFF0F2"); + + test_geometry<mls, mls>("MULTILINESTRING((0 5,10 5,10 10,5 10),(5 10,5 0,5 2),(5 2,5 5,0 5))", + "MULTILINESTRING((5 5,0 5),(5 5,5 0),(10 10,10 5,5 5,5 10,10 10))", + "10FFFFFF2"); + + if ( BOOST_GEOMETRY_CONDITION(( + boost::is_same<typename bg::coordinate_type<P>::type, double>::value )) ) + { + // assertion failure in 1.57 + test_geometry<mls, mls>("MULTILINESTRING((-0.59322033898305082 -8.0508474576271194,-2.882352941176471 -7.7647058823529411,-2.8823529411764706 -7.7647058823529411,-3.7361111111111112 -6.5694444444444446,-3.4404145077720205 -5.766839378238342,-4.1864406779661012 -3.6779661016949152,-7.5252525252525251 -5.5858585858585865,-7.5862068965517242 -5.1896551724137936,-4.47887323943662 -2.859154929577465,-4.5789473684210531 -2.5789473684210527,-3 -1,-2.9310344827586206 -0.86206896551724144,-3.1764705882352944 -0.70588235294117663,-4.7401960784313726 -2.1274509803921577,-5.3255813953488369 -0.48837209302325502,-4.7872340425531918 0.31914893617021284,-5.8571428571428577 1.0000000000000007,-5.3255813953488369 -0.48837209302325502,-5.9473684210526319 -1.4210526315789465,-8 2,-7.7333333333333334 2.1939393939393939,-8.8294573643410867 2.891472868217055,-8.8556701030927822 3.061855670103093,-7.5999999999999996 3.6000000000000001,-7.7999999999999998 3.7999999999999998,-7.75 3.7916666666666665,-7.5471698113207548 3.6226415094339623,-7.3200000000000003 3.7200000000000002,-3.473684210526315 3.0789473684210527,-3.2549019607843133 3.2156862745098036,-2.9999999999999982 3.1428571428571423,-3.1733333333333325 3.2666666666666666,-2.9180327868852456 3.4262295081967209,-2.8723404255319145 3.1063829787234041,-2.1111111111111112 2.8888888888888888,-2.1428571428571428 2.8571428571428572,-1.8433734939759043 2.8072289156626509,-1.8396226415094346 2.8113207547169816,-1.6486486486486487 2.756756756756757,-1.76510067114094 2.8926174496644301,-0.53846153846153855 4.2307692307692308,1.8148148148148147 5.4074074074074074,1.588235294117647 2.2352941176470589,1.819672131147541 2.1967213114754101,2 4,2 2.1666666666666665,2.3538461538461544 2.1076923076923078,2 1.6875000000000004,2 -2,1.2173913043478262 -3.8260869565217392,1.7375886524822697 1.3758865248226959,1.5073170731707317 1.1024390243902444,1.1428571428571428 -4,-0.59322033898305082 -8.0508474576271194),(1.666666666666667 1.5999999999999988,1.5675675675675675 1.8378378378378377,1.4374999999999991 1.8750000000000002,1.0487804878048776 2.3414634146341466,0.46666666666666712 2.6060606060606055,0.086956521739131043 2.2608695652173911,1.4374999999999991 1.8750000000000002,1.666666666666667 1.5999999999999988))", + "MULTILINESTRING((-2.333333333333333 -8.6666666666666661,-4.3253012048192767 -8.168674698795181,-4.1194968553459113 -7.6100628930817606,-2.8823529411764706 -7.7647058823529411,-2.882352941176471 -7.7647058823529411,-2.263157894736842 -8.6315789473684212,-2.333333333333333 -8.6666666666666661))", + "*********"); + } +} + +template <typename P> +void test_all() +{ + test_linestring_linestring<P>(); + test_linestring_multi_linestring<P>(); + test_multi_linestring_multi_linestring<P>(); +} + +int test_main( int , char* [] ) +{ + test_all<bg::model::d2::point_xy<int> >(); + test_all<bg::model::d2::point_xy<double> >(); + +#if defined(HAVE_TTMATH) + test_all<bg::model::d2::point_xy<ttmath_big> >(); +#endif + + return 0; +} diff --git a/src/boost/libs/geometry/test/algorithms/relate/relate_linear_linear_sph.cpp b/src/boost/libs/geometry/test/algorithms/relate/relate_linear_linear_sph.cpp new file mode 100644 index 00000000..dce75f8b --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/relate_linear_linear_sph.cpp @@ -0,0 +1,451 @@ +// Boost.Geometry +// Unit Test + +// Copyright (c) 2016, 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_relate.hpp" + + +template <typename P> +void test_linestring_linestring() +{ + typedef bg::model::linestring<P> ls; + + test_geometry<ls, ls>("LINESTRING(0 0, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 3 2)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(0 0,3 2)", "LINESTRING(0 0, 2 2, 3 2)", "FF1F0F1F2"); + test_geometry<ls, ls>("LINESTRING(1 0,2 2,2 3)", "LINESTRING(0 0, 2 2, 3 2)", "0F1FF0102"); + + test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(0 0,1 1,2 0,2 -1)", "0F1F00102"); + + test_geometry<ls, ls>("LINESTRING(0 0, 1 1.0004570537241206, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 3 2)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(3 2, 2 2, 1 1.0004570537241206, 0 0)", "LINESTRING(0 0, 2 2, 3 2)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(0 0, 1 1.0004570537241206, 2 2, 3 2)", "LINESTRING(3 2, 2 2, 0 0)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(3 2, 2 2, 1 1.0004570537241206, 0 0)", "LINESTRING(3 2, 2 2, 0 0)", "1FFF0FFF2"); + + test_geometry<ls, ls>("LINESTRING(3 1, 2 2, 1 1.0004570537241206, 0 0)", "LINESTRING(0 0, 2 2, 3 2)", "1F1F00102"); + test_geometry<ls, ls>("LINESTRING(3 3, 2 2.0015234344160047, 1 1.0012195839797347, 0 0)", "LINESTRING(0 0, 2 2.0015234344160047, 3 2)", "1F1F00102"); + + test_geometry<ls, ls>("LINESTRING(0 0, 1 1.0004570537241206, 2 2, 2 3)", "LINESTRING(0 0, 2 2, 2 3)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(2 3, 2 2, 1 1.0004570537241206, 0 0)", "LINESTRING(0 0, 2 2, 2 3)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(0 0, 1 1.0004570537241206, 2 2, 2 3)", "LINESTRING(2 3, 2 2, 0 0)", "1FFF0FFF2"); + test_geometry<ls, ls>("LINESTRING(2 3, 2 2, 1 1.0004570537241206, 0 0)", "LINESTRING(2 3, 2 2, 0 0)", "1FFF0FFF2"); + + test_geometry<ls, ls>("LINESTRING(1 1.0004570537241206, 2 2, 3 2.0003044086155000)", "LINESTRING(0 0, 2 2, 4 2)", "1FF0FF102"); + + test_geometry<ls, ls>("LINESTRING(3 2.0003044086155000, 2 2, 1 1.0004570537241206)", "LINESTRING(0 0, 2 2, 4 2)", "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 1.0004570537241206, 2 2, 3 2.0003044086155000)", "LINESTRING(4 2, 2 2, 0 0)", "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(3 2.0003044086155000, 2 2, 1 1.0004570537241206)", "LINESTRING(4 2, 2 2, 0 0)", "1FF0FF102"); + +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 2 2)", "LINESTRING(0 0, 2 2, 4 2)", true); + +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 3)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 2, 3 3)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 1)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 1, 2 2, 3 2, 3 1)", "LINESTRING(0 0, 2 2, 4 2)", false); + +// test_geometry<ls, ls>("LINESTRING(0 1, 1 1, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(0 1, 0 0, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 0, 1 1, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", false); +// test_geometry<ls, ls>("LINESTRING(1 0, 0 0, 2 2, 3 2)", "LINESTRING(0 0, 2 2, 4 2)", false); + +// test_geometry<ls, ls>("LINESTRING(0 0)", "LINESTRING(0 0)", false); +// test_geometry<ls, ls>("LINESTRING(1 1)", "LINESTRING(0 0, 2 2)", true); +// test_geometry<ls, ls>("LINESTRING(0 0)", "LINESTRING(0 0, 2 2)", false); +// test_geometry<ls, ls>("LINESTRING(0 0, 1 1)", "LINESTRING(0 0)", false); + +// test_geometry<ls, ls>("LINESTRING(0 0,5 0,3 0,6 0)", "LINESTRING(0 0,6 0)", true); +// test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,1 1)", "LINESTRING(0 0,3 3,6 3)", true); + + // SPIKES! + test_geometry<ls, ls>("LINESTRING(0 0,2 2.0015234344160047,3 3,1 1.0012195839797347,5 3.0009124369434743)", "LINESTRING(0 0,3 3,6 3)", "1F100F102"); + test_geometry<ls, ls>("LINESTRING(5 3.0009124369434743,1 1.0012195839797347,3 3,2 2.0015234344160047,0 0)", "LINESTRING(0 0,3 3,6 3)", "1F100F102"); + test_geometry<ls, ls>("LINESTRING(0 0,2 2.0015234344160047,3 3,1 1.0012195839797347,5 3.0009124369434743)", "LINESTRING(6 3,3 3,0 0)", "1F100F102"); + test_geometry<ls, ls>("LINESTRING(5 3.0009124369434743,1 1.0012195839797347,3 3,2 2.0015234344160047,0 0)", "LINESTRING(6 3,3 3,0 0)", "1F100F102"); + + test_geometry<ls, ls>("LINESTRING(6 3,3 3,0 0)", "LINESTRING(0 0,2 2.0015234344160047,3 3,1 1.0012195839797347,5 3.0009124369434743)", "101F001F2"); + + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", "LINESTRING(1 0,9 0,2 0)", "101FF0FF2"); + test_geometry<ls, ls>("LINESTRING(0 0,2 2.0015234344160047,3 3,1 1.0012195839797347)", "LINESTRING(0 0,3 3,6 3)", "1FF00F102"); + // TODO: REWRITE MATRICES + // BEGIN + /*test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,1 1)", "LINESTRING(0 0,4 4,6 3)", "1FF00F102"); + + 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"); + + test_geometry<ls, ls>("LINESTRING(0 0,3 3,1 1)", "LINESTRING(3 0,3 3,3 1)", "0F1FF0102"); + test_geometry<ls, ls>("LINESTRING(0 0,3 3,1 1)", "LINESTRING(2 0,2 3,2 1)", "0F1FF0102"); + test_geometry<ls, ls>("LINESTRING(0 0,3 3,1 1)", "LINESTRING(2 0,2 2,2 1)", "0F1FF0102"); + + test_geometry<ls, ls>("LINESTRING(0 0,2 2,3 3,4 4)", "LINESTRING(0 0,1 1,4 4)", "1FFF0FFF2");*/ + // END + + test_geometry<ls, ls>("LINESTRING(0 0,2 2.0036594926050868,3 3.0031983963093536,4 4)", "LINESTRING(0 0,1 1.0022887548647632,4 4)", "1FFF0FFF2"); + + // loop i/i i/i u/u u/u + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", + "LINESTRING(1 1,1 0,6 0,6 1,4 1,4 0,9 0,9 1)", "1F1FF0102"); + + // self-intersecting and self-touching equal + test_geometry<ls, ls>("LINESTRING(0 5,5 5,10 5,10 10,5 10,5 5,5 0)", + "LINESTRING(0 5,5 5,5 10,10 10,10 5,5 5,5 0)", "1FFF0FFF2"); + // self-intersecting loop and self-touching equal + test_geometry<ls, ls>("LINESTRING(0 5,5 5,10 5,10 10,5 10,5 5,10 5,10 10,5 10,5 5,5 0)", + "LINESTRING(0 5,5 5,5 10,10 10,10 5,5 5,5 0)", "1FFF0FFF2"); + + test_geometry<ls, ls>("LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", "0F1FF0102"); + test_geometry<ls, ls>("LINESTRING(0 0,1 1)", "LINESTRING(1 1,2 0)", "FF1F00102"); + test_geometry<ls, ls>("LINESTRING(0 0,1 1)", "LINESTRING(2 0,1 1)", "FF1F00102"); + + test_geometry<ls, ls>("LINESTRING(0 0,1 0,2 1,3 5,4 0)", "LINESTRING(1 0,2 1,3 5)", "101FF0FF2"); + test_geometry<ls, ls>("LINESTRING(0 0,1 0,2 1,3 5,4 0)", "LINESTRING(3 5,2 1,1 0)", "101FF0FF2"); + test_geometry<ls, ls>("LINESTRING(1 0,2 1,3 5)", "LINESTRING(4 0,3 5,2 1,1 0,0 0)", "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(3 5,2 1,1 0)", "LINESTRING(4 0,3 5,2 1,1 0,0 0)", "1FF0FF102"); + + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", "LINESTRING(-1 -1,1 0,10 0,20 -1)", "1F10F0102"); + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", "LINESTRING(20 -1,10 0,1 0,-1 -1)", "1F10F0102"); + + test_geometry<ls, ls>("LINESTRING(-1 1,0 0,1 0,5 0,5 5,10 5,15 0,31 0)", + "LINESTRING(-1 -1,0 0,1 0,2 0,3 1,4 0,30 0)", + "101FF0102"); + test_geometry<ls, ls>("LINESTRING(-1 1,0 0,1 0,5 0,5 5,10 5,15 0,31 0)", + "LINESTRING(30 0,4 0,3 1,2 0,1 0,0 0,-1 -1)", + "101FF0102"); + test_geometry<ls, ls>("LINESTRING(31 0,15 0,10 5,5 5,5 0,1 0,0 0,-1 1)", + "LINESTRING(-1 -1,0 0,1 0,2 0,3 1,4 0,30 0)", + "101FF0102"); + test_geometry<ls, ls>("LINESTRING(31 0,15 0,10 5,5 5,5 0,1 0,0 0,-1 1)", + "LINESTRING(30 0,4 0,3 1,2 0,1 0,0 0,-1 -1)", + "101FF0102"); + + // self-IP + test_geometry<ls, ls>("LINESTRING(1 0,9 0)", + "LINESTRING(0 0,10 0,10 10,5 0,0 10)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,5 0,9 0)", + "LINESTRING(0 0,10 0,10 10,5 0,0 10)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,9 0)", + "LINESTRING(0 0,10 0,10 10,5 10,5 -1)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,9 0)", + "LINESTRING(0 0,10 0,5 0,5 5)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,7 0)", "LINESTRING(0 0,10 0,10 10,4 -1)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,5 0,7 0)", "LINESTRING(0 0,10 0,10 10,4 -1)", + "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 0,7 0,8 1)", "LINESTRING(0 0,10 0,10 10,4 -1)", + "1F10F0102"); + test_geometry<ls, ls>("LINESTRING(1 0,5 0,7 0,8 1)", "LINESTRING(0 0,10 0,10 10,4 -1)", + "1F10F0102"); + + // self-IP going out and in on the same point + test_geometry<ls, ls>("LINESTRING(2 0,5 0,5 5,6 5,5 0,8 0)", "LINESTRING(1 0,9 0)", + "1F10FF102"); + + // duplicated points + test_geometry<ls, ls>("LINESTRING(1 1.0004570537241206, 2 2, 2 2)", "LINESTRING(0 0, 2 2, 4 2)", "1FF0FF102"); + test_geometry<ls, ls>("LINESTRING(1 1.0004570537241206, 1 1.0004570537241206, 2 2)", "LINESTRING(0 0, 2 2, 4 2)", "1FF0FF102"); + + // linear ring + test_geometry<ls, ls>("LINESTRING(0 0,10 0)", "LINESTRING(5 0,9 0,5 5,1 0,5 0)", "1F1FF01F2"); + test_geometry<ls, ls>("LINESTRING(0 0,5 0,10 0)", "LINESTRING(5 0,9 0,5 5,1 0,5 0)", "1F1FF01F2"); + test_geometry<ls, ls>("LINESTRING(0 0,5 0,10 0)", "LINESTRING(5 0,10 0,5 5,1 0,5 0)", "1F10F01F2"); + + test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(5 0,10 0,5 5,0 0,5 0)", "1FF0FF1F2"); + test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(5 0,10 0,5 5,5 0)", "FF10F01F2"); + + test_geometry<ls, ls>("LINESTRING(1 0,1 6)", "LINESTRING(0 0,5 0,5 5,0 5)", "0F10F0102"); + + // point-size Linestring + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(0 0,5 0)", "0FFFFF102"); + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(1 0,5 0)", "F0FFFF102"); + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(0 0,1 0)", "F0FFFF102"); + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(1 0,1 0)", "0FFFFFFF2"); + test_geometry<ls, ls>("LINESTRING(1 0,1 0)", "LINESTRING(0 0,0 0)", "FF0FFF0F2"); + + //to_svg<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(5 0,10 0,5 5,5 0)", "test_relate_00.svg"); + + // INVALID LINESTRINGS + // 1-point LS (a Point) NOT disjoint + //test_geometry<ls, ls>("LINESTRING(1 0)", "LINESTRING(0 0,5 0)", "0FFFFF102"); + //test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(1 0)", "0F1FF0FF2"); + //test_geometry<ls, ls>("LINESTRING(0 0,5 0)", "LINESTRING(1 0,1 0,1 0)", "0F1FF0FF2"); + // Point/Point + //test_geometry<ls, ls>("LINESTRING(0 0)", "LINESTRING(0 0)", "0FFFFFFF2"); + + if ( BOOST_GEOMETRY_CONDITION( + boost::is_floating_point<typename bg::coordinate_type<ls>::type>::value ) ) + { + // https://svn.boost.org/trac/boost/ticket/10904 + // very small segments + test_geometry<ls, ls>("LINESTRING(5.6956521739130430148634331999347 -0.60869565217391330413931882503675,5.5 -0.50000000000000066613381477509392)", + "LINESTRING(5.5 -0.50000000000000066613381477509392,5.5 -0.5)", + "*********"); // TODO: be more specific with the result + test_geometry<ls, ls>("LINESTRING(-3.2333333333333333925452279800083 5.5999999999999978683717927196994,-3.2333333333333333925452279800083 5.5999999999999996447286321199499)", + "LINESTRING(-3.2333333333333325043668082798831 5.5999999999999996447286321199499,-3.2333333333333333925452279800083 5.5999999999999996447286321199499)", + "*********"); // TODO: be more specific with the result + } + + if ( BOOST_GEOMETRY_CONDITION(( + boost::is_same<typename bg::coordinate_type<ls>::type, double>::value )) ) + { + // detected as collinear + test_geometry<ls, ls>("LINESTRING(1 -10, 3.069359e+307 3.069359e+307)", + "LINESTRING(1 6, 1 0)", + "*********"); // TODO: be more specific with the result + } + + // OTHER MASKS + { + namespace bgdr = bg::detail::relate; + ls ls1, ls2, ls3, ls4; + bg::read_wkt("LINESTRING(0 0,2 0)", ls1); + bg::read_wkt("LINESTRING(2 0,4 0)", ls2); + bg::read_wkt("LINESTRING(1 0,1 1)", ls3); + bg::read_wkt("LINESTRING(1 0,4 0)", ls4); + BOOST_CHECK(bg::relate(ls1, ls2, bg::de9im::mask("FT*******") + || bg::de9im::mask("F**T*****") + || bg::de9im::mask("F***T****"))); + BOOST_CHECK(bg::relate(ls1, ls3, bg::de9im::mask("FT*******") + || bg::de9im::mask("F**T*****") + || bg::de9im::mask("F***T****"))); + BOOST_CHECK(bg::relate(ls3, ls1, bg::de9im::mask("FT*******") + || bg::de9im::mask("F**T*****") + || bg::de9im::mask("F***T****"))); + BOOST_CHECK(bg::relate(ls2, ls4, bg::de9im::mask("T*F**F***"))); // within + + BOOST_CHECK(bg::relate(ls1, ls2, bg::de9im::static_mask<'F','T'>() + || bg::de9im::static_mask<'F','*','*','T'>() + || bg::de9im::static_mask<'F','*','*','*','T'>())); + BOOST_CHECK(bg::relate(ls1, ls2, bg::de9im::mask("FT") + || bg::de9im::mask("F**T") + || bg::de9im::mask("F***T**************"))); + + BOOST_CHECK_THROW(bg::relate(ls1, ls2, bg::de9im::mask("A")), bg::invalid_input_exception); + } + + // spike - boundary and interior on the same point + test_geometry<ls, ls>("LINESTRING(3 7.0222344894505291, 8 8, 2 6.0297078652914440)", "LINESTRING(5 7.0264720782244758, 10 7, 0 7)", "0010F0102"); + + // 22.01.2015 + test_geometry<ls, ls>("LINESTRING(5 5.0276084891434261,10 10)", "LINESTRING(6 6.0348911579043349,3 3)", "1010F0102"); + test_geometry<ls, ls>("LINESTRING(5 5.0146631750126396,2 8)", "LINESTRING(4 6.0155438000959975,7 3)", "1010F0102"); +} + +template <typename P> +void test_linestring_multi_linestring() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::multi_linestring<ls> mls; + + // LS disjoint + test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,2 1))", "101FF0102"); + // linear ring disjoint + test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,2 1,2 2,1 1))", "101FF01F2"); + // 2xLS forming non-simple linear ring disjoint + test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,2 1,2 2),(1 1,2 2))", "101FF01F2"); + + test_geometry<ls, mls>("LINESTRING(0 0,10 0)", + "MULTILINESTRING((1 0,9 0),(9 0,2 0))", + "101FF0FF2"); + + // rings + test_geometry<ls, mls>("LINESTRING(0 0,5 0,5 5,0 5,0 0)", + "MULTILINESTRING((5 5,0 5,0 0),(0 0,5 0,5 5))", + "1FFFFFFF2"); + test_geometry<ls, mls>("LINESTRING(0 0,5 0,5 5,0 5,0 0)", + "MULTILINESTRING((5 5,5 0,0 0),(0 0,0 5,5 5))", + "1FFFFFFF2"); + // overlapping rings + test_geometry<ls, mls>("LINESTRING(0 0,5 0,5 5,0 5,0 0)", + "MULTILINESTRING((5 5,0 5,0 0),(0 0,5 0,5 5,0 5))", + "10FFFFFF2"); + test_geometry<ls, mls>("LINESTRING(0 0,5 0,5 5,0 5,0 0)", + "MULTILINESTRING((5 5,5 0,0 0),(0 0,0 5,5 5,5 0))", + "10FFFFFF2"); + + // INVALID LINESTRINGS + // 1-point LS (a Point) disjoint + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1))", "101FF00F2"); + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,1 1))", "101FF00F2"); + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,2 0),(1 1,1 1,1 1))", "101FF00F2"); + // 1-point LS (a Point) NOT disjoint + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,9 0),(2 0))", "101FF0FF2"); + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,9 0),(2 0,2 0))", "101FF0FF2"); + //test_geometry<ls, mls>("LINESTRING(0 0,10 0)", "MULTILINESTRING((1 0,9 0),(2 0,2 0,2 0))", "101FF0FF2"); + + // point-like + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 1 0),(2 0, 2 0))", // |------| * + "101F00FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 1 0),(1 0, 1 0))", // |------* + "101F00FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((5 0, 1 0),(1 0, 1 0))", // *-------| + "101F00FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 1 0),(5 0, 5 0))", // |------| * + "10100FFF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 1 0),(0 0, 0 0))", // *------| + "101000FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((4 0, 5 0),(5 0, 5 0))", // |------* + "101000FF2"); + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((1 0, 2 0),(0 0, 0 0))", // * |------| + "1010F0FF2"); + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((2 0, 2 0),(2 0, 2 2))", // * + "001FF0102"); // | + + // for consistency + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(0 0, 2 0))", // |--------------| + "10F00FFF2"); // |------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(3 0, 5 0))", // |--------------| + "10F00FFF2"); // |------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(0 0, 6 0))", // |--------------| + "1FF00F102"); // |----------------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(-1 0, 5 0))", // |--------------| + "1FF00F102"); // |----------------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(-1 0, 6 0))", // |--------------| + "1FF00F102"); // |------------------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(-1 0, 2 0))", // |--------------| + "10F00F102"); // |-------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(2 0, 6 0))", // |--------------| + "10F00F102"); // |-------| + + test_geometry<ls, mls>("LINESTRING(0 0, 5 0)", // |--------------| + "MULTILINESTRING((0 0, 5 0),(2 0, 2 2))", // |--------------| + "10FF0F102"); // | + // | + + if ( BOOST_GEOMETRY_CONDITION(boost::is_floating_point<typename bg::coordinate_type<ls>::type>::value) ) + { + // related to https://svn.boost.org/trac/boost/ticket/10904 + test_geometry<ls, mls>("LINESTRING(-2305843009213693956 4611686018427387906, -33 -92, 78 83)", + "MULTILINESTRING((20 100, 31 -97, -46 57, -20 -4),(-71 -4))", + "*********"); // TODO: be more specific with the result + } + + // 22.01.2015 + // inspired by L/A and A/A + test_geometry<ls, mls>("LINESTRING(1 1.0012195839797347,2 2.0015234344160047)", + "MULTILINESTRING((0 0,1 1.0012195839797347),(1 1.0012195839797347,3 3))", + "1FF0FF102"); + // for floats this is considered as collinear due to a special check in spherical intersection strategy + test_geometry<ls, mls>("LINESTRING(1 1,2 2)", + "MULTILINESTRING((0 0,1 1),(1 1,3 3))", + "FF10F0102", "1FF0FF102"); + + // 25.01.2015 + test_geometry<ls, mls>("LINESTRING(1 1.0152687848942923, 5 5.0575148968282102, 4 4.0516408785782314)", + "MULTILINESTRING((2 5.1322576184978592, 7 5, 8 3, 6 3, 4 0),(0 0,10 10))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(4 1, 4 5, 4 4)", + "MULTILINESTRING((2 5.1322576184978592, 7 5, 8 3, 6 3, 4 0),(4 0, 4 8, 0 4))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(1 1.0152687848942923,5 5.0575148968282102,4 4.0516408785782314)", + "MULTILINESTRING((5 0,5 5.0575148968282102,5 10),(0 0,10 10))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(1 1.0036662021874625,5 5,1 0)", + "MULTILINESTRING((5 0,5 5,5 10),(0 0,5 5,1 0))", + "1FF00F102"); + test_geometry<ls, mls>("LINESTRING(5 5.0575148968282102,4 4.0516408785782314)", + "MULTILINESTRING((5 0,5 5.0575148968282102,5 10),(0 0,10 10))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(6 6.0587459045645184,5 5.0575148968282102,4 4.0516408785782314)", + "MULTILINESTRING((5 0,5 5.0575148968282102,5 10),(0 0,10 10))", + "1FF0FF102"); + test_geometry<ls, mls>("LINESTRING(5 5,4 4)", + "MULTILINESTRING((5 0,5 5,5 10))", + "FF10F0102"); +} + +template <typename P> +void test_multi_linestring_multi_linestring() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::multi_linestring<ls> mls; + + test_geometry<mls, mls>("MULTILINESTRING((0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0))", + "MULTILINESTRING((0 10,5 0,20 0,20 0,30 0))", + "1F1F00102"); + test_geometry<mls, mls>("MULTILINESTRING((0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0))", + //"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))", + "MULTILINESTRING((0 10,5 0,20 0,20 0,30 0),(1 10,1 10,1 0,1 0,1 -10),(0 0,0 0,0 10,0 10),(30 0,30 0,31 0,31 0))", + "1F100F102"); + test_geometry<mls, mls>("MULTILINESTRING((0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0))", + "MULTILINESTRING((0 10,5 0,20 0,20 0,30 0),(0 0,0 0,0 10,0 10))", + "1F1F0F1F2"); + + // point-like + test_geometry<mls, mls>("MULTILINESTRING((0 0, 0 0),(1 1, 1 1))", + "MULTILINESTRING((0 0, 0 0))", + "0F0FFFFF2"); + test_geometry<mls, mls>("MULTILINESTRING((0 0, 0 0),(1 1, 1 1))", + "MULTILINESTRING((0 0, 0 0),(1 1, 1 1))", + "0FFFFFFF2"); + test_geometry<mls, mls>("MULTILINESTRING((0 0, 0 0),(1 1, 1 1))", + "MULTILINESTRING((2 2, 2 2),(3 3, 3 3))", + "FF0FFF0F2"); + + test_geometry<mls, mls>("MULTILINESTRING((0 5,10 5,10 10,5 10),(5 10,5 0,5 2),(5 2,5 5.0190018174896416,0 5))", + "MULTILINESTRING((5 5.0190018174896416,0 5),(5 5.0190018174896416,5 0),(10 10,10 5,5 5.0190018174896416,5 10,10 10))", + "10FFFFFF2"); + + if ( BOOST_GEOMETRY_CONDITION(( + boost::is_same<typename bg::coordinate_type<P>::type, double>::value )) ) + { + // assertion failure in 1.57 + test_geometry<mls, mls>("MULTILINESTRING((-0.59322033898305082 -8.0508474576271194,-2.882352941176471 -7.7647058823529411,-2.8823529411764706 -7.7647058823529411,-3.7361111111111112 -6.5694444444444446,-3.4404145077720205 -5.766839378238342,-4.1864406779661012 -3.6779661016949152,-7.5252525252525251 -5.5858585858585865,-7.5862068965517242 -5.1896551724137936,-4.47887323943662 -2.859154929577465,-4.5789473684210531 -2.5789473684210527,-3 -1,-2.9310344827586206 -0.86206896551724144,-3.1764705882352944 -0.70588235294117663,-4.7401960784313726 -2.1274509803921577,-5.3255813953488369 -0.48837209302325502,-4.7872340425531918 0.31914893617021284,-5.8571428571428577 1.0000000000000007,-5.3255813953488369 -0.48837209302325502,-5.9473684210526319 -1.4210526315789465,-8 2,-7.7333333333333334 2.1939393939393939,-8.8294573643410867 2.891472868217055,-8.8556701030927822 3.061855670103093,-7.5999999999999996 3.6000000000000001,-7.7999999999999998 3.7999999999999998,-7.75 3.7916666666666665,-7.5471698113207548 3.6226415094339623,-7.3200000000000003 3.7200000000000002,-3.473684210526315 3.0789473684210527,-3.2549019607843133 3.2156862745098036,-2.9999999999999982 3.1428571428571423,-3.1733333333333325 3.2666666666666666,-2.9180327868852456 3.4262295081967209,-2.8723404255319145 3.1063829787234041,-2.1111111111111112 2.8888888888888888,-2.1428571428571428 2.8571428571428572,-1.8433734939759043 2.8072289156626509,-1.8396226415094346 2.8113207547169816,-1.6486486486486487 2.756756756756757,-1.76510067114094 2.8926174496644301,-0.53846153846153855 4.2307692307692308,1.8148148148148147 5.4074074074074074,1.588235294117647 2.2352941176470589,1.819672131147541 2.1967213114754101,2 4,2 2.1666666666666665,2.3538461538461544 2.1076923076923078,2 1.6875000000000004,2 -2,1.2173913043478262 -3.8260869565217392,1.7375886524822697 1.3758865248226959,1.5073170731707317 1.1024390243902444,1.1428571428571428 -4,-0.59322033898305082 -8.0508474576271194),(1.666666666666667 1.5999999999999988,1.5675675675675675 1.8378378378378377,1.4374999999999991 1.8750000000000002,1.0487804878048776 2.3414634146341466,0.46666666666666712 2.6060606060606055,0.086956521739131043 2.2608695652173911,1.4374999999999991 1.8750000000000002,1.666666666666667 1.5999999999999988))", + "MULTILINESTRING((-2.333333333333333 -8.6666666666666661,-4.3253012048192767 -8.168674698795181,-4.1194968553459113 -7.6100628930817606,-2.8823529411764706 -7.7647058823529411,-2.882352941176471 -7.7647058823529411,-2.263157894736842 -8.6315789473684212,-2.333333333333333 -8.6666666666666661))", + "*********"); + } +} + +template <typename P> +void test_all() +{ + test_linestring_linestring<P>(); + test_linestring_multi_linestring<P>(); + test_multi_linestring_multi_linestring<P>(); +} + +int test_main( int , char* [] ) +{ + typedef bg::cs::spherical_equatorial<bg::degree> cs_t; + + test_all<bg::model::point<float, 2, cs_t> >(); + test_all<bg::model::point<double, 2, cs_t> >(); + +#if defined(HAVE_TTMATH) + test_all<bg::model::point<ttmath_big, 2, cs_t> >(); +#endif + + return 0; +} diff --git a/src/boost/libs/geometry/test/algorithms/relate/relate_pointlike_geometry.cpp b/src/boost/libs/geometry/test/algorithms/relate/relate_pointlike_geometry.cpp new file mode 100644 index 00000000..8894b685 --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/relate_pointlike_geometry.cpp @@ -0,0 +1,254 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2018 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2013, 2014, 2015, 2017. +// Modifications copyright (c) 2013-2017 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_relate.hpp" +#include "nan_cases.hpp" + +//TEST +//#include <to_svg.hpp> + +template <typename P> +void test_point_point() +{ + test_geometry<P, P>("POINT(0 0)", "POINT(0 0)", "0FFFFFFF2"); + test_geometry<P, P>("POINT(1 0)", "POINT(0 0)", "FF0FFF0F2"); +} + +template <typename P> +void test_point_multipoint() +{ + typedef bg::model::multi_point<P> mpt; + + test_geometry<P, mpt>("POINT(0 0)", "MULTIPOINT(0 0)", "0FFFFFFF2"); + test_geometry<P, mpt>("POINT(1 0)", "MULTIPOINT(0 0)", "FF0FFF0F2"); + test_geometry<P, mpt>("POINT(0 0)", "MULTIPOINT(0 0, 1 0)", "0FFFFF0F2"); +} + +template <typename P> +void test_multipoint_multipoint() +{ + typedef bg::model::multi_point<P> mpt; + + test_geometry<mpt, mpt>("MULTIPOINT(0 0)", "MULTIPOINT(0 0)", "0FFFFFFF2"); + test_geometry<mpt, mpt>("MULTIPOINT(1 0)", "MULTIPOINT(0 0)", "FF0FFF0F2"); + test_geometry<mpt, mpt>("MULTIPOINT(0 0)", "MULTIPOINT(0 0, 1 0)", "0FFFFF0F2"); + test_geometry<mpt, mpt>("MULTIPOINT(0 0, 1 0)", "MULTIPOINT(0 0)", "0F0FFFFF2"); + test_geometry<mpt, mpt>("MULTIPOINT(0 0, 1 1)", "MULTIPOINT(0 0, 1 0)", "0F0FFF0F2"); + + //typedef bg::model::d2::point_xy<float> ptf; + //typedef bg::model::multi_point<ptf> mptf; + //test_geometry<mptf, mpt>("MULTIPOINT(0 0)", "MULTIPOINT(0 0)", "0FFFFFFF2"); + + // assertion failure in relate->boundary_checker->std::equal_range with msvc + if (BOOST_GEOMETRY_CONDITION(is_nan_case_supported<mpt>::value)) + { + mpt g; + std::string wkt; + nan_case(g, wkt); + + check_geometry(g, g, wkt, wkt, "*********"); + } +} + +template <typename P> +void test_point_linestring() +{ + typedef bg::model::linestring<P> ls; + + // degenerated + //test_geometry<P, ls>("POINT(0 0)", "LINESTRING(0 0)", "0FFFFFFF2"); + + test_geometry<P, ls>("POINT(0 0)", "LINESTRING(0 0, 2 2, 3 2)", "F0FFFF102"); + test_geometry<P, ls>("POINT(1 1)", "LINESTRING(0 0, 2 2, 3 2)", "0FFFFF102"); + test_geometry<P, ls>("POINT(3 2)", "LINESTRING(0 0, 2 2, 3 2)", "F0FFFF102"); + test_geometry<P, ls>("POINT(1 0)", "LINESTRING(0 0, 2 2, 3 2)", "FF0FFF102"); + + test_geometry<P, ls>("POINT(0 0)", "LINESTRING(0 0, 2 2, 3 2, 0 0)", "0FFFFF1F2"); + test_geometry<P, ls>("POINT(1 1)", "LINESTRING(0 0, 2 2, 3 2, 0 0)", "0FFFFF1F2"); + test_geometry<P, ls>("POINT(3 2)", "LINESTRING(0 0, 2 2, 3 2, 0 0)", "0FFFFF1F2"); + test_geometry<P, ls>("POINT(1 0)", "LINESTRING(0 0, 2 2, 3 2, 0 0)", "FF0FFF1F2"); +} + +template <typename P> +void test_point_multilinestring() +{ + typedef bg::model::linestring<P> ls; + typedef bg::model::multi_linestring<ls> mls; + + test_geometry<P, mls>("POINT(0 0)", "MULTILINESTRING((0 0, 2 0, 2 2),(0 0, 0 2))", "0FFFFF102"); + test_geometry<P, mls>("POINT(0 0)", "MULTILINESTRING((0 0, 2 0, 2 2),(0 0, 0 2, 2 2))", "0FFFFF1F2"); + test_geometry<P, mls>("POINT(0 0)", "MULTILINESTRING((0 0, 2 0, 2 2),(0 0, 0 2, 2 2),(0 0, 1 1))", "F0FFFF102"); + + test_geometry<P, mls>("POINT(0 0)", "MULTILINESTRING((0 0,5 0),(0 0,0 5,5 0),(0 0,-5 0),(0 0,0 -5,-5 0))", "0FFFFF1F2"); + test_geometry<P, mls>("POINT(5 0)", "MULTILINESTRING((0 0,5 0),(0 0,0 5,5 0),(0 0,-5 0),(0 0,0 -5,-5 0))", "0FFFFF1F2"); + test_geometry<P, mls>("POINT(1 0)", "MULTILINESTRING((0 0,5 0),(0 0,0 5,5 0),(0 0,-5 0),(0 0,0 -5,-5 0))", "0FFFFF1F2"); + + // assertion failure in relate->boundary_checker->std::equal_range with msvc + if (BOOST_GEOMETRY_CONDITION(is_nan_case_supported<mls>::value)) + { + // on the boundary + std::string wkt0 = "POINT(3.1e+307 1)"; + P g0; + bg::read_wkt(wkt0, g0); + + // disjoint + std::string wkt1 = "POINT(1.1e+308 1.2e+308)"; + P g1; + bg::read_wkt(wkt1, g1); + + mls g2; + std::string wkt2; + nan_case(g2, wkt2); + + check_geometry(g0, g2, wkt0, wkt2, "*********"); + check_geometry(g1, g2, wkt1, wkt2, "*********"); + } +} + +template <typename P> +void test_multipoint_linestring() +{ + typedef bg::model::multi_point<P> mpt; + typedef bg::model::linestring<P> ls; + + // degenerated + //test_geometry<mpt, ls>("MULTIPOINT(0 0)", "LINESTRING(0 0)", "0FFFFFFF2"); + + test_geometry<mpt, ls>("MULTIPOINT(0 0)", "LINESTRING(0 0, 2 2, 3 2)", "F0FFFF102"); + test_geometry<mpt, ls>("MULTIPOINT(0 0, 1 1)", "LINESTRING(0 0, 2 2, 3 2)", "00FFFF102"); + test_geometry<mpt, ls>("MULTIPOINT(0 0, 1 1, 3 3)", "LINESTRING(0 0, 2 2, 3 2)", "000FFF102"); + test_geometry<mpt, ls>("MULTIPOINT(0 0, 3 3)", "LINESTRING(0 0, 2 2, 3 2)", "F00FFF102"); + test_geometry<mpt, ls>("MULTIPOINT(1 1, 3 3)", "LINESTRING(0 0, 2 2, 3 2)", "0F0FFF102"); + + test_geometry<mpt, ls>("MULTIPOINT(0 0, 1 1)", "LINESTRING(0 0, 2 2, 3 2, 0 0)", "0FFFFF1F2"); + test_geometry<mpt, ls>("MULTIPOINT(0 0, 3 3)", "LINESTRING(0 0, 2 2, 3 2, 0 0)", "0F0FFF1F2"); + + test_geometry<mpt, ls>("MULTIPOINT(0 0)", "LINESTRING(0 0, 2 2)", "F0FFFF102"); + test_geometry<mpt, ls>("MULTIPOINT(2 2)", "LINESTRING(0 0, 2 2)", "F0FFFF102"); + test_geometry<mpt, ls>("MULTIPOINT(0 0, 2 2)", "LINESTRING(0 0, 2 2)", "F0FFFF1F2"); + test_geometry<mpt, ls>("MULTIPOINT(0 0, 1 1, 0 1, 2 2)", "LINESTRING(0 0, 2 2)", "000FFF1F2"); +} + +template <typename P> +void test_multipoint_multilinestring() +{ + typedef bg::model::multi_point<P> mpt; + typedef bg::model::linestring<P> ls; + typedef bg::model::multi_linestring<ls> mls; + + test_geometry<mpt, mls>("MULTIPOINT(0 0)", "MULTILINESTRING((0 0, 2 2),(2 2, 3 2))", "F0FFFF102"); + test_geometry<mpt, mls>("MULTIPOINT(0 0, 1 1)", "MULTILINESTRING((0 0, 2 2),(2 2, 3 2))", "00FFFF102"); + test_geometry<mpt, mls>("MULTIPOINT(0 0, 1 1, 3 3)", "MULTILINESTRING((0 0, 2 2),(2 2, 3 2))", "000FFF102"); + test_geometry<mpt, mls>("MULTIPOINT(0 0, 3 3)", "MULTILINESTRING((0 0, 2 2),(2 2, 3 2))", "F00FFF102"); + test_geometry<mpt, mls>("MULTIPOINT(1 1, 3 3)", "MULTILINESTRING((0 0, 2 2),(2 2, 3 2))", "0F0FFF102"); + + test_geometry<mpt, mls>("MULTIPOINT(0 0, 1 1)", "MULTILINESTRING((0 0, 2 2),(2 2, 3 2, 0 0))", "0FFFFF1F2"); + test_geometry<mpt, mls>("MULTIPOINT(0 0, 3 3)", "MULTILINESTRING((0 0, 2 2),(2 2, 3 2, 0 0))", "0F0FFF1F2"); + + test_geometry<mpt, mls>("MULTIPOINT(0 0,1 1)", "MULTILINESTRING((0 0,0 1,1 1),(1 1,1 0,0 0))", "0FFFFF1F2"); + + test_geometry<mpt, mls>("MULTIPOINT(0 0)", "MULTILINESTRING((0 0,1 1),(1 1,2 2))", "F0FFFF102"); + test_geometry<mpt, mls>("MULTIPOINT(0 0, 1 1)", "MULTILINESTRING((0 0,1 1),(1 1,2 2))", "00FFFF102"); + test_geometry<mpt, mls>("MULTIPOINT(0 0, 1 1, 2 2)", "MULTILINESTRING((0 0,1 1),(1 1,2 2))", "00FFFF1F2"); + test_geometry<mpt, mls>("MULTIPOINT(0 0, 2 2)", "MULTILINESTRING((0 0,1 1),(1 1,2 2))", "F0FFFF1F2"); +} + +template <typename P> +void test_point_ring_polygon() +{ + typedef bg::model::ring<P> ring; + typedef bg::model::polygon<P> poly; + + test_geometry<P, ring>("POINT(0 0)", "POLYGON((0 0, 0 2, 2 2, 2 0, 0 0))", "F0FFFF212"); + + test_geometry<P, poly>("POINT(1 1)", "POLYGON((0 0, 0 2, 2 2, 2 0, 0 0))", "0FFFFF212"); + test_geometry<P, poly>("POINT(1 3)", "POLYGON((0 0, 0 2, 2 2, 2 0, 0 0))", "FF0FFF212"); +} + +template <typename P> +void test_point_multipolygon() +{ + typedef bg::model::polygon<P> poly; + typedef bg::model::multi_polygon<poly> mpoly; + + test_geometry<P, mpoly>("POINT(0 0)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "F0FFFF212"); + test_geometry<P, mpoly>("POINT(1 1)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "0FFFFF212"); + test_geometry<P, mpoly>("POINT(5 5)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "F0FFFF212"); + test_geometry<P, mpoly>("POINT(6 6)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "0FFFFF212"); + test_geometry<P, mpoly>("POINT(1 6)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "FF0FFF212"); +} + +template <typename P> +void test_multipoint_ring_polygon() +{ + typedef bg::model::multi_point<P> mpt; + typedef bg::model::ring<P> ring; + typedef bg::model::polygon<P> poly; + + test_geometry<mpt, ring>("MULTIPOINT(0 0)", "POLYGON((0 0, 0 3, 3 3, 3 0, 0 0))", "F0FFFF212"); + test_geometry<mpt, ring>("MULTIPOINT(0 0, 1 1)", "POLYGON((0 0, 0 3, 3 3, 3 0, 0 0))", "00FFFF212"); + test_geometry<mpt, ring>("MULTIPOINT(0 0, 1 1, 4 4)", "POLYGON((0 0, 0 3, 3 3, 3 0, 0 0))", "000FFF212"); + test_geometry<mpt, ring>("MULTIPOINT(1 1, 4 4)", "POLYGON((0 0, 0 3, 3 3, 3 0, 0 0))", "0F0FFF212"); + + test_geometry<mpt, poly>("MULTIPOINT(2 2)", "POLYGON((0 0, 0 4, 4 4, 4 0, 0 0),(1 1, 3 1, 3 3, 1 3, 1 1))", "FF0FFF212"); + test_geometry<mpt, poly>("MULTIPOINT(0 0, 1 1)", "POLYGON((0 0, 0 4, 4 4, 4 0, 0 0),(1 1, 3 1, 3 3, 1 3, 1 1))", "F0FFFF212"); + test_geometry<mpt, poly>("MULTIPOINT(0 0, 1 1, 2 2)", "POLYGON((0 0, 0 4, 4 4, 4 0, 0 0),(1 1, 3 1, 3 3, 1 3, 1 1))", "F00FFF212"); + test_geometry<mpt, poly>("MULTIPOINT(2 2, 4 4)", "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(1 1, 3 1, 3 3, 1 3, 1 1))", "0F0FFF212"); +} + +template <typename P> +void test_multipoint_multipolygon() +{ + typedef bg::model::multi_point<P> mpt; + typedef bg::model::polygon<P> poly; + typedef bg::model::multi_polygon<poly> mpoly; + + test_geometry<mpt, mpoly>("MULTIPOINT(0 0)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "F0FFFF212"); + test_geometry<mpt, mpoly>("MULTIPOINT(0 0, 1 1)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "00FFFF212"); + test_geometry<mpt, mpoly>("MULTIPOINT(1 1, 5 5)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "00FFFF212"); + test_geometry<mpt, mpoly>("MULTIPOINT(1 6, 6 6)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "0F0FFF212"); + test_geometry<mpt, mpoly>("MULTIPOINT(0 0, 1 6)", "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)),((5 5, 5 9, 9 9, 9 5, 5 5)))", "F00FFF212"); +} + +template <typename P> +void test_all() +{ + test_point_point<P>(); + test_point_multipoint<P>(); + test_multipoint_multipoint<P>(); + + test_point_linestring<P>(); + test_point_multilinestring<P>(); + test_multipoint_linestring<P>(); + test_multipoint_multilinestring<P>(); + + test_point_ring_polygon<P>(); + test_point_multipolygon<P>(); + test_multipoint_ring_polygon<P>(); + test_multipoint_multipolygon<P>(); +} + +int test_main( int , char* [] ) +{ + check_mask(); + + test_all<bg::model::d2::point_xy<int> >(); + test_all<bg::model::d2::point_xy<double> >(); + +#if defined(HAVE_TTMATH) + test_all<bg::model::d2::point_xy<ttmath_big> >(); +#endif + + return 0; +} diff --git a/src/boost/libs/geometry/test/algorithms/relate/test_relate.hpp b/src/boost/libs/geometry/test/algorithms/relate/test_relate.hpp new file mode 100644 index 00000000..859d29ad --- /dev/null +++ b/src/boost/libs/geometry/test/algorithms/relate/test_relate.hpp @@ -0,0 +1,232 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. + +// This file was modified by Oracle on 2013, 2014, 2015, 2017. +// Modifications copyright (c) 2013-2017 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) + +#ifndef BOOST_GEOMETRY_TEST_RELATE_HPP +#define BOOST_GEOMETRY_TEST_RELATE_HPP + +#include <geometry_test_common.hpp> + +#include <boost/variant.hpp> + +#include <boost/geometry/core/ring_type.hpp> +#include <boost/geometry/algorithms/relate.hpp> +#include <boost/geometry/algorithms/relation.hpp> +#include <boost/geometry/strategies/strategies.hpp> +#include <boost/geometry/geometries/geometries.hpp> +#include <boost/geometry/geometries/point_xy.hpp> + +#include <boost/geometry/io/wkt/read.hpp> + +#include <boost/geometry/strategies/cartesian/point_in_box.hpp> +#include <boost/geometry/strategies/cartesian/box_in_box.hpp> +#include <boost/geometry/strategies/agnostic/point_in_box_by_side.hpp> + +namespace bgdr = bg::detail::relate; + +std::string transposed(std::string matrix) +{ + if ( !matrix.empty() ) + { + std::swap(matrix[1], matrix[3]); + std::swap(matrix[2], matrix[6]); + std::swap(matrix[5], matrix[7]); + } + return matrix; +} + +bool matrix_compare(std::string const& m1, std::string const& m2) +{ + BOOST_ASSERT(m1.size() == 9 && m2.size() == 9); + for ( size_t i = 0 ; i < 9 ; ++i ) + { + if ( m1[i] == '*' || m2[i] == '*' ) + continue; + + if ( m1[i] != m2[i] ) + return false; + } + return true; +} + +bool matrix_compare(std::string const& m, std::string const& res1, std::string const& res2) +{ + return matrix_compare(m, res1) + || ( !res2.empty() ? matrix_compare(m, res2) : false ); +} + +std::string matrix_format(std::string const& matrix1, std::string const& matrix2) +{ + return matrix1 + + ( !matrix2.empty() ? " || " : "" ) + matrix2; +} + +template <typename M> +char get_ii(M const& m) +{ + using bg::detail::relate::interior; + return m.template get<interior, interior>(); +} + +template <typename M> +char get_ee(M const& m) +{ + using bg::detail::relate::exterior; + return m.template get<exterior, exterior>(); +} + +void check_mask() +{ + bg::de9im::mask m1(""); + bg::de9im::mask m2("TTT"); + bg::de9im::mask m3("000111222"); + bg::de9im::mask m4("000111222FFFF"); + bg::de9im::mask m5(std::string("")); + bg::de9im::mask m6(std::string("TTT")); + bg::de9im::mask m7(std::string("000111222")); + bg::de9im::mask m8(std::string("000111222FFFF")); + + using bg::detail::relate::interior; + using bg::detail::relate::exterior; + + BOOST_CHECK(get_ii(m1) == '*' && get_ee(m1) == '*'); + BOOST_CHECK(get_ii(m2) == 'T' && get_ee(m2) == '*'); + BOOST_CHECK(get_ii(m3) == '0' && get_ee(m3) == '2'); + BOOST_CHECK(get_ii(m4) == '0' && get_ee(m4) == '2'); + BOOST_CHECK(get_ii(m5) == '*' && get_ee(m5) == '*'); + BOOST_CHECK(get_ii(m6) == 'T' && get_ee(m6) == '*'); + BOOST_CHECK(get_ii(m7) == '0' && get_ee(m7) == '2'); + BOOST_CHECK(get_ii(m8) == '0' && get_ee(m8) == '2'); +} + +template <typename Geometry1, typename Geometry2> +void check_geometry(Geometry1 const& geometry1, + Geometry2 const& geometry2, + std::string const& wkt1, + std::string const& wkt2, + std::string const& expected1, + std::string const& expected2 = std::string()) +{ + boost::variant<Geometry1> variant1 = geometry1; + boost::variant<Geometry2> variant2 = geometry2; + + { + std::string res_str = bg::relation(geometry1, geometry2).str(); + bool ok = matrix_compare(res_str, expected1, expected2); + BOOST_CHECK_MESSAGE(ok, + "relate: " << wkt1 + << " and " << wkt2 + << " -> Expected: " << matrix_format(expected1, expected2) + << " detected: " << res_str); + + typedef typename bg::strategy::relate::services::default_strategy + < + Geometry1, Geometry2 + >::type strategy_type; + std::string res_str0 = bg::relation(geometry1, geometry2, strategy_type()).str(); + BOOST_CHECK(res_str == res_str0); + + // test variants + boost::variant<Geometry1> v1 = geometry1; + boost::variant<Geometry2> v2 = geometry2; + std::string res_str1 = bg::relation(geometry1, variant2).str(); + std::string res_str2 = bg::relation(variant1, geometry2).str(); + std::string res_str3 = bg::relation(variant1, variant2).str(); + BOOST_CHECK(res_str == res_str1); + BOOST_CHECK(res_str == res_str2); + BOOST_CHECK(res_str == res_str3); + } + + // changed sequence of geometries - transposed result + { + std::string res_str = bg::relation(geometry2, geometry1).str(); + std::string expected1_tr = transposed(expected1); + std::string expected2_tr = transposed(expected2); + bool ok = matrix_compare(res_str, expected1_tr, expected2_tr); + BOOST_CHECK_MESSAGE(ok, + "relate: " << wkt2 + << " and " << wkt1 + << " -> Expected: " << matrix_format(expected1_tr, expected2_tr) + << " detected: " << res_str); + } + + if ( expected2.empty() ) + { + { + bool result = bg::relate(geometry1, geometry2, bg::de9im::mask(expected1)); + // TODO: SHOULD BE !interrupted - CHECK THIS! + BOOST_CHECK_MESSAGE(result, + "relate: " << wkt1 + << " and " << wkt2 + << " -> Expected: " << expected1); + + typedef typename bg::strategy::relate::services::default_strategy + < + Geometry1, Geometry2 + >::type strategy_type; + bool result0 = bg::relate(geometry1, geometry2, bg::de9im::mask(expected1), strategy_type()); + BOOST_CHECK(result == result0); + + // test variants + bool result1 = bg::relate(geometry1, variant2, bg::de9im::mask(expected1)); + bool result2 = bg::relate(variant1, geometry2, bg::de9im::mask(expected1)); + bool result3 = bg::relate(variant1, variant2, bg::de9im::mask(expected1)); + BOOST_CHECK(result == result1); + BOOST_CHECK(result == result2); + BOOST_CHECK(result == result3); + } + + if ( BOOST_GEOMETRY_CONDITION(( + bg::detail::relate::interruption_enabled<Geometry1, Geometry2>::value )) ) + { + // brake the expected output + std::string expected_interrupt = expected1; + bool changed = false; + BOOST_FOREACH(char & c, expected_interrupt) + { + if ( c >= '0' && c <= '9' ) + { + if ( c == '0' ) + c = 'F'; + else + --c; + + changed = true; + } + } + + if ( changed ) + { + bool result = bg::relate(geometry1, geometry2, bg::de9im::mask(expected_interrupt)); + // TODO: SHOULD BE interrupted - CHECK THIS! + BOOST_CHECK_MESSAGE(!result, + "relate: " << wkt1 + << " and " << wkt2 + << " -> Expected interrupt for:" << expected_interrupt); + } + } + } +} + +template <typename Geometry1, typename Geometry2> +void test_geometry(std::string const& wkt1, + std::string const& wkt2, + std::string const& expected1, + std::string const& expected2 = std::string()) +{ + Geometry1 geometry1; + Geometry2 geometry2; + bg::read_wkt(wkt1, geometry1); + bg::read_wkt(wkt2, geometry2); + check_geometry(geometry1, geometry2, wkt1, wkt2, expected1, expected2); +} + +#endif // BOOST_GEOMETRY_TEST_RELATE_HPP |