- 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 java.lang.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 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 Summary
Fields Modifier and Type Field Description private SupportBallGenerator<S,P>
generator
Generator for balls on support.private double
tolerance
Tolerance below which points are consider to be identical.
-
Constructor Summary
Constructors Constructor Description WelzlEncloser(double tolerance, SupportBallGenerator<S,P> generator)
Simple constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
Constructor Detail
-
WelzlEncloser
public WelzlEncloser(double tolerance, SupportBallGenerator<S,P> generator)
Simple constructor.- Parameters:
tolerance
- below which points are consider to be identicalgenerator
- generator for balls on support
-
-
Method Detail
-
enclose
public EnclosingBall<S,P> enclose(java.lang.Iterable<P> points)
Find a ball enclosing a list of points.
-
pivotingBall
private EnclosingBall<S,P> pivotingBall(java.lang.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(java.util.List<P> extreme, int nbExtreme, java.util.List<P> support)
Compute enclosing ball using Welzl's move to front heuristic.- Parameters:
extreme
- subset of extreme pointsnbExtreme
- number of extreme points to considersupport
- points that must belong to the ball support- Returns:
- enclosing ball, for the extreme subset only
-
selectFarthest
public P selectFarthest(java.lang.Iterable<P> points, EnclosingBall<S,P> ball)
Select the point farthest to the current ball.- Parameters:
points
- points to be enclosedball
- current ball- Returns:
- farthest point
-
-