MBR.jl

using GeometryBasics

x(a::Point{2, T}) where { T <: Number } = first(a)
y(a::Point{2, T}) where { T <: Number } = last(a)
#Ewy
Matrix(z::Vector{Point{2, T}}) where { T <: Number } = hcat( z .|> x, z .|> y )
to_points(z) = [ Point(z[:,r][:]...) for r in 1:size(z,2)]

function orientation(p::Point{2, T}, q::Point{2, T}, r::Point{2, T})::Int where {T <: Number }
	val = ( y(q) - y(p) ) * ( x(r) - x(q) ) - ( x(q) - x(p) ) * ( y(r) - y(q) ) 
    return (val == 0) ? 0 : ( (val > 0) ? 1 : 2 )
end

"""
Classic Jarvis/Gift Wrapping Convex Hull
"""
function convexhull( points::Vector{Point{2, T}} )::Vector where {T <: Number } 
    n       = length(points) 
	@assert (n > 2) "Convex Hull requires at least 3 points." 
    hull    = []
    p, q    = argmin( x.( points ) ), 0
    init = p
	while ( p != init ) || (length(hull) == 0)
		push!( hull, p ) 
		q = (( p + 1 ) % n ) + 1 #+ 1
		for i in 1:n 
            if orientation(points[p], points[i], points[q]) == 2 
                q = i 
            end
        end
		p = q; 
    end
    return hull
end
p1 = Vector(Point{2, Int}[  Point(3, 1),
                            Point(2, 2),
                            Point(1, 1),
                            Point(2, 1),
                            Point(3, 0),
                            Point(0, 0),
                            Point(3, 3) 
] )
hull_inds = convexhull( p1 )

function minimum_bounding_rectangle( points, hull_idxs )
    n = length(hull_idxs)
    # calculate edge angles
    #edges = points[ hull_idxs[ 2:end ] ] - points[ hull_idxs[ 1:(end-1) ] ]
    edges = points[ hull_idxs[ 1:(end-1) ] ] .- points[ hull_idxs[ 2:end ] ]
    angles = atan.( y.( edges ), x.( edges ) ) .% (pi/2)
    angles = unique( abs.( angles  ) )
    # find rotation matrices
    rot_matrices = zeros( 2, 2, length( angles ) )
    rot_matrices[1,1,:] = cos.(angles)
    rot_matrices[1,2,:] = -sin.(angles )
    rot_matrices[2,1,:] = sin.( angles )
    rot_matrices[2,2,:] = cos.( angles )
    const_view = Matrix( points[ hull_idxs ] )
    rot_points = [ rot_matrices[:,:,z] * const_view' for z in 1:size( rot_matrices, 3 ) ]
    # find the bounding points
    min_x = [ reduce( min, rp[1,:] ) for rp in rot_points]
    max_x = [ reduce( max, rp[1,:] ) for rp in rot_points]
    min_y = [ reduce( min, rp[2,:] ) for rp in rot_points]
    max_y = [ reduce( max, rp[2,:] ) for rp in rot_points]
    # find the box with the best area
    smallest_box = argmin( (max_x .- min_x) .* (max_y .- min_y) )
    x1,x2 = min_x[smallest_box], max_x[smallest_box]
    y1,y2 = min_y[smallest_box], max_y[smallest_box]
    return rot_matrices[:,:,smallest_box]' * [ x1 y1; x1 y2; x2 y2; x2 y1 ]'
end 

p1 = Vector(Point{2, Float64}[  Point(randn(2)...),
                            Point(randn(2)...),
                            Point(randn(2)...),
                            Point(randn(2)...),
                            Point(randn(2)...),
                            Point(randn(2)...)
] )

hull_inds = convexhull( p1 )
mbr = minimum_bounding_rectangle( p1, hull_inds )

using Plots
scatter( p1, color = "black", legend = false);
scatter!( p1[hull_inds], color = "purple");
scatter!(mbr |> to_points , color = "pink")