bresenham based supercover line


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Bresenham-based Supercover line marching algorithm
-- See: http://lifc.univ-fcomte.fr/home/~ededu/projects/bresenham/

-- Note: This algorithm is based on Bresenham's line marching, but
--  instead of considering one step per axis, it covers all the points
--  the ideal line covers. It may be useful for example when you have 
--  to know if an obstacle exists between two points (in which case the 
--  points do not see each other)

-- x1: the x-coordinate of the start point
-- y1: the y-coordinate of the end point
-- x2: the x-coordinate of the start point
-- y2: the y-coordinate of the end point
-- returns: an array of {x = x, y = y} pairs
return function (x1, y1, x2, y2)
  local points = {}
  local xstep, ystep, err, errprev, ddx, ddy
  local x, y = x1, y1
  local dx, dy = x2 - x1, y2 - y1

  points[#points + 1] = {x = x1, y = y1}

  if dy < 0 then
    ystep = ystep - 1
    dy = -dy
  else
    ystep = 1
  end

  if dx < 0 then
    xstep = xstep - 1
    dx = -dx
  else
    xstep = 1
  end

  ddx, ddy = dx * 2, dy * 2

  if ddx >= ddy then
    errprev, err = dx, dx
    for i = 1, dx do
      x = x + xstep
      err = err + ddy
      if err > ddx then
        y = y + ystep
        err = err - ddx
        if err + errprev < ddx then
          points[#points + 1] = {x = x, y = y - ystep}
        elseif err + errprev > ddx then
          points[#points + 1] = {x = x - xstep, y = y}
        else
          points[#points + 1] = {x = x, y = y - ystep}
          points[#points + 1] = {x = x - xstep, y = y}
        end
      end
      points[#points + 1] = {x = x, y = y}
      errprev = err
    end
  else
    errprev, err = dy, dy
    for i = 1, dy do
      y = y + ystep
      err = err + ddx
      if err > ddy then
        x = x + xstep
        err = err - ddy
        if err + errprev < ddy then
          points[#points + 1] = {x = x - xstep, y = y}
        elseif err + errprev > ddy then
          points[#points + 1] = {x = x, y = y - ystep}
        else
          points[#points + 1] = {x = x, y = y - ystep}
          points[#points + 1] = {x = x - xstep, y = y}
        end
      end
      points[#points + 1] = {x = x, y = y}
      errprev = err
    end
  end
  return points
end
-- Tests for bresenham.lua
local supercover_line = require 'bresenham_based_supercover'

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-based supercover line marching', function()
	local expected = {
		{x = 1, y = 1}, {x = 2, y = 1}, {x = 1, y = 2},
		{x = 2, y = 2}, {x = 3, y = 2}, {x = 2, y = 3},
		{x = 3, y = 3}, {x = 4, y = 3}, {x = 3, y = 4},
		{x = 4, y = 4}, {x = 5, y = 4}, {x = 4, y = 5},
		{x = 5, y = 5}
	}
  assert(same(supercover_line(1, 1, 5, 5), expected))
end)

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