Bresenham's Line Algorithm
From RogueBasin
(Difference between revisions)
(use syntax highlighting for the code example) |
|||
Line 1: | Line 1: | ||
− | + | == C++ == | |
− | + | Here's a C++ version; plot() draws a "dot" at (x, y): | |
+ | |||
+ | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | ||
+ | <syntaxhighlight lang="cpp"> | ||
+ | #include <cmath> | ||
− | + | //////////////////////////////////////////////////////////////////////////////// | |
− | + | void Bresenham(int x1, | |
− | + | int y1, | |
− | + | int x2, | |
− | + | int y2) | |
− | + | { | |
− | + | int delta_x = std::abs(x2 - x1) << 1; | |
− | + | int delta_y = std::abs(y2 - y1) << 1; | |
+ | |||
+ | // if x1 == x2 or y1 == y2, then it does not matter what we set here | ||
+ | signed char ix = x2 > x1?1:-1; | ||
+ | signed char iy = y2 > y1?1:-1; | ||
+ | |||
+ | plot(x1, y1); | ||
+ | |||
+ | if (delta_x >= delta_y) | ||
+ | { | ||
+ | // error may go below zero | ||
+ | int error = delta_y - (delta_x >> 1); | ||
− | + | while (x1 != x2) | |
− | + | { | |
− | + | if (error >= 0) | |
+ | { | ||
+ | if (error || (ix > 0)) | ||
+ | { | ||
+ | y1 += iy; | ||
+ | error -= delta_x; | ||
+ | } | ||
+ | // else do nothing | ||
+ | } | ||
+ | // else do nothing | ||
+ | |||
+ | x1 += ix; | ||
+ | error += delta_y; | ||
+ | |||
+ | plot(x1, y1); | ||
+ | } | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | // error may go below zero | ||
+ | int error = delta_x - (delta_y >> 1); | ||
+ | |||
+ | while (y1 != y2) | ||
+ | { | ||
+ | if (error >= 0) | ||
+ | { | ||
+ | if (error || (iy > 0)) | ||
+ | { | ||
+ | x1 += ix; | ||
+ | error -= delta_y; | ||
+ | } | ||
+ | // else do nothing | ||
+ | } | ||
+ | // else do nothing | ||
+ | |||
+ | y1 += iy; | ||
+ | error += delta_x; | ||
− | + | plot(x1, y1); | |
− | + | } | |
− | + | } | |
− | + | } | |
− | + | </syntaxhighlight> | |
− | + | </div> | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | |||
+ | == Ruby == | ||
− | + | And here 's a Ruby version, it returns an array of points, each being an hash with 2 elements (x and y). | |
− | + | ||
− | + | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | |
+ | <syntaxhighlight lang="ruby"> | ||
+ | |||
+ | def get_line(x0,x1,y0,y1) | ||
+ | points = [] | ||
+ | steep = ((y1-y0).abs) > ((x1-x0).abs) | ||
+ | if steep | ||
+ | x0,y0 = y0,x0 | ||
+ | x1,y1 = y1,x1 | ||
+ | end | ||
+ | if x0 > x1 | ||
+ | x0,x1 = x1,x0 | ||
+ | y0,y1 = y1,y0 | ||
+ | end | ||
+ | deltax = x1-x0 | ||
+ | deltay = (y1-y0).abs | ||
+ | error = (deltax / 2).to_i | ||
+ | y = y0 | ||
+ | ystep = nil | ||
+ | if y0 < y1 | ||
+ | ystep = 1 | ||
+ | else | ||
+ | ystep = -1 | ||
+ | end | ||
+ | for x in x0..x1 | ||
if steep | if steep | ||
− | + | points << {:x => y, :y => x} | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
else | else | ||
− | + | points << {:x => x, :y => y} | |
end | end | ||
− | + | error -= deltay | |
− | + | if error < 0 | |
− | + | y += ystep | |
− | + | error += deltax | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
end | end | ||
− | |||
end | end | ||
+ | return points | ||
+ | end | ||
+ | |||
+ | </syntaxhighlight> | ||
+ | </div> | ||
[[Category:Articles]] | [[Category:Articles]] |
Revision as of 13:09, 5 April 2010
C++
Here's a C++ version; plot() draws a "dot" at (x, y):
#include <cmath> //////////////////////////////////////////////////////////////////////////////// void Bresenham(int x1, int y1, int x2, int y2) { int delta_x = std::abs(x2 - x1) << 1; int delta_y = std::abs(y2 - y1) << 1; // if x1 == x2 or y1 == y2, then it does not matter what we set here signed char ix = x2 > x1?1:-1; signed char iy = y2 > y1?1:-1; plot(x1, y1); if (delta_x >= delta_y) { // error may go below zero int error = delta_y - (delta_x >> 1); while (x1 != x2) { if (error >= 0) { if (error || (ix > 0)) { y1 += iy; error -= delta_x; } // else do nothing } // else do nothing x1 += ix; error += delta_y; plot(x1, y1); } } else { // error may go below zero int error = delta_x - (delta_y >> 1); while (y1 != y2) { if (error >= 0) { if (error || (iy > 0)) { x1 += ix; error -= delta_y; } // else do nothing } // else do nothing y1 += iy; error += delta_x; plot(x1, y1); } } }
Ruby
And here 's a Ruby version, it returns an array of points, each being an hash with 2 elements (x and y).
def get_line(x0,x1,y0,y1) points = [] steep = ((y1-y0).abs) > ((x1-x0).abs) if steep x0,y0 = y0,x0 x1,y1 = y1,x1 end if x0 > x1 x0,x1 = x1,x0 y0,y1 = y1,y0 end deltax = x1-x0 deltay = (y1-y0).abs error = (deltax / 2).to_i y = y0 ystep = nil if y0 < y1 ystep = 1 else ystep = -1 end for x in x0..x1 if steep points << {:x => y, :y => x} else points << {:x => x, :y => y} end error -= deltay if error < 0 y += ystep error += deltax end end return points end