S
- Space type.P
- Point type.public class WelzlEncloser<S extends Space,P extends Point<S>> extends java.lang.Object implements Encloser<S,P>
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 SupportBallGenerator<S,P> |
generator
Generator for balls on support.
|
private double |
tolerance
Tolerance below which points are consider to be identical.
|
Constructor and Description |
---|
WelzlEncloser(double tolerance,
SupportBallGenerator<S,P> generator)
Simple constructor.
|
Modifier and Type | Method and Description |
---|---|
EnclosingBall<S,P> |
enclose(java.lang.Iterable<P> points)
Find a ball enclosing a list of points.
|
private EnclosingBall<S,P> |
moveToFrontBall(java.util.List<P> extreme,
int nbExtreme,
java.util.List<P> support)
Compute enclosing ball using Welzl's move to front heuristic.
|
private EnclosingBall<S,P> |
pivotingBall(java.lang.Iterable<P> points)
Compute enclosing ball using Gärtner's pivoting heuristic.
|
P |
selectFarthest(java.lang.Iterable<P> points,
EnclosingBall<S,P> ball)
Select the point farthest to the current ball.
|
private final double tolerance
public WelzlEncloser(double tolerance, SupportBallGenerator<S,P> generator)
tolerance
- below which points are consider to be identicalgenerator
- generator for balls on supportpublic EnclosingBall<S,P> enclose(java.lang.Iterable<P> points)
private EnclosingBall<S,P> pivotingBall(java.lang.Iterable<P> points)
points
- points to be enclosedprivate EnclosingBall<S,P> moveToFrontBall(java.util.List<P> extreme, int nbExtreme, java.util.List<P> support)
extreme
- subset of extreme pointsnbExtreme
- number of extreme points to considersupport
- points that must belong to the ball supportpublic P selectFarthest(java.lang.Iterable<P> points, EnclosingBall<S,P> ball)
points
- points to be enclosedball
- current ball