2D Straight Skeletons known issues

[MaelRL]

Issue Details

• Weighted straight skeletons of polygons with holes cannot handle "backward" splits: one needs to also detect and handle Split Events on concave vertices of holes. Geometry:

4
-3 -0.5
3 -0.5
3 0.5
-3 0.5

5
0.85486109764315188 0.041659302776679397
0.82030845247209072 0.13873305753804743
1.0046812503132969 0.16035508806817234
0.8976809096056968 0.17358406633138657
1.2234705875162035 0.27342820237390697

Weights:

0.073729580901563174
5.8892423566430807
0.074201285829767594
3.663008295930922

10
10
10
10
10

• One can create non-simple offset polygons (or skeleton extrusions) due to numerical errors: for example A.poly and offset = the double approximation of the time at the earlier skeleton vertex. This is the typical problem of having a valid result as long as we are in the exact world, and an invalid result once we go back to doubles.

[MaelRL]

There is also this random error here:

------------------------------------------------------------------
- Straight_skeleton_2/ProgramOutput.execution   of  test_sls_weighted_polygons_with_holes
------------------------------------------------------------------

CGAL::Random()::get_seed() = 1699956259
Seed is 1699956259
4 holes of size 10
pwh.outer_boundary() = 4 -3 -0.5 3 -0.5 3 0.5 -3 0.5 
PWH:
4 -3 -0.5 3 -0.5 3 0.5 -3 0.5  4 10 0.89298469154164195 0.060238552512601018 0.93239129288122058 -0.021098113153129816 0.96821496612392366 -0.075823144288733602 0.968829883961007 -0.17430318240076303 0.93746731407009065 -0.068807110423222184 0.76320072636008263 0.074444569414481521 0.78009634255431592 0.13391915312968194 0.88456345000304282 0.08359029795974493 0.88363206782378256 0.23363283392973244 0.95339045417495072 0.0071330938953906298  10 -1.2103602802380919 0.21851327735930681 -1.0872563056182116 0.22094908426515758 -0.92185277142561972 0.10035610618069768 -0.82318635610863566 0.32477875822223723 -0.9373556268401444 -0.024469547672197223 -0.98320027091540396 -0.097337594488635659 -1.2417593956924975 0.011971306055784225 -0.99549860064871609 -0.081253964453935623 -1.2403800380416214 0.22891584364697337 -1.2062491746619344 0.24017702741548419  10 2.2254603325854987 0.071492629125714302 2.2250997936353087 -0.026726458454504609 2.1583880528341979 -0.10135049442760646 2.1102954158559442 -0.27123981737531722 1.8504574454855174 -0.0096228683833032846 2.0921173749957234 -0.089974242961034179 1.8364722421392798 0.14040041412226856 1.7787762954831123 0.20934050483629107 2.0185474366880953 0.073279990116134286 2.142642029793933 -0.050581275252625346  10 -2.0933614699169993 -0.186910021584481 -1.8289539420511574 -0.051822102861478925 -2.1473373547196388 -0.145320552168414 -2.2055388849694282 -0.027373840333893895 -2.1041005623992532 0.0010488282423466444 -2.1195002731401473 -0.12525291251949966 -2.042118598241359 0.12653344473801553 -1.7942938786000013 0.14510671375319362 -1.7997975482139736 0.046831700950860977 -1.8211114613804966 -0.16063649766147137  
Weights:
0.26268645743839442 1.6544004352763295 0.43193368827924133 2.6486621163785458 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
CGAL warning: check violation!
Expression : closest_artificial_event != nullptr
File       : /mnt/testsuite/include/CGAL/Straight_skeleton_2/Straight_skeleton_builder_2_impl.h
Line       : 2200
Explanation: 
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
Error: failed to create straight skeleton

[MaelRL]

