How can I draw a "string" in a two-dimensional array (simulacrum for the screen)

Question

I am working on a project that will print before the bitmap (more specifically RAW, but this is not important for the question), but I work in a two-dimensional in-program array.

I want to be able to draw a line from point (a, b) to point (x, y) for any arbitrary values ​​of a, b, x and y. I don't need anything like smoothing; at this moment the closest neighbor is good. for example, suppose I have a 5x5 2d array, for example:

00,10,20,30,40 01,11,21,31,41 02,12,22,32,42 03,13,23,33,43 04,14,24,34,44 

Now, let's say I want to draw a line between 04 and 42. I want the method to come up with something like this reliably:

 0,0,0,0,0 0,0,0,0,0 0,0,0,1,1 0,1,1,1,0 1,1,0,0,0 

I'm sure someone thinks "guh, is this guy retarded?" He could not here? "but please humorous please!

I work in C ++, but this should be secondary to the actual issue.

Answer 1

the Bresenham line algorithm is what you need:

Illustration of the result of the Breschenem line algorithm.

Answer 2

As Simukal said, Breschenham is the way. Here is a naive implementation.

Not a perfect C code, and you need to do some magic if you need thickness on linear segments. In addition, you should cross along x instead of y, as I am here. It is more convenient for caching. If you want smoothing, find "Wu-lines". This is a smart trick to use a fraction of the positions as a gradient.

Tips on line thickness: Calculate the normalized vector V (-y, x) from v1 - v0 if your vertices are in counterclockwise order, or V (y, -x) if your vertices are clockwise. Then you have four points defined: v0, v0 + V * line width, v1 and v1 + V * line width. Rasterize this quadrangle by interpolating around the edges. But if you already want to go this far, you are likely to code the triangle rasterizer.

 typedef struct Point { int x, y; } Point; typedef struct Color { unsigned char r,g,b; } Color; #define RGB(x) (x->r << 16) | (x->g << 8) | (x->b) int DrawLinestrip(int width, int height, unsigned int* buffer, Color* color, Point* verts, int count) { int i, x,y,xbegin, xdelta, ydelta, xdiff, ydiff, accum, sign; Point *p1, *p2; if(!verts || count < 2) return -1; for(i=1; i<count; ++i){ if(verts[i].y > verts[i-1].y){ /* sort by y */ p1 = &verts[i-1]; p2 = &verts[i]; } else { p1 = &verts[i]; p2 = &verts[i-1]; } xdelta = p2->x - p1->x; ydelta = p2->y - p1->y; accum = 0; sign = 0; if(!xdelta && !ydelta) continue; else if(!xdelta && ydelta){ /* Special case: straight vertical line */ x = p1->x; for(y=p1->y; y<(p1->y + ydelta); ++y){ buffer[x + y*width] = RGB(color); } } else if(xdelta && !ydelta){ /* Special case: straight horisontal line */ y = p1->y; xbegin = (p1->x < p2->x ? p1->x : p2->x); for(x=xbegin; x<=xbegin+abs(xdelta); ++x){ buffer[x + y*width] = RGB(color); } } else { xdiff = (xdelta << 16) / ydelta; ydiff = (ydelta << 16) / xdelta; if( abs(xdiff) > abs(ydiff) ){ /* horizontal-major */ y = p1->y; if(xdelta < 0){ /* traversing negative x */ for(x=p1->x; x >= p2->x; --x){ buffer[x + y*width] = RGB(color); accum += abs(ydiff); while(accum >= (1<<16)){ ++y; accum -= (1<<16); } } } else { /* traversing positive x */ for(x=p1->x; x <= p2->x; ++x){ buffer[x + y*width] = RGB(color); accum += abs(ydiff); while(accum >= (1<<16)){ ++y; accum -= (1<<16); } } } } else if( abs(ydiff) > abs(xdiff) ){ /* vertical major */ sign = (xdelta > 0 ? 1 : -1); x = p1->x; for(y=p1->y; y <= p2->y; ++y){ buffer[x + y*width] = RGB(color); accum += abs(xdiff); while(accum >= (1<<16)){ x += sign; accum -= (1<<16); } } } else if( abs(ydiff) == abs(xdiff) ){ /* 45 degrees */ sign = (xdelta > 0 ? 1 : -1); x = p1->x; for(y=p1->y; y <= p2->y; ++y){ buffer[x + y*width] = RGB(color); x+= sign; } } } } return 0; }