InflatePaths creates additional tiny segments

[ccoustet]

Hello everyone,
The following chunk of code illustrates the problem.
If possible, the fix could be followed by a new tag/release.

Paths64 polyline, solution;
Point64 coords[56] = {
  {1525311078, 1352369439},
  {1526632284, 1366692987},
  {1519397110, 1367437476},
  {1520246456, 1380177674},
  {1520613458, 1385913385},
  {1517383844, 1386238444},
  {1517771817, 1392099983},
  {1518233190, 1398758441},
  {1518421934, 1401883197},
  {1518694564, 1406612275},
  {1520267428, 1430289121},
  {1520770744, 1438027612},
  {1521148232, 1443438264},
  {1521441833, 1448964260},
  {1521683005, 1452518932},
  {1521819320, 1454374912},
  {1527943004, 1454154711},
  {1527649403, 1448523858},
  {1535901696, 1447989084},
  {1535524209, 1442788147},
  {1538953052, 1442463089},
  {1541553521, 1442242888},
  {1541459149, 1438855987},
  {1538764308, 1439076188},
  {1538575565, 1436832236},
  {1538764308, 1436832236},
  {1536509870, 1405374956},
  {1550497874, 1404347351},
  {1550214758, 1402428457},
  {1543818445, 1402868859},
  {1543734559, 1402124370},
  {1540672717, 1402344571},
  {1540473487, 1399995761},
  {1524996506, 1400981422},
  {1524807762, 1398223667},
  {1530092585, 1397898609},
  {1531675935, 1397783265},
  {1531392819, 1394920653},
  {1529809469, 1395025510},
  {1529348096, 1388880855},
  {1531099218, 1388660654},
  {1530826588, 1385158410},
  {1532955197, 1384938209},
  {1532661596, 1379003269},
  {1532472852, 1376235028},
  {1531277476, 1376350372},
  {1530050642, 1361806623},
  {1599487345, 1352704983},
  {1602758902, 1378489467},
  {1618990858, 1376350372},
  {1615058698, 1344085688},
  {1603230761, 1345700495},
  {1598648484, 1346329641},
  {1598931599, 1348667965},
  {1596698132, 1348993024},
  {1595775386, 1342722540}};
  polyline.push_back(Path64(std::begin(coords), std::end(coords)));
  // offset polyline
  solution = InflatePaths(polyline, -209715, JoinType::Miter, EndType::Polygon);

  //print polyline and inflated solution
  std::cout << "Counts: " << polyline[0].size() << " ===> " << solution[0].size() << std::endl;
  std::cout << polyline << "=====>\n" << solution;

