libs/geometry/test/algorithms/is_valid.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2014, Oracle and/or its affiliates.
   5
   6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   7
   8 // Licensed under the Boost Software License version 1.0.
   9 // http://www.boost.org/users/license.html
  10
  11 #ifndef BOOST_TEST_MODULE
  12 #define BOOST_TEST_MODULE test_is_valid
  13 #endif
  14
  15 #include <iostream>
  16
  17 #include <boost/test/included/unit_test.hpp>
  18
  19 #include "from_wkt.hpp"
  20 #include "test_is_valid.hpp"
  21
  22
  23 BOOST_AUTO_TEST_CASE( test_is_valid_point )
  24 {
  25 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  26     std::cout << std::endl << std::endl;
  27     std::cout << "************************************" << std::endl;
  28     std::cout << " is_valid: POINT " << std::endl;
  29     std::cout << "************************************" << std::endl;
  30 #endif
  31
  32     typedef point_type G;
  33     typedef default_validity_tester tester;
  34     typedef test_valid<tester, G> test;
  35
  36     test::apply(from_wkt<G>("POINT(0 0)"), true);
  37 }
  38
  39 BOOST_AUTO_TEST_CASE( test_is_valid_multipoint )
  40 {
  41 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  42     std::cout << std::endl << std::endl;
  43     std::cout << "************************************" << std::endl;
  44     std::cout << " is_valid: MULTIPOINT " << std::endl;
  45     std::cout << "************************************" << std::endl;
  46 #endif
  47
  48     typedef multi_point_type G;
  49     typedef default_validity_tester tester;
  50     typedef test_valid<tester, G> test;
  51
  52     test::apply(from_wkt<G>("MULTIPOINT()"), false);
  53     test::apply(from_wkt<G>("MULTIPOINT(0 0,0 0)"), true);
  54     test::apply(from_wkt<G>("MULTIPOINT(0 0,1 0,1 1,0 1)"), true);
  55     test::apply(from_wkt<G>("MULTIPOINT(0 0,1 0,1 1,1 0,0 1)"), true);
  56 }
  57
  58 BOOST_AUTO_TEST_CASE( test_is_valid_segment )
  59 {
  60 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  61     std::cout << std::endl << std::endl;
  62     std::cout << "************************************" << std::endl;
  63     std::cout << " is_valid: SEGMENT " << std::endl;
  64     std::cout << "************************************" << std::endl;
  65 #endif
  66
  67     typedef segment_type G;
  68     typedef default_validity_tester tester;
  69     typedef test_valid<tester, G> test;
  70
  71     test::apply(from_wkt<G>("SEGMENT(0 0,0 0)"), false);
  72     test::apply(from_wkt<G>("SEGMENT(0 0,1 0)"), true);
  73 }
  74
  75 BOOST_AUTO_TEST_CASE( test_is_valid_box )
  76 {
  77 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  78     std::cout << std::endl << std::endl;
  79     std::cout << "************************************" << std::endl;
  80     std::cout << " is_valid: BOX " << std::endl;
  81     std::cout << "************************************" << std::endl;
  82 #endif
  83
  84     typedef box_type G;
  85     typedef default_validity_tester tester;
  86     typedef test_valid<tester, G> test;
  87
  88     // boxes where the max corner and below and/or to the left of min corner
  89     test::apply(from_wkt<G>("BOX(0 0,-1 0)"), false);
  90     test::apply(from_wkt<G>("BOX(0 0,0 -1)"), false);
  91     test::apply(from_wkt<G>("BOX(0 0,-1 -1)"), false);
  92
  93     // boxes of zero area; they are not 2-dimensional, so invalid
  94     test::apply(from_wkt<G>("BOX(0, 0, 0, 0)"), false);
  95     test::apply(from_wkt<G>("BOX(0 0,1 0)"), false);
  96     test::apply(from_wkt<G>("BOX(0 0,0 1)"), false);
  97
  98     test::apply(from_wkt<G>("BOX(0 0,1 1)"), true);
  99 }
 100
 101 template <typename G, bool AllowSpikes>
 102 void test_linestrings()
 103 {
 104 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 105     std::cout << "SPIKES ALLOWED? "
 106               << std::boolalpha
 107               << AllowSpikes
 108               << std::noboolalpha
 109               << std::endl;
 110 #endif
 111
 112     typedef validity_tester_linear<AllowSpikes> tester;
 113     typedef test_valid<tester, G> test;
 114
 115     // empty linestring
 116     test::apply(from_wkt<G>("LINESTRING()"), false);
 117
 118     // 1-point linestrings
 119     test::apply(from_wkt<G>("LINESTRING(0 0)"), false);
 120     test::apply(from_wkt<G>("LINESTRING(0 0,0 0)"), false);
 121     test::apply(from_wkt<G>("LINESTRING(0 0,0 0,0 0)"), false);
 122
 123     // 2-point linestrings
 124     test::apply(from_wkt<G>("LINESTRING(0 0,1 2)"), true);
 125     test::apply(from_wkt<G>("LINESTRING(0 0,1 2,1 2)"), true);
 126     test::apply(from_wkt<G>("LINESTRING(0 0,0 0,1 2,1 2)"), true);
 127     test::apply(from_wkt<G>("LINESTRING(0 0,0 0,0 0,1 2,1 2)"), true);
 128
 129     // 3-point linestrings
 130     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,2 10)"), true);
 131     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,2 10,0 0)"), true);
 132     test::apply(from_wkt<G>("LINESTRING(0 0,10 0,10 10,5 0)"), true);
 133
 134     // linestrings with spikes
 135     test::apply(from_wkt<G>("LINESTRING(0 0,1 2,0 0)"), AllowSpikes);
 136     test::apply(from_wkt<G>("LINESTRING(0 0,1 2,1 2,0 0)"), AllowSpikes);
 137     test::apply(from_wkt<G>("LINESTRING(0 0,0 0,1 2,1 2,0 0)"),
 138                 AllowSpikes);
 139     test::apply(from_wkt<G>("LINESTRING(0 0,0 0,0 0,1 2,1 2,0 0,0 0)"),
 140                 AllowSpikes);
 141     test::apply(from_wkt<G>("LINESTRING(0 0,10 0,5 0)"), AllowSpikes);
 142     test::apply(from_wkt<G>("LINESTRING(0 0,10 0,10 10,5 0,0 0)"),
 143                 AllowSpikes);
 144     test::apply(from_wkt<G>("LINESTRING(0 0,10 0,10 10,5 0,4 0,6 0)"),
 145                 AllowSpikes);
 146     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,1 1,5 5,4 4)"),
 147                 AllowSpikes);
 148     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,1 1,5 5,4 4,6 6)"),
 149                 AllowSpikes);
 150     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,1 1,5 5,4 4,4 0)"),
 151                 AllowSpikes);
 152     test::apply(from_wkt<G>("LINESTRING(0 0,0 0,1 0,1 0,1 0,0 0,0 0,2 0)"),
 153                 AllowSpikes);
 154     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,0 0,2 0,0 0,3 0,0 0,4 0)"),
 155                 AllowSpikes);
 156     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,0 0,2 0,0 0,3 0,0 0,4 0,0 0)"),
 157                 AllowSpikes);
 158
 159     // other examples
 160     test::apply(from_wkt<G>("LINESTRING(0 0,10 0,10 10,5 0,4 0)"), true);
 161     test::apply(from_wkt<G>("LINESTRING(0 0,10 0,10 10,5 0,4 0,3 0)"),
 162                 true);
 163     test::apply(from_wkt<G>("LINESTRING(0 0,10 0,10 10,5 0,4 0,-1 0)"),
 164                 true);
 165     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,1 1,-1 1,-1 0,0 0)"),
 166                 true);
 167
 168     test::apply(from_wkt<G>("LINESTRING(0 0,1 0,1 1,-1 1,-1 0,0.5 0)"),
 169                 true);
 170 }
 171
 172 BOOST_AUTO_TEST_CASE( test_is_valid_linestring )
 173 {
 174 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 175     std::cout << std::endl << std::endl;
 176     std::cout << "************************************" << std::endl;
 177     std::cout << " is_valid: LINESTRING " << std::endl;
 178     std::cout << "************************************" << std::endl;
 179 #endif
 180
 181     bool const allow_spikes = true;
 182     bool const do_not_allow_spikes = !allow_spikes;
 183
 184     test_linestrings<linestring_type, allow_spikes>();
 185     test_linestrings<linestring_type, do_not_allow_spikes>();
 186 }
 187
 188 template <typename G, bool AllowSpikes>
 189 void test_multilinestrings()
 190 {
 191 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 192     std::cout << "SPIKES ALLOWED? "
 193               << std::boolalpha
 194               << AllowSpikes
 195               << std::noboolalpha
 196               << std::endl;
 197 #endif
 198
 199     typedef validity_tester_linear<AllowSpikes> tester;
 200     typedef test_valid<tester, G> test;
 201
 202     // empty multilinestring
 203     test::apply(from_wkt<G>("MULTILINESTRING()"), false);
 204
 205     // multilinestring with empty linestring(s)
 206     test::apply(from_wkt<G>("MULTILINESTRING(())"), false);
 207     test::apply(from_wkt<G>("MULTILINESTRING((),(),())"), false);
 208     test::apply(from_wkt<G>("MULTILINESTRING((),(0 1,1 0))"), false);
 209
 210     // multilinestring with invalid linestrings
 211     test::apply(from_wkt<G>("MULTILINESTRING((0 0),(0 1,1 0))"), false);
 212     test::apply(from_wkt<G>("MULTILINESTRING((0 0,0 0),(0 1,1 0))"), false);
 213     test::apply(from_wkt<G>("MULTILINESTRING((0 0),(1 0))"), false);
 214     test::apply(from_wkt<G>("MULTILINESTRING((0 0,0 0),(1 0,1 0))"), false);
 215     test::apply(from_wkt<G>("MULTILINESTRING((0 0),(0 0))"), false);
 216     test::apply(from_wkt<G>("MULTILINESTRING((0 0,1 0,0 0),(5 0))"), false);
 217
 218     // multilinstring that has linestrings with spikes
 219     test::apply(from_wkt<G>("MULTILINESTRING((0 0,1 0,0 0),(5 0,1 0,4 1))"),
 220                 AllowSpikes);
 221     test::apply(from_wkt<G>("MULTILINESTRING((0 0,1 0,0 0),(1 0,2 0))"),
 222                 AllowSpikes);
 223
 224     // valid multilinestrings
 225     test::apply(from_wkt<G>("MULTILINESTRING((0 0,1 0,2 0),(5 0,1 0,4 1))"),
 226                 true);
 227     test::apply(from_wkt<G>("MULTILINESTRING((0 0,1 0,2 0),(1 0,2 0))"),
 228                 true);
 229     test::apply(from_wkt<G>("MULTILINESTRING((0 0,1 1),(0 1,1 0))"), true);
 230     test::apply(from_wkt<G>("MULTILINESTRING((0 0,1 1,2 2),(0 1,1 0,2 2))"),
 231                 true);
 232 }
 233
 234 BOOST_AUTO_TEST_CASE( test_is_valid_multilinestring )
 235 {
 236 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 237     std::cout << std::endl << std::endl;
 238     std::cout << "************************************" << std::endl;
 239     std::cout << " is_valid: MULTILINESTRING " << std::endl;
 240     std::cout << "************************************" << std::endl;
 241 #endif
 242
 243     bool const allow_spikes = true;
 244     bool const do_not_allow_spikes = !allow_spikes;
 245
 246     test_multilinestrings<multi_linestring_type, allow_spikes>();
 247     test_multilinestrings<multi_linestring_type, do_not_allow_spikes>();
 248 }
 249
 250
 251 template <typename Point, bool AllowDuplicates>
 252 void test_open_rings()
 253 {
 254 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 255     std::cout << std::endl << std::endl;
 256     std::cout << "************************************" << std::endl;
 257     std::cout << " is_valid: RING (open) " << std::endl;
 258     std::cout << "************************************" << std::endl;
 259     std::cout << "DUPLICATES ALLOWED? "
 260               << std::boolalpha
 261               << AllowDuplicates
 262               << std::noboolalpha
 263               << std::endl;
 264 #endif
 265
 266     typedef bg::model::ring<Point, false, false> OG; // ccw, open ring
 267     typedef bg::model::ring<Point, false, true> CG; // ccw, closed ring
 268     typedef bg::model::ring<Point, true, false> CW_OG; // cw, open ring
 269     typedef bg::model::ring<Point, true, true> CW_CG; // cw, closed ring
 270
 271     typedef validity_tester_areal<AllowDuplicates> tester;
 272     typedef test_valid<tester, OG, CG, CW_OG, CW_CG> test;
 273
 274     // not enough points
 275     test::apply(from_wkt<OG>("POLYGON(())"), false);
 276     test::apply(from_wkt<OG>("POLYGON((0 0))"), false);
 277     test::apply(from_wkt<OG>("POLYGON((0 0,1 0))"), false);
 278
 279     // duplicate points
 280     test::apply(from_wkt<OG>("POLYGON((0 0,0 0,0 0))"), false);
 281     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 0))"), false);
 282     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,0 0))"), false);
 283     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 1,0 0))"),
 284                 AllowDuplicates);
 285     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 0,1 1))"),
 286                 AllowDuplicates);
 287     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 0,1 1,0 0))"),
 288                 AllowDuplicates);
 289
 290     // with spikes
 291     test::apply(from_wkt<OG>("POLYGON((0 0,2 0,2 2,0 2,1 2))"), false);
 292     test::apply(from_wkt<OG>("POLYGON((0 0,2 0,1 0,2 2))"), false);
 293     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,2 0,1 0,4 0,4 4))"), false);
 294     test::apply(from_wkt<OG>("POLYGON((0 0,2 0,2 2,1 0))"), false);
 295     test::apply(from_wkt<OG>("POLYGON((0 0,2 0,1 0))"), false);
 296     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,4 4,5 5,0 5))"), false);
 297     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,4 4,3 3,5 5,0 5))"), false);
 298
 299     // with spikes and duplicate points
 300     test::apply(from_wkt<OG>("POLYGON((0 0,0 0,2 0,2 0,1 0,1 0))"), false);
 301
 302     // with self-crossings
 303     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,3 -1,0 5))"), false);
 304
 305     // with self-crossings and duplicate points
 306     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,5 5,3 -1,0 5,0 5))"),
 307                 false);
 308
 309     // with self-intersections
 310     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,3 5,3 0,2 0,2 5,0 5))"),
 311                 false);
 312
 313     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,3 5,3 0,2 5,0 5))"),
 314                 false);
 315
 316     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 1,1 1,1 2,2 2,3 1,4 2,5 2,5 5,0 5))"),
 317                 false);
 318
 319     // with self-intersections and duplicate points
 320     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,3 5,3 5,3 0,3 0,2 0,2 0,2 5,2 5,0 5))"),
 321                 false);
 322
 323     // next two suggested by Adam Wulkiewicz
 324     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,0 5,4 4,2 2,0 5))"), false);
 325     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,1 4,4 4,4 1,0 5))"),
 326                 false);
 327
 328     // and a few more
 329     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,4 4,1 4,1 1,4 1,4 4,0 5))"),
 330                 false);
 331     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,4 4,4 1,1 1,1 4,4 4,0 5))"),
 332                 false);
 333
 334     // valid rings
 335     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 1))"), true);
 336     test::apply(from_wkt<OG>("POLYGON((1 0,1 1,0 0))"), true);
 337     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 1,0 1))"), true);
 338     test::apply(from_wkt<OG>("POLYGON((1 0,1 1,0 1,0 0))"), true);
 339 }
 340
 341
 342 template <typename Point, bool AllowDuplicates>
 343 void test_closed_rings()
 344 {
 345 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 346     std::cout << std::endl << std::endl;
 347     std::cout << "************************************" << std::endl;
 348     std::cout << " is_valid: RING (closed) " << std::endl;
 349     std::cout << "************************************" << std::endl;
 350     std::cout << "DUPLICATES ALLOWED? "
 351               << std::boolalpha
 352               << AllowDuplicates
 353               << std::noboolalpha
 354               << std::endl;
 355 #endif
 356
 357     typedef bg::model::ring<Point, false, true> CG; // ccw, closed ring
 358     typedef bg::model::ring<Point, true, true> CW_CG; // cw, closed ring
 359
 360     typedef validity_tester_areal<AllowDuplicates> tester;
 361     typedef test_valid<tester, CG, CG, CW_CG> test;
 362
 363     // not enough points
 364     test::apply(from_wkt<CG>("POLYGON(())"), false);
 365     test::apply(from_wkt<CG>("POLYGON((0 0))"), false);
 366     test::apply(from_wkt<CG>("POLYGON((0 0,0 0))"), false);
 367     test::apply(from_wkt<CG>("POLYGON((0 0,1 0))"), false);
 368     test::apply(from_wkt<CG>("POLYGON((0 0,1 0,1 0))"), false);
 369     test::apply(from_wkt<CG>("POLYGON((0 0,1 0,2 0))"), false);
 370     test::apply(from_wkt<CG>("POLYGON((0 0,1 0,1 0,2 0))"), false);
 371     test::apply(from_wkt<CG>("POLYGON((0 0,1 0,2 0,2 0))"), false);
 372
 373     // boundary not closed
 374     test::apply(from_wkt<CG>("POLYGON((0 0,1 0,1 1,1 2))"), false);
 375     test::apply(from_wkt<CG>("POLYGON((0 0,1 0,1 0,1 1,1 1,1 2))"),
 376                 false);
 377 }
 378
 379 BOOST_AUTO_TEST_CASE( test_is_valid_ring )
 380 {
 381     bool const allow_duplicates = true;
 382     bool const do_not_allow_duplicates = !allow_duplicates;
 383
 384     test_open_rings<point_type, allow_duplicates>();
 385     test_open_rings<point_type, do_not_allow_duplicates>();
 386
 387     test_closed_rings<point_type, allow_duplicates>();
 388     test_closed_rings<point_type, do_not_allow_duplicates>();
 389 }
 390
 391 template <typename Point, bool AllowDuplicates>
 392 void test_open_polygons()
 393 {
 394 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 395     std::cout << std::endl << std::endl;
 396     std::cout << "************************************" << std::endl;
 397     std::cout << " is_valid: POLYGON (open) " << std::endl;
 398     std::cout << "************************************" << std::endl;
 399     std::cout << "DUPLICATES ALLOWED? "
 400               << std::boolalpha
 401               << AllowDuplicates
 402               << std::noboolalpha
 403               << std::endl;
 404 #endif
 405
 406     typedef bg::model::polygon<Point, false, false> OG; // ccw, open
 407     typedef bg::model::polygon<Point, false, true> CG; // ccw, closed
 408     typedef bg::model::polygon<Point, true, false> CW_OG; // cw, open
 409     typedef bg::model::polygon<Point, true, true> CW_CG; // cw, closed
 410
 411     typedef validity_tester_areal<AllowDuplicates> tester;
 412     typedef test_valid<tester, OG, CG, CW_OG, CW_CG> test;
 413
 414     // not enough points in exterior ring
 415     test::apply(from_wkt<OG>("POLYGON(())"), false);
 416     test::apply(from_wkt<OG>("POLYGON((0 0))"), false);
 417     test::apply(from_wkt<OG>("POLYGON((0 0,1 0))"), false);
 418
 419     // not enough points in interior ring
 420     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),())"), false);
 421     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1))"), false);
 422     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,2 2))"),
 423                 false);
 424
 425     // duplicate points in exterior ring
 426     test::apply(from_wkt<OG>("POLYGON((0 0,0 0,0 0))"), false);
 427     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 0))"), false);
 428     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,0 0))"), false);
 429     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 1,0 0))"), AllowDuplicates);
 430     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 0,1 1))"), AllowDuplicates);
 431     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 0,1 1,0 0))"),
 432                 AllowDuplicates);
 433
 434     // duplicate points in interior ring
 435     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 1,1 1))"),
 436                 false);
 437     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,2 1,2 1))"),
 438                 false);
 439     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,2 1,1 1))"),
 440                 false);
 441     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,2 2,2 1,1 1))"),
 442                 AllowDuplicates);
 443     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,2 2,2 2,2 1))"),
 444                 AllowDuplicates);
 445     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,2 2,2 1,2 1,1 1))"),
 446                 AllowDuplicates);
 447
 448     // with spikes in exterior ring
 449     test::apply(from_wkt<OG>("POLYGON((0 0,2 0,2 2,0 2,1 2))"), false);
 450     test::apply(from_wkt<OG>("POLYGON((0 0,2 0,1 0,2 2))"), false);
 451     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,2 0,1 0,4 0,4 4))"), false);
 452     test::apply(from_wkt<OG>("POLYGON((0 0,2 0,2 2,1 0))"), false);
 453     test::apply(from_wkt<OG>("POLYGON((0 0,2 0,1 0))"), false);
 454     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,4 4,5 5,0 5))"), false);
 455     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,4 4,3 3,5 5,0 5))"), false);
 456
 457     // with spikes in interior ring
 458     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,3 1,3 3,1 3,2 3))"),
 459                 false);
 460     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,3 1,2 1,3 3))"),
 461                 false);
 462     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,2 1,3 1,2 1,4 1,4 4))"),
 463                 false);
 464     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,3 1,3 3,2 1))"),
 465                 false);
 466     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,3 1,2 1))"),
 467                 false);
 468
 469     // with self-crossings in exterior ring
 470     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,3 -1,0 5))"),
 471                 false);
 472
 473     // example from Norvald Ryeng
 474     test::apply(from_wkt<OG>("POLYGON((100 1300,140 1300,140 170,100 1700))"),
 475                 false);
 476     // and with point order reversed
 477     test::apply(from_wkt<OG>("POLYGON((100 1300,100 1700,140 170,140 1300))"),
 478                 false);
 479
 480     // with self-crossings in interior ring
 481     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(3 3,3 7,4 6,2 6))"),
 482                 false);
 483
 484     // with self-crossings between rings
 485     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,0 5),(1 1,2 1,1 -1))"),
 486                 false);
 487
 488     // with self-intersections in exterior ring
 489     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,3 5,3 0,2 0,2 5,0 5))"),
 490                 false);
 491
 492     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,3 5,3 0,2 5,0 5))"),
 493                 false);
 494
 495     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 1,1 1,1 2,2 2,3 1,4 2,5 2,5 5,0 5))"),
 496                 false);
 497
 498     // next two suggested by Adam Wulkiewicz
 499     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,0 5,4 4,2 2,0 5))"), false);
 500     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,1 4,4 4,4 1,0 5))"),
 501                false);
 502     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,4 4,1 4,1 1,4 1,4 4,0 5))"),
 503                false);
 504     test::apply(from_wkt<OG>("POLYGON((0 0,5 0,5 5,4 4,4 1,1 1,1 4,4 4,0 5))"),
 505                false);
 506
 507     // with self-intersections in interior ring
 508     test::apply(from_wkt<OG>("POLYGON((-10 -10,10 -10,10 10,-10 10),(0 0,5 0,5 5,3 5,3 0,2 0,2 5,0 5))"),
 509                 false);
 510     test::apply(from_wkt<OG>("POLYGON((-10 -10,10 -10,10 10,-10 10),(0 0,5 0,5 5,3 5,3 0,2 5,0 5))"),
 511                 false);
 512
 513     test::apply(from_wkt<OG>("POLYGON((-10 -10,10 -10,10 10,-10 10),(0 0,5 0,5 1,1 1,1 2,2 2,3 1,4 2,5 2,5 5,0 5))"),
 514                 false);
 515
 516     // with self-intersections between rings
 517     // hole has common segment with exterior ring
 518     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 10,2 10,2 1))"),
 519                 false);
 520     test::apply(from_wkt<OG>("POLYGON((0 0,0 0,10 0,10 10,0 10,0 10),(1 1,1 10,1 10,2 10,2 10,2 1))"),
 521                 false);
 522     // hole touches exterior ring at one point
 523     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 10,2 1))"),
 524                 true);
 525     // "hole" is outside the exterior ring, but touches it
 526     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(5 10,4 11,6 11))"),
 527                 false);
 528     // hole touches exterior ring at vertex
 529     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(0 0,1 4,4 1))"),
 530                 true);
 531     // "hole" is completely outside the exterior ring
 532     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(20 20,20 21,21 21,21 20))"),
 533                 false);
 534     // two "holes" completely outside the exterior ring, that touch
 535     // each other
 536     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(20 0,25 10,21 0),(30 0,25 10,31 0))"),
 537                 false);
 538
 539     // example from Norvald Ryeng
 540     test::apply(from_wkt<OG>("POLYGON((58 31,56.57 30,62 33),(35 9,28 14,31 16),(23 11,29 5,26 4))"),
 541                 false);
 542     // and with points reversed
 543     test::apply(from_wkt<OG>("POLYGON((58 31,62 33,56.57 30),(35 9,31 16,28 14),(23 11,26 4,29 5))"),
 544                 false);
 545
 546     // "hole" is completely inside another "hole"
 547     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 9,9 9,9 1),(2 2,2 8,8 8,8 2))"),
 548                 false);
 549     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 9,9 9,9 1),(2 2,8 2,8 8,2 8))"),
 550                false);
 551
 552     // "hole" is inside another "hole" (touching)
 553     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 9,9 9,9 1),(2 2,2 8,8 8,9 6,8 2))"),
 554                 false);
 555     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 9,9 9,9 1),(2 2,8 2,9 6,8 8,2 8))"),
 556                 false);
 557     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,9 1,9 9,1 9),(2 2,2 8,8 8,9 6,8 2))"),
 558                 false);
 559     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,9 1,9 9,1 9),(2 2,8 2,9 6,8 8,2 8))"),
 560                 false);
 561     // hole touches exterior ring at two points
 562     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(5 0,0 5,5 5))"),
 563                 false);
 564
 565     // cases with more holes
 566     // two holes, touching the exterior at the same point
 567     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(0 0,1 9,2 9),(0 0,9 2,9 1))"),
 568                 true);
 569     test::apply(from_wkt<OG>("POLYGON((0 0,0 0,10 0,10 10,0 10,0 0),(0 0,0 0,1 9,2 9),(0 0,0 0,9 2,9 1))"),
 570                 AllowDuplicates);
 571     test::apply(from_wkt<OG>("POLYGON((0 10,0 0,0 0,0 0,10 0,10 10),(2 9,0 0,0 0,1 9),(9 1,0 0,0 0,9 2))"),
 572                 AllowDuplicates);
 573     // two holes, one inside the other
 574     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(0 0,1 9,9 1),(0 0,4 5,5 4))"),
 575                 false);
 576     // 1st hole touches has common segment with 2nd hole
 577     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 5,5 5,5 1),(5 4,5 8,8 8,8 4))"),
 578                 false);
 579     // 1st hole touches 2nd hole at two points
 580     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 9,9 9,9 8,2 8,2 1),(2 5,5 8,5 5))"),
 581                 false);
 582     // polygon with many holes, where the last two touch at two points
 583     test::apply(from_wkt<OG>("POLYGON((0 0,20 0,20 20,0 20),(1 18,1 19,2 19,2 18),(3 18,3 19,4 19,4 18),(5 18,5 19,6 19,6 18),(7 18,7 19,8 19,8 18),(9 18,9 19,10 19,10 18),(11 18,11 19,12 19,12 18),(13 18,13 19,14 19,14 18),(15 18,15 19,16 19,16 18),(17 18,17 19,18 19,18 18),(1 1,1 9,9 9,9 8,2 8,2 1),(2 5,5 8,5 5))"),
 584                 false);
 585     // two holes completely inside exterior ring but touching each
 586     // other at a point
 587     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 9,2 9),(1 1,9 2,9 1))"),
 588                 true);
 589     // four holes, each two touching at different points
 590     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(0 10,2 1,1 1),(0 10,4 1,3 1),(10 10,9 1,8 1),(10 10,7 1,6 1))"),
 591                 true);
 592     // five holes, with two pairs touching each at some point, and
 593     // fifth hole creating a disconnected component for the interior
 594     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(0 10,2 1,1 1),(0 10,4 1,3 1),(10 10,9 1,8 1),(10 10,7 1,6 1),(4 1,4 4,6 4,6 1))"),
 595                 false);
 596     // five holes, with two pairs touching each at some point, and
 597     // fifth hole creating three disconnected components for the interior
 598     test::apply(from_wkt<OG>("POLYGON((0 0,10 0,10 10,0 10),(0 10,2 1,1 1),(0 10,4 1,3 1),(10 10,9 1,8 1),(10 10,7 1,6 1),(4 1,4 4,6 4,6 1,5 0))"),
 599                 false);
 600
 601     // both examples: a polygon with one hole, where the hole contains
 602     // the exterior ring
 603     test::apply(from_wkt<OG>("POLYGON((0 0,1 0,1 1,0 1),(-10 -10,-10 10,10 10,10 -10))"),
 604                 false);
 605     test::apply(from_wkt<OG>("POLYGON((-10 -10,1 0,1 1,0 1),(-10 -10,-10 10,10 10,10 -10))"),
 606                 false);
 607 }
 608
 609 template <typename Point>
 610 inline void test_doc_example_polygon()
 611 {
 612 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 613     std::cout << std::endl << std::endl;
 614     std::cout << "************************************" << std::endl;
 615     std::cout << " is_valid: doc example polygon " << std::endl;
 616     std::cout << "************************************" << std::endl;
 617 #endif
 618
 619     typedef bg::model::polygon<Point> CCW_CG;
 620
 621     CCW_CG poly;
 622
 623     typedef validity_tester_areal<true> tester;
 624     typedef test_valid<tester, CCW_CG> test;
 625
 626     test::apply(from_wkt<CCW_CG>("POLYGON((0 0,0 10,10 10,10 0,0 0),(0 0,9 1,9 2,0 0),(0 0,2 9,1 9,0 0),(2 9,9 2,9 9,2 9))"),
 627                 false);
 628 }
 629
 630 BOOST_AUTO_TEST_CASE( test_is_valid_polygon )
 631 {
 632     bool const allow_duplicates = true;
 633     bool const do_not_allow_duplicates = !allow_duplicates;
 634
 635     test_open_polygons<point_type, allow_duplicates>();
 636     test_open_polygons<point_type, do_not_allow_duplicates>();
 637     test_doc_example_polygon<point_type>();
 638 }
 639
 640 template <typename Point, bool AllowDuplicates>
 641 void test_open_multipolygons()
 642 {
 643 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 644     std::cout << std::endl << std::endl;
 645     std::cout << "************************************" << std::endl;
 646     std::cout << " is_valid: MULTIPOLYGON (open) " << std::endl;
 647     std::cout << "************************************" << std::endl;
 648     std::cout << "DUPLICATES ALLOWED? "
 649               << std::boolalpha
 650               << AllowDuplicates
 651               << std::noboolalpha
 652               << std::endl;
 653 #endif
 654
 655     // cw, ccw, open and closed polygons
 656     typedef bg::model::polygon<point_type,false,false> ccw_open_polygon_type;
 657     typedef bg::model::polygon<point_type,false,true>  ccw_closed_polygon_type;
 658     typedef bg::model::polygon<point_type,true,false>  cw_open_polygon_type;
 659     typedef bg::model::polygon<point_type,true,true>   cw_closed_polygon_type;
 660
 661     typedef bg::model::multi_polygon<ccw_open_polygon_type> OG;
 662     typedef bg::model::multi_polygon<ccw_closed_polygon_type> CG;
 663     typedef bg::model::multi_polygon<cw_open_polygon_type> CW_OG;
 664     typedef bg::model::multi_polygon<cw_closed_polygon_type> CW_CG;
 665
 666     typedef validity_tester_areal<AllowDuplicates> tester;
 667     typedef test_valid<tester, OG, CG, CW_OG, CW_CG> test;
 668
 669     // not enough points
 670     test::apply(from_wkt<OG>("MULTIPOLYGON((()))"), false);
 671     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0)),(()))"), false);
 672     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,1 0)))"), false);
 673
 674     // two disjoint polygons
 675     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,1 0,1 1,0 1)),((2 2,3 2,3 3,2 3)))"),
 676                 true);
 677
 678     // two disjoint polygons with multiple points
 679     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,1 0,1 0,1 1,0 1)),((2 2,3 2,3 3,3 3,2 3)))"),
 680                 AllowDuplicates);
 681
 682     // two polygons touch at a point
 683     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,1 0,1 1,0 1)),((1 1,2 1,2 2,1 2)))"),
 684                 true);
 685
 686     // two polygons share a segment at a point
 687     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,1.5 0,1.5 1,0 1)),((1 1,2 1,2 2,1 2)))"),
 688                 false);
 689
 690     // one polygon inside another and boundaries touching
 691     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,10 0,10 10,0 10)),((0 0,9 1,9 2)))"),
 692                 false);
 693
 694     // one polygon inside another and boundaries not touching
 695     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,10 0,10 10,0 10)),((1 1,9 1,9 2)))"),
 696                 false);
 697
 698     // free space is disconnected
 699     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,1 0,1 1,0 1)),((1 1,2 1,2 2,1 2)),((0 1,0 2,-1 2,-1 -1)),((1 2,1 3,0 3,0 2)))"),
 700                 true);
 701
 702     // multi-polygon with a polygon inside the hole of another polygon
 703     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,100 0,100 100,0 100),(1 1,1 99,99 99,99 1)),((2 2,98 2,98 98,2 98)))"),
 704                 true);
 705     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,100 0,100 100,0 100),(1 1,1 99,99 99,99 1)),((1 1,98 2,98 98,2 98)))"),
 706                 true);
 707
 708     // test case suggested by Barend Gehrels: take two valid polygons P1 and
 709     // P2 with holes H1 and H2, respectively, and consider P2 to be
 710     // fully inside H1; now invalidate the multi-polygon by
 711     // considering H2 as a hole of P1 and H1 as a hole of P2; this
 712     // should be invalid
 713     //
 714     // first the valid case:
 715     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,100 0,100 100,0 100),(1 1,1 99,99 99,99 1)),((2 2,98 2,98 98,2 98),(3 3,3 97,97 97,97 3)))"),
 716                 true);
 717     // and the invalid case:
 718     test::apply(from_wkt<OG>("MULTIPOLYGON(((0 0,100 0,100 100,0 100),(3 3,3 97,97 97,97 3)),((2 2,98 2,98 98,2 98),(1 1,1 99,99 99,99 1)))"),
 719                 false);
 720 }
 721
 722 BOOST_AUTO_TEST_CASE( test_is_valid_multipolygon )
 723 {
 724     bool const allow_duplicates = true;
 725     bool const do_not_allow_duplicates = !allow_duplicates;
 726
 727     test_open_multipolygons<point_type, allow_duplicates>();
 728     test_open_multipolygons<point_type, do_not_allow_duplicates>();
 729 }
 730
 731 BOOST_AUTO_TEST_CASE( test_is_valid_variant )
 732 {
 733 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 734     std::cout << std::endl << std::endl;
 735     std::cout << "************************************" << std::endl;
 736     std::cout << " is_valid: variant support" << std::endl;
 737     std::cout << "************************************" << std::endl;
 738 #endif
 739
 740     typedef bg::model::polygon<point_type> polygon_type; // cw, closed
 741
 742     typedef boost::variant
 743         <
 744             linestring_type, multi_linestring_type, polygon_type
 745         > variant_geometry;
 746     typedef test_valid_variant<variant_geometry> test;
 747
 748     variant_geometry vg;
 749
 750     linestring_type valid_linestring =
 751         from_wkt<linestring_type>("LINESTRING(0 0,1 0)");
 752     multi_linestring_type invalid_multi_linestring =
 753         from_wkt<multi_linestring_type>("MULTILINESTRING((0 0,1 0),(0 0))");
 754     polygon_type valid_polygon =
 755         from_wkt<polygon_type>("POLYGON((0 0,1 1,1 0,0 0))");
 756     polygon_type invalid_polygon =
 757         from_wkt<polygon_type>("POLYGON((0 0,1 1,1 0))");
 758
 759     vg = valid_linestring;
 760     test::apply(vg, true);
 761     vg = invalid_multi_linestring;
 762     test::apply(vg, false);
 763     vg = valid_polygon;
 764     test::apply(vg, true);
 765     vg = invalid_polygon;
 766     test::apply(vg, false);
 767 }