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
local function isCCW(p, q, r) return signedArea(p, q, r) < 0 end
local function jarvis_march(points)
local numPoints = #points
if numPoints < 3 then return end
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 = {}
repeat
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])
p = q
until (p == leftMostPointIndex)
return hull
end