-- This is a port of CineMol to lua
-- CineMol https://github.com/moltools/CineMol was written by David Meijer, Marnix H. Medema & Justin J. J. van der Hooft and is MIT licensed
-- Please consider any edits I make to this page also dual licensed MIT & CC-BY-SA 4.0
local p = {}
local Point2D = require( 'Module:CineMol/geometry' ).Point2D
local function argmin(vals)
assert( #vals > 0, "At least one value must be provided" )
assert( vals[1]._TYPE == 'Point2D', "expected list of Point2D" )
local min = vals[1].x
local minIndex = 1
for i,v in ipairs(vals) do
if ( v.x < min ) then
min = v.x
minIndex = i
end
end
return minIndex
end
local function argmax(vals)
assert( #vals > 0, "At least one value must be provided" )
assert( vals[1]._TYPE == 'Point2D', "expected list of Point2D" )
local max = vals[1].x
local maxIndex = 1
for i,v in ipairs(vals) do
if ( v.x > max ) then
max = v.x
maxIndex = i
end
end
return maxIndex
end
-- Original was 0-indexed, converting to 1-indexed
local function arange(n)
local res = {}
for i = 1,n do
res[i] = i
end
return res
end
local function append( t1, t2 )
for i,v in ipairs(t2) do
t1[#t1+1] = v
end
return t1
end
-- Recursively computes the convex hull of a set of points in 2D space.
local function process( points, indices_of_points_to_consider, index_a, index_b )
-- Calculate the signed distance from each point in indices_of_points_to_consider
-- to the line between a and b.
local signed_dist = {}
for _, i in ipairs(indices_of_points_to_consider) do
signed_dist[#signed_dist+1] =
points[i]
:subtract_point(points[index_a])
:cross(points[index_b]:subtract_point(points[index_a]))
end
-- Find the points in indices_of_points_to_consider that are on the positive
-- side of the line between a and b.
local indices_on_positive_side = {}
for n, s in ipairs(signed_dist) do
local i = indices_of_points_to_consider[n]
if ( s > 0 and i ~= index_a and i ~= index_b ) then
indices_on_positive_side[#indices_on_positive_side+1] = i
end
end
-- If there are no points on the positive side of the line, return the line.
if #indices_on_positive_side == 0 then
return {index_a, index_b}
end
-- Find the point in indices_of_points_to_consider that is farthest from the
-- line between a and b.
local index_c = indices_of_points_to_consider[1]
local max = signed_dist[1]
for i, sd in ipairs(signed_dist) do
if sd > max then
max = sd
index_c = indices_of_points_to_consider[i]
end
end
-- Recursively compute the convex hull of the points on the positive side of the line.
local firstHalf = process(points, indices_on_positive_side, index_a, index_c)
table.remove( firstHalf ) -- remove last entry
local secondHalf = process(
points, indices_on_positive_side, index_c, index_b
)
return append( firstHalf, secondHalf )
end
-- Note, unlike original, this returns results 1-indexed.
function p.calculate_convex_hull(points)
assert( type(points) == 'table', 'First argument should be a list of Point2Ds' )
assert( #points > 0, "At least one point is needed" )
assert( points[1]._TYPE == 'Point2D', 'First argument should be a list of Point2Ds' )
local min_index = argmin(points)
local max_index = argmax(points)
local firstHalf = process(points, arange(#points), min_index, max_index)
table.remove( firstHalf ) -- remove last entry
local secondHalf = process(points, arange(#points), max_index, min_index)
table.remove( secondHalf ) -- remove last entry
return append( firstHalf, secondHalf )
end
return p
