Added Jarvi's convex hull in Lua

Yonaba · Yonaba · commit 7f0e78047183 · 2014-02-08T21:01:20.000Z
diff --git a/Convex_hull/Lua/Yonaba/convex_hull.lua b/Convex_hull/Lua/Yonaba/convex_hull.lua
@@ -0,0 +1,50 @@
+-- Convex hull algorithms implementation
+-- See : http://en.wikipedia.org/wiki/Convex_hull
+
+-- Checks if points p, q, r are oriented counter-clockwise
+local function isCCW(p, q, r)
+  local cross = (q.y - p.y) * (r.x - q.x)
+              - (q.x - p.x) * (r.y - q.y)
+  return cross < 0
+end
+
+-- Returns the convex hull using Jarvi's 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 jarvi_convex_hull(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 {
+  jarvi = jarvi_convex_hull
+}
diff --git a/Convex_hull/Lua/Yonaba/convex_hull_test.lua b/Convex_hull/Lua/Yonaba/convex_hull_test.lua
@@ -0,0 +1,51 @@
+-- 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.jarvi(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.jarvi(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)))
