Designing the Model
Subtitle: The Ultra Hyper Totally Amazing Push Me Pull You Supercavitating Surface Effect Flying Machine · Part III
# Flites of Fancy
Building a model helps to get a feel for how the ideas developed in the previous posts Betz The Limit and The Pushmi-Pullyu might work. A catamaran (see Of Sailing Ships, Velociraptors, and Walking on the Moon) provides a relatively steady surface to attach the wind turbine. For this model, I ignored detailed calculations but used the method described in Yacht Design with Mathematics to create the hull form.
To keep the hull relatively simple, the freeboard (top edge of the hull) is a straight line except where it tapers at the stern.
The people at Flite Test put out lots of great videos showing how to create model aircraft and one of their videos shows how to make a hot wire foam cutter,
and how to build templates to create the shape.
The mathematical tools shown in the yacht design post can easily be modified to create the JA 37 Viggen jet shown in their video by modifying the shape of the section curves, and possibly using more than one homotopy, but for this project that’s not necessary. A few section curves along the length of the hull, and sheer and freeboard/profile curves at the bow and stern should be sufficient. Here’s a plot of the curves drawn in Octave,
The top two rows are sections while the bottom row (from left to right) shows the half-bow sheer, half-stern sheer, bow freeboard and profile back to the first section, and the freeboard and profile for the aft section. The reason for using only half the sheer curve is that the sheer and freeboard/profile curves can be combined at right angles on a piece of foam to cut the bow and stern pieces. It might be useful to first cut the general outline by using two copies of the first and last sections.
To make the bow, make two rectangular blocks of foam that are half the width of the boat at the first section, as deep as that section, and the length of the distance between the bow and the first station. Attach a copy of the section template at both ends and use the hot wire cutter to generate the hull shape at the section curve.
Separate the two pieces of foam, and attach the sheer curve template to the top, and the profile to the inner edge. Now use the hot wire cutter to remove the excess foam to shape the bow, and glue the two pieces together. The same process can be done at the stern.
Print the curves and then paste them to a board to cut the shapes. If you have a CNC machine you can import the svg code directly into jscut to generate the gcode, or use gcmc and Matilda.
But, there’s a lot of wasted space in the plot generated by Octave. If you’ve ever tried to pack a bunch of stuff in the trunk of your car as you leave for vacation, or had to pack a trailer or rental truck full of household items for a move, you understand that efficient packing is key.
There’s a math for that. But first,
# … or Is It?
Many problems that we ask computers to solve are very easy, just tedious, which is why we like to have the computer do it. Adding a column of numbers, multiplying two large numbers together, sorting a set of words in lexicographic order, and searching for a string of words in a document are all the sorts of problems that computers do very well and quickly. If you ask a computer to sum numbers and it takes seconds, you’d expect that finding the sum of similar numbers would take about seconds. Problems that can be solved in time where is a polynomial are said to be in class , and there are efficient algorithms for finding the answers. The time required is called polynomial time because of the polynomial relationship between the number of inputs and the processing time required, .
Problems in the class (nondeterministic polynomial) are easy to check in polynomial time, but nobody has found an algorithm to solve them in polynomial time. The nondeterministic part means that whatever state the computer is in at one point of the algorithm doesn’t necessarily define what state will be next. KenKen puzzles are in because they’re difficult to solve but easy to check. Every problem in is also in because you can check the answer just by solving the problem again.
Why is there a question about being equivalent to ? Suppose you found some tricky algorithm that could quickly solve a KenKen puzzle in polynomial time. KenKen is thought to be in a sub-class called complete which means that you can try every possible combination of solutions to see if one of them works (and it’s easy to check if the solution is correct). It turns out that finding a polynomial time solution to an complete problem would unlock solutions to all other problems. hard problems are all the problems that are at least as hard as complete problems:
The vs problem is one of the seven Millennium Problems. Find an answer to any one of them and the Clay Mathematics Institute will give you one million dollars.
# Bin Packer, Bin Packer, Pack Me A Bin
In a two-dimensional bin packing problem, we have several shapes (in our case section and bow/stern curves) that need to be optimally fitted into an area. Usually, the area is a rectangle, but that’s not a requirement. The bin packing problem is in the class hard meaning that there isn’t a known algorithm that can optimally fill the bin in polynomial time. So the question we want to answer is, does there exist an order and orientation of items with areas such that the sum of the sizes of items is less than or equal to the bin size ?
There are quite a few heuristic methods available. These algorithms choose the next item to be placed based on the size and orientation of the item, looking at the remaining available space and possible future items to pack. You could put the largest item in the lower-left corner of the bin, the next largest beside that one, and so on until you’ve filled items up to the right wall. Now work your way back towards the left side, still filling large to small, like this:
To read about other methods, see “Survey on two-dimensional packing”. If you have just a few items to pack, you might try all possible arrangements, which is called the “brute force method”. Implementing any of these algorithms might be considered “work”, which we’d like to avoid. Instead, there’s a very nice (free) nesting tool called Deepnest that handles the nesting for us. Download and install Deepnest, and then run it. You should see something like this (without the curves, yet):
Click on “Import” to begin selecting curves generated by Octave. When you’ve imported all of them (only 5 shown here) click on the “+” at the bottom of the page which will let you add a bounding rectangle that will become the container bin. Set the dimensions of the container and click “Add”. This generates the rectangle shown at the top of the page. Under “Sheet”, make sure that only the bin is checked to indicate which item is the container. In some cases, you may want to increase the quantities of some curves, which may be adjusted under the heading “Quantity”.
You may also want to adjust the configuration parameters by clicking on the gear shown on the left side.
Hovering your cursor over any of the gray boxes brings up help information on the right side. Click on the Deepnest icon to return to the main page when done.
Next, click the “Start Nest” button which will switch to the nesting window,
Nesting continues until you click “Stop nest” because the algorithm never knows if it’s found the best possible solution. With just five pieces, it found a solution that gets all of them inside the bounding box, but there might be another way to do it that makes them fit more compactly. You’ll have to run it until you think you’ve got a good enough fit. At that point, click on “Export” and save the nest file in .svg format.
Deepnest uses a method called a Genetic Algorithm. Genetic algorithms mimic biological genetics by encoding information in strands of DNA, or what mathematicians call vectors. A vector is just an ordered list of numbers like, . While working at the Institute for Advanced Study in Princeton, NJ, Alan Turing and Nils Barricelli used the IAS machine at night (when it wasn’t being used to design the bomb) to study artificial life. Historian George Freeman wrote about the early work done building the first electronic computer at the IAS, “Turing’s Cathedral”, and gave a TED Talk, “The Birth of the Computer”.
Genetic algorithms are a descendent of their early artificial life experiments, and use evolution to find near-optimal solutions to problems. A population of vectors is created randomly, the vectors are paired off to generate a new generation of offspring vectors and the best of breed are kept for subsequent generations.
Deepnest may be generating vectors where the numbers come in pairs. The first number is the piece number, and the second of the pair could indicate the orientation angle. The default number of orientation angles is , but you can change this in the configuration window.
One way to encode the orientation would be to use a “1” if the orientation is on the positive axis, “2” for positive , “3” for negative and “4” for negative ,
A vector describing the order that items are placed in the bin and their orientation might be
meaning that the item would be placed first and it would be oriented along the axis, the item next along the negative axis and so on. By following the instructions in this DNA vector, the algorithm knows how and in what order to place each item. When it’s done, the algorithm measures how much space was needed, and how many items were placed.
The genetic algorithm creates many of these DNA vectors and then randomly selects pairs to “breed” a new generation. Breeding is done by randomly selecting a point along the vector, snipping off the ends, and then swapping DNA.
Suppose you created a second vector with random placement order and orientations,
Snip the ends off of and and swap the segments to form two new offspring vectors, and ,
In terms of the bin packing algorithm, this generates new packing rubrics that may be better than the original pair. In any case, we can try out both and pick the two best of . With a large population of random DNA samples, the genetic algorithm rapidly converges to a very good solution.
There is a flaw with using this method for the bin packing algorithm because in almost every swap it’s likely that you’ll be packing two of some items, and none of some others. In notice that the first item packed is with orientation , but then appears again at the end with orientation . If you want to pack one of every item, you could choose a permutation of the numbers . There are permutations and by choosing the next larger power of two, you could encode the permutation in binary.
In the example above, there are the eleven sections and bow/stern curves, and . This would take digits in binary, something like
so the DNA vectors would become a bit longer, but not unmanageable. The first digits (s and s) form a unique binary encoding of a permutation of the numbers , while the last numbers are randomly selected orientations. You have to create the binary encoding larger than , and so some mappings won’t work, but fortunately the coding for this problem is handled by Deepnest.
# Greek Myths
For most applications of Deepnest, the items are visually distinguishable, but the section curves for this model are nearly identical and after they’ve been placed in the bin it’s hard to tell one from another. One possible solution would be to include a unique number or letter with each item in .svg format. Another way would be to compare shapes since .svg files encode the locations of all points in the item. Of course, svg stands for “scalable vector graphics”, so the encoded dimensions may change, and the orientation very likely is altered.
This is where Greek myths meet math geeks. In Greek mythology, Procrustes, the son of Poseidon, is described as an innkeeper and a bandit. Anyone who stayed at his inn had to fit the bed Procrustes provided, and nobody ever fit exactly. If the visitor was too short, Procrustes stretched him until he was long enough, and if he was too tall, his legs got cut off at the end of the bed. You might be better staying at . In the end, Theseus fits Procrustes to his own bed.
For all myths Greek and Roman, check out Liv Albert’s “Let’s Talk About Myths, Baby!” podcast. That must be a typo. It should have been, “Let’s Talk About Math, Baby!”. Theseus may not have been so great either; episode is “Theseus, Ruiner of Women & All Around Awful Person”.
Anyway, the Procrustes method finds the best fit between two sets of points and can make correspondences between the initial set of curves provided to Deepnest and the completed packed set. If you can’t get all of the curves on one sheet of paper or wood template, let Deepnest pack what it can, remove those items from the input set, and pack again until everything fits on several sheets.
Suppose you have two sets of points and where are the input points before Deepnest packs them and are the packed set. These points are in 2D, so each has coordinates . Deepnest shifts the set of points by some fixed distance (called an affine transformation), scales the points by a constant and rotates them through an angle . The rotation can be written as a matrix,
Deepnest changes the scale of the bin and everything in it which is why we need the scaling factor, but we’ll rescale both sets so we don’t need to find . To find the best match between an input set and nested set we need to find the best fit between “visitor” and “bed”. Mathematically, this means we need to find and that minimizes the function ,
The rotation matrix multiplies the and coordinates of point by
In polar coordinates, , and to get to we’ll rotate about the origin by some angle . Notice that the distance from the origin to both and is the constant .
So the coordinates of are . Using the trigonometric identities,
which is the result of the matrix multiplication by . The operator is the norm function, also known as the Euclidean Distance (Greeks again!), where
To find the affine translation that minimizes we can take the derivative and set it to ,
Let and be the centers of the points in and . This means that , so the optimal value of the affine transformation is just the difference between the centers, and substituting this value of into gives
To simplify, let’s call and , in other words, the locations of the points after subtracting the centers. This puts the centers of both sets at the origin.
The norm squared can be written as
Since is a rotation, the product , the identity matrix (all ones on the diagonal and zeros elsewhere), so , and since is a scalar (number) taking the transpose doesn’t change the value, so . Now, the first and last terms don’t have in them, so minimizing this with respect to is equivalent to finding the minimum of over all ,
The coefficient can be ignored because it only changes the value of the minimum, but removing the minus sign changes a minimum to a maximum.
Let’s call the array of translated points and the equivalent array for . Then if you multiply the result is an array, but along the diagonal are the terms . Adding up all of the elements of the diagonal of a matrix is called the trace of the matrix, so
By itself, this doesn’t seem that it helps much but the trace operator has properties that we can use, one of them being that for any pair of compatible matrices and , . For the arrays here, this means that
Next, let . Since is a array and is then is . Using the Singular Value Decomposition (svd) we can write as
The matrices and are unitary meaning that if you multiply them by their conjugate transposes you get the identity matrix. The matrix in the middle, is diagonal and the elements on the diagonal are called the singular values. Substituting into the equation for the trace,
Since and are all orthogonal matrices then the product is also orthogonal, so columns of are orthonormal vectors and all of the entries of are less than or equal to one, meaning
Since we can bound the trace of as
To maximize each entry must be which means that is the identity matrix. In other words,
We can get the rotation matrix that maps into by calculating , computing the svd of , and then getting . Very simple!
This is the basis of the Procrustes method when and have the same number of points. In many cases, points will be missing from one set or the other and the Procrustes method needs to be modified. One way to do this is with The Softassign Procrustes Matching Algorithm.
The Octave function
idNestObjects.m reads in the set of .svg files generated by
bez2svg.m and the file of nested objects from Deepnest, makes the corresponding identifications and plots the curves with their identifying file names. On the left is the result of the Deepnest packing algorithm and on the right is the identification by Octave:
# The Recipe
To build a model boat using foam and a hot wire cutter, follow these steps:
- Draw the hull lines (sheer, freeboard, profile, sections, homotopy) as described in Yacht Design with Mathematics. You can use the online version of Geogebra if you don’t want to download it.
- Using the Octave function BezierHull.m, generate the lines structure:
BezStruct = BezierHull(<fName>);.
- Make a new directory for svg files, then run bez2svg.m:
- Install Deepnest.io, load the svg files, and begin packing. Stop when a good solution is found, and save the nested svg file.
- Identify the parts using idNestObjects.m:
idNestObjects(<svgDir>,<NestFile>);. Save the image with ID’d objects so you can match it to the nested svg file later. You’ll need the Octave/Matlab function v2struct.m which is called from
idNestObjects. Delete curves in the input list in Deepnest and repeat until all of the objects have been nested. Inkscape is useful for plotting svg image files.
- Print the curves, cut them out, and attach them to the foam blocks. Build the hot wire foam cutter, and begin cutting out the hull.
If anyone asks, you’re not making a toy boat out of old pieces of Styrofoam you threw in the garage for some project, you’re …
Applying a genetic algorithm to determine a heuristically optimal solution to an hard bin packing method of orthogonal sections through a smooth manifold generated from Bezier polynomials and homotopies, and then applying the Procrustes method to form a bijective mapping between pre and post-packed coordinate sets. It sounds a lot more important that way.