pythonoptimizationgeometryandroid-3.0-honeycombtessellation

Optimization Problem: Fitting Hexagons within a Domain


I have a geometry problem and I thought of using python to solve it (I have little experience). I need advice on how to approach the problem.

hexagons fitting

In the annex you can see the problem. I have a domain L x B and given the cell size of a hexagon (Ls), I found the maximum number of cells in straight (n) and zig zag (m) directions to cover the domain, staying within it. ErrorL and errorB are the errors that I commit between the boundary of the domain and the cells, since I have an integer number of cells to use, and this error should be minimized.

Here the simple code (maybe is possible to obtain it much simpler, but it works)

from scipy import optimize
import numpy as np

#case cells in L straight (n), in B zig zag (m)

L = 500
B = 200
Ls = 10
Lz = Ls*(3**(0.5)/2)

print('Ls =', Ls)
print('Lz =', Lz)
print('-------------')

def errorL(n):
    return abs(L-(Ls*n + Ls/2))

def errorB(m):
    return abs(B-(Lz*m + Lz/3))

resultL = optimize.minimize_scalar(errorL)
resultB = optimize.minimize_scalar(errorB)

a = round(resultL.x)
b = round(resultL.x)-1
c = round(resultB.x)
d = round(resultB.x)-1

if (Ls*a + Ls/2) <= L:
    print('n =', a)
    print('errorL =', errorL(a))
else:
    print('n =', b)
    print('errorL =', errorL(b))

if (Lz*c + Lz/3) <= B:
    print('m =', c)
    print('errorB =', errorB(c))

else:
    print('m =', d)
    print('errorB =', errorB(d))

This was an example with a given cell size Ls, now I would like to find a way to mantain Ls within a range [a,b] and find the best Ls, n and m to minimize errorL and errorB. Each minimization of errorL and errorB depends on two variables, but the choice of Ls affects both. I started writing a minimization problem with two variables but I am not sure how to proceed considering errorL and errorB to minimize with the same variable Ls. Furthermore I would like to work only with n and m as integer numbers. How can i do it?

Any suggestions is welcome.

Thank you very much

dr


Solution

  • At constant Ls, you need not to solve an optimization problem in order to fine m and n. You can simply set:

    n = floor((L-Ls/2)/Ls)
    m = floor((B-Lz/3)/Lz)
    

    and the errors will become:

    errorL = L-(Ls*n + Ls/2)
    errorB = B-(Lz*m + Lz/3)
    

    and of course Lz is equal to sqrt(3)/2*Ls

    So, both error values become functions of only a single variable i.e. Ls. Now you can define a single cost function (for example errorL*errorB or errorL+errorB) and minimize it w.r.t. Ls.