## Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
##### Activity
Benoît Legat
@blegat
If you have equlalities Ax = 0
You need to start with rays spanning the linear subspace {x : Ax = 0} instead
That is, you need to first solve the double description for the affine hull
Then the rest of the algo is the same
Mathieu Besançon
@matbesancon

Only Ax <= b

you mean Ax <= 0 no?

Benoît Legat
@blegat
Yes :)
Mathieu Besançon
@matbesancon
:tada: for ConvexHull, I haven't digged into the incremental resolution yet
Marcelo Forets
@mforets
Hi! We were discussing in the JuliaReach room whether we can do "something" to help fix 3d plotting with Makie. There is JuliaPolyhedra/Polyhedra.jl#212 for some reason that wasn't fully working.
Does it make sense to ask help from someone from JuliaPlots?
Benoît Legat
@blegat
Yes, I wasn't abl
e to make it work with Makie with this PR either
Marcelo Forets
@mforets
ok. hmm we could try approaching folks from Plots / Makie. it's a pity that JuliaCon has already ended, that would have been a good venue.
Joey Huchette
@joehuchette
Quick Q: What's the simplest way to take the Minkowski sum of two Polyhedra.jl polyhedra?
Marcelo Forets
@mforets
P + Q should do it? if the polyhedra are in h-rep then this will compute the vrep and this can be costly (depends on your ambient dimension).
LazySets.jl implements a lazy minkowski sum to handle higher dimensional cases efficiently (and also specializes over the 2d case) and a concrete minkowski sum that uses Polyhedra+CDDLib but doesn't convert to vrep, using variable elimination, see LazySets.minkowski_sum.
Joey Huchette
@joehuchette
Got it--thanks
I was looking for a function named something like minkowski_sum, didn't even think to check the operators...
Marcelo Forets
@mforets
:thumbsup:
Benoît Legat
@blegat
In fact searching "minkowski" in the doc doesn't work as we don't include + in the doc
Joey Huchette
@joehuchette
Yeah, searching "+" in the docs doesn't yield anything useful, unfortunately
I also tried searching "+" on github but the results aren't very useful because it's so overloaded
Benoît Legat
@blegat
Should be resolved by JuliaPolyhedra/Polyhedra.jl@91c3ef3
Joey Huchette
@joehuchette
Thanks, Benoit
lgtm
Joey Huchette
@joehuchette
I have a polyhedron of type T <: Polyhedron, and want to create an empty polyhedron in the same ambient dimension. What's the best way to do this in a generic way? I.e. I only know that T <: Polyhedron
Benoît Legat
@blegat
julia> h = HalfSpace([1], 1) ∩ HalfSpace([-1], 0)
H-representation Polyhedra.Intersection{Int64,Array{Int64,1},Int64}:
2-element iterator of HalfSpace{Int64,Array{Int64,1}}:
HalfSpace([1], 1)
HalfSpace([-1], 0)

julia> p = polyhedron(h)
Polyhedron Interval{Int64,StaticArrays.SArray{Tuple{1},Int64,1,1},StaticArrays.Size{(1,)}}:
2-element iterator of HalfSpace{Int64,StaticArrays.SArray{Tuple{1},Int64,1,1}}:
HalfSpace([1], 1)
HalfSpace([-1], 0):
2-element iterator of StaticArrays.SArray{Tuple{1},Int64,1,1}:
[1]
[0]

