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.ArrayList;
20  import java.util.Arrays;
21  import java.util.Collections;
22  import java.util.Comparator;
23  import java.util.List;
24  import java.util.stream.Collectors;
25  
26  import org.apache.commons.geometry.core.GeometryTestUtils;
27  import org.apache.commons.geometry.core.Region;
28  import org.apache.commons.geometry.core.RegionLocation;
29  import org.apache.commons.geometry.core.partitioning.Split;
30  import org.apache.commons.geometry.core.partitioning.SplitLocation;
31  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
32  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
33  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D.PartitionedRegionBuilder2D;
34  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D.RegionNode2D;
35  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
36  import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
37  import org.apache.commons.numbers.angle.Angle;
38  import org.apache.commons.numbers.core.Precision;
39  import org.junit.jupiter.api.Assertions;
40  import org.junit.jupiter.api.Test;
41  
42  class RegionBSPTree2DTest {
43  
44      private static final double TEST_EPS = 1e-10;
45  
46      private static final Precision.DoubleEquivalence TEST_PRECISION =
47              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
48  
49      private static final Comparator<LineConvexSubset> SEGMENT_COMPARATOR =
50          (a, b) -> Vector2D.COORDINATE_ASCENDING_ORDER.compare(a.getStartPoint(), b.getStartPoint());
51  
52      private static final Line X_AXIS = Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
53  
54      private static final Line Y_AXIS = Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION);
55  
56      @Test
57      void testCtor_booleanArg_true() {
58          // act
59          final RegionBSPTree2D tree = new RegionBSPTree2D(true);
60  
61          // assert
62          Assertions.assertTrue(tree.isFull());
63          Assertions.assertFalse(tree.isEmpty());
64          Assertions.assertEquals(1, tree.count());
65      }
66  
67      @Test
68      void testCtor_booleanArg_false() {
69          // act
70          final RegionBSPTree2D tree = new RegionBSPTree2D(false);
71  
72          // assert
73          Assertions.assertFalse(tree.isFull());
74          Assertions.assertTrue(tree.isEmpty());
75          Assertions.assertEquals(1, tree.count());
76      }
77  
78      @Test
79      void testCtor_default() {
80          // act
81          final RegionBSPTree2D tree = new RegionBSPTree2D();
82  
83          // assert
84          Assertions.assertFalse(tree.isFull());
85          Assertions.assertTrue(tree.isEmpty());
86          Assertions.assertEquals(1, tree.count());
87      }
88  
89      @Test
90      void testFull_factoryMethod() {
91          // act
92          final RegionBSPTree2D tree = RegionBSPTree2D.full();
93  
94          // assert
95          Assertions.assertTrue(tree.isFull());
96          Assertions.assertFalse(tree.isEmpty());
97          Assertions.assertEquals(1, tree.count());
98      }
99  
100     @Test
101     void testEmpty_factoryMethod() {
102         // act
103         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
104 
105         // assert
106         Assertions.assertFalse(tree.isFull());
107         Assertions.assertTrue(tree.isEmpty());
108         Assertions.assertEquals(1, tree.count());
109     }
110 
111     @Test
112     void testPartitionedRegionBuilder_halfSpace() {
113         // act
114         final RegionBSPTree2D tree = RegionBSPTree2D.partitionedRegionBuilder()
115                 .insertPartition(
116                     Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION))
117                 .insertBoundary(
118                     Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.MINUS_X, TEST_PRECISION).span())
119                 .build();
120 
121         // assert
122         Assertions.assertFalse(tree.isFull());
123         Assertions.assertTrue(tree.isInfinite());
124 
125         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE, Vector2D.of(0, -1));
126         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY, Vector2D.ZERO);
127         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE, Vector2D.of(0, 1));
128     }
129 
130     @Test
131     void testPartitionedRegionBuilder_square() {
132         // arrange
133         final Parallelogram square = Parallelogram.unitSquare(TEST_PRECISION);
134         final List<LineConvexSubset> boundaries = square.getBoundaries();
135 
136         final Vector2D lowerBound = Vector2D.of(-2, -2);
137 
138         final int maxUpper = 5;
139         final int maxLevel = 4;
140 
141         // act/assert
142         Bounds2D bounds;
143         for (int u = 0; u <= maxUpper; ++u) {
144             for (int level = 0; level <= maxLevel; ++level) {
145                 bounds = Bounds2D.from(lowerBound, Vector2D.of(u, u));
146 
147                 checkFinitePartitionedRegion(bounds, level, square);
148                 checkFinitePartitionedRegion(bounds, level, boundaries);
149             }
150         }
151     }
152 
153     @Test
154     void testPartitionedRegionBuilder_nonConvex() {
155         // arrange
156         final RegionBSPTree2D src = Parallelogram.unitSquare(TEST_PRECISION).toTree();
157         src.union(Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).toTree());
158 
159         final List<LineConvexSubset> boundaries = src.getBoundaries();
160 
161         final Vector2D lowerBound = Vector2D.of(-2, -2);
162 
163         final int maxUpper = 5;
164         final int maxLevel = 4;
165 
166         // act/assert
167         Bounds2D bounds;
168         for (int u = 0; u <= maxUpper; ++u) {
169             for (int level = 0; level <= maxLevel; ++level) {
170                 bounds = Bounds2D.from(lowerBound, Vector2D.of(u, u));
171 
172                 checkFinitePartitionedRegion(bounds, level, src);
173                 checkFinitePartitionedRegion(bounds, level, boundaries);
174             }
175         }
176     }
177 
178     /** Check that a partitioned BSP tree behaves the same as a non-partitioned tree when
179      * constructed with the given boundary source.
180      * @param bounds
181      * @param level
182      * @param src
183      */
184     private void checkFinitePartitionedRegion(final Bounds2D bounds, final int level, final BoundarySource2D src) {
185         // arrange
186         final String msg = "Partitioned region check failed with bounds= " + bounds + " and level= " + level;
187 
188         final RegionBSPTree2D standard = RegionBSPTree2D.from(src.boundaryStream().collect(Collectors.toList()));
189 
190         // act
191         final RegionBSPTree2D partitioned = RegionBSPTree2D.partitionedRegionBuilder()
192                 .insertAxisAlignedGrid(bounds, level, TEST_PRECISION)
193                 .insertBoundaries(src)
194                 .build();
195 
196         // assert
197         Assertions.assertEquals(standard.getSize(), partitioned.getSize(), TEST_EPS, msg);
198         Assertions.assertEquals(standard.getBoundarySize(), partitioned.getBoundarySize(), TEST_EPS, msg);
199         EuclideanTestUtils.assertCoordinatesEqual(standard.getCentroid(), partitioned.getCentroid(), TEST_EPS);
200 
201         final RegionBSPTree2D diff = RegionBSPTree2D.empty();
202         diff.difference(partitioned, standard);
203         Assertions.assertTrue(diff.isEmpty(), msg);
204     }
205 
206     /** Check that a partitioned BSP tree behaves the same as a non-partitioned tree when
207      * constructed with the given boundaries.
208      * @param bounds
209      * @param level
210      * @param boundaries
211      */
212     private void checkFinitePartitionedRegion(final Bounds2D bounds, final int level,
213                                               final List<? extends LineConvexSubset> boundaries) {
214         // arrange
215         final String msg = "Partitioned region check failed with bounds= " + bounds + " and level= " + level;
216 
217         final RegionBSPTree2D standard = RegionBSPTree2D.from(boundaries);
218 
219         // act
220         final RegionBSPTree2D partitioned = RegionBSPTree2D.partitionedRegionBuilder()
221                 .insertAxisAlignedGrid(bounds, level, TEST_PRECISION)
222                 .insertBoundaries(boundaries)
223                 .build();
224 
225         // assert
226         Assertions.assertEquals(standard.getSize(), partitioned.getSize(), TEST_EPS, msg);
227         Assertions.assertEquals(standard.getBoundarySize(), partitioned.getBoundarySize(), TEST_EPS, msg);
228         EuclideanTestUtils.assertCoordinatesEqual(standard.getCentroid(), partitioned.getCentroid(), TEST_EPS);
229 
230         final RegionBSPTree2D diff = RegionBSPTree2D.empty();
231         diff.difference(partitioned, standard);
232         Assertions.assertTrue(diff.isEmpty(), msg);
233     }
234 
235     @Test
236     void testPartitionedRegionBuilder_insertPartitionAfterBoundary() {
237         // arrange
238         final PartitionedRegionBuilder2D builder = RegionBSPTree2D.partitionedRegionBuilder();
239         builder.insertBoundary(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 0), TEST_PRECISION));
240 
241         final Line partition = Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION);
242 
243         final String msg = "Cannot insert partitions after boundaries have been inserted";
244 
245         // act/assert
246         GeometryTestUtils.assertThrowsWithMessage(() -> {
247             builder.insertPartition(partition);
248         }, IllegalStateException.class, msg);
249 
250         GeometryTestUtils.assertThrowsWithMessage(() -> {
251             builder.insertPartition(partition.span());
252         }, IllegalStateException.class, msg);
253 
254         GeometryTestUtils.assertThrowsWithMessage(() -> {
255             builder.insertAxisAlignedPartitions(Vector2D.ZERO, TEST_PRECISION);
256         }, IllegalStateException.class, msg);
257 
258         GeometryTestUtils.assertThrowsWithMessage(() -> {
259             builder.insertAxisAlignedGrid(Bounds2D.from(Vector2D.ZERO, Vector2D.of(1, 1)), 1, TEST_PRECISION);
260         }, IllegalStateException.class, msg);
261     }
262 
263     @Test
264     void testCopy() {
265         // arrange
266         final RegionBSPTree2D tree = new RegionBSPTree2D(true);
267         tree.getRoot().cut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
268 
269         // act
270         final RegionBSPTree2D copy = tree.copy();
271 
272         // assert
273         Assertions.assertNotSame(tree, copy);
274         Assertions.assertEquals(3, copy.count());
275     }
276 
277     @Test
278     void testBoundaries() {
279         // arrange
280         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
281                 .toTree();
282 
283         // act
284         final List<LineConvexSubset> segments = new ArrayList<>();
285         tree.boundaries().forEach(segments::add);
286 
287         // assert
288         Assertions.assertEquals(4, segments.size());
289     }
290 
291     @Test
292     void testGetBoundaries() {
293         // arrange
294         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
295                 .toTree();
296 
297         // act
298         final List<LineConvexSubset> segments = tree.getBoundaries();
299 
300         // assert
301         Assertions.assertEquals(4, segments.size());
302     }
303 
304     @Test
305     void testBoundaryStream() {
306         // arrange
307         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
308                 .toTree();
309 
310         // act
311         final List<LineConvexSubset> segments = tree.boundaryStream().collect(Collectors.toList());
312 
313         // assert
314         Assertions.assertEquals(4, segments.size());
315     }
316 
317     @Test
318     void testBoundaryStream_noBoundaries() {
319         // arrange
320         final RegionBSPTree2D tree = RegionBSPTree2D.full();
321 
322         // act
323         final List<LineConvexSubset> segments = tree.boundaryStream().collect(Collectors.toList());
324 
325         // assert
326         Assertions.assertEquals(0, segments.size());
327     }
328 
329     @Test
330     void testGetBounds_hasBounds() {
331         // arrange
332         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.of(2, 3), Vector2D.of(5, 8), TEST_PRECISION)
333                 .toTree();
334 
335         // act
336         final Bounds2D bounds = tree.getBounds();
337 
338         // assert
339         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 3), bounds.getMin(), TEST_EPS);
340         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(5, 8), bounds.getMax(), TEST_EPS);
341     }
342 
343     @Test
344     void testGetBounds_noBounds() {
345         // act/assert
346         Assertions.assertNull(RegionBSPTree2D.empty().getBounds());
347         Assertions.assertNull(RegionBSPTree2D.full().getBounds());
348 
349         final RegionBSPTree2D halfFull = RegionBSPTree2D.empty();
350         halfFull.getRoot().insertCut(Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION));
351         Assertions.assertNull(halfFull.getBounds());
352     }
353 
354     @Test
355     void testGetBoundaryPaths_cachesResult() {
356         // arrange
357         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
358         tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
359 
360         // act
361         final List<LinePath> a = tree.getBoundaryPaths();
362         final List<LinePath> b = tree.getBoundaryPaths();
363 
364         // assert
365         Assertions.assertSame(a, b);
366     }
367 
368     @Test
369     void testGetBoundaryPaths_recomputesResultOnChange() {
370         // arrange
371         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
372         tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
373 
374         // act
375         final List<LinePath> a = tree.getBoundaryPaths();
376         tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION));
377         final List<LinePath> b = tree.getBoundaryPaths();
378 
379         // assert
380         Assertions.assertNotSame(a, b);
381     }
382 
383     @Test
384     void testGetBoundaryPaths_isUnmodifiable() {
385         // arrange
386         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
387         tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
388 
389         // act/assert
390         Assertions.assertThrows(UnsupportedOperationException.class, () -> tree.getBoundaryPaths().add(LinePath.builder(null).build()));
391     }
392 
393     @Test
394     void testAdd_convexArea() {
395         // arrange
396         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
397 
398         // act
399         tree.add(ConvexArea.convexPolygonFromVertices(Arrays.asList(
400                     Vector2D.ZERO, Vector2D.of(2, 0),
401                     Vector2D.of(2, 2), Vector2D.of(0, 2)
402                 ), TEST_PRECISION));
403         tree.add(ConvexArea.convexPolygonFromVertices(Arrays.asList(
404                 Vector2D.of(1, 1), Vector2D.of(3, 1),
405                 Vector2D.of(3, 3), Vector2D.of(1, 3)
406             ), TEST_PRECISION));
407 
408         // assert
409         Assertions.assertFalse(tree.isFull());
410         Assertions.assertFalse(tree.isEmpty());
411 
412         Assertions.assertEquals(7, tree.getSize(), TEST_EPS);
413         Assertions.assertEquals(12, tree.getBoundarySize(), TEST_EPS);
414         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 1.5), tree.getCentroid(), TEST_EPS);
415 
416         checkClassify(tree, RegionLocation.INSIDE,
417                 Vector2D.of(1, 1), Vector2D.of(1.5, 1.5), Vector2D.of(2, 2));
418     }
419 
420     @Test
421     void testToConvex_full() {
422         // arrange
423         final RegionBSPTree2D tree = RegionBSPTree2D.full();
424 
425         // act
426         final List<ConvexArea> result = tree.toConvex();
427 
428         // assert
429         Assertions.assertEquals(1, result.size());
430         Assertions.assertTrue(result.get(0).isFull());
431     }
432 
433     @Test
434     void testToConvex_empty() {
435         // arrange
436         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
437 
438         // act
439         final List<ConvexArea> result = tree.toConvex();
440 
441         // assert
442         Assertions.assertEquals(0, result.size());
443     }
444 
445     @Test
446     void testToConvex_halfSpace() {
447         // arrange
448         final RegionBSPTree2D tree = RegionBSPTree2D.full();
449         tree.getRoot().insertCut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
450 
451         // act
452         final List<ConvexArea> result = tree.toConvex();
453 
454         // assert
455         Assertions.assertEquals(1, result.size());
456 
457         final ConvexArea area = result.get(0);
458         Assertions.assertFalse(area.isFull());
459         Assertions.assertFalse(area.isEmpty());
460 
461         checkClassify(area, RegionLocation.INSIDE, Vector2D.of(0, 1));
462         checkClassify(area, RegionLocation.BOUNDARY, Vector2D.ZERO);
463         checkClassify(area, RegionLocation.OUTSIDE, Vector2D.of(0, -1));
464     }
465 
466     @Test
467     void testToConvex_quadrantComplement() {
468         // arrange
469         final RegionBSPTree2D tree = RegionBSPTree2D.full();
470         tree.getRoot().cut(Lines.fromPointAndAngle(Vector2D.ZERO, Math.PI, TEST_PRECISION))
471             .getPlus().cut(Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION));
472 
473         tree.complement();
474 
475         // act
476         final List<ConvexArea> result = tree.toConvex();
477 
478         // assert
479         Assertions.assertEquals(1, result.size());
480 
481         final ConvexArea area = result.get(0);
482         Assertions.assertFalse(area.isFull());
483         Assertions.assertFalse(area.isEmpty());
484 
485         checkClassify(area, RegionLocation.INSIDE, Vector2D.of(1, 1));
486         checkClassify(area, RegionLocation.BOUNDARY, Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1));
487         checkClassify(area, RegionLocation.OUTSIDE, Vector2D.of(1, -1), Vector2D.of(-1, -1), Vector2D.of(-1, 1));
488     }
489 
490     @Test
491     void testToConvex_square() {
492         // arrange
493         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).toTree();
494 
495         // act
496         final List<ConvexArea> result = tree.toConvex();
497 
498         // assert
499         Assertions.assertEquals(1, result.size());
500 
501         final ConvexArea area = result.get(0);
502         Assertions.assertFalse(area.isFull());
503         Assertions.assertFalse(area.isEmpty());
504 
505         Assertions.assertEquals(1, area.getSize(), TEST_EPS);
506         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), TEST_EPS);
507 
508         checkClassify(area, RegionLocation.INSIDE, Vector2D.of(0.5, 0.5));
509         checkClassify(area, RegionLocation.BOUNDARY, Vector2D.ZERO, Vector2D.of(1, 1));
510         checkClassify(area, RegionLocation.OUTSIDE,
511                 Vector2D.of(0.5, -1), Vector2D.of(0.5, 2),
512                 Vector2D.of(-1, 0.5), Vector2D.of(2, 0.5));
513     }
514 
515     @Test
516     void testToConvex_multipleConvexAreas() {
517         // arrange
518         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
519         tree.insert(Arrays.asList(
520                     Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION),
521 
522                     Lines.segmentFromPoints(Vector2D.of(1, 1), Vector2D.of(0, 1), TEST_PRECISION),
523                     Lines.segmentFromPoints(Vector2D.of(0, 1), Vector2D.ZERO, TEST_PRECISION),
524 
525                     Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 0), TEST_PRECISION),
526                     Lines.segmentFromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), TEST_PRECISION)
527                 ));
528 
529         // act
530         final List<ConvexArea> result = tree.toConvex();
531 
532         // assert
533         result.sort((a, b) ->
534                 Vector2D.COORDINATE_ASCENDING_ORDER.compare(a.getCentroid(), b.getCentroid()));
535 
536         Assertions.assertEquals(2, result.size());
537 
538         final ConvexArea firstArea = result.get(0);
539         Assertions.assertFalse(firstArea.isFull());
540         Assertions.assertFalse(firstArea.isEmpty());
541 
542         Assertions.assertEquals(0.5, firstArea.getSize(), TEST_EPS);
543         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.0 / 3.0, 2.0 / 3.0), firstArea.getCentroid(), TEST_EPS);
544 
545         checkClassify(firstArea, RegionLocation.INSIDE, Vector2D.of(1.0 / 3.0, 2.0 / 3.0));
546         checkClassify(firstArea, RegionLocation.BOUNDARY, Vector2D.ZERO, Vector2D.of(1, 1), Vector2D.of(0.5, 0.5));
547         checkClassify(firstArea, RegionLocation.OUTSIDE,
548                 Vector2D.of(0.25, -1), Vector2D.of(0.25, 2),
549                 Vector2D.of(-1, 0.5), Vector2D.of(0.75, 0.5));
550 
551         final ConvexArea secondArea = result.get(1);
552         Assertions.assertFalse(secondArea.isFull());
553         Assertions.assertFalse(secondArea.isEmpty());
554 
555         Assertions.assertEquals(0.5, secondArea.getSize(), TEST_EPS);
556         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2.0 / 3.0, 1.0 / 3.0), secondArea.getCentroid(), TEST_EPS);
557 
558         checkClassify(secondArea, RegionLocation.INSIDE, Vector2D.of(2.0 / 3.0, 1.0 / 3.0));
559         checkClassify(secondArea, RegionLocation.BOUNDARY, Vector2D.ZERO, Vector2D.of(1, 1), Vector2D.of(0.5, 0.5));
560         checkClassify(secondArea, RegionLocation.OUTSIDE,
561                 Vector2D.of(0.75, -1), Vector2D.of(0.75, 2),
562                 Vector2D.of(2, 0.5), Vector2D.of(0.25, 0.5));
563     }
564 
565     @Test
566     void testGetNodeRegion() {
567         // arrange
568         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
569 
570         final RegionNode2D root = tree.getRoot();
571         root.cut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
572 
573         final RegionNode2D minus = root.getMinus();
574         minus.cut(Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION));
575 
576         final Vector2D origin = Vector2D.ZERO;
577 
578         final Vector2D a = Vector2D.of(1, 0);
579         final Vector2D b = Vector2D.of(1, 1);
580         final Vector2D c = Vector2D.of(0, 1);
581         final Vector2D d = Vector2D.of(-1, 1);
582         final Vector2D e = Vector2D.of(-1, 0);
583         final Vector2D f = Vector2D.of(-1, -1);
584         final Vector2D g = Vector2D.of(0, -1);
585         final Vector2D h = Vector2D.of(1, -1);
586 
587         // act/assert
588         checkConvexArea(root.getNodeRegion(), Arrays.asList(origin, a, b, c, d, e, f, g, h), Collections.emptyList());
589 
590         checkConvexArea(minus.getNodeRegion(), Arrays.asList(b, c, d), Arrays.asList(f, g, h));
591         checkConvexArea(root.getPlus().getNodeRegion(), Arrays.asList(f, g, h), Arrays.asList(b, c, d));
592 
593         checkConvexArea(minus.getMinus().getNodeRegion(), Collections.singletonList(d), Arrays.asList(a, b, f, g, h));
594         checkConvexArea(minus.getPlus().getNodeRegion(), Collections.singletonList(b), Arrays.asList(d, e, f, g, h));
595     }
596 
597     @Test
598     void testSplit_full() {
599         // arrange
600         final RegionBSPTree2D tree = RegionBSPTree2D.full();
601 
602         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(1, 0), 0.25 * Math.PI, TEST_PRECISION);
603 
604         // act
605         final Split<RegionBSPTree2D> split = tree.split(splitter);
606 
607         // assert
608         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
609 
610         checkClassify(split.getMinus(), RegionLocation.INSIDE, Vector2D.of(0, 1));
611         checkClassify(split.getMinus(), RegionLocation.OUTSIDE, Vector2D.of(1, -1));
612 
613         final List<LinePath> minusBoundaryList = split.getMinus().getBoundaryPaths();
614         Assertions.assertEquals(1, minusBoundaryList.size());
615 
616         final LinePath minusBoundary = minusBoundaryList.get(0);
617         Assertions.assertEquals(1, minusBoundary.getElements().size());
618         Assertions.assertTrue(minusBoundary.isInfinite());
619         Assertions.assertSame(splitter, minusBoundary.getStart().getLine());
620 
621         checkClassify(split.getPlus(), RegionLocation.OUTSIDE, Vector2D.of(0, 1));
622         checkClassify(split.getPlus(), RegionLocation.INSIDE, Vector2D.of(1, -1));
623 
624         final List<LinePath> plusBoundaryList = split.getPlus().getBoundaryPaths();
625         Assertions.assertEquals(1, plusBoundaryList.size());
626 
627         final LinePath plusBoundary = minusBoundaryList.get(0);
628         Assertions.assertEquals(1, plusBoundary.getElements().size());
629         Assertions.assertTrue(plusBoundary.isInfinite());
630         Assertions.assertSame(splitter, plusBoundary.getStart().getLine());
631     }
632 
633     @Test
634     void testSplit_empty() {
635         // arrange
636         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
637 
638         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(1, 0), 0.25 * Math.PI, TEST_PRECISION);
639 
640         // act
641         final Split<RegionBSPTree2D> split = tree.split(splitter);
642 
643         // assert
644         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
645 
646         Assertions.assertNull(split.getMinus());
647         Assertions.assertNull(split.getPlus());
648     }
649 
650     @Test
651     void testSplit_bothSides() {
652         // arrange
653         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(2, 1), TEST_PRECISION)
654                 .toTree();
655 
656         final Line splitter = Lines.fromPointAndAngle(Vector2D.ZERO, 0.25 * Math.PI, TEST_PRECISION);
657 
658         // act
659         final Split<RegionBSPTree2D> split = tree.split(splitter);
660 
661         // assert
662         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
663 
664         final List<LinePath> minusPath = split.getMinus().getBoundaryPaths();
665         Assertions.assertEquals(1, minusPath.size());
666         checkVertices(minusPath.get(0), Vector2D.ZERO, Vector2D.of(1, 1),
667                 Vector2D.of(0, 1), Vector2D.ZERO);
668 
669         final List<LinePath> plusPath = split.getPlus().getBoundaryPaths();
670         Assertions.assertEquals(1, plusPath.size());
671         checkVertices(plusPath.get(0), Vector2D.ZERO, Vector2D.of(2, 0),
672                 Vector2D.of(2, 1), Vector2D.of(1, 1), Vector2D.ZERO);
673     }
674 
675     @Test
676     void testSplit_plusSideOnly() {
677         // arrange
678         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(2, 1), TEST_PRECISION)
679                 .toTree();
680 
681         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.25 * Math.PI, TEST_PRECISION);
682 
683         // act
684         final Split<RegionBSPTree2D> split = tree.split(splitter);
685 
686         // assert
687         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
688 
689         Assertions.assertNull(split.getMinus());
690 
691         final List<LinePath> plusPath = split.getPlus().getBoundaryPaths();
692         Assertions.assertEquals(1, plusPath.size());
693         checkVertices(plusPath.get(0), Vector2D.ZERO, Vector2D.of(2, 0),
694                 Vector2D.of(2, 1), Vector2D.of(0, 1), Vector2D.ZERO);
695     }
696 
697     @Test
698     void testSplit_minusSideOnly() {
699         // arrange
700         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(2, 1), TEST_PRECISION)
701                 .toTree();
702 
703         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.25 * Math.PI, TEST_PRECISION)
704                 .reverse();
705 
706         // act
707         final Split<RegionBSPTree2D> split = tree.split(splitter);
708 
709         // assert
710         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
711 
712         final List<LinePath> minusPath = split.getMinus().getBoundaryPaths();
713         Assertions.assertEquals(1, minusPath.size());
714         checkVertices(minusPath.get(0), Vector2D.ZERO, Vector2D.of(2, 0),
715                 Vector2D.of(2, 1), Vector2D.of(0, 1), Vector2D.ZERO);
716 
717         Assertions.assertNull(split.getPlus());
718     }
719 
720     @Test
721     void testGeometricProperties_full() {
722         // arrange
723         final RegionBSPTree2D tree = RegionBSPTree2D.full();
724 
725         // act/assert
726         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
727         Assertions.assertNull(tree.getCentroid());
728 
729         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
730 
731         Assertions.assertEquals(0, tree.getBoundaries().size());
732         Assertions.assertEquals(0, tree.getBoundaryPaths().size());
733     }
734 
735     @Test
736     void testGeometricProperties_empty() {
737         // arrange
738         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
739 
740         // act/assert
741         Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
742         Assertions.assertNull(tree.getCentroid());
743 
744         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
745 
746         Assertions.assertEquals(0, tree.getBoundaries().size());
747         Assertions.assertEquals(0, tree.getBoundaryPaths().size());
748     }
749 
750     @Test
751     void testGeometricProperties_halfSpace() {
752         // arrange
753         final RegionBSPTree2D tree = RegionBSPTree2D.full();
754         tree.getRoot().cut(X_AXIS);
755 
756         // act/assert
757         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
758         Assertions.assertNull(tree.getCentroid());
759 
760         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
761 
762         final List<LineConvexSubset> segments = tree.getBoundaries();
763         Assertions.assertEquals(1, segments.size());
764 
765         final LineConvexSubset segment = segments.get(0);
766         Assertions.assertSame(X_AXIS, segment.getLine());
767         Assertions.assertNull(segment.getStartPoint());
768         Assertions.assertNull(segment.getEndPoint());
769 
770         final List<LinePath> paths = tree.getBoundaryPaths();
771         Assertions.assertEquals(1, paths.size());
772 
773         final LinePath path = paths.get(0);
774         Assertions.assertEquals(1, path.getElements().size());
775         assertSegmentsEqual(segment, path.getStart());
776     }
777 
778     @Test
779     void testGeometricProperties_complementedHalfSpace() {
780         // arrange
781         final RegionBSPTree2D tree = RegionBSPTree2D.full();
782         tree.getRoot().cut(X_AXIS);
783 
784         tree.complement();
785 
786         // act/assert
787         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
788         Assertions.assertNull(tree.getCentroid());
789 
790         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
791 
792         final List<LineConvexSubset> segments = tree.getBoundaries();
793         Assertions.assertEquals(1, segments.size());
794 
795         final LineConvexSubset segment = segments.get(0);
796         Assertions.assertEquals(X_AXIS.reverse(), segment.getLine());
797         Assertions.assertNull(segment.getStartPoint());
798         Assertions.assertNull(segment.getEndPoint());
799 
800         final List<LinePath> paths = tree.getBoundaryPaths();
801         Assertions.assertEquals(1, paths.size());
802 
803         final LinePath path = paths.get(0);
804         Assertions.assertEquals(1, path.getElements().size());
805         assertSegmentsEqual(segment, path.getElements().get(0));
806     }
807 
808     @Test
809     void testGeometricProperties_quadrant() {
810         // arrange
811         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
812         tree.getRoot().cut(X_AXIS)
813             .getMinus().cut(Y_AXIS);
814 
815         // act/assert
816         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
817         Assertions.assertNull(tree.getCentroid());
818 
819         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
820 
821         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
822         Assertions.assertEquals(2, segments.size());
823 
824         segments.sort(SEGMENT_COMPARATOR);
825 
826         final LineConvexSubset firstSegment = segments.get(0);
827         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, firstSegment.getStartPoint(), TEST_EPS);
828         Assertions.assertNull(firstSegment.getEndPoint());
829         Assertions.assertSame(Y_AXIS, firstSegment.getLine());
830 
831         final LineConvexSubset secondSegment = segments.get(1);
832         Assertions.assertNull(secondSegment.getStartPoint());
833         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, secondSegment.getEndPoint(), TEST_EPS);
834         Assertions.assertSame(X_AXIS, secondSegment.getLine());
835 
836         final List<LinePath> paths = tree.getBoundaryPaths();
837         Assertions.assertEquals(1, paths.size());
838 
839         final LinePath path = paths.get(0);
840         Assertions.assertEquals(2, path.getElements().size());
841         assertSegmentsEqual(secondSegment, path.getElements().get(0));
842         assertSegmentsEqual(firstSegment, path.getElements().get(1));
843     }
844 
845     @Test
846     void testGeometricProperties_mixedCutRule() {
847         // arrange
848         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
849 
850         tree.getRoot().cut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.25 * Math.PI, TEST_PRECISION),
851                 RegionCutRule.INHERIT);
852 
853         tree.getRoot()
854             .getPlus().cut(X_AXIS, RegionCutRule.MINUS_INSIDE)
855                 .getMinus().cut(Lines.fromPointAndAngle(Vector2D.of(1, 0), 0.5 * Math.PI, TEST_PRECISION));
856 
857         tree.getRoot()
858             .getMinus().cut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.5 * Math.PI, TEST_PRECISION), RegionCutRule.PLUS_INSIDE)
859                 .getPlus().cut(Lines.fromPointAndAngle(Vector2D.of(1, 1), Math.PI, TEST_PRECISION))
860                     .getMinus().cut(Lines.fromPointAndAngle(Vector2D.of(0.5, 0.5), 0.75 * Math.PI, TEST_PRECISION), RegionCutRule.INHERIT);
861 
862         // act/assert
863         Assertions.assertEquals(1, tree.getSize(), TEST_EPS);
864         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), tree.getCentroid(), TEST_EPS);
865 
866         Assertions.assertEquals(4, tree.getBoundarySize(), TEST_EPS);
867 
868         final List<LinePath> paths = tree.getBoundaryPaths();
869         Assertions.assertEquals(1, paths.size());
870 
871         final LinePath path = paths.get(0);
872         Assertions.assertEquals(4, path.getElements().size());
873 
874         final List<Vector2D> vertices = path.getVertexSequence();
875         Assertions.assertEquals(5, vertices.size());
876         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(0), TEST_EPS);
877         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), vertices.get(1), TEST_EPS);
878         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), vertices.get(2), TEST_EPS);
879         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 1), vertices.get(3), TEST_EPS);
880         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(4), TEST_EPS);
881     }
882 
883     @Test
884     void testGeometricProperties_complementedQuadrant() {
885         // arrange
886         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
887         tree.getRoot().cut(X_AXIS)
888             .getMinus().cut(Y_AXIS);
889 
890         tree.complement();
891 
892         // act/assert
893         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
894         Assertions.assertNull(tree.getCentroid());
895 
896         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
897 
898         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
899         Assertions.assertEquals(2, segments.size());
900 
901         segments.sort(SEGMENT_COMPARATOR);
902 
903         final LineConvexSubset firstSegment = segments.get(0);
904         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, firstSegment.getStartPoint(), TEST_EPS);
905         Assertions.assertNull(firstSegment.getEndPoint());
906         Assertions.assertEquals(X_AXIS.reverse(), firstSegment.getLine());
907 
908         final LineConvexSubset secondSegment = segments.get(1);
909         Assertions.assertNull(secondSegment.getStartPoint());
910         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, secondSegment.getEndPoint(), TEST_EPS);
911         Assertions.assertEquals(Y_AXIS.reverse(), secondSegment.getLine());
912 
913         final List<LinePath> paths = tree.getBoundaryPaths();
914         Assertions.assertEquals(1, paths.size());
915 
916         final LinePath path = paths.get(0);
917         Assertions.assertEquals(2, path.getElements().size());
918         assertSegmentsEqual(secondSegment, path.getElements().get(0));
919         assertSegmentsEqual(firstSegment, path.getElements().get(1));
920     }
921 
922     @Test
923     void testGeometricProperties_closedRegion() {
924         // arrange
925         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
926         tree.insert(LinePath.builder(TEST_PRECISION)
927                 .appendVertices(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(2, 1))
928                 .close());
929 
930         // act/assert
931         Assertions.assertEquals(0.5, tree.getSize(), TEST_EPS);
932         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1.0 / 3.0), tree.getCentroid(), TEST_EPS);
933 
934         Assertions.assertEquals(1.0 + Math.sqrt(2) + Math.sqrt(5), tree.getBoundarySize(), TEST_EPS);
935 
936         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
937         segments.sort(SEGMENT_COMPARATOR);
938 
939         Assertions.assertEquals(3, segments.size());
940 
941         checkFiniteSegment(segments.get(0), Vector2D.ZERO, Vector2D.of(1, 0));
942         checkFiniteSegment(segments.get(1), Vector2D.of(1, 0), Vector2D.of(2, 1));
943         checkFiniteSegment(segments.get(2), Vector2D.of(2, 1), Vector2D.ZERO);
944 
945         final List<LinePath> paths = tree.getBoundaryPaths();
946         Assertions.assertEquals(1, paths.size());
947 
948         checkVertices(paths.get(0), Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(2, 1), Vector2D.ZERO);
949     }
950 
951     @Test
952     void testGeometricProperties_complementedClosedRegion() {
953         // arrange
954         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
955         tree.insert(LinePath.builder(TEST_PRECISION)
956                 .appendVertices(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(2, 1))
957                 .close());
958 
959         tree.complement();
960 
961         // act/assert
962         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
963         Assertions.assertNull(tree.getCentroid());
964 
965         Assertions.assertEquals(1.0 + Math.sqrt(2) + Math.sqrt(5), tree.getBoundarySize(), TEST_EPS);
966 
967         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
968         segments.sort(SEGMENT_COMPARATOR);
969 
970         Assertions.assertEquals(3, segments.size());
971 
972         checkFiniteSegment(segments.get(0), Vector2D.ZERO, Vector2D.of(2, 1));
973         checkFiniteSegment(segments.get(1), Vector2D.of(1, 0), Vector2D.ZERO);
974         checkFiniteSegment(segments.get(2), Vector2D.of(2, 1), Vector2D.of(1, 0));
975 
976         final List<LinePath> paths = tree.getBoundaryPaths();
977         Assertions.assertEquals(1, paths.size());
978 
979         checkVertices(paths.get(0), Vector2D.ZERO, Vector2D.of(2, 1), Vector2D.of(1, 0), Vector2D.ZERO);
980     }
981 
982     @Test
983     void testGeometricProperties_regionWithHole() {
984         // arrange
985         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(3, 3), TEST_PRECISION)
986                 .toTree();
987         final RegionBSPTree2D inner = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION)
988                 .toTree();
989 
990         tree.difference(inner);
991 
992         // act/assert
993         Assertions.assertEquals(8, tree.getSize(), TEST_EPS);
994         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 1.5), tree.getCentroid(), TEST_EPS);
995 
996         Assertions.assertEquals(16, tree.getBoundarySize(), TEST_EPS);
997 
998         final List<LinePath> paths = tree.getBoundaryPaths();
999         Assertions.assertEquals(2, paths.size());
1000 
1001         checkVertices(paths.get(0), Vector2D.of(0, 3), Vector2D.ZERO, Vector2D.of(3, 0),
1002                 Vector2D.of(3, 3), Vector2D.of(0, 3));
1003         checkVertices(paths.get(1), Vector2D.of(1, 1), Vector2D.of(1, 2), Vector2D.of(2, 2),
1004                 Vector2D.of(2, 1), Vector2D.of(1, 1));
1005     }
1006 
1007     @Test
1008     void testGeometricProperties_complementedRegionWithHole() {
1009         // arrange
1010         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(3, 3), TEST_PRECISION)
1011                 .toTree();
1012         final RegionBSPTree2D inner = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION)
1013                 .toTree();
1014 
1015         tree.difference(inner);
1016 
1017         tree.complement();
1018 
1019         // act/assert
1020         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
1021         Assertions.assertNull(tree.getCentroid());
1022 
1023         Assertions.assertEquals(16, tree.getBoundarySize(), TEST_EPS);
1024 
1025         final List<LinePath> paths = tree.getBoundaryPaths();
1026         Assertions.assertEquals(2, paths.size());
1027 
1028         checkVertices(paths.get(0), Vector2D.ZERO, Vector2D.of(0, 3), Vector2D.of(3, 3),
1029                 Vector2D.of(3, 0), Vector2D.ZERO);
1030         checkVertices(paths.get(1), Vector2D.of(1, 1), Vector2D.of(2, 1), Vector2D.of(2, 2),
1031                 Vector2D.of(1, 2), Vector2D.of(1, 1));
1032     }
1033 
1034     @Test
1035     void testFrom_boundaries() {
1036         // act
1037         final RegionBSPTree2D tree = RegionBSPTree2D.from(Arrays.asList(
1038                     Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION).span(),
1039                     Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION)
1040                         .rayFrom(Vector2D.ZERO)
1041                 ));
1042 
1043         // assert
1044         Assertions.assertFalse(tree.isFull());
1045         Assertions.assertFalse(tree.isEmpty());
1046 
1047         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
1048 
1049         checkClassify(tree, RegionLocation.INSIDE, Vector2D.of(-1, 1));
1050         checkClassify(tree, RegionLocation.OUTSIDE,
1051                 Vector2D.of(1, 1), Vector2D.of(1, -1), Vector2D.of(-1, -1));
1052     }
1053 
1054     @Test
1055     void testFrom_boundaries_fullIsTrue() {
1056         // act
1057         final RegionBSPTree2D tree = RegionBSPTree2D.from(Arrays.asList(
1058                     Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION).span(),
1059                     Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION)
1060                         .rayFrom(Vector2D.ZERO)
1061                 ), true);
1062 
1063         // assert
1064         Assertions.assertFalse(tree.isFull());
1065         Assertions.assertFalse(tree.isEmpty());
1066 
1067         Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
1068 
1069         checkClassify(tree, RegionLocation.INSIDE, Vector2D.of(-1, 1));
1070         checkClassify(tree, RegionLocation.OUTSIDE,
1071                 Vector2D.of(1, 1), Vector2D.of(1, -1), Vector2D.of(-1, -1));
1072     }
1073 
1074     @Test
1075     void testFrom_boundaries_noBoundaries() {
1076         // act/assert
1077         Assertions.assertTrue(RegionBSPTree2D.from(Collections.emptyList()).isEmpty());
1078         Assertions.assertTrue(RegionBSPTree2D.from(Collections.emptyList(), true).isFull());
1079         Assertions.assertTrue(RegionBSPTree2D.from(Collections.emptyList(), false).isEmpty());
1080     }
1081 
1082     @Test
1083     void testToList() {
1084         // arrange
1085         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).toTree();
1086 
1087         // act
1088         final BoundaryList2D list = tree.toList();
1089 
1090         // assert
1091         Assertions.assertEquals(4, list.toList().count());
1092         Assertions.assertEquals(1, list.toTree().getSize(), TEST_EPS);
1093     }
1094 
1095     @Test
1096     void testToList_fullAndEmpty() {
1097         // act/assert
1098         Assertions.assertEquals(0, RegionBSPTree2D.full().toList().count());
1099         Assertions.assertEquals(0, RegionBSPTree2D.empty().toList().count());
1100     }
1101 
1102     @Test
1103     void testToTree_returnsSameInstance() {
1104         // arrange
1105         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 2), TEST_PRECISION).toTree();
1106 
1107         // act/assert
1108         Assertions.assertSame(tree, tree.toTree());
1109     }
1110 
1111     @Test
1112     void testProject_fullAndEmpty() {
1113         // act/assert
1114         Assertions.assertNull(RegionBSPTree2D.full().project(Vector2D.ZERO));
1115         Assertions.assertNull(RegionBSPTree2D.empty().project(Vector2D.of(1, 2)));
1116     }
1117 
1118     @Test
1119     void testProject_halfSpace() {
1120         // arrange
1121         final RegionBSPTree2D tree = RegionBSPTree2D.full();
1122         tree.getRoot().cut(X_AXIS);
1123 
1124         // act/assert
1125         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, tree.project(Vector2D.ZERO), TEST_EPS);
1126         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-1, 0), tree.project(Vector2D.of(-1, 0)), TEST_EPS);
1127         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 0),
1128                 tree.project(Vector2D.of(2, -1)), TEST_EPS);
1129         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-3, 0),
1130                 tree.project(Vector2D.of(-3, 1)), TEST_EPS);
1131     }
1132 
1133     @Test
1134     void testProject_rect() {
1135         // arrange
1136         final RegionBSPTree2D tree = Parallelogram.axisAligned(
1137                     Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).toTree();
1138 
1139         // act/assert
1140         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), tree.project(Vector2D.ZERO), TEST_EPS);
1141         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), tree.project(Vector2D.of(1, 0)), TEST_EPS);
1142         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 1), tree.project(Vector2D.of(1.5, 0)), TEST_EPS);
1143         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 1), tree.project(Vector2D.of(2, 0)), TEST_EPS);
1144         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 1), tree.project(Vector2D.of(3, 0)), TEST_EPS);
1145 
1146         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 2), tree.project(Vector2D.of(1, 3)), TEST_EPS);
1147         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 2), tree.project(Vector2D.of(1, 3)), TEST_EPS);
1148         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 2), tree.project(Vector2D.of(1.5, 3)), TEST_EPS);
1149         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 2), tree.project(Vector2D.of(2, 3)), TEST_EPS);
1150         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 2), tree.project(Vector2D.of(3, 3)), TEST_EPS);
1151 
1152         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1.5), tree.project(Vector2D.of(0, 1.5)), TEST_EPS);
1153         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1.5), tree.project(Vector2D.of(1.5, 1.5)), TEST_EPS);
1154         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 1.5), tree.project(Vector2D.of(3, 1.5)), TEST_EPS);
1155     }
1156 
1157     @Test
1158     void testLinecast_empty() {
1159         // arrange
1160         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
1161 
1162         // act/assert
1163         LinecastChecker2D.with(tree)
1164             .expectNothing()
1165             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
1166 
1167         LinecastChecker2D.with(tree)
1168             .expectNothing()
1169             .whenGiven(Lines.segmentFromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
1170     }
1171 
1172     @Test
1173     void testLinecast_full() {
1174         // arrange
1175         final RegionBSPTree2D tree = RegionBSPTree2D.full();
1176 
1177         // act/assert
1178         LinecastChecker2D.with(tree)
1179             .expectNothing()
1180             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
1181 
1182         LinecastChecker2D.with(tree)
1183             .expectNothing()
1184             .whenGiven(Lines.segmentFromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
1185     }
1186 
1187     @Test
1188     void testLinecast() {
1189         // arrange
1190         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
1191                 .toTree();
1192 
1193         // act/assert
1194         LinecastChecker2D.with(tree)
1195             .expectNothing()
1196             .whenGiven(Lines.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
1197 
1198         LinecastChecker2D.with(tree)
1199             .expect(Vector2D.ZERO, Vector2D.Unit.MINUS_X)
1200             .and(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
1201             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
1202             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
1203             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
1204 
1205         LinecastChecker2D.with(tree)
1206             .expect(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
1207             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
1208             .whenGiven(Lines.segmentFromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
1209     }
1210 
1211     @Test
1212     void testLinecast_complementedTree() {
1213         // arrange
1214         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
1215                 .toTree();
1216 
1217         tree.complement();
1218 
1219         // act/assert
1220         LinecastChecker2D.with(tree)
1221             .expectNothing()
1222             .whenGiven(Lines.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
1223 
1224         LinecastChecker2D.with(tree)
1225             .expect(Vector2D.ZERO, Vector2D.Unit.PLUS_Y)
1226             .and(Vector2D.ZERO, Vector2D.Unit.PLUS_X)
1227             .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X)
1228             .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_Y)
1229             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
1230 
1231         LinecastChecker2D.with(tree)
1232             .expect(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X)
1233             .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_Y)
1234             .whenGiven(Lines.segmentFromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
1235     }
1236 
1237     @Test
1238     void testLinecast_complexRegion() {
1239         // arrange
1240         final RegionBSPTree2D a = LinePath.fromVertexLoop(Arrays.asList(
1241                     Vector2D.ZERO, Vector2D.of(0, 1),
1242                     Vector2D.of(0.5, 1), Vector2D.of(0.5, 0)
1243                 ), TEST_PRECISION).toTree();
1244         a.complement();
1245 
1246         final RegionBSPTree2D b = LinePath.fromVertexLoop(Arrays.asList(
1247                 Vector2D.of(0.5, 0), Vector2D.of(0.5, 1),
1248                 Vector2D.of(1, 1), Vector2D.of(1, 0)
1249             ), TEST_PRECISION).toTree();
1250         b.complement();
1251 
1252         final RegionBSPTree2D c = LinePath.fromVertexLoop(Arrays.asList(
1253                 Vector2D.of(0.5, 0.5), Vector2D.of(1.5, 0.5),
1254                 Vector2D.of(1.5, 1.5), Vector2D.of(0.5, 1.5)
1255             ), TEST_PRECISION).toTree();
1256 
1257         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
1258         tree.union(a, b);
1259         tree.union(c);
1260 
1261         // act/assert
1262         LinecastChecker2D.with(tree)
1263             .expect(Vector2D.of(1.5, 1.5), Vector2D.Unit.PLUS_Y)
1264             .and(Vector2D.of(1.5, 1.5), Vector2D.Unit.PLUS_X)
1265             .whenGiven(Lines.segmentFromPoints(Vector2D.of(0.25, 0.25), Vector2D.of(2, 2), TEST_PRECISION));
1266     }
1267 
1268     @Test
1269     void testLinecast_removesDuplicatePoints() {
1270         // arrange
1271         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
1272         tree.insert(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION).span());
1273         tree.insert(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION).span());
1274 
1275         // act/assert
1276         LinecastChecker2D.with(tree)
1277             .expect(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
1278             .whenGiven(Lines.fromPoints(Vector2D.of(1, 1), Vector2D.of(-1, -1), TEST_PRECISION));
1279 
1280         LinecastChecker2D.with(tree)
1281             .expect(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
1282             .whenGiven(Lines.segmentFromPoints(Vector2D.of(1, 1), Vector2D.of(-1, -1), TEST_PRECISION));
1283     }
1284 
1285     @Test
1286     void testTransform() {
1287         // arrange
1288         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(3, 2), TEST_PRECISION)
1289                 .toTree();
1290 
1291         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.createScale(0.5, 2)
1292                 .rotate(Angle.PI_OVER_TWO)
1293                 .translate(Vector2D.of(0, -1));
1294 
1295         // act
1296         tree.transform(transform);
1297 
1298         // assert
1299         final List<LinePath> paths = tree.getBoundaryPaths();
1300         Assertions.assertEquals(1, paths.size());
1301 
1302         final LinePath path = paths.get(0);
1303         Assertions.assertEquals(4, path.getElements().size());
1304         checkFiniteSegment(path.getElements().get(0), Vector2D.of(-4, -0.5), Vector2D.of(-2, -0.5));
1305         checkFiniteSegment(path.getElements().get(1), Vector2D.of(-2, -0.5), Vector2D.of(-2, 0.5));
1306         checkFiniteSegment(path.getElements().get(2), Vector2D.of(-2, 0.5), Vector2D.of(-4, 0.5));
1307         checkFiniteSegment(path.getElements().get(3), Vector2D.of(-4, 0.5), Vector2D.of(-4, -0.5));
1308     }
1309 
1310     @Test
1311     void testTransform_halfSpace() {
1312         // arrange
1313         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
1314         tree.getRoot().insertCut(Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION));
1315 
1316         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.createScale(0.5, 2)
1317                 .rotate(Angle.PI_OVER_TWO)
1318                 .translate(Vector2D.of(1, 0));
1319 
1320         // act
1321         tree.transform(transform);
1322 
1323         // assert
1324         final List<LinePath> paths = tree.getBoundaryPaths();
1325         Assertions.assertEquals(1, paths.size());
1326 
1327         final LinePath path = paths.get(0);
1328         Assertions.assertEquals(1, path.getElements().size());
1329         final LineConvexSubset segment = path.getStart();
1330         Assertions.assertNull(segment.getStartPoint());
1331         Assertions.assertNull(segment.getEndPoint());
1332 
1333         final Line expectedLine = Lines.fromPointAndAngle(Vector2D.of(-1, 0), Angle.PI_OVER_TWO, TEST_PRECISION);
1334         Assertions.assertTrue(expectedLine.eq(segment.getLine(), expectedLine.getPrecision()));
1335     }
1336 
1337     @Test
1338     void testTransform_fullAndEmpty() {
1339         // arrange
1340         final RegionBSPTree2D full = RegionBSPTree2D.full();
1341         final RegionBSPTree2D empty = RegionBSPTree2D.empty();
1342 
1343         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.createRotation(Angle.PI_OVER_TWO);
1344 
1345         // act
1346         full.transform(transform);
1347         empty.transform(transform);
1348 
1349         // assert
1350         Assertions.assertTrue(full.isFull());
1351         Assertions.assertTrue(empty.isEmpty());
1352     }
1353 
1354     @Test
1355     void testTransform_reflection() {
1356         // arrange
1357         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).toTree();
1358 
1359         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.from(v -> Vector2D.of(-v.getX(), v.getY()));
1360 
1361         // act
1362         tree.transform(transform);
1363 
1364         // assert
1365         final List<LinePath> paths = tree.getBoundaryPaths();
1366         Assertions.assertEquals(1, paths.size());
1367 
1368         final LinePath path = paths.get(0);
1369         Assertions.assertEquals(4, path.getElements().size());
1370         checkFiniteSegment(path.getElements().get(0), Vector2D.of(-2, 1), Vector2D.of(-1, 1));
1371         checkFiniteSegment(path.getElements().get(1), Vector2D.of(-1, 1), Vector2D.of(-1, 2));
1372         checkFiniteSegment(path.getElements().get(2), Vector2D.of(-1, 2), Vector2D.of(-2, 2));
1373         checkFiniteSegment(path.getElements().get(3), Vector2D.of(-2, 2), Vector2D.of(-2, 1));
1374     }
1375 
1376     @Test
1377     void testTransform_doubleReflection() {
1378         // arrange
1379         final RegionBSPTree2D tree = Parallelogram.axisAligned(
1380                     Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).toTree();
1381 
1382         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.from(Vector2D::negate);
1383 
1384         // act
1385         tree.transform(transform);
1386 
1387         // assert
1388         final List<LinePath> paths = tree.getBoundaryPaths();
1389         Assertions.assertEquals(1, paths.size());
1390 
1391         final LinePath path = paths.get(0);
1392         Assertions.assertEquals(4, path.getElements().size());
1393         checkFiniteSegment(path.getElements().get(0), Vector2D.of(-2, -2), Vector2D.of(-1, -2));
1394         checkFiniteSegment(path.getElements().get(1), Vector2D.of(-1, -2), Vector2D.of(-1, -1));
1395         checkFiniteSegment(path.getElements().get(2), Vector2D.of(-1, -1), Vector2D.of(-2, -1));
1396         checkFiniteSegment(path.getElements().get(3), Vector2D.of(-2, -1), Vector2D.of(-2, -2));
1397     }
1398 
1399     @Test
1400     void testBooleanOperations() {
1401         // arrange
1402         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(3, 3), TEST_PRECISION).toTree();
1403         RegionBSPTree2D temp;
1404 
1405         // act
1406         temp = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).toTree();
1407         temp.complement();
1408         tree.intersection(temp);
1409 
1410         temp = Parallelogram.axisAligned(Vector2D.of(3, 0), Vector2D.of(6, 3), TEST_PRECISION).toTree();
1411         tree.union(temp);
1412 
1413         temp = Parallelogram.axisAligned(Vector2D.of(2, 1), Vector2D.of(5, 2), TEST_PRECISION).toTree();
1414         tree.difference(temp);
1415 
1416         temp.setFull();
1417         tree.xor(temp);
1418 
1419         // assert
1420         final List<LinePath> paths = tree.getBoundaryPaths();
1421         Assertions.assertEquals(2, paths.size());
1422 
1423         checkVertices(paths.get(0), Vector2D.ZERO, Vector2D.of(0, 3), Vector2D.of(6, 3),
1424                 Vector2D.of(6, 0), Vector2D.ZERO);
1425 
1426         checkVertices(paths.get(1), Vector2D.of(1, 1), Vector2D.of(5, 1), Vector2D.of(5, 2),
1427                 Vector2D.of(1, 2), Vector2D.of(1, 1));
1428     }
1429 
1430     private static void assertSegmentsEqual(final LineConvexSubset expected, final LineConvexSubset actual) {
1431         Assertions.assertEquals(expected.getLine(), actual.getLine());
1432 
1433         final Vector2D expectedStart = expected.getStartPoint();
1434         final Vector2D expectedEnd = expected.getEndPoint();
1435 
1436         if (expectedStart != null) {
1437             EuclideanTestUtils.assertCoordinatesEqual(expectedStart, actual.getStartPoint(), TEST_EPS);
1438         } else {
1439             Assertions.assertNull(actual.getStartPoint());
1440         }
1441 
1442         if (expectedEnd != null) {
1443             EuclideanTestUtils.assertCoordinatesEqual(expectedEnd, actual.getEndPoint(), TEST_EPS);
1444         } else {
1445             Assertions.assertNull(actual.getEndPoint());
1446         }
1447     }
1448 
1449     private static void checkFiniteSegment(final LineConvexSubset segment, final Vector2D start, final Vector2D end) {
1450         EuclideanTestUtils.assertCoordinatesEqual(start, segment.getStartPoint(), TEST_EPS);
1451         EuclideanTestUtils.assertCoordinatesEqual(end, segment.getEndPoint(), TEST_EPS);
1452     }
1453 
1454     private static void checkClassify(final Region<Vector2D> region, final RegionLocation loc, final Vector2D... points) {
1455         for (final Vector2D point : points) {
1456             final String msg = "Unexpected location for point " + point;
1457 
1458             Assertions.assertEquals(loc, region.classify(point), msg);
1459         }
1460     }
1461 
1462     private static void checkConvexArea(final ConvexArea area, final List<Vector2D> inside, final List<Vector2D> outside) {
1463         checkClassify(area, RegionLocation.INSIDE, inside.toArray(new Vector2D[0]));
1464         checkClassify(area, RegionLocation.OUTSIDE, outside.toArray(new Vector2D[0]));
1465     }
1466 
1467     /** Assert that the given path is finite and contains the given vertices.
1468      * @param path
1469      * @param vertices
1470      */
1471     private static void checkVertices(final LinePath path, final Vector2D... vertices) {
1472         Assertions.assertTrue(path.isFinite(), "Line segment path is not finite");
1473 
1474         final List<Vector2D> actual = path.getVertexSequence();
1475 
1476         Assertions.assertEquals(vertices.length, actual.size(), "Vertex lists have different lengths");
1477 
1478         for (int i  = 0; i < vertices.length; ++i) {
1479             EuclideanTestUtils.assertCoordinatesEqual(vertices[i], actual.get(i), TEST_EPS);
1480         }
1481     }
1482 }