View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.geometry.euclidean.twod;
18  
19  import java.util.List;
20  
21  import org.apache.commons.geometry.core.GeometryTestUtils;
22  import org.apache.commons.geometry.core.RegionLocation;
23  import org.apache.commons.geometry.core.partitioning.Split;
24  import org.apache.commons.geometry.core.partitioning.SplitLocation;
25  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
26  import org.apache.commons.geometry.euclidean.oned.Interval;
27  import org.apache.commons.geometry.euclidean.oned.RegionBSPTree1D;
28  import org.apache.commons.numbers.angle.Angle;
29  import org.apache.commons.numbers.core.Precision;
30  import org.junit.jupiter.api.Assertions;
31  import org.junit.jupiter.api.Test;
32  
33  class EmbeddedTreeLineSubsetTest {
34  
35      private static final double TEST_EPS = 1e-10;
36  
37      private static final Precision.DoubleEquivalence TEST_PRECISION =
38              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
39  
40      private static final Line DEFAULT_TEST_LINE =
41              Lines.fromPointAndDirection(Vector2D.of(0, 1), Vector2D.Unit.PLUS_X, TEST_PRECISION);
42  
43      @Test
44      void testCtor_lineOnly() {
45          // act
46          final EmbeddedTreeLineSubset sub = new EmbeddedTreeLineSubset(DEFAULT_TEST_LINE);
47  
48          // assert
49          Assertions.assertSame(DEFAULT_TEST_LINE, sub.getLine());
50          Assertions.assertSame(TEST_PRECISION, sub.getPrecision());
51  
52          Assertions.assertFalse(sub.isFull());
53          Assertions.assertTrue(sub.isEmpty());
54          Assertions.assertFalse(sub.isInfinite());
55          Assertions.assertTrue(sub.isFinite());
56  
57          Assertions.assertEquals(0, sub.getSize(), TEST_EPS);
58          Assertions.assertNull(sub.getCentroid());
59      }
60  
61      @Test
62      void testCtor_lineAndBoolean() {
63          // act
64          final EmbeddedTreeLineSubset sub = new EmbeddedTreeLineSubset(DEFAULT_TEST_LINE, true);
65  
66          // assert
67          Assertions.assertSame(DEFAULT_TEST_LINE, sub.getLine());
68          Assertions.assertSame(TEST_PRECISION, sub.getPrecision());
69  
70          Assertions.assertTrue(sub.isFull());
71          Assertions.assertFalse(sub.isEmpty());
72          Assertions.assertTrue(sub.isInfinite());
73          Assertions.assertFalse(sub.isFinite());
74  
75          GeometryTestUtils.assertPositiveInfinity(sub.getSize());
76          Assertions.assertNull(sub.getCentroid());
77      }
78  
79      @Test
80      void testCtor_lineAndRegion() {
81          // arrange
82          final RegionBSPTree1D tree = RegionBSPTree1D.full();
83  
84          // act
85          final EmbeddedTreeLineSubset sub = new EmbeddedTreeLineSubset(DEFAULT_TEST_LINE, tree);
86  
87          // assert
88          Assertions.assertSame(DEFAULT_TEST_LINE, sub.getLine());
89          Assertions.assertSame(tree, sub.getSubspaceRegion());
90          Assertions.assertSame(TEST_PRECISION, sub.getPrecision());
91  
92          Assertions.assertTrue(sub.isFull());
93          Assertions.assertFalse(sub.isEmpty());
94          Assertions.assertTrue(sub.isInfinite());
95          Assertions.assertFalse(sub.isFinite());
96  
97          GeometryTestUtils.assertPositiveInfinity(sub.getSize());
98          Assertions.assertNull(sub.getCentroid());
99      }
100 
101     @Test
102     void testToConvex_full() {
103         // arrange
104         final EmbeddedTreeLineSubset sub = new EmbeddedTreeLineSubset(DEFAULT_TEST_LINE, true);
105 
106         // act
107         final List<LineConvexSubset> segments = sub.toConvex();
108 
109         // assert
110         Assertions.assertEquals(1, segments.size());
111 
112         final LineConvexSubset seg = segments.get(0);
113         Assertions.assertTrue(seg.isFull());
114     }
115 
116     @Test
117     void testToConvex_empty() {
118         // arrange
119         final EmbeddedTreeLineSubset sub = new EmbeddedTreeLineSubset(DEFAULT_TEST_LINE, false);
120 
121         // act
122         final List<LineConvexSubset> segments = sub.toConvex();
123 
124         // assert
125         Assertions.assertEquals(0, segments.size());
126     }
127 
128     @Test
129     void testToConvex_finiteAndInfiniteSegments() {
130         // arrange
131         final EmbeddedTreeLineSubset sub = new EmbeddedTreeLineSubset(DEFAULT_TEST_LINE, false);
132         final RegionBSPTree1D tree = sub.getSubspaceRegion();
133         tree.add(Interval.max(-2.0, TEST_PRECISION));
134         tree.add(Interval.of(-1, 2, TEST_PRECISION));
135 
136         // act
137         final List<LineConvexSubset> segments = sub.toConvex();
138 
139         // assert
140         Assertions.assertEquals(2, segments.size());
141 
142         Assertions.assertNull(segments.get(0).getStartPoint());
143         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-2, 1), segments.get(0).getEndPoint(), TEST_EPS);
144 
145         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-1, 1), segments.get(1).getStartPoint(), TEST_EPS);
146         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 1), segments.get(1).getEndPoint(), TEST_EPS);
147     }
148 
149     @Test
150     void testAdd_lineSegment() {
151         // arrange
152         final Line line = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
153         final Line otherLine = Lines.fromPointAndAngle(Vector2D.of(0, 1), 1e-11, TEST_PRECISION);
154 
155         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line);
156 
157         // act
158         subset.add(Lines.subsetFromInterval(line, 2, 4));
159         subset.add(Lines.subsetFromInterval(otherLine, 1, 3));
160         subset.add(Lines.segmentFromPoints(Vector2D.of(-3, 1), Vector2D.of(-1, 1), TEST_PRECISION));
161 
162         // assert
163         Assertions.assertFalse(subset.isFull());
164         Assertions.assertFalse(subset.isEmpty());
165 
166         final List<LineConvexSubset> segments = subset.toConvex();
167 
168         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-3, 1), segments.get(0).getStartPoint(), TEST_EPS);
169         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-1, 1), segments.get(0).getEndPoint(), TEST_EPS);
170 
171         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), segments.get(1).getStartPoint(), TEST_EPS);
172         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(4, 1), segments.get(1).getEndPoint(), TEST_EPS);
173 
174         Assertions.assertEquals(5, subset.getSize(), TEST_EPS);
175         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.7, 1), subset.getCentroid(), TEST_EPS);
176     }
177 
178     @Test
179     void testAdd_subset() {
180         // arrange
181         final Line line = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
182 
183         final EmbeddedTreeLineSubset a = new EmbeddedTreeLineSubset(line);
184         final RegionBSPTree1D aTree = a.getSubspaceRegion();
185         aTree.add(Interval.max(-3, TEST_PRECISION));
186         aTree.add(Interval.of(1, 2, TEST_PRECISION));
187 
188         final EmbeddedTreeLineSubset b = new EmbeddedTreeLineSubset(line);
189         final RegionBSPTree1D bTree = b.getSubspaceRegion();
190         bTree.add(Interval.of(2, 4, TEST_PRECISION));
191         bTree.add(Interval.of(-4, -2, TEST_PRECISION));
192 
193         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line);
194 
195         final int aTreeCount = aTree.count();
196         final int bTreeCount = bTree.count();
197 
198         // act
199         subset.add(a);
200         subset.add(b);
201 
202         // assert
203         Assertions.assertFalse(subset.isFull());
204         Assertions.assertFalse(subset.isEmpty());
205 
206         final List<LineConvexSubset> segments = subset.toConvex();
207 
208         Assertions.assertEquals(2, segments.size());
209 
210         Assertions.assertNull(segments.get(0).getStartPoint());
211         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-2, 1), segments.get(0).getEndPoint(), TEST_EPS);
212 
213         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), segments.get(1).getStartPoint(), TEST_EPS);
214         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(4, 1), segments.get(1).getEndPoint(), TEST_EPS);
215 
216         Assertions.assertEquals(aTreeCount, aTree.count());
217         Assertions.assertEquals(bTreeCount, bTree.count());
218 
219         GeometryTestUtils.assertPositiveInfinity(subset.getSize());
220         Assertions.assertNull(subset.getCentroid());
221     }
222 
223     @Test
224     void testAdd_argumentsFromDifferentLine() {
225         // arrange
226         final Line line = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
227         final Line otherLine = Lines.fromPointAndAngle(Vector2D.of(0, 1), 1e-2, TEST_PRECISION);
228 
229         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line);
230 
231         // act/assert
232         Assertions.assertThrows(IllegalArgumentException.class, () -> subset.add(Lines.subsetFromInterval(otherLine, 0, 1)));
233         Assertions.assertThrows(IllegalArgumentException.class, () -> subset.add(new EmbeddedTreeLineSubset(otherLine)));
234     }
235 
236     @Test
237     void testGetBounds_noBounds() {
238         // arrange
239         final Line line = Lines.fromPointAndAngle(Vector2D.of(1, 0), 0.25 * Math.PI, TEST_PRECISION);
240 
241         final EmbeddedTreeLineSubset full = new EmbeddedTreeLineSubset(line, RegionBSPTree1D.full());
242         final EmbeddedTreeLineSubset empty = new EmbeddedTreeLineSubset(line, RegionBSPTree1D.empty());
243         final EmbeddedTreeLineSubset halfFull = new EmbeddedTreeLineSubset(line, Interval.min(1.0, TEST_PRECISION).toTree());
244 
245         // act/assert
246         Assertions.assertNull(full.getBounds());
247         Assertions.assertNull(empty.getBounds());
248         Assertions.assertNull(halfFull.getBounds());
249     }
250 
251     @Test
252     void testGetBounds_hasBounds() {
253         // arrange
254         final Line line = Lines.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION);
255 
256         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, false);
257 
258         final double sqrt2 = Math.sqrt(2);
259         subset.getSubspaceRegion().add(Interval.of(-2 * sqrt2, -sqrt2, TEST_PRECISION));
260         subset.getSubspaceRegion().add(Interval.of(0, sqrt2, TEST_PRECISION));
261 
262         // act
263         final Bounds2D bounds = subset.getBounds();
264 
265         // assert
266         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-2, -2), bounds.getMin(), TEST_EPS);
267         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), bounds.getMax(), TEST_EPS);
268     }
269 
270     @Test
271     void testSplit_both_anglePositive() {
272         // arrange
273         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
274         subRegion.add(Interval.of(0,  2, TEST_PRECISION));
275         subRegion.add(Interval.of(3,  4, TEST_PRECISION));
276 
277         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
278         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
279 
280         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(1, 0), 0.1 * Math.PI, TEST_PRECISION);
281 
282         // act
283         final Split<EmbeddedTreeLineSubset> split = subset.split(splitter);
284 
285         // assert
286         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
287 
288         final List<LineConvexSubset> minusSegments = split.getMinus().toConvex();
289         Assertions.assertEquals(1, minusSegments.size());
290         checkFiniteSegment(minusSegments.get(0), Vector2D.ZERO, Vector2D.of(1, 0));
291 
292         final List<LineConvexSubset> plusSegments = split.getPlus().toConvex();
293         Assertions.assertEquals(2, plusSegments.size());
294         checkFiniteSegment(plusSegments.get(0), Vector2D.of(1, 0), Vector2D.of(2, 0));
295         checkFiniteSegment(plusSegments.get(1), Vector2D.of(3, 0), Vector2D.of(4, 0));
296     }
297 
298     @Test
299     void testSplit_both_angleNegative() {
300         // arrange
301         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
302         subRegion.add(Interval.of(0,  2, TEST_PRECISION));
303         subRegion.add(Interval.of(3,  4, TEST_PRECISION));
304 
305         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
306         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
307 
308         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(1, 0), -0.9 * Math.PI, TEST_PRECISION);
309 
310         // act
311         final Split<EmbeddedTreeLineSubset> split = subset.split(splitter);
312 
313         // assert
314         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
315 
316         final List<LineConvexSubset> minusSegments = split.getMinus().toConvex();
317         Assertions.assertEquals(2, minusSegments.size());
318         checkFiniteSegment(minusSegments.get(0), Vector2D.of(1, 0), Vector2D.of(2, 0));
319         checkFiniteSegment(minusSegments.get(1), Vector2D.of(3, 0), Vector2D.of(4, 0));
320 
321         final List<LineConvexSubset> plusSegments = split.getPlus().toConvex();
322         Assertions.assertEquals(1, plusSegments.size());
323         checkFiniteSegment(plusSegments.get(0), Vector2D.ZERO, Vector2D.of(1, 0));
324     }
325 
326     @Test
327     void testSplit_intersection_plusOnly() {
328         // arrange
329         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
330         subRegion.add(Interval.of(0,  2, TEST_PRECISION));
331         subRegion.add(Interval.of(3,  4, TEST_PRECISION));
332 
333         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
334         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
335 
336         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(-1, 0), 0.1 * Math.PI, TEST_PRECISION);
337 
338         // act
339         final Split<EmbeddedTreeLineSubset> split = subset.split(splitter);
340 
341         // assert
342         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
343 
344         Assertions.assertNull(split.getMinus());
345         Assertions.assertSame(subset, split.getPlus());
346     }
347 
348     @Test
349     void testSplit_intersection_minusOnly() {
350         // arrange
351         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
352         subRegion.add(Interval.of(0,  2, TEST_PRECISION));
353         subRegion.add(Interval.of(3,  4, TEST_PRECISION));
354 
355         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
356         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
357 
358         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(10, 0), 0.1 * Math.PI, TEST_PRECISION);
359 
360         // act
361         final Split<EmbeddedTreeLineSubset> split = subset.split(splitter);
362 
363         // assert
364         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
365 
366         Assertions.assertSame(subset, split.getMinus());
367         Assertions.assertNull(split.getPlus());
368     }
369 
370     @Test
371     void testSplit_parallel_plus() {
372         // arrange
373         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
374         subRegion.add(Interval.of(0,  2, TEST_PRECISION));
375         subRegion.add(Interval.of(3,  4, TEST_PRECISION));
376 
377         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
378         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
379 
380         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
381 
382         // act
383         final Split<EmbeddedTreeLineSubset> split = subset.split(splitter);
384 
385         // assert
386         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
387 
388         Assertions.assertNull(split.getMinus());
389         Assertions.assertSame(subset, split.getPlus());
390     }
391 
392     @Test
393     void testSplit_parallel_minus() {
394         // arrange
395         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
396         subRegion.add(Interval.of(0,  2, TEST_PRECISION));
397         subRegion.add(Interval.of(3,  4, TEST_PRECISION));
398 
399         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
400         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
401 
402         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(0, -1), 0.0, TEST_PRECISION);
403 
404         // act
405         final Split<EmbeddedTreeLineSubset> split = subset.split(splitter);
406 
407         // assert
408         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
409 
410         Assertions.assertSame(subset, split.getMinus());
411         Assertions.assertNull(split.getPlus());
412     }
413 
414     @Test
415     void testSplit_coincident_sameDirection() {
416         // arrange
417         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
418         subRegion.add(Interval.of(0,  2, TEST_PRECISION));
419         subRegion.add(Interval.of(3,  4, TEST_PRECISION));
420 
421         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
422         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
423 
424         final Line splitter = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
425 
426         // act
427         final Split<EmbeddedTreeLineSubset> split = subset.split(splitter);
428 
429         // assert
430         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
431 
432         Assertions.assertNull(split.getMinus());
433         Assertions.assertNull(split.getPlus());
434     }
435 
436     @Test
437     void testSplit_coincident_oppositeDirection() {
438         // arrange
439         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
440         subRegion.add(Interval.of(0,  2, TEST_PRECISION));
441         subRegion.add(Interval.of(3,  4, TEST_PRECISION));
442 
443         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
444         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
445 
446         final Line splitter = Lines.fromPointAndAngle(Vector2D.ZERO, Math.PI, TEST_PRECISION);
447 
448         // act
449         final Split<EmbeddedTreeLineSubset> split = subset.split(splitter);
450 
451         // assert
452         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
453 
454         Assertions.assertNull(split.getMinus());
455         Assertions.assertNull(split.getPlus());
456     }
457 
458     @Test
459     void testTransform() {
460         // arrange
461         final AffineTransformMatrix2D mat = AffineTransformMatrix2D
462                 .createRotation(Vector2D.of(0, 1), Angle.PI_OVER_TWO)
463                 .scale(Vector2D.of(3, 2));
464 
465         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
466         subset.getSubspaceRegion().add(Interval.of(0, 1, TEST_PRECISION));
467         subset.getSubspaceRegion().add(Interval.min(3, TEST_PRECISION));
468 
469         // act
470         final EmbeddedTreeLineSubset transformed = subset.transform(mat);
471 
472         // assert
473         Assertions.assertNotSame(subset, transformed);
474 
475         final List<LineConvexSubset> originalSegments = subset.toConvex();
476         Assertions.assertEquals(2, originalSegments.size());
477         checkFiniteSegment(originalSegments.get(0), Vector2D.ZERO, Vector2D.Unit.PLUS_X);
478         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 0), originalSegments.get(1).getStartPoint(), TEST_EPS);
479         Assertions.assertNull(originalSegments.get(1).getEndPoint());
480 
481         final List<LineConvexSubset> transformedSegments = transformed.toConvex();
482         Assertions.assertEquals(2, transformedSegments.size());
483         checkFiniteSegment(transformedSegments.get(0), Vector2D.of(3, 2), Vector2D.of(3, 4));
484         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 8), transformedSegments.get(1).getStartPoint(), TEST_EPS);
485         Assertions.assertNull(transformedSegments.get(1).getEndPoint());
486     }
487 
488     @Test
489     void testTransform_reflection() {
490         // arrange
491         final AffineTransformMatrix2D mat = AffineTransformMatrix2D.createScale(Vector2D.of(-1, 2));
492 
493         final EmbeddedTreeLineSubset subset =
494                 new EmbeddedTreeLineSubset(Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION));
495         subset.getSubspaceRegion().add(Interval.of(0, 1, TEST_PRECISION));
496 
497         // act
498         final EmbeddedTreeLineSubset transformed = subset.transform(mat);
499 
500         // assert
501         Assertions.assertNotSame(subset, transformed);
502 
503         final List<LineConvexSubset> originalSegments = subset.toConvex();
504         Assertions.assertEquals(1, originalSegments.size());
505         checkFiniteSegment(originalSegments.get(0), Vector2D.of(0, 1), Vector2D.of(1, 1));
506 
507         final List<LineConvexSubset> transformedSegments = transformed.toConvex();
508         Assertions.assertEquals(1, transformedSegments.size());
509         checkFiniteSegment(transformedSegments.get(0), Vector2D.of(0, 2), Vector2D.of(-1, 2));
510     }
511 
512     @Test
513     void testClosest() {
514         // arrange
515         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
516         subRegion.add(Interval.of(0, 2, TEST_PRECISION));
517         subRegion.add(Interval.of(3, 4, TEST_PRECISION));
518 
519         final Line line = Lines.fromPointAndAngle(Vector2D.of(0, 2), 0.0, TEST_PRECISION);
520         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
521 
522         // act/assert
523         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 2), subset.closest(Vector2D.of(0, 1)), TEST_EPS);
524         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 2), subset.closest(Vector2D.of(0, 3)), TEST_EPS);
525 
526         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 2), subset.closest(Vector2D.of(1, 1)), TEST_EPS);
527         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 2), subset.closest(Vector2D.of(1, 3)), TEST_EPS);
528 
529         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 2), subset.closest(Vector2D.of(2, 1)), TEST_EPS);
530         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 2), subset.closest(Vector2D.of(2, 3)), TEST_EPS);
531 
532         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 2), subset.closest(Vector2D.of(2.4, 1)), TEST_EPS);
533         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 2), subset.closest(Vector2D.of(2.4, 3)), TEST_EPS);
534 
535         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 2), subset.closest(Vector2D.of(2.6, 1)), TEST_EPS);
536         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 2), subset.closest(Vector2D.of(2.6, 3)), TEST_EPS);
537 
538         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(4, 2), subset.closest(Vector2D.of(5, 1)), TEST_EPS);
539         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(4, 2), subset.closest(Vector2D.of(5, 3)), TEST_EPS);
540     }
541 
542     @Test
543     void testClosest_empty() {
544         // arrange
545         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
546         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, RegionBSPTree1D.empty());
547 
548         // act/assert
549         Assertions.assertNull(subset.closest(Vector2D.ZERO));
550     }
551 
552     @Test
553     void testClassify() {
554         // arrange
555         final RegionBSPTree1D subRegion = RegionBSPTree1D.empty();
556         subRegion.add(Interval.of(0, 2, TEST_PRECISION));
557         subRegion.add(Interval.of(3, 4, TEST_PRECISION));
558 
559         final Line line = Lines.fromPointAndAngle(Vector2D.of(0, 2), 0.0, TEST_PRECISION);
560         final EmbeddedTreeLineSubset subset = new EmbeddedTreeLineSubset(line, subRegion);
561 
562         // act/assert
563         EuclideanTestUtils.assertRegionLocation(subset, RegionLocation.INSIDE,
564                 Vector2D.of(1, 2), Vector2D.of(3.5, 2));
565 
566         EuclideanTestUtils.assertRegionLocation(subset, RegionLocation.BOUNDARY,
567                 Vector2D.of(0, 2), Vector2D.of(2, 2), Vector2D.of(3, 2), Vector2D.of(4, 2));
568 
569         EuclideanTestUtils.assertRegionLocation(subset, RegionLocation.OUTSIDE,
570                 Vector2D.of(-1, 2), Vector2D.of(2.5, 2), Vector2D.of(5, 2),
571                 Vector2D.of(1, 3), Vector2D.of(3.5, 1));
572     }
573 
574     @Test
575     void testToString() {
576         // arrange
577         final EmbeddedTreeLineSubset sub = new EmbeddedTreeLineSubset(DEFAULT_TEST_LINE);
578 
579         // act
580         final String str = sub.toString();
581 
582         // assert
583         Assertions.assertTrue(str.contains("EmbeddedTreeLineSubset[lineOrigin= "));
584         Assertions.assertTrue(str.contains(", lineDirection= "));
585         Assertions.assertTrue(str.contains(", region= "));
586     }
587 
588     private static void checkFiniteSegment(final LineConvexSubset segment, final Vector2D start, final Vector2D end) {
589         Assertions.assertFalse(segment.isInfinite());
590 
591         EuclideanTestUtils.assertCoordinatesEqual(start, segment.getStartPoint(), TEST_EPS);
592         EuclideanTestUtils.assertCoordinatesEqual(end, segment.getEndPoint(), TEST_EPS);
593     }
594 }