Concentric Octagons

or, Sweet Jesus Why!?, being functional anti-pattern the seventh.

This anti-pattern will be presented in the form of a problem, with progressively better solutions until I arrive at a rough approximation of the original code.

The problem

You are provided with a source figure and a destination figure; both of these are arbitrary polygons. Your goal is to return the heading from the center of mass of the source polygon to the center of mass of the destination polygon.

A polygon is represented as a counter-clockwise list of points. The polygon is not guaranteed to be convex. To make your life easier, a function

centerOfMass :: Polygon -> Point

is provided. The centerOfMass function does not return (or not). You also have a function

polygonIntersections :: Polygon -> Polygon -> [Point]

which finds the (possibly empty) set of points at which two polygons intersect.

The First Solution

heading source dest = atan2 (y' - y) (x' - x)
   where (x,y)   = centerOfMass source
         (x',y') = centerOfMass dest

Unfortunately, this solution is too simple and takes too few lines to be seriously considered.

The Second Solution

From high school geometry, you may remember that the segment between the two points of intersection of two circles is perpendicular to the segment between their centers. We can take advantage of this to find the segment between their centers: first, we can use the centerOfMass function to find the centers of the polygons and then compute the distance r between the centers. Then, we can construct two circles, concentric with the polygons and each having radius r. Finally, we can find the points of intersection, compute the slope of the segment between them, compute the heading based on that slope, and then rotate it 90 degrees (since we want the heading from center to center instead of from intersection point to intersection point).

Unfortunately, there are several difficulties with this code. First, our library of routines does not include routines for manipulating circles, and while it may seem somewhat appealing to represent a circle as an infinite list of points, manipulating that list is likely to be difficult. A second difficulty is that the circles used are larger than they need to be. We will address both these problems in the next solutions.

The Third Solution

First, we will address the problem with representing circles. As I mentioned, we do not have either a representation for circles, or routines manipulating them. However, we do have code to manipulate polygons, so we can appoximate them. Obviously, the more sides a polygon has, the better approximation it will provide; for our purposes, eight should be fine. While this will introduce some deviation in the result, it will surely not be too much. We now have the function

octagonFromCenterAndRadius :: Point -> Double -> [Point]

whose implementation we leave to the reader.

Sadly, we have not yet found a use for infinite lists. Luckily, we have one more problem to solve.

The Fourth Solution

As previously mentioned, our solutions so far have relied on computing the distance between the centers of mass of the two input polygons, and creating circles (or octagons) of that size. However, this creates shapes that are larger than we precisely need. Instead, we can take advantages of infinite lists and filtering to ease this problem:

octagonsFromCenter c = map f [1..]
where f = octagonFromCenterAndRadius c

Now, we are better equipped to find the intersection points to use in the process from Solution 2:

intersectionPoints p1 p2 =
   take 2 $ head $ filter (not . null) points
   where c1 = centerOfMass p1
         c2 = centerOfMass p2
         points = zipWith
           polygonIntersections
           (octagonsFromCenter c1)
           (octagonsFromCenter c2)

And, at this point, I believe we can be happy with our solution. Note that we no longer have to find the distance between the centers of mass, and have thus saved outself a square root operation.

A Confession

I have made up this derivation of the final solution. In fact, I was not around when the original solution was divised; I only discovered this algorithm while attempting to understand what happened in a module I was supposed to be porting to a more modern version of our libraries. However, none of the fundamental points of the algorithm have changed: the polygonIntersections and centerOfMass functions were both used in the original solution and they were used to generate infinite lists of octagons such that the intersection points of the first two that intersected could be used to find a heading between the centers of mass.

I suppose there are any number of lessons you could draw from this code. I've always seen it as an example of two things: first, that sometimes it's not worth looking for a more interesting solution, but that second, if you must find a more interesting solution, at least it will be amusing to future generations.