Skip to content

Instantly share code, notes, and snippets.

@boxdot
Last active August 29, 2015 14:06
Show Gist options
  • Save boxdot/6cd4024af75bd57c6cf2 to your computer and use it in GitHub Desktop.
Save boxdot/6cd4024af75bd57c6cf2 to your computer and use it in GitHub Desktop.
Bresenham's line algorithm
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
shape-rendering: crispEdges;
}
.grid line {
stroke: #DEDEDE;
stroke-width: 1px;
}
#line {
stroke: red;
stroke-width: 3px;
}
rect {
fill: grey;
opacity: 0.5;
}
</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>
var width = 960
var height = 500
var n = 19
var m = 10
var grid_x = d3.range(0, width, width/n)
var grid_y = d3.range(0, height, height/m)
var x = d3.scale.quantize()
.domain([0, width])
.range(d3.range(0, n))
var x2 = d3.scale.quantize()
.domain(d3.range(0, n))
.range(grid_x)
var y = d3.scale.quantize()
.domain([0, height])
.range(d3.range(0, m))
var y2 = d3.scale.quantize()
.domain(d3.range(0, m))
.range(grid_y)
var svg = d3.select('body').append('svg')
.attr('width', width)
.attr('height', height)
var grid_el = svg.append('g')
.attr('class', 'grid')
grid_el.append('g')
.selectAll('line')
.data(d3.range(1, n).map(x2))
.enter()
.append('line')
.attr('x1', function(d) { return d })
.attr('x2', function(d) { return d })
.attr('y1', 0)
.attr('y2', height)
grid_el.append('g')
.selectAll('line')
.data(d3.range(1, m).map(y2))
.enter()
.append('line')
.attr('x1', 0)
.attr('x2', width)
.attr('y1', function(d) { return d })
.attr('y2', function(d) { return d })
var line_el = svg.append('line')
.attr('id', 'line')
var debug = d3.select('#debug')
var a, b, isMouseDown
svg.on('mousedown', function() {
isMouseDown = true
a = d3.mouse(this)
})
.on('mousemove', function() {
if (!isMouseDown) return
b = d3.mouse(this)
drawLine(
[x2(x(a[0])) + 25, y2(y(a[1])) + 25],
[x2(x(b[0])) + 25, y2(y(b[1])) + 25])
var res = bresenham(
[x(a[0]), y(a[1])],
[x(b[0]), y(b[1])])
drawRects(res.map(function(pt) {
return [x2(pt[0]), y2(pt[1])]
}))
})
.on('mouseup', function() {
isMouseDown = false
b = d3.mouse(this)
})
function drawLine(a, b) {
line_el
.attr('x1', a[0])
.attr('y1', a[1])
.attr('x2', b[0])
.attr('y2', b[1])
}
function drawRect(a, w, h) {
svg.append('rect')
.attr('x', a[0])
.attr('y', a[1])
.attr('width', w)
.attr('height', h)
}
function drawRects(data) {
var rect_w = width/n
var rect_h = height/m
var rect = svg.selectAll('rect')
.data(data)
rect.enter().append('rect')
.attr('width', rect_w)
.attr('height', rect_h)
rect.attr({
x: function(d) { return d[0] },
y: function(d) { return d[1] },
})
rect.exit().remove()
}
//
// bresenham
//
function bresenham(a, b) {
var marked = []
var x0 = a[0], y0 = a[1], x1 = b[0], y1 = b[1]
var dx = Math.abs(x1-x0), sx = x0<x1 ? 1 : -1
var dy = -Math.abs(y1-y0), sy = y0<y1 ? 1 : -1
var err = dx + dy, e2
while(true) {
plot(x0, y0)
if (x0 == x1 && y0 == y1) break
e2 = 2 * err
if (e2 > dy) { err += dy; x0 += sx; }
if (e2 < dx) { err += dx; y0 += sy; }
}
function plot(x, y) {
marked.push([x, y])
}
return marked
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment