3D bin packaging using Convex.jl

Intent :Write a convex function that takes a set of points of shape (m,n) basically convexhull points by reading a CAD model.

  1. The function must return a Variable(from Convex.jl) of shape/size of the original vector (to be used in optimization later - i have to estimate the coordinates) plus a set of affine constraints to keep it convex.

Here’s the code for the function

function vrep(v)
    λ = Variable(size(v)[1])
    x = Variable(size(v))
    c = zeros(size(v)[1])
    for i in 1:size(v)[1]
         c = c + λ[i] * v[i]
    add_constraint!(x,v' * x <= sum(x))
    add_constraint!(x,c <= sum(x))
    add_constraint!(λ,λ >= 0)
    add_constraint!(λ,λ <= 1)
    add_constraint!(λ, sum(λ) == 1)
    return x
  1. The idea is to fit together many such vreps of different sizes/shapes in R3 in a given box without any overlaps so to simplify i start with R2 assuming the same should work in R3
va = [0 0;1 0 ;1 1 ;0 1 ] # a unit square 
function get_nooverlap_constraint(m, n)
    Am = ones(size(m))
    An = ones(size(n))
    return ((Am' * m) - (An' * n)) >= 1
a = vrep(va)
b = vrep(va)

p = minimize(norm(a + b))
# ensure none overlaps 
add_constraint!(p, get_nooverlap_constraint(a,b))

solve!(p, () -> SCS.Optimizer(verbose=false))
print(a.value, b.value)
  1. Result : When i plot these points, i get the first two points in a single line and the rest three look ok - why is the first point estimated incorrectly? :
a : [-0.45427274477738133 -0.45418622832194044; 0.2049041263858669 0.20490966184077403; 1.0444644866772845 1.0443668979909329; 0.2049041263168114 0.20490966190984883]
b: [0.7042727350943662 0.7041862185089512; 0.045095874300268665 0.04509033885584125; -0.7944644863584401 -0.7943668978393343; 0.04509587423119381 0.0450903389248964]
  1. a few questions :
    a. should my objective function be minkowski sum instead?
    b. What is the right way to estimate the b such that it does not overlap - please see my current implementation - get_nooverlap_constraint I could not get the A’*n >= b & A’*n <=b constraint working
    c. will this implementation work in R3 because I have more constraints the no overlap, then a few boundary conditions, preference for certain part of the available configuration space, some no-go zones etc.
    please suggest/advice