A Con-Vexing Problem

This week in my research I've been trying to produce some figures that will go into a paper on the work I've been doing modeling the LIGO pendulums. The models use a tool from engineering called finite element analysis (FEA), which represent an object as a set of small pieces, called elements, which each have a number of properties assigned to them. For each element, we can calculate the forces applied to it to find how it moves and interacts with the surrounding elements. The problem I was having though was, given a set of these elements that make up a part, how do we find the outline of that part?

To make things more mathematical, I have a set of points in 2 dimensions (since I'm just looking for a top-down view), and I want to find a closed curve that contains all the points, but has the minimum area. As a zeroth-order approximation, we could just use a box with the minimum/maximum coordinates of all the points as the corners. That doesn't work very well for the set of points I was dealing with though:

Since this stage of the pendulum is tilted in these coordinates, we end up including a lot of empty space. We could do a little better if we rotated our box, but we're still not going to do great with right angles.

Another option is to try to find a convex hull. To get an idea what this looks like, you can imagine stretching a rubber band around the points. One method for finding the path is called the gift-wrapping algorithm, since it touches only the outer-most points, like wrapping a present. The algorithm builds up the path by looking for the largest angle to the next point. Wikipedia has a nice animation of this:

Wikipedia

Unfortunately, this only works for convex curves, meaning the shape can't have dents, like our point set does. That brings us to the idea of alpha shapes. These start by dividing the shape into a set of triangles. Each triangle can be assigned a radius based on the size of the circle that would be needed to surround them. We throw out any triangles with radius larger than a given value, then find all the edges that belong to only one triangle – This is the border of our shape. Below are two examples of this for different alpha values, which correspond to the inverse of the radius limit. The red triangles are those that don't pass the limit.

α = 1

α = 2

Below is a comparison of the borders for a couple values of alpha. The first plot is the convex hull, using the Jarvis algorithm, another name for the gift-wrapping algorithm. The second plot, with α = 0, is the same, since that corresponds to an infinite radius, so all the red triangles from above get included.

Once the paper is more complete, I may discuss it here in full, but I'm glad I was able to learn about this technique, so my figures can be a bit more informative.