algorithm - Rotate a diagonal line in a 2D 3 x 3 grid - rotation matrix needed?

Question

I'm building a library for drawing ASCII art. Given I have a 3 x 3 graph, where each point represents a pixel, a line starts at point 0,0 and goes diagonal to 2,2 (bottom left point to top right point).

If I draw the canvas, it looks like this:

2   /      Points: 2,0  2,1  2,2
1  /               1,0  1,1  2,1
0 /                0,0  1,0  2,0
  0 1 2

I now want to build an algorithm that can rotate the line clockwise to the right, so if I apply the algorithm to the line, the result should be:

2         Points: 2,0  2,1  2,2
1                 1,0  1,1  2,1
0 _ _ _           0,0  1,0  2,0
  0 1 2

So basically the line is rotated by 45 degrees to the right, resulting in an horizontal line.

I think I need a rotation matrix for this as described in http://mathworld.wolfram.com/RotationMatrix.html but the math is a bit above my head.

Anyone has a simple explanation on how this would work, given my 2D coordinate system, maybe in pseudo code?

Answer 1

It does not matter if you use the matrices or not. Here simple C++ example without matrices using all what I mention in my comments:

//---------------------------------------------------------------------------
const int xs=32;
const int ys=32;
char pic[xs][ys];
//---------------------------------------------------------------------------
void cls();
void rot45cw();
void rot90cw();
//---------------------------------------------------------------------------
void cls()
    {
    int x,y;
    // clear screen
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
      pic[x][y]=' ';
    // add diagonal line for testing
    for (x=xs/2;(x<xs)&&(x<ys);x++) pic[x][x]='\';
    }
