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 #include <geometry_test_common.hpp>
  22
  23 #include <boost/geometry/algorithms/assign.hpp>
  24
  25 #include <boost/geometry/strategies/cartesian/intersection.hpp>
  26 #include <boost/geometry/strategies/intersection_result.hpp>
  27
  28 #include <boost/geometry/policies/relate/intersection_points.hpp>
  29 #include <boost/geometry/policies/relate/direction.hpp>
  30 #include <boost/geometry/policies/relate/tupled.hpp>
  31
  32 #include <boost/geometry/algorithms/intersection.hpp>
  33
  34
  35 #include <boost/geometry/geometries/point.hpp>
  36 #include <boost/geometry/geometries/segment.hpp>
  37 #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
  38
  39 BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian);
  40
  41
  42 template <typename P>
  43 static void test_segment_intersection(int caseid,
  44                 int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4,
  45                 char expected_how,
  46                 int expected_x1 = -99, int expected_y1 = -99,
  47                 int expected_x2 = -99, int expected_y2 = -99)
  48 {
  49     using namespace boost::geometry;
  50
  51     typedef typename bg::coordinate_type<P>::type coordinate_type;
  52     typedef bg::model::referring_segment<const P> segment_type;
  53
  54     P p1, p2, p3, p4;
  55     bg::assign_values(p1, x1, y1);
  56     bg::assign_values(p2, x2, y2);
  57     bg::assign_values(p3, x3, y3);
  58     bg::assign_values(p4, x4, y4);
  59
  60     segment_type s12(p1,p2);
  61     segment_type s34(p3,p4);
  62
  63     std::size_t expected_count = 0;
  64
  65     if (expected_x1 != -99 && expected_y1 != -99)
  66     {
  67         expected_count++;
  68     }
  69     if (expected_x2 != -99 && expected_y2 != -99)
  70     {
  71         expected_count++;
  72     }
  73
  74     // Using intersection_insert
  75
  76     std::vector<P> out;
  77     bg::detail::intersection::intersection_insert<P>(s12, s34, std::back_inserter(out));
  78
  79     // Using strategy
  80     typedef bg::detail::no_rescale_policy rescale_policy_type;
  81     rescale_policy_type rescale_policy;
  82     typedef typename bg::segment_ratio_type<P, rescale_policy_type>::type ratio_type;
  83     typedef bg::segment_intersection_points
  84     <
  85         P,
  86         ratio_type
  87     > result_type;
  88     typedef bg::policies::relate::segments_intersection_points
  89         <
  90             result_type
  91         > points_policy_type;
  92
  93     result_type is
  94         = bg::strategy::intersection::cartesian_segments<>
  95             ::apply(s12, s34, points_policy_type(), rescale_policy, p1, p2, p3, p4);
  96
  97     bg::policies::relate::direction_type dir
  98         = bg::strategy::intersection::cartesian_segments<>
  99             ::apply(s12, s34, bg::policies::relate::segments_direction(),
 100                     rescale_policy, p1, p2, p3, p4);
 101
 102     BOOST_CHECK_EQUAL(boost::size(out), expected_count);
 103     BOOST_CHECK_EQUAL(is.count, expected_count);
 104     BOOST_CHECK_MESSAGE(dir.how == expected_how,
 105             caseid
 106             << " how: detected: " << dir.how
 107             << " expected: "  << expected_how);
 108
 109     if (expected_count == 2
 110             && is.count == 2
 111             && boost::size(out) == 2)
 112     {
 113         // Two intersection points, reverse expectation if necessary
 114         bool const first_matches
 115                 = std::fabs(bg::get<0>(out[0]) - expected_x1) < 1.0e-6
 116                && std::fabs(bg::get<1>(out[0]) - expected_y1) < 1.0e-6;
 117
 118         if (! first_matches)
 119         {
 120             std::swap(expected_x1, expected_x2);
 121             std::swap(expected_y1, expected_y2);
 122         }
 123     }
 124
 125     if (expected_x1 != -99 && expected_y1 != -99
 126         && boost::size(out) >= 1)
 127     {
 128
 129         BOOST_CHECK_CLOSE(bg::get<0>(out[0]), coordinate_type(expected_x1), 0.001);
 130         BOOST_CHECK_CLOSE(bg::get<1>(out[0]), coordinate_type(expected_y1), 0.001);
 131
 132         BOOST_CHECK_CLOSE(bg::get<0>(is.intersections[0]), expected_x1, 0.001);
 133         BOOST_CHECK_CLOSE(bg::get<1>(is.intersections[0]), expected_y1, 0.001);
 134
 135     }
 136     if (expected_x2 != -99 && expected_y2 != -99
 137         && boost::size(out) >= 2)
 138     {
 139         BOOST_CHECK_CLOSE(bg::get<0>(out[1]), coordinate_type(expected_x2), 0.001);
 140         BOOST_CHECK_CLOSE(bg::get<1>(out[1]), coordinate_type(expected_y2), 0.001);
 141
 142         BOOST_CHECK_CLOSE(bg::get<0>(is.intersections[1]), expected_x2, 0.001);
 143         BOOST_CHECK_CLOSE(bg::get<1>(is.intersections[1]), expected_y2, 0.001);
 144     }
 145 }
 146
 147
 148 template <typename P>
 149 void test_all()
 150 {
 151     test_segment_intersection<P>( 1, 0,2, 2,0, 0,0, 2,2, 'i', 1, 1);
 152     test_segment_intersection<P>( 2, 2,2, 3,1, 0,0, 2,2, 'a', 2, 2);
 153     test_segment_intersection<P>( 3, 3,1, 2,2, 0,0, 2,2, 't', 2, 2);
 154     test_segment_intersection<P>( 4, 0,2, 1,1, 0,0, 2,2, 'm', 1, 1);
 155
 156     test_segment_intersection<P>( 5, 1,1, 0,2, 0,0, 2,2, 's', 1, 1);
 157     test_segment_intersection<P>( 6, 0,2, 2,0, 0,0, 1,1, 'm', 1, 1);
 158     test_segment_intersection<P>( 7, 2,0, 0,2, 0,0, 1,1, 'm', 1, 1);
 159     test_segment_intersection<P>( 8, 2,3, 3,2, 0,0, 2,2, 'd');
 160
 161     test_segment_intersection<P>( 9, 0,0, 2,2, 0,0, 2,2, 'e', 0, 0, 2, 2);
 162     test_segment_intersection<P>(10, 2,2, 0,0, 0,0, 2,2, 'e', 2, 2, 0, 0);
 163     test_segment_intersection<P>(11, 1,1, 3,3, 0,0, 2,2, 'c', 1, 1, 2, 2);
 164     test_segment_intersection<P>(12, 3,3, 1,1, 0,0, 2,2, 'c', 1, 1, 2, 2);
 165
 166     test_segment_intersection<P>(13, 0,2, 2,2, 2,1, 2,3, 'm', 2, 2);
 167     test_segment_intersection<P>(14, 2,2, 2,4, 2,0, 2,2, 'a', 2, 2);
 168     test_segment_intersection<P>(15, 2,2, 2,4, 2,0, 2,1, 'd');
 169     test_segment_intersection<P>(16, 2,4, 2,2, 2,0, 2,1, 'd');
 170
 171     test_segment_intersection<P>(17, 2,1, 2,3, 2,2, 2,4, 'c', 2, 2, 2, 3);
 172     test_segment_intersection<P>(18, 2,3, 2,1, 2,2, 2,4, 'c', 2, 3, 2, 2);
 173     test_segment_intersection<P>(19, 0,2, 2,2, 4,2, 2,2, 't', 2, 2);
 174     test_segment_intersection<P>(20, 0,2, 2,2, 2,2, 4,2, 'a', 2, 2);
 175
 176     test_segment_intersection<P>(21, 1,2, 3,2, 2,1, 2,3, 'i', 2, 2);
 177     test_segment_intersection<P>(22, 2,4, 2,1, 2,1, 2,3, 'c', 2, 1, 2, 3);
 178     test_segment_intersection<P>(23, 2,4, 2,1, 2,3, 2,1, 'c', 2, 3, 2, 1);
 179     test_segment_intersection<P>(24, 1,1, 3,3, 0,0, 3,3, 'c', 1, 1, 3, 3);
 180
 181     test_segment_intersection<P>(25, 2,0, 2,4, 2,1, 2,3, 'c', 2, 1, 2, 3);
 182     test_segment_intersection<P>(26, 2,0, 2,4, 2,3, 2,1, 'c', 2, 3, 2, 1);
 183     test_segment_intersection<P>(27, 0,0, 4,4, 1,1, 3,3, 'c', 1, 1, 3, 3);
 184     test_segment_intersection<P>(28, 0,0, 4,4, 3,3, 1,1, 'c', 3, 3, 1, 1);
 185
 186     test_segment_intersection<P>(29, 1,1, 3,3, 0,0, 4,4, 'c', 1, 1, 3, 3);
 187     test_segment_intersection<P>(30, 0,0, 2,2, 2,2, 3,1, 'a', 2, 2);
 188     test_segment_intersection<P>(31, 0,0, 2,2, 2,2, 1,3, 'a', 2, 2);
 189     test_segment_intersection<P>(32, 0,0, 2,2, 1,1, 2,0, 's', 1, 1);
 190
 191     test_segment_intersection<P>(33, 0,0, 2,2, 1,1, 0,2, 's', 1, 1);
 192     test_segment_intersection<P>(34, 2,2, 1,3, 0,0, 2,2, 'a', 2, 2);
 193     test_segment_intersection<P>(35, 2,2, 3,1, 0,0, 2,2, 'a', 2, 2);
 194     test_segment_intersection<P>(36, 0,0, 2,2, 0,2, 1,1, 'm', 1, 1);
 195
 196     test_segment_intersection<P>(37, 0,0, 2,2, 2,0, 1,1, 'm', 1, 1);
 197     test_segment_intersection<P>(38, 1,1, 0,2, 0,0, 2,2, 's', 1, 1);
 198     test_segment_intersection<P>(39, 1,1, 2,0, 0,0, 2,2, 's', 1, 1);
 199     test_segment_intersection<P>(40, 2,0, 1,1, 0,0, 2,2, 'm', 1, 1);
 200
 201     test_segment_intersection<P>(41, 1,2, 0,2, 2,2, 0,2, 'c', 1, 2, 0, 2);
 202     test_segment_intersection<P>(42, 2,1, 1,1, 2,2, 0,2, 'd');
 203     test_segment_intersection<P>(43, 4,1, 3,1, 2,2, 0,2, 'd');
 204     test_segment_intersection<P>(44, 4,2, 3,2, 2,2, 0,2, 'd');
 205
 206     test_segment_intersection<P>(45, 2,0, 0,2, 0,0, 2,2, 'i', 1, 1);
 207
 208     // In figure: times 2
 209     test_segment_intersection<P>(46, 8,2, 4,6, 0,0, 8, 8, 'i', 5, 5);
 210 }
 211
 212 int test_main(int, char* [])
 213 {
 214 #if !defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
 215     test_all<boost::tuple<double, double> >();
 216     test_all<bg::model::point<float, 2, bg::cs::cartesian> >();
 217 #endif
 218     test_all<bg::model::point<double, 2, bg::cs::cartesian> >();
 219
 220     return 0;
 221 }