Comments (5)
@DavidUmsonst Thanks for showing us your code and manuscript!
from polytope.
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
from polytope.
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.
from polytope.
@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
I used your mink_sum function to sum both the polys and obtained the following result
- polytope 1: blue color
- polytope 2: red color
- 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
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
from polytope.
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.
from polytope.
Related Issues (20)
- cvxopt 1.2.0 bug HOT 5
- support Python 3.7 HOT 4
- create regression test for bug fix of PR #56
- release `polytope == 0.2.2` HOT 1
- Error message says "Cannot plot polytopes of dimension larger than 2", but can't plot dimension 1 aswell HOT 2
- Zero Volume for 14D polytope HOT 8
- remove support for Python 2.7, 3.5, 3.6 HOT 7
- support Python 3.10
- With large scales `reduce` can remove non-redundant hyperplanes HOT 2
- `.project` can return redundant hyperplanes despite `minrep == True` HOT 1
- Plotting polytopes on same plot/ adding "_get_patch" as an import option
- How to use cvxopt to find intersection between polytope HOT 4
- polytope volume changing on each trial HOT 2
- Polytope.reduce and removal of possibly overlapping polytopes HOT 3
- Updated release on PyPI? HOT 4
- Rmove or delete particular polytope from a region HOT 1
- combining many polytopes into single polytope HOT 4
- MIB2 cannot clear 01637 error HOT 3
- Usefull future feature
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from polytope.