图像原地旋转 -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 */
   
5. 
   
6. #include <stdio.h>
   
7. #include <stdlib.h>
   
8. 
   
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. }
    
22. 
    
23. void transf( int *a, int w, int h )
    
24. {
    
25.     int k, pos, t, c=w*h;
    
26.     div_t xy;
    
27. 
    
28. #define TRANSF(pos,w,h)     xy = div( pos, w ); pos = (w-1-xy.rem)*h + xy.quot;
    
29. 
    
30.     for( k=0; ; ++k )
    
31.     {
    
32.         pos = k;
    
33.         do
    
34.         {
    
35.             TRANSF( pos, w, h );
    
36.         } while( pos > k );
    
37. 
    
38.         if( pos == k )
    
39.         {
    
40.             t = a[k];
    
41.             do
    
42.             {
    
43.                 TRANSF( pos, w, h );
    
44. 
    
45.                 a[pos] ^= t ^= a[pos] ^= t;
    
46.                 --c;
    
47.             } while( pos != k );
    
48. 
    
49.             if ( c <= 1 )
    
50.                 break;
    
51.         }
    
52.     }
    
53. 
    
54. #undef TRANSF
    
55. }
    
56. 
    
57. int main()
    
58. {
    
59.     int w=12, h=16, i, j;
    
60.     int *a = malloc( w*h*sizeof(int) );
    
61. 
    
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.     }
    
69. 
    
70.     output( a, w, h );
    
71.     transf( a, w, h );//旋转
    
72.     output( a, h, w );
    
73. 
    
74.     free( a );
    
75. 
    
76.     return 0;
    
77. }

复制代码

此算法相对于 6#，最大的改进是可以提前结束循环。

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

无心人

一圈圈转吧

gxqcn

不是简单意义上的转圈圈，

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

无心人

设计好了就行