You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2014/01/28 21:29:28 UTC
svn commit: r1562220 - in /commons/proper/math/trunk/src: changes/
main/java/org/apache/commons/math3/geometry/enclosing/
main/java/org/apache/commons/math3/geometry/euclidean/twod/
test/java/org/apache/commons/math3/geometry/enclosing/ test/java/org/a...
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
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"
Re: svn commit: r1562220 - in /commons/proper/math/trunk/src: changes/
main/java/org/apache/commons/math3/geometry/enclosing/ main/java/org/apache/commons/math3/geometry/euclidean/twod/
test/java/org/apache/commons/math3/geometry/enclosing/ test/java/org/a...
Posted by Thomas Neidhart <th...@gmail.com>.
On 01/28/2014 09:29 PM, luc@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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org