Headline:Square Pegs, Round Holes, and Convex Polygons
Date:Thursday, April 25, 2019
Posted By:Plaid Hatter Games

I knew I was getting off way too easy with my little scheme to number plots of deck on the ship. I'm going to be talking math for a little bit here, so anyone whose eyes glazed over in Geometry class, you have been warned.

When I render my deck layouts in SVG format, I currently lay down vectors. Imagine if I was drawing this on paper, and describing to the computer all of the instructions for how to move the pen. Our eyes can chop up the screen into tiles, and follow the boundaries to turn that large circle in to a set of odd shaped tiles. Computers aren't quite so smart.

For a computer I have to write an algorithm to explain how to pair one location on the page with what section of the ship it corresponds to. That algorithm is pretty simple, take the X and Y, convert that into a polar coordinate (distance and angle), with the center as the middle of the deck. I can then consult a lookup table of the ranges for each sector.

What I can't do with either the vectors or the polar coordinates is apply color to individual sectors. To fill in a color, I need to be able to describe to SVG an area. Tracks I can do, because they are circles, and circles have an area. Most rendering platforms I am familiar with virtually insist that every area that isn't a conic section should be a polygon. My sectors, with two edges as straight lines, and two edges as arcs are not, technically, polygons.

SVG has a workaround called a "path", that can take complex ingredients like curves:

The notion, though, is ... complicated:

<?xml version="1.0" encoding="utf-8"?>
<svg viewBox="0 0 250 250" xmlns="http://www.w3.org/2000/svg">
  <path style="fill: rgb(216, 216, 216); stroke: rgb(0, 0, 0);" d="M 9.745 148.574 C 13.378 112.705 89.749 23.829 135.516 9.618 L 222.972 158.995 C 186.433 167.407 155.162 230.01 167.601 220.403 L 9.745 148.574 Z"/>
  <path style="fill: rgb(216, 216, 216); stroke-dasharray: 4px; stroke: rgb(255, 15, 15); stroke-linecap: round; stroke-width: 3px;" d="M 166.065 222.607 L 223.916 158.312"/>
</svg>

Paths do satisfy the goal of giving me a region to color. But paths do not allow me to use any of my other math tools. Those tools need polygons with straight sides. And not just any polygon, a Convex Polygon.

In the graphic above, the red dotted line is the most direct path from one corner to the other. Not that it passes out of the sector. Notation issues aside, sectors are not a great fit for my tools mathematically.

The simple answer is take the same corners of my sector (in X and Y) and then just make a polygon of the same dimensions. Except that doesn't work:

I end up with a shape that covers over an area outside of the sector on the inner edge, and misses a big chunk of the sector on the outer edge.

If I break the polygon into two pieces:

It's still not perfect. I still miss areas in the outer region of the sector. And I still cover areas outside the sector on the inner region. But the errors are much, much smaller. In fact, the smaller I chop the sector with a polygon, the better approximation I get:

And if I could somehow make a polygon that was infinitely narrow (i.e. a straight line) I could fit the sector perfectly! If only. (And that was a little calculus. Sorry.) The problem is that a straight line has no area, and that as I add more polygons, the math of movement takes longer and longer to process.

Accounting for this sort of slop in math is not all that unheard of in engineering problems. It's just one type of slop that has to be accounted for. The other is the fact that building a physical object means that parts will be ever so slightly out of alignment. Either the a plate comes out slightly thinner, or thicker from the factory. Or the welders were ever so slightly off putting the plate into place. A sound design accounts for some variation in the material. State of the art construction can't build things the size of a ship to better than a 1/4 inch tolerance, or 6.4 mm.

A 6.4mm tolerance basically means that any wall on the ship can be up to 6.4mm away from where it should have been on the drawing. And that is 6.4mm in any direction. If I am looking at a bunch of ships, all built to the same drawings, where the walls actually are is a mathematical cloud 12.8 mm thick, centered on where the drawing said the wall should have been. So, if my polygon approximation can keep the error to less than 6.4 either inside, or outside, of the sector, that is as good as I was going to get from a decent shipyard anyway.

Another factor to consider is that flat plates are much easier to construct than curved plates. When trying to build this ship, plates are made in a factory, shipped, unpacked, and then finally dragged out to their final location to be welded. That is a lot of handling. Shipping and tracking curved plates is going to be a nightmare, on top of the nightmare of fabricating them.

Think of the difference between building a jigsaw puzzle and tiling a floor.

I suppose that plates could be curved on site, but that would require a monster of a machine to do that, and I suspect the tolerances on plates formed like that won't be terribly good. (Fine for an artistic feature, but not something you want to rely on for structural integrity.)

If the design calls for miles and miles of curved plating that has to be essentially formed on site, that is going to make the vessel tremendously expensive to construct.

The right answer may be to keep the sectors as a kind of artistic goal, but when it comes to storing shapes in a database, use something that conforms to how the ship will actually be built. Namely the physical plates the ship is made from.

I haven't written a plate model for this application yet, but the output would look something like this:

The grey squares are deck plates. You can see we just lay those out like tiles on a floor. The blue and black lines are wall plates. For them we start at one point on the shape, flop the plate on the floor, and then rotate it until the other side is back on an imaginary outline of the shape we are trying to form. And then, take the next plate off the stack, and drop it down where we left off the first, and continue until we have gone all of the way around the perimeter of the sector. Where we have excess plate, we will have to cut it down before welding, so those are the chunks of plate that seem to extend out from the shape itself. But in truth, that is exactly the way this thing would be constructed in real life.

The red dotted line are logical divisions inside the space that aren't real plates, but allow the shape to still be treated as a convex polygon. We do take a shortcut and make those logical lines emanate from the physical extents of the plates themselves.

From a structural perspective, the sector is the shape that is formed by following all of those plates around. From a math perspective, it is any point in X and Y that is inside the area of one of those three polygons.

A nice side effect of that is that same procedure could be expressed in a number of ways that are useful to the project. The shapes I produce could also include slight alterations to account for other design elements. (Say, a corner that needs rounding off to allow robots to pass, or a chunk of ductwork.) That same database can also drop right into a render description language like POV Ray or OpenGL to produce 3d visuals. I could also design an export to go to a CAD model if someone actually wanted to try to build the thing. (I dunno, maybe for a movie set, or dare I say, an actual spacecraft.) This technique could also export to finite element analysis software to see if it holds up to the loads demanded on it.

Each of those models have different rules about the shapes. The idea is that instead of having one "shape", we store how to make those shapes. We then adapt the output to the nuances of the format.

My SVG vector drawings are one expression of the "shape". A plate model is another form. The database of plates used for the crew navigation system is still a third. The OpenGL model is a fourth. They are procedurally produced from the same maths, but will each be expressed in radically different ways.