You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2020/01/16 12:39:49 UTC
[commons-geometry] 01/04: GEOMETRY-85: using list instead of array
for EnclosingBall.getSupport();
using DoublePrecisionContext instead of margin for EnclosingBall.contains();
adding WelzelEncloser2D and WelzelEncloser3D convenience classes
This is an automated email from the ASF dual-hosted git repository.
erans pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
commit 34ce0ca0c23b3dba590448d88cea6daf03796ce8
Author: Matt Juntunen <ma...@hotmail.com>
AuthorDate: Wed Jan 15 21:48:26 2020 -0500
GEOMETRY-85: using list instead of array for EnclosingBall.getSupport(); using DoublePrecisionContext instead of margin for EnclosingBall.contains(); adding WelzelEncloser2D and WelzelEncloser3D convenience classes
---
.../commons/geometry/enclosing/EnclosingBall.java | 56 +++++---
.../commons/geometry/enclosing/WelzlEncloser.java | 27 ++--
.../euclidean/threed/SphereGenerator.java | 41 +++---
.../euclidean/threed/WelzlEncloser3D.java | 35 +++++
.../enclosing/euclidean/twod/DiskGenerator.java | 13 +-
.../enclosing/euclidean/twod/WelzlEncloser2D.java | 35 +++++
.../geometry/enclosing/EnclosingBallTest.java | 153 +++++++++++++++++++++
.../euclidean/threed/SphereGeneratorTest.java | 115 +++++++++++-----
.../threed}/WelzlEncloser3DTest.java | 68 ++++-----
.../euclidean/twod/DiskGeneratorTest.java | 79 ++++++++---
.../{ => euclidean/twod}/WelzlEncloser2DTest.java | 74 +++++-----
11 files changed, 515 insertions(+), 181 deletions(-)
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/EnclosingBall.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/EnclosingBall.java
index 9ea604d..0a02dc7 100644
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/EnclosingBall.java
+++ b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/EnclosingBall.java
@@ -16,7 +16,13 @@
*/
package org.apache.commons.geometry.enclosing;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
import org.apache.commons.geometry.core.Point;
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
/** This class represents a ball enclosing some points.
* @param <P> Point type.
@@ -31,18 +37,18 @@ public class EnclosingBall<P extends Point<P>> {
private final double radius;
/** Support points used to define the ball. */
- private final P[] support;
+ private final List<P> support;
- /** Simple constructor.
+ /** Construct an enclosing ball defined by a collection of support points. Callers are responsible
+ * for ensuring that the given points lie inside the ball. No validation is performed.
* @param center center of the ball
* @param radius radius of the ball
* @param support support points used to define the ball
*/
- @SafeVarargs
- public EnclosingBall(final P center, final double radius, final P... support) {
+ public EnclosingBall(final P center, final double radius, final Collection<P> support) {
this.center = center;
this.radius = radius;
- this.support = support.clone();
+ this.support = Collections.unmodifiableList(new ArrayList<>(support));
}
/** Get the center of the ball.
@@ -62,33 +68,51 @@ public class EnclosingBall<P extends Point<P>> {
/** Get the support points used to define the ball.
* @return support points used to define the ball
*/
- public P[] getSupport() {
- return support.clone();
+ public List<P> getSupport() {
+ return support;
}
/** 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;
+ return support.size();
}
- /** Check if a point is within the ball or at boundary.
+ /** Check if a point is within the ball or on the boundary. True is returned if the
+ * distance from the center of the ball to the given point is strictly less than
+ * or equal to the ball radius.
* @param point point to test
- * @return true if the point is within the ball or at boundary
+ * @return true if the point is within the ball or on the boundary
*/
public boolean contains(final P point) {
return point.distance(center) <= radius;
}
- /** Check if a point is within an enlarged ball or at boundary.
+ /** Check if a point is within the ball or on the boundary, using the given precision
+ * context for floating point comparison. True is returned if the distance from the
+ * center of the ball to the given point is less than or equal to the ball radius
+ * as evaluated by the precision context.
* @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
+ * @param precision precision context to use for floating point comparisons
+ * @return true if the point is within the ball or on the boundary as evaluated by
+ * the precision context
*/
- public boolean contains(final P point, final double margin) {
- return point.distance(center) <= radius + margin;
+ public boolean contains(final P point, final DoublePrecisionContext precision) {
+ return precision.lte(point.distance(center), radius);
}
+ /** {@inheritDoc} */
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ sb.append(getClass().getSimpleName())
+ .append("[center= ")
+ .append(getCenter())
+ .append(", radius= ")
+ .append(getRadius())
+ .append(']');
+
+ return sb.toString();
+ }
}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/WelzlEncloser.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/WelzlEncloser.java
index 4158245..e21b862 100755
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/WelzlEncloser.java
+++ b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/WelzlEncloser.java
@@ -23,7 +23,7 @@ import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.internal.GeometryInternalError;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
-/** Class implementing Emo Welzl algorithm to find the smallest enclosing ball in linear time.
+/** Class implementing Emo Welzl's 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
@@ -43,16 +43,16 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
/** Precision context used to compare floating point numbers. */
private final DoublePrecisionContext precision;
- /** Generator for balls on support. */
+ /** Object used to generate balls from support points. */
private final SupportBallGenerator<P> generator;
/** Simple constructor.
- * @param precision precision context used to compare floating point values
* @param generator generator for balls on support
+ * @param precision precision context used to compare floating point values
*/
- public WelzlEncloser(final DoublePrecisionContext precision, final SupportBallGenerator<P> generator) {
- this.precision = precision;
+ public WelzlEncloser(final SupportBallGenerator<P> generator, final DoublePrecisionContext precision) {
this.generator = generator;
+ this.precision = precision;
}
/** {@inheritDoc} */
@@ -66,7 +66,6 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<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.
@@ -88,7 +87,7 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
// select the point farthest to current ball
final P farthest = selectFarthest(points, ball);
- if (ball.contains(farthest, precision.getMaxZero())) {
+ if (ball.contains(farthest, precision)) {
// we have found a ball containing all points
return ball;
}
@@ -98,7 +97,7 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
support.add(farthest);
EnclosingBall<P> savedBall = ball;
ball = moveToFrontBall(extreme, extreme.size(), support);
- if (this.precision.lt(ball.getRadius(), savedBall.getRadius())) {
+ if (precision.lt(ball.getRadius(), savedBall.getRadius())) {
// this should never happen
throw new GeometryInternalError();
}
@@ -109,8 +108,6 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
// prune the least interesting points
extreme.subList(ball.getSupportSize(), extreme.size()).clear();
-
-
}
}
@@ -122,7 +119,6 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
*/
private EnclosingBall<P> moveToFrontBall(final List<P> extreme, final int nbExtreme,
final List<P> support) {
-
// create a new ball on the prescribed support
EnclosingBall<P> ball = generator.ballOnSupport(support);
@@ -130,7 +126,7 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
for (int i = 0; i < nbExtreme; ++i) {
final P pi = extreme.get(i);
- if (!ball.contains(pi, precision.getMaxZero())) {
+ if (!ball.contains(pi, precision)) {
// we have found an outside point,
// enlarge the ball by adding it to the support
@@ -144,14 +140,11 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
extreme.set(j, extreme.get(j - 1));
}
extreme.set(0, pi);
-
}
}
-
}
return ball;
-
}
/** Select the point farthest to the current ball.
@@ -159,7 +152,7 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
* @param ball current ball
* @return farthest point
*/
- public P selectFarthest(final Iterable<P> points, final EnclosingBall<P> ball) {
+ private P selectFarthest(final Iterable<P> points, final EnclosingBall<P> ball) {
final P center = ball.getCenter();
P farthest = null;
@@ -174,7 +167,5 @@ public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
}
return farthest;
-
}
-
}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGenerator.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGenerator.java
index f910b50..698c46b 100644
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGenerator.java
+++ b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGenerator.java
@@ -17,10 +17,10 @@
package org.apache.commons.geometry.enclosing.euclidean.threed;
import java.util.Arrays;
+import java.util.Collections;
import java.util.List;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
-import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.enclosing.EnclosingBall;
import org.apache.commons.geometry.enclosing.SupportBallGenerator;
import org.apache.commons.geometry.enclosing.euclidean.twod.DiskGenerator;
@@ -29,34 +29,38 @@ import org.apache.commons.geometry.euclidean.threed.Vector3D;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.numbers.fraction.BigFraction;
-/** Class generating an enclosing ball from its support points.
+/** Class generating a sphere from its support points.
*/
public class SphereGenerator implements SupportBallGenerator<Vector3D> {
- /** Base epsilon value. */
- private static final double BASE_EPS = 1e-10;
+
+ /** Precision context used to compare floating point numbers. */
+ private final DoublePrecisionContext precision;
+
+ /** Construct a new instance with the given precision context.
+ * @param precision precision context used to compare floating point numbers
+ */
+ public SphereGenerator(final DoublePrecisionContext precision) {
+ this.precision = precision;
+ }
/** {@inheritDoc} */
@Override
public EnclosingBall<Vector3D> ballOnSupport(final List<Vector3D> support) {
if (support.isEmpty()) {
- return new EnclosingBall<>(Vector3D.ZERO, Double.NEGATIVE_INFINITY);
+ return new EnclosingBall<>(Vector3D.ZERO, Double.NEGATIVE_INFINITY, Collections.emptyList());
} else {
final Vector3D vA = support.get(0);
if (support.size() < 2) {
- return new EnclosingBall<>(vA, 0, vA);
+ return new EnclosingBall<>(vA, 0, Arrays.asList(vA));
} else {
final Vector3D vB = support.get(1);
if (support.size() < 3) {
return new EnclosingBall<>(Vector3D.linearCombination(0.5, vA, 0.5, vB),
0.5 * vA.distance(vB),
- vA, vB);
+ Arrays.asList(vA, vB));
} else {
final Vector3D vC = support.get(2);
if (support.size() < 4) {
-
- // delegate to 2D disk generator
- final DoublePrecisionContext precision =
- new EpsilonDoublePrecisionContext(BASE_EPS * (norm1(vA) + norm1(vB) + norm1(vC)));
final Plane p = Plane.fromPoints(vA, vB, vC, precision);
final EnclosingBall<Vector2D> disk =
new DiskGenerator().ballOnSupport(Arrays.asList(p.toSubspace(vA),
@@ -65,7 +69,8 @@ public class SphereGenerator implements SupportBallGenerator<Vector3D> {
// convert back to 3D
return new EnclosingBall<>(p.toSpace(disk.getCenter()),
- disk.getRadius(), vA, vB, vC);
+ disk.getRadius(),
+ Arrays.asList(vA, vB, vC));
} else {
final Vector3D vD = support.get(3);
@@ -125,7 +130,7 @@ public class SphereGenerator implements SupportBallGenerator<Vector3D> {
centerY.doubleValue(),
centerZ.doubleValue()),
Math.sqrt(r2.doubleValue()),
- vA, vB, vC, vD);
+ Arrays.asList(vA, vB, vC, vD));
}
}
}
@@ -152,14 +157,4 @@ public class SphereGenerator implements SupportBallGenerator<Vector3D> {
add(c2[3].multiply(c3[1]).multiply(c1[0].subtract(c1[2]))).
add(c2[3].multiply(c3[2]).multiply(c1[1].subtract(c1[0])));
}
-
- /** Compute the L<sub>1</sub> vector norm for the given set of coordinates.
- * This is defined as the sum of the absolute values of all components.
- * @param coord set of coordinates
- * @return L<sub>1</sub> vector norm for the given set of coordinates
- * @see <a href="http://mathworld.wolfram.com/L1-Norm.html">L1 Norm</a>
- */
- private double norm1(final Vector3D coord) {
- return Math.abs(coord.getX()) + Math.abs(coord.getY()) + Math.abs(coord.getZ());
- }
}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3D.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3D.java
new file mode 100644
index 0000000..d32ca82
--- /dev/null
+++ b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3D.java
@@ -0,0 +1,35 @@
+/*
+ * 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.geometry.enclosing.euclidean.threed;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.enclosing.WelzlEncloser;
+import org.apache.commons.geometry.euclidean.threed.Vector3D;
+
+/** Extension of the {@link WelzlEncloser} class for Euclidean 3D space. This is
+ * primarily a convenience class to simplify instantiation.
+ */
+public class WelzlEncloser3D extends WelzlEncloser<Vector3D> {
+
+ /** Construct a new instance with the given precision context. A new {@link SphereGenerator}
+ * instance is used as the support ball generator.
+ * @param precision precision context to use for floating point comparisons
+ */
+ public WelzlEncloser3D(final DoublePrecisionContext precision) {
+ super(new SphereGenerator(precision), precision);
+ }
+}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGenerator.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGenerator.java
index f0b3b33..d6f50e6 100644
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGenerator.java
+++ b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGenerator.java
@@ -16,6 +16,8 @@
*/
package org.apache.commons.geometry.enclosing.euclidean.twod;
+import java.util.Arrays;
+import java.util.Collections;
import java.util.List;
import org.apache.commons.geometry.enclosing.EnclosingBall;
@@ -23,24 +25,25 @@ import org.apache.commons.geometry.enclosing.SupportBallGenerator;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.numbers.fraction.BigFraction;
-/** Class generating an enclosing ball from its support points.
+/** Class generating a disk from its support points.
*/
public class DiskGenerator implements SupportBallGenerator<Vector2D> {
+
/** {@inheritDoc} */
@Override
public EnclosingBall<Vector2D> ballOnSupport(final List<Vector2D> support) {
if (support.isEmpty()) {
- return new EnclosingBall<>(Vector2D.ZERO, Double.NEGATIVE_INFINITY);
+ return new EnclosingBall<>(Vector2D.ZERO, Double.NEGATIVE_INFINITY, Collections.emptyList());
} else {
final Vector2D vA = support.get(0);
if (support.size() < 2) {
- return new EnclosingBall<>(vA, 0, vA);
+ return new EnclosingBall<>(vA, 0, Arrays.asList(vA));
} else {
final Vector2D vB = support.get(1);
if (support.size() < 3) {
return new EnclosingBall<>(Vector2D.linearCombination(0.5, vA, 0.5, vB),
0.5 * vA.distance(vB),
- vA, vB);
+ Arrays.asList(vA, vB));
} else {
final Vector2D vC = support.get(2);
// a disk is 2D can be defined as:
@@ -86,7 +89,7 @@ public class DiskGenerator implements SupportBallGenerator<Vector2D> {
return new EnclosingBall<>(Vector2D.of(centerX.doubleValue(),
centerY.doubleValue()),
Math.sqrt(r2.doubleValue()),
- vA, vB, vC);
+ Arrays.asList(vA, vB, vC));
}
}
}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2D.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2D.java
new file mode 100644
index 0000000..6366e53
--- /dev/null
+++ b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2D.java
@@ -0,0 +1,35 @@
+/*
+ * 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.geometry.enclosing.euclidean.twod;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.enclosing.WelzlEncloser;
+import org.apache.commons.geometry.euclidean.twod.Vector2D;
+
+/** Extension of the {@link WelzlEncloser} class for Euclidean 2D space. This is
+ * primarily a convenience class to simplify instantiation.
+ */
+public class WelzlEncloser2D extends WelzlEncloser<Vector2D> {
+
+ /** Construct a new instance with the given precision context. A new {@link DiskGenerator}
+ * instance is used as the support ball generator.
+ * @param precision precision context to use for floating point comparisons.
+ */
+ public WelzlEncloser2D(final DoublePrecisionContext precision) {
+ super(new DiskGenerator(), precision);
+ }
+}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/EnclosingBallTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/EnclosingBallTest.java
new file mode 100644
index 0000000..8ec6fb5
--- /dev/null
+++ b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/EnclosingBallTest.java
@@ -0,0 +1,153 @@
+/*
+ * 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.geometry.enclosing;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.apache.commons.geometry.euclidean.twod.Vector2D;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class EnclosingBallTest {
+
+ private static final double TEST_EPS = 1e-10;
+
+ @Test
+ public void testProperties_emptySupport() {
+ // arrange
+ Vector2D center = Vector2D.of(1.2, 3.4);
+ double radius = 10;
+ List<Vector2D> support = new ArrayList<>();
+
+ // act
+ EnclosingBall<Vector2D> ball = new EnclosingBall<>(center, radius, support);
+
+ // assert
+ Assert.assertSame(center, ball.getCenter());
+ Assert.assertEquals(radius, ball.getRadius(), TEST_EPS);
+ Assert.assertEquals(0, ball.getSupportSize());
+
+ List<Vector2D> resultSupport = ball.getSupport();
+ Assert.assertEquals(0, resultSupport.size());
+ }
+
+ @Test
+ public void testProperties_nonEmptySupport() {
+ // arrange
+ Vector2D center = Vector2D.of(1.2, 3.4);
+ double radius = 10;
+ List<Vector2D> support = new ArrayList<>(Arrays.asList(
+ Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y));
+
+ // act
+ EnclosingBall<Vector2D> ball = new EnclosingBall<>(center, radius, support);
+
+ // assert
+ Assert.assertSame(center, ball.getCenter());
+ Assert.assertEquals(radius, ball.getRadius(), TEST_EPS);
+ Assert.assertEquals(3, ball.getSupportSize());
+
+ List<Vector2D> resultSupport = ball.getSupport();
+ Assert.assertNotSame(support, resultSupport);
+ Assert.assertEquals(support, resultSupport);
+ }
+
+ @Test(expected = UnsupportedOperationException.class)
+ public void testGetSupport_listCannotBeModified() {
+ // arrange
+ List<Vector2D> support = new ArrayList<>(Arrays.asList(Vector2D.ZERO));
+
+ EnclosingBall<Vector2D> ball = new EnclosingBall<>(Vector2D.of(1, 1), 4, support);
+
+ // act/assert
+ ball.getSupport().add(Vector2D.Unit.PLUS_X);
+ }
+
+ @Test
+ public void testContains_strict() {
+ // arrange
+ Vector2D center = Vector2D.of(1, 2);
+ double radius = 2;
+ EnclosingBall<Vector2D> ball = new EnclosingBall<>(center, radius, Collections.emptyList());
+
+ // act/assert
+ Assert.assertTrue(ball.contains(center));
+
+ Assert.assertTrue(ball.contains(Vector2D.of(2, 3)));
+ Assert.assertTrue(ball.contains(Vector2D.of(0, 1)));
+
+ Assert.assertTrue(ball.contains(Vector2D.of(0, 2)));
+ Assert.assertTrue(ball.contains(Vector2D.of(1, 4)));
+
+ Assert.assertFalse(ball.contains(Vector2D.of(3.00001, 2)));
+ Assert.assertFalse(ball.contains(Vector2D.of(1, -1e-12)));
+
+ Assert.assertFalse(ball.contains(Vector2D.of(1, 5)));
+ Assert.assertFalse(ball.contains(Vector2D.of(1, -1)));
+ Assert.assertFalse(ball.contains(Vector2D.of(-2, 2)));
+ Assert.assertFalse(ball.contains(Vector2D.of(4, 2)));
+ }
+
+ @Test
+ public void testContains_precision() {
+ // arrange
+ DoublePrecisionContext lowerPrecision = new EpsilonDoublePrecisionContext(1e-4);
+ DoublePrecisionContext higherPrecision = new EpsilonDoublePrecisionContext(1e-10);
+
+ Vector2D center = Vector2D.of(1, 2);
+ double radius = 2;
+ EnclosingBall<Vector2D> ball = new EnclosingBall<>(center, radius, Collections.emptyList());
+
+ // act/assert
+ Assert.assertTrue(ball.contains(center, higherPrecision));
+
+ Assert.assertTrue(ball.contains(Vector2D.of(2, 3), higherPrecision));
+ Assert.assertTrue(ball.contains(Vector2D.of(0, 1), higherPrecision));
+
+ Assert.assertTrue(ball.contains(Vector2D.of(0, 2), higherPrecision));
+ Assert.assertTrue(ball.contains(Vector2D.of(1, 4), higherPrecision));
+
+ Assert.assertFalse(ball.contains(Vector2D.of(3.00001, 2), higherPrecision));
+ Assert.assertTrue(ball.contains(Vector2D.of(1, -1e-12), higherPrecision));
+
+ Assert.assertTrue(ball.contains(Vector2D.of(3.00001, 2), lowerPrecision));
+ Assert.assertTrue(ball.contains(Vector2D.of(1, -1e-12), lowerPrecision));
+
+ Assert.assertFalse(ball.contains(Vector2D.of(1, 5), higherPrecision));
+ Assert.assertFalse(ball.contains(Vector2D.of(1, -1), higherPrecision));
+ Assert.assertFalse(ball.contains(Vector2D.of(-2, 2), higherPrecision));
+ Assert.assertFalse(ball.contains(Vector2D.of(4, 2), higherPrecision));
+ }
+
+ @Test
+ public void testToString() {
+ // arrange
+ EnclosingBall<Vector2D> ball = new EnclosingBall<>(Vector2D.ZERO, 1, Arrays.asList(Vector2D.Unit.PLUS_X));
+
+ // act
+ String str = ball.toString();
+
+ // assert
+ Assert.assertTrue(str.startsWith("EnclosingBall[center= (0"));
+ Assert.assertTrue(str.contains("radius= 1"));
+ }
+}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGeneratorTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGeneratorTest.java
index 11b8a31..2911284 100644
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGeneratorTest.java
+++ b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGeneratorTest.java
@@ -20,6 +20,8 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.enclosing.EnclosingBall;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
import org.apache.commons.rng.UniformRandomProvider;
@@ -30,66 +32,101 @@ import org.junit.Test;
public class SphereGeneratorTest {
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ private SphereGenerator generator = new SphereGenerator(TEST_PRECISION);
+
@Test
public void testSupport0Point() {
+ // arrange
List<Vector3D> support = Arrays.asList(new Vector3D[0]);
- EnclosingBall<Vector3D> sphere = new SphereGenerator().ballOnSupport(support);
+
+ // act
+ EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
+
+ // assert
Assert.assertTrue(sphere.getRadius() < 0);
Assert.assertEquals(0, sphere.getSupportSize());
- Assert.assertEquals(0, sphere.getSupport().length);
+ Assert.assertEquals(0, sphere.getSupport().size());
}
@Test
public void testSupport1Point() {
+ // arrange
+ DoublePrecisionContext lowPrecision = new EpsilonDoublePrecisionContext(0.5);
+ DoublePrecisionContext highPrecision = new EpsilonDoublePrecisionContext(0.001);
List<Vector3D> support = Arrays.asList(Vector3D.of(1, 2, 3));
- EnclosingBall<Vector3D> sphere = new SphereGenerator().ballOnSupport(support);
- Assert.assertEquals(0.0, sphere.getRadius(), 1.0e-10);
+
+ // act
+ EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
+
+ // assert
+ Assert.assertEquals(0.0, sphere.getRadius(), TEST_EPS);
+
Assert.assertTrue(sphere.contains(support.get(0)));
- Assert.assertTrue(sphere.contains(support.get(0), 0.5));
+ Assert.assertTrue(sphere.contains(support.get(0), lowPrecision));
Assert.assertFalse(sphere.contains(Vector3D.of(support.get(0).getX() + 0.1,
support.get(0).getY() + 0.1,
support.get(0).getZ() + 0.1),
- 0.001));
+ highPrecision));
Assert.assertTrue(sphere.contains(Vector3D.of(support.get(0).getX() + 0.1,
support.get(0).getY() + 0.1,
support.get(0).getZ() + 0.1),
- 0.5));
+ lowPrecision));
+
Assert.assertEquals(0, support.get(0).distance(sphere.getCenter()), 1.0e-10);
Assert.assertEquals(1, sphere.getSupportSize());
- Assert.assertTrue(support.get(0) == sphere.getSupport()[0]);
+ Assert.assertEquals(support.get(0), sphere.getSupport().get(0));
}
@Test
public void testSupport2Points() {
+ // arrange
List<Vector3D> support = Arrays.asList(Vector3D.of(1, 0, 0),
Vector3D.of(3, 0, 0));
- EnclosingBall<Vector3D> sphere = new SphereGenerator().ballOnSupport(support);
- Assert.assertEquals(1.0, sphere.getRadius(), 1.0e-10);
+
+ // act
+ EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
+
+ // assert
+ Assert.assertEquals(1.0, sphere.getRadius(), TEST_EPS);
+
int i = 0;
for (Vector3D v : support) {
Assert.assertTrue(sphere.contains(v));
- Assert.assertEquals(1.0, v.distance(sphere.getCenter()), 1.0e-10);
- Assert.assertTrue(v == sphere.getSupport()[i++]);
+ Assert.assertEquals(1.0, v.distance(sphere.getCenter()), TEST_EPS);
+ Assert.assertTrue(v == sphere.getSupport().get(i++));
}
+
Assert.assertTrue(sphere.contains(Vector3D.of(2, 0.9, 0)));
Assert.assertFalse(sphere.contains(Vector3D.ZERO));
- Assert.assertEquals(0.0, Vector3D.of(2, 0, 0).distance(sphere.getCenter()), 1.0e-10);
+ Assert.assertEquals(0.0, Vector3D.of(2, 0, 0).distance(sphere.getCenter()), TEST_EPS);
Assert.assertEquals(2, sphere.getSupportSize());
}
@Test
public void testSupport3Points() {
+ // arrange
List<Vector3D> support = Arrays.asList(Vector3D.of(1, 0, 0),
Vector3D.of(3, 0, 0),
Vector3D.of(2, 2, 0));
- EnclosingBall<Vector3D> sphere = new SphereGenerator().ballOnSupport(support);
- Assert.assertEquals(5.0 / 4.0, sphere.getRadius(), 1.0e-10);
+
+ // act
+ EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
+
+ // assert
+ Assert.assertEquals(5.0 / 4.0, sphere.getRadius(), TEST_EPS);
+
int i = 0;
for (Vector3D v : support) {
Assert.assertTrue(sphere.contains(v));
- Assert.assertEquals(5.0 / 4.0, v.distance(sphere.getCenter()), 1.0e-10);
- Assert.assertTrue(v == sphere.getSupport()[i++]);
+ Assert.assertEquals(5.0 / 4.0, v.distance(sphere.getCenter()), TEST_EPS);
+ Assert.assertEquals(v, sphere.getSupport().get(i++));
}
+
Assert.assertTrue(sphere.contains(Vector3D.of(2, 0.9, 0)));
Assert.assertFalse(sphere.contains(Vector3D.of(0.9, 0, 0)));
Assert.assertFalse(sphere.contains(Vector3D.of(3.1, 0, 0)));
@@ -97,24 +134,31 @@ public class SphereGeneratorTest {
Assert.assertFalse(sphere.contains(Vector3D.of(2.0, -0.501, 0)));
Assert.assertTrue(sphere.contains(Vector3D.of(2.0, 3.0 / 4.0, -1.249)));
Assert.assertFalse(sphere.contains(Vector3D.of(2.0, 3.0 / 4.0, -1.251)));
- Assert.assertEquals(0.0, Vector3D.of(2.0, 3.0 / 4.0, 0).distance(sphere.getCenter()), 1.0e-10);
+ Assert.assertEquals(0.0, Vector3D.of(2.0, 3.0 / 4.0, 0).distance(sphere.getCenter()), TEST_EPS);
Assert.assertEquals(3, sphere.getSupportSize());
}
@Test
public void testSupport4Points() {
+ // arrange
List<Vector3D> support = Arrays.asList(Vector3D.of(17, 14, 18),
Vector3D.of(11, 14, 22),
Vector3D.of(2, 22, 17),
Vector3D.of(22, 11, -10));
- EnclosingBall<Vector3D> sphere = new SphereGenerator().ballOnSupport(support);
- Assert.assertEquals(25.0, sphere.getRadius(), 1.0e-10);
+
+ // act
+ EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
+
+ // assert
+ Assert.assertEquals(25.0, sphere.getRadius(), TEST_EPS);
+
int i = 0;
for (Vector3D v : support) {
Assert.assertTrue(sphere.contains(v));
Assert.assertEquals(25.0, v.distance(sphere.getCenter()), 1.0e-10);
- Assert.assertTrue(v == sphere.getSupport()[i++]);
+ Assert.assertEquals(v, sphere.getSupport().get(i++));
}
+
Assert.assertTrue(sphere.contains(Vector3D.of(-22.999, 2, 2)));
Assert.assertFalse(sphere.contains(Vector3D.of(-23.001, 2, 2)));
Assert.assertTrue(sphere.contains(Vector3D.of(26.999, 2, 2)));
@@ -127,12 +171,13 @@ public class SphereGeneratorTest {
Assert.assertFalse(sphere.contains(Vector3D.of(2, 2, -23.001)));
Assert.assertTrue(sphere.contains(Vector3D.of(2, 2, 26.999)));
Assert.assertFalse(sphere.contains(Vector3D.of(2, 2, 27.001)));
- Assert.assertEquals(0.0, Vector3D.of(2.0, 2.0, 2.0).distance(sphere.getCenter()), 1.0e-10);
+ Assert.assertEquals(0.0, Vector3D.of(2.0, 2.0, 2.0).distance(sphere.getCenter()), TEST_EPS);
Assert.assertEquals(4, sphere.getSupportSize());
}
@Test
public void testRandom() {
+ // arrange
final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A,
0xd015982e9f31ee04L);
final UnitSphereSampler sr = new UnitSphereSampler(3, random);
@@ -144,7 +189,11 @@ public class SphereGeneratorTest {
for (int j = 0; j < 5; ++j) {
support.add(Vector3D.linearCombination(1.0, refCenter, refRadius, Vector3D.of(sr.nextVector())));
}
- EnclosingBall<Vector3D> sphere = new SphereGenerator().ballOnSupport(support);
+
+ // act
+ EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
+
+ // assert
Assert.assertEquals(0.0, refCenter.distance(sphere.getCenter()), 4e-7 * refRadius);
Assert.assertEquals(refRadius, sphere.getRadius(), 1e-7 * refRadius);
}
@@ -152,6 +201,7 @@ public class SphereGeneratorTest {
@Test
public void testDegeneratedCase() {
+ // --- arrange
final List<Vector3D> support =
Arrays.asList(Vector3D.of(Math.scalb(-8039905610797991.0, -50), // -7.140870659936730
Math.scalb(-4663475464714142.0, -48), // -16.567993074240455
@@ -165,21 +215,24 @@ public class SphereGeneratorTest {
Vector3D.of(Math.scalb(-8038007803611611.0, -50), // -7.139185068549035
Math.scalb(-4664291215918380.0, -48), // -16.570891204702250
Math.scalb(6595270610894208.0, -49))); // 11.715554057357394
- EnclosingBall<Vector3D> sphere = new SphereGenerator().ballOnSupport(support);
+ // --- act
+ EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
+
+ // --- assert
// the following values have been computed using Emacs calc with exact arithmetic from the
// rational representation corresponding to the scalb calls (i.e. -8039905610797991/2^50, ...)
// The results were converted to decimal representation rounded to 1.0e-30 when writing the reference
// values in this test
- Assert.assertEquals(0.003616820213530053297575846168, sphere.getRadius(), 1.0e-20);
- Assert.assertEquals(-7.139325643360503322823511839511, sphere.getCenter().getX(), 1.0e-20);
- Assert.assertEquals(-16.571096474251747245361467833760, sphere.getCenter().getY(), 1.0e-20);
- Assert.assertEquals(11.711945804096960876521111630800, sphere.getCenter().getZ(), 1.0e-20);
+ final double eps = 1e-20;
+ Assert.assertEquals(0.003616820213530053297575846168, sphere.getRadius(), eps);
+ Assert.assertEquals(-7.139325643360503322823511839511, sphere.getCenter().getX(), eps);
+ Assert.assertEquals(-16.571096474251747245361467833760, sphere.getCenter().getY(), eps);
+ Assert.assertEquals(11.711945804096960876521111630800, sphere.getCenter().getZ(), eps);
+ final DoublePrecisionContext supportPrecision = new EpsilonDoublePrecisionContext(1e-14);
for (Vector3D v : support) {
- Assert.assertTrue(sphere.contains(v, 1.0e-14));
+ Assert.assertTrue(sphere.contains(v, supportPrecision));
}
-
}
-
}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/WelzlEncloser3DTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3DTest.java
similarity index 83%
rename from commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/WelzlEncloser3DTest.java
rename to commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3DTest.java
index 12246ec..c260eca 100644
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/WelzlEncloser3DTest.java
+++ b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3DTest.java
@@ -14,7 +14,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-package org.apache.commons.geometry.enclosing;
+package org.apache.commons.geometry.enclosing.euclidean.threed;
import java.util.ArrayList;
import java.util.Arrays;
@@ -22,7 +22,7 @@ import java.util.List;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
-import org.apache.commons.geometry.enclosing.euclidean.threed.SphereGenerator;
+import org.apache.commons.geometry.enclosing.EnclosingBall;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.sampling.UnitSphereSampler;
@@ -30,7 +30,6 @@ import org.apache.commons.rng.simple.RandomSource;
import org.junit.Assert;
import org.junit.Test;
-
public class WelzlEncloser3DTest {
private static final double TEST_EPS = 1e-10;
@@ -38,26 +37,31 @@ public class WelzlEncloser3DTest {
private static final DoublePrecisionContext TEST_PRECISION =
new EpsilonDoublePrecisionContext(TEST_EPS);
+ private WelzlEncloser3D encloser = new WelzlEncloser3D(TEST_PRECISION);
+
@Test
public void testNullList() {
- SphereGenerator generator = new SphereGenerator();
- WelzlEncloser<Vector3D> encloser =
- new WelzlEncloser<>(TEST_PRECISION, generator);
+ // act
EnclosingBall<Vector3D> ball = encloser.enclose(null);
+
+ // assert
Assert.assertTrue(ball.getRadius() < 0);
}
@Test
public void testNoPoints() {
- SphereGenerator generator = new SphereGenerator();
- WelzlEncloser<Vector3D> encloser =
- new WelzlEncloser<>(TEST_PRECISION, generator);
+ // act
EnclosingBall<Vector3D> ball = encloser.enclose(new ArrayList<Vector3D>());
+
+ // assert
Assert.assertTrue(ball.getRadius() < 0);
+ Assert.assertEquals(0, ball.getSupportSize());
+ Assert.assertEquals(0, ball.getSupport().size());
}
@Test
public void testReducingBall() {
+ // arrange
List<Vector3D> list =
Arrays.asList(Vector3D.of(-7.140397329568118, -16.571661242582177, 11.714458961735405),
Vector3D.of(-7.137986707455888, -16.570767323375720, 11.708602108715928),
@@ -70,14 +74,17 @@ public class WelzlEncloser3DTest {
Vector3D.of(-7.140453077221105, -16.570212820780647, 11.708624578004980),
Vector3D.of(-7.140322188726825, -16.574152894557717, 11.710305611121410),
Vector3D.of(-7.141116131477088, -16.574061164624560, 11.712938509321699));
- WelzlEncloser<Vector3D> encloser =
- new WelzlEncloser<>(TEST_PRECISION, new SphereGenerator());
+
+ // act
EnclosingBall<Vector3D> ball = encloser.enclose(list);
+
+ // assert
Assert.assertTrue(ball.getRadius() > 0);
}
@Test
public void testInfiniteLoop() {
+ // arrange
// this test used to generate an infinite loop
List<Vector3D> list =
Arrays.asList(Vector3D.of(-0.89227075512164380, -2.89317694645713900, 14.84572323743355500),
@@ -99,14 +106,16 @@ public class WelzlEncloser3DTest {
Vector3D.of(-1.53348892951571640, -3.66688919703524900, 14.73095600812074200),
Vector3D.of(-0.98034899533935820, -3.34004481162763960, 13.03245014017556800));
- WelzlEncloser<Vector3D> encloser =
- new WelzlEncloser<>(TEST_PRECISION, new SphereGenerator());
+ // act
EnclosingBall<Vector3D> ball = encloser.enclose(list);
+
+ // assert
Assert.assertTrue(ball.getRadius() > 0);
}
@Test
public void testLargeSamples() {
+ // arrange
final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A,
0x35ddecfc78131e1dL);
final UnitSphereSampler sr = new UnitSphereSampler(3, random);
@@ -118,15 +127,16 @@ public class WelzlEncloser3DTest {
Vector3D refCenter = Vector3D.linearCombination(d, Vector3D.of(sr.nextVector()));
// set up a large sample inside the reference sphere
int nbPoints = random.nextInt(1000);
+
List<Vector3D> points = new ArrayList<>();
for (int i = 0; i < nbPoints; ++i) {
double r = refRadius * random.nextDouble();
points.add(Vector3D.linearCombination(1.0, refCenter, r, Vector3D.of(sr.nextVector())));
}
+ // act/assert
// test we find a sphere at most as large as the one used for random drawings
checkSphere(points, refRadius);
-
}
}
@@ -146,45 +156,35 @@ public class WelzlEncloser3DTest {
reducedSupport.add(s);
}
}
- EnclosingBall<Vector3D> reducedSphere =
- new SphereGenerator().ballOnSupport(reducedSupport);
+ EnclosingBall<Vector3D> reducedSphere = new SphereGenerator(TEST_PRECISION)
+ .ballOnSupport(reducedSupport);
boolean foundOutside = false;
for (int j = 0; j < points.size() && !foundOutside; ++j) {
- if (!reducedSphere.contains(points.get(j), 1.0e-10)) {
+ if (!reducedSphere.contains(points.get(j), TEST_PRECISION)) {
foundOutside = true;
}
}
Assert.assertTrue(foundOutside);
}
-
}
private EnclosingBall<Vector3D> checkSphere(List<Vector3D> points) {
- WelzlEncloser<Vector3D> encloser =
- new WelzlEncloser<>(TEST_PRECISION, new SphereGenerator());
EnclosingBall<Vector3D> sphere = encloser.enclose(points);
// all points are enclosed
for (Vector3D v : points) {
- Assert.assertTrue(sphere.contains(v, 1.0e-10));
+ Assert.assertTrue(sphere.contains(v, TEST_PRECISION));
}
- for (Vector3D v : points) {
- boolean inSupport = false;
- for (Vector3D s : sphere.getSupport()) {
- if (v == s) {
- inSupport = true;
- }
- }
- if (inSupport) {
- // points on the support should be outside of reduced ball
- Assert.assertFalse(sphere.contains(v, -0.001));
- }
+ // all support points are on the boundary
+ Vector3D center = sphere.getCenter();
+ double radius = sphere.getRadius();
+
+ for (Vector3D s : sphere.getSupport()) {
+ Assert.assertTrue(TEST_PRECISION.eqZero(center.distance(s) - radius));
}
return sphere;
-
}
-
}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGeneratorTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGeneratorTest.java
index 1ecd22a..99f1c86 100644
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGeneratorTest.java
+++ b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGeneratorTest.java
@@ -20,6 +20,8 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.enclosing.EnclosingBall;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.rng.UniformRandomProvider;
@@ -28,78 +30,108 @@ import org.apache.commons.rng.simple.RandomSource;
import org.junit.Assert;
import org.junit.Test;
-
public class DiskGeneratorTest {
+ private static final double TEST_EPS = 1e-10;
+
+ private DiskGenerator generator = new DiskGenerator();
+
@Test
public void testSupport0Point() {
+ // arrange
List<Vector2D> support = Arrays.asList(new Vector2D[0]);
- EnclosingBall<Vector2D> disk = new DiskGenerator().ballOnSupport(support);
+
+ // act
+ EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
+
+ // assert
Assert.assertTrue(disk.getRadius() < 0);
Assert.assertEquals(0, disk.getSupportSize());
- Assert.assertEquals(0, disk.getSupport().length);
+ Assert.assertEquals(0, disk.getSupport().size());
}
@Test
public void testSupport1Point() {
+ // arrange
+ DoublePrecisionContext lowPrecision = new EpsilonDoublePrecisionContext(0.5);
+ DoublePrecisionContext highPrecision = new EpsilonDoublePrecisionContext(0.001);
List<Vector2D> support = Arrays.asList(Vector2D.of(1, 2));
- EnclosingBall<Vector2D> disk = new DiskGenerator().ballOnSupport(support);
- Assert.assertEquals(0.0, disk.getRadius(), 1.0e-10);
+
+ // act
+ EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
+
+ // assert
+ Assert.assertEquals(0.0, disk.getRadius(), TEST_EPS);
Assert.assertTrue(disk.contains(support.get(0)));
- Assert.assertTrue(disk.contains(support.get(0), 0.5));
+ Assert.assertTrue(disk.contains(support.get(0), lowPrecision));
Assert.assertFalse(disk.contains(Vector2D.of(support.get(0).getX() + 0.1,
support.get(0).getY() - 0.1),
- 0.001));
+ highPrecision));
Assert.assertTrue(disk.contains(Vector2D.of(support.get(0).getX() + 0.1,
support.get(0).getY() - 0.1),
- 0.5));
- Assert.assertEquals(0, support.get(0).distance(disk.getCenter()), 1.0e-10);
+ lowPrecision));
+ Assert.assertEquals(0, support.get(0).distance(disk.getCenter()), TEST_EPS);
Assert.assertEquals(1, disk.getSupportSize());
- Assert.assertTrue(support.get(0) == disk.getSupport()[0]);
+ Assert.assertEquals(support.get(0), disk.getSupport().get(0));
}
@Test
public void testSupport2Points() {
+ // arrange
List<Vector2D> support = Arrays.asList(Vector2D.of(1, 0),
Vector2D.of(3, 0));
- EnclosingBall<Vector2D> disk = new DiskGenerator().ballOnSupport(support);
- Assert.assertEquals(1.0, disk.getRadius(), 1.0e-10);
+
+ // act
+ EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
+
+ // assert
+ Assert.assertEquals(1.0, disk.getRadius(), TEST_EPS);
+
int i = 0;
for (Vector2D v : support) {
Assert.assertTrue(disk.contains(v));
- Assert.assertEquals(1.0, v.distance(disk.getCenter()), 1.0e-10);
- Assert.assertTrue(v == disk.getSupport()[i++]);
+ Assert.assertEquals(1.0, v.distance(disk.getCenter()), TEST_EPS);
+ Assert.assertEquals(v, disk.getSupport().get(i++));
}
+
Assert.assertTrue(disk.contains(Vector2D.of(2, 0.9)));
Assert.assertFalse(disk.contains(Vector2D.ZERO));
- Assert.assertEquals(0.0, Vector2D.of(2, 0).distance(disk.getCenter()), 1.0e-10);
+ Assert.assertEquals(0.0, Vector2D.of(2, 0).distance(disk.getCenter()), TEST_EPS);
Assert.assertEquals(2, disk.getSupportSize());
}
@Test
public void testSupport3Points() {
+ // arrange
List<Vector2D> support = Arrays.asList(Vector2D.of(1, 0),
Vector2D.of(3, 0),
Vector2D.of(2, 2));
- EnclosingBall<Vector2D> disk = new DiskGenerator().ballOnSupport(support);
- Assert.assertEquals(5.0 / 4.0, disk.getRadius(), 1.0e-10);
+
+ // act
+ EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
+
+ // assert
+ Assert.assertEquals(5.0 / 4.0, disk.getRadius(), TEST_EPS);
+
int i = 0;
for (Vector2D v : support) {
Assert.assertTrue(disk.contains(v));
- Assert.assertEquals(5.0 / 4.0, v.distance(disk.getCenter()), 1.0e-10);
- Assert.assertTrue(v == disk.getSupport()[i++]);
+ Assert.assertEquals(5.0 / 4.0, v.distance(disk.getCenter()), TEST_EPS);
+ Assert.assertEquals(v, disk.getSupport().get(i++));
}
+
Assert.assertTrue(disk.contains(Vector2D.of(2, 0.9)));
Assert.assertFalse(disk.contains(Vector2D.of(0.9, 0)));
Assert.assertFalse(disk.contains(Vector2D.of(3.1, 0)));
Assert.assertTrue(disk.contains(Vector2D.of(2.0, -0.499)));
Assert.assertFalse(disk.contains(Vector2D.of(2.0, -0.501)));
- Assert.assertEquals(0.0, Vector2D.of(2.0, 3.0 / 4.0).distance(disk.getCenter()), 1.0e-10);
+ Assert.assertEquals(0.0, Vector2D.of(2.0, 3.0 / 4.0).distance(disk.getCenter()), TEST_EPS);
Assert.assertEquals(3, disk.getSupportSize());
}
@Test
public void testRandom() {
+ // arrange
final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A,
0x12faa818373ffe90L);
final UnitSphereSampler sr = new UnitSphereSampler(2, random);
@@ -111,10 +143,13 @@ public class DiskGeneratorTest {
for (int j = 0; j < 3; ++j) {
support.add(Vector2D.linearCombination(1.0, refCenter, refRadius, Vector2D.of(sr.nextVector())));
}
- EnclosingBall<Vector2D> disk = new DiskGenerator().ballOnSupport(support);
+
+ // act
+ EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
+
+ // assert
Assert.assertEquals(0.0, refCenter.distance(disk.getCenter()), 3e-9 * refRadius);
Assert.assertEquals(refRadius, disk.getRadius(), 7e-10 * refRadius);
}
-
}
}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/WelzlEncloser2DTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
similarity index 81%
rename from commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/WelzlEncloser2DTest.java
rename to commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
index f15b02b..11356fe 100755
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/WelzlEncloser2DTest.java
+++ b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
@@ -14,7 +14,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-package org.apache.commons.geometry.enclosing;
+package org.apache.commons.geometry.enclosing.euclidean.twod;
import java.util.ArrayList;
import java.util.Arrays;
@@ -22,14 +22,13 @@ import java.util.List;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
-import org.apache.commons.geometry.enclosing.euclidean.twod.DiskGenerator;
+import org.apache.commons.geometry.enclosing.EnclosingBall;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.simple.RandomSource;
import org.junit.Assert;
import org.junit.Test;
-
public class WelzlEncloser2DTest {
private static final double TEST_EPS = 1e-10;
@@ -37,57 +36,74 @@ public class WelzlEncloser2DTest {
private static final DoublePrecisionContext TEST_PRECISION =
new EpsilonDoublePrecisionContext(TEST_EPS);
+ private WelzlEncloser2D encloser = new WelzlEncloser2D(TEST_PRECISION);
+
@Test
public void testNullList() {
- DiskGenerator generator = new DiskGenerator();
- WelzlEncloser<Vector2D> encloser =
- new WelzlEncloser<>(TEST_PRECISION, generator);
+ // act
EnclosingBall<Vector2D> ball = encloser.enclose(null);
+
+ // assert
Assert.assertTrue(ball.getRadius() < 0);
+ Assert.assertEquals(0, ball.getSupportSize());
+ Assert.assertEquals(0, ball.getSupport().size());
}
@Test
public void testNoPoints() {
- DiskGenerator generator = new DiskGenerator();
- WelzlEncloser<Vector2D> encloser =
- new WelzlEncloser<>(TEST_PRECISION, generator);
+ // act
EnclosingBall<Vector2D> ball = encloser.enclose(new ArrayList<Vector2D>());
+
+ // assert
Assert.assertTrue(ball.getRadius() < 0);
}
@Test
public void testRegularPoints() {
+ // arrange
List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28, 8, 54, 11, 15);
+
+ // act/assert
checkDisk(list, Arrays.asList(list.get(2), list.get(3), list.get(4)));
}
@Test
public void testSolutionOnDiameter() {
+ // arrange
List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28, 8, 54);
+
+ // act/assert
checkDisk(list, Arrays.asList(list.get(2), list.get(3)));
}
@Test
public void testReducingBall1() {
+ // arrange
List<Vector2D> list = buildList(0.05380958511396061, 0.57332359658700000,
0.99348810731127870, 0.02056421361521466,
0.01203950647796437, 0.99779675042261860,
0.00810189987706078, 0.00589246003827815,
0.00465180821202149, 0.99219972923046940);
+
+ // act/assert
checkDisk(list, Arrays.asList(list.get(1), list.get(3), list.get(4)));
}
@Test
public void testReducingBall2() {
+ // arrange
List<Vector2D> list = buildList(0.016930586154703, 0.333955448537779,
0.987189104892331, 0.969778855274507,
0.983696889599935, 0.012904580013266,
0.013114499572905, 0.034740156356895);
+
+ // act/assert
checkDisk(list, Arrays.asList(list.get(1), list.get(2), list.get(3)));
}
@Test
public void testLargeSamples() {
+ // arrange
UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A, 0xa2a63cad12c01fb2L);
for (int k = 0; k < 100; ++k) {
int nbPoints = random.nextInt(10000);
@@ -97,12 +113,15 @@ public class WelzlEncloser2DTest {
double y = random.nextDouble();
points.add(Vector2D.of(x, y));
}
+
+ // act/assert
checkDisk(points);
}
}
@Test
public void testEnclosingWithPrecision() {
+ // arrange
final List<Vector2D> points = Arrays.asList(
Vector2D.of(271.59, 57.282),
Vector2D.of(269.145, 57.063),
@@ -112,8 +131,10 @@ public class WelzlEncloser2DTest {
);
double precision = 1;
DoublePrecisionContext precisionContext = new EpsilonDoublePrecisionContext(precision);
- WelzlEncloser<Vector2D> encloser = new WelzlEncloser<>(precisionContext, new DiskGenerator());
- encloser.enclose(points);
+ WelzlEncloser2D customPrecisionEncloser = new WelzlEncloser2D(precisionContext);
+
+ // act
+ customPrecisionEncloser.enclose(points);
}
private List<Vector2D> buildList(final double... coordinates) {
@@ -129,8 +150,7 @@ public class WelzlEncloser2DTest {
EnclosingBall<Vector2D> disk = checkDisk(points);
// compare computed disk with expected disk
- DiskGenerator generator = new DiskGenerator();
- EnclosingBall<Vector2D> expected = generator.ballOnSupport(refSupport);
+ EnclosingBall<Vector2D> expected = new DiskGenerator().ballOnSupport(refSupport);
Assert.assertEquals(refSupport.size(), disk.getSupportSize());
Assert.assertEquals(expected.getRadius(), disk.getRadius(), 1.0e-10);
Assert.assertEquals(expected.getCenter().getX(), disk.getCenter().getX(), 1.0e-10);
@@ -155,44 +175,34 @@ public class WelzlEncloser2DTest {
reducedSupport.add(s);
}
}
- EnclosingBall<Vector2D> reducedDisk = generator.ballOnSupport(reducedSupport);
+ EnclosingBall<Vector2D> reducedDisk = new DiskGenerator().ballOnSupport(reducedSupport);
boolean foundOutside = false;
for (int j = 0; j < points.size() && !foundOutside; ++j) {
- if (!reducedDisk.contains(points.get(j), 1.0e-10)) {
+ if (!reducedDisk.contains(points.get(j), TEST_PRECISION)) {
foundOutside = true;
}
}
Assert.assertTrue(foundOutside);
}
-
}
private EnclosingBall<Vector2D> checkDisk(List<Vector2D> points) {
- WelzlEncloser<Vector2D> encloser =
- new WelzlEncloser<>(TEST_PRECISION, new DiskGenerator());
EnclosingBall<Vector2D> disk = encloser.enclose(points);
// all points are enclosed
for (Vector2D v : points) {
- Assert.assertTrue(disk.contains(v, 1.0e-10));
+ Assert.assertTrue(disk.contains(v, TEST_PRECISION));
}
- for (Vector2D v : points) {
- boolean inSupport = false;
- for (Vector2D s : disk.getSupport()) {
- if (v == s) {
- inSupport = true;
- }
- }
- if (inSupport) {
- // points on the support should be outside of reduced ball
- Assert.assertFalse(disk.contains(v, -0.001));
- }
+ // all support points are on the boundary
+ Vector2D center = disk.getCenter();
+ double radius = disk.getRadius();
+
+ for (Vector2D s : disk.getSupport()) {
+ Assert.assertTrue(TEST_PRECISION.eqZero(center.distance(s) - radius));
}
return disk;
-
}
-
}