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

    • 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.
    • 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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • tolerance

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

      • 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 Detail

      • enclose

        public EnclosingBall<S,​P> enclose​(java.lang.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​(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 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​(java.lang.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