Generalized Minkowski Sum calculation

49 views (last 30 days)
Is there any library or function to calculate Minkowski Sum of convex and concave polygons, I have found this - https://in.mathworks.com/matlabcentral/fileexchange/116000-closed-form-minkowski-sums in the file exchange but this only works for convex shapes (curved).

Accepted Answer

John D'Errico
John D'Errico on 1 Dec 2022
Edited: John D'Errico on 1 Dec 2022
The convex case is quite simple to solve. I could write code for that in a few minutes at most, because the Minkowski sum of two convex polygons must also be convex. But once you allow concave domains, things get more complicated. (I assume you are not asking about fully general polygons that may cross themselves, sometimes called a Catholic polygon. That would seem to add yet an additional level of complexity, though it would be resolvable I think.)
This is why you did not find one on the FEX, due to the complexities for concave polygons. The code on the FEX seems fairly well written, but it only works for convex domains.
How would I write it? Hmm. Actually, this seems quite solvable as I think about the necessary algorithm. All that is needed are the polyshape tools in MATLAB. The minkowskiSum code I have attached should work. It takes either two polyshapes, or two arrays of vertices comprising the polygons (which it turns into polyyshapes.) For example...
The minkowski sum of two triangles will be a hexagon. (If the triangles are equilateral, it will be a regular hexagon, but I've just used random triangles here.)
Pa = polyshape(rand(3,2));
Pb = polyshape(rand(3,2));
MSumShape = minkowskiSum(Pa,Pb);
plot(Pa)
hold on
plot(Pb)
plot(MSumShape)
hold off
The Minkowski sum of two squares is another square. The sum of a square with itself will be a square of twice the size in each dimension.
Pa = polyshape([0 0;1 0;1 1;0 1]);
plot(Pa)
hold on
MSumShape = minkowskiSum(Pa,Pa);
plot(MSumShape)
hold off
axis equal
That seems to have worked. Now for a pair of curved shapes, represented as polygons with a fair number of sides. How about a pair of ellipses?
t = linspace(0,2*pi)'; t(end) = [];
Pa = polyshape([2*cos(t),sin(t)]);
Pb = polyshape([cos(t),3*sin(t)]);
plot(Pa)
hold on
plot(Pb)
MSumShape = minkowskiSum(Pa,Pb);
plot(MSumShape)
hold off
axis equal
Again, that looks correct. Now for something more difficult: convex shapes.
Pa = polyshape([-1 2;0 2;-0.75 2.25;-1 3]);
Pb = polyshape([1 0;2 0;3 1;4 3;2 .3]);
plot(Pa)
hold on
plot(Pb)
MSumShape = minkowskiSum(Pa,Pb);
plot(MSumShape)
hold off
It should even work on self-intersecting polygons, though polyshape will give a warning message then.
Pa = polyshape(rand(6,2));
Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or unexpected results. Input data has been modified to create a well-defined polyshape.
Pb = polyshape(rand(6,2));
Psum = minkowskiSum(Pa,Pb);
plot(Pa)
hold on
plot(Pb)
plot(Psum)
Honestly, that is probably a meaningless mess, but it did work, and produces a result that I think is correct based on the crap I passed it. It did pass all the tests I threw at it.
Will this code run on an older release of MATLAB that does not offer polyshapes? Sorry, but no, and I won't offer a version that will run under earlier releases, since I won't spend the time to re-write the necessary polyshape operations.
You can also download minkowskiSum from the FEX, here:
  2 Comments
Ashish
Ashish on 17 Dec 2022
Could you please elaborate on the working time complexity of this function

Sign in to comment.

More Answers (0)

Categories

Find more on Elementary Polygons in Help Center and File Exchange

Products


Release

R2022b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!