ceph/src/boost/libs/geometry/test/algorithms/set_operations/difference/difference_linear_linear.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2015, Oracle and/or its affiliates.
   4
   5 // Licensed under the Boost Software License version 1.0.
   6 // http://www.boost.org/users/license.html
   7
   8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   9
  10 #include <iostream>
  11
  12 #ifndef BOOST_TEST_MODULE
  13 #define BOOST_TEST_MODULE test_difference_linear_linear
  14 #endif
  15
  16 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  17 #define BOOST_GEOMETRY_DEBUG_TURNS
  18 #define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER
  19 #endif
  20
  21 #include <boost/test/included/unit_test.hpp>
  22
  23 #include "test_difference_linear_linear.hpp"
  24
  25 #include <boost/geometry/geometries/linestring.hpp>
  26 #include <boost/geometry/geometries/multi_linestring.hpp>
  27 #include <boost/geometry/algorithms/difference.hpp>
  28
  29 typedef bg::model::point<double,2,bg::cs::cartesian>  point_type;
  30 typedef bg::model::segment<point_type>                segment_type;
  31 typedef bg::model::linestring<point_type>             linestring_type;
  32 typedef bg::model::multi_linestring<linestring_type>  multi_linestring_type;
  33
  34
  35
  36 //===========================================================================
  37 //===========================================================================
  38 //===========================================================================
  39
  40
  41 BOOST_AUTO_TEST_CASE( test_difference_linestring_linestring )
  42 {
  43 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  44     std::cout << std::endl << std::endl << std::endl;
  45     std::cout << "*** LINESTRING / LINESTRING DIFFERENCE ***" << std::endl;
  46     std::cout << std::endl;
  47 #endif
  48
  49     typedef linestring_type L;
  50     typedef multi_linestring_type ML;
  51
  52     typedef test_difference_of_geometries<L, L, ML> tester;
  53
  54     tester::apply
  55         (from_wkt<L>("LINESTRING(0 0,1 1,2 1,3 2)"),
  56          from_wkt<L>("LINESTRING(0 2,1 1,2 1,3 0)"),
  57          from_wkt<ML>("MULTILINESTRING((0 0,1 1),(2 1,3 2))"),
  58          "lldf00");
  59
  60     tester::apply
  61         (from_wkt<L>("LINESTRING(0 2,1 1,2 1,3 0)"),
  62          from_wkt<L>("LINESTRING(0 0,1 1,2 1,3 2)"),
  63          from_wkt<ML>("MULTILINESTRING((0 2,1 1),(2 1,3 0))"),
  64          "lldf00-1");
  65
  66     tester::apply
  67         (from_wkt<L>("LINESTRING(0 0,5 0)"),
  68          from_wkt<L>("LINESTRING(3 0,4 0)"),
  69          from_wkt<ML>("MULTILINESTRING((0 0,3 0),(4 0,5 0))"),
  70          "lldf01");
  71
  72     tester::apply
  73         (from_wkt<L>("LINESTRING(3 0,4 0)"),
  74          from_wkt<L>("LINESTRING(0 0,5 0)"),
  75          from_wkt<ML>("MULTILINESTRING()"),
  76          "lldf01-1");
  77
  78     tester::apply
  79         (from_wkt<L>("LINESTRING(0 0,4 0)"),
  80          from_wkt<L>("LINESTRING(3 0,6 0)"),
  81          from_wkt<ML>("MULTILINESTRING((0 0,3 0))"),
  82          "lldf01-2");
  83
  84     tester::apply
  85         (from_wkt<L>("LINESTRING(3 0,6 0)"),
  86          from_wkt<L>("LINESTRING(0 0,4 0)"),
  87          from_wkt<ML>("MULTILINESTRING((4 0,6 0))"),
  88          "lldf01-3");
  89
  90     tester::apply
  91         (from_wkt<L>("LINESTRING(0 0,6 0)"),
  92          from_wkt<L>("LINESTRING(0 0,4 0)"),
  93          from_wkt<ML>("MULTILINESTRING((4 0,6 0))"),
  94          "lldf01-4");
  95
  96     tester::apply
  97         (from_wkt<L>("LINESTRING(0 0,4 0)"),
  98          from_wkt<L>("LINESTRING(0 0,6 0)"),
  99          from_wkt<ML>("MULTILINESTRING()"),
 100          "lldf01-5");
 101
 102     tester::apply
 103         (from_wkt<L>("LINESTRING(0 0,20 0)"),
 104          from_wkt<L>("LINESTRING(0 0,1 1,2 0,3 1,4 0,5 0,6 1,7 -1,8 0)"),
 105          from_wkt<ML>("MULTILINESTRING((0 0,4 0),(5 0,20 0))"),
 106          "lldf01-6");
 107
 108     tester::apply
 109         (from_wkt<L>("LINESTRING(-20 0,20 0)"),
 110          from_wkt<L>("LINESTRING(0 0,1 1,2 0,3 1,4 0,5 0,6 1,7 -1,8 0)"),
 111          from_wkt<ML>("MULTILINESTRING((-20 0,4 0),(5 0,20 0))"),
 112          "lldf01-7");
 113
 114     tester::apply
 115         (from_wkt<L>("LINESTRING(0 0,4 0)"),
 116          from_wkt<L>("LINESTRING(2 0,4 0)"),
 117          from_wkt<ML>("MULTILINESTRING((0 0,2 0))"),
 118          "lldf01-8");
 119
 120     tester::apply
 121         (from_wkt<L>("LINESTRING(2 0,4 0)"),
 122          from_wkt<L>("LINESTRING(0 0,4 0)"),
 123          from_wkt<ML>("MULTILINESTRING()"),
 124          "lldf01-9");
 125
 126     tester::apply
 127         (from_wkt<L>("LINESTRING(0 0,2 0)"),
 128          from_wkt<L>("LINESTRING(4 0,5 0)"),
 129          from_wkt<ML>("MULTILINESTRING((0 0,2 0))"),
 130          "lldf01-10");
 131
 132     tester::apply
 133         (from_wkt<L>("LINESTRING(0 0,2 0)"),
 134          from_wkt<L>("LINESTRING(2 0,5 0)"),
 135          from_wkt<ML>("MULTILINESTRING((0 0,2 0))"),
 136          "lldf01-11");
 137
 138     tester::apply
 139         (from_wkt<L>("LINESTRING(0 0,1 0,4 0)"),
 140          from_wkt<L>("LINESTRING(3 0,5 0)"),
 141          from_wkt<ML>("MULTILINESTRING((0 0,1 0,3 0))"),
 142          "lldf01-11a");
 143
 144     tester::apply
 145         (from_wkt<L>("LINESTRING(0 0,1 0,4 0)"),
 146          from_wkt<L>("LINESTRING(3 0,4 0,5 0)"),
 147          from_wkt<ML>("MULTILINESTRING((0 0,1 0,3 0))"),
 148          "lldf01-11b");
 149
 150     tester::apply
 151         (from_wkt<L>("LINESTRING(0 0,6 0)"),
 152          from_wkt<L>("LINESTRING(2 0,4 0,5 0)"),
 153          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(5 0,6 0))"),
 154          "lldf01-12");
 155
 156     tester::apply
 157         (from_wkt<L>("LINESTRING(0 0,1 0,5 5,10 5,15 0)"),
 158          from_wkt<L>("LINESTRING(-1 6,0 5,15 5)"),
 159          from_wkt<ML>("MULTILINESTRING((0 0,1 0,5 5),(10 5,15 0))"),
 160          "lldf02");
 161
 162     tester::apply
 163         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0)"),
 164          from_wkt<L>("LINESTRING(-1 0,30 0)"),
 165          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(1 0,5 5,10 5,15 0))"),
 166          "lldf03");
 167
 168     tester::apply
 169         (from_wkt<L>("LINESTRING(0 0,1 0,5 5,10 5,15 0,20 0)"),
 170          from_wkt<L>("LINESTRING(-1 0,30 0)"),
 171          from_wkt<ML>("MULTILINESTRING((1 0,5 5,10 5,15 0))"),
 172          "lldf04");
 173
 174     tester::apply
 175         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,25 1)"),
 176          from_wkt<L>("LINESTRING(-1 0,30 0)"),
 177          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(1 0,5 5,10 5,15 0),\
 178                       (20 0,25 1))"),
 179          "lldf05");
 180
 181     tester::apply
 182         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0)"),
 183          from_wkt<L>("LINESTRING(-1 0,30 0)"),
 184          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(1 0,5 5,10 5,15 0))"),
 185          "lldf05-1");
 186
 187     tester::apply
 188         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"),
 189          from_wkt<L>("LINESTRING(-1 0,30 0)"),
 190          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(1 0,5 5,10 5,15 0),\
 191                       (30 0,31 0))"),
 192          "lldf06");
 193
 194     tester::apply
 195         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"),
 196          from_wkt<L>("LINESTRING(-1 0,25 0,30 0)"),
 197          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(1 0,5 5,10 5,15 0),\
 198                       (30 0,31 0))"),
 199          "lldf07");
 200
 201     tester::apply
 202         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"),
 203          from_wkt<L>("LINESTRING(-1 0,19 0,30 0)"),
 204          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(1 0,5 5,10 5,15 0),\
 205                       (30 0,31 0))"),
 206          "lldf08");
 207
 208     tester::apply
 209         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0,31 1)"),
 210          from_wkt<L>("LINESTRING(-1 0,30 0)"),
 211          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(1 0,5 5,10 5,15 0),\
 212                       (30 0,31 1))"),
 213          "lldf09");
 214
 215     tester::apply
 216         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0,31 1)"),
 217          from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 1,3 0,30 0)"),
 218          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(1 0,5 5,10 5,15 0),\
 219                       (30 0,31 1))"),
 220          "lldf10");
 221
 222     tester::apply
 223         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,4 0,5 5,10 5,15 0,20 0,\
 224                                  30 0,31 1)"),
 225          from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 0,2.5 1,3 0,30 0)"),
 226          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(2 0,3 0),\
 227                       (4 0,5 5,10 5,15 0),(30 0,31 1))"),
 228          "lldf11");
 229
 230     tester::apply
 231         (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,4 0,5 5,10 5,15 0,31 0)"),
 232          from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 0,2.5 1,3 0,30 0)"),
 233          from_wkt<ML>("MULTILINESTRING((-1 1,0 0),(2 0,3 0),\
 234                       (4 0,5 5,10 5,15 0),(30 0,31 0))"),
 235          "lldf11-1");
 236
 237     tester::apply
 238         (from_wkt<L>("LINESTRING(0 0,2 0,3 1)"),
 239          from_wkt<L>("LINESTRING(0 0,2 0,3 1)"),
 240          from_wkt<ML>("MULTILINESTRING()"),
 241          "lldf12");
 242
 243     tester::apply
 244         (from_wkt<L>("LINESTRING(0 0,2 0,3 1)"),
 245          from_wkt<L>("LINESTRING(3 1,2 0,0 0)"),
 246          from_wkt<ML>("MULTILINESTRING()"),
 247          "lldf12-1");
 248
 249    tester::apply
 250         (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 5,4 0)"),
 251          from_wkt<L>("LINESTRING(1 0,2 1,3 5,4 0,5 10)"),
 252          from_wkt<ML>("MULTILINESTRING((0 0,1 0))"),
 253          "lldf13");
 254
 255     tester::apply
 256         (from_wkt<L>("LINESTRING(0 0,1 0,2 0,2.5 0,3 1)"),
 257          from_wkt<L>("LINESTRING(0 0,2 0,2.5 0,3 1)"),
 258          from_wkt<ML>("MULTILINESTRING()"),
 259          "lldf14");
 260
 261     tester::apply
 262         (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 5,4 0)"),
 263          from_wkt<L>("LINESTRING(1 0,2 1,3 5)"),
 264          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(3 5,4 0))"),
 265          "lldf15");
 266
 267     tester::apply
 268         (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 2)"),
 269          from_wkt<L>("LINESTRING(0.5 0,1 0,3 2,4 5)"),
 270          from_wkt<ML>("MULTILINESTRING((0 0,0.5 0))"),
 271          "lldf16");
 272
 273     tester::apply
 274         (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 2)"),
 275          from_wkt<L>("LINESTRING(4 5,3 2,1 0,0.5 0)"),
 276          from_wkt<ML>("MULTILINESTRING((0 0,0.5 0))"),
 277          "lldf16-r");
 278
 279     tester::apply
 280         (from_wkt<L>("LINESTRING(0 0,10 0,20 1,30 1)"),
 281          from_wkt<L>("LINESTRING(1 1,2 0,3 1,20 1,25 1)"),
 282          from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(25 1,30 1))"),
 283          "lldf17");
 284
 285     tester::apply
 286         (from_wkt<L>("LINESTRING(0 0,10 0,20 1,21 0,30 0)"),
 287          from_wkt<L>("LINESTRING(1 1,2 0,3 1,20 1,25 0)"),
 288          from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1,21 0,30 0))"),
 289          "lldf18");
 290
 291     tester::apply
 292         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 293          from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 1)"),
 294          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 295          "lldf19");
 296
 297     tester::apply
 298         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 299          from_wkt<L>("LINESTRING(5 1,4 0,4 1,20 1,5 0,1 0)"),
 300          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 301          "lldf19-r");
 302
 303     tester::apply
 304         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 305          from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0)"),
 306          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 307          "lldf19a");
 308
 309     tester::apply
 310         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 311          from_wkt<L>("LINESTRING(4 0,4 1,20 1,5 0,1 0)"),
 312          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 313          "lldf19a-r");
 314
 315     tester::apply
 316         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 317          from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0)"),
 318          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 319          "lldf19b");
 320
 321     tester::apply
 322         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 323          from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0,6 1)"),
 324          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 325          "lldf19c");
 326
 327     tester::apply
 328         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 329          from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,3 0)"),
 330          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 331          "lldf19d");
 332
 333     tester::apply
 334         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 335          from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,3 0,3 1)"),
 336          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 337          "lldf19e");
 338
 339     tester::apply
 340         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 341          from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0,5 1)"),
 342          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 343          "lldf19f");
 344
 345     tester::apply
 346         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 347          from_wkt<L>("LINESTRING(5 1,5 0,4 0,4 1,20 1,5 0,1 0)"),
 348          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 349          "lldf19f-r");
 350
 351     tester::apply
 352         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 353          from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,5 0,5 1)"),
 354          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 355          "lldf19g");
 356
 357     tester::apply
 358         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 359          from_wkt<L>("LINESTRING(5 1,5 0,4 1,20 1,5 0,1 0)"),
 360          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,30 0))"),
 361          "lldf19g-r");
 362
 363     tester::apply
 364         (from_wkt<L>("LINESTRING(0 0,30 0,30 30,10 30,10 -10,15 0,40 0)"),
 365          from_wkt<L>("LINESTRING(5 5,10 0,10 30,20 0,25 0,25 25,50 0,35 0)"),
 366          from_wkt<ML>("MULTILINESTRING((0 0,20 0),(25 0,30 0,30 30,10 30),\
 367                        (10 0,10 -10,15 0,20 0),(25 0,35 0))"),
 368          "lldf20");
 369
 370     tester::apply
 371         (from_wkt<L>("LINESTRING(0 0,30 0,30 30,10 30,10 -10,15 0,40 0)"),
 372          from_wkt<L>("LINESTRING(5 5,10 0,10 30,20 0,25 0,25 25,50 0,15 0)"),
 373          from_wkt<ML>("MULTILINESTRING((0 0,15 0),(30 0,30 30,10 30),\
 374                        (10 0,10 -10,15 0))"),
 375          "lldf20a");
 376
 377     tester::apply
 378         (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"),
 379          from_wkt<L>("LINESTRING(2 2,5 -1,15 2,18 0,20 0)"),
 380          from_wkt<ML>("MULTILINESTRING((0 0,18 0),(20 0,30 0))"),
 381          "lldf21"
 382          );
 383
 384     tester::apply
 385         (from_wkt<L>("LINESTRING(2 2,5 -1,15 2,18 0,20 0)"),
 386          from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"),
 387          from_wkt<ML>("MULTILINESTRING((2 2,5 -1,15 2,18 0))"),
 388          "lldf21a"
 389          );
 390
 391     tester::apply
 392         (from_wkt<L>("LINESTRING(0 0,10 0)"),
 393          from_wkt<L>("LINESTRING(1 0,4 0,2 1,5 1,4 0,8 0)"),
 394          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(8 0,10 0))"),
 395          "lldf22"
 396          );
 397
 398     tester::apply
 399         (from_wkt<L>("LINESTRING(0 0,10 0)"),
 400          from_wkt<L>("LINESTRING(4 0,5 0,5 1,1 1,1 0,4 0)"),
 401          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(5 0,10 0))"),
 402          "lldf23"
 403          );
 404
 405     // the following two tests have been discussed with by Adam
 406     tester::apply
 407         (from_wkt<L>("LINESTRING(1 0,1 1,2 1)"),
 408          from_wkt<L>("LINESTRING(2 1,1 1,1 0)"),
 409          from_wkt<ML>("MULTILINESTRING()"),
 410          "lldf24"
 411          );
 412
 413     tester::apply
 414         (from_wkt<L>("LINESTRING(1 0,1 1,2 1)"),
 415          from_wkt<L>("LINESTRING(1 2,1 1,1 0)"),
 416          from_wkt<ML>("MULTILINESTRING((1 1,2 1))"),
 417          "lldf25"
 418          );
 419
 420     tester::apply
 421         (from_wkt<L>("LINESTRING(6 0,0 0,5 0)"),
 422          from_wkt<L>("LINESTRING(2 0,-10 0)"),
 423          from_wkt<ML>("MULTILINESTRING((6 0,2 0),(2 0,5 0))"),
 424          "lldf27a"
 425          );
 426
 427     tester::apply
 428         (from_wkt<L>("LINESTRING(6 0,0 0,5 0)"),
 429          from_wkt<L>("LINESTRING(2 0,-1 0,-10 0)"),
 430          from_wkt<ML>("MULTILINESTRING((6 0,2 0),(2 0,5 0))"),
 431          "lldf27b"
 432          );
 433
 434     tester::apply
 435         (from_wkt<L>("LINESTRING(6 0,0 0,5 0)"),
 436          from_wkt<L>("LINESTRING(2 0,0 0,-10 0)"),
 437          from_wkt<ML>("MULTILINESTRING((6 0,2 0),(2 0,5 0))"),
 438          "lldf27c"
 439          );
 440
 441     tester::apply
 442         (from_wkt<L>("LINESTRING(2 0,0 0,-10 0)"),
 443          from_wkt<L>("LINESTRING(6 0,0 0,5 0)"),
 444          from_wkt<ML>("MULTILINESTRING((0 0,-10 0))"),
 445          "lldf27d"
 446          );
 447
 448     tester::apply
 449         (from_wkt<L>("LINESTRING(-3 6,-3 0,-3 5)"),
 450          from_wkt<L>("LINESTRING(-3 2,-3 0,-3 -10)"),
 451          from_wkt<ML>("MULTILINESTRING((-3 6,-3 2),(-3 2,-3 5))"),
 452          "lldf28a"
 453          );
 454
 455     tester::apply
 456         (from_wkt<L>("LINESTRING(-3 2,-3 0,-3 -10)"),
 457          from_wkt<L>("LINESTRING(-3 6,-3 0,-3 5)"),
 458          from_wkt<ML>("MULTILINESTRING((-3 0,-3 -10))"),
 459          "lldf28b"
 460          );
 461
 462     tester::apply
 463         (from_wkt<L>("LINESTRING(-3 6,-3 0,-3 5)"),
 464          from_wkt<L>("LINESTRING(-3 2,-3 0,-3 -10)"),
 465          from_wkt<ML>("MULTILINESTRING((-3 6,-3 2),(-3 2,-3 5))"),
 466          "lldf28c"
 467          );
 468
 469     tester::apply
 470         (from_wkt<L>("LINESTRING(-7 -8,3 0,4 -1)"),
 471          from_wkt<L>("LINESTRING(-5 -4,3 0,4 -1,7 -4)"),
 472          from_wkt<ML>("MULTILINESTRING((-7 -8,3 0))"),
 473          "lldf29a"
 474          );
 475
 476     tester::apply
 477         (from_wkt<L>("LINESTRING(-7 -8,3 0,4 -1,-7 10)"),
 478          from_wkt<L>("LINESTRING(-5 -4,3 0,4 -1,2 -1)"),
 479          from_wkt<ML>("MULTILINESTRING((-7 -8,3 0),(3 0,-7 10))"),
 480          "lldf29b"
 481          );
 482
 483     tester::apply
 484         (from_wkt<L>("LINESTRING(-7 -8,3 0,4 -1,-7 10)"),
 485          from_wkt<L>("LINESTRING(-5 -4,3 0,4 -1,7 -4,2 -1)"),
 486          from_wkt<ML>("MULTILINESTRING((-7 -8,3 0),(3 0,-7 10))"),
 487          "lldf29c"
 488          );
 489
 490     tester::apply
 491         (from_wkt<L>("LINESTRING(-5 -4,3 0,4 -1,7 -4,2 -1)"),
 492          from_wkt<L>("LINESTRING(-7 -8,3 0,4 -1,-7 10)"),
 493          from_wkt<ML>("MULTILINESTRING((-5 -4,3 0),(4 -1,7 -4,2 -1))"),
 494          "lldf29c-r"
 495          );
 496
 497     tester::apply
 498         (from_wkt<L>("LINESTRING(-2 -2,-4 0,1 -8,-2 6,8 5,-7 -8,\
 499                      3 0,4 -1,-7 10,-4 10)"),
 500          from_wkt<L>("LINESTRING(-5 -4,3 0,4 -1,7 -4,2 -1,-4 -1,-2 6)"),
 501          from_wkt<ML>("MULTILINESTRING((-2 -2,-4 0,1 -8,-2 6,8 5,-7 -8,\
 502                       3 0),(3 0,-7 10,-4 10))"),
 503          "lldf29d"
 504          );
 505
 506 #ifdef GEOMETRY_TEST_INCLUDE_FAILING_TESTS
 507      tester::apply
 508          (from_wkt<L>("LINESTRING(8 5,5 1,-2 3,1 10)"),
 509           from_wkt<L>("LINESTRING(1.9375 1.875,\
 510                       1.7441860465116283 1.9302325581395348,\
 511                       -0.7692307692307692 2.6483516483516487,\
 512                       -2 3,-1.0071942446043165 5.316546762589928)"),
 513           from_wkt<ML>("MULTILINESTRING((8 5,5 1,-2 3,1 10))"),
 514           "lldf30a"
 515           );
 516
 517      tester::apply
 518          (from_wkt<L>("LINESTRING(1.9375 1.875,\
 519                       1.7441860465116283 1.9302325581395348,\
 520                       -0.7692307692307692 2.6483516483516487,\
 521                       -2 3,-1.0071942446043165 5.316546762589928)"),
 522           from_wkt<L>("LINESTRING(8 5,5 1,-2 3,1 10)"),
 523           from_wkt<ML>("MULTILINESTRING((1.9375 1.875,\
 524                        1.7441860465116283 1.9302325581395348,\
 525                        -0.7692307692307692 2.6483516483516487,\
 526                        -2 3,-1.0071942446043165 5.316546762589928))"),
 527           "lldf30b"
 528           );
 529
 530    tester::apply
 531         (from_wkt<L>("LINESTRING(5 -8,-7 -6,-3 6,-3 1,-5 4,-1 0,8 5,\
 532                      5 1,-2 3,1 10,8 5,6 2,7 4)"),
 533          from_wkt<L>("LINESTRING(1.9375 1.875,\
 534                      1.7441860465116283 1.9302325581395348,\
 535                      -0.7692307692307692 2.6483516483516487,\
 536                      -2 3,-1.0071942446043165 5.316546762589928)"),
 537          from_wkt<ML>("MULTILINESTRING((5 -8,-7 -6,-3 6,-3 1,-5 4,-1 0,8 5,\
 538                       5 1,-2 3,1 10,8 5,6 2,7 4))"),
 539
 540          "lldf30c"
 541          );
 542 #endif
 543
 544     tester::apply
 545         (from_wkt<L>("LINESTRING(8 1, 4 .4)"),
 546          from_wkt<L>("LINESTRING(0 -.2, 8 1)"),
 547          from_wkt<ML>("MULTILINESTRING()"),
 548          "lldf31s"
 549          );
 550
 551     tester::apply
 552         (from_wkt<L>("LINESTRING(8 1, 4 .4,2 8)"),
 553          from_wkt<L>("LINESTRING(0 -.2, 8 1)"),
 554          from_wkt<ML>("MULTILINESTRING((4 .4,2 8))"),
 555          "lldf31x",
 556          1e-10
 557          );
 558
 559     tester::apply
 560         (from_wkt<L>("LINESTRING(2 8,4 .4,8 1)"),
 561          from_wkt<L>("LINESTRING(0 -.2, 8 1)"),
 562          from_wkt<ML>("MULTILINESTRING((2 8,4 .4))"),
 563          "lldf31x-r",
 564          1e-10
 565          );
 566
 567     tester::apply
 568         (from_wkt<L>("LINESTRING(0 5, 8 1, 4 .4, 2 8)"),
 569          from_wkt<L>("LINESTRING(0 -.2, 8 1, -.5 7)"),
 570          from_wkt<ML>("MULTILINESTRING((0 5,8 1),(4 .4,2 8))"),
 571          "lldf31y",
 572          1e-10
 573          );
 574
 575     tester::apply
 576         (from_wkt<L>("LINESTRING(0 -.2, 8 1, -.5 7)"),
 577          from_wkt<L>("LINESTRING(0 5, 8 1, 4 .4, 2 8)"),
 578          from_wkt<ML>("MULTILINESTRING((0 -.2,4 .4),(8 1,-.5 7))"),
 579          "lldf31y-r",
 580          1e-10
 581          );
 582
 583     tester::apply
 584         (from_wkt<L>("LINESTRING(0 5, 8 1, 4 .4, 2 8)"),
 585          from_wkt<L>("LINESTRING(0 -.2, 8 1, -.5 7, 6 +.2)"),
 586          from_wkt<ML>("MULTILINESTRING((0 5,8 1),(4 .4,2 8))"),
 587          "lldf31y+",
 588          1e-10
 589          );
 590
 591     tester::apply
 592         (from_wkt<L>("LINESTRING(10.0002 2,9 -1032.34324, .3 8, 0 5, 8 1, 4 .4, 2 8)"),
 593          from_wkt<L>("LINESTRING(0 -.2, 8 1, -.5 7, 6 +.2)"),
 594          from_wkt<ML>("MULTILINESTRING((10.0002 2,9 -1032.34324,.3 8,0 5,8 1),(4 .4,2 8))"),
 595          "lldf31z",
 596          1e-10
 597          );
 598
 599     tester::apply
 600         (from_wkt<L>("LINESTRING(0 -.2, 8 1, -.5 7, 6 +.2)"),
 601          from_wkt<L>("LINESTRING(10.0002 2,9 -1032.34324, .3 8, 0 5, 8 1, 4 .4, 2 8)"),
 602          from_wkt<ML>("MULTILINESTRING((0 -.2,4 .4),(8 1,-.5 7,6 .2))"),
 603          "lldf31z-r",
 604          1e-10
 605          );
 606
 607     tester::apply
 608         (from_wkt<L>("LINESTRING(0 0, 8 1, -.5 7)"),
 609          from_wkt<L>("LINESTRING(0 5, 8 1, 4 .5, 2 8)"),
 610          from_wkt<ML>("MULTILINESTRING((0 0,4 .5),(8 1,-.5 7))"),
 611          "lldf32"
 612          );
 613 }
 614
 615
 616
 617 BOOST_AUTO_TEST_CASE( test_difference_linestring_multilinestring )
 618 {
 619 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 620     std::cout << std::endl << std::endl << std::endl;
 621     std::cout << "*** LINESTRING / MULTILINESTRING DIFFERENCE ***"
 622               << std::endl;
 623     std::cout << std::endl;
 624 #endif
 625
 626     typedef linestring_type L;
 627     typedef multi_linestring_type ML;
 628
 629     typedef test_difference_of_geometries<L, ML, ML> tester;
 630
 631     // disjoint linestrings
 632     tester::apply
 633         (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"),
 634          from_wkt<ML>("MULTILINESTRING((1 1,2 2,4 3),(1 1,2 2,5 3))"),
 635          from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1))"),
 636          "lmldf01"
 637         );
 638
 639     tester::apply
 640         (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"),
 641          from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,4 0))"),
 642          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(4 0,10 0,20 1))"),
 643          "lmldf02"
 644         );
 645
 646     tester::apply
 647         (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"),
 648          from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,5 0))"),
 649          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(5 0,10 0,20 1))"),
 650          "lmldf03"
 651         );
 652
 653     tester::apply
 654         (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"),
 655          from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0))"),
 656          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(4 0,10 0,20 1))"),
 657          "lmldf04"
 658         );
 659
 660     tester::apply
 661         (from_wkt<L>("LINESTRING(0 0,101 0)"),
 662          from_wkt<ML>("MULTILINESTRING((-1 -1,1 0,101 0,200 -1))"),
 663          from_wkt<ML>("MULTILINESTRING((0 0,1 0))"),
 664          "lmldf07"
 665         );
 666
 667     tester::apply
 668         (from_wkt<L>("LINESTRING(-1 1,0 0,101 0)"),
 669          from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\
 670                       (19 -1,20 0,101 0,200 -1))"),
 671          from_wkt<ML>("MULTILINESTRING((-1 1,0 0))"),
 672          "lmldf07a"
 673         );
 674
 675     tester::apply
 676         (from_wkt<L>("LINESTRING(0 0,101 0)"),
 677          from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\
 678                       (19 -1,20 0,101 0,200 -1))"),
 679          from_wkt<ML>("MULTILINESTRING()"),
 680          "lmldf07b"
 681         );
 682
 683     tester::apply
 684         (from_wkt<L>("LINESTRING(0 0,101 0)"),
 685          from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0),\
 686                        (-1 -1,1 0,101 0,200 -1))"),
 687          from_wkt<ML>("MULTILINESTRING((0 0,1 0))"),
 688          "lmldf08"
 689         );
 690
 691     tester::apply
 692         (from_wkt<L>("LINESTRING(0 0,1 0,2 0.5,3 0,101 0)"),
 693          from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0.5),\
 694                        (-1 -1,1 0,101 0,200 -1))"),
 695          from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0.5,3 0))"),
 696          "lmldf09"
 697         );
 698
 699     tester::apply
 700         (from_wkt<L>("LINESTRING(0 0,1 0,1.5 0,2 0.5,3 0,101 0)"),
 701          from_wkt<ML>("MULTILINESTRING((0 1,1 1,1 0,2 0.5),\
 702                        (-1 -1,1 0,101 0,200 -1))"),
 703          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(1.5 0,2 0.5,3 0))"),
 704          "lmldf10"
 705         );
 706
 707     tester::apply
 708         (from_wkt<L>("LINESTRING(0 0,20 0)"),
 709          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 710                       (1 1,2 0,18 0,19 1),(2 1,3 0,17 0,18 1),\
 711                       (3 1,4 0,16 0,17 1))"),
 712          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
 713          "lmldf12"
 714          );
 715
 716     tester::apply
 717         (from_wkt<L>("LINESTRING(0 0,20 0)"),
 718          from_wkt<ML>("MULTILINESTRING((1 0,19 0,20 1),\
 719                       (2 0,18 0,19 1),(3 0,17 0,18 1),\
 720                       (4 0,16 0,17 1))"),
 721          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
 722          "lmldf13"
 723          );
 724
 725     tester::apply
 726         (from_wkt<L>("LINESTRING(0 0,20 0)"),
 727          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1,19 1,18 0,2 0,\
 728                        1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1))"),
 729          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
 730          "lmldf14"
 731          );
 732
 733     tester::apply
 734         (from_wkt<L>("LINESTRING(0 0,20 0)"),
 735          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 736                        (2 2,4 2,6 0))"),
 737          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
 738          "lmldf15"
 739          );
 740
 741     tester::apply
 742         (from_wkt<L>("LINESTRING(0 0,20 0)"),
 743          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 744                        (6 0,4 2,2 2))"),
 745          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
 746          "lmldf15a"
 747          );
 748
 749     tester::apply
 750         (from_wkt<L>("LINESTRING(0 0,20 0)"),
 751          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 752                        (2 2,4 2,5 0,6 0))"),
 753          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
 754          "lmldf16"
 755          );
 756
 757     tester::apply
 758         (from_wkt<L>("LINESTRING(0 0,20 0)"),
 759          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 760                        (6 0,5 0,4 2,2 2))"),
 761          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
 762          "lmldf16a"
 763          );
 764
 765     tester::apply
 766         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 767          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 768                        (2 2,4 0,5 2,20 2,25 0))"),
 769          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,30 0))"),
 770          "lmldf17"
 771          );
 772
 773     tester::apply
 774         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 775          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 776                        (2 2,4 0,5 2,20 2,25 0,26 2))"),
 777          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,30 0))"),
 778          "lmldf17a"
 779          );
 780
 781     tester::apply
 782         (from_wkt<L>("LINESTRING(0 0,30 0)"),
 783          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 784                        (2 2,5 -1,15 2,18 0))"),
 785          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,30 0))"),
 786          "lmldf18"
 787          );
 788
 789     tester::apply
 790         (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"),
 791          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 792                        (2 2,5 -1,15 2,18 0))"),
 793          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,30 0))"),
 794          "lmldf18a"
 795          );
 796
 797     tester::apply
 798         (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"),
 799          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 800                        (2 2,5 -1,15 2,18 0,20 0))"),
 801          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(20 0,30 0))"),
 802          "lmldf18b"
 803          );
 804
 805     tester::apply
 806         (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"),
 807          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 808                        (2 2,5 -1,15 2,25 0,26 0))"),
 809          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,25 0),(26 0,30 0))"),
 810          "lmldf18c"
 811          );
 812
 813     tester::apply
 814         (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"),
 815          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
 816                        (2 2,5 -1,15 2,25 0,21 0))"),
 817          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,21 0),(25 0,30 0))"),
 818          "lmldf18d"
 819          );
 820
 821     tester::apply
 822         (from_wkt<L>("LINESTRING(0 0,10 0)"),
 823          from_wkt<ML>("MULTILINESTRING((0 5,1 0,9 0,10 5),(0 1,2 0,3 1),\
 824                       (0 -2,3 0,4 4),(0 -5,4 0,5 0,6 3))"),
 825          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10))"),
 826          "lmldf19"
 827          );
 828
 829     tester::apply
 830         (from_wkt<L>("LINESTRING(0 0,10 0)"),
 831          from_wkt<ML>("MULTILINESTRING((-1 0,0 0),(10 0,12 0))"),
 832          from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
 833          "lmldf20"
 834          );
 835 }
 836
 837
 838
 839
 840
 841 BOOST_AUTO_TEST_CASE( test_difference_multilinestring_linestring )
 842 {
 843 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 844     std::cout << std::endl << std::endl << std::endl;
 845     std::cout << "*** MULTILINESTRING / LINESTRING DIFFERENCE ***"
 846               << std::endl;
 847     std::cout << std::endl;
 848 #endif
 849
 850     typedef linestring_type L;
 851     typedef multi_linestring_type ML;
 852
 853     typedef test_difference_of_geometries<ML, L, ML> tester;
 854
 855     // disjoint linestrings
 856     tester::apply
 857         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
 858          from_wkt<L>("LINESTRING(1 1,2 2,4 3)"),
 859          from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
 860          "mlldf01"
 861         );
 862
 863     tester::apply
 864         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
 865          from_wkt<L>("LINESTRING(1 1,2 0,4 0)"),
 866          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(4 0,10 0,20 1),\
 867                       (1 0,2 0),(4 0,7 0))"),
 868          "mlldf02"
 869         );
 870
 871     tester::apply
 872         (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
 873          from_wkt<L>("LINESTRING(-1 -1,1 0,101 0,200 -1)"),
 874          from_wkt<ML>("MULTILINESTRING((0 0,1 0))"),
 875          "mlldf03"
 876         );
 877
 878     tester::apply
 879         (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
 880          from_wkt<L>("LINESTRING(0 1,1 0,19 0,20 1,19 1,18 0,2 0,\
 881                        1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1)"),
 882          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
 883          "mlldf04"
 884          );
 885
 886     tester::apply
 887         (from_wkt<ML>("MULTILINESTRING((-1 0,-1 10),(0 0,20 0),(25 0,30 0))"),
 888          from_wkt<L>("LINESTRING(0 1,1 0,19 0,20 1,19 1,18 0,2 0,\
 889                        1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1)"),
 890          from_wkt<ML>("MULTILINESTRING((-1 0,-1 10),(0 0,1 0),(19 0,20 0),(25 0,30 0))"),
 891          "mlldf05"
 892          );
 893
 894     tester::apply
 895         (from_wkt<ML>("MULTILINESTRING((-3 2,-3 0,-3 -10))"),
 896          from_wkt<L>("LINESTRING(-3 6,-3 0,-3 5)"),
 897          from_wkt<ML>("MULTILINESTRING((-3 0,-3 -10))"),
 898          "mlldf06a"
 899          );
 900
 901     tester::apply
 902         (from_wkt<ML>("MULTILINESTRING((6 6,-3 2,-3 0,-3 -10,9 -2))"),
 903          from_wkt<L>("LINESTRING(-3 6,-3 0,-3 5,2 -3,-6 10,5 0,2 8,\
 904                      -6 1,10 -6)"),
 905          from_wkt<ML>("MULTILINESTRING((6 6,-3 2),(-3 0,-3 -10,9 -2))"),
 906          "mlldf06b"
 907          );
 908
 909     tester::apply
 910         (from_wkt<ML>("MULTILINESTRING((0 -3,5 4,6 6,-3 2,-3 0,-3 -10,\
 911                       9 -2,9 5,5 -5,-4 -8,9 0))"),
 912          from_wkt<L>("LINESTRING(-3 6,-3 0,-3 5,2 -3,-6 10,5 0,2 8,\
 913                      -6 1,10 -6)"),
 914          from_wkt<ML>("MULTILINESTRING((0 -3,5 4,6 6,-3 2),\
 915                       (-3 0,-3 -10,9 -2,9 5,5 -5,-4 -8,9 0))"),
 916          "mlldf06c"
 917          );
 918 }
 919
 920
 921
 922
 923
 924
 925
 926 BOOST_AUTO_TEST_CASE( test_difference_multilinestring_multilinestring )
 927 {
 928 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 929     std::cout << std::endl << std::endl << std::endl;
 930     std::cout << "*** MULTILINESTRING / MULTILINESTRING DIFFERENCE ***"
 931               << std::endl;
 932     std::cout << std::endl;
 933 #endif
 934
 935     typedef multi_linestring_type ML;
 936
 937     typedef test_difference_of_geometries<ML, ML, ML> tester;
 938
 939     // disjoint linestrings
 940     tester::apply
 941         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
 942          from_wkt<ML>("MULTILINESTRING((1 1,2 2,4 3),(1 1,2 2,5 3))"),
 943          from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
 944          "mlmldf01"
 945         );
 946
 947     tester::apply
 948         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
 949          from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,4 0))"),
 950          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(4 0,10 0,20 1),\
 951                       (1 0,2 0),(4 0,7 0))"),
 952          "mlmldf02"
 953         );
 954
 955     tester::apply
 956         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
 957          from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,5 0))"),
 958          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(5 0,10 0,20 1),\
 959                       (1 0,2 0),(5 0,7 0))"),
 960          "mlmldf03"
 961         );
 962
 963     tester::apply
 964         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
 965          from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0))"),
 966          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(4 0,10 0,20 1),\
 967                       (1 0,2 0),(4 0,7 0))"),
 968          "mlmldf04"
 969         );
 970
 971     tester::apply
 972         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0),\
 973                        (10 10,20 10,30 20))"),
 974          from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),\
 975                        (10 20,15 10,25 10,30 15))"),
 976          from_wkt<ML>("MULTILINESTRING((0 0,2 0),(4 0,10 0,20 1),\
 977                       (1 0,2 0),(4 0,7 0),(10 10,15 10),(20 10,30 20))"),
 978          "mlmldf05"
 979         );
 980
 981     tester::apply
 982         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 10),(1 0,7 0),\
 983                        (10 10,20 10,30 20))"),
 984          from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),\
 985                        (-1 -1,0 0,9 0,11 10,12 10,13 3,14 4,15 5),\
 986                        (10 20,15 10,25 10,30 15))"),
 987          from_wkt<ML>("MULTILINESTRING((9 0,10 0,13 3),(15 5,20 10),\
 988                       (10 10,11 10),(12 10,15 10),(20 10,30 20))"),
 989          "mlmldf06"
 990         );
 991
 992     tester::apply
 993         (from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),\
 994                       (-1 -1,0 0,9 0,11 10,12 10,13 3,14 4,15 5),\
 995                       (10 20,15 10,25 10,30 15))"),
 996          from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 10),(1 0,7 0),\
 997                       (10 10,20 10,30 20))"),
 998          from_wkt<ML>("MULTILINESTRING((1 1,2 0),(-1 -1,0 0),(9 0,11 10),\
 999                       (12 10,13 3),(10 20,15 10),(20 10,25 10,30 15))"),
