Methods for searching for arrangements of shapes subject to boundary distance constraints among those shapes

Abstract

This disclosure describes methods to manufacture one or more articles of manufacture that searches for an arrangement of shapes that satisfy exact or approximate analytical representations of boundary distance constraints. The disclosed methods include the execution of the following steps: step (a) constructing functions for one or more boundary distance constraints; step (b) constructing an analytical optimization problem which incorporates the constraint functions of step (a); step (c) selecting the initial values of one or more optimization variables; step (d) solving the optimization problem constructed in step (b) using one or more analytical optimization methods and one or more of the initial values of step (c).

I claim the following invention: 
     
         1 . A method to manufacture one or more articles of manufacture that searches for an arrangement of shapes that satisfy exact or approximate analytical representations of boundary distance constraints using the execution of the following steps comprising:
 (a) constructing functions for one or more boundary distance constraints where said functions are exact or approximate analytical representations of said constraints using one or more external boundary surface of closest approach functions where at least one of the external boundary surfaces of closest approach is a non-n-sphere and each external boundary surface of closest approach is formed from two shapes and, optionally, additional boundary distance constraints between the shapes and is determined using the addition of two or three functions where one of the three functions represents the first shape and another function represents the second shape and, optionally, a third function represents the additional boundary distance constraints between the shapes;   (b) constructing an analytical optimization problem which incorporates said constraint functions of step (a) and which is an exact or approximate representation of a boundary distance constrained arrangement problem;   (c) selecting the initial values of one or more optimization variables;   (d) solving the optimization problem constructed in step (b) using one or more analytical optimization methods and one or more of the initial values of step (c).   
     
     
         2 . The claim according to  claim 1  wherein said constraint functions of said step (a) further comprise using one or more analytical compositions. 
     
     
         3 . The claim according to  claim 1  wherein said constraint functions of said step (a) further comprise using one or more superellipsoid shape function approximations for the interior or exterior boundary surface of closest approach between a pair of axis aligned orthotopes with axis-aligned orthotopic boundary distance constraints where at least one of the boundary surfaces of closest approach is a non-n-sphere. 
     
     
         4 . The claim according to  claim 2  wherein said constraint functions of said step (a) further comprise using one or more superellipsoid shape function approximations for the interior or exterior boundary surface of closest approach between a pair of axis aligned orthotopes with axis-aligned orthotopic boundary distance constraints where at least one of the boundary surfaces of closest approach is a non-n-sphere. 
     
     
         5 . The claim according to  claim 1  wherein said steps are executed two or more times where said steps (a), (b), (c) and (d) may use any information generated in or used by previous said executions of said steps (a) through (d). 
     
     
         6 . The claim according to  claim 5  wherein for one or more of said executions of said step (b) constructs different said optimization problems for at least two of said executions. 
     
     
         7 . The claim according to  claim 1  wherein said constraint functions of said step (a) further comprise using one or more gradient shaping transformations. 
     
     
         8 . The claim according to  claim 7  wherein said constraint functions of said step (a) further comprise using one or more analytical compositions. 
     
     
         9 . The claim according to  claim 7  wherein said constraint functions of said step (a) further comprise using one or more superellipsoid shape function approximations for the interior or exterior boundary surface of closest approach between a pair of axis aligned orthotopes with axis-aligned orthotopic boundary distance constraints where at least one of the boundary surfaces of closest approach is a non-n-sphere. 
     
     
         10 . The claim according to  claim 8  wherein said constraint functions of said step (a) further comprise using one or more superellipsoid shape function approximations for the interior or exterior boundary surface of closest approach between a pair of axis aligned orthotopes with axis-aligned orthotopic boundary distance constraints where at least one of the boundary surfaces of closest approach is a non-n-sphere. 
     
     
         11 . A non-transitory program storage device readable by a computing device that tangibly embodies a program of instructions executable by the computing device to perform a method to manufacture one or more articles of manufacture that searches for an arrangement of shapes that satisfy exact or approximate analytical representations of boundary distance constraints using the execution of the following steps comprising:
 (a) constructing functions for one or more boundary distance constraints where said functions are exact or approximate analytical representations of said constraints using one or more external boundary surface of closest approach functions where at least one of the external boundary surfaces of closest approach is a non-n-sphere and each external boundary surface of closest approach is formed from two shapes and, optionally, additional boundary distance constraints between the shapes and is determined using the addition of two or three functions where one of the three functions represents the first shape and another function represents the second shape and, optionally, a third function represents the additional boundary distance constraints between the shapes;   (b) constructing an analytical optimization problem which incorporates said constraint functions of step (a) and which is an exact or approximate representation of a boundary distance constrained arrangement problem;   (c) selecting the initial values of one or more optimization variables;   (d) solving the optimization problem constructed in step (b) using one or more analytical optimization methods and one or more of the initial values of step (c).   
     
     
         12 . The claim according to  claim 11  wherein said constraint functions of said step (a) further comprise using one or more analytical compositions. 
     
     
         13 . The claim according to  claim 11  wherein said constraint functions of said step (a) further comprise using one or more superellipsoid shape function approximations for the interior or exterior boundary surface of closest approach between a pair of axis aligned orthotopes with axis-aligned orthotopic boundary distance constraints where at least one of the boundary surfaces of closest approach is a non-n-sphere. 
     
     
         14 . The claim according to  claim 12  wherein said constraint functions of said step (a) further comprise using one or more superellipsoid shape function approximations for the interior or exterior boundary surface of closest approach between a pair of axis aligned orthotopes with axis-aligned orthotopic boundary distance constraints where at least one of the boundary surfaces of closest approach is a non-n-sphere. 
     
     
         15 . The claim according to  claim 11  wherein said steps are executed two or more times where said steps (a), (b), (c) and (d) may use any information generated in or used by previous said executions of said steps (a) through (d). 
     
     
         16 . The claim according to  claim 15  wherein for one or more of said executions of said step (b) constructs different said optimization problems for at least two of said executions. 
     
     
         17 . The claim according to  claim 11  wherein said constraint functions of said step (a) further comprise using one or more gradient shaping transformations. 
     
     
         18 . The claim according to  claim 17  wherein said constraint functions of said step (a) further comprise using one or more analytical compositions. 
     
     
         19 . The claim according to  claim 17  wherein said constraint functions of said step (a) further comprise using one or more superellipsoid shape function approximations for the interior or exterior boundary surface of closest approach between a pair of axis aligned orthotopes with axis-aligned orthotopic boundary distance constraints where at least one of the boundary surfaces of closest approach is a non-n-sphere. 
     
     
         20 . The claim according to  claim 18  wherein said constraint functions of said step (a) further comprise using one or more superellipsoid shape function approximations for the interior or exterior boundary surface of closest approach between a pair of axis aligned orthotopes with axis-aligned orthotopic boundary distance constraints where at least one of the boundary surfaces of closest approach is a non-n-sphere.