ceph/src/boost/libs/geometry/test/algorithms/is_simple.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2014-2017, Oracle and/or its affiliates.
   5
   6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   8
   9 // Licensed under the Boost Software License version 1.0.
  10 // http://www.boost.org/users/license.html
  11
  12 #ifndef BOOST_TEST_MODULE
  13 #define BOOST_TEST_MODULE test_is_simple
  14 #endif
  15
  16 #include "test_is_simple.hpp"
  17
  18
  19 namespace bg = ::boost::geometry;
  20
  21 typedef bg::model::point<double, 2, bg::cs::cartesian>  point_type;
  22 typedef bg::model::segment<point_type>                  segment_type;
  23 typedef bg::model::linestring<point_type>               linestring_type;
  24 typedef bg::model::multi_linestring<linestring_type>    multi_linestring_type;
  25 // ccw open and closed polygons
  26 typedef bg::model::polygon<point_type,false,false>      open_ccw_polygon_type;
  27 typedef bg::model::polygon<point_type,false,true>       closed_ccw_polygon_type;
  28 // multi-geometries
  29 typedef bg::model::multi_point<point_type>              multi_point_type;
  30 typedef bg::model::multi_polygon<open_ccw_polygon_type> multi_polygon_type;
  31 // box
  32 typedef bg::model::box<point_type>                      box_type;
  33
  34
  35 BOOST_AUTO_TEST_CASE( test_is_simple_point )
  36 {
  37 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  38     std::cout << std::endl << std::endl;
  39     std::cout << "************************************" << std::endl;
  40     std::cout << " is_simple: POINT " << std::endl;
  41     std::cout << "************************************" << std::endl;
  42 #endif
  43
  44     typedef point_type G;
  45
  46     test_simple(from_wkt<G>("POINT(0 0)"), true);
  47 }
  48
  49 BOOST_AUTO_TEST_CASE( test_is_simple_multipoint )
  50 {
  51 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  52     std::cout << std::endl << std::endl;
  53     std::cout << "************************************" << std::endl;
  54     std::cout << " is_simple: MULTIPOINT " << std::endl;
  55     std::cout << "************************************" << std::endl;
  56 #endif
  57
  58     typedef multi_point_type G;
  59
  60     test_simple(from_wkt<G>("MULTIPOINT(0 0)"), true);
  61     test_simple(from_wkt<G>("MULTIPOINT(0 0,1 0,1 1,0 1)"), true);
  62     test_simple(from_wkt<G>("MULTIPOINT(0 0,1 0,1 1,1 0,0 1)"), false);
  63
  64     // empty multipoint
  65     test_simple(from_wkt<G>("MULTIPOINT()"), true);
  66 }
  67
  68 BOOST_AUTO_TEST_CASE( test_is_simple_segment )
  69 {
  70 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  71     std::cout << std::endl << std::endl;
  72     std::cout << "************************************" << std::endl;
  73     std::cout << " is_simple: SEGMENT " << std::endl;
  74     std::cout << "************************************" << std::endl;
  75 #endif
  76
  77     typedef segment_type G;
  78
  79     test_simple(from_wkt<G>("SEGMENT(0 0,1 0)"), true);
  80 }
  81
  82 BOOST_AUTO_TEST_CASE( test_is_simple_linestring )
  83 {
  84 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  85     std::cout << std::endl << std::endl;
  86     std::cout << "************************************" << std::endl;
  87     std::cout << " is_simple: LINESTRING " << std::endl;
  88     std::cout << "************************************" << std::endl;
  89 #endif
  90
  91     typedef linestring_type G;
  92
  93     // valid linestrings with multiple points
  94     test_simple(from_wkt<G>("LINESTRING(0 0,0 0,1 0)"), false);
  95     test_simple(from_wkt<G>("LINESTRING(0 0,0 0,1 0,0 0)"), false);
  96     test_simple(from_wkt<G>("LINESTRING(0 0,0 0,1 0,1 0,1 1,0 0)"), false);
  97     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,2 0,1 1,1 0,1 -1)"), false);
  98
  99     // simple open linestrings
 100     test_simple(from_wkt<G>("LINESTRING(0 0,1 2)"), true);
 101     test_simple(from_wkt<G>("LINESTRING(0 0,1 2,2 3)"), true);
 102
 103     // simple closed linestrings
 104     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,1 1,0 0)"), true);
 105     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,1 1,0 1,0 0)"), true);
 106     test_simple(from_wkt<G>("LINESTRING(0 0,10 0,10 10,0 10,0 0)"), true);
 107
 108     // non-simple linestrings
 109     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,0 0)"), false);
 110     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,2 10,0.5 -1)"), false);
 111     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,2 1,1 0)"), false);
 112     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,2 1,0.5 0)"), false);
 113     test_simple(from_wkt<G>("LINESTRING(0 0,2 0,1 0)"), false);
 114     test_simple(from_wkt<G>("LINESTRING(0 0,3 0,5 0,1 0)"), false);
 115     test_simple(from_wkt<G>("LINESTRING(0 0,3 0,5 0,4 0)"), false);
 116     test_simple(from_wkt<G>("LINESTRING(0 0,3 0,5 0,4 0,2 0)"), false);
 117     test_simple(from_wkt<G>("LINESTRING(0 0,3 0,2 0,5 0)"), false);
 118     test_simple(from_wkt<G>("LINESTRING(0 0,2 0,2 2,1 0,0 0)"), false);
 119     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,2 0,2 2,1 0,0 0)"), false);
 120     test_simple(from_wkt<G>("LINESTRING(0 0,10 0,10 10,0 10,0 0,0 0)"), false);
 121     test_simple(from_wkt<G>("LINESTRING(0 0,0 10,5 10,0 0,10 10,10 5,10 0,0 0)"), false);
 122     test_simple(from_wkt<G>("LINESTRING(0 0,0 0,10 0,10 10,0 10,0 0,0 0)"),
 123                 false);
 124     test_simple(from_wkt<G>("LINESTRING(0 0,0 0,0 0,10 0,10 10,0 10,0 0,0 0,0 0,0 0)"),
 125                 false);
 126     test_simple(from_wkt<G>("LINESTRING(0 0,0 0,10 0,10 10,10 10,10 10,10 10,10 10,0 10,0 0,0 0)"),
 127                 false);
 128     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,2 0,2 2,1 0)"), false);
 129     test_simple(from_wkt<G>("LINESTRING(1 0,2 2,2 0,1 0,0 0)"), false);
 130     test_simple(from_wkt<G>("LINESTRING(0 0,1 0,2 0,2 2,1 0,1 4,0 0)"), false);
 131     test_simple(from_wkt<G>("LINESTRING(4 1,10 8,4 6,4 1,10 5,10 3)"),
 132                 false);
 133     test_simple(from_wkt<G>("LINESTRING(10 3,10 5,4 1,4 6,10 8,4 1)"),
 134                 false);
 135
 136     // empty linestring
 137     // the simplicity result is irrelevant since an empty linestring
 138     // is considered as invalid
 139     test_simple(from_wkt<G>("LINESTRING()"), false, false);
 140 }
 141
 142 BOOST_AUTO_TEST_CASE( test_is_simple_multilinestring )
 143 {
 144 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 145     std::cout << std::endl << std::endl;
 146     std::cout << "************************************" << std::endl;
 147     std::cout << " is_simple: MULTILINESTRING " << std::endl;
 148     std::cout << "************************************" << std::endl;
 149 #endif
 150
 151     typedef multi_linestring_type G;
 152
 153     // multilinestrings with linestrings with spikes
 154     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0,0 0),(5 0,6 0,7 0))"),
 155                 false);
 156     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0,0 0),(5 0,1 0,4 1))"),
 157                 false);
 158     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0,0 0),(5 0,1 0,4 0))"),
 159                 false);
 160     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0,0 0),(1 0,2 0))"),
 161                 false);
 162
 163     // simple multilinestrings
 164     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 1),(1 1,1 0))"), true);
 165     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 1),(1 1,1 0),(0 1,1 1))"),
 166                 true);
 167     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2),(0 0,1 0,2 0,2 2))"), true);
 168     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2),(2 2,2 0,1 0,0 0))"), true);
 169     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0),(0 0,-1 0),(1 0,2 0))"),
 170                 true);
 171     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0),(-1 0,0 0),(2 0,1 0))"),
 172                 true);
 173     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0),(0 0,0 1),(0 0,-1 0),(0 0,0 -1))"),
 174                 true);
 175     test_simple(from_wkt<G>("MULTILINESTRING((0 0,10 0,10 10,0 10,0 0))"), true);
 176
 177     // non-simple multilinestrings
 178     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2),(0 0,2 2))"), false);
 179     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2),(2 2,0 0))"), false);
 180     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2),(0 0,1 0,1 1,2 0,2 2))"),
 181                 false);
 182     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 1,2 2),(0 0,1 0,1 1,2 0,2 2))"),
 183                 false);
 184     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 1,2 2),(2 2,0 0))"),
 185                 false);
 186     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2,4 4),(0 0,1 1))"),
 187                 false);
 188     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2,4 4),(0 0,3 3))"),
 189                 false);
 190     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2,4 4),(1 1,3 3))"),
 191                 false);
 192     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2,4 4),(1 1,2 2))"),
 193                 false);
 194     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2,4 4),(2 2,3 3))"),
 195                 false);
 196     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2,4 4),(2 2,4 4))"),
 197                 false);
 198     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 2,4 4),(4 4,2 2))"),
 199                 false);
 200     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 1),(0 1,1 0))"),
 201                 false);
 202     test_simple(from_wkt<G>("MULTILINESTRING((0 0,2 0),(1 0,0 1))"),
 203                 false);
 204     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 1),(1 1,1 0),(1 1,0 1,0.5,0.5))"),
 205                 false);
 206     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0,1 1,0 1,0 0),(1 0,1 -1))"),
 207                 false);
 208     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0,1 1,0 1,0 0),(-1 0,0 0))"),
 209                 false);
 210     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0,1 1,0 1,0 0),(0 0,-1 0,-1 -1,0 -1,0 0))"),
 211                 false);
 212     test_simple(from_wkt<G>("MULTILINESTRING((0 0,1 0,1 1,0 1,0 0),(-1 -1,-1 0,0 0,0 -1,-1 -1))"),
 213                 false);
 214     test_simple(from_wkt<G>("MULTILINESTRING((0 0,0 10,5 10,0 0,10 10,10 5,10 0,0 0))"),
 215                 false);
 216     test_simple(from_wkt<G>("MULTILINESTRING((4 1,10 8,4 6,4 1,10 5,10 3))"),
 217                 false);
 218     test_simple(from_wkt<G>("MULTILINESTRING((10 3,10 5,4 1,4 6,10 8,4 1))"),
 219                 false);
 220
 221     // empty multilinestring
 222     test_simple(from_wkt<G>("MULTILINESTRING()"), true);
 223 }
 224
 225 BOOST_AUTO_TEST_CASE( test_is_simple_areal )
 226 {
 227     typedef box_type b;
 228     typedef open_ccw_polygon_type o_ccw_p;
 229     typedef multi_polygon_type mpl;
 230
 231     // check that is_simple compiles for boxes
 232     test_simple(from_wkt<b>("BOX(0 0,1 1)"), true);
 233
 234     // simple polygons and multi-polygons
 235     test_simple(from_wkt<o_ccw_p>("POLYGON((0 0,1 0,1 1))"), true);
 236     test_simple(from_wkt<o_ccw_p>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 9,9 9,9 1))"),
 237                 true);
 238     test_simple(from_wkt<mpl>("MULTIPOLYGON(((0 0,1 0,1 1)),((10 0,20 0,20 10,10 10)))"),
 239                 true);
 240
 241     // non-simple polygons & multi-polygons (have duplicate points)
 242     test_simple(from_wkt<o_ccw_p>("POLYGON((0 0,1 0,1 0,1 1))"), false);
 243     test_simple(from_wkt<o_ccw_p>("POLYGON((0 0,10 0,10 10,0 10),(1 1,1 9,9 9,9 9,9 1))"),
 244                 false);
 245     test_simple(from_wkt<mpl>("MULTIPOLYGON(((0 0,1 0,1 1,1 1)),((10 0,20 0,20 0,20 10,10 10)))"),
 246                 false);
 247
 248     // empty polygon
 249     // the simplicity result is irrelevant since an empty polygon
 250     // is considered as invalid
 251     test_simple(from_wkt<o_ccw_p>("POLYGON(())"), false, false);
 252
 253     // empty multipolygon
 254     test_simple(from_wkt<mpl>("MULTIPOLYGON()"), true);
 255 }
 256
 257 BOOST_AUTO_TEST_CASE( test_geometry_with_NaN_coordinates )
 258 {
 259 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 260     std::cout << std::endl << std::endl;
 261     std::cout << "************************************" << std::endl;
 262     std::cout << " is_valid: geometry with NaN coordinates" << std::endl;
 263     std::cout << "************************************" << std::endl;
 264 #endif
 265
 266     linestring_type ls1, ls2;
 267     bg::read_wkt("LINESTRING(1 1,1.115235e+308 1.738137e+308)", ls1);
 268     bg::read_wkt("LINESTRING(-1 1,1.115235e+308 1.738137e+308)", ls2);
 269
 270     // the intersection of the two linestrings is a new linestring
 271     // (multilinestring with a single element) that has NaN coordinates
 272     multi_linestring_type mls;
 273     bg::intersection(ls1, ls2, mls);
 274
 275     test_simple(mls, true, false);
 276 }
 277
 278 BOOST_AUTO_TEST_CASE( test_is_simple_variant )
 279 {
 280 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 281     std::cout << std::endl << std::endl;
 282     std::cout << "************************************" << std::endl;
 283     std::cout << " is_simple: variant support" << std::endl;
 284     std::cout << "************************************" << std::endl;
 285 #endif
 286
 287     typedef bg::model::polygon<point_type> polygon_type; // cw, closed
 288     typedef boost::variant
 289         <
 290             linestring_type, multi_linestring_type, polygon_type
 291         > variant_geometry;
 292
 293     variant_geometry vg;
 294
 295     linestring_type simple_linestring =
 296         from_wkt<linestring_type>("LINESTRING(0 0,1 0)");
 297     multi_linestring_type non_simple_multi_linestring = from_wkt
 298         <
 299             multi_linestring_type
 300         >("MULTILINESTRING((0 0,1 0,1 1,0 0),(10 0,1 1))");
 301     polygon_type simple_polygon =
 302         from_wkt<polygon_type>("POLYGON((0 0,1 1,1 0,0 0))");
 303     polygon_type non_simple_polygon =
 304         from_wkt<polygon_type>("POLYGON((0 0,1 1,1 0,1 0,0 0))");
 305
 306     vg = simple_linestring;
 307     test_simple(vg, true);
 308     vg = non_simple_multi_linestring;
 309     test_simple(vg, false);
 310     vg = simple_polygon;
 311     test_simple(vg, true);
 312     vg = non_simple_polygon;
 313     test_simple(vg, false);
 314 }