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.util.ArrayList;
25 import java.util.Arrays;
26 import java.util.List;
27
28 import org.hipparchus.geometry.euclidean.twod.DiskGenerator;
29 import org.hipparchus.geometry.euclidean.twod.Euclidean2D;
30 import org.hipparchus.geometry.euclidean.twod.Vector2D;
31 import org.hipparchus.random.RandomGenerator;
32 import org.hipparchus.random.Well1024a;
33 import org.junit.Assert;
34 import org.junit.Test;
35
36
37 public class WelzlEncloser2DTest {
38
39 @Test
40 public void testNullList() {
41 DiskGenerator generator = new DiskGenerator();
42 WelzlEncloser<Euclidean2D, Vector2D> encloser =
43 new WelzlEncloser<Euclidean2D, Vector2D>(1.0e-10, generator);
44 EnclosingBall<Euclidean2D, Vector2D> ball = encloser.enclose(null);
45 Assert.assertTrue(ball.getRadius() < 0);
46 }
47
48 @Test
49 public void testNoPoints() {
50 DiskGenerator generator = new DiskGenerator();
51 WelzlEncloser<Euclidean2D, Vector2D> encloser =
52 new WelzlEncloser<Euclidean2D, Vector2D>(1.0e-10, generator);
53 EnclosingBall<Euclidean2D, Vector2D> ball = encloser.enclose(new ArrayList<Vector2D>());
54 Assert.assertTrue(ball.getRadius() < 0);
55 }
56
57 @Test
58 public void testRegularPoints() {
59 List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28, 8, 54, 11, 15);
60 checkDisk(list, Arrays.asList(list.get(2), list.get(3), list.get(4)));
61 }
62
63 @Test
64 public void testSolutionOnDiameter() {
65 List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28, 8, 54);
66 checkDisk(list, Arrays.asList(list.get(2), list.get(3)));
67 }
68
69 @Test
70 public void testReducingBall1() {
71 List<Vector2D> list = buildList(0.05380958511396061, 0.57332359658700000,
72 0.99348810731127870, 0.02056421361521466,
73 0.01203950647796437, 0.99779675042261860,
74 0.00810189987706078, 0.00589246003827815,
75 0.00465180821202149, 0.99219972923046940);
76 checkDisk(list, Arrays.asList(list.get(1), list.get(3), list.get(4)));
77 }
78
79 @Test
80 public void testReducingBall2() {
81 List<Vector2D> list = buildList(0.016930586154703, 0.333955448537779,
82 0.987189104892331, 0.969778855274507,
83 0.983696889599935, 0.012904580013266,
84 0.013114499572905, 0.034740156356895);
85 checkDisk(list, Arrays.asList(list.get(1), list.get(2), list.get(3)));
86 }
87
88 @Test
89 public void testLargeSamples() {
90 RandomGenerator random = new Well1024a(0xa2a63cad12c01fb2l);
91 for (int k = 0; k < 100; ++k) {
92 int nbPoints = random.nextInt(10000);
93 List<Vector2D> points = new ArrayList<Vector2D>();
94 for (int i = 0; i < nbPoints; ++i) {
95 double x = random.nextDouble();
96 double y = random.nextDouble();
97 points.add(new Vector2D(x, y));
98 }
99 checkDisk(points);
100 }
101 }
102
103 private List<Vector2D> buildList(final double ... coordinates) {
104 List<Vector2D> list = new ArrayList<Vector2D>(coordinates.length / 2);
105 for (int i = 0; i < coordinates.length; i += 2) {
106 list.add(new Vector2D(coordinates[i], coordinates[i + 1]));
107 }
108 return list;
109 }
110
111 private void checkDisk(List<Vector2D> points, List<Vector2D> refSupport) {
112
113 EnclosingBall<Euclidean2D, Vector2D> disk = checkDisk(points);
114
115
116 DiskGenerator generator = new DiskGenerator();
117 EnclosingBall<Euclidean2D, Vector2D> expected = generator.ballOnSupport(refSupport);
118 Assert.assertEquals(refSupport.size(), disk.getSupportSize());
119 Assert.assertEquals(expected.getRadius(), disk.getRadius(), 1.0e-10);
120 Assert.assertEquals(expected.getCenter().getX(), disk.getCenter().getX(), 1.0e-10);
121 Assert.assertEquals(expected.getCenter().getY(), disk.getCenter().getY(), 1.0e-10);
122
123 for (Vector2D s : disk.getSupport()) {
124 boolean found = false;
125 for (Vector2D rs : refSupport) {
126 if (s == rs) {
127 found = true;
128 }
129 }
130 Assert.assertTrue(found);
131 }
132
133
134 for (int i = 0; i < disk.getSupportSize(); ++i) {
135 List<Vector2D> reducedSupport = new ArrayList<Vector2D>();
136 int count = 0;
137 for (Vector2D s : disk.getSupport()) {
138 if (count++ != i) {
139 reducedSupport.add(s);
140 }
141 }
142 EnclosingBall<Euclidean2D, Vector2D> reducedDisk = generator.ballOnSupport(reducedSupport);
143 boolean foundOutside = false;
144 for (int j = 0; j < points.size() && !foundOutside; ++j) {
145 if (!reducedDisk.contains(points.get(j), 1.0e-10)) {
146 foundOutside = true;
147 }
148 }
149 Assert.assertTrue(foundOutside);
150 }
151
152 }
153
154 private EnclosingBall<Euclidean2D, Vector2D> checkDisk(List<Vector2D> points) {
155
156 WelzlEncloser<Euclidean2D, Vector2D> encloser =
157 new WelzlEncloser<Euclidean2D, Vector2D>(1.0e-10, new DiskGenerator());
158 EnclosingBall<Euclidean2D, Vector2D> disk = encloser.enclose(points);
159
160
161 for (Vector2D v : points) {
162 Assert.assertTrue(disk.contains(v, 1.0e-10));
163 }
164
165 for (Vector2D v : points) {
166 boolean inSupport = false;
167 for (Vector2D s : disk.getSupport()) {
168 if (v == s) {
169 inSupport = true;
170 }
171 }
172 if (inSupport) {
173
174 Assert.assertFalse(disk.contains(v, -0.001));
175 }
176 }
177
178 return disk;
179
180 }
181
182 }