search

CGAL / cgal

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

Segmentation fault with some polygons in approximated_inset_2 #7226

Open thomasp85 opened 1 year ago

thomasp85 commented 1 year ago

Issue Details

When attempting to inset some polygons using the approximated_inset_2() method from the 2D Minkowski Sums package you get a segmentation fault in the line sweeping done when uniting the the cycles after offsetting. I have not been able to find any issues in the polygons that provoke the issue and failed at finding the root cause.

CGAL error: assertion violation!
Expression : sl_iter != m_statusLine.end()
File       : /opt/homebrew/include/CGAL/Surface_sweep_2/No_intersection_surface_sweep_2_impl.h
Line       : 547
Explanation: 
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
libc++abi: terminating with uncaught exception of type CGAL::Assertion_exception: CGAL ERROR: assertion violation!
Expr: sl_iter != m_statusLine.end()
File: /opt/homebrew/include/CGAL/Surface_sweep_2/No_intersection_surface_sweep_2_impl.h
Line: 547

Source Code

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/approximated_offset_2.h>
#include <CGAL/Gps_circle_segment_traits_2.h>

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

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;

typedef CGAL::Gps_circle_segment_traits_2<Kernel> Circ_traits;
typedef Circ_traits::Polygon_2 Circ_polygon_2;

std::vector<std::string> x = {
  "60510737080633972995752446937480483161395985769214244579877258317/12637282929892346249890231843923042287534613488875103608364859392",
  "774118977829219384697893562412727/162259276829213363391578010288128",
  "377798110761552539171896218631907/81129638414606681695789005144064",
  "368251638352669596636235138011475/81129638414606681695789005144064",
  "716858309290070347843941181532765/162259276829213363391578010288128",
  "696679427757404347688066371338635/162259276829213363391578010288128",
  "337992317667451094421373682159061/81129638414606681695789005144064",
  "81848973206664896201495135549845/20282409603651670423947251286016",
  "19784954435296591387113445890139/5070602400912917605986812821504",
  "610982339690871324516464642061057/162259276829213363391578010288128",
  "147100088255357149387039220176877/40564819207303340847894502572032",
  "565389464277568320859307801570251/162259276829213363391578010288128",
  "541966237195534401667764913911833/162259276829213363391578010288128",
  "518146893288323189989824126191551/162259276829213363391578010288128",
  "61743411426305091851754336541301/20282409603651670423947251286016",
  "469382910352691042501595063202831/162259276829213363391578010288128",
  "222234417158204182491840800727797/81129638414606681695789005144064",
  "104804935276727674401631433105961/40564819207303340847894502572032",
  "393649892879198511628053640994459/162259276829213363391578010288128",
  "367773129264782994357867241357203/162259276829213363391578010288128",
  "42700357838340373446252291353347/20282409603651670423947251286016",
  "19697004739387587068685759914511/10141204801825835211973625643008",
  "288433320678006983995005964032371/162259276829213363391578010288128",
  "261458719643842722778412519235411/162259276829213363391578010288128",
  "234239967941208232081328692393205/162259276829213363391578010288128",
  "7708562596448516476774624264727777902997659729975816101976761391/3237670281553573176589656966601544213951499158650431898680033280",
  "200148527380464642418110726740399/81129638414606681695789005144064",
  "430125098263451460375838762740711/162259276829213363391578010288128",
  "45807599065411912055081675084367305833063389579816194076380609501/17278923676385768454445714777093208581774026285823267786937335808",
  "459828849982667785300701118687431/162259276829213363391578010288128",
  "489401892662174742428315592078739/162259276829213363391578010288128",
  "32427345583733228021826966978589/10141204801825835211973625643008",
  "548128775260972157445709978443837/162259276829213363391578010288128",
  "577268349975770244787254643250839/162259276829213363391578010288128",
  "37890541854170703165211748792913/10141204801825835211973625643008",
  "317530919881671870878133110201317/81129638414606681695789005144064",
  "663699647899493817405597988132245/162259276829213363391578010288128",
  "692153557276283140958742395270787/162259276829213363391578010288128",
  "90051837562046740558011515469843/20282409603651670423947251286016",
  "93559234242546294169760048878307/20282409603651670423947251286016",
  "194080383189998234322068103179589/40564819207303340847894502572032",
  "401973893283480630420882894343997/81129638414606681695789005144064",
  "831342395900513578246329588350847/162259276829213363391578010288128",
  "429247384780148557649465058167833/81129638414606681695789005144064",
  "221348490723722418653922039006129/40564819207303340847894502572032",
  "456014338569692465919998639887109/81129638414606681695789005144064",
  "938387259898205856109082342975017/162259276829213363391578010288128",
  "964457706871514133644483375683163/162259276829213363391578010288128",
  "990227664925161069869899162814879/162259276829213363391578010288128",
  "1015684436604975707055073844099205/162259276829213363391578010288128",
  "1040814986196203159483941352521631/162259276829213363391578010288128",
  "532802973713991018353732743976363/81129638414606681695789005144064"
};

