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 Efficient Computation of Smallest Enclosing Balls in Three Dimensions by Linus Källberg to avoid performing local copies of data have been included.
| Modifier and Type | Field and Description |
|---|---|
| private final SupportBallGenerator | generator
Generator for balls on support. |
| private final double | tolerance
Tolerance below which points are consider to be identical. |
| Access | Constructor and Description |
|---|---|
| public | WelzlEncloser(final double
below which points are consider to be identical tolerance, final SupportBallGenerator<S, P> generator for balls on support generator)Simple constructor. |
| Modifier and Type | Method and Description |
|---|---|
| public EnclosingBall | enclose(final Iterable<P>
points to enclose points)Implements org. Find a ball enclosing a list of points. |
| private EnclosingBall | Returns: enclosing ball, for the extreme subset onlysubset of extreme points extreme, final int number of extreme points to consider nbExtreme, final List<P> points that must belong to the ball support support)Compute enclosing ball using Welzl's move to front heuristic. |
| private EnclosingBall | Returns: enclosing ballpoints to be enclosed points)Compute enclosing ball using Gärtner's pivoting heuristic. |
| public P | Returns: farthest pointpoints to be enclosed points, final EnclosingBall<S, P> current ball ball)Select the point farthest to the current ball. |
| generator | back to summary |
|---|---|
| private final SupportBallGenerator<S, P> generator Generator for balls on support. | |
| tolerance | back to summary |
|---|---|
| private final double tolerance Tolerance below which points are consider to be identical. | |
| WelzlEncloser | back to summary |
|---|---|
| public WelzlEncloser(final double tolerance, final SupportBallGenerator<S, P> generator) Simple constructor.
| |
| enclose | back to summary |
|---|---|
| public EnclosingBall Implements org. Doc from org. Find a ball enclosing a list of points.
| |
| moveToFrontBall | back to summary |
|---|---|
| private EnclosingBall Compute enclosing ball using Welzl's move to front heuristic.
| |
| pivotingBall | back to summary |
|---|---|
| private EnclosingBall Compute enclosing ball using Gärtner's pivoting heuristic.
| |
| selectFarthest | back to summary |
|---|---|
| public P selectFarthest(final Iterable<P> points, final EnclosingBall<S, P> ball) Select the point farthest to the current ball.
| |