Last active
August 29, 2015 14:06
-
-
Save boxdot/6cd4024af75bd57c6cf2 to your computer and use it in GitHub Desktop.
Bresenham's line algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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