search

CGAL / cgal

The public CGAL repository, see the README below
https://github.com/CGAL/cgal#readme
Other
4.9k stars 1.38k forks source link

The Minkowski Sum results using minkowski_sum_by_decomposition_2() lose holes in some rare cases #5839

Open KaimoHu opened 3 years ago

KaimoHu commented 3 years ago

Issue Details

We demonstrates (possibly) a bug of Minkowski Sum calculation using minkowski_sum_by_decomposition_2() implemented in CGAL 5.2.2. We construct a Polygon_with_holes_2, which contains 1 big hole and 9 small holes. In release mode, when we calculate the exterior padding with value 2.0 using Minkowski Sum, the result contains no holes. In our intuition, the result should contain 1 hole. We further test it in debug mode, and found the “Debug Assertion Failed” with expression : “cannot increment value - initialized deque iterator”.

Source Code

#include <iostream>
#include <string>
#include <vector>

#include <CGAL/Gmpq.h>
#include <CGAL/Lazy_exact_nt.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_set_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/draw_polygon_with_holes_2.h>
#include <CGAL/minkowski_sum_2.h>
#include <CGAL/Small_side_angle_bisector_decomposition_2.h>
#include <CGAL/Polygon_vertical_decomposition_2.h>

#include <boost/algorithm/string.hpp>

using KernelEE = CGAL::Simple_cartesian<CGAL::Lazy_exact_nt<CGAL::Gmpq>>;
using NumberEE = KernelEE::FT;
using Point2EE = KernelEE::Point_2;
using PolygonEE = CGAL::Polygon_2<KernelEE>;
using PolygonWHEE = CGAL::Polygon_with_holes_2<KernelEE>;
using PolygonDecompEE = CGAL::Small_side_angle_bisector_decomposition_2<KernelEE>;
using PolygonWHDecompEE = CGAL::Polygon_vertical_decomposition_2<KernelEE>;

NumberEE StrToEE(const std::string& str, int base = 36) {
  mpq_t mpq;
  mpq_init(mpq);
  mpq_set_str(mpq, str.c_str(), base);
  return NumberEE(std::move(mpq));
}

void ReadPolygonWHsExactly(std::istream& is, std::vector<PolygonWHEE>& pwhs) {
  pwhs.clear();
  PolygonEE temp_plg;
  PolygonWHEE temp_pwh;
  std::string line;
  std::vector<std::string> tokens;

  auto ConstructPolygon = [&tokens, &temp_plg]() {
    for (size_t i = 0; i < tokens.size(); i += 2) {
      NumberEE x = StrToEE(tokens[i]);
      NumberEE y = StrToEE(tokens[i + 1]);
      temp_plg.push_back(Point2EE(x, y));
    }
  };

  bool is_outer_boundary = true;
  while (!is.eof()) {
    std::getline(is, line);
    boost::trim(line);
    if (line.length() == 0) {  // a polygonwh has been constructed
      pwhs.push_back(temp_pwh);
      temp_pwh.clear();
      is_outer_boundary = true;
      continue;
    }
    tokens.clear();
    boost::split(tokens, line, boost::is_any_of(" "));
    temp_plg.clear();
    ConstructPolygon();
    if (is_outer_boundary) {
      temp_pwh.outer_boundary() = temp_plg;
      is_outer_boundary = false;
    } else {
      temp_pwh.add_hole(temp_plg);
    }
  }
}

bool GetPolygonWHData(PolygonWHEE& polygonwh);

PolygonWHEE ExteriorPaddingOfPolygonWHEE(const PolygonWHEE& polygonwh, double padding) {
  std::vector<Point2EE> points{
      {-padding, padding}, {-padding, -padding}, {padding, -padding}, {padding, padding}};
  PolygonEE polygon(points.begin(), points.end());  // it is a square
  // return CGAL::minkowski_sum_2(polygonwh, polygon);
  PolygonDecompEE polygon_decomp;
  PolygonWHDecompEE polygonwh_decomp;
  return CGAL::minkowski_sum_2(polygonwh, polygon, polygonwh_decomp, polygon_decomp);
}

void TestMinkowskiSumMissingHolesBug() {
  typedef typename CGAL::Polygon_set_2<KernelEE>::Traits_2 Traits_2;
  PolygonWHEE original_polygonwh;
  bool succeeded = GetPolygonWHData(original_polygonwh);
  if (!succeeded) {
    std::cout << "The data.pwh is not found. Please provide it." << std::endl;
    return;
  }

  // step 1: output the information of original polygonwh.
  // We check whether the original polygonwh is valid, and also whether all the
  // holes in the original polygonwh are valid.
  {
    bool is_valid_pwh = CGAL::is_valid_polygon_with_holes(original_polygonwh, Traits_2());
    std::cout << "Original polygonwh: " << std::endl;
    std::cout << "  original polygonwh is valid? " << is_valid_pwh << std::endl;
    std::cout << "  number of holes: " << original_polygonwh.number_of_holes() << std::endl;
    int index = 0;
    for (const auto& hole : original_polygonwh.holes()) {
      PolygonEE polygon(hole);
      polygon.reverse_orientation();
      bool is_valid_polygon = CGAL::is_valid_polygon(polygon, Traits_2());
      std::cout << "    hole " << index++ << " is valid? " << is_valid_polygon << std::endl;
    }
    CGAL::draw(original_polygonwh);
  }

  // step 2: output the information of padded_polygonwh with 2.0.
  // The result has no holes. Although it is correct that the 9 small holes
  // disappear in the result, it is wrong that the 1 big hole is missing.
  {
    PolygonWHEE padded_pwh = ExteriorPaddingOfPolygonWHEE(original_polygonwh, 2.0);
    std::cout << "Padded polygonwh with 2.0: " << std::endl;
    bool is_valid_pwh = CGAL::is_valid_polygon_with_holes(padded_pwh, Traits_2());
    std::cout << "  padded polygonwh is valid? " << is_valid_pwh << std::endl;
    std::cout << "  number of holes: " << padded_pwh.number_of_holes() << std::endl;
    std::cout << "  the result is WRONG." << std::endl;
    CGAL::draw(padded_pwh);
  }

  std::cout << std::endl;
}

