BoundingSphere.WelzlMTF — Type
WelzlMTF()

Welzl algorithm with move to front heuristic. See Algorithm I in https://people.inf.ethz.ch/gaertner/subdir/texts/ownwork/esa99final.pdf. In almost all situations it is better to use WelzlPivot instead.

Pros

  • Fast for small examples

Cons

  • Prone to numerical stability issues
BoundingSphere.WelzlPivot — Type
WelzlPivot(;max_iterations=1000)

Welzl algorithm with pivoting. See Algorithm II in https://people.inf.ethz.ch/gaertner/subdir/texts/ownwork/esa99final.pdf.

Pros

  • Fast

Cons

  • In very rare cases can be numerically instable
BoundingSphere.boundingsphere — Function
center, radius = boundingsphere(pts [, algorithm=WelzlPivot()])

Compute the smallest sphere that contains each point in pts.

Arguments

  • pts: A list of points. Points should be vectors with floating point entries.
  • algorithm: An optional algorithm to do the computation. See names(BoundingSphere) to get
BoundingSphere.BoundaryDevice — Type
BoundaryDevice

Finds unique spheres determined by prescribed affine independent boundary points. In the welzl algorithm this problem needs to be solved in series, where points are pushed and popped from to the boundary.

Subtypes must implement the following interface:

  • pushifstable!(device, pt)::Bool :
  • pop!(device): Remove last point from the boundary.
  • get_ball(device)::SqBall : Get the last ball from the device.
  • length(device)::Int : Get the current count of boundary points
  • ismaxlength(device)::Bool: Check if there are dim+1 boundary points in the device