shulman@topaz.RUTGERS.EDU (Jeff Shulman) (11/20/85)
I am looking for an alogithm that would allow me to rotate N x N bitmaps in
90 degree increments. I am already familiar with the shearing algorithm (too
slow) and the quarter masking algorithm (N is not always a power of 2.)
Ideally this algorithm should have at least the same speed as the
masking algorithm and be capable of rotating the bitmap in place (or
require minimal additional memory since there is no room for a duplicate size
bitmap.)
Thanks.
Jeff
uucp: ...{harvard, seismo, ut-sally, sri-iu, ihnp4!packard}!topaz!shulman
arpa: SHULMAN@RUTGERS
CIS: 76136,667
Delphi: JEFFSksbooth@watcgl.UUCP (Kelly Booth) (11/23/85)
The classic algorithm is due to Bob Floyd. It computes the transpose of a matrix in something like n log n time (where n is the number of entries in the matrix). This will handle the case of 90 degrees. The other angles can be derived. The basic unit of operation is "shuffling" the entries in two "blocks" of the matrix (a page, a word, whatever) to produce two new blocks consisting of exactly the entries from the original two, but permuted. I don't have a direct reference at hand, but will look for one. The algorithm is from the 60's?
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (11/25/85)
> The classic algorithm is due to Bob Floyd. It computes the transpose of > a matrix in something like n log n time (where n is the number of entries > in the matrix). This will handle the case of 90 degrees. I would appreciate an explanation of how in-place transposition of a matrix can be used to rotate a bitmap in-place by 90 degrees.
shulman@topaz.RUTGERS.EDU (Jeff Shulman) (11/27/85)
Since noone came up with any more algorithms than I already knew I will
mention those. They can be found in "ACM Transactions on Graphics" Vol 1
No. 3, July 1982 Pages 191-214.
The first algorithm, shearing, can work on any N x N matrix and you need
an extra 2N x 2N temporary bitmap for storage. The gist of this algorithm
is that individual rows and columns are rotated around themselves in
stepwise amounts. In the first rotation you rotate the I'th row around
itself by I bits. You then rotate the J'th column by N - J - 1 bits down.
You finally rotate back the I'th row by N - I - 1 bits left.
The second algorithm, binary mask (developed by Floyd), works on an N x N
matrix where N is a power of two. This algorithm works by swapping
halves and then opposite corners of the bitmap recursively halving the
size of the pieces being swapped. By cleverly using a mask it is possible
to accomplish all the recursive swapping in parallel. A better explanation
of this algorithm can be found in "Smalltalk-80, the language and an
implementation" (I believe that's the correct title) on pages 408-410.
Jeff
uucp: ...{harvard, seismo, ut-sally, sri-iu, ihnp4!packard}!topaz!shulman
arpa: SHULMAN@RUTGERS
CIS: 76136,667
Delphi: JEFFS