Sangaku: Finding the Pole of Inaccessibility

Originally posted on the Agworld Developers Blog, hosted on Tumblr, on March 15, 2013.

Here at Agworld we deal a lot with Paddock boundaries. One of the things we’d like to know is where best to place an icon indicating where the paddock is, given its boundary. This isn’t a trivial problem. Consider a paddock in the shape of the letter “L”. The naïve approach of putting the icon in the centre of the bounding box obviously will break down badly in this case.

A better solution might be to find the centroid of the polygon that defines the paddock boundary. But the algorithms that do that are complicated, needing work-arounds for concave polygons and breaking down altogether for self-intersecting polygons. Plus, the centroid may often be rather close to a vertex, which is less than ideal.

What we really want to find is the centre of the blobbiest bit of the paddock. Basically the place that a human being would point to and say “put the icon there”. For every conceivable shape. Automagically.

Turns out that the best solution would be to find the so-called “Pole of Inaccessibility” for the paddock. That’s defined (by Wikipedia) as “the most distant point from the coastline”. I first heard about it from Stephen Fry on his QI programme, but have since done some research to figure out how to estimate a solution via the following iterative technique. Because it’s an NP-Hard problem, this technique isn’t guaranteed to find the maxima, but it does a pretty fast approximation.

The Algorithm

Step 1: Place an AABB Around the Polygon

This is easy; you just build up an AABB (which stands for Axis-Aligned Bounding Box) by looking at all of the points in the polygon. You then make it 10% larger, to avoid edge-cases. Note that here we’re also showing the initial solution of placing the icon in the centre of the bounding box.

Step 2: Place 11 Horizontal and Vertical Lines

Now we superimpose a grid of 11 horizontal and 11 vertical lines over the AABB. These mark the places where we’ll be looking for intersections between the grid lines and the polygon. Again, this is easy to do, as each line has it’s X or Y co-ordinate fixed. It is therefore quite trivial, and fast, to test each line segment in the polygon for intersection with each of the 22 grid lines.

Step 3: Find All Internal Line Segments

Consider a single grid line, horizontal or vertical. In the previous step, we marked the grid line whenever it intersected the polygon. It’s plain to see that, when you move along the grid line, the first mark denotes a transition from outside to inside, the second from inside to outside, and so on. It’s therefore very quick to find a bunch of horizontal and vertical line segments that are internal to the polygon. We can also quickly calculate the mid-point for each of these.

Step 4: Score Each Line Mid-Point

Now we iterate through each of these line segments and calculate their fitness, using some criterion. Here I’m trying to find the centre of the largest internal circle, so the fitness function is based on that. If you wanted to find the best place to display a text label, which is much wider than it is high, then you’d vary the fitness function.

Step 6: Rinse and Repeat

By this stage we’ve found our first candidate solution. We can improve that by shrinking the AABB to 70% of its size, centring it on the candidate solution, and going back to step 2. We use some kind of stopping criterion to break out of this loop. Perhaps when the AABB is very small, or when the candidate solution only changes by some small epsilon value, or whatever.

The Implementation

We’ve published two Ruby gems that implement this algorithm. The first, Sangaku, is a simple, generic 2D geometry library. Nothing special, but lightweight and suited to the problem. The second, Sangaku Eyeball, uses the Gosu 2D games library to allow you to draw polygons and then find the Pole of Inaccessibility for them. It was used to generate the screenshots above. Try them out!

This article was originally posted on the Agworld Developers Blog, hosted on Tumblr, on March 15, 2013, and is almost certainly out of date by now.