Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

minkovski sum of polytopes #87

Open
mvnayagam opened this issue Dec 4, 2023 · 5 comments
Open

minkovski sum of polytopes #87

mvnayagam opened this issue Dec 4, 2023 · 5 comments
Assignees

Comments

@mvnayagam
Copy link

Dear Developers and users,
I am trying to get the Minkovski sum of polytopes from my calculations. does the Polytope package provide such options?
if yes, how should it be done? if not, your alternative suggestions are more welcome.

I used '+' as implemented in the polytope package, but it returns the region instead of the single polytope. I want to find the Minkovski sum. the resultant should be a single polytope that covers or contains given polytopes as subspace.

appreciate your time on this issue

Thank you

Best regards,
Muthu Vallinayagam
Researcher, Institute of Experimental Physics,
TU Freiberg, Germany

@slivingston slivingston self-assigned this Dec 6, 2023
@DavidUmsonst
Copy link

Hi Muthu,

As far as I know there is no implementation of the Minkowski sum in the polytope package.
However, to compute it you could use Equation (2) of this paper.
The idea is that you could first get the vertices from the two polytopes you want to sum, let's call them poly1 and poly2, via the extreme function. Then you sum the vertices of poly2 and each vertex of poly1 to obtain a new set of vertices, whose convex hull (using the qhull function) is the H representation of the Minkowski sum of poly1 and poly2.

If you look for an implementation, my colleague and I have recently published open-source code for our Robust Tube Model Predictive Controller. For that we had to implement several functions for polytope objects from the polytope package, such as the Minkowski sum.
Note, however, there we used the qhull function only for one dimensional polytopes and otherwise the scipy.Spatial.ConvexHull function, since it was faster.

Best,
David

@slivingston
Copy link
Member

@DavidUmsonst Thanks for showing us your code and manuscript!

@slivingston
Copy link
Member

Your implementation of the Minkowski sum may be of general interest (beyond MPC). Would you consider submitting a pull request for inclusion in this repository, or do you prefer to keep it separate?

The only issue is that you have an MIT license in Robust-Tracking-MPC-over-Lossy-Networks, whereas we use BSD license here.

@mvnayagam
Copy link
Author

@DavidUmsonst Thank you very much for your answer and thanks for your code. I tried to work out the examples for Minkowski sum and tried for my cases. In the example, the box2poly from polytope is used to show how the mink_sum function works. After plotting I see the mink_sum contains given bo2poly's. Everything goes well until this point.

My polytope problem

In my project, I am dealing with polytopes in three-dimensional space. As an example, I show two polytopes from my calculation

polys

I used your mink_sum function to sum both the polys and obtained the following result

  • polytope 1: blue color
  • polytope 2: red color

poly_unshifted

  • resultant polytope: green color
  • The red point: the closest corner to the origin from polytope 1 and polytope 2 ( which has the coordinate [0.32738, 0.14126, 0.14126] )
  • The black point: the closest corner to the origin from the mink_sum resultant polytope ( which has the coordinate [0.66072, 0.28518, 0.28518] )

The resultant polytope is shown in green. It is shifted in the space away from the given polytope 1 and polytope 2 due to the summation of coordinates. So I tried to translate the green polytope with respect to the black and red points. I obtained the following results

poly_shifted

As per my understanding, the polytope from mink_sum of two polytopes should enclose the given polytopes, at least in my project it should.

So anyone in this condition may have a look at this method to translate the resultant polytope. However, this method somehow works in this example polytopes and may fail with other polytopes. Still, I have to work with many other polytopes to verify it.

Again thank you very much for your help and code. Indeed, It is more helpful in my project.

Thank you

Best regards,
Muthu Vallinayagam
Researcher, Institute of Experimental Physics,
TU Freiberg, Germany

@DavidUmsonst
Copy link

Your implementation of the Minkowski sum may be of general interest (beyond MPC). Would you consider submitting a pull request for inclusion in this repository, or do you prefer to keep it separate?

The only issue is that you have an MIT license in Robust-Tracking-MPC-over-Lossy-Networks, whereas we use BSD license here.

@slivingston Sorry for the late reply! I was told that it is possible to have two different licenses, since the MIT and the BSD license are compatible. We could do a pull request with our code and we could include a license header that our code is has an MIT license, if that would be ok for you.

@mvnayagam Sorry for the late reply!
I don't think that the Minkowski sum of two polytopes should be a contain both A and B. The Wikipedia page for the Minkowski sum has an illustrative picture on why this is not necessarily the case. Therefore, looking at the red and blue polytopes, in your case, it makes sense that their Minkowski sum does not contain these polytopes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants