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