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.euclidean.twod;
23
24 import java.util.ArrayList;
25 import java.util.Arrays;
26 import java.util.Collections;
27 import java.util.List;
28
29 import org.hipparchus.exception.MathIllegalArgumentException;
30 import org.hipparchus.geometry.euclidean.oned.Interval;
31 import org.hipparchus.geometry.euclidean.oned.IntervalsSet;
32 import org.hipparchus.geometry.euclidean.oned.Vector1D;
33 import org.hipparchus.geometry.partitioning.BSPTree;
34 import org.hipparchus.geometry.partitioning.BSPTreeVisitor;
35 import org.hipparchus.geometry.partitioning.BoundaryProjection;
36 import org.hipparchus.geometry.partitioning.Hyperplane;
37 import org.hipparchus.geometry.partitioning.Region;
38 import org.hipparchus.geometry.partitioning.Region.Location;
39 import org.hipparchus.geometry.partitioning.RegionFactory;
40 import org.hipparchus.geometry.partitioning.SubHyperplane;
41 import org.hipparchus.random.RandomVectorGenerator;
42 import org.hipparchus.random.UncorrelatedRandomVectorGenerator;
43 import org.hipparchus.random.UniformRandomGenerator;
44 import org.hipparchus.random.Well1024a;
45 import org.hipparchus.util.FastMath;
46 import org.junit.Assert;
47 import org.junit.Test;
48
49 public class PolygonsSetTest {
50
51 @Test
52 public void testSimplyConnected() {
53 Vector2D[][] vertices = new Vector2D[][] {
54 new Vector2D[] {
55 new Vector2D(36.0, 22.0),
56 new Vector2D(39.0, 32.0),
57 new Vector2D(19.0, 32.0),
58 new Vector2D( 6.0, 16.0),
59 new Vector2D(31.0, 10.0),
60 new Vector2D(42.0, 16.0),
61 new Vector2D(34.0, 20.0),
62 new Vector2D(29.0, 19.0),
63 new Vector2D(23.0, 22.0),
64 new Vector2D(33.0, 25.0)
65 }
66 };
67 PolygonsSet set = buildSet(vertices);
68 Assert.assertEquals(Region.Location.OUTSIDE, set.checkPoint(new Vector2D(50.0, 30.0)));
69 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
70 new Vector2D(30.0, 15.0),
71 new Vector2D(15.0, 20.0),
72 new Vector2D(24.0, 25.0),
73 new Vector2D(35.0, 30.0),
74 new Vector2D(19.0, 17.0)
75 });
76 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
77 new Vector2D(50.0, 30.0),
78 new Vector2D(30.0, 35.0),
79 new Vector2D(10.0, 25.0),
80 new Vector2D(10.0, 10.0),
81 new Vector2D(40.0, 10.0),
82 new Vector2D(50.0, 15.0),
83 new Vector2D(30.0, 22.0)
84 });
85 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
86 new Vector2D(30.0, 32.0),
87 new Vector2D(34.0, 20.0)
88 });
89 checkVertices(set.getVertices(), vertices);
90 }
91
92 @Test
93 public void testBox() {
94 PolygonsSet box = new PolygonsSet(0, 2, -1, 1, 1.0e-10);
95 Assert.assertEquals(4.0, box.getSize(), 1.0e-10);
96 Assert.assertEquals(8.0, box.getBoundarySize(), 1.0e-10);
97 }
98
99 @Test
100 public void testInfinite() {
101 PolygonsSet box = new PolygonsSet(new BSPTree<Euclidean2D>(Boolean.TRUE), 1.0e-10);
102 Assert.assertTrue(Double.isInfinite(box.getSize()));
103 }
104
105 @Test
106 public void testStair() {
107 Vector2D[][] vertices = new Vector2D[][] {
108 new Vector2D[] {
109 new Vector2D( 0.0, 0.0),
110 new Vector2D( 0.0, 2.0),
111 new Vector2D(-0.1, 2.0),
112 new Vector2D(-0.1, 1.0),
113 new Vector2D(-0.3, 1.0),
114 new Vector2D(-0.3, 1.5),
115 new Vector2D(-1.3, 1.5),
116 new Vector2D(-1.3, 2.0),
117 new Vector2D(-1.8, 2.0),
118 new Vector2D(-1.8 - 1.0 / FastMath.sqrt(2.0),
119 2.0 - 1.0 / FastMath.sqrt(2.0))
120 }
121 };
122
123 PolygonsSet set = buildSet(vertices);
124 checkVertices(set.getVertices(), vertices);
125
126 Assert.assertEquals(1.1 + 0.95 * FastMath.sqrt(2.0), set.getSize(), 1.0e-10);
127
128 }
129
130 @Test
131 public void testEmpty() {
132 PolygonsSet empty = (PolygonsSet) new RegionFactory<Euclidean2D>().getComplement(new PolygonsSet(1.0e-10));
133 Assert.assertTrue(empty.isEmpty());
134 Assert.assertEquals(0, empty.getVertices().length);
135 Assert.assertEquals(0.0, empty.getBoundarySize(), 1.0e-10);
136 Assert.assertEquals(0.0, empty.getSize(), 1.0e-10);
137 for (double y = -1; y < 1; y += 0.1) {
138 for (double x = -1; x < 1; x += 0.1) {
139 Assert.assertEquals(Double.POSITIVE_INFINITY,
140 empty.projectToBoundary(new Vector2D(x, y)).getOffset(),
141 1.0e-10);
142 }
143 }
144 }
145
146 @Test
147 public void testFull() {
148 PolygonsSet empty = new PolygonsSet(1.0e-10);
149 Assert.assertFalse(empty.isEmpty());
150 Assert.assertEquals(0, empty.getVertices().length);
151 Assert.assertEquals(0.0, empty.getBoundarySize(), 1.0e-10);
152 Assert.assertEquals(Double.POSITIVE_INFINITY, empty.getSize(), 1.0e-10);
153 for (double y = -1; y < 1; y += 0.1) {
154 for (double x = -1; x < 1; x += 0.1) {
155 Assert.assertEquals(Double.NEGATIVE_INFINITY,
156 empty.projectToBoundary(new Vector2D(x, y)).getOffset(),
157 1.0e-10);
158 }
159 }
160 }
161
162 @Test
163 public void testHole() {
164 Vector2D[][] vertices = new Vector2D[][] {
165 new Vector2D[] {
166 new Vector2D(0.0, 0.0),
167 new Vector2D(3.0, 0.0),
168 new Vector2D(3.0, 3.0),
169 new Vector2D(0.0, 3.0)
170 }, new Vector2D[] {
171 new Vector2D(1.0, 2.0),
172 new Vector2D(2.0, 2.0),
173 new Vector2D(2.0, 1.0),
174 new Vector2D(1.0, 1.0)
175 }
176 };
177 PolygonsSet set = buildSet(vertices);
178 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
179 new Vector2D(0.5, 0.5),
180 new Vector2D(1.5, 0.5),
181 new Vector2D(2.5, 0.5),
182 new Vector2D(0.5, 1.5),
183 new Vector2D(2.5, 1.5),
184 new Vector2D(0.5, 2.5),
185 new Vector2D(1.5, 2.5),
186 new Vector2D(2.5, 2.5),
187 new Vector2D(0.5, 1.0)
188 });
189 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
190 new Vector2D(1.5, 1.5),
191 new Vector2D(3.5, 1.0),
192 new Vector2D(4.0, 1.5),
193 new Vector2D(6.0, 6.0)
194 });
195 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
196 new Vector2D(1.0, 1.0),
197 new Vector2D(1.5, 0.0),
198 new Vector2D(1.5, 1.0),
199 new Vector2D(1.5, 2.0),
200 new Vector2D(1.5, 3.0),
201 new Vector2D(3.0, 3.0)
202 });
203 checkVertices(set.getVertices(), vertices);
204
205 for (double x = -0.999; x < 3.999; x += 0.11) {
206 Vector2D v = new Vector2D(x, x + 0.5);
207 BoundaryProjection<Euclidean2D> projection = set.projectToBoundary(v);
208 Assert.assertTrue(projection.getOriginal() == v);
209 Vector2D p = (Vector2D) projection.getProjected();
210 if (x < -0.5) {
211 Assert.assertEquals(0.0, p.getX(), 1.0e-10);
212 Assert.assertEquals(0.0, p.getY(), 1.0e-10);
213 Assert.assertEquals(+v.distance(Vector2D.ZERO), projection.getOffset(), 1.0e-10);
214 } else if (x < 0.5) {
215 Assert.assertEquals(0.0, p.getX(), 1.0e-10);
216 Assert.assertEquals(v.getY(), p.getY(), 1.0e-10);
217 Assert.assertEquals(-v.getX(), projection.getOffset(), 1.0e-10);
218 } else if (x < 1.25) {
219 Assert.assertEquals(1.0, p.getX(), 1.0e-10);
220 Assert.assertEquals(v.getY(), p.getY(), 1.0e-10);
221 Assert.assertEquals(v.getX() - 1.0, projection.getOffset(), 1.0e-10);
222 } else if (x < 2.0) {
223 Assert.assertEquals(v.getX(), p.getX(), 1.0e-10);
224 Assert.assertEquals(2.0, p.getY(), 1.0e-10);
225 Assert.assertEquals(2.0 - v.getY(), projection.getOffset(), 1.0e-10);
226 } else if (x < 3.0) {
227 Assert.assertEquals(v.getX(), p.getX(), 1.0e-10);
228 Assert.assertEquals(3.0, p.getY(), 1.0e-10);
229 Assert.assertEquals(v.getY() - 3.0, projection.getOffset(), 1.0e-10);
230 } else {
231 Assert.assertEquals(3.0, p.getX(), 1.0e-10);
232 Assert.assertEquals(3.0, p.getY(), 1.0e-10);
233 Assert.assertEquals(+v.distance(new Vector2D(3, 3)), projection.getOffset(), 1.0e-10);
234 }
235
236 }
237
238 }
239
240 @Test
241 public void testDisjointPolygons() {
242 Vector2D[][] vertices = new Vector2D[][] {
243 new Vector2D[] {
244 new Vector2D(0.0, 1.0),
245 new Vector2D(2.0, 1.0),
246 new Vector2D(1.0, 2.0)
247 }, new Vector2D[] {
248 new Vector2D(4.0, 0.0),
249 new Vector2D(5.0, 1.0),
250 new Vector2D(3.0, 1.0)
251 }
252 };
253 PolygonsSet set = buildSet(vertices);
254 Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new Vector2D(1.0, 1.5)));
255 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
256 new Vector2D(1.0, 1.5),
257 new Vector2D(4.5, 0.8)
258 });
259 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
260 new Vector2D(1.0, 0.0),
261 new Vector2D(3.5, 1.2),
262 new Vector2D(2.5, 1.0),
263 new Vector2D(3.0, 4.0)
264 });
265 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
266 new Vector2D(1.0, 1.0),
267 new Vector2D(3.5, 0.5),
268 new Vector2D(0.0, 1.0)
269 });
270 checkVertices(set.getVertices(), vertices);
271 }
272
273 @Test
274 public void testOppositeHyperplanes() {
275 Vector2D[][] vertices = new Vector2D[][] {
276 new Vector2D[] {
277 new Vector2D(1.0, 0.0),
278 new Vector2D(2.0, 1.0),
279 new Vector2D(3.0, 1.0),
280 new Vector2D(2.0, 2.0),
281 new Vector2D(1.0, 1.0),
282 new Vector2D(0.0, 1.0)
283 }
284 };
285 PolygonsSet set = buildSet(vertices);
286 checkVertices(set.getVertices(), vertices);
287 }
288
289 @Test
290 public void testSingularPoint() {
291 Vector2D[][] vertices = new Vector2D[][] {
292 new Vector2D[] {
293 new Vector2D( 0.0, 0.0),
294 new Vector2D( 1.0, 0.0),
295 new Vector2D( 1.0, 1.0),
296 new Vector2D( 0.0, 1.0),
297 new Vector2D( 0.0, 0.0),
298 new Vector2D(-1.0, 0.0),
299 new Vector2D(-1.0, -1.0),
300 new Vector2D( 0.0, -1.0)
301 }
302 };
303 PolygonsSet set = buildSet(vertices);
304 checkVertices(set.getVertices(), vertices);
305 }
306
307 @Test
308 public void testLineIntersection() {
309 Vector2D[][] vertices = new Vector2D[][] {
310 new Vector2D[] {
311 new Vector2D( 0.0, 0.0),
312 new Vector2D( 2.0, 0.0),
313 new Vector2D( 2.0, 1.0),
314 new Vector2D( 3.0, 1.0),
315 new Vector2D( 3.0, 3.0),
316 new Vector2D( 1.0, 3.0),
317 new Vector2D( 1.0, 2.0),
318 new Vector2D( 0.0, 2.0)
319 }
320 };
321 PolygonsSet set = buildSet(vertices);
322
323 Line l1 = new Line(new Vector2D(-1.5, 0.0), FastMath.PI / 4, 1.0e-10);
324 SubLine s1 = (SubLine) set.intersection(l1.wholeHyperplane());
325 List<Interval> i1 = ((IntervalsSet) s1.getRemainingRegion()).asList();
326 Assert.assertEquals(2, i1.size());
327 Interval v10 = i1.get(0);
328 Vector2D p10Lower = l1.toSpace(new Vector1D(v10.getInf()));
329 Assert.assertEquals(0.0, p10Lower.getX(), 1.0e-10);
330 Assert.assertEquals(1.5, p10Lower.getY(), 1.0e-10);
331 Vector2D p10Upper = l1.toSpace(new Vector1D(v10.getSup()));
332 Assert.assertEquals(0.5, p10Upper.getX(), 1.0e-10);
333 Assert.assertEquals(2.0, p10Upper.getY(), 1.0e-10);
334 Interval v11 = i1.get(1);
335 Vector2D p11Lower = l1.toSpace(new Vector1D(v11.getInf()));
336 Assert.assertEquals(1.0, p11Lower.getX(), 1.0e-10);
337 Assert.assertEquals(2.5, p11Lower.getY(), 1.0e-10);
338 Vector2D p11Upper = l1.toSpace(new Vector1D(v11.getSup()));
339 Assert.assertEquals(1.5, p11Upper.getX(), 1.0e-10);
340 Assert.assertEquals(3.0, p11Upper.getY(), 1.0e-10);
341
342 Line l2 = new Line(new Vector2D(-1.0, 2.0), 0, 1.0e-10);
343 SubLine s2 = (SubLine) set.intersection(l2.wholeHyperplane());
344 List<Interval> i2 = ((IntervalsSet) s2.getRemainingRegion()).asList();
345 Assert.assertEquals(1, i2.size());
346 Interval v20 = i2.get(0);
347 Vector2D p20Lower = l2.toSpace(new Vector1D(v20.getInf()));
348 Assert.assertEquals(1.0, p20Lower.getX(), 1.0e-10);
349 Assert.assertEquals(2.0, p20Lower.getY(), 1.0e-10);
350 Vector2D p20Upper = l2.toSpace(new Vector1D(v20.getSup()));
351 Assert.assertEquals(3.0, p20Upper.getX(), 1.0e-10);
352 Assert.assertEquals(2.0, p20Upper.getY(), 1.0e-10);
353
354 }
355
356 @Test
357 public void testUnlimitedSubHyperplane() {
358 Vector2D[][] vertices1 = new Vector2D[][] {
359 new Vector2D[] {
360 new Vector2D(0.0, 0.0),
361 new Vector2D(4.0, 0.0),
362 new Vector2D(1.4, 1.5),
363 new Vector2D(0.0, 3.5)
364 }
365 };
366 PolygonsSet set1 = buildSet(vertices1);
367 Vector2D[][] vertices2 = new Vector2D[][] {
368 new Vector2D[] {
369 new Vector2D(1.4, 0.2),
370 new Vector2D(2.8, -1.2),
371 new Vector2D(2.5, 0.6)
372 }
373 };
374 PolygonsSet set2 = buildSet(vertices2);
375
376 PolygonsSet set =
377 (PolygonsSet) new RegionFactory<Euclidean2D>().union(set1.copySelf(),
378 set2.copySelf());
379 checkVertices(set1.getVertices(), vertices1);
380 checkVertices(set2.getVertices(), vertices2);
381 checkVertices(set.getVertices(), new Vector2D[][] {
382 new Vector2D[] {
383 new Vector2D(0.0, 0.0),
384 new Vector2D(1.6, 0.0),
385 new Vector2D(2.8, -1.2),
386 new Vector2D(2.6, 0.0),
387 new Vector2D(4.0, 0.0),
388 new Vector2D(1.4, 1.5),
389 new Vector2D(0.0, 3.5)
390 }
391 });
392
393 }
394
395 @Test
396 public void testUnion() {
397 Vector2D[][] vertices1 = new Vector2D[][] {
398 new Vector2D[] {
399 new Vector2D( 0.0, 0.0),
400 new Vector2D( 2.0, 0.0),
401 new Vector2D( 2.0, 2.0),
402 new Vector2D( 0.0, 2.0)
403 }
404 };
405 PolygonsSet set1 = buildSet(vertices1);
406 Vector2D[][] vertices2 = new Vector2D[][] {
407 new Vector2D[] {
408 new Vector2D( 1.0, 1.0),
409 new Vector2D( 3.0, 1.0),
410 new Vector2D( 3.0, 3.0),
411 new Vector2D( 1.0, 3.0)
412 }
413 };
414 PolygonsSet set2 = buildSet(vertices2);
415 PolygonsSet set = (PolygonsSet) new RegionFactory<Euclidean2D>().union(set1.copySelf(),
416 set2.copySelf());
417 checkVertices(set1.getVertices(), vertices1);
418 checkVertices(set2.getVertices(), vertices2);
419 checkVertices(set.getVertices(), new Vector2D[][] {
420 new Vector2D[] {
421 new Vector2D( 0.0, 0.0),
422 new Vector2D( 2.0, 0.0),
423 new Vector2D( 2.0, 1.0),
424 new Vector2D( 3.0, 1.0),
425 new Vector2D( 3.0, 3.0),
426 new Vector2D( 1.0, 3.0),
427 new Vector2D( 1.0, 2.0),
428 new Vector2D( 0.0, 2.0)
429 }
430 });
431 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
432 new Vector2D(1.0, 1.0),
433 new Vector2D(0.5, 0.5),
434 new Vector2D(2.0, 2.0),
435 new Vector2D(2.5, 2.5),
436 new Vector2D(0.5, 1.5),
437 new Vector2D(1.5, 1.5),
438 new Vector2D(1.5, 0.5),
439 new Vector2D(1.5, 2.5),
440 new Vector2D(2.5, 1.5),
441 new Vector2D(2.5, 2.5)
442 });
443 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
444 new Vector2D(-0.5, 0.5),
445 new Vector2D( 0.5, 2.5),
446 new Vector2D( 2.5, 0.5),
447 new Vector2D( 3.5, 2.5)
448 });
449 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
450 new Vector2D(0.0, 0.0),
451 new Vector2D(0.5, 2.0),
452 new Vector2D(2.0, 0.5),
453 new Vector2D(2.5, 1.0),
454 new Vector2D(3.0, 2.5)
455 });
456
457 }
458
459 @Test
460 public void testIntersection() {
461 Vector2D[][] vertices1 = new Vector2D[][] {
462 new Vector2D[] {
463 new Vector2D( 0.0, 0.0),
464 new Vector2D( 2.0, 0.0),
465 new Vector2D( 2.0, 2.0),
466 new Vector2D( 0.0, 2.0)
467 }
468 };
469 PolygonsSet set1 = buildSet(vertices1);
470 Vector2D[][] vertices2 = new Vector2D[][] {
471 new Vector2D[] {
472 new Vector2D( 1.0, 1.0),
473 new Vector2D( 3.0, 1.0),
474 new Vector2D( 3.0, 3.0),
475 new Vector2D( 1.0, 3.0)
476 }
477 };
478 PolygonsSet set2 = buildSet(vertices2);
479 PolygonsSet set = (PolygonsSet) new RegionFactory<Euclidean2D>().intersection(set1.copySelf(),
480 set2.copySelf());
481 checkVertices(set1.getVertices(), vertices1);
482 checkVertices(set2.getVertices(), vertices2);
483 checkVertices(set.getVertices(), new Vector2D[][] {
484 new Vector2D[] {
485 new Vector2D( 1.0, 1.0),
486 new Vector2D( 2.0, 1.0),
487 new Vector2D( 2.0, 2.0),
488 new Vector2D( 1.0, 2.0)
489 }
490 });
491 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
492 new Vector2D(1.5, 1.5)
493 });
494 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
495 new Vector2D(0.5, 1.5),
496 new Vector2D(2.5, 1.5),
497 new Vector2D(1.5, 0.5),
498 new Vector2D(0.5, 0.5)
499 });
500 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
501 new Vector2D(1.0, 1.0),
502 new Vector2D(2.0, 2.0),
503 new Vector2D(1.0, 1.5),
504 new Vector2D(1.5, 2.0)
505 });
506 }
507
508 @Test
509 public void testXor() {
510 Vector2D[][] vertices1 = new Vector2D[][] {
511 new Vector2D[] {
512 new Vector2D( 0.0, 0.0),
513 new Vector2D( 2.0, 0.0),
514 new Vector2D( 2.0, 2.0),
515 new Vector2D( 0.0, 2.0)
516 }
517 };
518 PolygonsSet set1 = buildSet(vertices1);
519 Vector2D[][] vertices2 = new Vector2D[][] {
520 new Vector2D[] {
521 new Vector2D( 1.0, 1.0),
522 new Vector2D( 3.0, 1.0),
523 new Vector2D( 3.0, 3.0),
524 new Vector2D( 1.0, 3.0)
525 }
526 };
527 PolygonsSet set2 = buildSet(vertices2);
528 PolygonsSet set = (PolygonsSet) new RegionFactory<Euclidean2D>().xor(set1.copySelf(),
529 set2.copySelf());
530 checkVertices(set1.getVertices(), vertices1);
531 checkVertices(set2.getVertices(), vertices2);
532 checkVertices(set.getVertices(), new Vector2D[][] {
533 new Vector2D[] {
534 new Vector2D( 0.0, 0.0),
535 new Vector2D( 2.0, 0.0),
536 new Vector2D( 2.0, 1.0),
537 new Vector2D( 3.0, 1.0),
538 new Vector2D( 3.0, 3.0),
539 new Vector2D( 1.0, 3.0),
540 new Vector2D( 1.0, 2.0),
541 new Vector2D( 0.0, 2.0)
542 },
543 new Vector2D[] {
544 new Vector2D( 1.0, 1.0),
545 new Vector2D( 1.0, 2.0),
546 new Vector2D( 2.0, 2.0),
547 new Vector2D( 2.0, 1.0)
548 }
549 });
550 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
551 new Vector2D(0.5, 0.5),
552 new Vector2D(2.5, 2.5),
553 new Vector2D(0.5, 1.5),
554 new Vector2D(1.5, 0.5),
555 new Vector2D(1.5, 2.5),
556 new Vector2D(2.5, 1.5),
557 new Vector2D(2.5, 2.5)
558 });
559 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
560 new Vector2D(-0.5, 0.5),
561 new Vector2D( 0.5, 2.5),
562 new Vector2D( 2.5, 0.5),
563 new Vector2D( 1.5, 1.5),
564 new Vector2D( 3.5, 2.5)
565 });
566 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
567 new Vector2D(1.0, 1.0),
568 new Vector2D(2.0, 2.0),
569 new Vector2D(1.5, 1.0),
570 new Vector2D(2.0, 1.5),
571 new Vector2D(0.0, 0.0),
572 new Vector2D(0.5, 2.0),
573 new Vector2D(2.0, 0.5),
574 new Vector2D(2.5, 1.0),
575 new Vector2D(3.0, 2.5)
576 });
577 }
578
579 @Test
580 public void testDifference() {
581 Vector2D[][] vertices1 = new Vector2D[][] {
582 new Vector2D[] {
583 new Vector2D( 0.0, 0.0),
584 new Vector2D( 2.0, 0.0),
585 new Vector2D( 2.0, 2.0),
586 new Vector2D( 0.0, 2.0)
587 }
588 };
589 PolygonsSet set1 = buildSet(vertices1);
590 Vector2D[][] vertices2 = new Vector2D[][] {
591 new Vector2D[] {
592 new Vector2D( 1.0, 1.0),
593 new Vector2D( 3.0, 1.0),
594 new Vector2D( 3.0, 3.0),
595 new Vector2D( 1.0, 3.0)
596 }
597 };
598 PolygonsSet set2 = buildSet(vertices2);
599 PolygonsSet set = (PolygonsSet) new RegionFactory<Euclidean2D>().difference(set1.copySelf(),
600 set2.copySelf());
601 checkVertices(set1.getVertices(), vertices1);
602 checkVertices(set2.getVertices(), vertices2);
603 checkVertices(set.getVertices(), new Vector2D[][] {
604 new Vector2D[] {
605 new Vector2D( 0.0, 0.0),
606 new Vector2D( 2.0, 0.0),
607 new Vector2D( 2.0, 1.0),
608 new Vector2D( 1.0, 1.0),
609 new Vector2D( 1.0, 2.0),
610 new Vector2D( 0.0, 2.0)
611 }
612 });
613 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
614 new Vector2D(0.5, 0.5),
615 new Vector2D(0.5, 1.5),
616 new Vector2D(1.5, 0.5)
617 });
618 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
619 new Vector2D( 2.5, 2.5),
620 new Vector2D(-0.5, 0.5),
621 new Vector2D( 0.5, 2.5),
622 new Vector2D( 2.5, 0.5),
623 new Vector2D( 1.5, 1.5),
624 new Vector2D( 3.5, 2.5),
625 new Vector2D( 1.5, 2.5),
626 new Vector2D( 2.5, 1.5),
627 new Vector2D( 2.0, 1.5),
628 new Vector2D( 2.0, 2.0),
629 new Vector2D( 2.5, 1.0),
630 new Vector2D( 2.5, 2.5),
631 new Vector2D( 3.0, 2.5)
632 });
633 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
634 new Vector2D(1.0, 1.0),
635 new Vector2D(1.5, 1.0),
636 new Vector2D(0.0, 0.0),
637 new Vector2D(0.5, 2.0),
638 new Vector2D(2.0, 0.5)
639 });
640 }
641
642 @Test
643 public void testEmptyDifference() {
644 Vector2D[][] vertices1 = new Vector2D[][] {
645 new Vector2D[] {
646 new Vector2D( 0.5, 3.5),
647 new Vector2D( 0.5, 4.5),
648 new Vector2D(-0.5, 4.5),
649 new Vector2D(-0.5, 3.5)
650 }
651 };
652 PolygonsSet set1 = buildSet(vertices1);
653 Vector2D[][] vertices2 = new Vector2D[][] {
654 new Vector2D[] {
655 new Vector2D( 1.0, 2.0),
656 new Vector2D( 1.0, 8.0),
657 new Vector2D(-1.0, 8.0),
658 new Vector2D(-1.0, 2.0)
659 }
660 };
661 PolygonsSet set2 = buildSet(vertices2);
662 Assert.assertTrue(new RegionFactory<Euclidean2D>().difference(set1.copySelf(), set2.copySelf()).isEmpty());
663 }
664
665 @Test
666 public void testChoppedHexagon() {
667 double pi6 = FastMath.PI / 6.0;
668 double sqrt3 = FastMath.sqrt(3.0);
669 SubLine[] hyp = {
670 new Line(new Vector2D( 0.0, 1.0), 5 * pi6, 1.0e-10).wholeHyperplane(),
671 new Line(new Vector2D(-sqrt3, 1.0), 7 * pi6, 1.0e-10).wholeHyperplane(),
672 new Line(new Vector2D(-sqrt3, 1.0), 9 * pi6, 1.0e-10).wholeHyperplane(),
673 new Line(new Vector2D(-sqrt3, 0.0), 11 * pi6, 1.0e-10).wholeHyperplane(),
674 new Line(new Vector2D( 0.0, 0.0), 13 * pi6, 1.0e-10).wholeHyperplane(),
675 new Line(new Vector2D( 0.0, 1.0), 3 * pi6, 1.0e-10).wholeHyperplane(),
676 new Line(new Vector2D(-5.0 * sqrt3 / 6.0, 0.0), 9 * pi6, 1.0e-10).wholeHyperplane()
677 };
678 hyp[1] = (SubLine) hyp[1].split(hyp[0].getHyperplane()).getMinus();
679 hyp[2] = (SubLine) hyp[2].split(hyp[1].getHyperplane()).getMinus();
680 hyp[3] = (SubLine) hyp[3].split(hyp[2].getHyperplane()).getMinus();
681 hyp[4] = (SubLine) hyp[4].split(hyp[3].getHyperplane()).getMinus().split(hyp[0].getHyperplane()).getMinus();
682 hyp[5] = (SubLine) hyp[5].split(hyp[4].getHyperplane()).getMinus().split(hyp[0].getHyperplane()).getMinus();
683 hyp[6] = (SubLine) hyp[6].split(hyp[3].getHyperplane()).getMinus().split(hyp[1].getHyperplane()).getMinus();
684 BSPTree<Euclidean2D> tree = new BSPTree<Euclidean2D>(Boolean.TRUE);
685 for (int i = hyp.length - 1; i >= 0; --i) {
686 tree = new BSPTree<Euclidean2D>(hyp[i], new BSPTree<Euclidean2D>(Boolean.FALSE), tree, null);
687 }
688 PolygonsSet set = new PolygonsSet(tree, 1.0e-10);
689 SubLine splitter =
690 new Line(new Vector2D(-2.0 * sqrt3 / 3.0, 0.0), 9 * pi6, 1.0e-10).wholeHyperplane();
691 PolygonsSet slice =
692 new PolygonsSet(new BSPTree<Euclidean2D>(splitter,
693 set.getTree(false).split(splitter).getPlus(),
694 new BSPTree<Euclidean2D>(Boolean.FALSE), null),
695 1.0e-10);
696 Assert.assertEquals(Region.Location.OUTSIDE,
697 slice.checkPoint(new Vector2D(0.1, 0.5)));
698 Assert.assertEquals(11.0 / 3.0, slice.getBoundarySize(), 1.0e-10);
699
700 }
701
702 @Test
703 public void testConcentric() {
704 double h = FastMath.sqrt(3.0) / 2.0;
705 Vector2D[][] vertices1 = new Vector2D[][] {
706 new Vector2D[] {
707 new Vector2D( 0.00, 0.1 * h),
708 new Vector2D( 0.05, 0.1 * h),
709 new Vector2D( 0.10, 0.2 * h),
710 new Vector2D( 0.05, 0.3 * h),
711 new Vector2D(-0.05, 0.3 * h),
712 new Vector2D(-0.10, 0.2 * h),
713 new Vector2D(-0.05, 0.1 * h)
714 }
715 };
716 PolygonsSet set1 = buildSet(vertices1);
717 Vector2D[][] vertices2 = new Vector2D[][] {
718 new Vector2D[] {
719 new Vector2D( 0.00, 0.0 * h),
720 new Vector2D( 0.10, 0.0 * h),
721 new Vector2D( 0.20, 0.2 * h),
722 new Vector2D( 0.10, 0.4 * h),
723 new Vector2D(-0.10, 0.4 * h),
724 new Vector2D(-0.20, 0.2 * h),
725 new Vector2D(-0.10, 0.0 * h)
726 }
727 };
728 PolygonsSet set2 = buildSet(vertices2);
729 Assert.assertTrue(set2.contains(set1));
730 }
731
732 @Test
733 public void testBug20040520() {
734 BSPTree<Euclidean2D> a0 =
735 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.85, -0.05),
736 new Vector2D(0.90, -0.10)),
737 new BSPTree<Euclidean2D>(Boolean.FALSE),
738 new BSPTree<Euclidean2D>(Boolean.TRUE),
739 null);
740 BSPTree<Euclidean2D> a1 =
741 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.85, -0.10),
742 new Vector2D(0.90, -0.10)),
743 new BSPTree<Euclidean2D>(Boolean.FALSE), a0, null);
744 BSPTree<Euclidean2D> a2 =
745 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.90, -0.05),
746 new Vector2D(0.85, -0.05)),
747 new BSPTree<Euclidean2D>(Boolean.FALSE), a1, null);
748 BSPTree<Euclidean2D> a3 =
749 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.82, -0.05),
750 new Vector2D(0.82, -0.08)),
751 new BSPTree<Euclidean2D>(Boolean.FALSE),
752 new BSPTree<Euclidean2D>(Boolean.TRUE),
753 null);
754 BSPTree<Euclidean2D> a4 =
755 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.85, -0.05),
756 new Vector2D(0.80, -0.05),
757 false),
758 new BSPTree<Euclidean2D>(Boolean.FALSE), a3, null);
759 BSPTree<Euclidean2D> a5 =
760 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.82, -0.08),
761 new Vector2D(0.82, -0.18)),
762 new BSPTree<Euclidean2D>(Boolean.FALSE),
763 new BSPTree<Euclidean2D>(Boolean.TRUE),
764 null);
765 BSPTree<Euclidean2D> a6 =
766 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.82, -0.18),
767 new Vector2D(0.85, -0.15),
768 true),
769 new BSPTree<Euclidean2D>(Boolean.FALSE), a5, null);
770 BSPTree<Euclidean2D> a7 =
771 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.85, -0.05),
772 new Vector2D(0.82, -0.08),
773 false),
774 a4, a6, null);
775 BSPTree<Euclidean2D> a8 =
776 new BSPTree<Euclidean2D>(buildLine(new Vector2D(0.85, -0.25),
777 new Vector2D(0.85, 0.05)),
778 a2, a7, null);
779 BSPTree<Euclidean2D> a9 =
780 new BSPTree<Euclidean2D>(buildLine(new Vector2D(0.90, 0.05),
781 new Vector2D(0.90, -0.50)),
782 a8, new BSPTree<Euclidean2D>(Boolean.FALSE), null);
783
784 BSPTree<Euclidean2D> b0 =
785 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.92, -0.12),
786 new Vector2D(0.92, -0.08)),
787 new BSPTree<Euclidean2D>(Boolean.FALSE), new BSPTree<Euclidean2D>(Boolean.TRUE),
788 null);
789 BSPTree<Euclidean2D> b1 =
790 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.92, -0.08),
791 new Vector2D(0.90, -0.10),
792 true),
793 new BSPTree<Euclidean2D>(Boolean.FALSE), b0, null);
794 BSPTree<Euclidean2D> b2 =
795 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.92, -0.18),
796 new Vector2D(0.92, -0.12)),
797 new BSPTree<Euclidean2D>(Boolean.FALSE), new BSPTree<Euclidean2D>(Boolean.TRUE),
798 null);
799 BSPTree<Euclidean2D> b3 =
800 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.85, -0.15),
801 new Vector2D(0.90, -0.20)),
802 new BSPTree<Euclidean2D>(Boolean.FALSE), b2, null);
803 BSPTree<Euclidean2D> b4 =
804 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.95, -0.15),
805 new Vector2D(0.85, -0.05)),
806 b1, b3, null);
807 BSPTree<Euclidean2D> b5 =
808 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.85, -0.05),
809 new Vector2D(0.85, -0.25),
810 true),
811 new BSPTree<Euclidean2D>(Boolean.FALSE), b4, null);
812 BSPTree<Euclidean2D> b6 =
813 new BSPTree<Euclidean2D>(buildLine(new Vector2D(0.0, -1.10),
814 new Vector2D(1.0, -0.10)),
815 new BSPTree<Euclidean2D>(Boolean.FALSE), b5, null);
816
817 PolygonsSet c =
818 (PolygonsSet) new RegionFactory<Euclidean2D>().union(new PolygonsSet(a9, 1.0e-10),
819 new PolygonsSet(b6, 1.0e-10));
820
821 checkPoints(Region.Location.INSIDE, c, new Vector2D[] {
822 new Vector2D(0.83, -0.06),
823 new Vector2D(0.83, -0.15),
824 new Vector2D(0.88, -0.15),
825 new Vector2D(0.88, -0.09),
826 new Vector2D(0.88, -0.07),
827 new Vector2D(0.91, -0.18),
828 new Vector2D(0.91, -0.10)
829 });
830
831 checkPoints(Region.Location.OUTSIDE, c, new Vector2D[] {
832 new Vector2D(0.80, -0.10),
833 new Vector2D(0.83, -0.50),
834 new Vector2D(0.83, -0.20),
835 new Vector2D(0.83, -0.02),
836 new Vector2D(0.87, -0.50),
837 new Vector2D(0.87, -0.20),
838 new Vector2D(0.87, -0.02),
839 new Vector2D(0.91, -0.20),
840 new Vector2D(0.91, -0.08),
841 new Vector2D(0.93, -0.15)
842 });
843
844 checkVertices(c.getVertices(),
845 new Vector2D[][] {
846 new Vector2D[] {
847 new Vector2D(0.85, -0.15),
848 new Vector2D(0.90, -0.20),
849 new Vector2D(0.92, -0.18),
850 new Vector2D(0.92, -0.08),
851 new Vector2D(0.90, -0.10),
852 new Vector2D(0.90, -0.05),
853 new Vector2D(0.82, -0.05),
854 new Vector2D(0.82, -0.18),
855 }
856 });
857
858 }
859
860 @Test
861 public void testBug20041003() {
862
863 Line[] l = {
864 new Line(new Vector2D(0.0, 0.625000007541172),
865 new Vector2D(1.0, 0.625000007541172), 1.0e-10),
866 new Line(new Vector2D(-0.19204433621902645, 0.0),
867 new Vector2D(-0.19204433621902645, 1.0), 1.0e-10),
868 new Line(new Vector2D(-0.40303524786887, 0.4248364535319128),
869 new Vector2D(-1.12851149797877, -0.2634107480798909), 1.0e-10),
870 new Line(new Vector2D(0.0, 2.0),
871 new Vector2D(1.0, 2.0), 1.0e-10)
872 };
873
874 BSPTree<Euclidean2D> node1 =
875 new BSPTree<Euclidean2D>(new SubLine(l[0],
876 new IntervalsSet(intersectionAbscissa(l[0], l[1]),
877 intersectionAbscissa(l[0], l[2]),
878 1.0e-10)),
879 new BSPTree<Euclidean2D>(Boolean.TRUE),
880 new BSPTree<Euclidean2D>(Boolean.FALSE),
881 null);
882 BSPTree<Euclidean2D> node2 =
883 new BSPTree<Euclidean2D>(new SubLine(l[1],
884 new IntervalsSet(intersectionAbscissa(l[1], l[2]),
885 intersectionAbscissa(l[1], l[3]),
886 1.0e-10)),
887 node1,
888 new BSPTree<Euclidean2D>(Boolean.FALSE),
889 null);
890 BSPTree<Euclidean2D> node3 =
891 new BSPTree<Euclidean2D>(new SubLine(l[2],
892 new IntervalsSet(intersectionAbscissa(l[2], l[3]),
893 Double.POSITIVE_INFINITY, 1.0e-10)),
894 node2,
895 new BSPTree<Euclidean2D>(Boolean.FALSE),
896 null);
897 BSPTree<Euclidean2D> node4 =
898 new BSPTree<Euclidean2D>(l[3].wholeHyperplane(),
899 node3,
900 new BSPTree<Euclidean2D>(Boolean.FALSE),
901 null);
902
903 PolygonsSet set = new PolygonsSet(node4, 1.0e-10);
904 Assert.assertEquals(0, set.getVertices().length);
905
906 }
907
908 @Test
909 public void testSqueezedHexa() {
910 PolygonsSet set = new PolygonsSet(1.0e-10,
911 new Vector2D(-6, -4), new Vector2D(-8, -8), new Vector2D( 8, -8),
912 new Vector2D( 6, -4), new Vector2D(10, 4), new Vector2D(-10, 4));
913 Assert.assertEquals(Location.OUTSIDE, set.checkPoint(new Vector2D(0, 6)));
914 }
915
916 @Test
917 public void testIssue880Simplified() {
918
919 Vector2D[] vertices1 = new Vector2D[] {
920 new Vector2D( 90.13595870833188, 38.33604606376991),
921 new Vector2D( 90.14047850603913, 38.34600084496253),
922 new Vector2D( 90.11045289492762, 38.36801537312368),
923 new Vector2D( 90.10871471476526, 38.36878044144294),
924 new Vector2D( 90.10424901707671, 38.374300101757),
925 new Vector2D( 90.0979455456843, 38.373578376172475),
926 new Vector2D( 90.09081227075944, 38.37526295920463),
927 new Vector2D( 90.09081378927135, 38.375193883266434)
928 };
929 PolygonsSet set1 = new PolygonsSet(1.0e-10, vertices1);
930 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.12, 38.32)));
931 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.135, 38.355)));
932
933 }
934
935 @Test
936 public void testIssue880Complete() {
937 Vector2D[] vertices1 = new Vector2D[] {
938 new Vector2D( 90.08714908223715, 38.370299337260235),
939 new Vector2D( 90.08709517675004, 38.3702895991413),
940 new Vector2D( 90.08401538704919, 38.368849330127944),
941 new Vector2D( 90.08258210430711, 38.367634558585564),
942 new Vector2D( 90.08251455106665, 38.36763409247078),
943 new Vector2D( 90.08106599752608, 38.36761621664249),
944 new Vector2D( 90.08249585300035, 38.36753627557965),
945 new Vector2D( 90.09075743352184, 38.35914647644972),
946 new Vector2D( 90.09099945896571, 38.35896264724079),
947 new Vector2D( 90.09269383800086, 38.34595756121246),
948 new Vector2D( 90.09638631543191, 38.3457988093121),
949 new Vector2D( 90.09666417351019, 38.34523360999418),
950 new Vector2D( 90.1297082145872, 38.337670454923625),
951 new Vector2D( 90.12971687748956, 38.337669827794684),
952 new Vector2D( 90.1240820219179, 38.34328502001131),
953 new Vector2D( 90.13084259656404, 38.34017811765017),
954 new Vector2D( 90.13378567942857, 38.33860579180606),
955 new Vector2D( 90.13519557833206, 38.33621054663689),
956 new Vector2D( 90.13545616732307, 38.33614965452864),
957 new Vector2D( 90.13553111202748, 38.33613962818305),
958 new Vector2D( 90.1356903436448, 38.33610227127048),
959 new Vector2D( 90.13576283227428, 38.33609255422783),
960 new Vector2D( 90.13595870833188, 38.33604606376991),
961 new Vector2D( 90.1361556630693, 38.3360024198866),
962 new Vector2D( 90.13622408795709, 38.335987048115726),
963 new Vector2D( 90.13696189099994, 38.33581914328681),
964 new Vector2D( 90.13746655304897, 38.33616706665265),
965 new Vector2D( 90.13845973716064, 38.33650776167099),
966 new Vector2D( 90.13950901827667, 38.3368469456463),
967 new Vector2D( 90.14393814424852, 38.337591835857495),
968 new Vector2D( 90.14483839716831, 38.337076122362475),
969 new Vector2D( 90.14565474433601, 38.33769000964429),
970 new Vector2D( 90.14569421179482, 38.3377117256905),
971 new Vector2D( 90.14577067124333, 38.33770883625908),
972 new Vector2D( 90.14600350631684, 38.337714326520995),
973 new Vector2D( 90.14600355139731, 38.33771435193319),
974 new Vector2D( 90.14600369112401, 38.33771443882085),
975 new Vector2D( 90.14600382486884, 38.33771453466096),
976 new Vector2D( 90.14600395205912, 38.33771463904344),
977 new Vector2D( 90.14600407214999, 38.337714751520764),
978 new Vector2D( 90.14600418462749, 38.337714871611695),
979 new Vector2D( 90.14600422249327, 38.337714915811034),
980 new Vector2D( 90.14867838361471, 38.34113888210675),
981 new Vector2D( 90.14923750157374, 38.341582537502575),
982 new Vector2D( 90.14877083250991, 38.34160685841391),
983 new Vector2D( 90.14816667319519, 38.34244232585684),
984 new Vector2D( 90.14797696744586, 38.34248455284745),
985 new Vector2D( 90.14484318014337, 38.34385573215269),
986 new Vector2D( 90.14477919958296, 38.3453797747614),
987 new Vector2D( 90.14202393306448, 38.34464324839456),
988 new Vector2D( 90.14198920640195, 38.344651155237216),
989 new Vector2D( 90.14155207025175, 38.34486424263724),
990 new Vector2D( 90.1415196143314, 38.344871730519),
991 new Vector2D( 90.14128611910814, 38.34500196593859),
992 new Vector2D( 90.14047850603913, 38.34600084496253),
993 new Vector2D( 90.14045907000337, 38.34601860032171),
994 new Vector2D( 90.14039496493928, 38.346223030432384),
995 new Vector2D( 90.14037626063737, 38.346240203360026),
996 new Vector2D( 90.14030005823724, 38.34646920000705),
997 new Vector2D( 90.13799164754806, 38.34903093011013),
998 new Vector2D( 90.11045289492762, 38.36801537312368),
999 new Vector2D( 90.10871471476526, 38.36878044144294),
1000 new Vector2D( 90.10424901707671, 38.374300101757),
1001 new Vector2D( 90.10263482039932, 38.37310041316073),
1002 new Vector2D( 90.09834601753448, 38.373615053823414),
1003 new Vector2D( 90.0979455456843, 38.373578376172475),
1004 new Vector2D( 90.09086514328669, 38.37527884194668),
1005 new Vector2D( 90.09084931407364, 38.37590801712463),
1006 new Vector2D( 90.09081227075944, 38.37526295920463),
1007 new Vector2D( 90.09081378927135, 38.375193883266434)
1008 };
1009 PolygonsSet set1 = new PolygonsSet(1.0e-8, vertices1);
1010 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.0905, 38.3755)));
1011 Assert.assertEquals(Location.INSIDE, set1.checkPoint(new Vector2D(90.09084, 38.3755)));
1012 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.0913, 38.3755)));
1013 Assert.assertEquals(Location.INSIDE, set1.checkPoint(new Vector2D(90.1042, 38.3739)));
1014 Assert.assertEquals(Location.INSIDE, set1.checkPoint(new Vector2D(90.1111, 38.3673)));
1015 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.0959, 38.3457)));
1016
1017 Vector2D[] vertices2 = new Vector2D[] {
1018 new Vector2D( 90.13067558880044, 38.36977255037573),
1019 new Vector2D( 90.12907570488, 38.36817308242706),
1020 new Vector2D( 90.1342774136516, 38.356886880294724),
1021 new Vector2D( 90.13090330629757, 38.34664392676211),
1022 new Vector2D( 90.13078571364593, 38.344904617518466),
1023 new Vector2D( 90.1315602208914, 38.3447185040846),
1024 new Vector2D( 90.1316336226821, 38.34470643148342),
1025 new Vector2D( 90.134020944832, 38.340936644972885),
1026 new Vector2D( 90.13912536387306, 38.335497255122334),
1027 new Vector2D( 90.1396178806582, 38.334878075552126),
1028 new Vector2D( 90.14083049696671, 38.33316530644106),
1029 new Vector2D( 90.14145252901329, 38.33152722916191),
1030 new Vector2D( 90.1404779335565, 38.32863516047786),
1031 new Vector2D( 90.14282712131586, 38.327504432532066),
1032 new Vector2D( 90.14616669875488, 38.3237354115015),
1033 new Vector2D( 90.14860976050608, 38.315714862457924),
1034 new Vector2D( 90.14999277782437, 38.3164932507504),
1035 new Vector2D( 90.15005207194997, 38.316534677663356),
1036 new Vector2D( 90.15508513859612, 38.31878731691609),
1037 new Vector2D( 90.15919938519221, 38.31852743183782),
1038 new Vector2D( 90.16093758658837, 38.31880662005153),
1039 new Vector2D( 90.16099420184912, 38.318825953291594),
1040 new Vector2D( 90.1665411125756, 38.31859497874757),
1041 new Vector2D( 90.16999653861313, 38.32505772048029),
1042 new Vector2D( 90.17475243391698, 38.32594398441148),
1043 new Vector2D( 90.17940844844992, 38.327427213761325),
1044 new Vector2D( 90.20951909541378, 38.330616833491774),
1045 new Vector2D( 90.2155400467941, 38.331746223670336),
1046 new Vector2D( 90.21559881391778, 38.33175551425302),
1047 new Vector2D( 90.21916646426041, 38.332584299620805),
1048 new Vector2D( 90.23863749852285, 38.34778978875795),
1049 new Vector2D( 90.25459855175802, 38.357790570608984),
1050 new Vector2D( 90.25964298227257, 38.356918010203174),
1051 new Vector2D( 90.26024593994703, 38.361692743151366),
1052 new Vector2D( 90.26146187570015, 38.36311080550837),
1053 new Vector2D( 90.26614159359622, 38.36510808579902),
1054 new Vector2D( 90.26621342936448, 38.36507942500333),
1055 new Vector2D( 90.26652190211962, 38.36494042196722),
1056 new Vector2D( 90.26621240678867, 38.365113172030874),
1057 new Vector2D( 90.26614057102057, 38.365141832826794),
1058 new Vector2D( 90.26380080055299, 38.3660381760273),
1059 new Vector2D( 90.26315345241, 38.36670658276421),
1060 new Vector2D( 90.26251574942881, 38.367490323488084),
1061 new Vector2D( 90.26247873448426, 38.36755266444749),
1062 new Vector2D( 90.26234628016698, 38.36787989125406),
1063 new Vector2D( 90.26214559424784, 38.36945909356126),
1064 new Vector2D( 90.25861728442555, 38.37200753430875),
1065 new Vector2D( 90.23905557537864, 38.375405314295904),
1066 new Vector2D( 90.22517251874075, 38.38984691662256),
1067 new Vector2D( 90.22549955153215, 38.3911564273979),
1068 new Vector2D( 90.22434386063355, 38.391476432092134),
1069 new Vector2D( 90.22147729457276, 38.39134652252034),
1070 new Vector2D( 90.22142070120117, 38.391349167741964),
1071 new Vector2D( 90.20665060751588, 38.39475580900313),
1072 new Vector2D( 90.20042268367109, 38.39842558622888),
1073 new Vector2D( 90.17423771242085, 38.402727751805344),
1074 new Vector2D( 90.16756796257476, 38.40913898597597),
1075 new Vector2D( 90.16728283954308, 38.411255399912875),
1076 new Vector2D( 90.16703538220418, 38.41136059866693),
1077 new Vector2D( 90.16725865657685, 38.41013618805954),
1078 new Vector2D( 90.16746107640665, 38.40902614307544),
1079 new Vector2D( 90.16122795307462, 38.39773101873203)
1080 };
1081 PolygonsSet set2 = new PolygonsSet(1.0e-8, vertices2);
1082 PolygonsSet set = (PolygonsSet) new
1083 RegionFactory<Euclidean2D>().difference(set1.copySelf(),
1084 set2.copySelf());
1085
1086 Vector2D[][] vertices = set.getVertices();
1087 Assert.assertTrue(vertices[0][0] != null);
1088 Assert.assertEquals(1, vertices.length);
1089 }
1090
1091 @Test
1092 public void testTooThinBox() {
1093 Assert.assertEquals(0.0,
1094 new PolygonsSet(0.0, 0.0, 0.0, 10.3206397147574, 1.0e-10).getSize(),
1095 1.0e-10);
1096 }
1097
1098 @Test
1099 public void testWrongUsage() {
1100
1101
1102
1103 PolygonsSet ps = new PolygonsSet(new BSPTree<Euclidean2D>(), 1.0e-10);
1104 Assert.assertNotNull(ps);
1105 try {
1106 ps.getSize();
1107 Assert.fail("an exception should have been thrown");
1108 } catch (NullPointerException npe) {
1109
1110 }
1111 }
1112
1113 @Test
1114 public void testIssue1162() {
1115 PolygonsSet p = new PolygonsSet(1.0e-10,
1116 new Vector2D(4.267199999996532, -11.928637756014894),
1117 new Vector2D(4.267200000026445, -14.12360595809307),
1118 new Vector2D(9.144000000273694, -14.12360595809307),
1119 new Vector2D(9.144000000233383, -11.928637756020067));
1120
1121 PolygonsSet w = new PolygonsSet(1.0e-10,
1122 new Vector2D(2.56735636510452512E-9, -11.933116461089332),
1123 new Vector2D(2.56735636510452512E-9, -12.393225665247766),
1124 new Vector2D(2.56735636510452512E-9, -27.785625665247778),
1125 new Vector2D(4.267200000030211, -27.785625665247778),
1126 new Vector2D(4.267200000030211, -11.933116461089332));
1127
1128 Assert.assertFalse(p.contains(w));
1129
1130 }
1131
1132 @Test
1133 public void testThinRectangle() {
1134
1135 RegionFactory<Euclidean2D> factory = new RegionFactory<Euclidean2D>();
1136 Vector2D pA = new Vector2D(0.0, 1.0);
1137 Vector2D pB = new Vector2D(0.0, 0.0);
1138 Vector2D pC = new Vector2D(1.0 / 64.0, 0.0);
1139 Vector2D pD = new Vector2D(1.0 / 64.0, 1.0);
1140
1141
1142 Hyperplane<Euclidean2D>[] h1 = new Line[] {
1143 new Line(pA, pB, 1.0 / 256),
1144 new Line(pB, pC, 1.0 / 256),
1145 new Line(pC, pD, 1.0 / 256),
1146 new Line(pD, pA, 1.0 / 256)
1147 };
1148 Region<Euclidean2D> accuratePolygon = factory.buildConvex(h1);
1149 Assert.assertEquals(1.0 / 64.0, accuratePolygon.getSize(), 1.0e-10);
1150 Assert.assertTrue(Double.isInfinite(new RegionFactory<Euclidean2D>().getComplement(accuratePolygon).getSize()));
1151 Assert.assertEquals(2 * (1.0 + 1.0 / 64.0), accuratePolygon.getBoundarySize(), 1.0e-10);
1152
1153
1154
1155
1156 Hyperplane<Euclidean2D>[] h2 = new Line[] {
1157 new Line(pA, pB, 1.0 / 16),
1158 new Line(pB, pC, 1.0 / 16),
1159 new Line(pC, pD, 1.0 / 16),
1160 new Line(pD, pA, 1.0 / 16)
1161 };
1162 Region<Euclidean2D> degeneratedPolygon = factory.buildConvex(h2);
1163 Assert.assertEquals(0.0, degeneratedPolygon.getSize(), 1.0e-10);
1164 Assert.assertTrue(degeneratedPolygon.isEmpty());
1165
1166 }
1167
1168 @Test(expected=MathIllegalArgumentException.class)
1169 public void testInconsistentHyperplanes() {
1170 double tolerance = 1.0e-10;
1171 new RegionFactory<Euclidean2D>().buildConvex(new Line(new Vector2D(0, 0), new Vector2D(0, 1), tolerance),
1172 new Line(new Vector2D(1, 1), new Vector2D(1, 0), tolerance));
1173 }
1174
1175 @Test
1176 public void testBoundarySimplification() {
1177
1178
1179 PolygonsSet square = new PolygonsSet(1.0e-10,
1180 new Vector2D(0, 0),
1181 new Vector2D(1, 0),
1182 new Vector2D(1, 1),
1183 new Vector2D(0, 1));
1184 Vector2D[][] squareBoundary = square.getVertices();
1185 Assert.assertEquals(1, squareBoundary.length);
1186 Assert.assertEquals(4, squareBoundary[0].length);
1187 Counter squareCount = new Counter();
1188 squareCount.count(square);
1189 Assert.assertEquals(4, squareCount.getInternalNodes());
1190 Assert.assertEquals(5, squareCount.getLeafNodes());
1191
1192
1193
1194 SubLine cut = new Line(new Vector2D(0.5, 0.5), 0.0, square.getTolerance()).wholeHyperplane();
1195 PolygonsSet splitSquare = new PolygonsSet(square.getTree(false).split(cut),
1196 square.getTolerance());
1197 Counter splitSquareCount = new Counter();
1198 splitSquareCount.count(splitSquare);
1199 Assert.assertEquals(squareCount.getInternalNodes() + 3, splitSquareCount.getInternalNodes());
1200 Assert.assertEquals(squareCount.getLeafNodes() + 3, splitSquareCount.getLeafNodes());
1201
1202
1203
1204
1205 Vector2D[][] splitBoundary = splitSquare.getVertices();
1206 Assert.assertEquals(1, splitBoundary.length);
1207 Assert.assertEquals(4, splitBoundary[0].length);
1208
1209 }
1210
1211 @Test
1212 public void testOppositeEdges() {
1213 PolygonsSet polygon = new PolygonsSet(1.0e-6,
1214 new Vector2D(+1, -2),
1215 new Vector2D(+1, 0),
1216 new Vector2D(+2, 0),
1217 new Vector2D(-1, +2),
1218 new Vector2D(-1, 0),
1219 new Vector2D(-2, 0));
1220 Assert.assertEquals(6.0, polygon.getSize(), 1.0e-10);
1221 Assert.assertEquals(2.0 * FastMath.sqrt(13.0) + 6.0, polygon.getBoundarySize(), 1.0e-10);
1222 }
1223
1224 @Test
1225 public void testInfiniteQuadrant() {
1226 final double tolerance = 1.0e-10;
1227 BSPTree<Euclidean2D> bsp = new BSPTree<>();
1228 bsp.insertCut(new Line(Vector2D.ZERO, 0.0, tolerance));
1229 bsp.getPlus().setAttribute(Boolean.FALSE);
1230 bsp.getMinus().insertCut(new Line(Vector2D.ZERO, 0.5 * FastMath.PI, tolerance));
1231 bsp.getMinus().getPlus().setAttribute(Boolean.FALSE);
1232 bsp.getMinus().getMinus().setAttribute(Boolean.TRUE);
1233 PolygonsSet polygons = new PolygonsSet(bsp, tolerance);
1234 Assert.assertEquals(Double.POSITIVE_INFINITY, polygons.getSize(), 1.0e-10);
1235 }
1236
1237 @Test
1238 public void testZigZagBoundaryOversampledIssue46() {
1239 final double tol = 1.0e-4;
1240
1241 final List<Vector2D> vertices = Arrays.asList(
1242 new Vector2D(-0.12630940610562444e1, (0.8998192093789258 - 0.89) * 100),
1243 new Vector2D(-0.12731320182988207e1, (0.8963735568774486 - 0.89) * 100),
1244 new Vector2D(-0.1351107624622557e1, (0.8978258663483273 - 0.89) * 100),
1245 new Vector2D(-0.13545331405131725e1, (0.8966781238246179 - 0.89) * 100),
1246 new Vector2D(-0.14324883017454967e1, (0.8981309629283796 - 0.89) * 100),
1247 new Vector2D(-0.14359875625524995e1, (0.896983965573036 - 0.89) * 100),
1248 new Vector2D(-0.14749650541159384e1, (0.8977109994666864 - 0.89) * 100),
1249 new Vector2D(-0.14785037758231825e1, (0.8965644005442432 - 0.89) * 100),
1250 new Vector2D(-0.15369807257448784e1, (0.8976550608135502 - 0.89) * 100),
1251 new Vector2D(-0.1526225554339386e1, (0.9010934265410458 - 0.89) * 100),
1252 new Vector2D(-0.14679028466684121e1, (0.9000043396997698 - 0.89) * 100),
1253 new Vector2D(-0.14643807494172612e1, (0.9011511073761742 - 0.89) * 100),
1254 new Vector2D(-0.1386609051963748e1, (0.8996991539048602 - 0.89) * 100),
1255 new Vector2D(-0.13831601655974668e1, (0.9008466623902937 - 0.89) * 100),
1256 new Vector2D(-0.1305365419828323e1, (0.8993961857946309 - 0.89) * 100),
1257 new Vector2D(-0.1301989630405964e1, (0.9005444294061787 - 0.89) * 100));
1258 Collections.reverse(vertices);
1259 PolygonsSet expected = new PolygonsSet(tol, vertices.toArray(new Vector2D[0]));
1260
1261 List<Vector2D> points = new ArrayList<>();
1262 final Vector2D[] boundary = expected.getVertices()[0];
1263 double step = tol / 10;
1264 for (int i = 1; i < boundary.length; i++) {
1265 Segment edge = new Segment(boundary[i - 1], boundary[i], tol);
1266 final double length = edge.getLength();
1267 final double x0 = edge.getLine().toSubSpace(edge.getStart()).getX();
1268 int n = (int) (length / step);
1269 for (int j = 0; j < n; j++) {
1270 points.add(edge.getLine().getPointAt(new Vector1D(x0 + j * step), 0));
1271 }
1272 }
1273
1274 PolygonsSet zone = new PolygonsSet(tol, points.toArray(new Vector2D[0]));
1275 Assert.assertEquals(expected.getSize(), zone.getSize(), tol);
1276 Assert.assertEquals(expected.getBarycenter().distance(zone.getBarycenter()), 0, tol);
1277 Assert.assertEquals("" + expected.getBarycenter() + zone.getBarycenter(),
1278 Location.INSIDE, zone.checkPoint(zone.getBarycenter()));
1279
1280
1281 final double cornerTol = 3.1 * tol;
1282 for (Vector2D vertex : vertices) {
1283
1284 Assert.assertEquals("" + vertex, Location.BOUNDARY, zone.checkPoint(vertex));
1285 double offset = FastMath.abs(zone.projectToBoundary(vertex).getOffset());
1286 Assert.assertEquals("" + vertex + " offset: " + offset, 0, offset, cornerTol);
1287 }
1288 }
1289
1290 @Test
1291 public void testPositiveQuadrantByVerticesDetailIssue46() {
1292 double tol = 0.01;
1293 Line x = new Line(Vector2D.ZERO, new Vector2D(1, 0), tol);
1294 Line y = new Line(Vector2D.ZERO, new Vector2D(0, 1), tol);
1295 double length = 1;
1296 double step = tol / 10;
1297
1298 int n = (int) (length / step);
1299 List<Vector2D> points = new ArrayList<>();
1300 for (int i = 0; i < n; i++) {
1301 double t = i * step;
1302 points.add(y.getPointAt(new Vector1D(t), 0));
1303 }
1304 for (int i = 0; i < n; i++) {
1305 double t = i * step;
1306 points.add(x.getPointAt(new Vector1D(t), 0).add(new Vector2D(0, 1)));
1307 }
1308 for (int i = 0; i < n; i++) {
1309 double t = i * step;
1310 points.add(new Vector2D(1, 1).subtract(y.getPointAt(new Vector1D(t), 0)));
1311 }
1312 Collections.reverse(points);
1313 PolygonsSet set = new PolygonsSet(tol, points.toArray(new Vector2D[0]));
1314 RandomVectorGenerator random =
1315 new UncorrelatedRandomVectorGenerator(2, new UniformRandomGenerator(new Well1024a(0xb8fc5acc91044308l)));
1316
1317
1318
1319
1320
1321 for (int i = 0; i < 1000; ++i) {
1322 Vector2D v = new Vector2D(random.nextVector());
1323 final Location actual = set.checkPoint(v);
1324 if ((v.getX() > tol) && (v.getY() > tol) && (v.getX() < 1 - tol) && (v.getY() < 1 - tol)) {
1325 if ((v.getX() > 2 * tol) && (v.getY() > 2 * tol) && (v.getX() < 1 - 2 * tol) && (v.getY() < 1 - 2 * tol)) {
1326
1327 Assert.assertEquals("" + v, Location.INSIDE, actual);
1328 } else {
1329
1330 Assert.assertNotEquals("" + v, Location.OUTSIDE, actual);
1331 }
1332 } else if ((v.getX() < 0) || (v.getY() < 0) || (v.getX() > 1) || (v.getY() > 1)) {
1333 if ((v.getX() < -tol) || (v.getY() < -tol) || (v.getX() > 1 + tol) || (v.getY() > 1 + tol)) {
1334
1335 Assert.assertEquals(Location.OUTSIDE, actual);
1336 } else {
1337
1338 Assert.assertNotEquals(Location.INSIDE, actual);
1339 }
1340 } else {
1341
1342 Assert.assertEquals(Location.BOUNDARY, actual);
1343 }
1344 }
1345
1346 for (Vector2D point : points) {
1347 Assert.assertEquals("" + point, Location.BOUNDARY, set.checkPoint(point));
1348 }
1349 }
1350
1351 @Test
1352 public void testOversampledCircleIssue64() {
1353
1354 double tol = 1e-2;
1355 double length = FastMath.PI * 2;
1356 int n = (int) (length / tol);
1357 double step = length / n;
1358 List<Vector2D> points = new ArrayList<>(n);
1359 for (int i = 0; i < n; i++) {
1360 double angle = i * step;
1361 points.add(new Vector2D(FastMath.cos(angle), FastMath.sin(angle)));
1362 }
1363
1364
1365 PolygonsSet set = new PolygonsSet(tol, points.toArray(new Vector2D[0]));
1366
1367
1368 Assert.assertEquals(set.getSize(), FastMath.PI, tol);
1369 Assert.assertEquals(set.getBarycenter().distance(Vector2D.ZERO), 0, tol);
1370
1371 Assert.assertEquals(set.getBoundarySize(), length, 2 * tol);
1372 for (Vector2D point : points) {
1373 Assert.assertEquals(set.checkPoint(point), Location.BOUNDARY);
1374 }
1375 }
1376
1377 private static class Counter {
1378
1379 private int internalNodes;
1380 private int leafNodes;
1381
1382 public void count(PolygonsSet polygonsSet) {
1383 leafNodes = 0;
1384 internalNodes = 0;
1385 polygonsSet.getTree(false).visit(new BSPTreeVisitor<Euclidean2D>() {
1386 public Order visitOrder(BSPTree<Euclidean2D> node) {
1387 return Order.SUB_PLUS_MINUS;
1388 }
1389 public void visitInternalNode(BSPTree<Euclidean2D> node) {
1390 ++internalNodes;
1391 }
1392 public void visitLeafNode(BSPTree<Euclidean2D> node) {
1393 ++leafNodes;
1394 }
1395
1396 });
1397 }
1398
1399 public int getInternalNodes() {
1400 return internalNodes;
1401 }
1402
1403 public int getLeafNodes() {
1404 return leafNodes;
1405 }
1406
1407 }
1408
1409 private PolygonsSet buildSet(Vector2D[][] vertices) {
1410 ArrayList<SubHyperplane<Euclidean2D>> edges = new ArrayList<SubHyperplane<Euclidean2D>>();
1411 for (int i = 0; i < vertices.length; ++i) {
1412 int l = vertices[i].length;
1413 for (int j = 0; j < l; ++j) {
1414 edges.add(buildSegment(vertices[i][j], vertices[i][(j + 1) % l]));
1415 }
1416 }
1417 return new PolygonsSet(edges, 1.0e-10);
1418 }
1419
1420 private SubHyperplane<Euclidean2D> buildLine(Vector2D start, Vector2D end) {
1421 return new Line(start, end, 1.0e-10).wholeHyperplane();
1422 }
1423
1424 private double intersectionAbscissa(Line l0, Line l1) {
1425 Vector2D p = l0.intersection(l1);
1426 return (l0.toSubSpace(p)).getX();
1427 }
1428
1429 private SubHyperplane<Euclidean2D> buildHalfLine(Vector2D start, Vector2D end,
1430 boolean startIsVirtual) {
1431 Line line = new Line(start, end, 1.0e-10);
1432 double lower = startIsVirtual ? Double.NEGATIVE_INFINITY : (line.toSubSpace(start)).getX();
1433 double upper = startIsVirtual ? (line.toSubSpace(end)).getX() : Double.POSITIVE_INFINITY;
1434 return new SubLine(line, new IntervalsSet(lower, upper, 1.0e-10));
1435 }
1436
1437 private SubHyperplane<Euclidean2D> buildSegment(Vector2D start, Vector2D end) {
1438 Line line = new Line(start, end, 1.0e-10);
1439 double lower = (line.toSubSpace(start)).getX();
1440 double upper = (line.toSubSpace(end)).getX();
1441 return new SubLine(line, new IntervalsSet(lower, upper, 1.0e-10));
1442 }
1443
1444 private void checkPoints(Region.Location expected, PolygonsSet set,
1445 Vector2D[] points) {
1446 for (int i = 0; i < points.length; ++i) {
1447 Assert.assertEquals(expected, set.checkPoint(points[i]));
1448 }
1449 }
1450
1451 private boolean checkInSegment(Vector2D p,
1452 Vector2D p1, Vector2D p2,
1453 double tolerance) {
1454 Line line = new Line(p1, p2, 1.0e-10);
1455 if (line.getOffset(p) < tolerance) {
1456 double x = (line.toSubSpace(p)).getX();
1457 double x1 = (line.toSubSpace(p1)).getX();
1458 double x2 = (line.toSubSpace(p2)).getX();
1459 return (((x - x1) * (x - x2) <= 0.0)
1460 || (p1.distance(p) < tolerance)
1461 || (p2.distance(p) < tolerance));
1462 } else {
1463 return false;
1464 }
1465 }
1466
1467 private void checkVertices(Vector2D[][] rebuiltVertices,
1468 Vector2D[][] vertices) {
1469
1470
1471 for (int i = 0; i < rebuiltVertices.length; ++i) {
1472 for (int j = 0; j < rebuiltVertices[i].length; ++j) {
1473 boolean inSegment = false;
1474 Vector2D p = rebuiltVertices[i][j];
1475 for (int k = 0; k < vertices.length; ++k) {
1476 Vector2D[] loop = vertices[k];
1477 int length = loop.length;
1478 for (int l = 0; (! inSegment) && (l < length); ++l) {
1479 inSegment = checkInSegment(p, loop[l], loop[(l + 1) % length], 1.0e-10);
1480 }
1481 }
1482 Assert.assertTrue(inSegment);
1483 }
1484 }
1485
1486
1487 for (int k = 0; k < vertices.length; ++k) {
1488 for (int l = 0; l < vertices[k].length; ++l) {
1489 double min = Double.POSITIVE_INFINITY;
1490 for (int i = 0; i < rebuiltVertices.length; ++i) {
1491 for (int j = 0; j < rebuiltVertices[i].length; ++j) {
1492 min = FastMath.min(vertices[k][l].distance(rebuiltVertices[i][j]),
1493 min);
1494 }
1495 }
1496 Assert.assertEquals(0.0, min, 1.0e-10);
1497 }
1498 }
1499
1500 }
1501
1502 }