Module:CineMol/fitting

-- 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
This page was redesigned at the edge.