std::vector<std::string> y = {
  "-57517038340034830191250680737547790893849849453312380469936885365/12637282929892346249890231843923042287534613488875103608364859392",
  "-742759493871231741012322051676079/162259276829213363391578010288128",
  "-769405889790940558863578754175365/162259276829213363391578010288128",
  "-795646742956783295551675656998063/162259276829213363391578010288128",
  "-821476922436194531352202078683319/162259276829213363391578010288128",
  "-846892186683811614544077840869539/162259276829213363391578010288128",
  "-871889156165633190042431501829529/162259276829213363391578010288128",
  "-448232641793786263543650775247237/81129638414606681695789005144064",
  "-920618822110387596095152315362489/162259276829213363391578010288128",
  "-472174395959698572410963285970309/81129638414606681695789005144064",
  "-967654945500515652676794054703959/162259276829213363391578010288128",
  "-495268865977300331716745256143297/81129638414606681695789005144064",
  "-506499130330255749691559326768617/81129638414606681695789005144064",
  "-1035038264574203803390599702999517/162259276829213363391578010288128",
  "-1056660063427156808231092443126249/162259276829213363391578010288128",
  "-1077866527062926921629309658165983/162259276829213363391578010288128",
  "-1098661039126062647105286947248647/162259276829213363391578010288128",
  "-1119047461293369759358690295607867/162259276829213363391578010288128",
  "-1139030098213889935011029456784393/162259276829213363391578010288128",
  "-579306831650604128463332084498585/81129638414606681695789005144064",
  "-1177803245500038383478834971918887/162259276829213363391578010288128",
  "-598302138564303069025226836355497/81129638414606681695789005144064",
  "-1215022502879276496012765461788153/162259276829213363391578010288128",
  "-616531975021109365299330041743623/81129638414606681695789005144064",
  "-1250734900000721359478566786276017/162259276829213363391578010288128",
  "-59262028359412580474155039985036300033434908052214935853784825417/6475340563107146353179313933203088427902998317300863797360066560",
  "-2958309511505849689315068892875033/324518553658426726783156020576256",
  "-1466371534816978514821701687518185/162259276829213363391578010288128",
  "-1873819800267079595419164909731326479517205819454177773064990634213/207347084116629221453348577325118502981288315429879213443248029696",
  "-726651051452750913811887185678263/81129638414606681695789005144064",
  "-179992442612449715048567274051121/20282409603651670423947251286016",
  "-89142309786747890091763292396347/10141204801825835211973625643008",
  "-706153748000926284790963721846563/81129638414606681695789005144064",
  "-699012177758215792152136948373255/81129638414606681695789005144064",
  "-2766841589483811482992730312753281/324518553658426726783156020576256",
  "-2736980300451403805509495283025129/324518553658426726783156020576256",
  "-2706451699969715917526762318971931/324518553658426726783156020576256",
  "-2675242857769914110765512645022419/324518553658426726783156020576256",
  "-2643341089757524028102197973032357/324518553658426726783156020576256",
  "-2610733992227980092320208729018059/324518553658426726783156020576256",
  "-2577409477830829845576666314992599/324518553658426726783156020576256",
  "-2543355813283322472876519063207071/324518553658426726783156020576256",
  "-2508561658823262944409075716299897/324518553658426726783156020576256",
  "-2473016109378919547804664495524779/324518553658426726783156020576256",
  "-2436708737420388416502756585039647/324518553658426726783156020576256",
  "-2399629637442117448469996590541773/324518553658426726783156020576256",
  "-2361769472010256997076525407082051/324518553658426726783156020576256",
  "-2323119519291140075166457749712011/324518553658426726783156020576256",
  "-2283671721958520886102184268767903/324518553658426726783156020576256",
  "-2243418737357258866259825977291329/324518553658426726783156020576256",
  "-2202353988779997148098157462067051/324518553658426726783156020576256",
  "-2160471717691145779724623145474335/324518553658426726783156020576256"
};

int main() {
  std::vector<Point_2> poly_vec;

  for (size_t i = 0; i < x.size(); ++i) {
    poly_vec.emplace_back(Kernel::FT(mpq_class(x[i])), Kernel::FT(mpq_class(y[i])));
  }

  Polygon_2 poly(poly_vec.begin(), poly_vec.end());

  std::vector<Circ_polygon_2> inset;

  CGAL::approximated_inset_2(poly, 0.1, 1e-5, std::back_inserter(inset));

  std::cout << inset[0];

  return 0;
}

Environment

GilesBathgate commented 1 year ago

Is it a segfault or an Assertion_exception :shrug:

thomasp85 commented 1 year ago

ah, well... It is a seg fault when compiled with -DNDEBUG, but as provided here I assume that part is pretty murky

GilesBathgate commented 1 year ago

Ah, yeah in CGAL I often find when assertions are off and the assertion isn't met, the behaviour is undefined. It's an assertion failure bug really.

thomasp85 commented 1 year ago

yeah, that makes sense - sorry for the confusing description

GilesBathgate commented 1 year ago

If it helps, the sl_iter is populated from curve->hint(), which returns m_hint which is set via set_hint, the set_hint function is called from either _init_curve, _handle_right_curves or _remove_curve_from_status_line . Both _init_curve, and _remove_curve_from_status_line set the hint to m_statusLine.end(), which is what the assertion fails with, so presumably, _handle_right_curves is not being called when it should be?

GilesBathgate commented 1 year ago

@sloriot is it related to #7235 ?

sloriot commented 1 year ago

No it's not. Here the problem is that during the sweep a curved is declared as being on the left of an event but that curve is not in the status line.