convex hull


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

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>}.
-- See : http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
-- 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)))