bresenham line


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Bresenham line marching algorithm implementation
-- See: http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html

-- x0: the x-coordinate of the start point
-- y0: the y-coordinate of the end point
-- x1: the x-coordinate of the start point
-- y1: the y-coordinate of the end point
-- returns: an array of {x = x, y = y} pairs
return function(x0, y0, x1, y1)
  local points = {}
  local dx, dy = math.abs(x1-x0), math.abs(y1-y0)
  local err = dx - dy
  local sx, sy= (x0 < x1) and 1 or -1, (y0 < y1) and 1 or -1

  while true do
    points[#points + 1] = {x = x0, y = y0}
    if x0 == x1 and y0 == y1 then break end
    local e2 = 2 * err
    if e2 > -dy then
      err = err - dy
      x0 = x0 + sx
    end
    if e2 < dx then
      err = err + dx
      y0 = y0 + sy
    end
  end
  return points
end
-- Tests for bresenham.lua
local bresenham = require 'bresenham'

local total, pass = 0, 0

local function dec(str, len)
	return #str < len
	   and str .. (('.'):rep(len-#str))
		  or str:sub(1,len)
end

local function run(message, f)
	total = total + 1
	local ok, err = pcall(f)
	if ok then pass = pass + 1 end
	local status = ok and 'PASSED' or 'FAILED'
	print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

-- Checks if t1 and t2 arrays are the same
local function same(t1, t2)
	for k,v in ipairs(t1) do
		if t2[k].x ~= v.x or t2[k].y ~= v.y then 
      return false
    end
	end
	return true
end

run('Testing Bresenham line marching', function()
	local expected = {{x = 1, y = 1}, {x = 2, y = 2}, {x = 3, y = 3}, {x = 4, y = 4}, {x = 5, y = 5}}
  assert(same(bresenham(1, 1, 5, 5), expected))
	local expected = {{x = 1, y = 1}, {x = 2, y = 2}, {x = 2, y = 3}, {x = 3, y = 4}} 
  assert(same(bresenham(1, 1, 3, 4), expected))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
	:format(total, pass, total-pass, (pass*100/total)))