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