ceph/src/boost/libs/geometry/test/strategies/segment_intersection.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   5 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
   6 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
   7
   8 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
   9 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  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
  16 #if defined(_MSC_VER)
  17 // We deliberately mix float/double's here so turn off warning
  18 #pragma warning( disable : 4244 )
  19 #endif // defined(_MSC_VER)
  20
  21 #define HAVE_MATRIX_AS_STRING
  22
  23
  24 #include <geometry_test_common.hpp>
  25
  26 #include <boost/geometry/algorithms/assign.hpp>
  27
  28 #include <boost/geometry/strategies/cartesian/intersection.hpp>
  29 #include <boost/geometry/strategies/intersection_result.hpp>
  30
  31 #include <boost/geometry/policies/relate/intersection_points.hpp>
  32 #include <boost/geometry/policies/relate/direction.hpp>
  33 #include <boost/geometry/policies/relate/tupled.hpp>
  34
  35 #include <boost/geometry/algorithms/intersection.hpp>
  36
  37
  38 #include <boost/geometry/geometries/point.hpp>
  39 #include <boost/geometry/geometries/segment.hpp>
  40 #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
  41
  42 BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian);
  43
  44
  45 template <typename R>
  46 void print_is(R const& is)
  47 {
  48 #ifdef REPORT
  49     for (int i = 0; i < is.count; i++)
  50     {
  51         std::cout
  52             << " (" << bg::get<0>(is.intersections[i])
  53             << "," << bg::get<1>(is.intersections[i])
  54             << ")";
  55     }
  56 #endif
  57 }
  58 /*
  59 void print_im(bg::de9im const& im)
  60 {
  61 #ifdef REPORT
  62     if (im.equals()) std::cout << " EQUALS";
  63     if (im.disjoint()) std::cout << " DISJOINT";
  64     if (im.intersects()) std::cout << " INTERSECTS";
  65     if (im.touches()) std::cout << " TOUCHES";
  66     if (im.crosses()) std::cout << " CROSSES";
  67     if (im.overlaps()) std::cout << " OVERLAPS";
  68     if (im.within()) std::cout << " WITHIN";
  69     if (im.contains()) std::cout << " CONTAINS";
  70
  71     //std::cout << " ra=" << im.ra << " rb=" << im.rb;
  72 #endif
  73 }
  74 */
  75
  76 template <typename P>
  77 static void test_segment_intersection(int caseno,
  78                 int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4,
  79                 std::string const& expected_matrix,
  80                 std::string const& expected_characteristic,
  81                 std::string const& expected_direction_a = "",
  82                 std::string const& expected_direction_b = "",
  83                 int expected_x1 = -99, int expected_y1 = -99,
  84                 int expected_x2 = -99, int expected_y2 = -99)
  85 {
  86     using namespace boost::geometry;
  87
  88 #ifdef REPORT
  89     std::cout << "CASE " << caseno << std::endl;
  90 #endif
  91
  92     typedef typename bg::coordinate_type<P>::type coordinate_type;
  93     typedef bg::model::referring_segment<const P> segment_type;
  94
  95     P p1, p2, p3, p4;
  96     bg::assign_values(p1, x1, y1);
  97     bg::assign_values(p2, x2, y2);
  98     bg::assign_values(p3, x3, y3);
  99     bg::assign_values(p4, x4, y4);
 100
 101     segment_type s12(p1,p2);
 102     segment_type s34(p3,p4);
 103
 104     // Get the intersection point (or two points)
 105     typedef bg::detail::no_rescale_policy rescale_policy_type;
 106     rescale_policy_type rescale_policy;
 107
 108     typedef bg::segment_intersection_points
 109     <
 110         P,
 111         typename bg::segment_ratio_type
 112         <
 113             P,
 114             rescale_policy_type
 115         >::type
 116     > result_type;
 117
 118     result_type is = strategy::intersection::relate_cartesian_segments
 119         <
 120             bg::policies::relate::segments_intersection_points<result_type>
 121         >::apply(s12, s34, rescale_policy);
 122
 123     // Get the Dimension Extended 9 Intersection Matrix (de9im) for Segments
 124     // (this one is extended by GGL having opposite)
 125     /***
 126     TODO TO BE UPDATED (if necessary) OR DELETED
 127     de9im_segment matrix = strategy::intersection::relate_cartesian_segments
 128         <
 129             policies::relate::segments_de9im<segment_type, segment_type>
 130         >::apply(s12, s34);
 131     ***/
 132
 133     // Get just a character for Left/Right/intersects/etc, purpose is more for debugging
 134     policies::relate::direction_type dir = strategy::intersection::relate_cartesian_segments
 135         <
 136             policies::relate::segments_direction
 137         >::apply(s12, s34, rescale_policy);
 138
 139     int expected_count = 0;
 140
 141     if (expected_x1 != -99 && expected_y1 != -99)
 142     {
 143         expected_count++;
 144
 145         BOOST_CHECK(is.count >= 1);
 146         BOOST_CHECK_CLOSE(bg::get<0>(is.intersections[0]),
 147                 coordinate_type(expected_x1), 0.001);
 148         BOOST_CHECK_CLOSE(bg::get<1>(is.intersections[0]),
 149                 coordinate_type(expected_y1), 0.001);
 150     }
 151     if (expected_x2 != -99 && expected_y2 != -99)
 152     {
 153         expected_count++;
 154
 155         BOOST_CHECK(is.count >= 2);
 156         BOOST_CHECK_CLOSE(bg::get<0>(is.intersections[1]),
 157                 coordinate_type(expected_x2), 0.001);
 158         BOOST_CHECK_CLOSE(bg::get<1>(is.intersections[1]),
 159                 coordinate_type(expected_y2), 0.001);
 160     }
 161     BOOST_CHECK_EQUAL(is.count, expected_count);
 162
 163     //BOOST_CHECK_EQUAL(expected_matrix, matrix.matrix_as_string());
 164
 165     std::string characteristic;
 166     characteristic += dir.how;
 167
 168     BOOST_CHECK_EQUAL(characteristic, expected_characteristic);
 169
 170     if (!expected_direction_a.empty())
 171     {
 172         BOOST_CHECK_EQUAL(dir.dir_a == 1 ? "L"
 173                     : dir.dir_a == -1 ? "R"
 174                     : "-", expected_direction_a);
 175     }
 176     if (!expected_direction_b.empty())
 177     {
 178         BOOST_CHECK_EQUAL(dir.dir_b == 1 ? "L"
 179                     : dir.dir_b == -1 ? "R"
 180                     : "-", expected_direction_b);
 181     }
 182
 183
 184
 185     // Things can also be used together
 186     // -> intersection is only once calculated, two results
 187     /***
 188     typedef boost::tuple
 189         <
 190             de9im_segment,
 191             policies::relate::direction_type
 192         > tup;
 193
 194     tup t = strategy::intersection::relate_cartesian_segments
 195         <
 196             policies::relate::segments_tupled
 197                 <
 198                     policies::relate::segments_de9im<segment_type, segment_type>,
 199                     policies::relate::segments_direction<segment_type, segment_type>
 200                 >
 201         >::apply(segment_type(p1,p2), segment_type(p3,p4));
 202
 203
 204     //BOOST_CHECK_EQUAL(t.get<0>().matrix_as_string(), matrix.matrix_as_string());
 205     BOOST_CHECK_EQUAL(t.get<1>().how, dir.how);
 206     */
 207
 208 #ifdef REPORT
 209     //std::cout << std::endl << "\t" << matrix.as_string() << " ";
 210     std::cout << "METHOD=" << c << " ";
 211     print_is(is);
 212     //print_im(matrix);
 213     std::cout << std::endl;
 214 #endif
 215
 216     /*
 217     To check with a spatial database: issue this statement
 218     std::cout << "select relate("
 219             << "GeomFromText(LINESTRING('" << x1 << " " << y1 << "," << x2 << " " << y2 << ")')"
 220             << ", "
 221             << "GeomFromText(LINESTRING('" << x3 << " " << y3 << "," << x4 << " " << y4 << ")')"
 222             << ");"
 223             << std::endl;
 224     */
 225
 226
 227     // Now use generic intersection.
 228     std::vector<P> out;
 229     bg::detail::intersection::intersection_insert<P>(s12, s34, std::back_inserter(out));
 230
 231     BOOST_CHECK_EQUAL(boost::size(out), expected_count);
 232
 233     if (expected_x1 != -99 && expected_y1 != -99
 234         && is.count >= 1
 235         && boost::size(out) >= 1)
 236     {
 237         BOOST_CHECK_CLOSE(bg::get<0>(out[0]),
 238                 coordinate_type(expected_x1), 0.001);
 239         BOOST_CHECK_CLOSE(bg::get<1>(out[0]),
 240                 coordinate_type(expected_y1), 0.001);
 241     }
 242     if (expected_x2 != -99 && expected_y2 != -99
 243         && is.count >= 2
 244         && boost::size(out) >= 2)
 245     {
 246         BOOST_CHECK_CLOSE(bg::get<0>(out[1]),
 247                 coordinate_type(expected_x2), 0.001);
 248         BOOST_CHECK_CLOSE(bg::get<1>(out[1]),
 249                 coordinate_type(expected_y2), 0.001);
 250     }
 251 }
 252
 253
 254 template <typename P>
 255 void test_all()
 256 {
 257     test_segment_intersection<P>( 1, 0,2, 2,0, 0,0, 2,2, "0-1--0102",
 258         "i", "R", "L", 1, 1);
 259     test_segment_intersection<P>( 2, 2,2, 3,1, 0,0, 2,2, "--1-00102",
 260         "a", "R", "R", 2, 2);
 261     test_segment_intersection<P>( 3, 3,1, 2,2, 0,0, 2,2, "--1-00102",
 262         "t", "R", "L", 2, 2);
 263     test_segment_intersection<P>( 4, 0,2, 1,1, 0,0, 2,2, "--10-0102",
 264         "m", "L", "L", 1, 1);
 265 #ifdef REPORT
 266     std::cout << std::endl;
 267 #endif
 268
 269     test_segment_intersection<P>( 5, 1,1, 0,2, 0,0, 2,2, "--10-0102",
 270         "s", "L", "R", 1, 1);
 271     test_segment_intersection<P>( 6, 0,2, 2,0, 0,0, 1,1, "-01--0102",
 272         "m", "R", "R", 1, 1);
 273     test_segment_intersection<P>( 7, 2,0, 0,2, 0,0, 1,1, "-01--0102",
 274         "m", "L", "L", 1, 1);
 275     test_segment_intersection<P>( 8, 2,3, 3,2, 0,0, 2,2, "--1--0102",
 276         "d");
 277 #ifdef REPORT
 278     std::cout << std::endl;
 279 #endif
 280
 281     test_segment_intersection<P>( 9, 0,0, 2,2, 0,0, 2,2, "1---0---2",
 282         "e", "-", "-", 0, 0, 2, 2);
 283     test_segment_intersection<P>(10, 2,2, 0,0, 0,0, 2,2, "1---0---2",
 284         "e", "-", "-", 2, 2, 0, 0);
 285     test_segment_intersection<P>(11, 1,1, 3,3, 0,0, 2,2, "1010-0102",
 286         "c", "-", "-", 1, 1, 2, 2);
 287     test_segment_intersection<P>(12, 3,3, 1,1, 0,0, 2,2, "1010-0102",
 288         "c", "-", "-", 1, 1, 2, 2);
 289 #ifdef REPORT
 290     std::cout << std::endl;
 291 #endif
 292
 293     test_segment_intersection<P>(13, 0,2, 2,2, 2,1, 2,3, "--10-0102",
 294         "m", "L", "L", 2, 2);
 295     test_segment_intersection<P>(14, 2,2, 2,4, 2,0, 2,2, "--1-00102",
 296         "C", "-", "-", 2, 2);
 297     test_segment_intersection<P>(15, 2,2, 2,4, 2,0, 2,1, "--1--0102",
 298         "d");
 299     test_segment_intersection<P>(16, 2,4, 2,2, 2,0, 2,1, "--1--0102",
 300         "d");
 301
 302     test_segment_intersection<P>(17, 2,1, 2,3, 2,2, 2,4, "1010-0102",
 303         "c", "-", "-", 2, 3, 2, 2);
 304     test_segment_intersection<P>(18, 2,3, 2,1, 2,2, 2,4, "1010-0102",
 305         "c", "-", "-", 2, 3, 2, 2);
 306     test_segment_intersection<P>(19, 0,2, 2,2, 4,2, 2,2, "--1-00102",
 307         "C", "-", "-", 2, 2);
 308     test_segment_intersection<P>(20, 0,2, 2,2, 2,2, 4,2, "--1-00102",
 309         "C", "-", "-", 2, 2);
 310
 311     test_segment_intersection<P>(21, 1,2, 3,2, 2,1, 2,3, "0-1--0102",
 312         "i", "R", "L", 2, 2);
 313     test_segment_intersection<P>(22, 2,4, 2,1, 2,1, 2,3, "101-00--2",
 314         "c", "-", "-", 2, 1, 2, 3);
 315     test_segment_intersection<P>(23, 2,4, 2,1, 2,3, 2,1, "101-00--2",
 316         "c", "-", "-", 2, 3, 2, 1);
 317     test_segment_intersection<P>(24, 1,1, 3,3, 0,0, 3,3, "1--00-102",
 318         "c", "-", "-", 1, 1, 3, 3);
 319
 320     test_segment_intersection<P>(25, 2,0, 2,4, 2,1, 2,3, "101--0--2",
 321         "c", "-", "-", 2, 1, 2, 3);
 322     test_segment_intersection<P>(26, 2,0, 2,4, 2,3, 2,1, "101--0--2",
 323         "c", "-", "-", 2, 3, 2, 1);
 324     test_segment_intersection<P>(27, 0,0, 4,4, 1,1, 3,3, "101--0--2",
 325         "c", "-", "-", 1, 1, 3, 3);
 326     test_segment_intersection<P>(28, 0,0, 4,4, 3,3, 1,1, "101--0--2",
 327         "c", "-", "-", 3, 3, 1, 1);
 328
 329     test_segment_intersection<P>(29, 1,1, 3,3, 0,0, 4,4, "1--0--102",
 330         "c", "-", "-", 1, 1, 3, 3);
 331     test_segment_intersection<P>(30, 0,0, 2,2, 2,2, 3,1, "--1-00102",
 332         "a", "R", "R", 2, 2);
 333     test_segment_intersection<P>(31, 0,0, 2,2, 2,2, 1,3, "--1-00102",
 334         "a", "L", "L", 2, 2);
 335     test_segment_intersection<P>(32, 0,0, 2,2, 1,1, 2,0, "-01--0102",
 336         "s", "L", "R", 1, 1);
 337
 338     test_segment_intersection<P>(33, 0,0, 2,2, 1,1, 0,2, "-01--0102",
 339         "s", "R", "L", 1, 1);
 340     test_segment_intersection<P>(34, 2,2, 1,3, 0,0, 2,2, "--1-00102",
 341         "a", "L", "L", 2, 2);
 342     test_segment_intersection<P>(35, 2,2, 3,1, 0,0, 2,2, "--1-00102",
 343         "a", "R", "R", 2, 2);
 344     test_segment_intersection<P>(36, 0,0, 2,2, 0,2, 1,1, "-01--0102",
 345         "m", "L", "L", 1, 1);
 346
 347     test_segment_intersection<P>(37, 0,0, 2,2, 2,0, 1,1, "-01--0102",
 348         "m", "R", "R", 1, 1);
 349     test_segment_intersection<P>(38, 1,1, 0,2, 0,0, 2,2, "--10-0102",
 350         "s", "L", "R", 1, 1);
 351     test_segment_intersection<P>(39, 1,1, 2,0, 0,0, 2,2, "--10-0102",
 352         "s", "R", "L", 1, 1);
 353     test_segment_intersection<P>(40, 2,0, 1,1, 0,0, 2,2, "--10-0102",
 354         "m", "R", "R", 1, 1);
 355
 356     test_segment_intersection<P>(41, 1,2, 0,2, 2,2, 0,2, "1--00-102",
 357         "c", "-", "-", 1, 2, 0, 2);
 358     test_segment_intersection<P>(42, 2,1, 1,1, 2,2, 0,2, "--1--0102",
 359         "p");
 360     test_segment_intersection<P>(43, 4,1, 3,1, 2,2, 0,2, "--1--0102",
 361         "p");
 362     test_segment_intersection<P>(44, 4,2, 3,2, 2,2, 0,2, "--1--0102",
 363         "d");
 364
 365     test_segment_intersection<P>(45, 2,0, 0,2, 0,0, 2,2, "0-1--0102",
 366         "i", "L", "R", 1, 1);
 367
 368     // In figure: times 2
 369     test_segment_intersection<P>(46, 8,2, 4,6, 0,0, 8, 8, "0-1--0102",
 370         "i", "L", "R", 5, 5);
 371 }
 372
 373 int test_main(int, char* [])
 374 {
 375     std::cout << "Note this test is out-of-date and either obsolete or should be updated" << std::endl;
 376     test_all<boost::tuple<double, double> >();
 377     test_all<bg::model::point<float, 2, bg::cs::cartesian> >();
 378     test_all<bg::model::point<double, 2, bg::cs::cartesian> >();
 379     return 0;
 380 }