Map Borders (Part 4)

At the end of my previous posting, I had implemented the primitives for drawing lines and geometric shapes.  I had started working on using repeating shapes to fill borders, and pointed out the difficulties of making an arbitrary pattern fit into a map border so that it meets up perfectly in the corners.  The basic problem is that in general you have to make the pattern longer (or shorter) to fit in the side.  The choices for changing the pattern length -- adding or removing space, changing the length of the pattern elements -- all change the pattern itself in some way.  Knowing which choice to pick and how to apply it not to ruin a pattern of multiple elements seems very challenging!

Whenever I run into a seemingly intractable problem like this, I like to start by implementing some simple version.  Intractable problems can often be solved by repeatedly shaving away a “simple" problem until the result is good enough.  And sometimes implementing the simple version creates some insight that makes the harder problem easier.  If worse comes to worse and the problem remains intractable, at least I've got a simplified version that might still be useful, if not quite as good as I'd like.

The simplest way to change the pattern length is to add length without changing anything else about the pattern.  This essentially adds empty space at the end of the pattern.  (Note:  It's better to spread the empty space out between each element in the pattern.)  Note that this approach only works to make a pattern longer.  You can always add space to a pattern, but you can't necessarily take it away -- there might not be any empty space in the pattern!

With this approach, the algorithm for laying out a pattern on a map side is straightforward:

• Divide the length of map side by the length of the pattern and take the floor to determine the number of repeats of the pattern that will fit on this side.
• The spacing of elements on this side is then the length of the side divided by the number of repeats.  (This is the closest possible spacing to the original spacing given that we can only add space.)
• Draw the pattern along the side using the calculated spacing.

I had a hard time getting this to work.  My corners were stubbornly unmatched.  It took me an embarrassingly long time to realize that when the map isn't square, I cannot draw the clipping regions for the four sides to the center of the map.  That creates clipping angles that aren't 45 degrees.  Instead, I have to draw the clipping regions like the back of an envelope:

Once I had that in place the algorithm worked nicely.

(But recall the previous note that I eventually abandoned clipping areas!)

Here's an example of a nearly 2:1 ratio:

It's a little hard to see at this scale, but the corners meet up nicely, and there's little visual difference between the sides.  In this case, the algorithm only needs to insert fractional pixels to adjust the patterns, so it's not really visible to the eye, particularly since the circle outlines overlap by a pixel.

Here's another example, with bars:

That's the top of a square border.  Here's the same border on a more rectangular map:

Here you can see that there's visibly more gap between the bars on the side of the map.  At most this algorithm has to include space for just less than one full element; so the worst case occurs where there are long elements and a short side that is just off the right size.  But in most practical cases the adjustment is not severe.

Here's an example with multiple elements in the pattern:

Here's bars overlaid on bars:

You can see that because the same adjustment is made to each element, the bars stay centered with respect to each other.

I had assumed that a good solution for pattern fitting was going to have to be complex, but the very simple approach of spreading out the pattern elements equally to fill the required space works well for many patterns.  It's a reminder not to assume that a solution to a problem will be complex; the solution may turn out simpler than you think!

However, this solution doesn't work well for patterns with touching elements, like a map scale.  Then the added space moves the elements apart:

Another option I mentioned last time to make a pattern longer was to stretch out all the individual elements in the pattern.  This would work well for something like a scale pattern but not as well for a pattern with symmetrical elements, because the stretching will make them asymmetrical.

Implementing this stretching option turns out to be more difficult than I expected, largely because I have to stretch elements different amounts on different map edges (since the map could be rectangular rather than square), and I have to also dynamically adjust the placement of elements based upon their new stretched sizes.  But after a few hours to work all that out:

I now have all the capability I need to draw a border on a map (although the border elements themselves are hand-crafted):

I put this in grey-scale because I didn't want to obsess about picking colors, and the map itself is pretty uninteresting, but as a proof of concept I think the borders looks pretty good.