Author: luc
Date: Thu Jan 30 16:31:08 2014
New Revision: 1562882
URL: http://svn.apache.org/r1562882
Log:
Partly fixed MATH-1096.
The 2D cases seem to work now, but there are still problems with the 3D
cases.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser2DTest.java
Modified:
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=1562882&r1=1562881&r2=1562882&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java
Thu Jan 30 16:31:08 2014
@@ -16,8 +16,6 @@
*/
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;
@@ -34,6 +32,6 @@ public interface Encloser<S extends Spac
* @param points points to enclose
* @return enclosing ball
*/
- EnclosingBall<S, P> enclose(List<P> points);
+ EnclosingBall<S, P> enclose(Iterable<P> points);
}
Modified:
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=1562882&r1=1562881&r2=1562882&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java
Thu Jan 30 16:31:08 2014
@@ -65,9 +65,9 @@ public class WelzlEncloser<S extends Spa
}
/** {@inheritDoc} */
- public EnclosingBall<S, P> enclose(final List<P> points) {
+ public EnclosingBall<S, P> enclose(final Iterable<P> points) {
- if (points == null || points.isEmpty()) {
+ if (points == null || !points.iterator().hasNext()) {
// return an empty ball
return generator.ballOnSupport(new ArrayList<P>());
}
@@ -81,14 +81,14 @@ public class WelzlEncloser<S extends Spa
* @param points points to be enclosed
* @return enclosing ball
*/
- private EnclosingBall<S, P> pivotingBall(final List<P> points) {
+ private EnclosingBall<S, P> pivotingBall(final Iterable<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);
+ extreme.add(points.iterator().next());
+ EnclosingBall<S, P> ball = moveToFrontBall(extreme, extreme.size(),
support);
while (true) {
@@ -103,7 +103,7 @@ public class WelzlEncloser<S extends Spa
support.clear();
support.add(farthest);
EnclosingBall<S, P> savedBall = ball;
- ball = moveToFrontBall(extreme, support);
+ ball = moveToFrontBall(extreme, extreme.size(), support);
if (ball.getRadius() < savedBall.getRadius()) {
// TODO: fix this, it should never happen but it does!
throw new MathInternalError();
@@ -122,28 +122,31 @@ public class WelzlEncloser<S extends Spa
/** Compute enclosing ball using Welzl's move to front heuristic.
* @param extreme subset of extreme points
+ * @param nbExtreme number of extreme points to consider
* @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) {
+ private EnclosingBall<S, P> moveToFrontBall(final List<P> extreme, final
int nbExtreme,
+ 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) {
+ for (int i = 0; i < nbExtreme; ++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);
+ ball = moveToFrontBall(extreme, i, support);
+ support.remove(support.size() - 1);
// it was an interesting point, move it to the front
// according to Welzl's heuristic
- for (int j = i; j > 1; --j) {
+ for (int j = i; j > 0; --j) {
extreme.set(j, extreme.get(j - 1));
}
extreme.set(0, pi);
@@ -162,7 +165,7 @@ public class WelzlEncloser<S extends Spa
* @param ball current ball
* @return farthest point
*/
- public P selectFarthest(final List<P> points, final EnclosingBall<S, P>
ball) {
+ public P selectFarthest(final Iterable<P> points, final EnclosingBall<S,
P> ball) {
final P center = ball.getCenter();
P farthest = null;
Modified:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser2DTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser2DTest.java?rev=1562882&r1=1562881&r2=1562882&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser2DTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser2DTest.java
Thu Jan 30 16:31:08 2014
@@ -26,7 +26,6 @@ import org.apache.commons.math3.geometry
import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.random.Well1024a;
import org.junit.Assert;
-import org.junit.Ignore;
import org.junit.Test;
@@ -63,8 +62,7 @@ public class WelzlEncloser2DTest {
}
@Test
- @Ignore // this test currently fails, it generate a ball that reduces at
one iteration
- public void testReducingBall() {
+ public void testReducingBall1() {
List<Vector2D> list = buildList(0.05380958511396061,
0.57332359658700000,
0.99348810731127870,
0.02056421361521466,
0.01203950647796437,
0.99779675042261860,
@@ -74,7 +72,15 @@ public class WelzlEncloser2DTest {
}
@Test
- @Ignore // this test currently fails, it generate balls that reduce at
some iterations
+ public void testReducingBall2() {
+ List<Vector2D> list = buildList(0.016930586154703, 0.333955448537779,
+ 0.987189104892331, 0.969778855274507,
+ 0.983696889599935, 0.012904580013266,
+ 0.013114499572905, 0.034740156356895);
+ checkDisk(list, Arrays.asList(list.get(1), list.get(2), list.get(3)));
+ }
+
+ @Test
public void testLargeSamples() {
RandomGenerator random = new Well1024a(0xa2a63cad12c01fb2l);
for (int k = 0; k < 100; ++k) {
