1 /* bresenham.c - compute line from x1,y1 to x2,y2 using Bresham's algorithm
2
3 Copyright 2001 Carl Worth
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
8 any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14 */
15
16 #include "bresenham.h"
17
18 #ifdef DMALLOC
19 #include "dmalloc.h"
20 #endif
21
bresenham(bresenham_cb_t cb,void * data,int x1,int y1,int x2,int y2)22 void bresenham(bresenham_cb_t cb, void *data, int x1, int y1, int x2, int y2)
23 {
24 (cb)(data, x1, y1);
25 bresenham_skip_first_last(cb, data, x1, y1, x2, y2);
26 if (x2 != x1 || y2 != y1)
27 (cb)(data, x2, y2);
28 }
29
bresenham_skip_first(bresenham_cb_t cb,void * data,int x1,int y1,int x2,int y2)30 void bresenham_skip_first(bresenham_cb_t cb, void *data,
31 int x1, int y1, int x2, int y2)
32 {
33 bresenham_skip_first_last(cb, data, x1, y1, x2, y2);
34 if (x2 != x1 || y2 != y1)
35 (cb)(data, x2, y2);
36 }
37
bresenham_skip_last(bresenham_cb_t cb,void * data,int x1,int y1,int x2,int y2)38 void bresenham_skip_last(bresenham_cb_t cb, void *data,
39 int x1, int y1, int x2, int y2)
40 {
41 (cb)(data, x1, y1);
42 bresenham_skip_first_last(cb, data, x1, y1, x2, y2);
43 }
44
bresenham_skip_first_last(bresenham_cb_t cb,void * data,int x1,int y1,int x2,int y2)45 void bresenham_skip_first_last(bresenham_cb_t cb, void *data,
46 int x1, int y1, int x2, int y2)
47 {
48 int dy = y2 - y1;
49 int dx = x2 - x1;
50 int stepx, stepy;
51
52 if (dy < 0) {
53 dy = -dy;
54 stepy = -1;
55 } else {
56 stepy = 1;
57 }
58 if (dx < 0) {
59 dx = -dx;
60 stepx = -1;
61 } else {
62 stepx = 1;
63 }
64
65 if (dx == 0 && dy == 0)
66 return;
67
68 dy <<= 1;
69 dx <<= 1;
70 if (dx > dy) {
71 int fraction = dy - (dx >> 1);
72 while (1) {
73 if (fraction >= 0) {
74 y1 += stepy;
75 fraction -= dx;
76 }
77 x1 += stepx;
78 fraction += dy;
79 if (x1 == x2)
80 break;
81 (cb)(data, x1, y1);
82 }
83 } else {
84 int fraction = dx - (dy >> 1);
85 while (1) {
86 if (fraction >= 0) {
87 x1 += stepx;
88 fraction -= dy;
89 }
90 y1 += stepy;
91 fraction += dx;
92 if (y1 == y2)
93 break;
94 (cb)(data, x1, y1);
95 }
96 }
97 }
98