Path: utzoo!attcan!uunet!lll-winken!csd4.csd.uwm.edu!mailrus!cwjcc!gatech!prism!vsserv!loligo!pepke From: pepke@loligo (Eric Pepke) Newsgroups: comp.sys.mac.programmer Subject: Re: Rotating Bit Images. Keywords: Bitmaps Message-ID: <113@vsserv.scri.fsu.edu> Date: 24 Aug 89 22:01:32 GMT References: <1495@unocss.UUCP> <3736@ncsuvx.ncsu.edu> <34285@apple.Apple.COM> Sender: news@vsserv.scri.fsu.edu Reply-To: pepke@loligo.UUCP (Eric Pepke) Organization: Supercomputer Computations Research Institute Lines: 33 In article <34285@apple.Apple.COM> kazim@Apple.COM (Alex Kazim) writes: >In article <3736@ncsuvx.ncsu.edu> jnh@ecemwl.UUCP (Joseph N. Hall) writes: >> >>There is an elegant algorithm for 90-degree rotations that is fast and >>efficient. The simplest version requires that your source pattern be both > >This was in a VERY early issue of MacTutor. Try the Best of Mac Tutor >volume 1. There is an algorithm for rotating bitmaps in November 1985 Mac Tutor, but although it is clever, it is not particularly efficient. The claim is made that the algorithm can rotate an image n pixels on a side in log n steps. This is true, but the problem is that each step requires enough CopyBits operations to move every pixel on the image. Assuming, as seems quite reasonable, that CopyBits on an image m pixels on a side takes O(n^2) time, the MacTutor algorithm takes O(n^2 log n) time. The obvious, brute-force approach to rotating bitmaps only takes O(n^2) time. Of course, CopyBits might have some good optimizations on small bitmaps, but then again, you can do your own optimizations on small squares, say 8 by 8 or 16 by 16. There is no reason that you should not be able to do a rotation just as fast as a single CopyBits of that image. The MacTutor algorithm perhaps has value as a curiosity, and it's fun to watch, but it is a waste of time, and it imposes needless restrictions on the shape and size of the data. Eric Pepke INTERNET: pepke@gw.scri.fsu.edu Supercomputer Computations Research Institute MFENET: pepke@fsu Florida State University SPAN: scri::pepke Tallahassee, FL 32306-4052 BITNET: pepke@fsu Disclaimer: My employers seldom even LISTEN to my opinions. Meta-disclaimer: Any society that needs disclaimers has too many lawyers.