Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Line-drawing algorithm prints nonsensical intermediate Y values. Where is the problem?
This question was originally asked in SE.
I have a program that draws lines using line drawing algorithms. I use gcc 5.2.1 on Xubuntu 15.10 to compile it.
Executing it throws a "Segment violation" fault. Further investigation let me isolate the problem in this MCVE:
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int uint;
typedef unsigned char byte;
typedef struct {
uint x;
uint y;
} point;
typedef struct {
point start;
point end;
} line;
line new_line(point start, point end) {
line l;
l.start = start; l.end = end;
return l;
}
point new_point(uint x, uint y) {
point p;
p.x = x; p.y = y;
return p;
}
byte points_equal(point p1, point p2) {
int equal = (p1.x == p2.x && p1.y == p2.y) ? 1 : 0;
return equal;
}
double line_slope(line l) {
return (double) (l.end.y - l.start.y) / (l.end.x - l.start.x);
}
/* Naive line drawing algorithm: assumes line in 1st octant */
point * naive(line l) {
uint numelems = abs( l.end.x - l.start.x );
double m = line_slope(l);
point * tbl = calloc(numelems + 1, sizeof *tbl);
if (tbl == NULL) return NULL;
int x, nt;
double b = (double) l.start.y - ((double) l.start.x * m);
tbl[0] = l.start;
tbl[numelems] = l.end;
for (x = l.start.x + 1, nt = 1; nt < numelems; x++, nt++) {
tbl[nt].x = x;
tbl[nt].y = (int) ( m*x + b );
}
return tbl;
}
/* Main program */
int main() {
line l = new_line( new_point( -345, -236 ), new_point( -25, -3 ) );
point *tbl = naive( l );
if (tbl != NULL) {
uint n = 0;
do {
printf("(%d,%d)\n", tbl[n].x, tbl[n].y);
} while ( !points_equal( tbl[n++], l.end ) );
free(tbl);
}
return 0;
}
The output of this program is
(-345,-236)
(-344,1167693998)
(-343,1167693999)
(-342,1167693999)
(-341,1167694000)
(-340,1167694001)
/* output continues */
(-30,1167694226)
(-29,1167694227)
(-28,1167694228)
(-27,1167694229)
(-26,1167694229)
(-25,-3)
As you can see, the Y coordinates are all wrong (huge positive numbers), instead of smoothly going up from -236 to -3, as it should when drawing lines.
Here comes my question: What does this mean? Would the structure be interfering with the cast? Can something like that actually happen? Is there any other problem I'm not seeing here?
1 answer
I answered myself as it can be found here.
Silly me! The root of the entire problem was the type used in both point.x and point.y:
typedef unsigned int uint;
typedef struct {
uint x;
uint y;
} point;
As both are unsigned integers, they "wrap up" once they receive a negative value, just like in the MCVE. This gets corrected by just changing uint to int:
typedef struct {
int x;
int y;
} point;
So keep this in mind when using signed and unsigned numbers!
0 comment threads
0 comment threads