Murray Polygon

Three murray polygons, each filling rectangles of size 3×3, 9×9, and 27×27, respectively.

The murray polygon is a type of space-filling curve developed by Professor Alfred Jack Cole. He generalized the existing Peano polygon, extending it to fill any rectangular space of arbitrary integer length and width. Where the Peano polygon algorithm uses the base 3 number system—a fixed radix arithmetic, Cole's algorithm uses a number system which allows each digit to use a different radix.^[1]:235 The name multiple radix arithmetic later became shortened to murray.^[2]

Definitions

Murray integer

Cole defined a murray integer formally as follows:

Suppose that

r_n, r_n−1, ..., r₂, r₁

are n non-negative decimal integers, which may or may not be single digits. Let

d_n, d_n−1, ..., d₂, d₁

be digits such that 0 ≤ d_i < r_i for i = 1, 2, ..., n. That is, each digit d_i is a base r_i digit. Then

d_n d_n−1 ... d₂ d₁

is defined to be a mixed radix or murray integer.^[1]:235

Reduced radix complement

The following is Cole's definition of a reduced radix complement.

Suppose

d = d_n d_n−1 ... d₂ d₁

is a murray integer. Then the murray integer

e = e_n e_n−1 ... e₂ e₁,

where e_i = r_i−1−d_i for i = 1, 2, ..., n is the reduced radix complement of d.^[1]:236

Gray coding

The Gray coding algorithm used for murray integers is modified from that of fixed-based systems. In Cole's version, he replaces d_i with r_i−1−d_i rather than r−1−d_i; using the variable radix in place of the fixed radix.^[1]:236

Murray algorithm

The following is Cole's outline of the full algorithm to produce a murray polygon for a given rectangle.

The algorithm to transform a decimal integer d (0 ≤ d ≤ mn−1) to the corresponding point (x, y) on a murray polygon within a rectangle with sides of length m−1, n−1 (Cole 1986, 1988) is now as follows...

1) Convert d to murray integer form

p = p_n p_n−1 ... p₂ p₁,

where n = 2j and the radix r_i (1 ≤ i ≤ 2j) associated with p_i is m_k if i = 2k−1 and n_k if i = 2k.

2) Convert p to the equivalent murray Gray-coded integer

e = e_n e_n−1 ... e₂ e₁.

3) Split e into two parts

f = e_n−1 e_n−3 ... e₃ e₁

and

g = e_n e_n−2 ... e₄ e₂.

4) De-Gray code f and g to give

x = x_j x_j−1 ... x₂ x₁

and

y = y_j y_j−1 ... y₂ y₁.

5) The corresponding vertex in murray notation is now (x, y), which may be converted back to normal notation if required.^{[1]:236–237}

Repeating this process for every integer p from 0 to mn−1 sequentially plots all points through which a murray polygon passes for a given rectangle.^[1]:237

References

1. Cole, A. J. (September 1991). "Halftoning without dither or edge enhancement". The Visual Computer. 7 (5): 235–238. doi:10.1007/BF01905689.
2. "Murray Polygon". Retrieved 31 August 2015.