Counts: 56 ===> 63
1525311078,1352369439 , 1526632284,1366692987 , 1519397110,1367437476 , 1520246456,1380177674 , 1520613458,1385913385 , 1517383844,1386238444 , 1517771817,1392099983 , 1518233190,1398758441 , 1518421934,1401883197 , 1518694564,1406612275 , 1520267428,1430289121 , 1520770744,1438027612 , 1521148232,1443438264 , 1521441833,1448964260 , 1521683005,1452518932 , 1521819320,1454374912 , 1527943004,1454154711 , 1527649403,1448523858 , 1535901696,1447989084 , 1535524209,1442788147 , 1538953052,1442463089 , 1541553521,1442242888 , 1541459149,1438855987 , 1538764308,1439076188 , 1538575565,1436832236 , 1538764308,1436832236 , 1536509870,1405374956 , 1550497874,1404347351 , 1550214758,1402428457 , 1543818445,1402868859 , 1543734559,1402124370 , 1540672717,1402344571 , 1540473487,1399995761 , 1524996506,1400981422 , 1524807762,1398223667 , 1530092585,1397898609 , 1531675935,1397783265 , 1531392819,1394920653 , 1529809469,1395025510 , 1529348096,1388880855 , 1531099218,1388660654 , 1530826588,1385158410 , 1532955197,1384938209 , 1532661596,1379003269 , 1532472852,1376235028 , 1531277476,1376350372 , 1530050642,1361806623 , 1599487345,1352704983 , 1602758902,1378489467 , 1618990858,1376350372 , 1615058698,1344085688 , 1603230761,1345700495 , 1598648484,1346329641 , 1598931599,1348667965 , 1596698132,1348993024 , 1595775386,1342722540 
=====>
1595598131,1342958478 , 1525538337,1352549997 , 1526860173,1366880360 , 1519619818,1367625381 , 1520455707,1380163724 , 1520455743,1380164283 , 1520835657,1386101795 , 1517606485,1386426810 , 1517981057,1392085886 , 1518442403,1398743944 , 1518442523,1398745797 , 1518631267,1401870553 , 1518631301,1401871127 , 1518903874,1406599221 , 1520476682,1430275220 , 1520476701,1430275510 , 1520979993,1438013636 , 1521357438,1443423668 , 1521357652,1443427137 , 1521651172,1448951622 , 1521892195,1452504099 , 1522013674,1454158072 , 1527722475,1453952789 , 1527429189,1448327974 , 1535677231,1447793475 , 1535300194,1442598729 , 1538933260,1442254310 , 1538935357,1442254122 , 1541338367,1442050641 , 1541255678,1439083026 , 1538572867,1439302245 , 1538347470,1436622521 , 1538539025,1436622521 , 1536285727,1405181142 , 1550257469,1404154732 , 1550035607,1402651003 , 1543632531,1403091871 , 1543548714,1402347992 , 1540481251,1402568597 , 1540281878,1400218103 , 1524801532,1401203979 , 1524584118,1398027312 , 1530078469,1397689366 , 1531446056,1397589740 , 1531204103,1395143325 , 1529615907,1395248503 , 1529124036,1388697664 , 1530874613,1388477531 , 1530601638,1384970847 , 1532735917,1384750058 , 1532452232,1379015564 , 1532278295,1376464489 , 1531086345,1376579504 , 1529824837,1361624712 , 1599668886,1352469678 , 1602940424,1378254017 , 1618757558,1376169589 , 1614876261,1344322254 , 1603259129,1345908282 , 1603259287,1345908261 , 1598881487,1346509332 , 1599164402,1348846007 , 1596521135,1349230709 

[AngusJohnson]

Hi again Christophe.
There's no guarantee of a one-to-one relationship when offsetting (or indeed when clipping either) so I don't consider this a bug. And in this case, given the very high degree on precision you're providing in the input, what might seem collinear may not in fact be so, and the offsetting algorithm is likely squaring a join seemingly unnecessarily. What I suggest is that you call SimplifyPaths after offsetting (with a suitable epsilon value - perhaps 50 in this case).

[ccoustet]

Hi Angus,
It is true that calling SimplifyPaths can remove these tiny segments (with epsilon in the [40 400[ range in the present case). however, I can imagine that providing an adequate epsilon for every polygon will be really challenging. And also, I tried to limit precision (from 6 to 2) with the same output.
What surprises me, but maybe this is the result of a misunderstanding, is that the number of vertices increased with a negative offset. I would have guessed that this could only occur with positive offsets, and that the vertex count could only decrease when using negative offsets.
An additional piece of information I could have added to my first message is that this behavior is the result of commit df1c129.

[AngusJohnson]

I would have guessed that this could only occur with positive offsets, and that the vertex count could only decrease when using negative offsets.

Not necessarily. Using your vertices from above, the vertex marked red in the image below is very slightly concave. And negative offsetting concave vertices will require mitering, squaring or rounding, unless the angle of deviation is too small to justify this treatment.

Edit:
Q. When is this angle of deviation small enough to be treated as if there's no deviation?
A. Currently it's cos^-1(0.99) ... approx 8 degrees.

Edit2:
In OffsetPoint in clipper.offset.cpp you could try...

  if (cos_a > 0.99) // almost straight - less than 8 degrees
  {
    group.path.push_back(GetPerpendic(path[j], norms[k], group_delta_));
    if (cos_a < 0.9998) // greater than 1 degree (#424)
      group.path.push_back(GetPerpendic(path[j], norms[j], group_delta_)); // (#418)
  }