Class WelzlEncloser<S extends Space,P extends Point<S>>

java.lang.Object
org.apache.commons.math3.geometry.enclosing.WelzlEncloser<S,P>
Type Parameters:
S - Space type.
P - Point type.
All Implemented Interfaces:
Encloser<S,P>

public class WelzlEncloser<S extends Space,P extends Point<S>> extends Object implements Encloser<S,P>
Class implementing Emo Welzl algorithm to find the smallest enclosing ball in linear time.

The class implements the algorithm described in paper Smallest Enclosing Disks (Balls and Ellipsoids) by Emo Welzl, Lecture Notes in Computer Science 555 (1991) 359-370. The pivoting improvement published in the paper Fast and Robust Smallest Enclosing Balls, by Bernd Gärtner and further modified in paper invalid input: '<'a href=http://www.idt.mdh.se/kurser/ct3340/ht12/MINICONFERENCE/FinalPapers/ircse12_submission_30.pdf"> Efficient Computation of Smallest Enclosing Balls in Three Dimensions by Linus Källberg to avoid performing local copies of data have been included.

Since:
3.3
  • Field Details

    • tolerance

      private final double tolerance
      Tolerance below which points are consider to be identical.
    • generator

      private final SupportBallGenerator<S extends Space,P extends Point<S>> generator
      Generator for balls on support.
  • Constructor Details

    • WelzlEncloser

      public WelzlEncloser(double tolerance, SupportBallGenerator<S,P> generator)
      Simple constructor.
      Parameters:
      tolerance - below which points are consider to be identical
      generator - generator for balls on support
  • Method Details

    • enclose

      public EnclosingBall<S,P> enclose(Iterable<P> points)
      Find a ball enclosing a list of points.
      Specified by:
      enclose in interface Encloser<S extends Space,P extends Point<S>>
      Parameters:
      points - points to enclose
      Returns:
      enclosing ball
    • pivotingBall

      private EnclosingBall<S,P> pivotingBall(Iterable<P> points)
      Compute enclosing ball using Gärtner's pivoting heuristic.
      Parameters:
      points - points to be enclosed
      Returns:
      enclosing ball
    • moveToFrontBall

      private EnclosingBall<S,P> moveToFrontBall(List<P> extreme, int nbExtreme, List<P> support)
      Compute enclosing ball using Welzl's move to front heuristic.
      Parameters:
      extreme - subset of extreme points
      nbExtreme - number of extreme points to consider
      support - points that must belong to the ball support
      Returns:
      enclosing ball, for the extreme subset only
    • selectFarthest

      public P selectFarthest(Iterable<P> points, EnclosingBall<S,P> ball)
      Select the point farthest to the current ball.
      Parameters:
      points - points to be enclosed
      ball - current ball
      Returns:
      farthest point