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