convex hull

Data

in lua

Tags

geometry, mathematics

Source Code

``````-- Convex hull algorithms implementation
-- See : http://en.wikipedia.org/wiki/Convex_hull

-- Calculates the signed area
local function signedArea(p, q, r)
local cross = (q.y - p.y) * (r.x - q.x)
- (q.x - p.x) * (r.y - q.y)
return cross
end

-- Checks if points p, q, r are oriented counter-clockwise
local function isCCW(p, q, r) return signedArea(p, q, r) < 0 end

-- Returns the convex hull using Jarvis' Gift wrapping algorithm).
-- It expects an array of points as input. Each point is defined
-- as : {x = <value>, y = <value>}.
-- points  : an array of points
-- returns : the convex hull as an array of points
local function jarvis_march(points)
-- We need at least 3 points
local numPoints = #points
if numPoints < 3 then return end

-- Find the left-most point
local leftMostPointIndex = 1
for i = 1, numPoints do
if points[i].x < points[leftMostPointIndex].x then
leftMostPointIndex = i
end
end

local p = leftMostPointIndex
local hull = {} -- The convex hull to be returned

-- Process CCW from the left-most point to the start point
repeat
-- Find the next point q such that (p, i, q) is CCW for all i
q = points[p + 1] and p + 1 or 1
for i = 1, numPoints, 1 do
if isCCW(points[p], points[i], points[q]) then q = i end
end

table.insert(hull, points[q]) -- Save q to the hull
p = q  -- p is now q for the next iteration
until (p == leftMostPointIndex)

return hull
end

return {
jarvis = jarvis_march
}
``````
``````-- Tests for convex_hull.lua
local hull = require 'convex_hull'

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

-- Compare points
local function same(p1,p2)
return p1.x == p2.x and p1.y == p2.y
end

run('Returns nil when given less than three points', function()
local points = {{x = 0, y = 3}, {x = 2, y = 2}}
assert(hull.jarvis(points) == nil)
end)

run('Returns the convex hull', function()
local points = {
{x = 0, y = 3},
{x = 2, y = 2},
{x = 1, y = 1},
{x = 2, y = 1},
{x = 3, y = 0},
{x = 0, y = 0},
{x = 3, y = 3}
}
local chull = hull.jarvis(points)
assert(#chull == 4)
assert(same(chull[1], {x = 0, y = 0}))
assert(same(chull[2], {x = 3, y = 0}))
assert(same(chull[3], {x = 3, y = 3}))
assert(same(chull[4], {x = 0, y = 3}))
end)

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