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.

A randomly generated corral. Generated from a simple graph showing what areas should exist, the software first creates the paths for the fences, then places posts, then orients them using this algorithm, then builds out the fence geometry.

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 without the need to sort the panels (more of that next) or do a bunch of trigonometric calculations. Even though sorting a few panels (or even a few tens of panels) is trivially quick, a fast analytic solution would feel more satisfying to me.

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 at the expense of having to sort the panel angles. In practice the trig functions in my first error terms are far more complicated to calculate than sorting a 2-5 panels, but obviously we've upped the formal big-O order of the algorithm.

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).