## bresenham based supercover line

### Data

#### Tags

geometry, graphics

### 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)))
``````