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