图像原地旋转 -90°算法

gxqcn

1. /* 对应帖号：http://bbs.emath.ac.cn/viewthread.php?tid=1437&page=2&fromuid=8#pid18832 */
2. /* 算法功能：矩阵原地逆时针旋转90度（矩阵原地转置、顺时针旋转90度等均可参考） */
3. /* 算法优化：郭先强 */
4. /* 修订日期：2009-05-02 */
6. #include <stdio.h>
7. #include <stdlib.h>
9. void output( int *a, int w, int h )
10. {
11. int i, j;
12. for ( i=0; i<h; ++i )
13. {
14. for( j=0; j<w; ++j )
15. {
16. printf( "%d ", a[i*w+j] );
17. }
18. printf( "\n" );
19. }
20. printf( "\n" );
21. }
23. void transf( int *a, int w, int h )
24. {
25. int k, pos, t, c=w*h;
26. div_t xy;
28. #define TRANSF(pos,w,h) xy = div( pos, w ); pos = (w-1-xy.rem)*h + xy.quot;
30. for( k=0; ; ++k )
31. {
32. pos = k;
33. do
34. {
35. TRANSF( pos, w, h );
36. } while( pos > k );
38. if( pos == k )
39. {
40. t = a[k];
41. do
42. {
43. TRANSF( pos, w, h );
45. a[pos] ^= t ^= a[pos] ^= t;
46. --c;
47. } while( pos != k );
49. if ( c <= 1 )
50. break;
51. }
52. }
54. #undef TRANSF
55. }
57. int main()
58. {
59. int w=12, h=16, i, j;
60. int *a = malloc( w*h*sizeof(int) );
62. for( i=0; i<h; ++i )
63. {
64. for( j=0; j<w; ++j )
65. {
66. a[i*w+j]=i*w+j+1;
67. }
68. }
70. output( a, w, h );
71. transf( a, w, h );//旋转
72. output( a, h, w );
74. free( a );
76. return 0;
77. }

复制代码

此算法相对于 6#，最大的改进是可以提前结束循环。 如果用一个数组标记矩阵各元素是否被置换，则可以更快地判断某些位置上的元素是否已置换，但需多耗元素总数1/8字节的空间； 当然，如果空间充裕，可以另开一个等大的空间，则不存在读写有overlap的问题，算法设计更容易，效率也更高。

无心人

一圈圈转吧

gxqcn

不是简单意义上的转圈圈， 它要考虑二维变换的几何意义， 又要考虑数据存储的一维特征， 一般人很容易绕晕的。

无心人

设计好了就行