1000          "mlmldf06a"
1001         );
1002
1003     tester::apply
1004         (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
1005          from_wkt<ML>("MULTILINESTRING((-1 -1,1 0,101 0,200 -1))"),
1006          from_wkt<ML>("MULTILINESTRING((0 0,1 0))"),
1007          "mlmldf07"
1008         );
1009
1010     tester::apply
1011         (from_wkt<ML>("MULTILINESTRING((-1 1,0 0,101 0))"),
1012          from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\
1013                       (19 -1,20 0,101 0,200 -1))"),
1014          from_wkt<ML>("MULTILINESTRING((-1 1,0 0))"),
1015          "mlmldf07a"
1016         );
1017
1018     tester::apply
1019         (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
1020          from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\
1021                       (19 -1,20 0,101 0,200 -1))"),
1022          from_wkt<ML>("MULTILINESTRING()"),
1023          "mlmldf07b"
1024         );
1025
1026     tester::apply
1027         (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
1028          from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0),\
1029                        (-1 -1,1 0,101 0,200 -1))"),
1030          from_wkt<ML>("MULTILINESTRING((0 0,1 0))"),
1031          "mlmldf08"
1032         );
1033
1034     tester::apply
1035         (from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0.5,3 0,101 0))"),
1036          from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0.5),\
1037                        (-1 -1,1 0,101 0,200 -1))"),
1038          from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0.5,3 0))"),
1039          "mlmldf09"
1040         );
1041
1042     tester::apply
1043         (from_wkt<ML>("MULTILINESTRING((0 0,1 0,1.5 0,2 0.5,3 0,101 0))"),
1044          from_wkt<ML>("MULTILINESTRING((0 1,1 1,1 0,2 0.5),\
1045                        (-1 -1,1 0,101 0,200 -1))"),
1046          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(1.5 0,2 0.5,3 0))"),
1047          "mlmldf10"
1048         );
1049
1050     tester::apply
1051         (from_wkt<ML>("MULTILINESTRING((0 0,1 1,100 1,101 0),\
1052                        (0 0,101 0))"),
1053          from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1,3 0,4 0,5 1,6 1,\
1054                        7 0,8 0,9 1,10 1,11 0,12 0,13 1,14 1,15 0),\
1055                        (-1 -1,1 0,101 0,200 -1))"),
1056          from_wkt<ML>("MULTILINESTRING((0 0,1 1),(2 1,5 1),(6 1,9 1),\
1057                        (10 1,13 1),(14 1,100 1,101 0),(0 0,1 0))"),
1058          "mlmldf11"
1059         );
1060
1061     tester::apply
1062         (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1063          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1064                       (1 1,2 0,18 0,19 1),(2 1,3 0,17 0,18 1),\
1065                       (3 1,4 0,16 0,17 1))"),
1066          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
1067          "mlmldf12"
1068          );
1069
1070     tester::apply
1071         (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1072          from_wkt<ML>("MULTILINESTRING((1 0,19 0,20 1),\
1073                       (2 0,18 0,19 1),(3 0,17 0,18 1),\
1074                       (4 0,16 0,17 1))"),
1075          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
1076          "mlmldf13"
1077          );
1078
1079     tester::apply
1080         (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1081          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1,19 1,18 0,2 0,\
1082                        1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1))"),
1083          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
1084          "mlmldf14"
1085          );
1086
1087     tester::apply
1088         (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1089          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1090                        (2 2,4 2,6 0))"),
1091          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
1092          "mlmldf15"
1093          );
1094
1095     tester::apply
1096         (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1097          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1098                        (6 0,4 2,2 2))"),
1099          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
1100          "mlmldf15a"
1101          );
1102
1103     tester::apply
1104         (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1105          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1106                        (2 2,4 2,5 0,6 0))"),
1107          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
1108          "mlmldf16"
1109          );
1110
1111     tester::apply
1112         (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1113          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1114                        (6 0,5 0,4 2,2 2))"),
1115          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,20 0))"),
1116          "mlmldf16a"
1117          );
1118
1119     tester::apply
1120         (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"),
1121          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1122                        (2 2,4 0,5 2,20 2,25 0))"),
1123          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,30 0))"),
1124          "mlmldf17"
1125          );
1126
1127     tester::apply
1128         (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"),
1129          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1130                        (2 2,4 0,5 2,20 2,25 0,26 2))"),
1131          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,30 0))"),
1132          "mlmldf17a"
1133          );
1134
1135     tester::apply
1136         (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"),
1137          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1138                        (2 2,5 -1,15 2,18 0))"),
1139          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,30 0))"),
1140          "mlmldf18"
1141          );
1142
1143     tester::apply
1144         (from_wkt<ML>("MULTILINESTRING((0 0,18 0,19 0,30 0))"),
1145          from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1146                        (2 2,5 -1,15 2,18 0))"),
1147          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(19 0,30 0))"),
1148          "mlmldf18a"
1149          );
1150
1151     tester::apply
1152         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1153          from_wkt<ML>("MULTILINESTRING((-1 0,0 0),(10 0,12 0))"),
1154          from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1155          "mlmldf19"
1156          );
1157
1158     tester::apply
1159         (from_wkt<ML>("MULTILINESTRING((1 5, -4.3 -.1), (0 6, 8.6 6, 189.7654 5, 1 3, 6 3, 3 5, 6 2.232432, 0 4), (-6 5, 1 2.232432), (3 -1032.34324, 9 0, 189.7654 1, -1.4 3, 3 189.7654, +.3 10.0002, 1 5, 6 3, 5 1, 9 1, 10.0002 -1032.34324, -0.7654 0, 5 3, 3 4), (2.232432 2.232432, 8.6 +.4, 0.0 2.232432, 4 0, -8.8 10.0002), (1 0, 6 6, 7 2, -0 8.4), (-0.7654 3, +.6 8, 4 -1032.34324, 1 6, 0 4), (0 7, 2 1, 8 -7, 7 -.7, -1032.34324 9), (5 0, 10.0002 4, 8 7, 3 3, -8.1 5))"),
1160          from_wkt<ML>("MULTILINESTRING((5 10.0002, 2 7, -0.7654 0, 5 3), (0 -0.7654, 4 10.0002, 4 +.1, -.8 3, -.1 8, 10.0002 2, +.9 -1032.34324))"),
1161          from_wkt<ML>("MULTILINESTRING((1 5,-4.3 -0.1),(0 6,8.6 6,189.7654 5,1 3,6 3,3 5,6 2.232432,0 4),(-6 5,1 2.232432),(5 3,3 4),(3 -1032.34324,9 0,189.7654 1,-1.4 3,3 189.7654,0.3 10.0002,1 5,6 3,5 1,9 1,10.0002 -1032.34324,-0.7654 0),(2.232432 2.232432,8.6 0.4,0 2.232432,4 0,-8.8 10.0002),(1 0,6 6,7 2,-0 8.4),(-0.7654 3,0.6 8,4 -1032.34324,1 6,0 4),(0 7,2 1,8 -7,7 -0.7,-1032.34324 9),(5 0,10.0002 4,8 7,3 3,-8.1 5))"),
1162          "mlmldf24",
1163          1e-10
1164          );
1165
1166     tester::apply
1167         (from_wkt<ML>("MULTILINESTRING((5 10.0002, 2 7, -0.7654 0, 5 3), (0 -0.7654, 4 10.0002, 4 +.1, -.8 3, -.1 8, 10.0002 2, +.9 -1032.34324))"),
1168          from_wkt<ML>("MULTILINESTRING((1 5, -4.3 -.1), (0 6, 8.6 6, 189.7654 5, 1 3, 6 3, 3 5, 6 2.232432, 0 4), (-6 5, 1 2.232432), (3 -1032.34324, 9 0, 189.7654 1, -1.4 3, 3 189.7654, +.3 10.0002, 1 5, 6 3, 5 1, 9 1, 10.0002 -1032.34324, -0.7654 0, 5 3, 3 4), (2.232432 2.232432, 8.6 +.4, 0.0 2.232432, 4 0, -8.8 10.0002), (1 0, 6 6, 7 2, -0 8.4), (-0.7654 3, +.6 8, 4 -1032.34324, 1 6, 0 4), (0 7, 2 1, 8 -7, 7 -.7, -1032.34324 9), (5 0, 10.0002 4, 8 7, 3 3, -8.1 5))"),
1169          from_wkt<ML>("MULTILINESTRING((5 10.0002,2 7,-0.7654 8.88178e-16),(0 -0.7654,4 10.0002,4 0.1,-0.8 3,-0.1 8,10.0002 2,0.9 -1032.34324))"),
1170          "mlmldf24-r",
1171          1e-10
1172          );
1173
1174     tester::apply
1175         (from_wkt<ML>("MULTILINESTRING((-.4 2, 2.232432 3, 6 9, 8 189.7654, -1032.34324 5.4, 2.232432 9), (-1032.34324 3, 8 -1.6), (0 -.2, 8 1, -.5 7, 6 +.2))"),
1176          from_wkt<ML>("MULTILINESTRING((-8 1, 4.8 6, 2 +.5), (10.0002 2,9 -1032.34324, .3 8, 0 5, 8 1, 4 .4, 2 8), (6 7, +.1 7, 0 -.5))"),
1177          from_wkt<ML>("MULTILINESTRING((-0.4 2,2.232432 3,6 9,8 189.7654,-1032.34324 5.4,2.232432 9),(-1032.34324 3,8 -1.6),(0 -0.2,4 0.4),(8 1,-0.5 7,6 0.2))"),
1178          "mlmldf25",
1179          1e-10
1180          );
1181
1182     tester::apply
1183         (from_wkt<ML>("MULTILINESTRING((-8 1, 4.8 6, 2 +.5), (10.0002 2,9 -1032.34324, .3 8, 0 5, 8 1, 4 .4, 2 8), (6 7, +.1 7, 0 -.5))"),
1184          from_wkt<ML>("MULTILINESTRING((-.4 2, 2.232432 3, 6 9, 8 189.7654, -1032.34324 5.4, 2.232432 9), (-1032.34324 3, 8 -1.6), (0 -.2, 8 1, -.5 7, 6 +.2))"),
1185          from_wkt<ML>("MULTILINESTRING((-8 1,4.8 6,2 0.5),(10.0002 2,9 -1032.34324,0.3 8,0 5,8 1),(4 0.4,2 8),(6 7,0.1 7,0 -0.5))"),
1186          "mlmldf25-r",
1187          1e-10
1188          );
1189
1190     {
1191         std::string wkt1 = "MULTILINESTRING((0 -18,17 -9,8.422018348623853 -6.477064220183486),(4.0893470790378 -5.202749140893471,0 -4,6.049382716049383 -7.4567901234567895),(9.21951219512195 -9.26829268292683,14 -12),(-7 3,-5.903614457831325 6.289156626506024),(-5.277777777777778 8.166666666666668,-5 9,-5.445859872611465 8.26751592356688),(-6.342710997442455 6.794117647058823,-19 -14,-6.2338779019776425 6.668959587274291),(-5.3004291845493565 8.180257510729614,-3.579710144927536 10.966183574879228),(-3.390625 11.272321428571429,2 20),(20 -19,14 -3,3.258064516129032 1.774193548387096),(-5.275590551181104 5.5669291338582685,-13 9,-8.678414096916299 9.480176211453745),(-7.65625 9.59375,-4 10),(-2 -4,-0.15873015873015883 -0.31746031746031766),(1.875 3.75,9 18,6 8,13 17),(12 -11,6 4))";
1192
1193         std::string wkt2 = "MULTILINESTRING((1 16,-16 18),(17 10,15 4),(0 -14,-7 3),(-16 3,-6.471885336273427 6.942668136714442),(-4.557823129251701 7.73469387755102,-2.220994475138122 8.701657458563536),(-1.7326203208556137 8.90374331550802,13 15,15 -16,11 -11),(-6 11,-4.285714285714287 7.571428571428573),(-0.5882352941176467 0.1764705882352935,4 -9,-4 -8,-4 4.1),(-4 7.4,-4 11.666666666666666),(-4 12.142857142857142,-4 19),(-17 -1,-3.5989717223650377 3.638817480719794),(0.8699690402476783 5.185758513931889,9 8),(18 10,2.814814814814815 2.4074074074074057),(-0.9090909090909101 0.545454545454545,-4 -1,-3 -16,1.272141706924316 -1.9629629629629637),(2.666666666666667 2.6190476190476204,4 7),(-1 18,11 -6))";
1194
1195         std::string wkt_out = "MULTILINESTRING((0 -18,17 -9,8.4220183486238529 -6.47706422018348604),(4.08934707903780037 -5.20274914089347096,0 -4,6.04938271604938294 -7.45679012345678949),(9.21951219512195053 -9.26829268292683039,14 -12),(-7 3,-5.90361445783132499 6.28915662650602414),(-5.27777777777777768 8.16666666666666785,-5 9,-5.44585987261146531 8.26751592356687937),(-6.34271099744245515 6.79411764705882337,-19 -14,-6.23387790197764247 6.66895958727429061),(-5.30042918454935652 8.18025751072961427,-3.57971014492753614 10.9661835748792278),(-3.390625 11.2723214285714288,2 20),(20 -19,14 -3,3.25806451612903203 1.77419354838709609),(-5.27559055118110365 5.56692913385826849,-13 9,-8.67841409691629906 9.48017621145374534),(-7.65625 9.59375,-4 10),(-2 -4,-0.158730158730158832 -0.317460317460317665),(1.875 3.75,9 18,6 8,13 17),(12 -11,6 4))";
1196
1197         ML mls1, mls2, mls_out;
1198         bg::read_wkt(wkt1, mls1);
1199         bg::read_wkt(wkt2, mls2);
1200         bg::read_wkt(wkt_out, mls_out);
1201
1202         tester::apply(mls1, mls2, mls_out, "mlmldf26", 1e-10);
1203     }
1204     {
1205         std::string wkt1 = "MULTILINESTRING((12 -11,6 4))";
1206         std::string wkt2 = "MULTILINESTRING((18 10,2.814814814814815 2.4074074074074057),(-1 18,11 -6))";
1207
1208         std::string wkt_out = "MULTILINESTRING((12 -11,6 4))";
1209
1210         ML mls1, mls2, mls_out;
1211         bg::read_wkt(wkt1, mls1);
1212         bg::read_wkt(wkt2, mls2);
1213         bg::read_wkt(wkt_out, mls_out);
1214
1215         tester::apply(mls1, mls2, mls_out, "mlmldf27");
1216     }
1217 }
1218
1219
1220
1221
1222
1223
1224 #ifndef BOOST_GEOMETRY_TEST_NO_DEGENERATE
1225 BOOST_AUTO_TEST_CASE( test_difference_ml_ml_degenerate )
1226 {
1227 #ifdef BOOST_GEOMETRY_TEST_DEBUG
1228     std::cout << std::endl << std::endl << std::endl;
1229     std::cout << "*** MULTILINESTRING / MULTILINESTRING DIFFERENCE"
1230               << " (DEGENERATE) ***"
1231               << std::endl;
1232     std::cout << std::endl;
1233 #endif
1234
1235     typedef multi_linestring_type ML;
1236
1237     typedef test_difference_of_geometries<ML, ML, ML> tester;
1238
1239     // the following test cases concern linestrings with duplicate
1240     // points and possibly linestrings with zero length.
1241
1242     tester::apply
1243         (from_wkt<ML>("MULTILINESTRING((5 5,5 5),(0 0,18 0,18 0,\
1244                       19 0,19 0,19 0,30 0),(2 0,2 0),(4 10,4 10))"),
1245          from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1246                       (1 1,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1247                       (2 0,2 0),(3 0,3 0,3 0),(0 0,0 10),\
1248                       (4 0,4 10),(5 5,5 5))"),
1249          from_wkt<ML>("MULTILINESTRING((0 0,5 0),(20 0,30 0))"),
1250          "mlmldf20a"
1251          );
1252
1253     tester::apply
1254         (from_wkt<ML>("MULTILINESTRING((5 5,5 5),(0 0,0 0,18 0,18 0,\
1255                       19 0,19 0,19 0,30 0,30 0),(2 0,2 0),(4 10,4 10))"),
1256          from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1257                       (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1258                       (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
1259                       (4 0,4 10,4 10),(5 5,5 5))"),
1260          from_wkt<ML>("MULTILINESTRING((0 0,5 0),(20 0,30 0))"),
1261          "mlmldf20aa"
1262          );
1263
1264     tester::apply
1265         (from_wkt<ML>("MULTILINESTRING((10 10,10 10),(0 0,0 0,18 0,18 0,\
1266                       19 0,19 0,19 0,30 0,30 0),(2 0,2 0),(4 10,4 10))"),
1267          from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1268                       (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1269                       (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
1270                       (4 0,4 10,4 10),(5 5,5 5))"),
1271          from_wkt<ML>("MULTILINESTRING((10 10,10 10),(0 0,5 0),(20 0,30 0))"),
1272          "mlmldf20aaa"
1273          );
1274
1275     tester::apply
1276         (from_wkt<ML>("MULTILINESTRING((10 10),(0 0,0 0,18 0,18 0,\
1277                       19 0,19 0,19 0,30 0,30 0),(2 0,2 0),(4 10,4 10))"),
1278          from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1279                       (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1280                       (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
1281                       (4 0,4 10,4 10),(5 5,5 5))"),
1282          from_wkt<ML>("MULTILINESTRING((10 10,10 10),(0 0,5 0),(20 0,30 0))"),
1283          "mlmldf20aaaa"
1284          );
1285
1286     tester::apply
1287         (from_wkt<ML>("MULTILINESTRING((0 0,0 0),(1 1,1 1))"),
1288          from_wkt<ML>("MULTILINESTRING((1 1,1 1))"),
1289          from_wkt<ML>("MULTILINESTRING((0 0,0 0))"),
1290          "mlmldf21"
1291          );
1292
1293     tester::apply
1294         (from_wkt<ML>("MULTILINESTRING((0 0,0 0),(2 2,2 2),(1 1,1 1))"),
1295          from_wkt<ML>("MULTILINESTRING((1 1,1 1))"),
1296          from_wkt<ML>("MULTILINESTRING((0 0,0 0),(2 2,2 2))"),
1297          "mlmldf22"
1298          );
1299
1300     tester::apply
1301         (from_wkt<ML>("MULTILINESTRING((0 0,0 0),(1 1,1 1),(2 2,2 2))"),
1302          from_wkt<ML>("MULTILINESTRING((1 1,1 1))"),
1303          from_wkt<ML>("MULTILINESTRING((0 0,0 0),(2 2,2 2))"),
1304          "mlmldf23"
1305          );
1306 }
1307 #endif // BOOST_GEOMETRY_TEST_NO_DEGENERATE
1308
1309
1310
1311
1312 BOOST_AUTO_TEST_CASE( test_difference_ml_ml_spikes )
1313 {
1314 #ifdef BOOST_GEOMETRY_TEST_DEBUG
1315     std::cout << std::endl << std::endl << std::endl;
1316     std::cout << "*** MULTILINESTRING / MULTILINESTRING DIFFERENCE"
1317               << " (WITH SPIKES) ***"
1318               << std::endl;
1319     std::cout << std::endl;
1320 #endif
1321
1322     typedef multi_linestring_type ML;
1323
1324     typedef test_difference_of_geometries<ML, ML, ML> tester;
1325
1326     // the following test cases concern linestrings with spikes
1327
1328     tester::apply
1329         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1330          from_wkt<ML>("MULTILINESTRING((1 0,9 0,5 0))"),
1331          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"),
1332          "mlmldf-spikes-01"
1333          );
1334
1335     tester::apply
1336         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1337          from_wkt<ML>("MULTILINESTRING((9 0,1 0,5 0))"),
1338          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"),
1339          "mlmldf-spikes-02"
1340          );
1341
1342     tester::apply
1343         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1344          from_wkt<ML>("MULTILINESTRING((1 0,9 0,2 0,8 0,3 0,7 0,4 0,5 0))"),
1345          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"),
1346          "mlmldf-spikes-03"
1347          );
1348
1349     tester::apply
1350         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1351          from_wkt<ML>("MULTILINESTRING((1 0,3 0,2 0,4 0,3 0,5 0,4 0,6 0,\
1352                       5 0,7 0,6 0,8 0,7 0,9 0))"),
1353          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"),
1354          "mlmldf-spikes-04"
1355          );
1356
1357     tester::apply
1358         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1359          from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),\
1360                       (9 1,9 0,9 2))"),
1361          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(6 0,7 0),(8 0,10 0))"),
1362          "mlmldf-spikes-05"
1363          );
1364
1365     tester::apply
1366         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1367          from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),\
1368                       (9 0,9 2,9 1))"),
1369          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(6 0,7 0),(8 0,10 0))"),
1370          "mlmldf-spikes-05a"
1371          );
1372
1373     tester::apply
1374         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1375          from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(9 0,6 0,8 0),\
1376                       (11 0,8 0,12 0))"),
1377          from_wkt<ML>("MULTILINESTRING((0 0,1 0))"),
1378          "mlmldf-spikes-06"
1379          );
1380
1381     tester::apply
1382         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1383          from_wkt<ML>("MULTILINESTRING((-1 0,0 0,-2 0),(11 0,10 0,12 0))"),
1384          from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1385          "mlmldf-spikes-07"
1386          );
1387
1388     tester::apply
1389         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1390          from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,-2 -2),(11 1,10 0,12 2))"),
1391          from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1392          "mlmldf-spikes-07a"
1393          );
1394
1395     tester::apply
1396         (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1397          from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(11 0,10 0,12 0),\
1398                       (7 5,7 0,8 0,6.5 0,8.5 0,8.5 5))"),
1399          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(6 0,6.5 0),(8.5 0,10 0))"),
1400          "mlmldf-spikes-08"
1401          );
1402
1403     // now the first geometry has a spike
1404     tester::apply
1405         (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"),
1406          from_wkt<ML>("MULTILINESTRING((1 0,8 0))"),
1407          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(8 0,10 0))"),
1408          "mlmldf-spikes-09"
1409          );
1410
1411     tester::apply
1412         (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"),
1413          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"),
1414          from_wkt<ML>("MULTILINESTRING((1 0,7 0,4 0,9 0))"),
1415          "mlmldf-spikes-09a"
1416          );
1417
1418     tester::apply
1419         (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"),
1420          from_wkt<ML>("MULTILINESTRING((0 0,5 0),(9 0,10 0))"),
1421          from_wkt<ML>("MULTILINESTRING((5 0,7 0,5 0),(5 0,9 0))"),
1422          "mlmldf-spikes-09b"
1423          );
1424
1425     tester::apply
1426         (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"),
1427          from_wkt<ML>("MULTILINESTRING((0 0,5 0),(6 0,10 0))"),
1428          from_wkt<ML>("MULTILINESTRING((5 0,6 0),(6 0,5 0),(5 0,6 0))"),
1429          "mlmldf-spikes-09c"
1430          );
1431
1432     tester::apply
1433         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1434          from_wkt<ML>("MULTILINESTRING((1 0,8 0))"),
1435          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(8 0,10 0,8 0))"),
1436          "mlmldf-spikes-10"
1437          );
1438
1439     tester::apply
1440         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1441          from_wkt<ML>("MULTILINESTRING((1 0,8 0,4 0),(2 0,9 0,5 0))"),
1442          from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0,9 0))"),
1443          "mlmldf-spikes-11"
1444          );
1445
1446     tester::apply
1447         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1448          from_wkt<ML>("MULTILINESTRING((11 1,10 0,12 2))"),
1449          from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1450          "mlmldf-spikes-12"
1451          );
1452
1453     tester::apply
1454         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1455          from_wkt<ML>("MULTILINESTRING((11 -1,10 0,12 -2))"),
1456          from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1457          "mlmldf-spikes-12a"
1458          );
1459
1460     tester::apply
1461         (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1462          from_wkt<ML>("MULTILINESTRING((11 0,10 0,12 0))"),
1463          from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1464          "mlmldf-spikes-13"
1465          );
1466
1467     // the following three tests have been discussed with Adam
1468     tester::apply
1469         (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
1470          from_wkt<ML>("MULTILINESTRING((1 2,1 1,1 2))"),
1471          from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
1472          "mlmldf-spikes-14"
1473          );
1474
1475     tester::apply
1476         (from_wkt<ML>("MULTILINESTRING((0 0,1 0,0 0))"),
1477          from_wkt<ML>("MULTILINESTRING((2 0,1 0,2 0))"),
1478          from_wkt<ML>("MULTILINESTRING((0 0,1 0,0 0))"),
1479          "mlmldf-spikes-15"
1480          );
1481
1482     tester::apply
1483         (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
1484          from_wkt<ML>("MULTILINESTRING((2 0,1 1,2 0))"),
1485          from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
1486          "mlmldf-spikes-16"
1487          );
1488
1489     tester::apply
1490         (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
1491          from_wkt<ML>("MULTILINESTRING((2 1,1 1,2 1))"),
1492          from_wkt<ML>("MULTILINESTRING((1 0,1 1))"),
1493          "mlmldf-spikes-17"
1494          );
1495
1496     // test cases sent by Adam on the mailing list (equal slikes)
1497     tester::apply
1498         (from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"),
1499          from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"),
1500          from_wkt<ML>("MULTILINESTRING()"),
1501          "mlmldf-spikes-18"
1502          );
1503
1504     tester::apply
1505         (from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"),
1506          from_wkt<ML>("MULTILINESTRING((1 1,0 0,1 1))"),
1507          from_wkt<ML>("MULTILINESTRING()"),
1508          "mlmldf-spikes-19"
1509          );
1510 }
1511
1512 BOOST_AUTO_TEST_CASE( test_difference_ls_mls_geo_rad )
1513 {
1514     typedef bg::model::point<double, 2, bg::cs::geographic<bg::radian> > pt;
1515     typedef bg::model::linestring<pt> ls;
1516     typedef bg::model::multi_linestring<ls> mls;
1517
1518     bg::srs::spheroid<double> sph_wgs84(6378137.0, 6356752.3142451793);
1519     boost::geometry::strategy::intersection::geographic_segments<> wgs84(sph_wgs84);
1520
1521     ls g1 = from_wkt<ls>("LINESTRING(0 0, -3.14159265358979 0)");
1522     mls g2 = from_wkt<mls>("MULTILINESTRING((-2.1467549799530232 -0.12217304763960295,"
1523                                             "-2.5481807079117185 -0.90757121103705041,"
1524                                             "-2.6529004630313784 0.85521133347722067,"
1525                                             " 0.92502450355699373 0.62831853071795796,"
1526                                             "-2.5307274153917754 0,"
1527                                             " 2.8099800957108676 1.0646508437165401,"
1528                                             "-1.6057029118347816 -1.5009831567151219,"
1529                                             " 0.2268928027592626 1.0646508437165401,"
1530                                             "-2.199114857512853 -0.017453292519943278,"
1531                                             " 0 0.31415926535897898,"
1532                                             " 0 0.57595865315812822,"
1533                                             " 1.0471975511965967 -0.73303828583761765,"
1534                                             " 2.1118483949131366 -0.54105206811824158))");
1535     mls out;
1536     bg::difference(g1, g2, out, wgs84);
1537
1538     check_result(g1, g2, out,
1539                  from_wkt<mls>("MULTILINESTRING((0 0,0 0.31415926535897897853),"
1540                                                "(0 0.57595865315812821983,-3.1415926535897900074 0))"),
1541                  "geo_lmldf-1");
1542 }