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.miniballMethod.
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
Miniball.currierMethod.
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
Miniball.pow_2Method.
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

Index