SphereGenerator implements SupportBallGenerator<Euclidean3D, Vector3D> { public EnclosingBall<Euclidean3D, Vector3D> ballOnSupport(final List<Vector3D> support) { if (support.size() < 1) { return new EnclosingBall<Euclidean3D, Vector3D>(Vector3D.ZERO, Double.NEGATIVE_INFINITY); } else { final Vector3D vA = support.get(0); if (support.size() < 2) { return new EnclosingBall<Euclidean3D, Vector3D>(vA, 0, vA); } else { final Vector3D vB = support.get(1); if (support.size() < 3) { return new EnclosingBall<Euclidean3D, Vector3D>(new Vector3D(0.5, vA, 0.5, vB), 0.5 * vA.distance(vB), vA, vB); } else { final Vector3D vC = support.get(2); if (support.size() < 4) { final Plane p = new Plane(vA, vB, vC, 1.0e-10 * (vA.getNorm1() + vB.getNorm1() + vC.getNorm1())); final EnclosingBall<Euclidean2D, Vector2D> disk = new DiskGenerator().ballOnSupport(Arrays.asList(p.toSubSpace(vA), p.toSubSpace(vB), p.toSubSpace(vC))); return new EnclosingBall<Euclidean3D, Vector3D>(p.toSpace(disk.getCenter()), disk.getRadius(), vA, vB, vC); } else { final Vector3D vD = support.get(3); final BigFraction[] c2 = new BigFraction[] { new BigFraction(vA.getX()), new BigFraction(vB.getX()), new BigFraction(vC.getX()), new BigFraction(vD.getX()) }; final BigFraction[] c3 = new BigFraction[] { new BigFraction(vA.getY()), new BigFraction(vB.getY()), new BigFraction(vC.getY()), new BigFraction(vD.getY()) }; final BigFraction[] c4 = new BigFraction[] { new BigFraction(vA.getZ()), new BigFraction(vB.getZ()), new BigFraction(vC.getZ()), new BigFraction(vD.getZ()) }; final BigFraction[] c1 = new BigFraction[] { c2[0].multiply(c2[0]).add(c3[0].multiply(c3[0])).add(c4[0].multiply(c4[0])), c2[1].multiply(c2[1]).add(c3[1].multiply(c3[1])).add(c4[1].multiply(c4[1])), c2[2].multiply(c2[2]).add(c3[2].multiply(c3[2])).add(c4[2].multiply(c4[2])), c2[3].multiply(c2[3]).add(c3[3].multiply(c3[3])).add(c4[3].multiply(c4[3])) }; final BigFraction twoM11 = minor(c2, c3, c4).multiply(2); final BigFraction m12 = minor(c1, c3, c4); final BigFraction m13 = minor(c1, c2, c4); final BigFraction m14 = minor(c1, c2, c3); final BigFraction centerX = m12.divide(twoM11); final BigFraction centerY = m13.divide(twoM11).negate(); final BigFraction centerZ = m14.divide(twoM11); final BigFraction dx = c2[0].subtract(centerX); final BigFraction dy = c3[0].subtract(centerY); final BigFraction dz = c4[0].subtract(centerZ); final BigFraction r2 = dx.multiply(dx).add(dy.multiply(dy)).add(dz.multiply(dz)); return new EnclosingBall<Euclidean3D, Vector3D>(new Vector3D(centerX.doubleValue(), centerY.doubleValue(), centerZ.doubleValue()), FastMath.sqrt(r2.doubleValue()), vA, vB, vC, vD); } } } } }  EnclosingBall<Euclidean3D, Vector3D> ballOnSupport(final List<Vector3D> support);  }
@Test public void testSupport0Point() { List<Vector3D> support = Arrays.asList(new Vector3D[0]); EnclosingBall<Euclidean3D, Vector3D> sphere = new SphereGenerator().ballOnSupport(support); Assert.assertTrue(sphere.getRadius() < 0); Assert.assertEquals(0, sphere.getSupportSize()); Assert.assertEquals(0, sphere.getSupport().length); }
@Test public void testSupport1Point() { List<Vector3D> support = Arrays.asList(new Vector3D(1, 2, 3)); EnclosingBall<Euclidean3D, Vector3D> sphere = new SphereGenerator().ballOnSupport(support); Assert.assertEquals(0.0, sphere.getRadius(), 1.0e-10); Assert.assertTrue(sphere.contains(support.get(0))); Assert.assertTrue(sphere.contains(support.get(0), 0.5)); Assert.assertFalse(sphere.contains(new Vector3D(support.get(0).getX() + 0.1, support.get(0).getY() + 0.1, support.get(0).getZ() + 0.1), 0.001)); Assert.assertTrue(sphere.contains(new Vector3D(support.get(0).getX() + 0.1, support.get(0).getY() + 0.1, support.get(0).getZ() + 0.1), 0.5)); 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]); }
@Test public void testSupport2Points() { List<Vector3D> support = Arrays.asList(new Vector3D(1, 0, 0), new Vector3D(3, 0, 0)); EnclosingBall<Euclidean3D, Vector3D> sphere = new SphereGenerator().ballOnSupport(support); Assert.assertEquals(1.0, sphere.getRadius(), 1.0e-10); 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.assertTrue(sphere.contains(new Vector3D(2, 0.9, 0))); Assert.assertFalse(sphere.contains(Vector3D.ZERO)); Assert.assertEquals(0.0, new Vector3D(2, 0, 0).distance(sphere.getCenter()), 1.0e-10); Assert.assertEquals(2, sphere.getSupportSize()); }
@Test public void testSupport3Points() { List<Vector3D> support = Arrays.asList(new Vector3D(1, 0, 0), new Vector3D(3, 0, 0), new Vector3D(2, 2, 0)); EnclosingBall<Euclidean3D, Vector3D> sphere = new SphereGenerator().ballOnSupport(support); Assert.assertEquals(5.0 / 4.0, sphere.getRadius(), 1.0e-10); 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.assertTrue(sphere.contains(new Vector3D(2, 0.9, 0))); Assert.assertFalse(sphere.contains(new Vector3D(0.9, 0, 0))); Assert.assertFalse(sphere.contains(new Vector3D(3.1, 0, 0))); Assert.assertTrue(sphere.contains(new Vector3D(2.0, -0.499, 0))); Assert.assertFalse(sphere.contains(new Vector3D(2.0, -0.501, 0))); Assert.assertTrue(sphere.contains(new Vector3D(2.0, 3.0 / 4.0, -1.249))); Assert.assertFalse(sphere.contains(new Vector3D(2.0, 3.0 / 4.0, -1.251))); Assert.assertEquals(0.0, new Vector3D(2.0, 3.0 / 4.0, 0).distance(sphere.getCenter()), 1.0e-10); Assert.assertEquals(3, sphere.getSupportSize()); }
@Test public void testSupport4Points() { List<Vector3D> support = Arrays.asList(new Vector3D(17, 14, 18), new Vector3D(11, 14, 22), new Vector3D( 2, 22, 17), new Vector3D(22, 11, -10)); EnclosingBall<Euclidean3D, Vector3D> sphere = new SphereGenerator().ballOnSupport(support); Assert.assertEquals(25.0, sphere.getRadius(), 1.0e-10); 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.assertTrue(sphere.contains (new Vector3D(-22.999, 2, 2))); Assert.assertFalse(sphere.contains(new Vector3D(-23.001, 2, 2))); Assert.assertTrue(sphere.contains (new Vector3D( 26.999, 2, 2))); Assert.assertFalse(sphere.contains(new Vector3D( 27.001, 2, 2))); Assert.assertTrue(sphere.contains (new Vector3D(2, -22.999, 2))); Assert.assertFalse(sphere.contains(new Vector3D(2, -23.001, 2))); Assert.assertTrue(sphere.contains (new Vector3D(2, 26.999, 2))); Assert.assertFalse(sphere.contains(new Vector3D(2, 27.001, 2))); Assert.assertTrue(sphere.contains (new Vector3D(2, 2, -22.999))); Assert.assertFalse(sphere.contains(new Vector3D(2, 2, -23.001))); Assert.assertTrue(sphere.contains (new Vector3D(2, 2, 26.999))); Assert.assertFalse(sphere.contains(new Vector3D(2, 2, 27.001))); Assert.assertEquals(0.0, new Vector3D(2.0, 2.0, 2.0).distance(sphere.getCenter()), 1.0e-10); Assert.assertEquals(4, sphere.getSupportSize()); }
@Test public void testRandom() { final RandomGenerator random = new Well1024a(0xd015982e9f31ee04l); final UnitSphereRandomVectorGenerator sr = new UnitSphereRandomVectorGenerator(3, random); for (int i = 0; i < 100; ++i) { double d = 25 * random.nextDouble(); double refRadius = 10 * random.nextDouble(); Vector3D refCenter = new Vector3D(d, new Vector3D(sr.nextVector())); List<Vector3D> support = new ArrayList<Vector3D>(); for (int j = 0; j < 5; ++j) { support.add(new Vector3D(1.0, refCenter, refRadius, new Vector3D(sr.nextVector()))); } EnclosingBall<Euclidean3D, Vector3D> sphere = new SphereGenerator().ballOnSupport(support); Assert.assertEquals(0.0, refCenter.distance(sphere.getCenter()), 4e-7 * refRadius); Assert.assertEquals(refRadius, sphere.getRadius(), 1e-7 * refRadius); } }
@Test public void testDegeneratedCase() { final List<Vector3D> support = Arrays.asList(new Vector3D(FastMath.scalb(-8039905610797991.0, -50), FastMath.scalb(-4663475464714142.0, -48), FastMath.scalb( 6592658872616184.0, -49)), new Vector3D(FastMath.scalb(-8036658568968473.0, -50), FastMath.scalb(-4664256346424880.0, -48), FastMath.scalb( 6591357011730307.0, -49)), new Vector3D(FastMath.scalb(-8037820142977230.0, -50), FastMath.scalb(-4665280434237813.0, -48), FastMath.scalb( 6592435966112099.0, -49)), new Vector3D(FastMath.scalb(-8038007803611611.0, -50), FastMath.scalb(-4664291215918380.0, -48), FastMath.scalb( 6595270610894208.0, -49))); EnclosingBall<Euclidean3D, Vector3D> sphere = new SphereGenerator().ballOnSupport(support); 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); for (Vector3D v : support) { Assert.assertTrue(sphere.contains(v, 1.0e-14)); } }