Miniball.jl

# Miniball.jl

This is a Julia package for finding the smallest enclosing sphere for a set of points in an arbitrary number of dimensions. The implementation is based on Bernd Gärtner's C++ Miniball but is implemented entirely in Julia. The original C++ implementation is licensed under GNU General Public License (GPLv3), which is why this implementation also has the same license.

## Typical useage

This package has a simple interface. Call

``ball = miniball(points)``

where `points` is a 2D array of size `n × d` representing `n` points in `d` dimensions. The resulting object `ball` has two fields – `ball.center` and `ball.squared_radius` which contain details about the resulting miniball.

The `minball` function covers most use cases, but descriptions of all functions including internals can be found below.

## Types and functions

``miniball(points)``

Calculate the miniball (minimal enclosing hypersphere) of a set of points.

Parameters

``````points: Array{AbstractFloat, 2}
A 2D array of points, which is used to calculate the miniball.  The first dimension of the array corresponds to different points while the second dimension corresponds to the coordinate in each of N dimensions.``````

Returns

``````container: MBContainer
MBContainer type, which holds all the calculated values.``````

Example

2D-points (x, y): points = rand(100, 2) ball = miniball(points)

3D-points (x, y, z): points = rand(100, 3) ball = miniball(points)

source

MBContainer container

source
``calculate_miniball(container)``

Function for creating the support vector. This function finds the furthest point from the current center: the pivot point. The pivot point is added into the support vector, which is then used to create the miniball.

source
``currier(dim)``

Currier function for creating a loop list in push_fsize_not_zero function. This function's only purpose is to reduce the amount of memory used.

source
``find_pivot(len, points, center, arr_squared_r, dim)``

Find a pivot point, which is used for calculating the new miniball.

source
``inside_current_ball(coords, center, squared_radius, dim)``

Check if the given point is already inside the current miniball.

source
``miniball_pivot(container)``

Main loop for calculating the miniball. The algorithm can be found at http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf. It is from B. Gaertner, Fast and Robust Smallest Enclosing Balls, ESA 1999, as Algorithm 2: pivot_mb

source
``miniball_support_points(container, end_support_vector)``

Recursive function for creating a miniball using the support vector.

source
``new_center_and_radius!(pivot, container)``

Function for creating a miniball. All the math related for calculating the miniball can be found from the http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf, from B. Gaertner, Fast and Robust Smallest Enclosing Balls, ESA 1999, from section 3. The Primitive Operation and after that.

source
``pivot_move_to_front(pivot, container)``

Appends a pivot point to the front of the support vector.

source
``pow_2(r)``

Calculates the square of a float: r^2

source
``push_fsize_not_zero(pivot, container)``

fsize != 1, calculate the miniball center and squared radius using the current pivot element.

source
``push_fsize_zero(pivot, container)``

fsize == 1, insert pivot element to q0 and c vectors

source
``support_points_move_to_front(container, element, id_)``

Moves the support points inside the support vector. The idea is to move the points that are the furthest apart from each other to the front of the vector. Closest points to gather are at the end of the vector.

source