int main() {
  TestMinkowskiSumMissingHolesBug();
  return EXIT_SUCCESS;
}

bool GetPolygonWHData(PolygonWHEE& polygonwh) {
  auto GetPolygonData =
      [](const std::vector<std::pair<std::string, std::string>>& data) -> PolygonEE {
    PolygonEE polygon;
    for (const auto& pair : data) {
      polygon.push_back(Point2EE(StrToEE(pair.first), StrToEE(pair.second)));
    }
    return polygon;
  };
  // outer_boundary
  polygonwh.clear();
  std::vector<std::pair<std::string, std::string>> data;
  data.emplace_back("4a0rvu2vdbq5l3bby9ez2r67peoobmf14b/apje1coszud8s2m5jlpaylbefh5niznk",
                    "xtbme075613hi46jdg56mljlz1wcm64np/5crp0ocehx6me1b2rsunhanp7qktrhts");
  data.emplace_back("69mced0o87xom5p/fklk448oj5v5s", "36a7qyvjb8ppx3n/fklk448oj5v5s");
  data.emplace_back("79bjhicr002sg8d/fklk448oj5v5s", "3lcwz1t4r0kpy37/fklk448oj5v5s");
  data.emplace_back("79bjhicr002sg8d/fklk448oj5v5s", "3lcx3346wt197hp/fklk448oj5v5s");
  data.emplace_back("77082eagayptood/fklk448oj5v5s", "3qnht8xng6hl1d9/fklk448oj5v5s");
  data.emplace_back("7707ycze569af9v/fklk448oj5v5s", "3qnht8xng6hl1d9/fklk448oj5v5s");
  data.emplace_back("2mr05wpjpmmev7yq0tcnehrd1hhnzmpez1/6lmw4ioedxvnghz4tveauk66fooyguf4",
                    "1esny84qnlm1pyuwths2p49nkwgjv83nzb/6lmw4ioedxvnghz4tveauk66fooyguf4");
  data.emplace_back("1a44ncaulek8ossylaswt4a59lbh1k87v1/3ag0ggpisjjxbeugx9rxy7t4ph37mzgg",
                    "1ki9qgo2mdis98bgt2oabzqayq6xbav60h/6kw0wxf1l33umtoxujjvwfm9ey6f9yww");
  data.emplace_back("70aqvd3irbqkm5p/fklk448oj5v5s", "480wdqrmi9xevo3/fklk448oj5v5s");
  data.emplace_back("70aqvd3irbqkm5p/fklk448oj5v5s", "480whs2oo2dy52l/fklk448oj5v5s");
  data.emplace_back("6xivkvxsc4gw5d9/fklk448oj5v5s", "4d62gn5m7nbdl4d/fklk448oj5v5s");
  data.emplace_back("6xivgumq6c0cvyr/fklk448oj5v5s", "4d62gn5m7nbdl4d/fklk448oj5v5s");
  data.emplace_back("8e8c3y3vr8x5b31zye99apv5zjnnxex5/lu7zwaa5smzvf8vb8fbs9to9xnt9fk",
                    "5etznokhk19f95nhgqx28snp0zdpr2pb/lu7zwaa5smzvf8vb8fbs9to9xnt9fk");
  data.emplace_back("60xb2u2t0ev7sj1/fklk448oj5v5s", "3vp7edfwihqeker/fklk448oj5v5s");
  data.emplace_back("60xb2u2t0ev7sj1/fklk448oj5v5s", "3vp7ieqyoa6xtt9/fklk448oj5v5s");
  data.emplace_back("5thdpeckh68k4dp/fklk448oj5v5s", "49f82o2udtxc3sd/fklk448oj5v5s");
  data.emplace_back("5thdld1ibds0uz7/fklk448oj5v5s", "49f82o2udtxc3sd/fklk448oj5v5s");
  data.emplace_back("6qs9e20ma9fqq5rj8riveq5cd5xo5hc0l/i67le4nqriqeuc6at5tv38j99bjcwsg",
                    "4y4n0wz4tmztnhbefck0r2daplc5d5w0z/i67le4nqriqeuc6at5tv38j99bjcwsg");
  data.emplace_back("6kw2hzd5jzql54d/fklk448oj5v5s", "4ygg81oau96glw3/fklk448oj5v5s");
  data.emplace_back("6kw2hzd5jzql54d/fklk448oj5v5s", "4yggc2zd01mzval/fklk448oj5v5s");
  data.emplace_back("6f7kes8k0090ugd/fklk448oj5v5s", "54p2ickt0m2j6st/fklk448oj5v5s");
  data.emplace_back("6f7kaqxhu7shl1v/fklk448oj5v5s", "54p2ickt0m2j6st/fklk448oj5v5s");
  data.emplace_back("5mld2mwxi0h3r2r/fklk448oj5v5s", "4f1fbwy2cxgm7fx/fklk448oj5v5s");
  data.emplace_back("b55oh4phk7ia84ysr8z92yf2nxhfwuw7/v7isycdbmlwffph0jd0xg1ryjbe3gg",
                    "8sbumvjwwyknjnf7ycl7gx32u31qupn3/v7isycdbmlwffph0jd0xg1ryjbe3gg");
  data.emplace_back("a2kdy32b7mnnnc8amw9j7uejiv24aak4n/s9zspxgvbv9rin4yx0gsl9lkoon5534",
                    "83m4weegfrwlnzcqojki9v58ut2t1ed6x/s9zspxgvbv9rin4yx0gsl9lkoon5534");
  data.emplace_back("5kvri7xkgxxslyl/fklk448oj5v5s", "5iz9um5dd0o3mj7/fklk448oj5v5s");
  data.emplace_back("5kvri7xkgxxslyl/fklk448oj5v5s", "5iz9yngfit4mvxp/fklk448oj5v5s");
  data.emplace_back("5c9euuddh59pelp/fklk448oj5v5s", "5j8e1g61dvtqtyl/fklk448oj5v5s");
  data.emplace_back("5apuzkjr40nksa5/fklk448oj5v5s", "5j9wvheegi2l165/fklk448oj5v5s");
  data.emplace_back("4uze9zh5968rhv1/fklk448oj5v5s", "5jodk9871dgcq3x/fklk448oj5v5s");
  data.emplace_back("4tfv2m1g9n3v0h9/fklk448oj5v5s", "5jpbqy5ruc3jr59/fklk448oj5v5s");
  data.emplace_back("4nzxtbpjt0cmotp/fklk448oj5v5s", "5jsnj8tz3slfpd9/fklk448oj5v5s");
  data.emplace_back("4lqunkmfpfabb59/fklk448oj5v5s", "5ju11ozeq8bfl0t/fklk448oj5v5s");
  data.emplace_back("46crig0vh80ipt9/fklk448oj5v5s", "5k25ocbwnv7271p/fklk448oj5v5s");
  data.emplace_back("46creeptbfjzger/fklk448oj5v5s", "5k25ocbwnv7271p/fklk448oj5v5s");
  data.emplace_back("443glyzh9kihyvn/fklk448oj5v5s", "5k1vme0y7pe7qct/fklk448oj5v5s");
  data.emplace_back("3ycmcum27p2q0ur/fklk448oj5v5s", "5k0yxrzx2fll63x/fklk448oj5v5s");
  data.emplace_back("3ycmcum27p2q0ur/fklk448oj5v5s", "5k0ytqouwn51wpf/fklk448oj5v5s");
  data.emplace_back("2q5cvexldve4ejevzz11sot6sn1vzrjyj3/apyudfg9dczs6q436uwk9zq69t3l3y0w",
                    "337gx0odhefnknpk0u8i15ue23p8wf5ilt/apyudfg9dczs6q436uwk9zq69t3l3y0w");
  data.emplace_back("3qj3y279i9cpcr7/fklk448oj5v5s", "4gyif12d3rgvk19/fklk448oj5v5s");
  data.emplace_back("ltvhcp50l7b8t1pbldmgr4hs4w69uxh0t/2of4bi2u1gksbw0eii946d276uvn0f7k",
                    "6t5hick51154ey3lngpr00p6uh0kotixz/o3s2vipid572z03mmka1l9jsppwr3sw");
  data.emplace_back("32uj6gu972q6xwt/fklk448oj5v5s", "5di3jsg4ou6nk19/fklk448oj5v5s");
  data.emplace_back("32uj2fj71a9noib/fklk448oj5v5s", "5di3jsg4ou6nk19/fklk448oj5v5s");
  data.emplace_back("2xmbm7gofvku09f/fklk448oj5v5s", "5b3uqlg399w2w4t/fklk448oj5v5s");
  data.emplace_back("2vkdu5llgx3pxhv/fklk448oj5v5s", "5a5x6t5w17xs1f1/fklk448oj5v5s");
  data.emplace_back("2hoowe52src2b4j/fklk448oj5v5s", "53hhszcbpjejmlp/fklk448oj5v5s");
  data.emplace_back("2fnnx9lmm76295f/fklk448oj5v5s", "52i584nftvpmn1p/fklk448oj5v5s");
  data.emplace_back("2ar99561vapiuoj/fklk448oj5v5s", "504nrzc32i7bvhp/fklk448oj5v5s");
  data.emplace_back("29d9lw37mkcczwz/fklk448oj5v5s", "4zgf72sc8wn3xgt/fklk448oj5v5s");
  data.emplace_back("1v9on7blvz7vx77/fklk448oj5v5s", "4sgfjl8r1w1pqgd/fklk448oj5v5s");
  data.emplace_back("1tvzuhovyc2fc2b/fklk448oj5v5s", "4rrla2w6xgfqpm5/fklk448oj5v5s");
  data.emplace_back("1m6ujqk3my1jy6r/fklk448oj5v5s", "4nw65io17viitd9/fklk448oj5v5s");
  data.emplace_back("1m6ujqk3my1jy6r/fklk448oj5v5s", "4nw61hcz231zjyr/fklk448oj5v5s");
  data.emplace_back("23iiqn8fy90e6kz/fklk448oj5v5s", "3poxr4tiul8898z/fklk448oj5v5s");
  data.emplace_back("1h3l0rcyg0om7fczue7l9mbe1g2usems3/auilf7r2qedk4hmylmrqmu12amvlgxs",
                    "2jabvvdvzgpxoipi4dpr85zmpeasjyxur/auilf7r2qedk4hmylmrqmu12amvlgxs");
  data.emplace_back("21kkt2j5wor6jhp/fklk448oj5v5s", "3nrjcmb2x4qw08d/fklk448oj5v5s");
  data.emplace_back("12zcnohsp5snpyl/fklk448oj5v5s", "44kyfdy0xih2rzh/fklk448oj5v5s");
  data.emplace_back("12zcjn6qjdc4gk3/fklk448oj5v5s", "44kyfdy0xih2rzh/fklk448oj5v5s");
  data.emplace_back("za4wuobmai5gib/fklk448oj5v5s", "3x0imesozh4arsd/fklk448oj5v5s");
  data.emplace_back("ykgeolp0mzllub/fklk448oj5v5s", "3vji8ttkpysk3l9/fklk448oj5v5s");
  data.emplace_back("rz4i7tpmx8kzir/fklk448oj5v5s", "3hhbxok9avne4vh/fklk448oj5v5s");
  data.emplace_back("ra76oeqy192jmb/fklk448oj5v5s", "3fzz781tp3nxstp/fklk448oj5v5s");
  data.emplace_back("otis5lu41to15f/fklk448oj5v5s", "3ap950heish9uel/fklk448oj5v5s");
  data.emplace_back("otis5lu41to15f/fklk448oj5v5s", "3ap90z6cd00ql03/fklk448oj5v5s");
  data.emplace_back("hayuoyx6eg162pamnwi4661b1p24u24gvd/4i5sqb4h0tsutka5pt51a2dits6sawv7k",
                    "tmy8cw85hhqfqpb1rs46wee7v1mtulylef/4i5sqb4h0tsutka5pt51a2dits6sawv7k");
  data.emplace_back("fkc8z9hlhet2uwyfgoljmq2a2ikdwiomk7/4i1gbktm9ezfltvnfh52gbk3g9pftskjk",
                    "pl9g86wes08azqcycye3pxxc7ay8gufeqp/4i1gbktm9ezfltvnfh52gbk3g9pftskjk");
  data.emplace_back("hyogaoowjj4eul/fklk448oj5v5s", "2un9zjrkqpk8hm5/fklk448oj5v5s");
  data.emplace_back("hyoc9dmqr2l5g3/fklk448oj5v5s", "2un9zjrkqpk8hm5/fklk448oj5v5s");
  data.emplace_back("fum939hpe9y4lv/fklk448oj5v5s", "2p9cvplwfjg75f1/fklk448oj5v5s");
  data.emplace_back("fum939hpe9y4lv/fklk448oj5v5s", "2p9croau9qznw0j/fklk448oj5v5s");
  data.emplace_back("72vfqmduuiu77cl90vsq8fa4t14qqicpln/24rrh90tiy4e57eiegpt8eds57st9v9q8",
                    "be1ighjtxui0c1chkbxmk6xm9b9xgsobhd/24rrh90tiy4e57eiegpt8eds57st9v9q8");
  data.emplace_back("83y89tuxtarru265o58oouluxt3cc4jth/2owo5anzimnriybbwtt540y2ax53skxs",
                    "l25c2xvbcw1ipx4koggazlfkn6x3bvncv/4pl699nz5lnl661tug5zy1nm13zxn0n4");
  data.emplace_back("cxx2mcra4f89wt/fklk448oj5v5s", "2ewt9ubtigvbfot/fklk448oj5v5s");
  data.emplace_back("cxwyl1p4byp0ib/fklk448oj5v5s", "2ewt9ubtigvbfot/fklk448oj5v5s");
  data.emplace_back("afeiymvez3xfpv/fklk448oj5v5s", "2a0duzyknjt7lt9/fklk448oj5v5s");
  data.emplace_back("9e8mpdfqrykmhf/fklk448oj5v5s", "2814juwf7vdjpyl/fklk448oj5v5s");
  data.emplace_back("24bto0vrzyx043/fklk448oj5v5s", "1u5ts80i4cipzql/fklk448oj5v5s");
  data.emplace_back("12y0262brd9xw3/fklk448oj5v5s", "1s5x609td9dtuzx/fklk448oj5v5s");
  data.emplace_back("12y0262brd9xw3/fklk448oj5v5s", "1s5x1yyr7gxallf/fklk448oj5v5s");
  data.emplace_back("zdszxqhr8kwfyr/fklk448oj5v5s", "1al2kt7mxu4ybwz/fklk448oj5v5s");
  data.emplace_back("zdt3z1jx11fpd9/fklk448oj5v5s", "1al2kt7mxu4ybwz/fklk448oj5v5s");
  data.emplace_back("10hoyj31msoq4vh/fklk448oj5v5s", "1cjr4vcx7ggxccz/fklk448oj5v5s");
  data.emplace_back("rhkktf31h8xi7offq5xymxle5byymkms1/9sj7r5jgff4vi04jid310hvpttrazlz4",
                    "137qpeu5vvvyaxfiac1czhs9lhlw9taf5r/9sj7r5jgff4vi04jid310hvpttrazlz4");
  data.emplace_back("1gln8y7lad7tolv/fklk448oj5v5s", "1e1a7p74lmpyker/fklk448oj5v5s");
  data.emplace_back("1glnczing5ocy0d/fklk448oj5v5s", "1e1a7p74lmpyker/fklk448oj5v5s");
  data.emplace_back("b6bc6x9i3h70m96izel43bhtkk965ax5n/3763vf6i857ysnxf6lag85w47g5bbf28",
                    "2mzzk5wkvkif3daa1l9ef1sa92alug1fj/ssiyusmk1azp5zcsnbm21h11v1bturk");
  data.emplace_back("spidbu2a8p12oj/fklk448oj5v5s", "miwoximw70mv59/fklk448oj5v5s");
  data.emplace_back("spidbu2a8p12oj/fklk448oj5v5s", "miwkw7kqek3lqr/fklk448oj5v5s");
  data.emplace_back("wjmkr3pqxbm76b/fklk448oj5v5s", "j6vsunm8xvz9ar/fklk448oj5v5s");
  data.emplace_back("wjmoserwps5gkt/fklk448oj5v5s", "j6vsunm8xvz9ar/fklk448oj5v5s");
  data.emplace_back("1m5ywfgzn9kqb71/fklk448oj5v5s", "1brtaadlszh7wer/fklk448oj5v5s");
  data.emplace_back("fej792mniu6jygd1436qmwi2o651d4lb/409t7huxtp84duif8a9lnsov7rsb3sw",
                    "shlvv5vrkknpg937cksawv0bu25l6xd/90m2pv6m3tr9v5ng9n3lqjjy8hiozk");
  data.emplace_back("1wuyase7fmlmcd6nltvnq103m3lglwivh/hrnfg6x2796wivoymiu9cpuidokdo8w",
                    "2xwswicol94hoo9urrpklpxtg9bmcvj8p/zjauwdu4eidt1rdx91oipfp0rd4rchs");
  data.emplace_back("1jljka9zvkynob7/fklk448oj5v5s", "8jn64iead6bact/fklk448oj5v5s");
  data.emplace_back("1jljka9zvkynob7/fklk448oj5v5s", "8jn237c4kps0yb/fklk448oj5v5s");
  data.emplace_back("1rn5yla2oz8k2c3/fklk448oj5v5s", "7fhdvzljsk13o3/fklk448oj5v5s");
  data.emplace_back("1trnkk2z7v7bn4j/fklk448oj5v5s", "75tbx77an28y4z/fklk448oj5v5s");
  data.emplace_back("2b7ayjycdb6xuxf/fklk448oj5v5s", "53lzhuhiemx39v/fklk448oj5v5s");
  data.emplace_back("2dg18f0dwchcslv/fklk448oj5v5s", "4w9coqm4cda09f/fklk448oj5v5s");
  data.emplace_back("2liq6xlaz90inrn/fklk448oj5v5s", "45l69s0buujm4z/fklk448oj5v5s");
  data.emplace_back("2qq7l6sfztjlgb7/fklk448oj5v5s", "3l0e2vqf7cef9v/fklk448oj5v5s");
  data.emplace_back("2sywtowsr2fbphv/fklk448oj5v5s", "3ceqithbt3tyvn/fklk448oj5v5s");
  data.emplace_back("38ai3kpkmpy1cr7/fklk448oj5v5s", "1r1z1pkfzwlfbn/fklk448oj5v5s");
  data.emplace_back("3ajkl0htj0bispf/fklk448oj5v5s", "1k898eg8ollzo3/fklk448oj5v5s");
  data.emplace_back("3g9w4wlwi7im7df/fklk448oj5v5s", "12y0262brd9xw3/fklk448oj5v5s");
  data.emplace_back("3g9w8xwynzz5grx/fklk448oj5v5s", "12y0262brd9xw3/fklk448oj5v5s");
  data.emplace_back("4xh9xivw8zi1b62tt1rtzvsayrle9k6wzj/looiabsyh8yavg4lbkojzf0utza3k1kw",
                    "1j3vsxmvrueydfcdu178w14ouh2d6aofix/looiabsyh8yavg4lbkojzf0utza3k1kw");
  data.emplace_back("3rkfyiawo9s40r7/fklk448oj5v5s", "13kbstxsm1w7v0z/fklk448oj5v5s");
  data.emplace_back("3rkg2jlyu28na5p/fklk448oj5v5s", "13kbstxsm1w7v0z/fklk448oj5v5s");
  data.emplace_back("3oy01febyoz6qflck0fjimccb3uebo305v/ef5ulgkzxi0kpldrzcxn861o469tzzls",
                    "iyw2kb027v03yld2nqxeznf49zgmazc71/77kxaqahyr0acsovzogtm30u234wzzsw");
  data.emplace_back("47n8fzocae8h0ib/fklk448oj5v5s", "3cdaihunmaems3/fklk448oj5v5s");
  data.emplace_back("47n8k0zeg6p09wt/fklk448oj5v5s", "3cdaihunmaems3/fklk448oj5v5s");
  data.emplace_back("4d9b6ybf1u2p8vh/fklk448oj5v5s", "4jx33tkopkdjo3/fklk448oj5v5s");
  data.emplace_back("4fgpjziaw3ui819/fklk448oj5v5s", "513ihnnjtl5n0z/fklk448oj5v5s");
  data.emplace_back("4ufws9gkev2ftwt/fklk448oj5v5s", "8ixc38ptitmcb7/fklk448oj5v5s");
  data.emplace_back("4wmrfcc6l03271p/fklk448oj5v5s", "91h61zpgo26thv/fklk448oj5v5s");
  data.emplace_back("51xbkz38cyccwfh/fklk448oj5v5s", "aa3r4puec2zpar/fklk448oj5v5s");
  data.emplace_back("53fbx392xt22m99/fklk448oj5v5s", "amqxwdty04qh1v/fklk448oj5v5s");
  data.emplace_back("5ipnyf7ztrwk20d/fklk448oj5v5s", "eb9zwbr98vnlqr/fklk448oj5v5s");
  data.emplace_back("5k7lxwsd9vr29f1/fklk448oj5v5s", "eocnkxzb2m1ntf/fklk448oj5v5s");
  data.emplace_back("5skvplecodijtpp/fklk448oj5v5s", "gpv108iqjru577/fklk448oj5v5s");
  data.emplace_back("5skvplecodijtpp/fklk448oj5v5s", "gpv51jkwc8delp/fklk448oj5v5s");
  data.emplace_back("5jd6rq4dmgxrktp/fklk448oj5v5s", "1hy47iigfiwc6ct/fklk448oj5v5s");
  data.emplace_back("a4dnyje5ott0ipgzs8f1jki1ka7eatgij/sgvcn08w24ntf94hnkc4p85pka3pkow",
                    "cy6p01qiary7afyhjyuei9qxghmd108d/3k3x2vj409kz6en27g1il5ipp19gp34");
  data.emplace_back("5lfklnertdazwer/fklk448oj5v5s", "1jhj85xolbu958z/fklk448oj5v5s");
  data.emplace_back("6biro5a3v1uhm8j/fklk448oj5v5s", "rejkc6rk0ybqhf/fklk448oj5v5s");
  data.emplace_back("6birs6l60ub0vn1/fklk448oj5v5s", "rejkc6rk0ybqhf/fklk448oj5v5s");
  data.emplace_back("6gzvyzikuq2u5v1/fklk448oj5v5s", "wc58zdz9i4eksz/fklk448oj5v5s");
  data.emplace_back("6gzvyzikuq2u5v1/fklk448oj5v5s", "wc5d0p1fakxu7h/fklk448oj5v5s");
  data.emplace_back("ukgsja4zr95gz1lxni0xq50oyw7jmfckt5/2ax6iyji2akrzvbod7by6ht69oxmui874",
                    "8z8um06p301t1xr5fjt7565nu7n0fwupi1/2ax6iyji2akrzvbod7by6ht69oxmui874");
  data.emplace_back("ts5bgt6tpuqrgwibjy1ywoxz7nj2cm4jg9/253a986ghloubllt55zw1p2t12zfxp7nk",
                    "500ld0f8bgud8ld1js1rr0iq4soudg6kcp/12jn4m388suf5sswkkzy0ujeijhpyults");
  data.emplace_back("71navabcxn34afn/fklk448oj5v5s", "1pmpf8agadiahg3/fklk448oj5v5s");
  data.emplace_back("71nazbmf3fjnju5/fklk448oj5v5s", "1pmpf8agadiahg3/fklk448oj5v5s");
  data.emplace_back("7367yrlitllh9gt/fklk448oj5v5s", "1uut9o2ojww6x1v/fklk448oj5v5s");
  data.emplace_back("7367yrlitllh9gt/fklk448oj5v5s", "1uutdpdqppcq6gd/fklk448oj5v5s");
  data.emplace_back("2nze9qcb5zn0jo1qspr6bxeghresvx5d47/6ueulfbsmlwldjpnd4a7zkukw5mizi0w",
                    "h6lj1q43drie6spoip8tcqj90eo7xz3cx/3f7fapnwbayaorutok53zsfag2t9hr0g");
  data.emplace_back("41xtop67mqiyhygez5p021axriefwoj20p/a6u0hnspiw7j9j72dmvxjsecbcatcfsw",
                    "1oqxwxrweof3bx8v97x1ath55zia7stkf1/a6u0hnspiw7j9j72dmvxjsecbcatcfsw");
  data.emplace_back("78tmbne8xqgb6c3/fklk448oj5v5s", "2dkppdwd6iilfpv/fklk448oj5v5s");
  data.emplace_back("78tmfopb3iwufql/fklk448oj5v5s", "2dkppdwd6iilfpv/fklk448oj5v5s");
  data.emplace_back("79wz4oymblv1kx9/fklk448oj5v5s", "2iz1rh7um75wmvn/fklk448oj5v5s");
  data.emplace_back("79wz4oymblv1kx9/fklk448oj5v5s", "2iz1viiwrzmfwa5/fklk448oj5v5s");
  polygonwh.outer_boundary() = GetPolygonData(data);
  // hole #0
  data.clear();
  data.emplace_back("2phodn707usteasm3760ck5kg14y7ej1/lovjwwcyrenr9kpsr18nrdw5rgei9s",
                    "4t0mh3m927cgnjtpf8e1ceb7t4qehq2x/lovjwwcyrenr9kpsr18nrdw5rgei9s");
  data.emplace_back("7gr8vqa8633rzoz9dkk2fsj3ux9evsz/1v5kfb7fgva3hb0gn2cxcyadygxhq8",
                    "wb6b7gsnwtjcozcp8wjzn5rhu84empl/4nvx2a0ko678p9j5lnwbedpyw6bqbk");
  data.emplace_back("1qylfowdt8blagd/fklk448oj5v5s", "31b8t8he6vf987n/fklk448oj5v5s");
  data.emplace_back("1xblfxcmrxbqpm5/fklk448oj5v5s", "3et9viyzu95qz0z/fklk448oj5v5s");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #1
  data.clear();
  data.emplace_back("k16n35x5ukbt1sas26y4yzatpqvw2l13/3iazpobmw5s0rq75s3gghgfkmo5z9j4",
                    "4vlrxqfu6vvxekdeyntbdvbfchyvp0ez/1r5huu5tg2w0dv3kw1q88q7sbc2zmrk");
  data.emplace_back("2eum9ekug6a53jh/fklk448oj5v5s", "17hdb1qgwtf4kdp/fklk448oj5v5s");
  data.emplace_back("1yrpdwwvygh68tp/fklk448oj5v5s", "194sm42cc6udrn1/fklk448oj5v5s");
  data.emplace_back("4jtsbutc87oem87ucy608nbvfuuhp8tb/112wt6zf1aygibcxlhjhwj5ldfi483k",
                    "1i2fjd6jsn5876a293bqf552y7k7qlsl/ijgelhpinh895ogsqrqy9ksopr241s");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #2
  data.clear();
  data.emplace_back("2q9t1db2hkvwnukzwk0nrwa6i37l0opj/fd3cpzdqyi6w31zci2u98b9odee7ls",
                    "1zss0jqwq4st3is1st0ptluhwj5vp1fx/7ojoczovh93g1izo91f4m5mu6p73sw");
  data.emplace_back("q8y1calti62en9lpz6m7rogyna1bwjd/4wwo6k9gyksl2srcx44bdr4kwsym0w",
                    "lp6n8o7d6infol2zwho6kumq6gsac1x/2ggc3a4qhaeajedogk25ovkagehb0g");
  data.emplace_back("2cibnsethyj0b3h/fklk448oj5v5s", "3u6vsvqgclnxt5f/fklk448oj5v5s");
  data.emplace_back("2qadfmx4vlt0w19/fklk448oj5v5s", "40wq6zwkyt73p3n/fklk448oj5v5s");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #3
  data.clear();
  data.emplace_back("c9jpm8d2z1c5kes159gdtak1tqjw0ffp/1kipz0pvx0wp60lz4w83pm4k26kycjk",
                    "fqs3bvbr545ean3kb49jlhmts0zhb57d/1kipz0pvx0wp60lz4w83pm4k26kycjk");
  data.emplace_back("3opcd8oljjalixi1scaxif2qslcfk96b/jqy5l8y75kiccqf7yymtddgk9x0bnk",
                    "57q0gpcl992rbtazthjcq6twyds9abhj/jqy5l8y75kiccqf7yymtddgk9x0bnk");
  data.emplace_back("2yjj5cc67jwqq7h/fklk448oj5v5s", "44zftpfycwygatv/fklk448oj5v5s");
  data.emplace_back("3bqj2lotumfsy7h/fklk448oj5v5s", "4b9bzmennlmblqr/fklk448oj5v5s");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #4
  data.clear();
  data.emplace_back("rsk7qwstik4lkweri5c3xdfd15tqdag5/3jzx1jk4rvxwgee8yquehw3jekvgy68",
                    "93uapr1f69yy3m73vk8g7h2qckym5bc7/3jzx1jk4rvxwgee8yquehw3jekvgy68");
  data.emplace_back("3bmlmjfqzqsip0t/fklk448oj5v5s", "142qs37eqr5f0vh/fklk448oj5v5s");
  data.emplace_back("2x60xqv0lir7mzx/fklk448oj5v5s", "15hmewa4nwh9bfx/fklk448oj5v5s");
  data.emplace_back("1rm9wv8g65zfbv5kf6xt327fgfhqkjek1/9m1n2gx3igmfo3icm4lvd3f8fwrc1z4",
                    "prsqv0jpdz3pt499r5wgr0sg2jimze7x/9m1n2gx3igmfo3icm4lvd3f8fwrc1z4");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #5
  data.clear();
  data.emplace_back("3pqbhilcfnv75o5u7pkuq1cqxw5gj3j7/cgi6d1o1e7q5vfswkwptvdypbojdog",
                    "3l41wdeu9cr8tzpghx0x99dvh8479kxp/cgi6d1o1e7q5vfswkwptvdypbojdog");
  data.emplace_back("j8m4fr3lu3wgpamqqcon638gdwr5mon/20qrihfu7alnj64gggj8k72n0cke0w",
                    "ahku615bst4vz7isbbwl7vo9gu4fidv/10ddr8px3natrl28889ma3jbi6a70g");
  data.emplace_back("46dzqq71cnslmfn/fklk448oj5v5s", "4hn1a97bwi1nmxf/fklk448oj5v5s");
  data.emplace_back("4l0puzv2b2fnnbn/fklk448oj5v5s", "4hgfity7u1maq4z/fklk448oj5v5s");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #6
  data.clear();
  data.emplace_back("ray7r8rkmtu4sfh4yx6j0h8kwqwi2evr/2jazrp33wzbllwn0sp2l2rvhtkepqf4",
                    "f4cd4zc23nzuh9fauhkph50bje7murwb/52lzje67tyn77ta1le565jqzn4tfgu8");
  data.emplace_back("4lkc3d1h1mpq503/fklk448oj5v5s", "19w4mpovsxrj5t9/fklk448oj5v5s");
  data.emplace_back("47941m7z8ijqp5f/fklk448oj5v5s", "16kqqc6d974690t/fklk448oj5v5s");
  data.emplace_back("5wjo4s1nszneocnhm7mm3szzn33wzc3/m6pwp3a4ehjh7pesqk3825odupczk",
                    "bnxit1r28hhxmbnmtnk50vrq6fwtwkz/4bb1cvmyuteschxvl5wmkf3qoyxiww");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #7
  data.clear();
  data.emplace_back("31t5uvte2enf1z2cylod9jembw0bxn2v/8y9w47zc9q97t5yysecmcuhu6fgagw",
                    "6mzaxd57zeoc0volauv1n6r950bu2zvn/1zm74xruq5u1qhbrqb6syurypffmbr4");
  data.emplace_back("59katn82hbewrf7/fklk448oj5v5s", "1flyyz2nsbj6p0t/fklk448oj5v5s");
  data.emplace_back("4uk7qqrc4afkkpf/fklk448oj5v5s", "1c2v730grkk09bh/fklk448oj5v5s");
  data.emplace_back("8pk08ybvswjrukg8bkw1a89zltcf2eun/s7bj51qes6a7kviao8w1qft0escvsw",
                    "4sy3q9nfr2wb6qz4p3batmbabzgbwbbx/1ken2a3gtkckf5r0lchs3gvm0tkprls");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #8
  data.clear();
  data.emplace_back("7lba2brgpj6v7lirs2vc8453x38xofev/m9v4cjn2bmumzprtv15qq6n9zv5am8",
                    "6e3ez2x3heoy58u03s9d79zqwjx517nx/m9v4cjn2bmumzprtv15qq6n9zv5am8");
  data.emplace_back("9mf5ulgagrn7qi7swipe66c40vvrg49/v83yzev7as41ck19nq2va78mvcv7k",
                    "8zbtse1wvsqoqs611m5ncm7zfv9gwnl/v83yzev7as41ck19nq2va78mvcv7k");
  data.emplace_back("4u8jp0iogx7xzgz/fklk448oj5v5s", "4h7w74s86x480k3/fklk448oj5v5s");
  data.emplace_back("59l4nwa36zbvaab/fklk448oj5v5s", "4gwp34w5bvyua4z/fklk448oj5v5s");
  polygonwh.add_hole(GetPolygonData(data));
  // hole #9
  data.clear();
  data.emplace_back("7pdl98i4jinpjf6jt0dyjjsyptuf0jbdx/jg0792joran9a26aqxo61mrddojzz7k",
                    "fsrln1e5p0bo5c0y93erwqckohje8krvh/25s0t0a6r16l148p6zqoo6j1hiq7zwu8");
  data.emplace_back("63puzc9dhn643ir/fklk448oj5v5s", "2llmac906l0zq5p/fklk448oj5v5s");
  data.emplace_back("5xiq5tv0xc7hoer/fklk448oj5v5s", "22fpc7p0garxjcd/fklk448oj5v5s");
  data.emplace_back("5j01yr7u2shdbkj/fklk448oj5v5s", "1lg31ooyb9o4ilp/fklk448oj5v5s");
  data.emplace_back("5a67ovga0d9bl5f/fklk448oj5v5s", "1jfzkq8dnmqs9wt/fklk448oj5v5s");
  data.emplace_back("4sl35k9reoawxqr/fklk448oj5v5s", "1fab6jib32jxuel/fklk448oj5v5s");
  data.emplace_back("44n6gnekrglopn7/fklk448oj5v5s", "19kfvxn7r059dt9/fklk448oj5v5s");
  data.emplace_back("1bsuiiqaezt0ajda6ozas0lyobw2wdv0cj/5i3v2r6uzpst0l6p20ehecuntdtwwmww",
                    "ue0n7gvdi063y8fhrp0xkw45bewtyw27n/b07q5idpzflm16de40sysppbmrntt9ts");
  data.emplace_back("3dp8kdjersture5/fklk448oj5v5s", "17ctno8timg58od/fklk448oj5v5s");
  data.emplace_back("2q0ty1v8moxkqb1/fklk448oj5v5s", "19rjp38uvzw1sml/fklk448oj5v5s");
  data.emplace_back("1o8n5olu52yrsj1/fklk448oj5v5s", "1dwalbfo60p08bx/fklk448oj5v5s");
  data.emplace_back("77icb6q5ihes4afnflcmydijwa38nmsfvp/2bjhz43qiv6wromqs62pllp1mjza80vls",
                    "9nnshlf93z6wa67sqmls1pu0feig9q4fm5/2bjhz43qiv6wromqs62pllp1mjza80vls");
  data.emplace_back("1ixlf4qp8qmiael/fklk448oj5v5s", "29xmni8clq0xdxv/fklk448oj5v5s");
  data.emplace_back("1qya7tis8df5mb1/fklk448oj5v5s", "2svceifjv07x7tf/fklk448oj5v5s");
  data.emplace_back("214enets09kxlil/fklk448oj5v5s", "3eko6i9oz842ok3/fklk448oj5v5s");
  data.emplace_back("24u67q8g4ewqkod/fklk448oj5v5s", "3mhpu5l4qbc24sz/fklk448oj5v5s");
  data.emplace_back("2csqss6lnhetbu5/fklk448oj5v5s", "3qcrt4iwyldi8k3/fklk448oj5v5s");
  data.emplace_back("2swyggkgkq7l06l/fklk448oj5v5s", "3y7zxikc14iulzn/fklk448oj5v5s");
  data.emplace_back("3evg14by52cc3zh/fklk448oj5v5s", "48x8dty7v1hypxv/fklk448oj5v5s");
  data.emplace_back("3r771fa0s5raalp/fklk448oj5v5s", "4dm5eb45z02e3tf/fklk448oj5v5s");
  data.emplace_back("1tnzztpyujwielresh8m726xbqxze3jz/6vwfijoakluljcmfacsjq75ns9ko3k",
                    "9pr1jzjyobjbbf8flrnh63v9fo1ny8df/yfi5kqdgv18zor44fryqmzsaxbvchs");
  data.emplace_back("4szll8rtyqid6mr/fklk448oj5v5s", "4dodfs9he8jdec3/fklk448oj5v5s");
  data.emplace_back("5axkpl4t08kytar/fklk448oj5v5s", "4db3obkl6blkvdf/fklk448oj5v5s");
  data.emplace_back("5jr1gw39d8z96mr/fklk448oj5v5s", "4d31a7ayqmwr8pf/fklk448oj5v5s");
  data.emplace_back("5p34mlu91fkpm8j/fklk448oj5v5s", "46qk4hpljyyh1oz/fklk448oj5v5s");
  data.emplace_back("5z45cmfjpqdris3/fklk448oj5v5s", "3o9ucc2f3nkdbrn/fklk448oj5v5s");
  polygonwh.add_hole(GetPolygonData(data));
  return true;

  // backup: read from the file
  /* std::vector<PolygonWHEE> polygonwhs;
  std::ifstream ifs("data.pwh");
  if (!ifs) {
    return false;
  }
  ReadPolygonWHsExactly(ifs, polygonwhs);
  assert(!polygonwhs.empty();
  polygonwh = polygonwhs[0];
  return true; */
}

Environment

Screenshots

Original Polygon_with_holes_2: 1

Padded Polygon_with_holes_2 with padding_offset = 2.0 (wrong): 2

Debug Assertion Failed Screenshot: 3

Test Data

The test data are generated in the above source code rather than imported from the "data.pwh" by default. However, we still provide the file for convenience. You may see "data.pwh" after extracing the "data.zip" attached. data.zip

sloriot commented 3 years ago

Except if I missed it, you did not provide the input file.

KaimoHu commented 3 years ago

Except if I missed it, you did not provide the input file.

The test data are generated in the above source code rather than imported from the "data.pwh" by default. For convenience, I further provide the input file. You may see "data.pwh" after extracing the "data.zip" attached.