Jump to content

Murray polygon

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Tom.Reding (talk | contribs) at 20:16, 13 June 2016 (Fix Category:Pages using citations with accessdate and no URL when perm identifier present (doi|bibcode|arxiv|pmid|jstor|isbn|issn|lccn|oclc|ismn|hdl): rem access-date using AWB). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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. ^ a b c d e f 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.