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

rn, rn−1, ..., r2, r1

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

dn, dn−1, ..., d2, d1

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

dn dn−1 ... d2 d1

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 = dn dn−1 ... d2 d1

is a murray integer. Then the murray integer

e = en en−1 ... e2 e1,

where ei = ri−1−di 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 di with ri−1−di rather than r−1−di; 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 ≤ dmn−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 = pn pn−1 ... p2 p1,

where n = 2j and the radix ri (1 ≤ i ≤ 2j) associated with pi is mk if i = 2k−1 and nk if i = 2k.

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

e = en en−1 ... e2 e1.

3) Split e into two parts

f = en−1 en−3 ... e3 e1

and

g = en en−2 ... e4 e2.

4) De-Gray code f and g to give

x = xj xj−1 ... x2 x1

and

y = yj yj−1 ... y2 y1.

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. 1 2 3 4 5 6 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.
This article is issued from Wikipedia - version of the Wednesday, September 02, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.