ceph/src/boost/libs/geometry/test/algorithms/convex_hull/convex_hull_robust.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2020 Oracle and/or its affiliates.
   5 // Contributed and/or modified by Vissarion Fisikopoulos, on behalf of Oracle
   6
   7 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #include <cstddef>
  12 #include <string>
  13
  14 #include "test_convex_hull.hpp"
  15
  16 #include <boost/geometry/geometries/geometries.hpp>
  17 #include <boost/geometry/geometries/point_xy.hpp>
  18
  19 #include <boost/multiprecision/cpp_dec_float.hpp>
  20
  21 template <typename CT, typename CTmp>
  22 void test_all()
  23 {
  24     typedef bg::model::d2::point_xy<CT> P;
  25     typedef bg::model::d2::point_xy<CTmp> Pmp;
  26
  27     // from sample polygon, with concavity
  28     auto polygon_wkt0 = "polygon((2.0 1.3, 2.4 1.7, 2.8 1.8, 3.4 1.2, 3.7 1.6,\
  29         3.4 2.0, 4.1 3.0, 5.3 2.6, 5.4 1.2, 4.9 0.8, 2.9 0.7,2.0 1.3))";
  30     test_geometry<bg::model::polygon<P>, robust_cartesian>(
  31         polygon_wkt0, 12, 8, 5.245);
  32     test_geometry<bg::model::polygon<P>, non_robust_cartesian_sbt>(
  33         polygon_wkt0, 12, 8, 5.245);
  34     test_geometry<bg::model::polygon<P>, non_robust_cartesian_fast>(
  35         polygon_wkt0, 12, 8, 5.245);
  36     test_geometry<bg::model::polygon<Pmp>, non_robust_cartesian_sbt>(
  37         polygon_wkt0, 12, 8, 5.245);
  38
  39     // some colinear cases are ok with non robust predicate
  40     auto polygon_wkt1 = "polygon((0.50000000000001621 0.50000000000001243,\
  41         7.3000000000000173 7.3000000000000167,\
  42         24.00000000000005 24.000000000000053,\
  43         24.000000000000068 24.000000000000071,\
  44         0 1,8 4,25 26,26 25,19 11))";
  45     test_geometry<bg::model::polygon<P>, robust_cartesian >(
  46         polygon_wkt1, 9, 7, 137.25);
  47     test_geometry<bg::model::polygon<P>, non_robust_cartesian_sbt >(
  48         polygon_wkt1, 9, 7, 137.25);
  49     test_geometry<bg::model::polygon<P>, non_robust_cartesian_fast >(
  50         polygon_wkt1, 9, 7, 137.25);
  51     test_geometry<bg::model::polygon<Pmp>, non_robust_cartesian_sbt >(
  52         polygon_wkt1, 9, 7, 137.25);
  53
  54     // slightly non-convex result but areas equal
  55     auto polygon_wkt2 = "polygon((27.643564356435643 -21.881188118811881,\
  56         83.366336633663366 15.544554455445542,\
  57         4.0 4.0,\
  58         73.415841584158414 8.8613861386138595,\
  59         27.643564356435643 -21.881188118811881))";
  60     test_geometry<bg::model::polygon<P>, robust_cartesian >(
  61         polygon_wkt2, 5, 4, 1163.5247524752476);
  62     test_geometry<bg::model::polygon<P>, non_robust_cartesian_sbt >(
  63         polygon_wkt2, 5, 5, 1163.5247524752476);
  64     test_geometry<bg::model::polygon<P>, non_robust_cartesian_fast >(
  65         polygon_wkt2, 5, 5, 1163.5247524752476);
  66     test_geometry<bg::model::polygon<Pmp>, non_robust_cartesian_sbt >(
  67         polygon_wkt2, 5, 4, 1163.5247524752476);
  68
  69     // wrong orientation / sign in area
  70     // here non_robust_cartesian_sbt computes wrong result with mp arithmetic
  71     // correct results double checked with CGAL 5.1
  72     auto polygon_wkt3 = "polygon((200.0 49.200000000000003,\
  73         100.0 49.600000000000001,\
  74         -233.33333333333334 50.93333333333333,\
  75         166.66666666666669 49.333333333333336,\
  76         200.0 49.200000000000003))";
  77     test_geometry<bg::model::polygon<P>, robust_cartesian, precise_cartesian >(
  78         polygon_wkt3, 5, 4, 1.4210854715202004e-14);
  79     test_geometry<bg::model::polygon<P>, non_robust_cartesian_sbt, precise_cartesian >(
  80         polygon_wkt3, 5, 4, -1.4210854715202004e-14);
  81     test_geometry<bg::model::polygon<P>, non_robust_cartesian_fast, precise_cartesian >(
  82         polygon_wkt3, 5, 4, -1.4210854715202004e-14);
  83     test_geometry<bg::model::polygon<Pmp>, non_robust_cartesian_sbt >(
  84         polygon_wkt3, 5, 5, 1.69333333333333265e-13);
  85
  86     // missing one point could lead in arbitrary large errors in area
  87     auto polygon_wkt4 = "polygon((0.10000000000000001 0.10000000000000001,\
  88         0.20000000000000001 0.20000000000000004,\
  89         0.79999999999999993 0.80000000000000004,\
  90         1.267650600228229e30 1.2676506002282291e30,\
  91         0.10000000000000001 0.10000000000000001))";
  92     test_geometry<bg::model::polygon<P>, robust_cartesian, precise_cartesian>(
  93         polygon_wkt4, 5, 5, -0.315);
  94     test_geometry<bg::model::polygon<P>, non_robust_cartesian_sbt, precise_cartesian>(
  95         polygon_wkt4, 5, 4, 0);
  96     test_geometry<bg::model::polygon<P>, non_robust_cartesian_fast, precise_cartesian>(
  97         polygon_wkt4, 5, 4, -0.015);
  98     test_geometry<bg::model::polygon<Pmp>, non_robust_cartesian_sbt>(
  99         polygon_wkt4, 5, 5, 3.472078301e+13);
 100 }
 101
 102
 103 int test_main(int, char* [])
 104 {
 105     using boost::multiprecision::cpp_dec_float_50;
 106     test_all<double, cpp_dec_float_50>();
 107
 108     return 0;
 109 }