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?

@TimBiegeleisen you mean what's the center point of the rotation? — Max, Nov 01 '16 at 04:01
I would say that the rotation point should be the beginning of the line, at `0,0` in this case. Theoretically the line could also start at `1,1` then I would expect the line to be rotated around this point. Btw only someone in Asia can be awake at this time of the day, haha. — Max, Nov 01 '16 at 04:03
Yes, I live in Singapore. It is my lunch hour now, maybe I can help you. — Tim Biegeleisen, Nov 01 '16 at 04:05
@TimBiegeleisen would be great if you can give me any pointer. I'm from Singapore, too (still waiting for my lunch break though, hehe) — Max, Nov 01 '16 at 04:07
Here's the problem: When you rotate that line clockwise by 45 degrees, it doesn't sit where you placed it, because it is longer than 2. Check here for the matrix to rotate a point about the origin: http://math.stackexchange.com/questions/346672/2d-rotation-of-point-about-origin — Tim Biegeleisen, Nov 01 '16 at 04:10
You're going to need to think about your design and what behavior you really want here. Based on what you drew, it is not a simple rotation. — Tim Biegeleisen, Nov 01 '16 at 04:10
@TimBiegeleisen thanks, I will have a look at the link and also at the presentation mentioned in that question. I need to revisit what is the intended behaviour. — Max, Nov 01 '16 at 04:34
also if you are rotating the rendered stuff (not vertexes) then you need to convert all of the characters too (and need to use only rotatable ones like `- / | \ `) . btw if you use only `90deg` rotations instead then you do not need matrices ... instead you can use `(x,y) -> (y,-x)` or `(x,y) -> (-y,x)` for more info about matrices see: [Understanding 4x4 homogenous transform matrices](http://stackoverflow.com/a/28084380/2521214) there is a lot more rotatable characters with 90 deg rotations only then for 45deg rotations — Spektre, Nov 01 '16 at 06:15
Also take a look at this [Image to ASCII art conversion](http://stackoverflow.com/a/32987834/2521214) it is not directly related to your task but may get you new ideas (and features) for your project — Spektre, Nov 01 '16 at 06:19
@Max Added [edit1] to my answer with proper 45 deg rotation. Did not occur to me to use square rotation kernel at first ... no floating operations needed anymore ... :) — Spektre, Nov 02 '16 at 22:27

score 2 · Accepted Answer · edited Jun 20 '20 at 09:12

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:

Thank you! This is a very nice summary, I will go with 90 degree rotation, that seems to be much easier for my little pet project. The example you write with converting images to ASCII art is genuis, I want to have my try for that, too! — Max, Nov 01 '16 at 07:44
@Max glad to be of help ... if you want to make the rot90ccw then just negate the other coordinate instead... — Spektre, Nov 01 '16 at 07:45
Haha that is super cool! Thank you. :) Will have a look at it and try to adapt the code for what I need. You seem to really enjoy playing with ASCII graphics! — Max, Nov 03 '16 at 02:33
@Max I code anything to clear my mind before the hard stuff I code for my work and SO is great stack of interesting problems. But my favorite is 3D gfx + simulating the real stuff not ASCII Art for example take a look at these: [Is it possible to make realistic n-body solar system simulation in matter of size and mass?](http://stackoverflow.com/a/28020934/2521214) , [RGB values of visible spectrum](http://stackoverflow.com/a/22681410/2521214) , [Multi-Band Image raster to RGB](http://stackoverflow.com/a/29575362/2521214) — Spektre, Nov 03 '16 at 08:32

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

1 Answers1

Linked