Celtic Knotwork Algorithms

Rev. 10-Apr-2005

This article explains the basics of rectangular knotwork, and some of the principles used in my "Knotware" generation programs.

If you've read through my simple explanation, you may be ready for some of the inner secrets of how this program is possible. And, you may have already noticed the peculiar way that the graphics are drawn on the other two pages -- they pop up in little squares, instead of as complete images. I've determined that there are 26 different tiles that I need to draw any of these knotwork patterns (28, if you count the two blank ones that are available); they've been assigned letters in a purely arbitrary order. This way, my program just has to manipulate the letter codes, and the actual "drawing" is done by the HTML it generates.

Suppose that we are generating a (w) x (h) knotwork pattern. We'll create (2w x 2h) of these little cells, which start out with the pattern ... and ... If the user wants the cross-overs to go the other way, we'd generate them in reverse order: I,U,I,U... and W,L,W,L... or, alternatively, we'll transpose the result just before output. All cells start out as one of these:

Each cell has 4 sides; generally no more than 2 sides will have breaklines or borders. In order to support blanking out sections of the grid (if you want to make a cross shape, for example), we can throw in support for the "degenerate case" of a cell with breaklines on all 4 sides, to indicate where the blanked-out parts are. Or, alternatively, we could have some other method of indicating blanked squares, and make our algorithm detect for an adjacent "edge, breakline, or blank cell" on all 4 sides.

A cell with 2 parallel breaklines on the left and right will always turn into
A cell with 2 parallel breaklines on the top and bottom will always turn into

A cell with 2 perpendicular breaklines forming a corner will always form one of depending on which two sides the corner is.

A cell with a breakline on one side will change depending on which side it's on, and which type of cell it already is.
For a breakline on the left side: changes to
For a breakline on the right: changes to
For a breakline on the top: changes to
And for a breakline on the bottom: changes to

The transformations could be handled by a lookup table with 64 entries. (4 different inputs, L,W,U,I, and a theoretical maximum of 16 different breakline permutations; the five entries for 3-side and 4-side breaklines could be left out, or yield "blank." 4 x 16 = 64.)

Alternatively, the transformations could be handled by four different substitutions (tr///), one for each breakline present, by combining the rules listed.
So for two parallel breaklines, the transformation would go something like:
First breakline on the left side: changes to then with the right-side breakline changes to
First breakline on the right: changes to then with the left-side breakline changes to
First breakline on the top: changes to then then with the bottom-side breakline changes to
First breakline on the bottom edge: changes to then then with the top-side breakline changes to
And for two perpendicular breaklines, the transformations would go something like this:
First breakline on the left side: changes to then with a top-side breakline changes to
First breakline on the left side: changes to then with a bottom-side breakline changes to
First breakline on the right: changes to then with a top-side breakline changes to
First breakline on the right: changes to then with a bottom-side breakline changes to
First breakline on the top: changes to then with a left-side breakline changes to
First breakline on the top: changes to then with a right-side breakline changes to
First breakline on the bottom edge: changes to then with a left-side breakline changes to
First breakline on the bottom edge: changes to then with a right-side breakline changes to
Finally, to handle degenerate cases:
plus a breakline on the left changes to:
plus a breakline on the right changes to:
plus a breakline on the top changes to:
plus a breakline on the bottom changes to:

Combined rules:
For a breakline on the left side:
changes to

For a breakline on the right:
changes to

For a breakline on the top
changes to

And for a breakline on the bottom:
changes to

To reverse the polarity (handedness, parity, call it what you will):
changes to

Where are the breaklines? Each breakline affects 4 cells - the same 4 cells around the center point of the breakline, regardless of whether the breakline is horizontal or vertical. Recall that the dimensions of the pattern are 2w x 2h; assign the top left corner as (0,0) and the top right corrner as (2w,0). The breakline centerpoints occur at points with (odd,even) or (even,odd) cartesian coordinates - never at the (odd,odd) or (even,even) coordinates. Note that the first piece of the border can be considered a horizontal breakline centered on coordinate (1,0) -- i.e. it goes from (0,0) to (2,0). A breakline internal to the pattern, at for example (4,1), could either run vertically from (4,0) to (4,2) as in our Figure 9; or horizontally from (3,1) to (5,1) as in Figure 11.

So how many potential internal breaklines are there? (not counting the degenerate case of marking in extra breakline pieces to indicate blank cells) There are w*(h-1) "odd,even" breakpoint coordinates, and (w-1)*h "even, odd" breakpoint coordinates, each of which could be horizontal, vertical, or not present. Total: 2wh-w-h. The breakline permutations add up to 3**(2wh-w-h).

For Perl implementation: the tr/// operator is well suited for this. You don't even need to sort the translation tables. For a C implemention, it would probably make sense to use an index, of 1-26 for A-Z (0 for blank) into four 27-byte tables. A representation of where the breaklines are should probably be decided on, also where the blank squares are. One approach would be to create three or four 2w x 2h arrays - one for the cells themselves, one or two for where the breaklines are, and one for where the blank squares. (Or fold the blank square data into the "breakline" array.) For what it's worth, blank squares have to come in 2x2 pieces. (Although they don't have to be an even number of units in from the sides.)

My implementation of Version 3 will have a limit of 40x40 units. I have my reasons, which have to do with powers of 3.

The goal of the program I'm working on is to generate the letter codes, given a set of dimensions and the coordinates for the breaklines and blank squares. So the output is a 2w x 2h array. Can it be generated in one pass? That would be really elegant. We'd work our way from cell to cell, determine if there are breaklines on the 4 sides of the cell, and transform the cell's starting value (L,W,U,I) accordingly. But there's an efficiency problem with this approach /goal of -- since there are less than half as many potential breaklines as there are cells, it makes more sense to me to fill out the array at the outside with our starting values for the plaitwork, and then go from breakline to breakline transforming the cells around the breakline. In the former approach, we have to check the 4 sdies for each cell -- that's approximately 16 x w x h tests. In the latter approach, we check the (2w-w-h) breaklines, and only if the breakline is present do we transform the 4 cells around it. So we've improved the running time by at least 50% right there - more, really, because not all potential breaklines will be present.

Incidentally, the outside edges of the pattern are another matter; although they function like breaklines, it would be more trouble than it's worth to create a list of breaklines corresponding to the edges and then treat them in with the breakline processing. I'm thinking it makes more sense to just initialize the array with the appropriate values for the edge pieces at the beginning.

I have a program already written that takes the letter matrix and generates a little thumbnail-size knotwork graphic. I need to generalize it to use the different source pieces, though.

Combined rules, rewritten for table lookup.
For a breakline on the left side:
changes to

For a breakline on the right:
changes to

For a breakline on the top
changes to

And for a breakline on the bottom:
changes to

To reverse the polarity (handedness, parity, call it what you will):
changes to