1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 package org.hipparchus.geometry.enclosing;
23
24 import java.io.IOException;
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.List;
28
29 import org.hipparchus.geometry.euclidean.threed.Euclidean3D;
30 import org.hipparchus.geometry.euclidean.threed.SphereGenerator;
31 import org.hipparchus.geometry.euclidean.threed.Vector3D;
32 import org.hipparchus.random.RandomGenerator;
33 import org.hipparchus.random.UnitSphereRandomVectorGenerator;
34 import org.hipparchus.random.Well1024a;
35 import org.junit.Assert;
36 import org.junit.Test;
37
38
39 public class WelzlEncloser3DTest {
40
41 @Test
42 public void testNullList() {
43 SphereGenerator generator = new SphereGenerator();
44 WelzlEncloser<Euclidean3D, Vector3D> encloser =
45 new WelzlEncloser<Euclidean3D, Vector3D>(1.0e-10, generator);
46 EnclosingBall<Euclidean3D, Vector3D> ball = encloser.enclose(null);
47 Assert.assertTrue(ball.getRadius() < 0);
48 }
49
50 @Test
51 public void testNoPoints() {
52 SphereGenerator generator = new SphereGenerator();
53 WelzlEncloser<Euclidean3D, Vector3D> encloser =
54 new WelzlEncloser<Euclidean3D, Vector3D>(1.0e-10, generator);
55 EnclosingBall<Euclidean3D, Vector3D> ball = encloser.enclose(new ArrayList<Vector3D>());
56 Assert.assertTrue(ball.getRadius() < 0);
57 }
58
59 @Test
60 public void testReducingBall() {
61 List<Vector3D> list =
62 Arrays.asList(new Vector3D(-7.140397329568118, -16.571661242582177, 11.714458961735405),
63 new Vector3D(-7.137986707455888, -16.570767323375720, 11.708602108715928),
64 new Vector3D(-7.139185068549035, -16.570891204702250, 11.715554057357394),
65 new Vector3D(-7.142682716997507, -16.571609818234290, 11.710787934580328),
66 new Vector3D(-7.139018392423351, -16.574405614157020, 11.710518716711425),
67 new Vector3D(-7.140870659936730, -16.567993074240455, 11.710914678204503),
68 new Vector3D(-7.136350173659562, -16.570498228820930, 11.713965225900928),
69 new Vector3D(-7.141675762759172, -16.572852471407028, 11.714033471449508),
70 new Vector3D(-7.140453077221105, -16.570212820780647, 11.708624578004980),
71 new Vector3D(-7.140322188726825, -16.574152894557717, 11.710305611121410),
72 new Vector3D(-7.141116131477088, -16.574061164624560, 11.712938509321699));
73 WelzlEncloser<Euclidean3D, Vector3D> encloser =
74 new WelzlEncloser<Euclidean3D, Vector3D>(1.0e-10, new SphereGenerator());
75 EnclosingBall<Euclidean3D, Vector3D> ball = encloser.enclose(list);
76 Assert.assertTrue(ball.getRadius() > 0);
77 }
78
79 @Test
80 public void testInfiniteLoop() {
81
82 List<Vector3D> list =
83 Arrays.asList(new Vector3D( -0.89227075512164380, -2.89317694645713900, 14.84572323743355500),
84 new Vector3D( -0.92099498940693580, -2.31086108263908940, 12.92071026467688300),
85 new Vector3D( -0.85227999411005200, -3.06314731441320730, 15.40163831651287000),
86 new Vector3D( -1.77399413020785970, -3.65630391378114260, 14.13190097751873400),
87 new Vector3D( 0.33157833272465354, -2.22813591757792160, 14.21225234159008200),
88 new Vector3D( -1.53065579165484400, -1.65692084770139570, 14.61483055714788500),
89 new Vector3D( -1.08457093941217140, -1.96100325935602980, 13.09265170575555000),
90 new Vector3D( 0.30029469589708850, -3.05470831395667370, 14.56352400426342600),
91 new Vector3D( -0.95007443938638460, -1.86810946486118360, 15.14491234340057000),
92 new Vector3D( -1.89661503804130830, -2.17004080885185860, 14.81235128513927000),
93 new Vector3D( -0.72193328761607530, -1.44513142833618270, 14.52355724218561800),
94 new Vector3D( -0.26895980939606550, -3.69512371522084140, 14.72272846327652000),
95 new Vector3D( -1.53501693431786170, -3.25055166611021900, 15.15509062584274800),
96 new Vector3D( -0.71727553535519410, -3.62284279460799100, 13.26256700929380700),
97 new Vector3D( -0.30220950676137365, -3.25410412500779070, 13.13682612771606000),
98 new Vector3D( -0.04543996608267075, -1.93081853923797750, 14.79497997883171400),
99 new Vector3D( -1.53348892951571640, -3.66688919703524900, 14.73095600812074200),
100 new Vector3D( -0.98034899533935820, -3.34004481162763960, 13.03245014017556800));
101
102 WelzlEncloser<Euclidean3D, Vector3D> encloser =
103 new WelzlEncloser<Euclidean3D, Vector3D>(1.0e-10, new SphereGenerator());
104 EnclosingBall<Euclidean3D, Vector3D> ball = encloser.enclose(list);
105 Assert.assertTrue(ball.getRadius() > 0);
106 }
107
108 @Test
109 public void testLargeSamples() throws IOException {
110 RandomGenerator random = new Well1024a(0x35ddecfc78131e1dl);
111 final UnitSphereRandomVectorGenerator sr = new UnitSphereRandomVectorGenerator(3, random);
112 for (int k = 0; k < 50; ++k) {
113
114
115 double d = 25 * random.nextDouble();
116 double refRadius = 10 * random.nextDouble();
117 Vector3D refCenter = new Vector3D(d, new Vector3D(sr.nextVector()));
118
119 int nbPoints = random.nextInt(1000);
120 List<Vector3D> points = new ArrayList<Vector3D>();
121 for (int i = 0; i < nbPoints; ++i) {
122 double r = refRadius * random.nextDouble();
123 points.add(new Vector3D(1.0, refCenter, r, new Vector3D(sr.nextVector())));
124 }
125
126
127 checkSphere(points, refRadius);
128
129 }
130 }
131
132 @Test
133 public void testIssue20Generator() {
134
135 final SupportBallGenerator<Euclidean3D, Vector3D> generator = new SphereGenerator();
136 final Vector3D p1 = new Vector3D(0.9987716667, 0.0350821284, 0.0349914572);
137 final Vector3D p2 = new Vector3D(0.9987856181, -0.0346743952, 0.0349996489);
138 final Vector3D p4 = new Vector3D(0.9987798601, 0.0350739383, -0.0347650673);
139 EnclosingBall<Euclidean3D, Vector3D> s24 = generator.ballOnSupport(Arrays.asList(p2, p4));
140 EnclosingBall<Euclidean3D, Vector3D> s142 = generator.ballOnSupport(Arrays.asList(p1, p4, p2));
141
142 Assert.assertFalse(s24.contains(p1));
143 Assert.assertTrue(s24.contains(p2));
144 Assert.assertTrue(s24.contains(p4));
145
146 Assert.assertTrue(s142.contains(p1));
147 Assert.assertTrue(s142.contains(p4));
148 Assert.assertTrue(s142.contains(p2));
149
150 Assert.assertTrue(s142.getRadius() >= s24.getRadius());
151
152 }
153
154 @Test
155 public void testIssue20Encloser() {
156 final WelzlEncloser<Euclidean3D, Vector3D> encloser =
157 new WelzlEncloser<Euclidean3D, Vector3D>(1e-14, new SphereGenerator());
158 List<Vector3D> points = new ArrayList<Vector3D>();
159 points.add(new Vector3D(0.9999999731, 0.000200015, 0.0001174338));
160 points.add(new Vector3D(0.9987716667, 0.0350821284, 0.0349914572));
161 points.add(new Vector3D(0.9987856181, -0.0346743952, 0.0349996489));
162 points.add(new Vector3D(0.9987938115, -0.0346825853, -0.0347568755));
163 points.add(new Vector3D(0.9987798601, 0.0350739383, -0.0347650673));
164 EnclosingBall<Euclidean3D, Vector3D> enclosing3D = encloser.enclose(points);
165 Assert.assertEquals(0.04932531217754311, enclosing3D.getRadius(), 1.0e-15);
166 for (final Vector3D p : points) {
167 Assert.assertTrue(enclosing3D.contains(p));
168 }
169 }
170
171 private void checkSphere(List<Vector3D> points, double refRadius) {
172
173 EnclosingBall<Euclidean3D, Vector3D> sphere = checkSphere(points);
174
175
176 Assert.assertTrue(sphere.getRadius() <= refRadius);
177
178
179 for (int i = 0; i < sphere.getSupportSize(); ++i) {
180 List<Vector3D> reducedSupport = new ArrayList<Vector3D>();
181 int count = 0;
182 for (Vector3D s : sphere.getSupport()) {
183 if (count++ != i) {
184 reducedSupport.add(s);
185 }
186 }
187 EnclosingBall<Euclidean3D, Vector3D> reducedSphere =
188 new SphereGenerator().ballOnSupport(reducedSupport);
189 boolean foundOutside = false;
190 for (int j = 0; j < points.size() && !foundOutside; ++j) {
191 if (!reducedSphere.contains(points.get(j), 1.0e-10)) {
192 foundOutside = true;
193 }
194 }
195 Assert.assertTrue(foundOutside);
196 }
197
198 }
199
200 private EnclosingBall<Euclidean3D, Vector3D> checkSphere(List<Vector3D> points) {
201
202 WelzlEncloser<Euclidean3D, Vector3D> encloser =
203 new WelzlEncloser<Euclidean3D, Vector3D>(1.0e-10, new SphereGenerator());
204 EnclosingBall<Euclidean3D, Vector3D> Sphere = encloser.enclose(points);
205
206
207 for (Vector3D v : points) {
208 Assert.assertTrue(Sphere.contains(v, 1.0e-10));
209 }
210
211 for (Vector3D v : points) {
212 boolean inSupport = false;
213 for (Vector3D s : Sphere.getSupport()) {
214 if (v == s) {
215 inSupport = true;
216 }
217 }
218 if (inSupport) {
219
220 Assert.assertFalse(Sphere.contains(v, -0.001));
221 }
222 }
223
224 return Sphere;
225
226 }
227
228 }