//---------------------------------------------------------------------------
void rot45cw()
    {
    int x,y,ix,iy,x0,y0;
    float fx,fy,a,c,s;
    char tmp[xs][ys],q;
    a=-45.0*M_PI/180.0; // rotation angle [rad]
    x0=xs/2;            // center of rotation
    y0=ys/2;
    c=cos(a); s=sin(a);
    // copy pic to tmp
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
      tmp[x][y]=pic[x][y];
    // rotate
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
        {
        // offset so (0,0) is center of rotation
        fx=x-x0;
        fy=y-y0;
        // rotate (fx,fy) by ang
        ix=float((fx*c)-(fy*s));
        iy=float((fx*s)+(fy*c));
        // offset back
        ix+=x0;
        iy+=y0;
        // transform tmp to pic
        if ((ix>=0)&&(ix<xs)&&(iy>=0)&&(iy<ys)) q=tmp[ix][iy]; else q=' ';
             if (q=='/') q='\';
        else if (q=='\') q='/';
        else if (q=='-') q='|';
        else if (q=='|') q='-';
        pic[x][y]=q;
        }
    }
//---------------------------------------------------------------------------
void rot90cw()
    {
    int x,y,ix,iy,x0,y0;
    char tmp[xs][ys],q;
    // center of rotation
    x0=xs/2;
    y0=ys/2;
    // copy pic to tmp
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
      tmp[x][y]=pic[x][y];
    // rotate
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
        {
        // rotate
        iy=x0-(x-x0);
        ix=y0+(y-y0);
        // transform tmp to pic
        if ((ix>=0)&&(ix<xs)&&(iy>=0)&&(iy<ys)) q=tmp[ix][iy]; else q=' ';
             if (q=='-') q='\';
        else if (q=='\') q='|';
        else if (q=='|') q='/';
        else if (q=='/') q='-';
        pic[x][y]=q;
        }
    }
//---------------------------------------------------------------------------

and usage:

// clear and add diagonal line for testing once:
cls();
// and this do in some timer or whatever:
//rot45cw();
rot90cw();

Here 90deg preview:

Here 45deg preview:

As you can see 45deg rotation is a problem as it is not 1:1 mapping so some cells will map into more than one cell. For fixed resolution you can do some 1:1 mapping manually but I doubt it would be easily implemented algorithmically for dynamic resolution.

Yes You are using just (3x3) maps where the 45 deg rotation is possible but your problem persists because when you map individual pixels then some will be copied again and if you take into account you are viewing characters it would look bad.

If I put all together I would rather use 90deg rotations only unless you got vector representation of the image...

The character rotation can be speeded up with LUTs

[Edit1] 45 degree rotation

I give it a bit more taught and find out solution for the 45 degree rotations. You must use different rotation kernel. Not rotate around circles but arround squares by 1/8 of circumference. To better understand here small example:

// r=1
0 1 2    7 0 1
7   3 -> 6   2
6 5 4    5 4 3

// r=2
0 1 2 3 4    E F 0 1 2
F       5    D       3
E       6 -> C       4
D       7    B       5
C B A 9 8    A 9 8 7 6

This is 1:1 mapping so no problems with that. The code in C++ looks like this:

//---------------------------------------------------------------------------
void rot45cw()
    {
    int x0,y0,ax,ay,ad,bx,by,bd,a,b,i,r,rs;
    char tmp[xs][ys],q;
    // rotation kernel 4 directions
    const int dx[4]={ 0,-1, 0,+1};
    const int dy[4]={-1, 0,+1, 0};
    // center of rotation
    x0=xs/2;
    y0=ys/2;
    // copy pic to tmp
    for (ay=0;ay<ys;ay++)
     for (ax=0;ax<xs;ax++)
      tmp[ax][ay]=pic[ax][ay];
    // rotate all "screws" to fill entire map
    rs=xs; if (rs<ys) rs=ys;
    for (r=1;r<rs;r++)
        {
        ax=x0+r; ay=y0+r; ad=0; a=0; // start position a
        bx=x0  ; by=y0+r; bd=3; b=r; // start position b
        for (i=8*r;i>0;i--)          // process one screw
            {
            // fetch and convert processed character
            if ((ax>=0)&&(ax<xs)&&(ay>=0)&&(ay<ys))
             if ((bx>=0)&&(bx<xs)&&(by>=0)&&(by<ys))
                {
                q=tmp[ax][ay];
                     if (q=='-') q='\';
                else if (q=='\') q='|';
                else if (q=='|') q='/';
                else if (q=='/') q='-';
                pic[bx][by]=q;
                }
            // update position
            ax+=dx[ad]; bx+=dx[bd];
            ay+=dy[ad]; by+=dy[bd];
            // update direction
            a++; if (a>=r+r) { a=0; ad=(ad+1)&3; }
            b++; if (b>=r+r) { b=0; bd=(bd+1)&3; }
            }
        }
    // fetch and convert center of rotation
    if ((x0>=0)&&(x0<xs)&&(y0>=0)&&(y0<ys))
        {
        q=pic[x0][y0];
             if (q=='-') q='\';
        else if (q=='\') q='|';
        else if (q=='|') q='/';
        else if (q=='/') q='-';
        pic[x0][y0]=q;
        }
    }
//---------------------------------------------------------------------------
void rot45ccw()
    {
    int x0,y0,ax,ay,ad,bx,by,bd,a,b,i,r,rs;
    char tmp[xs][ys],q;
    // rotation kernel 4 directions
    const int dx[4]={ 0,-1, 0,+1};
    const int dy[4]={-1, 0,+1, 0};
    // center of rotation
    x0=xs/2;
    y0=ys/2;
    // copy pic to tmp
    for (ay=0;ay<ys;ay++)
     for (ax=0;ax<xs;ax++)
      tmp[ax][ay]=pic[ax][ay];
    // rotate all "screws" to fill entire map
    rs=xs; if (rs<ys) rs=ys;
    for (r=1;r<rs;r++)
        {
        ax=x0+r; ay=y0+r; ad=0; a=0; // start position a
        bx=x0  ; by=y0+r; bd=3; b=r; // start position b
        for (i=8*r;i>0;i--)          // process one screw
            {
            // fetch and convert processed character
            if ((ax>=0)&&(ax<xs)&&(ay>=0)&&(ay<ys))
             if ((bx>=0)&&(bx<xs)&&(by>=0)&&(by<ys))
                {
                q=tmp[bx][by];
                     if (q=='-') q='/';
                else if (q=='/') q='|';
                else if (q=='|') q='\';
                else if (q=='\') q='-';
                pic[ax][ay]=q;
                }
            // update position
            ax+=dx[ad]; bx+=dx[bd];
            ay+=dy[ad]; by+=dy[bd];
            // update direction
            a++; if (a>=r+r) { a=0; ad=(ad+1)&3; }
            b++; if (b>=r+r) { b=0; bd=(bd+1)&3; }
            }
        }
    // fetch and convert center of rotation
    if ((x0>=0)&&(x0<xs)&&(y0>=0)&&(y0<ys))
        {
        q=pic[x0][y0];
             if (q=='-') q='/';
        else if (q=='/') q='|';
        else if (q=='|') q='\';
        else if (q=='\') q='-';
        pic[x0][y0]=q;
        }
    }
//---------------------------------------------------------------------------

The dx,dy tables are simply analogy to sin and cos. Finally here is the preview:

but of coarse if you rotate square around its center it would not be as you expected !!! Here CCW example: