Fence Posts and Pylons

March 18, 2008

Here's a quick research note (nothing completed, but just a quick idea).

A couple of times in developing systems for automatic generation of content, I've had to calculate the orientation of a two dimensional object based on geometry that it connects. Fence posts, for example, should be oriented so that each adjoining panel leaves on a side. A pylon should be oriented so that it minimises the angle to each outgoing cable.

The Quick Way

We have n input angles (θ_i) s to an object with m faces (where m > 1 and n > 0).

We want to construct an error term that we can minimise. So we can sum the error for each incoming panel and find the minimum of the resulting function to find the best possible facing for our post. For just about any error function this isn't tractable beyond one or two incoming angles. But using the cosine as the error term we can avail ourselves of the fact that sine and cosine sum easily.

So the error for one angle is cos(φ + mθ_i), where φ is the angle of the post and m is the number of panel sides.

If we sum this we get a result of the form Kcos(φ + mθ_best), and this immediately gives us the result that the post should be angled at θ_best.

We aren't interested in K, it doesn't change the result. We can get θ_best from:

Code

In pseudo-code this looks like this:

real calculate_facing_angle(array<real> input_angles, int post_faces) 
{
    real sine_sum = 0.0;
    real cosine_sum = 0.0;
    for (angle in input_angles) {
        sine_sum += math.sin(angle * post_faces);
        cosine_sum += math.cos(angle * post_faces);
    }
    return math.atan2(sine_sum, cosine_sum) / post_faces;
}

Problems

Because this is an equal weighted calcuation it means that it will still send panels out of the corners of posts, if it means that other panels are in the center of their posts. Most of the time it does pretty well, as shown in the images below.

To improve things we'd need to use a different error term that disproportionately penalises corner placement. I'm still on the search for such a term that can be very simply summed and minimized. In my production code I've got a simple sanity check that sees if this method failed, and kicks in a more analytic form, which takes longer (more of that later). So far it seems to be needed only one in twenty times for 3 or more incoming panels, and never for 2 panels.

Since the vast majority of (my) use-cases are 2 incoming panels, this is reasonable.

The Accurate Way

If you think about the problem, you'll see that we're not actually interested in minimizing the average incidence angle, we are interested in minimizing the maximum incidence angle. The maximum incidence angle belongs to each incoming panel in turn. We can plot the incidence angle against the angle of the post and see where the minimum occurs.

It always occurs equidistant between two consecutive panels. So if we can sort the panels we can walk through these points and keep track of the minimum (as shown in the graph above). The only thing to remember is to make sure you wrap around at the extreme limit and compare the last with the first.

This gives a better solution for larger numbers of incoming panels, at the expense of sorting the panel angles. Profiling, the quick-and-dirty method in my implementation is around 2x faster than sorting for large numbers of panels.

These examples show 12 test-cases in both algorithms. The trig algorithm is on top and the sorting algorithm is below. There are two cases where the sorting algorithm does visibly better. In both cases there are many incoming panels (the top coloured example has 4 - two coming in from the top from very similar directions).