ceph/src/boost/libs/geometry/test/algorithms/overlay/get_clusters.cpp

   1 // Boost.Geometry
   2 // Unit Test
   3
   4 // Copyright (c) 2021 Barend Gehrels, Amsterdam, the Netherlands.
   5
   6 // This file was modified by Oracle on 2021.
   7 // Modifications copyright (c) 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 <geometry_test_common.hpp>
  15
  16 #include <boost/geometry/algorithms/detail/overlay/get_clusters.hpp>
  17
  18 #include <boost/geometry/algorithms/area.hpp>
  19 #include <boost/geometry/algorithms/is_valid.hpp>
  20
  21 #include <boost/geometry/strategies/strategies.hpp>
  22 #include <boost/geometry/geometries/geometries.hpp>
  23 #include <boost/geometry/io/wkt/wkt.hpp>
  24
  25 #include <vector>
  26 #include <map>
  27
  28 template <typename Turn, typename Point>
  29 Turn make_turn(Point const& p)
  30 {
  31     Turn result;
  32     result.point = p;
  33     return result;
  34 }
  35
  36 template <typename Point>
  37 void do_test(std::string const& case_id,
  38              std::vector<Point> const& points,
  39              std::size_t expected_cluster_count)
  40 {
  41     using coor_type = typename bg::coordinate_type<Point>::type;
  42     using policy_type = bg::detail::no_rescale_policy;
  43     using turn_info = bg::detail::overlay::turn_info
  44         <
  45             Point,
  46             typename bg::detail::segment_ratio_type<Point, policy_type>::type
  47         >;
  48
  49     using cluster_type = std::map
  50         <
  51             bg::signed_size_type,
  52             bg::detail::overlay::cluster_info
  53         >;
  54
  55     std::vector<turn_info> turns;
  56     for (auto const& p : points)
  57     {
  58         turns.push_back(make_turn<turn_info>(p));
  59     }
  60
  61     cluster_type clusters;
  62     bg::detail::overlay::get_clusters(turns, clusters, policy_type());
  63     BOOST_CHECK_MESSAGE(expected_cluster_count == clusters.size(),
  64                         "Case: " << case_id
  65                         << " ctype: " << string_from_type<coor_type>::name()
  66                         << " expected: " << expected_cluster_count
  67                         << " detected: " << clusters.size());
  68 }
  69
  70 template <typename Point>
  71 void test_get_clusters(typename bg::coordinate_type<Point>::type eps)
  72 {
  73     do_test<Point>("no", {{1.0, 1.0}, {1.0, 2.0}}, 0);
  74     do_test<Point>("simplex", {{1.0, 1.0}, {1.0, 1.0}}, 1);
  75
  76     // Tests below come from realtime cases
  77     do_test<Point>("buffer1", {{2, 1},{12, 13},{6, 5},{8, 9},{1, 1},{2, 1},{1, 13},{2, 13},{5, 5},{6, 5},{5, 9},{6, 9},{13, 1},{12, 1},{13, 13},{12, 13},{9, 5},{8, 5},{9, 9},{8, 9},{1, 12},{5, 8},{1, 2},{5, 6},{1, 12},{5, 8},{13, 2},{9, 6},{13, 2},{9, 6},{13, 12},{9, 8}},
  78                    8);
  79     do_test<Point>("buffer2", {{2.72426406871, 1.7},{2.72426406871, 4.7},{2.3, 3.12426406871},{2.3, 3.7},{2.7, 2.72426406871},{2.7, 3.7},{2.72426406871, 3.7},{2.72426406871, 1.7},{0.7, 3.12426406871},{0.7, 1.7},{1.7, 0.7},{1.7, 2.3},{1.7, 2.7},{1.3, 2.3},{1.3, 2.7},{1.7, 5.72426406871},{1.7, 5.72426406871},{1.7, 4.7},{1.7, 5},{1.7, 4.3},{3.7, 3.72426406871},{3.72426406871, 3.7},{3.7, 3.7},{3.72426406871, 1.7},{3, 1.7},{3.7, 3.7},{3.7, 5.72426406871},{4.72426406871, 4.7},{3.7, 4.72426406871},{3.7, 4.72426406871},{3.7, 4.7},{3.7, 4.7},{3.7, 4.7},{3.7, 4.7},{3.7, 5},{3.7, 5.72426406871}},
  80                    6);
  81     do_test<Point>("buffer3", {{6.41421356237, 5},{6.41421356236, 5},{6.70710678119, 5.29289321881},{6.41421356237, 5},{6, 5},{6.41421356238, 5},{7, 5},{8, 10},{8.41421356237, 10},{8, 9.58578643763},{8.41421356237, 10},{7.41421356237, 9},{7.41421356237, 9},{7, 5.58578643763},{7, 5.58578643763},{6, 5},{6, 5},{6, 5},{6, 5},{6, 5},{6, 6},{4, 6},{4, 6},{3.41421356237, 3},{3, 5},{6, 5},{5, 3},{4, 6},{4, 6},{4, 7},{4, 8},{10.9142135624, 5.5},{8, 5},{10.4142135624, 5},{8, 5},{8, 3.58578643763},{8, 5},{9.41421356237, 7},{9.41421356237, 7},{8.91421356237, 7.5},{10, 7},{8, 9},{7.41421356237, 9},{11, 7}},
  82                    8);
  83
  84     // Border cases
  85     do_test<Point>("borderx_no",  {{1, 1}, {1, 2}, {1 + eps * 10, 1}}, 0);
  86     do_test<Point>("borderx_yes", {{1, 1}, {1, 2}, {1 + eps, 1}}, 1);
  87     do_test<Point>("bordery_no",  {{1, 1}, {2, 1}, {1 + eps * 10, 1}}, 0);
  88     do_test<Point>("bordery_yes", {{1, 1}, {2, 1}, {1 + eps, 1}}, 1);
  89 }
  90
  91 int test_main(int, char* [])
  92 {
  93     using fp = bg::model::point<float, 2, bg::cs::cartesian>;
  94     using dp = bg::model::point<double, 2, bg::cs::cartesian>;
  95     using ep = bg::model::point<long double, 2, bg::cs::cartesian>;
  96     test_get_clusters<fp>(1.0e-4);
  97     test_get_clusters<dp>(1.0e-13);
  98     test_get_clusters<ep>(1.0e-16);
  99     return 0;
 100 }