ceph/src/boost/libs/geometry/test/algorithms/relate/relate_linear_areal.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2018 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2013, 2014, 2015.
   7 // Modifications copyright (c) 2013-2015 Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #include "test_relate.hpp"
  16 #include "nan_cases.hpp"
  17
  18 //TEST
  19 //#include <to_svg.hpp>
  20
  21 template <typename P>
  22 void test_linestring_polygon()
  23 {
  24     typedef bg::model::linestring<P> ls;
  25     typedef bg::model::polygon<P> poly;
  26     typedef bg::model::ring<P> ring;
  27
  28     // LS disjoint
  29     test_geometry<ls, poly>("LINESTRING(11 0,11 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212");
  30     test_geometry<ls, ring>("LINESTRING(11 0,11 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212");
  31
  32     // II BB
  33     test_geometry<ls, poly>("LINESTRING(0 0,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))",    "1FFF0F212");
  34     test_geometry<ls, poly>("LINESTRING(5 0,5 5,10 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1FFF0F212");
  35     test_geometry<ls, poly>("LINESTRING(5 1,5 5,9 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))",  "1FF0FF212");
  36
  37     // IE
  38     test_geometry<ls, poly>("LINESTRING(11 1,11 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1FF0212");
  39     // IE IB0
  40     test_geometry<ls, poly>("LINESTRING(11 1,10 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "FF1F00212");
  41     // IE IB1
  42     test_geometry<ls, poly>("LINESTRING(11 1,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212");
  43     test_geometry<ls, poly>("LINESTRING(11 1,10 10,0 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212");
  44     test_geometry<ls, poly>("LINESTRING(11 1,10 0,0 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212");
  45     test_geometry<ls, poly>("LINESTRING(0 -1,1 0,2 0)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212");
  46     // IE IB0 II
  47     test_geometry<ls, poly>("LINESTRING(11 1,10 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212");
  48     // IE IB0 lring
  49     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");
  50     // IE IB1 lring
  51     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");
  52
  53     // IB1 II
  54     test_geometry<ls, poly>("LINESTRING(0 0,5 0,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212");
  55     // BI0 II IB1
  56     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");
  57
  58     // IB1 II IB1
  59     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");
  60     // IB1 IE IB1
  61     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");
  62
  63     // II IB1
  64     test_geometry<ls, poly>("LINESTRING(5 5,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212");
  65     // IB1 II
  66     test_geometry<ls, poly>("LINESTRING(10 10,10 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "11F00F212");
  67     // IE IB1
  68     test_geometry<ls, poly>("LINESTRING(15 5,10 5,10 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212");
  69     // IB1 IE
  70     test_geometry<ls, poly>("LINESTRING(10 10,10 5,15 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "F11F00212");
  71
  72     // duplicated points
  73     {
  74         // II IB0 IE
  75         test_geometry<ls, poly>("LINESTRING(5 5,10 5,15 10)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212");
  76         test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5,10 5,10 5,10 5,15 10,15 10,15 10)",
  77             "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))",
  78             "1010F0212");
  79         test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5,10 0,10 0,10 0,15 10,15 10,15 10)",
  80             "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))",
  81             "1010F0212");
  82         // IE IB0 II
  83         test_geometry<ls, poly>("LINESTRING(15 10,15 10,15 10,10 5,10 5,10 5,5 5,5 5,5 5)",
  84             "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))",
  85             "1010F0212");
  86         test_geometry<ls, poly>("LINESTRING(15 10,15 10,15 10,10 0,10 0,10 0,5 5,5 5,5 5)",
  87             "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))",
  88             "1010F0212");
  89
  90         // TEST
  91         //test_geometry<ls, poly>("LINESTRING(5 5,5 5,5 5)", "POLYGON((0 0,0 10,10 10,10 0,0 0))", "1010F0212");
  92         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");
  93     }
  94
  95     // non-simple polygon with hole
  96     test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9)",
  97                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))",
  98                             "10F0FF212");
  99     test_geometry<ls, poly>("LINESTRING(10 1,10 5,10 9)",
 100                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))",
 101                             "F1FF0F212");
 102     test_geometry<ls, poly>("LINESTRING(2 8,10 5,2 2)",
 103                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))",
 104                             "F1FF0F212");
 105     test_geometry<ls, poly>("LINESTRING(10 1,10 5,2 2)",
 106                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))",
 107                             "F1FF0F212");
 108     test_geometry<ls, poly>("LINESTRING(10 1,10 5,2 8)",
 109                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))",
 110                             "F1FF0F212");
 111
 112     // non-simple polygon with hole, linear ring
 113     test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9,1 9,1 1,9 1)",
 114                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))",
 115                             "10FFFF212");
 116     test_geometry<ls, poly>("LINESTRING(10 5,10 9,11 5,10 1,10 5)",
 117                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))",
 118                             "F11FFF212");
 119     test_geometry<ls, poly>("LINESTRING(11 5,10 1,10 5,10 9,11 5)",
 120                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(10 5,2 8,2 2,10 5))",
 121                             "F11FFF212");
 122
 123     // non-simple polygon with self-touching holes
 124     test_geometry<ls, poly>("LINESTRING(7 1,8 5,7 9)",
 125                             "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))",
 126                             "10F0FF212");
 127     test_geometry<ls, poly>("LINESTRING(8 2,8 5,8 8)",
 128                             "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))",
 129                             "F1FF0F212");
 130     test_geometry<ls, poly>("LINESTRING(2 8,8 5,2 2)",
 131                             "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))",
 132                             "F1FF0F212");
 133
 134     // non-simple polygon self-touching
 135     test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9)",
 136                             "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))",
 137                             "10F0FF212");
 138     test_geometry<ls, poly>("LINESTRING(10 1,10 5,10 9)",
 139                             "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))",
 140                             "F1FF0F212");
 141     test_geometry<ls, poly>("LINESTRING(2 8,10 5,2 2)",
 142                             "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))",
 143                             "F1FF0F212");
 144
 145     // non-simple polygon self-touching, linear ring
 146     test_geometry<ls, poly>("LINESTRING(9 1,10 5,9 9,1 9,1 1,9 1)",
 147                             "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))",
 148                             "10FFFF212");
 149     test_geometry<ls, poly>("LINESTRING(10 5,10 9,11 5,10 1,10 5)",
 150                             "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))",
 151                             "F11FFF212");
 152     test_geometry<ls, poly>("LINESTRING(11 5,10 1,10 5,10 9,11 5)",
 153                             "POLYGON((0 0,0 10,10 10,10 5,2 8,2 2,10 5,10 0,0 0))",
 154                             "F11FFF212");
 155
 156     // polygons with some ring equal to the linestring
 157     test_geometry<ls, poly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)",
 158                             "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 159                             "F1FFFF2F2");
 160     test_geometry<ls, poly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)",
 161                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2))",
 162                             "F1FFFF212");
 163     test_geometry<ls, poly>("LINESTRING(2 2,5 5,2 8,2 2)",
 164                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2))",
 165                             "F1FFFF212");
 166
 167     // self-IP going on the boundary then into the exterior and to the boundary again
 168     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))",
 169                             "F11F0F212");
 170     // self-IP going on the boundary then into the interior and to the boundary again
 171     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))",
 172                             "11FF0F212");
 173
 174     // self-IP with a hole -> B to I to B to E
 175     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))",
 176                             "FF1F00212");
 177
 178     // ccw
 179     {
 180         typedef bg::model::polygon<P, false> ccwpoly;
 181
 182         // IE IB0 II
 183         test_geometry<ls, ccwpoly>("LINESTRING(11 1,10 5,5 5)", "POLYGON((0 0,10 0,10 10,0 10,0 0))", "1010F0212");
 184         // IE IB1 II
 185         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");
 186         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");
 187         // II IB0 IE
 188         test_geometry<ls, ccwpoly>("LINESTRING(5 1,10 5,11 1)", "POLYGON((0 0,10 0,10 10,0 10,0 0))", "1010F0212");
 189         // IE IB1 II
 190         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");
 191         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");
 192
 193     }
 194
 195     {
 196         // SPIKES
 197
 198         test_geometry<ls, poly>("LINESTRING(0 0,2 2,3 3,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212");
 199         test_geometry<ls, poly>("LINESTRING(0 0,3 3,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212");
 200         test_geometry<ls, poly>("LINESTRING(0 0,2 2,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212");
 201         test_geometry<ls, poly>("LINESTRING(1 1,3 3,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212");
 202         test_geometry<ls, poly>("LINESTRING(1 1,2 2,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FFFF212");
 203
 204         test_geometry<ls, poly>("LINESTRING(3 3,1 1,0 0,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212");
 205         test_geometry<ls, poly>("LINESTRING(3 3,0 0,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212");
 206         test_geometry<ls, poly>("LINESTRING(2 2,0 0,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212");
 207         test_geometry<ls, poly>("LINESTRING(3 3,1 1,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FF0F212");
 208         test_geometry<ls, poly>("LINESTRING(2 2,1 1,2 2)", "POLYGON((0 0,3 3,3 0,0 0))", "F1FFFF212");
 209
 210         test_geometry<ls, poly>("LINESTRING(0 0,2 2,4 4,1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F11F0F212");
 211
 212         test_geometry<ls, poly>("LINESTRING(0 1,1 1,0 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F01FFF212");
 213         test_geometry<ls, poly>("LINESTRING(0 1,3 3,0 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F01FFF212");
 214         test_geometry<ls, poly>("LINESTRING(0 1,0 0,0 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F01FFF212");
 215
 216         test_geometry<ls, poly>("LINESTRING(0 1,1 1,-1 1)", "POLYGON((0 0,3 3,3 0,0 0))", "F01FF0212");
 217     }
 218
 219     {
 220         // POLYGON SPIKES
 221         // note that those are invalid Polygons and in general the result is undefined
 222
 223         // MySQL bug 15.12.2014 (assertion for invalid polygon)
 224         test_geometry<ls, poly>("LINESTRING(6 3,9 0)",
 225                                 "POLYGON((0 0,5 8,6 1,6 3,8 1,5 4,9 6,2 5,7 4,1 7,0 0))",
 226                                 "F11F00212");
 227         test_geometry<ls, poly>("LINESTRING(9 0,2 7)",
 228                                 "POLYGON((4 1,3 2,5 9,8 4,4 5,3 6,8 1,6 2,2 4,6 0,4 1))",
 229                                 "F11FF0212");
 230
 231         test_geometry<ls, poly>("LINESTRING(6 3,9 0)",
 232                                 "POLYGON((6 1,6 3,8 1,5 4,6 1))",
 233                                 "F11F00212");
 234         test_geometry<ls, poly>("LINESTRING(6 3,8 1,9 0)",
 235                                 "POLYGON((6 1,6 3,8 1,5 4,6 1))",
 236                                 "F11F00212");
 237
 238         // entry-point spikes are not handled
 239         test_geometry<ls, poly>("LINESTRING(9 0,6 3)",
 240                                 "POLYGON((6 1,6 3,8 1,5 4,6 1))",
 241                                 "**1*00212");
 242         test_geometry<ls, poly>("LINESTRING(9 0,8 1,6 3)",
 243                                 "POLYGON((6 1,6 3,8 1,5 4,6 1))",
 244                                 "F11F00212");
 245
 246         // Ls going out-in on 2 collinear spikes touching each other
 247         //  this works partially, other invalid effect is noticeable here,
 248         //  the bottom of a spike shouldn't be there so the algorithm
 249         //  thinks the linestring is going into the interior
 250         test_geometry<ls, poly>("LINESTRING(2 2,6 6)",
 251                                 "POLYGON((0 0,0 2,2 2,4 4,3 3,5 3,5 5,4 4,7 7,7 0,0 0))",
 252                                 "*1FF0F212");
 253         // Ls going out-in on 2 collinear spikes NOT touching each other
 254         // This is not supported, plus the same as above
 255         test_geometry<ls, poly>("LINESTRING(2 2,6 6)",
 256                                 "POLYGON((0 0,0 2,2 2,3 3,2 2,5 3,5 5,4 4,7 7,7 0,0 0))",
 257                                 "*1*F0*212");
 258     }
 259
 260     // 21.01.2015
 261     test_geometry<ls, poly>("LINESTRING(3 7, 9 1)",
 262                             "POLYGON((0 0,0 10,10 10,10 0,5 5,0 0))",
 263                             "11F00F212");
 264
 265     // inspired by the bug for mls/poly
 266     test_geometry<ls, poly>("LINESTRING(0 0, 7 7)",
 267                             "POLYGON((5 5,5 15,15 15,15 5,5 5))",
 268                             "1010F0212");
 269
 270     // 25.01.2015
 271     test_geometry<ls, poly>("LINESTRING(4 5, 0 6, 5 6)",
 272                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(4 4,6 4,6 6,4 6,4 4))",
 273                             "11FF0F212");
 274     test_geometry<ls, poly>("LINESTRING(2 3, 4 5, 0 6, 5 6)",
 275                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(4 4,6 4,6 6,4 6,4 4))",
 276                             "11F00F212");
 277     test_geometry<ls, poly>("LINESTRING(2 9, 1 1, 10 1, 10 10, 1 10, 0 6, 5 6)",
 278                             "POLYGON((0 0,0 10,10 10,10 0,0 0),(4 4,4 6,6 6,6 4,4 4))",
 279                             "11F00F212");
 280 }
 281
 282 template <typename P>
 283 void test_linestring_multi_polygon()
 284 {
 285     typedef bg::model::linestring<P> ls;
 286     typedef bg::model::polygon<P> poly;
 287     typedef bg::model::multi_polygon<poly> mpoly;
 288
 289     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,10 9)",
 290                             "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)))",
 291                             "F1FF0F212");
 292     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,10 9)",
 293                             "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0)))",
 294                             "F1FF0F212");
 295
 296     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)",
 297                             "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)))",
 298                             "F1FF0F212");
 299     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)",
 300                             "MULTIPOLYGON(((0 20,0 30,10 30,10 20,0 20)),((0 0,0 10,10 10,10 0,0 0)))",
 301                             "11F00F212");
 302
 303     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 2)",
 304                             "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)))",
 305                             "F1FF0F212");
 306     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,2 8)",
 307                             "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)))",
 308                             "F1FF0F212");
 309     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,3 3)",
 310                             "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)))",
 311                             "F1FF0F212");
 312     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,3 7)",
 313                             "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)))",
 314                             "F1FF0F212");
 315     test_geometry<ls, mpoly>("LINESTRING(10 1,10 5,5 5)",
 316                             "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)))",
 317                             "11F00F212");
 318
 319     test_geometry<ls, mpoly>("LINESTRING(0 0,10 0,10 10,0 10,0 0)",
 320                              "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((20 0,20 10,30 20,20 0)))",
 321                              "F1FFFF212");
 322
 323     // degenerated points
 324     test_geometry<ls, mpoly>("LINESTRING(5 5,10 10,10 10,10 10,15 15)",
 325                              "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((10 10,10 20,20 20,20 10,10 10)))",
 326                              "10F0FF212");
 327
 328     // 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
 329     test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)",
 330                              "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)))",
 331                              "FF1F00212");
 332     // self-IP polygon with a hole and second polygon -> B to I to B to B to I
 333     test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)",
 334                              "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)))",
 335                              "1FF00F212");
 336     test_geometry<ls, mpoly>("LINESTRING(0 0,3 3)",
 337                              "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)))",
 338                              "1FF00F212");
 339
 340     // MySQL report 18.12.2014 (https://svn.boost.org/trac/boost/ticket/10887)
 341     test_geometry<ls, mpoly>("LINESTRING(5 -2,5 2)",
 342                              "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 343                              "10F0FF212");
 344     test_geometry<ls, mpoly>("LINESTRING(5 -2,5 5)",
 345                              "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 346                              "10F00F212");
 347     test_geometry<ls, mpoly>("LINESTRING(5 -2,5 0)",
 348                              "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 349                              "1FF00F212");
 350     // MySQL report 18.12.2014 - extended
 351     test_geometry<ls, mpoly>("LINESTRING(5 -2,5 0)",
 352                              "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)))",
 353                              "1FF00F212");
 354     test_geometry<ls, mpoly>("LINESTRING(0 0,5 0)",
 355                              "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)))",
 356                              "FF1F00212");
 357
 358     // 22.01.2015
 359     test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,10 0)",
 360                              "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 361                              "11F00F212");
 362     test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,0 10)",
 363                              "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 364                              "11F00F212");
 365     // extended
 366     test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,2 1)",
 367                              "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 368                              "10F0FF212");
 369     test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,5 -5)",
 370                              "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 371                              "1010F0212");
 372     test_geometry<ls, mpoly>("LINESTRING(5 5,0 0,5 -5,5 1)",
 373                              "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 374                              "1010FF212");
 375     test_geometry<ls, mpoly>("LINESTRING(-5 5,0 0,5 -5)",
 376                              "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 377                              "F01FF0212");
 378 }
 379
 380 template <typename P>
 381 void test_multi_linestring_polygon()
 382 {
 383     typedef bg::model::linestring<P> ls;
 384     typedef bg::model::multi_linestring<ls> mls;
 385     typedef bg::model::polygon<P> poly;
 386     typedef typename bg::coordinate_type<P>::type coord_t;
 387
 388     test_geometry<mls, poly>("MULTILINESTRING((11 11, 20 20),(5 7, 4 1))",
 389                              "POLYGON((0 0,0 10,10 10,10 0,0 0),(2 2,4 2,4 4,2 4,2 2))",
 390                              "1F10F0212");
 391     test_geometry<mls, poly>("MULTILINESTRING((10 0, 18 12),(2 2,2 1))",
 392                              "POLYGON((5 0,0 -5,-5 0,0 5,5 0))",
 393                              "1F10F0212");
 394
 395     if ( BOOST_GEOMETRY_CONDITION((
 396             boost::is_same<coord_t, double>::value )) )
 397     {
 398         // assertion failure in 1.57
 399         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))",
 400                                  "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))",
 401                                  "*********");
 402         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))",
 403                                  "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))",
 404                                  "*********");
 405     }
 406
 407     // 21.01.2015
 408     test_geometry<mls, poly>("MULTILINESTRING((6 6,15 15),(0 0, 7 7))",
 409                              "POLYGON((5 5,5 15,15 15,15 5,5 5))",
 410                              "101000212");
 411     test_geometry<mls, poly>("MULTILINESTRING((15 15,6 6),(0 0, 7 7))",
 412                              "POLYGON((5 5,5 15,15 15,15 5,5 5))",
 413                              "101000212");
 414     // extended
 415     test_geometry<mls, poly>("MULTILINESTRING((15 15,6 6),(4 14,6 16))",
 416                              "POLYGON((5 5,5 15,15 15,15 5,5 5))",
 417                              "101000212");
 418
 419     // 23.01.2015
 420     test_geometry<mls, poly>("MULTILINESTRING((4 10, 3 10, 10 6),(5 0, 7 5, 9 10))",
 421                              "POLYGON((0 0,0 10,10 10,10 0,5 5,0 0))",
 422                              "111F00212");
 423
 424     // 23.01.2015
 425     test_geometry<mls, poly>("MULTILINESTRING((3 10, 1 5, 1 10, 3 4, 7 8, 6 10, 10 2))",
 426                              "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 427                              "10FF0F212");
 428
 429     // mysql bug
 430     // assertion failure in relate->boundary_checker->std::equal_range with msvc
 431     if (BOOST_GEOMETRY_CONDITION(is_nan_case_supported<mls>::value))
 432     {
 433         mls g1;
 434         std::string wkt1;
 435         nan_case(g1, wkt1);
 436
 437         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))";
 438         poly g2;
 439         bg::read_wkt(wkt2, g2);
 440
 441         check_geometry(g1, g2, wkt1, wkt2, "*********");
 442     }
 443 }
 444
 445 template <typename P>
 446 void test_multi_linestring_multi_polygon()
 447 {
 448     typedef bg::model::linestring<P> ls;
 449     typedef bg::model::polygon<P> poly;
 450     typedef bg::model::multi_linestring<ls> mls;
 451     typedef bg::model::multi_polygon<poly> mpoly;
 452
 453     // polygons with some ring equal to the linestrings
 454     test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10,0 10,0 0),(20 20,50 50,20 80,20 20))",
 455                               "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))",
 456                               "F11FFF2F2");
 457
 458     test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10,0 10,0 0),(2 2,5 5,2 8,2 2))",
 459                               "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(2 2,5 5,2 8,2 2)))",
 460                               "F1FFFF2F2");
 461
 462
 463     test_geometry<mls, mpoly>("MULTILINESTRING((0 0,10 0,10 10),(10 10,0 10,0 0))",
 464                               "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))",
 465                               "F1FFFF2F2");
 466     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))",
 467                               "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))",
 468                               "F11FFF2F2");
 469
 470     // disjoint
 471     test_geometry<mls, mpoly>("MULTILINESTRING((20 20,30 30),(30 30,40 40))",
 472                               "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)))",
 473                               "FF1FF0212");
 474
 475     test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 5),(5 5,5 0),(10 10,10 5,5 5,5 10,10 10))",
 476                               "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)))",
 477                               "F1FF0F212");
 478     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))",
 479                               "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)))",
 480                               "F1FFFF212");
 481     test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 0),(5 5,5 0),(10 10,10 5,5 5,5 10,10 10))",
 482                               "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)))",
 483                               "11FF0F212");
 484
 485     // MySQL report 18.12.2014 - extended
 486     test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,4 -2,5 0),(5 -2,6 -2,5 0))",
 487                               "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 488                               "10FFFF212");
 489     test_geometry<mls, mpoly>("MULTILINESTRING((0 0,0 1,5 0),(0 0,0 -1,5 0))",
 490                               "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 491                               "F01FFF212");
 492     test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,4 -2,5 0),(6 -2,5 0))",
 493                               "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 494                               "10F0FF212");
 495     test_geometry<mls, mpoly>("MULTILINESTRING((0 0,0 1,5 0),(0 -1,5 0))",
 496                               "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 497                               "F01FF0212");
 498     test_geometry<mls, mpoly>("MULTILINESTRING((0 0,5 0),(5 -2,5 0))",
 499                               "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 500                               "1010F0212");
 501     test_geometry<mls, mpoly>("MULTILINESTRING((5 -2,5 0),(0 0,5 0))",
 502                               "MULTIPOLYGON(((5 0,0 5,10 5,5 0)),((5 0,10 -5,0 -5,5 0)))",
 503                               "1010F0212");
 504
 505     // 22.01.2015 - extended
 506     test_geometry<mls, mpoly>("MULTILINESTRING((10 10,0 10),(5 5,0 0,10 0))",
 507                               "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 508                               "11F00F212");
 509     test_geometry<mls, mpoly>("MULTILINESTRING((5 5,0 0,5 -5),(0 0,9 1))",
 510                               "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 511                               "101000212");
 512     test_geometry<mls, mpoly>("MULTILINESTRING((5 -5,0 0,5 5),(0 0,5 -1))",
 513                               "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((0 0,0 -10,-10 -10,-10 0,0 0)))",
 514                               "101000212");
 515 }
 516
 517 template <typename P>
 518 void test_all()
 519 {
 520     test_linestring_polygon<P>();
 521     test_linestring_multi_polygon<P>();
 522     test_multi_linestring_polygon<P>();
 523     test_multi_linestring_multi_polygon<P>();
 524 }
 525
 526 int test_main( int , char* [] )
 527 {
 528     test_all<bg::model::d2::point_xy<int> >();
 529     test_all<bg::model::d2::point_xy<double> >();
 530
 531     return 0;
 532 }