------------------------------------------------------------------
- ProgramOutput.test_sls_weighted_polygons_with_holes.Debian-Testing
------------------------------------------------------------------
CGAL::Random()::get_seed() = 1693395443
Seed is 1693395443
4 holes of size 10
pwh.outer_boundary() = 4 -3 -0.5 3 -0.5 3 0.5 -3 0.5 
PWH:
4 -3 -0.5 3 -0.5 3 0.5 -3 0.5  4 10 0.81107378378510475 0.31302423309534788 0.88030420080758631 0.10048065683804452 0.87694533308967948 0.093425779836252332 1.1962133585475385 0.3078381004743278 1.1438527351710945 0.12615396012552083 1.0245436688419431 0.015186724020168185 1.1141506207641214 0.055125517072156072 1.1481968632433563 -0.074900681618601084 0.9290995670016855 -0.064545084023848176 0.78754220274277031 0.14880898501724005  10 -0.88665841054171324 -0.088776362594217062 -0.95498075871728361 0.053735117660835385 -0.8665672002825886 -0.032569953240454197 -0.77513367170467973 -0.12375166174024343 -0.85587841714732349 -0.19924367172643542 -0.98111084755510092 -0.15187718439847231 -1.0553825371898711 -0.051172439707443118 -1.1983885534573346 -0.024522044928744435 -1.0730440034531057 0.21878608711995184 -0.97001076675951481 0.06924685463309288  10 2.1614125343039632 -0.0020332459826022387 2.0529766094405204 0.27656415966339409 2.2183736797887832 0.23525560111738741 2.2167045373935252 -0.17512912978418171 2.1088688855525106 -0.21678564418107271 1.9334122005384415 -0.18484683777205646 1.8258634626399726 -0.045782609609887004 1.8140514141414315 0.03519350616261363 1.8848629014100879 0.14393726643174887 2.0839762310497463 -0.015309200622141361  10 -1.8229593450669199 -0.28235960472375154 -1.7858786066062748 -0.37880595051683486 -1.9737124962266535 -0.29279845394194126 -2.0412485983688384 -0.31179019738920033 -2.0829674690030515 -0.25891842087730765 -2.1486445909831673 -0.34072575881145895 -2.0570106832310557 -0.1688454570248723 -1.9706729212775826 -0.052290770690888166 -1.8746075329836458 -0.092096928274258971 -1.8663039600942284 -0.11875109258107841  
Weights:
0.086620687087997805 6.4976298818364739 0.086620687087997805 1.0560863483697176 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
Warning: Failed to triangulate skeleton face
Warning: Failed to triangulate skeleton face
CGAL warning: check violation!
Expression : is_valid_polygon_mesh(out) && is_closed(out)
File       : /mnt/testsuite/include/CGAL/extrude_skeleton.h
Line       : 1064
Explanation: 
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
90 vertices and 159 faces

cf. https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-6.0-Ic-52/Straight_skeleton_2/TestReport_lrineau_Debian-Testing.gz

[sloriot]

Another here

------------------------------------------------------------------
- Straight_skeleton_2/ProgramOutput.execution   of  test_sls_weighted_polygons_with_holes
------------------------------------------------------------------

CGAL::Random()::get_seed() = 1702623130
Seed is 1702623130
4 holes of size 10
pwh.outer_boundary() = 4 -3 -0.5 3 -0.5 3 0.5 -3 0.5 
PWH:
4 -3 -0.5 3 -0.5 3 0.5 -3 0.5  4 10 0.90124114812351763 0.09701810753904283 0.77869885833933949 0.14887151611037552 0.75387798761948943 0.14244029857218266 0.79363645100966096 0.42678111931309104 0.89862855477258563 0.45844584866426885 0.92606696300208569 0.44924950343556702 0.98571785562671721 0.28125814348459244 0.97861310536973178 0.15377924754284322 1.1998633411712945 0.10619232035242021 1.1902849737089127 0.051739574875682592  10 -1.2350723671261221 -0.31390129425562918 -1.1846571015194058 0.0077284658327698708 -1.2102375356480479 0.032280871411785483 -1.1024735858663917 0.16787488036789 -0.93871822068467736 -0.11810377216897905 -1.0620483725797385 0.076096395030617714 -1.0602750901598483 0.070662816055119038 -1.1158469831570983 -0.004742056829854846 -1.0603688731789589 -0.045570971677079797 -0.88504792959429324 -0.24511936795897782  10 1.7895326174329966 0.089334221323952079 2.0802342938259244 0.19211481628008187 2.0584026763681322 -0.11106955236755311 1.8354958016425371 -0.21687906188890338 1.890642557060346 -0.14752923813648522 1.8813131609931588 -0.059314542450010777 1.8985375806223601 -0.17938052327372134 1.8941237756516784 -0.037217926466837525 1.7591064942535013 0.11145874415524304 1.9219126119278371 -0.0084349103271961212  10 -2.1583949371706694 -0.14096694043837488 -2.1294433739967644 -0.050111974123865366 -1.9630647168960422 0.26338881230913103 -1.8235363312996924 0.24254558584652841 -1.8659337875433266 0.083366761449724436 -1.7702605626545846 0.056861016433686018 -1.7650470507796854 -0.14992203563451767 -1.8884943041484803 -0.18814830551855266 -2.0049335036892444 -0.09446576377376914 -2.0529924349393696 -0.033443475607782602  
Weights:
0.20687204294372352 2.1568302898667753 0.12175213063601405 1.4984266827814281 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 
In CGAL_handle_signal, Program received signal SIGSEGV: Segmentation Fault.

[sloriot]

Maybe another one here

ERROR: execution of test_sls_simple in 8.6044 s : SEGFAULT
Stopping at

Construct straight skeleton of input: data/inputsquare.poly
Kernel: N4CGAL16Simple_cartesianIN4CORE4ExprEEE
Polygon with border of size: 4
4 holes
4 vertices

Log should be:

Construct straight skeleton of input: data/inputsquare.poly
Kernel: N4CGAL5EpickE
Polygon with border of size: 4
4 holes
4 vertices
29 unique vertices (29)
29 vertices
104 halfedges
20 faces
Exterior...
12 unique vertices (12)