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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2013-2020.
   7 // Modifications copyright (c) 2013-2020 Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #include "test_equals.hpp"
  16
  17 #include <boost/type_traits/is_floating_point.hpp>
  18
  19 #include <boost/geometry/geometries/geometries.hpp>
  20 #include <boost/geometry/geometries/point_xy.hpp>
  21
  22
  23 namespace bgm = bg::model;
  24
  25 template <typename P>
  26 void test_pointlike()
  27 {
  28     typedef bgm::multi_point<P> mpt;
  29
  30     test_geometry<P, P>("ptpt2d_1", "POINT(0 0)", "POINT(0 0)", true);
  31     test_geometry<P, P>("ptpt2d_2", "POINT(0 0)", "POINT(1 1)", false);
  32
  33     test_geometry<P, mpt>("ptmpt2d_1", "POINT(0 0)", "MULTIPOINT(0 0)", true);
  34     test_geometry<P, mpt>("ptmpt2d_1", "POINT(0 0)", "MULTIPOINT(0 0, 1 1)", false);
  35
  36     test_geometry<mpt, P>("mptpt2d_1", "MULTIPOINT(0 0)", "POINT(0 0)", true);
  37     test_geometry<mpt, P>("mptpt2d_1", "MULTIPOINT(0 0, 1 1)", "POINT(0 0)", false);
  38
  39     test_geometry<mpt, mpt>("mptmpt2d_1", "MULTIPOINT(0 0, 1 1)", "MULTIPOINT(0 0, 1 1)", true);
  40     test_geometry<mpt, mpt>("mptmpt2d_1", "MULTIPOINT(0 0, 1 1)", "MULTIPOINT(0 0, 2 2)", false);
  41     test_geometry<mpt, mpt>("mptmpt2d_1", "MULTIPOINT(0 0, 1 1)", "MULTIPOINT(2 2, 3 3)", false);
  42 }
  43
  44 template <typename P>
  45 void test_segment_segment()
  46 {
  47     typedef bgm::segment<P> seg;
  48
  49     test_geometry<seg, seg>("seg2d_1", "LINESTRING(0 0, 3 3)", "LINESTRING(0 0, 3 3)", true);
  50     test_geometry<seg, seg>("seg2d_1", "LINESTRING(0 0, 3 3)", "LINESTRING(3 3, 0 0)", true);
  51
  52     test_geometry<seg, seg>("seg2d_1", "LINESTRING(0 0, 3 3)", "LINESTRING(0 0, 1 1)", false);
  53     test_geometry<seg, seg>("seg2d_1", "LINESTRING(0 0, 3 3)", "LINESTRING(3 3, 2 2)", false);
  54
  55     test_geometry<seg, seg>("seg2d_1", "LINESTRING(0 0, 3 3)", "LINESTRING(1 1, 4 4)", false);
  56     test_geometry<seg, seg>("seg2d_1", "LINESTRING(0 0, 3 3)", "LINESTRING(1 0, 2 0)", false);
  57 }
  58
  59 template <typename P>
  60 void test_linestring_linestring()
  61 {
  62     typedef bgm::linestring<P> ls;
  63
  64     test_geometry<ls, ls>("ls2d_1", "LINESTRING(1 1, 3 3)", "LINESTRING(3 3, 1 1)", true);
  65     test_geometry<ls, ls>("ls2d_2", "LINESTRING(1 1, 3 3, 2 5)", "LINESTRING(1 1, 2 2, 3 3, 2 5)", true);
  66     test_geometry<ls, ls>("ls2d_3", "LINESTRING(1 0, 3 3, 2 5)", "LINESTRING(1 1, 2 2, 3 3, 2 5)", false);
  67     test_geometry<ls, ls>("ls2d_4", "LINESTRING(1 0, 3 3, 2 5)", "LINESTRING(1 1, 3 3, 2 5)", false);
  68     test_geometry<ls, ls>("ls2d_5", "LINESTRING(0 5,5 5,10 5,10 0,5 0,5 5,5 10,10 10,15 10,15 5,10 5,10 10,10 15)",
  69                                     "LINESTRING(0 5,15 5,15 10,5 10,5 0,10 0,10 15)", true);
  70     test_geometry<ls, ls>("ls2d_6", "LINESTRING(0 5,5 5,10 5,10 10,5 10,5 5,5 0)", "LINESTRING(0 5,5 5,5 10,10 10,10 5,5 5,5 0)", true);
  71     test_geometry<ls, ls>("ls2d_7", "LINESTRING(0 5,10 5,10 10,5 10,5 0)", "LINESTRING(0 5,5 5,5 10,10 10,10 5,5 5,5 0)", true);
  72     test_geometry<ls, ls>("ls2d_8", "LINESTRING(0 0,5 0,5 0,6 0)", "LINESTRING(0 0,6 0)", true);
  73
  74     test_geometry<ls, ls>("ls2d_seg", "LINESTRING(1 1,2 2)", "LINESTRING(1 1,2 2)", true);
  75     test_geometry<ls, ls>("ls2d_rev", "LINESTRING(1 1,2 2)", "LINESTRING(2 2,1 1)", true);
  76
  77     test_geometry<ls, ls>("ls2d_spike", "LINESTRING(0 0,5 0,3 0,6 0)", "LINESTRING(0 0,6 0)", true);
  78
  79     test_geometry<ls, ls>("ls2d_ring1", "LINESTRING(0 0,5 0,5 5,0 5,0 0)", "LINESTRING(5 5,0 5,0 0,5 0,5 5)", true);
  80     test_geometry<ls, ls>("ls2d_ring2", "LINESTRING(0 0,5 0,5 5,0 5,0 0)", "LINESTRING(5 5,5 0,0 0,0 5,5 5)", true);
  81     test_geometry<ls, ls>("ls2d_overl_ring1", "LINESTRING(0 0,5 0,5 5,0 5,0 0)", "LINESTRING(5 5,0 5,0 0,5 0,5 5,0 5)", true);
  82     test_geometry<ls, ls>("ls2d_overl_ring2", "LINESTRING(0 0,5 0,5 5,0 5,0 0)", "LINESTRING(5 5,5 0,0 0,0 5,5 5,5 0)", true);
  83
  84     // https://svn.boost.org/trac/boost/ticket/10904
  85     if ( BOOST_GEOMETRY_CONDITION(
  86             boost::is_floating_point<typename bg::coordinate_type<ls>::type>::value ) )
  87     {
  88         test_geometry<ls, ls>("ls2d_small1",
  89                               "LINESTRING(5.6956521739130430148634331999347 -0.60869565217391330413931882503675,5.5 -0.50000000000000066613381477509392)",
  90                               "LINESTRING(5.5 -0.50000000000000066613381477509392,5.5 -0.5)",
  91                               false);
  92
  93         test_geometry<ls, ls>("ls2d_small2",
  94                               "LINESTRING(-3.2333333333333333925452279800083 5.5999999999999978683717927196994,-3.2333333333333333925452279800083 5.5999999999999996447286321199499)",
  95                               "LINESTRING(-3.2333333333333325043668082798831 5.5999999999999996447286321199499,-3.2333333333333333925452279800083 5.5999999999999996447286321199499)",
  96                               false);
  97     }
  98 }
  99
 100 template <typename P>
 101 void test_linestring_multilinestring()
 102 {
 103     typedef bgm::linestring<P> ls;
 104     typedef bgm::multi_linestring<ls> mls;
 105
 106     test_geometry<ls, mls>("ls_mls_1", "LINESTRING(0 0,1 0,2 0)", "MULTILINESTRING((0 0,2 0))", true);
 107     test_geometry<ls, mls>("ls_mls_1", "LINESTRING(0 0,1 0,2 0)", "MULTILINESTRING((0 0,1 0),(1 0,2 0))", true);
 108     test_geometry<ls, mls>("ls_mls_1", "LINESTRING(0 0,2 0,4 0)", "MULTILINESTRING((0 0,2 0),(2 0,3 0),(3 0,4 0))", true);
 109     test_geometry<ls, mls>("ls_mls_1", "LINESTRING(0 0,2 0,4 0)", "MULTILINESTRING((0 0,2 0),(2 0,3 0),(2 0,3 0),(3 0,4 0))", true);
 110     test_geometry<ls, mls>("ls_mls_1", "LINESTRING(0 0,2 0,4 0)", "MULTILINESTRING((0 0,2 0),(3 0,4 0))", false);
 111
 112     test_geometry<ls, mls>("ls_mls_spike", "LINESTRING(0 0,2 0,2 2,2 0,4 0)", "MULTILINESTRING((0 0,4 0),(2 2,2 0))", true);
 113     test_geometry<ls, mls>("ls_mls_spike", "LINESTRING(0 0,2 0,2 2,2 0,4 0)", "MULTILINESTRING((0 0,4 0),(2 2,2 -1))", false);
 114
 115     test_geometry<ls, mls>("ls_mls_ring1", "LINESTRING(0 0,5 0,5 5,0 5,0 0)", "MULTILINESTRING((5 5,0 5,0 0),(0 0,5 0,5 5))", true);
 116     test_geometry<ls, mls>("ls_mls_ring2", "LINESTRING(0 0,5 0,5 5,0 5,0 0)", "MULTILINESTRING((5 5,5 0,0 0),(0 0,0 5,5 5))", true);
 117     test_geometry<ls, mls>("ls_mls_overl_ring1", "LINESTRING(0 0,5 0,5 5,0 5,0 0)", "MULTILINESTRING((5 5,0 5,0 0),(0 0,5 0,5 5,0 5))", true);
 118     test_geometry<ls, mls>("ls_mls_overl_ring2", "LINESTRING(0 0,5 0,5 5,0 5,0 0)", "MULTILINESTRING((5 5,5 0,0 0),(0 0,0 5,5 5,5 0))", true);
 119 }
 120
 121 template <typename P>
 122 void test_multilinestring_multilinestring()
 123 {
 124     typedef bgm::linestring<P> ls;
 125     typedef bgm::multi_linestring<ls> mls;
 126
 127     test_geometry<mls, mls>("ls_mls_mls",
 128                             "MULTILINESTRING((0 5,10 5,10 10,5 10),(5 10,5 0,5 2),(5 2,5 5,0 5))",
 129                             "MULTILINESTRING((5 5,0 5),(5 5,5 0),(10 10,10 5,5 5,5 10,10 10))",
 130                             true);
 131 }
 132
 133 template <typename P>
 134 void test_polygons()
 135 {
 136     typedef bg::model::polygon<P, true, true> poly_cw_c;
 137     typedef bg::model::polygon<P, true, false> poly_cw_o;
 138     typedef bg::model::polygon<P, false, true> poly_ccw_c;
 139     typedef bg::model::polygon<P, false, false> poly_ccw_o;
 140     typedef bg::model::box<P> box;
 141
 142     std::string wkt1 = "POLYGON((-18 1, -23 1, -23 -3, -18 -3))";
 143     std::string wkt2 = "POLYGON((-23 1, -23 -3, -18 -3, -18 1))";
 144
 145     test_geometry<poly_cw_c, poly_cw_c>("polys_cw_c_cw_c", wkt1, wkt2, true, true);
 146     test_geometry<poly_cw_c, poly_cw_o>("polys_cw_c_cw_o", wkt1, wkt2, true, true);
 147     test_geometry<poly_cw_c, poly_ccw_c>("polys_cw_c_ccw_c", wkt1, wkt2, true, true);
 148     test_geometry<poly_cw_c, poly_ccw_o>("polys_cw_c_ccw_o", wkt1, wkt2, true, true);
 149     test_geometry<poly_cw_c, box>("polys_cw_c_box", wkt1, wkt2, true, true);
 150
 151     test_geometry<poly_cw_o, poly_cw_c>("polys_cw_o_cw_c", wkt1, wkt2, true, true);
 152     test_geometry<poly_cw_o, poly_cw_o>("polys_cw_o_cw_o", wkt1, wkt2, true, true);
 153     test_geometry<poly_cw_o, poly_ccw_c>("polys_cw_o_ccw_c", wkt1, wkt2, true, true);
 154     test_geometry<poly_cw_o, poly_ccw_o>("polys_cw_o_ccw_o", wkt1, wkt2, true, true);
 155     test_geometry<poly_cw_o, box>("polys_cw_o_box", wkt1, wkt2, true, true);
 156
 157     test_geometry<poly_ccw_c, poly_cw_c>("polys_ccw_c_cw_c", wkt1, wkt2, true, true);
 158     test_geometry<poly_ccw_c, poly_cw_o>("polys_ccw_c_cw_o", wkt1, wkt2, true, true);
 159     test_geometry<poly_ccw_c, poly_ccw_c>("polys_ccw_c_ccw_c", wkt1, wkt2, true, true);
 160     test_geometry<poly_ccw_c, poly_ccw_o>("polys_ccw_c_ccw_o", wkt1, wkt2, true, true);
 161     test_geometry<poly_ccw_c, box>("polys_cw_o_box", wkt1, wkt2, true, true);
 162
 163     test_geometry<poly_ccw_o, poly_cw_c>("polys_ccw_o_cw_c", wkt1, wkt2, true, true);
 164     test_geometry<poly_ccw_o, poly_cw_o>("polys_ccw_o_cw_o", wkt1, wkt2, true, true);
 165     test_geometry<poly_ccw_o, poly_ccw_c>("polys_ccw_o_ccw_c", wkt1, wkt2, true, true);
 166     test_geometry<poly_ccw_o, poly_ccw_o>("polys_ccw_o_ccw_o", wkt1, wkt2, true, true);
 167     test_geometry<poly_ccw_o, box>("polys_ccw_o_box", wkt1, wkt2, true, true);
 168 }
 169
 170 template <typename P>
 171 void test_all()
 172 {
 173     typedef bg::model::box<P> box;
 174     typedef bg::model::ring<P> ring;
 175     typedef bg::model::polygon<P> polygon;
 176     //typedef bg::model::linestring<P> linestring;
 177
 178     std::string case_p1 = "POLYGON((0 0,0 2,2 2,0 0))";
 179
 180     test_geometry<P, P>("p1", "POINT(1 1)", "POINT(1 1)", true);
 181     test_geometry<P, P>("p2", "POINT(1 1)", "POINT(1 2)", false);
 182     test_geometry<box, box>("b1", "BOX(1 1,2 2)", "BOX(1 2,2 2)", false);
 183     test_geometry<box, box>("b1", "BOX(1 2,3 4)", "BOX(1 2,3 4)", true);
 184
 185     // Completely equal
 186     test_geometry<ring, ring>("poly_eq", case_p1, case_p1, true);
 187
 188     // Shifted
 189     test_geometry<ring, ring>("poly_sh", "POLYGON((2 2,0 0,0 2,2 2))", case_p1, true);
 190     test_geometry<polygon, polygon>("poly_sh2", case_p1, "POLYGON((0 2,2 2,0 0,0 2))", true);
 191
 192     // Extra coordinate
 193     test_geometry<ring, ring>("poly_extra", case_p1, "POLYGON((0 0,0 2,2 2,1 1,0 0))", true);
 194
 195     // Shifted + extra (redundant) coordinate
 196     test_geometry<ring, ring>("poly_shifted_extra1", "POLYGON((2 2,1 1,0 0,0 2,2 2))", case_p1, true);
 197
 198     // Shifted + extra (redundant) coordinate being first/last point
 199     test_geometry<ring, ring>("poly_shifted_extra2", "POLYGON((1 1,0 0,0 2,2 2,1 1))", case_p1, true);
 200
 201     // Degenerate (duplicate) points
 202     test_geometry<ring, ring>("poly_degenerate", "POLYGON((0 0,0 2,2 2,2 2,0 0))", "POLYGON((0 0,0 2,0 2,2 2,0 0))", true);
 203
 204     // Two different bends, same area, unequal
 205     test_geometry<ring, ring>("poly_bends",
 206         "POLYGON((4 0,5 3,8 4,7 7,4 8,0 4,4 0))",
 207         "POLYGON((4 0,7 1,8 4,5 5,4 8,0 4,4 0))", false);
 208
 209     // Unequal (but same area)
 210     test_geometry<ring, ring>("poly_uneq", case_p1, "POLYGON((1 1,1 3,3 3,1 1))", false);
 211
 212     // Note that POLYGON((0 0,0 4,4 4,0 0),(1 1,2 1,2 2,1 2,1 1))
 213     // below is invalid. equals() returns different result than
 214     // relate() with equals mask in this case because for areal
 215     // geometries different algorithms is used, i.e. collect_vectors.
 216
 217     // One having hole
 218     test_geometry<polygon, polygon>("poly_hole",
 219             "POLYGON((0 0,0 4,4 4,0 0))",
 220             "POLYGON((0 0,0 4,4 4,0 0),(1 1,2 1,2 2,1 2,1 1))", false);
 221
 222     // Both having holes
 223     test_geometry<polygon, polygon>("poly_holes",
 224             "POLYGON((0 0,0 4,4 4,0 0),(1 1,2 1,2 2,1 2,1 1))",
 225             "POLYGON((0 0,0 4,4 4,0 0),(1 1,2 1,2 2,1 2,1 1))", true);
 226
 227     // Both having holes, outer equal, inner not equal
 228     test_geometry<polygon, polygon>("poly_uneq_holes",
 229             "POLYGON((0 0,0 4,4 4,0 0),(1 1,2 1,2 2,1 2,1 1))",
 230             "POLYGON((0 0,0 4,4 4,0 0),(2 2,3 2,3 3,2 3,2 2))", false);
 231
 232     // Both having 2 holes, equal but in different order
 233     test_geometry<polygon, polygon>("poly_holes_diff_order",
 234             "POLYGON((0 0,0 4,4 4,0 0),(1 1,2 1,2 2,1 2,1 1),(2 2,3 2,3 3,2 3,2 2))",
 235             "POLYGON((0 0,0 4,4 4,0 0),(2 2,3 2,3 3,2 3,2 2),(1 1,2 1,2 2,1 2,1 1))", true);
 236
 237     // Both having 3 holes, equal but in different order
 238     test_geometry<polygon, polygon>("poly_holes_diff_order_3",
 239             "POLYGON((0 0,0 10,10 10,0 0),(1 1,2 1,2 2,1 2,1 1),(4 1,5 1,5 2,4 2,4 1),(2 2,3 2,3 3,2 3,2 2))",
 240             "POLYGON((0 0,0 10,10 10,0 0),(4 1,5 1,5 2,4 2,4 1),(2 2,3 2,3 3,2 3,2 2),(1 1,2 1,2 2,1 2,1 1))", true);
 241
 242     // polygon/ring vv
 243     test_geometry<polygon, ring>("poly_sh2_pr", case_p1, case_p1, true);
 244     test_geometry<ring, polygon>("poly_sh2_rp", case_p1, case_p1, true);
 245
 246     // box/ring/poly
 247     test_geometry<box, ring>("boxring1", "BOX(1 1,2 2)", "POLYGON((1 1,1 2,2 2,2 1,1 1))", true);
 248     test_geometry<ring, box>("boxring2", "POLYGON((1 1,1 2,2 2,2 1,1 1))", "BOX(1 1,2 2)", true);
 249     test_geometry<box, polygon>("boxpoly1", "BOX(1 1,2 2)", "POLYGON((1 1,1 2,2 2,2 1,1 1))", true);
 250     test_geometry<polygon, box>("boxpoly2", "POLYGON((1 1,1 2,2 2,2 1,1 1))", "BOX(1 1,2 2)", true);
 251
 252     test_geometry<polygon, box>("boxpoly2", "POLYGON((1 1,1 2,2 2,2 1,1 1))", "BOX(1 1,2 3)", false);
 253
 254     test_geometry<polygon, polygon>("poly_holes_shifted_points",
 255         "POLYGON((0 0,0 3,3 3,3 0,0 0),(1 1,2 1,2 2,1 2,1 1))",
 256         "POLYGON((0 0,0 3,3 3,3 0,0 0),(2 2,1 2,1 1,2 1,2 2))", true);
 257
 258     test_pointlike<P>();
 259     test_segment_segment<P>();
 260     test_linestring_linestring<P>();
 261     test_linestring_multilinestring<P>();
 262     test_multilinestring_multilinestring<P>();
 263     test_polygons<P>();
 264 }
 265
 266
 267 template <typename T>
 268 void verify()
 269 {
 270     T dxn1, dyn1, dxn2, dyn2;
 271
 272     {
 273         T x1 = "0", y1 = "0", x2 = "3", y2 = "3";
 274         T dx = x2 - x1, dy = y2 - y1;
 275         T mag = sqrt(dx * dx + dy * dy);
 276         dxn1 = dx / mag;
 277         dyn1 = dy / mag;
 278     }
 279
 280     {
 281         T x1 = "0", y1 = "0", x2 = "1", y2 = "1";
 282         T dx = x2 - x1, dy = y2 - y1;
 283         T mag = sqrt(dx * dx + dy * dy);
 284         dxn2 = dx / mag;
 285         dyn2 = dy / mag;
 286     }
 287
 288     if (dxn1 == dxn2 && dyn1 == dyn2)
 289     {
 290         //std::cout << "vectors are equal, using ==" << std::endl;
 291     }
 292     if (boost::geometry::math::equals(dxn1, dxn2)
 293         && boost::geometry::math::equals(dyn1, dyn2))
 294     {
 295         //std::cout << "vectors are equal, using bg::math::equals" << std::endl;
 296     }
 297
 298     bool equals = boost::geometry::math::equals_with_epsilon(dxn1, dxn2)
 299         && boost::geometry::math::equals_with_epsilon(dyn1, dyn2);
 300
 301     if (equals)
 302     {
 303         //std::cout << "vectors are equal, using bg::math::equals_with_epsilon" << std::endl;
 304     }
 305
 306     BOOST_CHECK_EQUAL(equals, true);
 307 }
 308
 309
 310 int test_main( int , char* [] )
 311 {
 312     //verify<double>();
 313
 314     test_all<bg::model::d2::point_xy<int> >();
 315     test_all<bg::model::d2::point_xy<double> >();
 316
 317     return 0;
 318 }