On 01/28/2014 09:29 PM, l...@apache.org wrote: > Author: luc > Date: Tue Jan 28 20:29:27 2014 > New Revision: 1562220 > > URL: http://svn.apache.org/r1562220 > Log: > Added Emo Welzl algorithm finding points smallest enclosing ball. > > JIRA: MATH-1095 > > Added: > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/ > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java > (with props) > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java > (with props) > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java > (with props) > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java > (with props) > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java > (with props) > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/BallGenerator.java > (with props) > > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/ > > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloserTest.java > (with props) > > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/BallGeneratorTest.java > (with props) > Modified: > commons/proper/math/trunk/src/changes/changes.xml
Hi Luc, looks nice and gives me some good ideas for the ConvexHull too! Thanks, Thomas > > Modified: commons/proper/math/trunk/src/changes/changes.xml > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1562220&r1=1562219&r2=1562220&view=diff > ============================================================================== > --- commons/proper/math/trunk/src/changes/changes.xml (original) > +++ commons/proper/math/trunk/src/changes/changes.xml Tue Jan 28 20:29:27 2014 > @@ -51,6 +51,9 @@ If the output is not quite correct, chec > </properties> > <body> > <release version="3.3" date="TBD" description="TBD"> > + <action dev="luc" type="add" issue="MATH-1095"> > + Added Emo Welzl algorithm to find the smallest enclosing ball of a > collection of points. > + </action> > <action dev="erans" type="fix" issue="MATH-985" due-to="Johnathan > Kool"> > Fixed an indexing problem in "BicubicSplineInterpolatingFunction" > which > resulted in wrong interpolations. > > Added: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java?rev=1562220&view=auto > ============================================================================== > --- > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java > (added) > +++ > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java > Tue Jan 28 20:29:27 2014 > @@ -0,0 +1,39 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math3.geometry.enclosing; > + > +import java.util.List; > + > +import org.apache.commons.math3.geometry.Point; > +import org.apache.commons.math3.geometry.Space; > + > +/** Interface for algorithms computing enclosing balls. > + * @param <S> Space type. > + * @param <P> Point type. > + * @version $Id$ > + * @see EnclosingBall > + * @since 3.3 > + */ > +public interface Encloser<S extends Space, P extends Point<S>> { > + > + /** Find a ball enclosing a list of points. > + * @param points points to enclose > + * @return enclosing ball > + */ > + EnclosingBall<S, P> enclose(List<P> points); > + > +} > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java > ------------------------------------------------------------------------------ > svn:keywords = "Author Date Id Revision" > > Added: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java?rev=1562220&view=auto > ============================================================================== > --- > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java > (added) > +++ > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java > Tue Jan 28 20:29:27 2014 > @@ -0,0 +1,104 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math3.geometry.enclosing; > + > +import java.io.Serializable; > + > +import org.apache.commons.math3.geometry.Point; > +import org.apache.commons.math3.geometry.Space; > + > +/** This class represents a ball enclosing some points. > + * @param <S> Space type. > + * @param <P> Point type. > + * @version $Id$ > + * @see Space > + * @see Point > + * @see Encloser > + * @since 3.3 > + */ > +public class EnclosingBall<S extends Space, P extends Point<S>> implements > Serializable { > + > + /** Serializable UID. */ > + private static final long serialVersionUID = 20140126L; > + > + /** Center of the ball. */ > + private final P center; > + > + /** Radius of the ball. */ > + private final double radius; > + > + /** Support points used to define the ball. */ > + private final P[] support; > + > + /** Simple constructor. > + * @param center center of the ball > + * @param radius radius of the ball > + * @param support support points used to define the ball > + */ > + public EnclosingBall(final P center, final double radius, final P ... > support) { > + this.center = center; > + this.radius = radius; > + this.support = support.clone(); > + } > + > + /** Get the center of the ball. > + * @return center of the ball > + */ > + public P getCenter() { > + return center; > + } > + > + /** Get the radius of the ball. > + * @return radius of the ball (can be negative if the ball is empty) > + */ > + public double getRadius() { > + return radius; > + } > + > + /** Get the support points used to define the ball. > + * @return support points used to define the ball > + */ > + public P[] getSupport() { > + return support.clone(); > + } > + > + /** Get the number of support points used to define the ball. > + * @return number of support points used to define the ball > + */ > + public int getSupportSize() { > + return support.length; > + } > + > + /** Check if a point is within the ball or at boundary. > + * @param point point to test > + * @return true if the point is within the ball or at boundary > + */ > + public boolean contains(final P point) { > + return point.distance(center) <= radius; > + } > + > + /** Check if a point is within an enlarged ball or at boundary. > + * @param point point to test > + * @param margin margin to consider > + * @return true if the point is within the ball enlarged > + * by the margin or at boundary > + */ > + public boolean contains(final P point, final double margin) { > + return point.distance(center) <= radius + margin; > + } > + > +} > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java > ------------------------------------------------------------------------------ > svn:keywords = "Author Date Id Revision" > > Added: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java?rev=1562220&view=auto > ============================================================================== > --- > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java > (added) > +++ > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java > Tue Jan 28 20:29:27 2014 > @@ -0,0 +1,43 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math3.geometry.enclosing; > + > +import java.util.List; > + > +import org.apache.commons.math3.geometry.Point; > +import org.apache.commons.math3.geometry.Space; > + > +/** Interface for generating balls based on support points. > + * <p> > + * This generator is used in the {@link WelzlEncloser Emo Welzl} algorithm > + * and its derivatives. > + * </p> > + * @param <S> Space type. > + * @param <P> Point type. > + * @version $Id$ > + * @see EnclosingBall > + * @since 3.3 > + */ > +public interface SupportBallGenerator<S extends Space, P extends Point<S>> { > + > + /** Create a ball whose boundary lies on prescribed support points. > + * @param support support points (may be empty) > + * @return ball whose boundary lies on the prescribed support points > + */ > + EnclosingBall<S, P> ballOnSupport(List<P> support); > + > +} > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java > ------------------------------------------------------------------------------ > svn:keywords = "Author Date Id Revision" > > Added: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java?rev=1562220&view=auto > ============================================================================== > --- > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java > (added) > +++ > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java > Tue Jan 28 20:29:27 2014 > @@ -0,0 +1,177 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math3.geometry.enclosing; > + > +import java.util.ArrayList; > +import java.util.List; > + > +import org.apache.commons.math3.geometry.Point; > +import org.apache.commons.math3.geometry.Space; > + > +/** Class implementing Emo Welzl algorithm to find the smallest enclosing > ball in linear time. > + * <p> > + * The class implements the algorithm described in paper <a > + * > href="http://www.inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf";>Smallest > + * Enclosing Disks (Balls and Ellipsoids)</a> by Emo Welzl, Lecture Notes in > Computer Science > + * 555 (1991) 359-370. The pivoting improvement published in the paper <a > + * > href="http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf";>Fast > and > + * Robust Smallest Enclosing Balls</a>, by Bernd Gärtner and further > modified in > + * paper <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</a> > by Linus Källberg > + * to avoid performing local copies of data have been included. > + * </p> > + * @param <S> Space type. > + * @param <P> Point type. > + * @version $Id$ > + * @since 3.3 > + */ > +public class WelzlEncloser<S extends Space, P extends Point<S>> implements > Encloser<S, P> { > + > + /** Tolerance below which points are consider to be identical. */ > + private final double tolerance; > + > + /** Maximum number of points to define a ball. */ > + private final int max; > + > + /** Generator for balls on support. */ > + private final SupportBallGenerator<S, P> generator; > + > + /** Simple constructor. > + * @param tolerance below which points are consider to be identical > + * @param dimension dimension of the space > + * @param generator generator for balls on support > + */ > + protected WelzlEncloser(final double tolerance, final int dimension, > + final SupportBallGenerator<S, P> generator) { > + this.tolerance = tolerance; > + this.max = dimension + 1; > + this.generator = generator; > + } > + > + /** {@inheritDoc} */ > + public EnclosingBall<S, P> enclose(final List<P> points) { > + > + if (points == null || points.isEmpty()) { > + // return an empty ball > + return generator.ballOnSupport(new ArrayList<P>()); > + } > + > + // Emo Welzl algorithm with Bernd Gärtner and Linus Källberg > improvements > + return pivotingBall(points); > + > + } > + > + /** Compute enclosing ball using Gärtner's pivoting heuristic. > + * @param points points to be enclosed > + * @return enclosing ball > + */ > + private EnclosingBall<S, P> pivotingBall(final List<P> points) { > + > + List<P> extreme = new ArrayList<P>(max); > + List<P> support = new ArrayList<P>(max); > + > + // start with only first point selected as a candidate support > + extreme.add(points.get(0)); > + EnclosingBall<S, P> ball = moveToFrontBall(extreme, support); > + > + while (true) { > + > + // select the point farthest to current ball > + final P farthest = selectFarthest(points, ball); > + if (ball.contains(farthest, tolerance)) { > + // we have found a ball containing all points > + return ball; > + } > + > + // recurse search, restricted to the small subset containing > support and farthest point > + support.clear(); > + support.add(farthest); > + ball = moveToFrontBall(extreme, support); > + > + // it was an interesting point, move it to the front > + // according to Gärtner's heuristic > + extreme.add(0, farthest); > + > + // prune the least interesting points > + extreme.subList(ball.getSupportSize(), extreme.size()).clear(); > + > + > + } > + } > + > + /** Compute enclosing ball using Welzl's move to front heuristic. > + * @param extreme subset of extreme points > + * @param support points that must belong to the ball support > + * @return enclosing ball, for the extreme subset only > + */ > + private EnclosingBall<S, P> moveToFrontBall(final List<P> extreme, final > List<P> support) { > + > + // create a new ball on the prescribed support > + EnclosingBall<S, P> ball = generator.ballOnSupport(support); > + > + if (ball.getSupportSize() < max) { > + > + for (int i = 0; i < extreme.size(); ++i) { > + final P pi = extreme.get(i); > + if (!ball.contains(pi, tolerance)) { > + > + // we have found an outside point, > + // enlarge the ball by adding it to the support > + support.add(pi); > + ball = moveToFrontBall(extreme.subList(i + 1, > extreme.size()), support); > + > + // it was an interesting point, move it to the front > + // according to Welzl's heuristic > + for (int j = i; j > 1; --j) { > + extreme.set(j, extreme.get(j - 1)); > + } > + extreme.set(0, pi); > + > + } > + } > + > + } > + > + return ball; > + > + } > + > + /** Select the point farthest to the current ball. > + * @param points points to be enclosed > + * @param ball current ball > + * @return farthest point > + */ > + public P selectFarthest(final List<P> points, final EnclosingBall<S, P> > ball) { > + > + final P center = ball.getCenter(); > + P farthest = null; > + double dMax = -1.0; > + > + for (final P point : points) { > + final double d = point.distance(center); > + if (d > dMax) { > + farthest = point; > + dMax = d; > + } > + } > + > + return farthest; > + > + } > + > +} > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java > ------------------------------------------------------------------------------ > svn:keywords = "Author Date Id Revision" > > Added: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java?rev=1562220&view=auto > ============================================================================== > --- > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java > (added) > +++ > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java > Tue Jan 28 20:29:27 2014 > @@ -0,0 +1,24 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +/** > + * > + * <p> > + * This package provides interfaces and classes related to the smallest > enclosing ball roblem. > + * </p> > + * > + */ > +package org.apache.commons.math3.geometry.enclosing; > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java > ------------------------------------------------------------------------------ > svn:keywords = "Author Date Id Revision" > > Added: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/BallGenerator.java > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/BallGenerator.java?rev=1562220&view=auto > ============================================================================== > --- > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/BallGenerator.java > (added) > +++ > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/BallGenerator.java > Tue Jan 28 20:29:27 2014 > @@ -0,0 +1,69 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math3.geometry.euclidean.twod; > + > +import java.util.List; > + > +import org.apache.commons.math3.geometry.enclosing.EnclosingBall; > +import org.apache.commons.math3.geometry.enclosing.SupportBallGenerator; > +import org.apache.commons.math3.util.MathArrays; > + > +/** Class implementing Emo Welzl algorithm to find the smallest enclosing > ball in linear time. > + * @version $Id$ > + * @since 3.3 > + */ > +public class BallGenerator implements SupportBallGenerator<Euclidean2D, > Vector2D> { > + > + /** {@inheritDoc} */ > + public EnclosingBall<Euclidean2D, Vector2D> ballOnSupport(final > List<Vector2D> support) { > + > + if (support.size() < 1) { > + return new EnclosingBall<Euclidean2D, Vector2D>(Vector2D.ZERO, > -1.0); > + } else { > + final Vector2D vA = support.get(0); > + if (support.size() < 2) { > + return new EnclosingBall<Euclidean2D, Vector2D>(vA, 0, vA); > + } else { > + final Vector2D vB = support.get(1); > + if (support.size() < 3) { > + return new EnclosingBall<Euclidean2D, Vector2D>(new > Vector2D(0.5, vA, 0.5, vB), > + 0.5 * > vA.distance(vB), > + vA, vB); > + } else { > + final Vector2D vC = support.get(2); > + final Vector2D bc = vB.subtract(vC); > + final Vector2D ca = vC.subtract(vA); > + final Vector2D ab = vA.subtract(vB); > + final double vA2 = vA.getNormSq(); > + final double vB2 = vB.getNormSq(); > + final double vC2 = vC.getNormSq(); > + final double d = 2 * > MathArrays.linearCombination(vA.getX(), bc.getY(), > + > vB.getX(), ca.getY(), > + > vC.getX(), ab.getY()); > + final Vector2D center = new Vector2D( > MathArrays.linearCombination(vA2, bc.getY(), > + > vB2, ca.getY(), > + > vC2, ab.getY()) / d, > + > -MathArrays.linearCombination(vA2, bc.getX(), > + > vB2, ca.getX(), > + > vC2, ab.getX()) / d); > + return new EnclosingBall<Euclidean2D, Vector2D>(center, > center.distance(vA), vA, vB, vC); > + } > + } > + } > + } > + > +} > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/BallGenerator.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/BallGenerator.java > ------------------------------------------------------------------------------ > svn:keywords = "Author Date Id Revision" > > Added: > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloserTest.java > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloserTest.java?rev=1562220&view=auto > ============================================================================== > --- > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloserTest.java > (added) > +++ > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloserTest.java > Tue Jan 28 20:29:27 2014 > @@ -0,0 +1,158 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math3.geometry.enclosing; > + > +import java.util.ArrayList; > +import java.util.Arrays; > +import java.util.List; > + > +import org.apache.commons.math3.geometry.euclidean.twod.BallGenerator; > +import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D; > +import org.apache.commons.math3.geometry.euclidean.twod.Vector2D; > +import org.apache.commons.math3.random.RandomGenerator; > +import org.apache.commons.math3.random.Well1024a; > +import org.junit.Assert; > +import org.junit.Test; > + > + > +public class WelzlEncloserTest { > + > + @Test > + public void testNullList() { > + BallGenerator generator = new BallGenerator(); > + WelzlEncloser<Euclidean2D, Vector2D> encloser = > + new WelzlEncloser<Euclidean2D, Vector2D>(1.0e-10, 2, > generator); > + EnclosingBall<Euclidean2D, Vector2D> ball = encloser.enclose(null); > + Assert.assertTrue(ball.getRadius() < 0); > + } > + > + @Test > + public void testNoPoints() { > + BallGenerator generator = new BallGenerator(); > + WelzlEncloser<Euclidean2D, Vector2D> encloser = > + new WelzlEncloser<Euclidean2D, Vector2D>(1.0e-10, 2, > generator); > + EnclosingBall<Euclidean2D, Vector2D> ball = encloser.enclose(new > ArrayList<Vector2D>()); > + Assert.assertTrue(ball.getRadius() < 0); > + } > + > + @Test > + public void testRegularPoints() { > + List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28, 8, 54, 11, > 15); > + checkBall(list, Arrays.asList(list.get(2), list.get(3), > list.get(4))); > + } > + > + @Test > + public void testSolutionOnDiameter() { > + List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28, 8, 54); > + checkBall(list, Arrays.asList(list.get(2), list.get(3))); > + } > + > + @Test > + public void testLargeSamples() { > + RandomGenerator random = new Well1024a(0xa2a63cad12c01fb2l); > + for (int k = 0; k < 100; ++k) { > + int nbPoints = random.nextInt(10000); > + List<Vector2D> points = new ArrayList<Vector2D>(); > + for (int i = 0; i < nbPoints; ++i) { > + double x = random.nextDouble(); > + double y = random.nextDouble(); > + points.add(new Vector2D(x, y)); > + } > + checkBall(points); > + } > + } > + > + private List<Vector2D> buildList(final double ... coordinates) { > + List<Vector2D> list = new ArrayList<Vector2D>(coordinates.length / > 2); > + for (int i = 0; i < coordinates.length; i += 2) { > + list.add(new Vector2D(coordinates[i], coordinates[i + 1])); > + } > + return list; > + } > + > + private void checkBall(List<Vector2D> points, List<Vector2D> refSupport) > { > + > + EnclosingBall<Euclidean2D, Vector2D> ball = checkBall(points); > + > + // compare computed ball with expected ball > + BallGenerator generator = new BallGenerator(); > + EnclosingBall<Euclidean2D, Vector2D> expected = > generator.ballOnSupport(refSupport); > + Assert.assertEquals(refSupport.size(), ball.getSupportSize()); > + Assert.assertEquals(expected.getRadius(), ball.getRadius(), > 1.0e-10); > + Assert.assertEquals(expected.getCenter().getX(), > ball.getCenter().getX(), 1.0e-10); > + Assert.assertEquals(expected.getCenter().getY(), > ball.getCenter().getY(), 1.0e-10); > + > + for (Vector2D s : ball.getSupport()) { > + boolean found = false; > + for (Vector2D rs : refSupport) { > + if (s == rs) { > + found = true; > + } > + } > + Assert.assertTrue(found); > + } > + > + // check removing any point of the support ball fails to enclose the > point > + for (int i = 0; i < ball.getSupportSize(); ++i) { > + List<Vector2D> reducedSupport = new ArrayList<Vector2D>(); > + int count = 0; > + for (Vector2D s : ball.getSupport()) { > + if (count++ != i) { > + reducedSupport.add(s); > + } > + } > + EnclosingBall<Euclidean2D, Vector2D> reducedBall = > generator.ballOnSupport(reducedSupport); > + boolean foundOutside = false; > + for (int j = 0; j < points.size() && !foundOutside; ++j) { > + if (!reducedBall.contains(points.get(j), 1.0e-10)) { > + foundOutside = true; > + } > + } > + Assert.assertTrue(foundOutside); > + } > + > + } > + > + private EnclosingBall<Euclidean2D, Vector2D> checkBall(List<Vector2D> > points) { > + > + WelzlEncloser<Euclidean2D, Vector2D> encloser = > + new WelzlEncloser<Euclidean2D, Vector2D>(1.0e-10, 2, new > BallGenerator()); > + EnclosingBall<Euclidean2D, Vector2D> ball = encloser.enclose(points); > + > + // all points are enclosed > + for (Vector2D v : points) { > + Assert.assertTrue(ball.contains(v, 1.0e-10)); > + } > + > + for (Vector2D v : points) { > + boolean inSupport = false; > + for (Vector2D s : ball.getSupport()) { > + if (v == s) { > + inSupport = true; > + } > + } > + if (inSupport) { > + // points on the support should be outside of reduced ball > + Assert.assertFalse(ball.contains(v, -0.001)); > + } > + } > + > + return ball; > + > + } > + > +} > > Propchange: > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloserTest.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloserTest.java > ------------------------------------------------------------------------------ > svn:keywords = "Author Date Id Revision" > > Added: > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/BallGeneratorTest.java > URL: > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/BallGeneratorTest.java?rev=1562220&view=auto > ============================================================================== > --- > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/BallGeneratorTest.java > (added) > +++ > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/BallGeneratorTest.java > Tue Jan 28 20:29:27 2014 > @@ -0,0 +1,96 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math3.geometry.euclidean.twod; > + > +import java.util.Arrays; > +import java.util.List; > + > +import org.apache.commons.math3.geometry.enclosing.EnclosingBall; > +import org.junit.Assert; > +import org.junit.Test; > + > + > +public class BallGeneratorTest { > + > + @Test > + public void testSupport0Point() { > + List<Vector2D> support = Arrays.asList(new Vector2D[0]); > + EnclosingBall<Euclidean2D, Vector2D> ball = new > BallGenerator().ballOnSupport(support); > + Assert.assertTrue(ball.getRadius() < 0); > + Assert.assertEquals(0, ball.getSupportSize()); > + Assert.assertEquals(0, ball.getSupport().length); > + } > + > + @Test > + public void testSupport1Point() { > + List<Vector2D> support = Arrays.asList(new Vector2D(1, 2)); > + EnclosingBall<Euclidean2D, Vector2D> ball = new > BallGenerator().ballOnSupport(support); > + Assert.assertEquals(0.0, ball.getRadius(), 1.0e-10); > + Assert.assertTrue(ball.contains(support.get(0))); > + Assert.assertTrue(ball.contains(support.get(0), 0.5)); > + Assert.assertFalse(ball.contains(new Vector2D(support.get(0).getX() > + 0.1, > + support.get(0).getY() > - 0.1), > + 0.001)); > + Assert.assertTrue(ball.contains(new Vector2D(support.get(0).getX() + > 0.1, > + support.get(0).getY() - > 0.1), > + 0.5)); > + Assert.assertEquals(0, support.get(0).distance(ball.getCenter()), > 1.0e-10); > + Assert.assertEquals(1, ball.getSupportSize()); > + Assert.assertTrue(support.get(0) == ball.getSupport()[0]); > + } > + > + @Test > + public void testSupport2Points() { > + List<Vector2D> support = Arrays.asList(new Vector2D(1, 0), > + new Vector2D(3, 0)); > + EnclosingBall<Euclidean2D, Vector2D> ball = new > BallGenerator().ballOnSupport(support); > + Assert.assertEquals(1.0, ball.getRadius(), 1.0e-10); > + int i = 0; > + for (Vector2D v : support) { > + Assert.assertTrue(ball.contains(v)); > + Assert.assertEquals(1.0, v.distance(ball.getCenter()), 1.0e-10); > + Assert.assertTrue(v == ball.getSupport()[i++]); > + } > + Assert.assertTrue(ball.contains(new Vector2D(2, 0.9))); > + Assert.assertFalse(ball.contains(Vector2D.ZERO)); > + Assert.assertEquals(0.0, new Vector2D(2, > 0).distance(ball.getCenter()), 1.0e-10); > + Assert.assertEquals(2, ball.getSupportSize()); > + } > + > + @Test > + public void testSupport3Points() { > + List<Vector2D> support = Arrays.asList(new Vector2D(1, 0), > + new Vector2D(3, 0), > + new Vector2D(2, 2)); > + EnclosingBall<Euclidean2D, Vector2D> ball = new > BallGenerator().ballOnSupport(support); > + Assert.assertEquals(5.0 / 4.0, ball.getRadius(), 1.0e-10); > + int i = 0; > + for (Vector2D v : support) { > + Assert.assertTrue(ball.contains(v)); > + Assert.assertEquals(5.0 / 4.0, v.distance(ball.getCenter()), > 1.0e-10); > + Assert.assertTrue(v == ball.getSupport()[i++]); > + } > + Assert.assertTrue(ball.contains(new Vector2D(2, 0.9))); > + Assert.assertFalse(ball.contains(new Vector2D(0.9, 0))); > + Assert.assertFalse(ball.contains(new Vector2D(3.1, 0))); > + Assert.assertTrue(ball.contains(new Vector2D(2.0, -0.499))); > + Assert.assertFalse(ball.contains(new Vector2D(2.0, -0.501))); > + Assert.assertEquals(0.0, new Vector2D(2.0, 3.0 / > 4.0).distance(ball.getCenter()), 1.0e-10); > + Assert.assertEquals(3, ball.getSupportSize()); > + } > + > +} > > Propchange: > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/BallGeneratorTest.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/BallGeneratorTest.java > ------------------------------------------------------------------------------ > svn:keywords = "Author Date Id Revision" > > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
