Minkowski Sum bug?

[antoniospagno]

Hi,
I'm trying to do the Minkowski Sum between a pentagon and a small linear segment.

Below is the C# code I'm using.

`
double r = 5;

       double twoPi=2 * 3.141592654;

        List<PointD> patternVers= new List<PointD>();
        
        for (int i = 0; i < 5; i++)
        {
            patternVers.Add(new PointD(r * Math.Cos(2*Math.PI * i / 5 + Math.PI/2), r * Math.Sin(2 * Math.PI * i / 5 + Math.PI / 2)));

        }
        
        PathD pattern = new PathD(patternVers);

        List<PointD> pathVerts = new List<PointD>() { new PointD(0, 0), new PointD(1, 0) };

        PathD path = new PathD(pathVerts);

        PathD minkSum = Minkowski.Sum(pattern,path, false)[0];`

The result I get does not satisfy me because I expected to obtain a convex polygon with 5 vertices and I don't understand if there is some enum to change inside the MinkowskiSum parameter or if it is a bug

[AngusJohnson]

Yep, it looks like a bug. I'll investigate.

[AngusJohnson]

Yep, it looks like a bug. I'll investigate.

Or maybe it isn't a bug 😁.

Is that what you were expecting?
If so, then you just needed to close the path 😱.

      PathD pattern = Clipper.MakePath(new double[] { 0, 0, 1, 0 });
      PathD path = Clipper.Ellipse(new PointD(5, 5), 5.0, 5.0, 5);
      PathsD solution = Minkowski.Sum(pattern, path, true); // TRUE == CLOSED PATH 

[antoniospagno]

Hi Angus,

thank you for your reply, but this is not the expected result. Let's consider an analogous situation but with a longer path:
List<PointD> pathVerts = new List<PointD>() { new PointD(0, 0), new PointD(10, 0) };
In this case, the result is the following and the expected:

So for the case I submitted where the path is shorter, I would expect a similar but smaller polygon

[antoniospagno]

In the original case that I submitted to you the problem is probably generated by the fact that the pentagon at the beginning and the one at the end of the path intersect

[AngusJohnson]

So for the case I submitted where the path is shorter, I would expect a similar but smaller polygon

And it is ...

      PathD pattern = Clipper.MakePath(new double[] { 0, 0, 1, 0 });
      PathD path = new PathD();
      for (int i = 0; i < 5; i++)
        path.Add(new PointD(5.0 * Math.Cos(2 * Math.PI * i / 5.0 + Math.PI / 2), 
          5.0 * Math.Sin(2 * Math.PI * i / 5 + Math.PI / 2)));
      Console.WriteLine(solution);

0.50,4.64 4.76,1.55 2.94,-4.05 3.94,-4.05 5.76,1.55 1.00,5.00 0.00,5.00 -4.76,1.55 -2.94,-4.05 -1.94,-4.05 -3.76,1.55

and what it looks like but without the union operation in Clipper.Minkowski.cs (ln 71) so you can better see what's happening:

      PathD pattern = Clipper.MakePath(new double[] { 0, 0, 10, 0 });
      PathD path = new PathD();
      for (int i = 0; i < 5; i++)
        path.Add(new PointD(5.0 * Math.Cos(2 * Math.PI * i / 5.0 + Math.PI / 2), 
          5.0 * Math.Sin(2 * Math.PI * i / 5 + Math.PI / 2)));
      Console.WriteLine(solution);

10.00,5.00 0.00,5.00 -4.76,1.55 -2.94,-4.05 7.06,-4.05 12.94,-4.05 14.76,1.55

And again, but this time with the pentagon rotated ...

      PathD pattern = Clipper.MakePath(new double[] { 0, 0, 1, 0 });
      PathD path = Clipper.Ellipse(new PointD(5, 5), 5.0, 5.0, 5);
      PathsD solution = Minkowski.Sum(path, pattern, true);
      Console.WriteLine(solution);

7.55,9.76 6.55,9.76 0.95,7.94 0.95,2.06 6.55,0.24 7.55,0.24 11.00,5.00 1.95,7.94 6.74,9.50 10.00,5.00 6.74,0.50 1.95,2.06

      PathD pattern = Clipper.MakePath(new double[] { 0, 0, 10, 0 });
      PathD path = Clipper.Ellipse(new PointD(5, 5), 5.0, 5.0, 5);
      PathsD solution = Minkowski.Sum(path, pattern, true);
      Console.WriteLine(solution);

16.55,0.24 20.00,5.00 16.55,9.76 6.55,9.76 0.95,7.94 0.95,2.06 6.55,0.24

[antoniospagno]

Hi Angus,

I also asked this forum https://math.stackexchange.com/questions/4741496/is-this-minkowski-sum-result-correct for opinions regarding the result I get, and the most voted and frequent answer is that I gave an input polygon that is not closed. Of course I checked to close it. What do you think about this closed/open topic?

Another thing that makes me think that the result is obviously wrong is that the Minkowski sum of two convex polygons must be convex (see https://math.stackexchange.com/questions/2410875/the-minkowski-sum-of-two-convex-sets-is-convex ), while the result of the figure is clearly not convex.

Taking a closer look at your code, it seems to me that the Minkowski base method does its job well. In my opinion, the error could be more in the merge operation you do afterwards.