julia> similar(p, Polyhedra.FullDim(p), Polyhedra.coefficient_type(p), hyperplanetype(p)[], halfspacetype(p)[])
Polyhedron Interval{Int64,StaticArrays.SArray{Tuple{1},Int64,1,1},StaticArrays.Size{(1,)}}:
1-element iterator of StaticArrays.SArray{Tuple{1},Int64,1,1}:
[0],
1-element iterator of Line{Int64,StaticArrays.SArray{Tuple{1},Int64,1,1}}:
Line([1])
Benoît Legat
@blegat
But that doesn't give you an empty polyhedron, rather a full-dimensional one that span the whole space ^^
To have an empty one, you need n + 1 equalities, e.g. https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/master/src/aff.jl#L66-L75
Joey Huchette
@joehuchette
thank you!
Gabriele Dragotto
@gdragotto
Hey! A quick and possibly silly question. I have a point and a polyhedron,and I need to check whether the point belongs to the polyhedron (I don't care wether it is the interior or anything else). Is there a quick way to do that?
Marcelo Forets
@mforets
yes, try with x ∈ P
(you have to type \in[TAB] for the symbol)
or just in(x, P)
this should check if x belongs to each and every half-space defining P
Gabriele Dragotto
@gdragotto
Thanks! I was recalling something like that in the docs, but I didn't manage to find it again
Marcelo Forets
@mforets
:thumbsup:
Andrei Leonard Nicusan
@anicusan

Hello all, long time no messages, I hope everybody is well. I have a few questions if that's alright:

• What would be the most efficient way to import an STL file into a Polyhedron? A sort of roundabout way I got working would use MeshIO to load it, then decompose it into an Array{Point{3, Float64}, 2}, then recollect that into an Array{Float64, 3}, which I then feed into vrep. There must be some better way...
• The translate function is extremely useful for a moving object; would it also be possible to implement a rotate function, taking a rotation matrix? I have multiple polyhedral rigid bodies translating and rotating through space and I need to compute their intersection volume when collisions happen - I would like to minimise the V- to H-representation conversions, so if we could translate and rotate both of these without creating new Polyhedrons, it would be amazing!
• Looking at the translate function's source code, it seems that we're losing the V-representation if the H- one exists. Could we translate both representations if available? It would mean creating new Polyhedrons with both V- and H- representations defined, so we'd have to ensure both refer to the same spatial object. Also, could we define an in-place translate! function to avoid creating new objects?

And a more open / subjective one:

• Are there any plans for closer interop with the JuliaGeometry stack, specifically Meshes.jl and GeometryBasics? E.g. creating Polyhedral approximations from the more continuous types there, like cones, cylinders or spheres? Both the JuliaPolyhedra and JuliaGeometry stacks are in most cases complementary, so perhaps merging or at least closer side-by-side development would be very helpful for a powerful geometry stack!
Marcelo Forets
@mforets
Hi @anicusan, maintainer of the cousin LazySets.jl project here. I think that all those are good concerns and the best way to go for items 2 and 3 may be that you make new issues in the Polyhedra.jl issue tracker.
About item 1, do you want to do sort of the "inverse" of what is done in decompose.jl, which creates a Mesh from a Polyhedron? or maybe thte parts of what you need is already there, but i'm not familiar enough with the code to say
Marcelo Forets
@mforets

E.g. creating Polyhedral approximations from the more continuous types there, like cones, cylinders or spheres?

you may find relevant stuff about polyhedral approximations of convex bodies in LazySets, see for example here and the methods in Approximations
Andrei Leonard Nicusan
@anicusan

Hi @mforets , thanks for taking the time to look into this, the resources you included here are very helpful! LazySets does include most of what I need, even more so than Polyhedra (which it does seem to build and expand upon) - thank you for developing and maintaining it. As I said, I would like to use it in accurate force models for rigid bodies (granular media specifically) which need intersection volume computations; this is rather hard to implement so most simulators today use gross approximations. Though LazySets was not specifically developed for rigid body dynamics, do you think it would be suitable as an efficient backend for more complex geometric operations?

I will post two new issues on Polyhedra.jl about rotation and in-place functions.

Regarding point one, the inverse of decompose is exactly what I need, for the very common mesh representations like STL, OBJ (which are what 3D modelling software use) - it would be useful to model complex shapes in a specialised graphical CAD-like program, then use LazySets.jl for the heavy maths.

If I seem to be chatting bollocks please call me out, my mathematical background is rather different from convex analysis and I do seem to want to use those packages in a non-standard way.

Marcelo Forets
@mforets

Though LazySets was not specifically developed for rigid body dynamics, do you think it would be suitable as an efficient backend for more complex geometric operations?

i can't tell without knowing in more detail what kind of algorithm you'd like to implement. with sets, there are many ways to do the same computation (either lazily, or concretely, or a combination of those, depends on which set representation is used, how does it behave with the dimensions, closedness under set operations linear map, minkowski sum, convex hull, intersection, and so on)

i'd say that that if your aplication requires that you stay in vrep or in hrep most of the time, then using Polyhedra.jl directly is the way to go. but if you require to solve large problems (high dimension or operations that involve many sets), or if you can delay some computations until some later point (eg. solve the 100-th term along some direction $d \in \mathbb{R}^n$ of the sequence $X_{k+1} = \Phi X_k \oplus V_k$ ) then LazySets has a lot to offer in terms of the flexibility of how to actually compute that very efficiently
Marcelo Forets
@mforets
that's the reason there is something like.. 43 different set representations in LazySets at the moment and we plan to add more (including concrete sets and operations between sets)
the idea is that any algorithm that is stated in terms of sets can be solved efficiently using the library
Marcelo Forets
@mforets
about in-place rotations and translations that's available in lazysets (though for in-place translation of every set i have an unfinished PR..). using Zonotopes is a good idea for those operations since translation (resp rotation) of a zonotope is again a zonotope.
Marcelo Forets
@mforets

which need intersection volume computations; this is rather hard to implement so most simulators today use gross approximations.

ok. the intersection of zonotopes is not necessarily a zonotope but you could use lazysets to simplify the intersection by overapproximating (or underapproximating) and get a better estimate. along the lines of : https://juliareach.github.io/LazySets.jl/dev/man/lazy_intersections/