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.core.partitioning.bsp;
18  
19  import java.util.ArrayList;
20  import java.util.Arrays;
21  import java.util.Collections;
22  import java.util.List;
23  import java.util.function.Consumer;
24  import java.util.function.Function;
25  import java.util.stream.Stream;
26  
27  import org.apache.commons.geometry.core.GeometryTestUtils;
28  import org.apache.commons.geometry.core.RegionLocation;
29  import org.apache.commons.geometry.core.Transform;
30  import org.apache.commons.geometry.core.partitioning.BoundarySource;
31  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
32  import org.apache.commons.geometry.core.partitioning.Split;
33  import org.apache.commons.geometry.core.partitioning.SplitLocation;
34  import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree.RegionSizeProperties;
35  import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
36  import org.apache.commons.geometry.core.partitioning.test.TestLine;
37  import org.apache.commons.geometry.core.partitioning.test.TestLineSegment;
38  import org.apache.commons.geometry.core.partitioning.test.TestLineSegmentCollection;
39  import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
40  import org.apache.commons.geometry.core.partitioning.test.TestRegionBSPTree;
41  import org.apache.commons.geometry.core.partitioning.test.TestRegionBSPTree.TestRegionNode;
42  import org.apache.commons.geometry.core.partitioning.test.TestTransform2D;
43  import org.junit.jupiter.api.Assertions;
44  import org.junit.jupiter.api.BeforeEach;
45  import org.junit.jupiter.api.Test;
46  
47  class AbstractRegionBSPTreeTest {
48  
49      private TestRegionBSPTree tree;
50  
51      private TestRegionNode root;
52  
53      @BeforeEach
54      public void setup() {
55          tree = new TestRegionBSPTree();
56          root = tree.getRoot();
57      }
58  
59      @Test
60      void testDefaultConstructor() {
61          // assert
62          Assertions.assertNotNull(root);
63          Assertions.assertNull(root.getParent());
64  
65          PartitionTestUtils.assertIsLeafNode(root);
66          Assertions.assertFalse(root.isPlus());
67          Assertions.assertFalse(root.isMinus());
68  
69          Assertions.assertSame(tree, root.getTree());
70  
71          Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
72      }
73  
74      @Test
75      void testParameterizedConstructor_true() {
76          // act
77          tree = new TestRegionBSPTree(true);
78          root = tree.getRoot();
79  
80          // assert
81          Assertions.assertNotNull(root);
82          Assertions.assertNull(root.getParent());
83  
84          PartitionTestUtils.assertIsLeafNode(root);
85          Assertions.assertFalse(root.isPlus());
86          Assertions.assertFalse(root.isMinus());
87  
88          Assertions.assertSame(tree, root.getTree());
89  
90          Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
91      }
92  
93      @Test
94      void testParameterizedConstructor_false() {
95          // act
96          tree = new TestRegionBSPTree(false);
97          root = tree.getRoot();
98  
99          // assert
100         Assertions.assertNotNull(root);
101         Assertions.assertNull(root.getParent());
102 
103         PartitionTestUtils.assertIsLeafNode(root);
104         Assertions.assertFalse(root.isPlus());
105         Assertions.assertFalse(root.isMinus());
106 
107         Assertions.assertSame(tree, root.getTree());
108 
109         Assertions.assertEquals(RegionLocation.OUTSIDE, root.getLocation());
110     }
111 
112     @Test
113     void testInsert_hyperplaneSubsets_mixedCutRules() {
114         // act/assert
115         checkMixedCutRuleInsertion(segs -> {
116             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[0])), RegionCutRule.PLUS_INSIDE);
117             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[1]))); // default rule
118             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[2])), RegionCutRule.PLUS_INSIDE);
119             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[3])), RegionCutRule.MINUS_INSIDE);
120             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[4])), RegionCutRule.INHERIT);
121         });
122 
123     }
124 
125     @Test
126     void testInsert_hyperplaneConvexSubsets_mixedCutRules() {
127         // act/assert
128         checkMixedCutRuleInsertion(segs -> {
129             tree.insert(segs[0], RegionCutRule.PLUS_INSIDE);
130             tree.insert(segs[1]); // default rule
131             tree.insert(segs[2], RegionCutRule.PLUS_INSIDE);
132             tree.insert(segs[3], RegionCutRule.MINUS_INSIDE);
133             tree.insert(segs[4], RegionCutRule.INHERIT);
134         });
135     }
136 
137     @Test
138     void testInsert_hyperplaneConvexSubsetList_mixedCutRules() {
139         // act/assert
140         checkMixedCutRuleInsertion(segs -> {
141             tree.insert(Collections.singletonList(segs[0]), RegionCutRule.PLUS_INSIDE);
142             tree.insert(Collections.singletonList(segs[1])); // default rule
143             tree.insert(Collections.singletonList(segs[2]), RegionCutRule.PLUS_INSIDE);
144             tree.insert(Collections.singletonList(segs[3]), RegionCutRule.MINUS_INSIDE);
145             tree.insert(Collections.singletonList(segs[4]), RegionCutRule.INHERIT);
146         });
147     }
148 
149     @Test
150     void testInsert_boundarySource_mixedCutRules() {
151         // arrange
152         final Function<TestLineSegment, BoundarySource<TestLineSegment>> factory = seg -> () -> Stream.of(seg);
153 
154         // act/assert
155         checkMixedCutRuleInsertion(segs -> {
156             tree.insert(factory.apply(segs[0]), RegionCutRule.PLUS_INSIDE);
157             tree.insert(factory.apply(segs[1])); // default rule
158             tree.insert(factory.apply(segs[2]), RegionCutRule.PLUS_INSIDE);
159             tree.insert(factory.apply(segs[3]), RegionCutRule.MINUS_INSIDE);
160             tree.insert(factory.apply(segs[4]), RegionCutRule.INHERIT);
161         });
162     }
163 
164     /** Helper function to check the insertion of hyperplane subsets using different region cut rules.
165      * @param fn
166      */
167     private void checkMixedCutRuleInsertion(final Consumer<TestLineSegment[]> fn) {
168         // arrange
169         final TestLineSegment bottom = new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(0, 0));
170         final TestLineSegment right = new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(1, 1));
171         final TestLineSegment top = new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(1, 1));
172         final TestLineSegment left = new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0));
173         final TestLineSegment diag = new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 1));
174 
175         tree = emptyTree();
176 
177         // act
178         fn.accept(new TestLineSegment[] {
179             bottom,
180             right,
181             top,
182             left,
183             diag
184         });
185 
186         // assert
187         TestRegionNode node = tree.getRoot();
188         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
189 
190         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
191         Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
192 
193         node = node.getPlus();
194         Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
195         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
196 
197         node = node.getMinus();
198         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
199         Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
200 
201         node = node.getPlus();
202         Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
203         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
204 
205         node = node.getMinus();
206         Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
207         Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
208     }
209 
210     @Test
211     void testGetLocation_emptyRoot() {
212         // act/assert
213         Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
214     }
215 
216     @Test
217     void testGetLocation_singleCut() {
218         // arrange
219         root.insertCut(TestLine.X_AXIS);
220 
221         // act/assert
222         Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
223         Assertions.assertFalse(root.isInside());
224         Assertions.assertFalse(root.isOutside());
225 
226         final TestRegionNode minus = root.getMinus();
227         Assertions.assertEquals(RegionLocation.INSIDE, minus.getLocation());
228         Assertions.assertTrue(minus.isInside());
229         Assertions.assertFalse(minus.isOutside());
230 
231         final TestRegionNode plus = root.getPlus();
232         Assertions.assertEquals(RegionLocation.OUTSIDE, plus.getLocation());
233         Assertions.assertFalse(plus.isInside());
234         Assertions.assertTrue(plus.isOutside());
235     }
236 
237     @Test
238     void testGetLocation_multipleCuts() {
239         // arrange
240         tree.insert(Arrays.asList(
241                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
242                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)),
243                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, -1))));
244 
245         // act/assert
246         Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
247 
248         final TestRegionNode plus = root.getPlus();
249         Assertions.assertEquals(RegionLocation.OUTSIDE, plus.getLocation());
250 
251         final TestRegionNode plusPlus = plus.getPlus();
252         Assertions.assertEquals(RegionLocation.OUTSIDE, plusPlus.getLocation());
253 
254         final TestRegionNode plusMinus = plus.getMinus();
255         Assertions.assertEquals(RegionLocation.INSIDE, plusMinus.getLocation());
256 
257         final TestRegionNode minus = root.getMinus();
258         Assertions.assertEquals(RegionLocation.INSIDE, minus.getLocation());
259 
260         final TestRegionNode minusPlus = minus.getPlus();
261         Assertions.assertEquals(RegionLocation.OUTSIDE, minusPlus.getLocation());
262 
263         final TestRegionNode minusMinus = minus.getMinus();
264         Assertions.assertEquals(RegionLocation.INSIDE, minusMinus.getLocation());
265     }
266 
267     @Test
268     void testSetLocation() {
269         // arrange
270         tree = emptyTree();
271         tree.insert(TestLine.Y_AXIS.span());
272 
273         final TestRegionNode node = tree.getRoot().getMinus();
274 
275         // act
276         node.setLocation(RegionLocation.OUTSIDE);
277 
278         // assert
279         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
280         Assertions.assertTrue(tree.isEmpty());
281     }
282 
283     @Test
284     void testSetLocation_invalidatesRegionProperties() {
285         // arrange
286         tree = emptyTree();
287         tree.insert(TestLine.Y_AXIS.span());
288 
289         final TestRegionNode node = tree.getRoot().getMinus();
290 
291         final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
292 
293         // act
294         node.setLocation(RegionLocation.OUTSIDE);
295 
296         // assert
297         Assertions.assertNotSame(prevProps, tree.getRegionSizeProperties());
298     }
299 
300     @Test
301     void testSetLocation_noChange_doesNotInvalidateTree() {
302         // arrange
303         tree = emptyTree();
304         tree.insert(TestLine.Y_AXIS.span());
305 
306         final TestRegionNode node = tree.getRoot().getMinus();
307 
308         final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
309 
310         // act
311         node.setLocation(RegionLocation.INSIDE);
312 
313         // assert
314         Assertions.assertSame(prevProps, tree.getRegionSizeProperties());
315     }
316 
317     @Test
318     void testSetLocation_invalidArgs() {
319         // act/assert
320         GeometryTestUtils.assertThrowsWithMessage(() -> root.setLocation(null),
321                 IllegalArgumentException.class, "Invalid node location: null");
322         GeometryTestUtils.assertThrowsWithMessage(() -> root.setLocation(RegionLocation.BOUNDARY),
323                 IllegalArgumentException.class, "Invalid node location: BOUNDARY");
324     }
325 
326     @Test
327     void testCondense() {
328         // arrange
329         tree = emptyTree();
330         tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
331         tree.insert(TestLine.X_AXIS.span(), RegionCutRule.INHERIT);
332 
333         // act
334         final boolean result = tree.condense();
335 
336         // assert
337         Assertions.assertTrue(result);
338 
339         Assertions.assertEquals(3, tree.count());
340         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
341         Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getMinus().getLocation());
342         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getPlus().getLocation());
343     }
344 
345     @Test
346     void testCondense_alreadyCondensed() {
347         // arrange
348         tree = emptyTree();
349         tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
350 
351         // act
352         final boolean result = tree.condense();
353 
354         // assert
355         Assertions.assertFalse(result);
356 
357         Assertions.assertEquals(3, tree.count());
358         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
359         Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getMinus().getLocation());
360         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getPlus().getLocation());
361     }
362 
363     @Test
364     void testCondense_invalidatesTreeWhenChanged() {
365         // arrange
366         tree = emptyTree();
367         tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
368         tree.insert(TestLine.X_AXIS.span(), RegionCutRule.INHERIT);
369 
370         final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
371 
372         // act
373         final boolean result = tree.condense();
374 
375         // assert
376         Assertions.assertTrue(result);
377 
378         Assertions.assertNotSame(prevProps, tree.getRegionSizeProperties());
379     }
380 
381     @Test
382     void testCondense_doesNotInvalidateTreeWhenNotChanged() {
383         // arrange
384         tree = emptyTree();
385 
386         final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
387 
388         // act
389         final boolean result = tree.condense();
390 
391         // assert
392         Assertions.assertFalse(result);
393 
394         Assertions.assertSame(prevProps, tree.getRegionSizeProperties());
395     }
396 
397     @Test
398     void testCut_nodeMethod() {
399         // arrange
400         tree = emptyTree();
401 
402         // act
403         tree.getRoot().cut(TestLine.X_AXIS, RegionCutRule.PLUS_INSIDE)
404             .getPlus()
405                 .cut(TestLine.Y_AXIS, RegionCutRule.MINUS_INSIDE)
406                 .getMinus()
407                     .cut(new TestLine(TestPoint2D.ZERO, new TestPoint2D(-1, -1)), RegionCutRule.INHERIT);
408 
409         // assert
410         TestRegionNode node = tree.getRoot();
411         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
412 
413         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
414         Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
415 
416         node = node.getPlus();
417         Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
418         Assertions.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
419 
420         node = node.getMinus();
421         Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
422         Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
423     }
424 
425     @Test
426     void testBoundaries_fullAndEmpty() {
427         // act/assert
428         tree.setFull();
429         Assertions.assertFalse(tree.boundaries().iterator().hasNext());
430 
431         tree.setEmpty();
432         Assertions.assertFalse(tree.boundaries().iterator().hasNext());
433     }
434 
435     @Test
436     void testBoundaries_finite() {
437         // arrange
438         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
439 
440         // act
441         final List<TestLineSegment> segments = new ArrayList<>();
442         for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.boundaries()) {
443             segments.add((TestLineSegment) sub);
444         }
445 
446         // assert
447         Assertions.assertEquals(4, segments.size());
448 
449         assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(1, 0));
450         assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(1, 1));
451         assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(0, 1));
452         assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(0, 0));
453     }
454 
455     @Test
456     void testBoundaries_finite_inverted() {
457         // arrange
458         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
459         tree.complement();
460 
461         // act
462         final List<TestLineSegment> segments = new ArrayList<>();
463         for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.boundaries()) {
464             segments.add((TestLineSegment) sub);
465         }
466 
467         // assert
468         Assertions.assertEquals(4, segments.size());
469 
470         assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(0, 1));
471         assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(1, 1));
472         assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(1, 0));
473         assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(0, 0));
474     }
475 
476     @Test
477     void testGetBoundaries_fullAndEmpty() {
478         // act/assert
479         tree.setFull();
480         Assertions.assertEquals(0, tree.getBoundaries().size());
481 
482         tree.setEmpty();
483         Assertions.assertEquals(0, tree.getBoundaries().size());
484     }
485 
486     @Test
487     void testGetBoundaries_finite() {
488         // arrange
489         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
490 
491         // act
492         final List<TestLineSegment> segments = new ArrayList<>();
493         for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.getBoundaries()) {
494             segments.add((TestLineSegment) sub);
495         }
496 
497         // assert
498         Assertions.assertEquals(4, segments.size());
499 
500         assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(1, 0));
501         assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(1, 1));
502         assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(0, 1));
503         assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(0, 0));
504     }
505 
506     @Test
507     void testGetBoundaries_finite_inverted() {
508         // arrange
509         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
510         tree.complement();
511 
512         // act
513         final List<TestLineSegment> segments = new ArrayList<>();
514         for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.getBoundaries()) {
515             segments.add((TestLineSegment) sub);
516         }
517 
518         // assert
519         Assertions.assertEquals(4, segments.size());
520 
521         assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(0, 1));
522         assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(1, 1));
523         assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(1, 0));
524         assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(0, 0));
525     }
526 
527     @Test
528     void testClassify() {
529         // arrange
530         insertSkewedBowtie(tree);
531 
532         // act/assert
533         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
534         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
535 
536         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, 1)));
537         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, -1)));
538 
539         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
540         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
541 
542         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(5, 0)));
543         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
544         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
545         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
546         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
547         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, 0)));
548         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
549         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
550         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
551         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
552         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-5, 0)));
553     }
554 
555     @Test
556     void testClassify_emptyTree() {
557         // act/assert
558         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
559     }
560 
561     @Test
562     void testClassify_NaN() {
563         // act/assert
564         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, Double.NaN)));
565     }
566 
567     @Test
568     void testContains() {
569         // arrange
570         insertSkewedBowtie(tree);
571 
572         // act/assert
573         Assertions.assertTrue(tree.contains(new TestPoint2D(3, 1)));
574         Assertions.assertTrue(tree.contains(new TestPoint2D(-3, -1)));
575 
576         Assertions.assertFalse(tree.contains(new TestPoint2D(-3, 1)));
577         Assertions.assertFalse(tree.contains(new TestPoint2D(3, -1)));
578 
579         Assertions.assertTrue(tree.contains(new TestPoint2D(4, 5)));
580         Assertions.assertTrue(tree.contains(new TestPoint2D(-4, -5)));
581 
582         Assertions.assertFalse(tree.contains(new TestPoint2D(5, 0)));
583 
584         Assertions.assertTrue(tree.contains(new TestPoint2D(4, 0)));
585         Assertions.assertTrue(tree.contains(new TestPoint2D(3, 0)));
586         Assertions.assertTrue(tree.contains(new TestPoint2D(2, 0)));
587         Assertions.assertTrue(tree.contains(new TestPoint2D(1, 0)));
588         Assertions.assertTrue(tree.contains(new TestPoint2D(0, 0)));
589         Assertions.assertTrue(tree.contains(new TestPoint2D(-1, 0)));
590         Assertions.assertTrue(tree.contains(new TestPoint2D(-2, 0)));
591         Assertions.assertTrue(tree.contains(new TestPoint2D(-3, 0)));
592         Assertions.assertTrue(tree.contains(new TestPoint2D(-4, 0)));
593 
594         Assertions.assertFalse(tree.contains(new TestPoint2D(-5, 0)));
595     }
596 
597     @Test
598     void testSetFull() {
599         // arrange
600         insertSkewedBowtie(tree);
601 
602         // act
603         tree.setFull();
604 
605         // assert
606         Assertions.assertTrue(tree.isFull());
607         Assertions.assertFalse(tree.isEmpty());
608 
609         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
610         Assertions.assertTrue(tree.contains(TestPoint2D.ZERO));
611     }
612 
613     @Test
614     void testSetEmpty() {
615         // arrange
616         insertSkewedBowtie(tree);
617 
618         // act
619         tree.setEmpty();
620 
621         // assert
622         Assertions.assertFalse(tree.isFull());
623         Assertions.assertTrue(tree.isEmpty());
624 
625         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
626         Assertions.assertFalse(tree.contains(TestPoint2D.ZERO));
627     }
628 
629     @Test
630     void testGetRegionSizeProperties_cachesValueBasedOnVersion() {
631         // act
632         final RegionSizeProperties<TestPoint2D> first = tree.getRegionSizeProperties();
633         final RegionSizeProperties<TestPoint2D> second = tree.getRegionSizeProperties();
634         tree.getRoot().cut(TestLine.X_AXIS);
635         final RegionSizeProperties<TestPoint2D> third = tree.getRegionSizeProperties();
636 
637         // assert
638         Assertions.assertSame(first, second);
639         Assertions.assertNotSame(second, third);
640 
641         Assertions.assertEquals(1234, first.getSize(), PartitionTestUtils.EPS);
642         PartitionTestUtils.assertPointsEqual(new TestPoint2D(12, 34), first.getCentroid());
643     }
644 
645     @Test
646     void testGetSize() {
647         // act/assert
648         // make sure our stub value is pulled
649         Assertions.assertEquals(1234, tree.getSize(), PartitionTestUtils.EPS);
650     }
651 
652     @Test
653     void testGetCentroid() {
654         // act/assert
655         // make sure our stub value is pulled
656         PartitionTestUtils.assertPointsEqual(new TestPoint2D(12, 34), tree.getCentroid());
657     }
658 
659     @Test
660     void testGetBoundarySize_fullAndEmpty() {
661         // act/assert
662         Assertions.assertEquals(0.0, fullTree().getBoundarySize(), PartitionTestUtils.EPS);
663         Assertions.assertEquals(0.0, emptyTree().getBoundarySize(), PartitionTestUtils.EPS);
664     }
665 
666     @Test
667     void testGetBoundarySize_infinite() {
668         // arrange
669         final TestRegionBSPTree halfPos = new TestRegionBSPTree(true);
670         halfPos.getRoot().cut(TestLine.X_AXIS);
671 
672         final TestRegionBSPTree halfPosComplement = new TestRegionBSPTree(true);
673         halfPosComplement.complement(halfPos);
674 
675         // act/assert
676         Assertions.assertEquals(Double.POSITIVE_INFINITY, halfPos.getBoundarySize(), PartitionTestUtils.EPS);
677         Assertions.assertEquals(Double.POSITIVE_INFINITY, halfPosComplement.getBoundarySize(), PartitionTestUtils.EPS);
678     }
679 
680     @Test
681     void testGetBoundarySize_alignedCuts() {
682         // arrange
683         final TestPoint2D p0 = TestPoint2D.ZERO;
684         final TestPoint2D p1 = new TestPoint2D(0, 3);
685 
686         TestRegionNode node = tree.getRoot();
687 
688         tree.cutNode(node, new TestLineSegment(p0, p1));
689         node = node.getMinus();
690 
691         tree.cutNode(node, new TestLineSegment(0, 0, new TestLine(p1, new TestPoint2D(-1, 3))));
692         node = node.getMinus();
693 
694         tree.cutNode(node, new TestLineSegment(p1, p0));
695         node = node.getMinus();
696 
697         tree.cutNode(node, new TestLineSegment(0, 0, new TestLine(p0, new TestPoint2D(1, 3))));
698 
699         // act/assert
700         Assertions.assertEquals(6, tree.getBoundarySize(), PartitionTestUtils.EPS);
701     }
702 
703     @Test
704     void testGetBoundarySize_box() {
705         // arrange
706         insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
707 
708         // act/assert
709         Assertions.assertEquals(6.0, tree.getBoundarySize(), PartitionTestUtils.EPS);
710     }
711 
712     @Test
713     void testGetBoundarySize_boxComplement() {
714         // arrange
715         insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
716         tree.complement();
717 
718         // act/assert
719         Assertions.assertEquals(6.0, tree.getBoundarySize(), PartitionTestUtils.EPS);
720     }
721 
722     @Test
723     void testGetBoundarySize_recomputesAfterChange() {
724         // arrange
725         insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
726 
727         // act
728         final double first = tree.getBoundarySize();
729         tree.insert(new TestLineSegment(new TestPoint2D(3, 1), new TestPoint2D(3, 2)));
730 
731         final double second = tree.getBoundarySize();
732         final double third = tree.getBoundarySize();
733 
734         // assert
735         Assertions.assertEquals(6.0, first, PartitionTestUtils.EPS);
736         Assertions.assertEquals(4.0, second, PartitionTestUtils.EPS);
737         Assertions.assertEquals(4.0, third, PartitionTestUtils.EPS);
738     }
739 
740     @Test
741     void testGetCutBoundary_emptyTree() {
742         // act
743         final RegionCutBoundary<TestPoint2D> boundary = root.getCutBoundary();
744 
745         // assert
746         Assertions.assertNull(boundary);
747     }
748 
749     @Test
750     void testGetCutBoundary_singleCut() {
751         // arrange
752         tree.insert(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
753 
754         // act
755         final RegionCutBoundary<TestPoint2D> boundary = root.getCutBoundary();
756 
757         // assert
758         Assertions.assertTrue(boundary.getInsideFacing().isEmpty());
759 
760         assertCutBoundarySegment(boundary.getOutsideFacing(),
761                 new TestPoint2D(Double.NEGATIVE_INFINITY, 0.0), new TestPoint2D(Double.POSITIVE_INFINITY, 0.0));
762     }
763 
764     @Test
765     void testGetCutBoundary_singleCut_leafNode() {
766         // arrange
767         tree.insert(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
768 
769         // act
770         final RegionCutBoundary<TestPoint2D> boundary = root.getMinus().getCutBoundary();
771 
772         // assert
773         Assertions.assertNull(boundary);
774     }
775 
776     @Test
777     void testGetCutBoundary_singleCorner() {
778         // arrange
779         tree.insert(new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)));
780         tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
781 
782         // act/assert
783         final RegionCutBoundary<TestPoint2D> rootBoundary = root.getCutBoundary();
784 
785         Assertions.assertTrue(rootBoundary.getInsideFacing().isEmpty());
786         assertCutBoundarySegment(rootBoundary.getOutsideFacing(),
787                 new TestPoint2D(Double.NEGATIVE_INFINITY, 0.0), TestPoint2D.ZERO);
788 
789         final RegionCutBoundary<TestPoint2D> childBoundary = tree.getRoot().getMinus().getCutBoundary();
790         Assertions.assertTrue(childBoundary.getInsideFacing().isEmpty());
791         assertCutBoundarySegment(childBoundary.getOutsideFacing(),
792                 TestPoint2D.ZERO, new TestPoint2D(0.0, Double.POSITIVE_INFINITY));
793     }
794 
795     @Test
796     void testGetCutBoundary_leafNode() {
797         // arrange
798         tree.insert(new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)));
799         tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
800 
801         // act/assert
802         Assertions.assertNull(root.getPlus().getCutBoundary());
803         Assertions.assertNull(root.getMinus().getMinus().getCutHyperplane());
804         Assertions.assertNull(root.getMinus().getPlus().getCutHyperplane());
805     }
806 
807     @Test
808     void testFullEmpty_fullTree() {
809         // act/assert
810         Assertions.assertTrue(tree.isFull());
811         Assertions.assertFalse(tree.isEmpty());
812         Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
813     }
814 
815     @Test
816     void testFullEmpty_emptyTree() {
817         // arrange
818         tree.complement();
819 
820         // act/assert
821         Assertions.assertFalse(tree.isFull());
822         Assertions.assertTrue(tree.isEmpty());
823         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
824     }
825 
826     @Test
827     void testTransform_noCuts() {
828         // arrange
829         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
830 
831         // act
832         tree.transform(t);
833 
834         // assert
835         Assertions.assertTrue(tree.isFull());
836         Assertions.assertFalse(tree.isEmpty());
837 
838         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE, TestPoint2D.ZERO);
839     }
840 
841     @Test
842     void testTransform_singleCut() {
843         // arrange
844         tree.getRoot().insertCut(TestLine.X_AXIS);
845 
846         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
847 
848         // act
849         tree.transform(t);
850 
851         // assert
852         Assertions.assertFalse(tree.isFull());
853         Assertions.assertFalse(tree.isEmpty());
854 
855         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
856                 new TestPoint2D(0, -1), TestPoint2D.ZERO, new TestPoint2D(0, 1));
857 
858         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY, new TestPoint2D(0, 2));
859 
860         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
861                 new TestPoint2D(0, 3), new TestPoint2D(0, 4));
862     }
863 
864     @Test
865     void testTransform_multipleCuts() {
866         // arrange
867         insertSkewedBowtie(tree);
868 
869         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 5));
870 
871         // act
872         tree.transform(t);
873 
874         // assert
875         Assertions.assertFalse(tree.isFull());
876         Assertions.assertFalse(tree.isEmpty());
877 
878         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
879                 new TestPoint2D(0, 5), new TestPoint2D(-1, 4), new TestPoint2D(1, 6));
880 
881         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
882                 new TestPoint2D(-2, 4), new TestPoint2D(2, 6));
883 
884         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
885                 new TestPoint2D(-3, 5), new TestPoint2D(3, 5));
886     }
887 
888     @Test
889     void testTransform_xAxisReflection() {
890         // arrange
891         insertSkewedBowtie(tree);
892 
893         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), p.getY()));
894 
895         // act
896         tree.transform(t);
897 
898         // assert
899         Assertions.assertFalse(tree.isFull());
900         Assertions.assertFalse(tree.isEmpty());
901 
902         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
903                 TestPoint2D.ZERO, new TestPoint2D(-1, 1), new TestPoint2D(1, -1));
904 
905         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
906                 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
907                 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
908 
909         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
910                 new TestPoint2D(1, 1), new TestPoint2D(-1, -1));
911     }
912 
913     @Test
914     void testTransform_yAxisReflection() {
915         // arrange
916         insertSkewedBowtie(tree);
917 
918         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), -p.getY()));
919 
920         // act
921         tree.transform(t);
922 
923         // assert
924         Assertions.assertFalse(tree.isFull());
925         Assertions.assertFalse(tree.isEmpty());
926 
927         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
928                 TestPoint2D.ZERO, new TestPoint2D(1, -1), new TestPoint2D(-1, 1));
929 
930         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
931                 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
932                 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
933 
934         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
935                 new TestPoint2D(-1, -1), new TestPoint2D(1, 1));
936     }
937 
938     @Test
939     void testTransform_xAndYAxisReflection() {
940         // arrange
941         insertSkewedBowtie(tree);
942 
943         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), -p.getY()));
944 
945         // act
946         tree.transform(t);
947 
948         // assert
949         Assertions.assertFalse(tree.isFull());
950         Assertions.assertFalse(tree.isEmpty());
951 
952         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
953                 TestPoint2D.ZERO, new TestPoint2D(1, 1), new TestPoint2D(-1, -1));
954 
955         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
956                 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
957                 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
958 
959         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
960                 new TestPoint2D(-1, 1), new TestPoint2D(1, -1));
961     }
962 
963     @Test
964     void testTransform_resetsCutBoundary() {
965         // arrange
966         insertSkewedBowtie(tree);
967 
968         final TestRegionNode node = tree.findNode(new TestPoint2D(1, 1)).getParent();
969 
970 
971         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 5));
972 
973         // act
974         final RegionCutBoundary<TestPoint2D> origBoundary = node.getCutBoundary();
975 
976         tree.transform(t);
977 
978         final RegionCutBoundary<TestPoint2D> resultBoundary = node.getCutBoundary();
979 
980         // assert
981         Assertions.assertNotSame(origBoundary, resultBoundary);
982 
983         assertCutBoundarySegment(origBoundary.getOutsideFacing(), new TestPoint2D(4, 5), new TestPoint2D(-1, 0));
984 
985         assertCutBoundarySegment(resultBoundary.getOutsideFacing(), new TestPoint2D(2, 10), new TestPoint2D(-0.5, 5));
986     }
987 
988     @Test
989     void testComplement_rootOnly() {
990         // act
991         tree.complement();
992 
993         // assert
994         Assertions.assertTrue(tree.isEmpty());
995         Assertions.assertFalse(tree.isFull());
996 
997         Assertions.assertEquals(RegionLocation.OUTSIDE, root.getLocation());
998         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
999     }
1000 
1001     @Test
1002     void testComplement_singleCut() {
1003         // arrange
1004         root.insertCut(TestLine.X_AXIS);
1005 
1006         // act
1007         tree.complement();
1008 
1009         // assert
1010         Assertions.assertFalse(tree.isEmpty());
1011         Assertions.assertFalse(tree.isFull());
1012 
1013         Assertions.assertEquals(RegionLocation.OUTSIDE, root.getMinus().getLocation());
1014         Assertions.assertEquals(RegionLocation.INSIDE, root.getPlus().getLocation());
1015 
1016         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, 1)));
1017         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
1018         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, -1)));
1019     }
1020 
1021     @Test
1022     void testComplement_skewedBowtie() {
1023         // arrange
1024         insertSkewedBowtie(tree);
1025 
1026         // act
1027         tree.complement();
1028 
1029         // assert
1030         Assertions.assertFalse(tree.isEmpty());
1031         Assertions.assertFalse(tree.isFull());
1032 
1033         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, 1)));
1034         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, -1)));
1035 
1036         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, 1)));
1037         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, -1)));
1038 
1039         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
1040         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
1041 
1042         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(5, 0)));
1043         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
1044         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
1045         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
1046         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
1047         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, 0)));
1048         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
1049         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
1050         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
1051         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
1052         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-5, 0)));
1053     }
1054 
1055     @Test
1056     void testComplement_addCutAfterComplement() {
1057         // arrange
1058         tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)));
1059         tree.complement();
1060 
1061         // act
1062         tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
1063 
1064         // assert
1065         Assertions.assertFalse(tree.isEmpty());
1066         Assertions.assertFalse(tree.isFull());
1067 
1068         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
1069 
1070         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(1, 1)));
1071         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, 1)));
1072         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(1, -1)));
1073         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, -1)));
1074     }
1075 
1076     @Test
1077     void testComplement_clearCutAfterComplement() {
1078         // arrange
1079         tree.insert(Arrays.asList(
1080                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1081                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))
1082                 ));
1083         tree.complement();
1084 
1085         // act
1086         root.getMinus().clearCut();
1087 
1088         // assert
1089         Assertions.assertFalse(tree.isEmpty());
1090         Assertions.assertFalse(tree.isFull());
1091 
1092         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
1093 
1094         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(1, 1)));
1095         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-1, 1)));
1096         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(1, -1)));
1097         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, -1)));
1098     }
1099 
1100     @Test
1101     void testComplement_clearRootAfterComplement() {
1102         // arrange
1103         tree.insert(Arrays.asList(
1104                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1105                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))
1106                 ));
1107         tree.complement();
1108 
1109         // act
1110         root.clearCut();
1111 
1112         // assert
1113         Assertions.assertTrue(tree.isEmpty());
1114         Assertions.assertFalse(tree.isFull());
1115 
1116         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
1117     }
1118 
1119     @Test
1120     void testComplement_isReversible_root() {
1121         // act
1122         tree.complement();
1123         tree.complement();
1124 
1125         // assert
1126         Assertions.assertFalse(tree.isEmpty());
1127         Assertions.assertTrue(tree.isFull());
1128 
1129         Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
1130         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
1131     }
1132 
1133     @Test
1134     void testComplement_isReversible_skewedBowtie() {
1135         // arrange
1136         insertSkewedBowtie(tree);
1137 
1138         // act
1139         tree.complement();
1140         tree.complement();
1141 
1142         // assert
1143         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
1144         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
1145 
1146         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, 1)));
1147         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, -1)));
1148 
1149         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
1150         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
1151 
1152         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(5, 0)));
1153         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
1154         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
1155         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
1156         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
1157         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, 0)));
1158         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
1159         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
1160         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
1161         Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
1162         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-5, 0)));
1163     }
1164 
1165     @Test
1166     void testComplement_getCutBoundary() {
1167         // arrange
1168         tree.insert(Arrays.asList(
1169                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1170                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))));
1171         tree.complement();
1172 
1173         // act
1174         final RegionCutBoundary<TestPoint2D> xAxisBoundary = root.getCutBoundary();
1175         final RegionCutBoundary<TestPoint2D> yAxisBoundary = root.getMinus().getCutBoundary();
1176 
1177         // assert
1178         Assertions.assertTrue(xAxisBoundary.getOutsideFacing().isEmpty());
1179         Assertions.assertFalse(xAxisBoundary.getInsideFacing().isEmpty());
1180 
1181         final List<HyperplaneConvexSubset<TestPoint2D>> xAxisInsideFacing = xAxisBoundary.getInsideFacing();
1182         Assertions.assertEquals(1, xAxisInsideFacing.size());
1183 
1184         final TestLineSegment xAxisSeg = (TestLineSegment) xAxisInsideFacing.get(0);
1185         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 0), xAxisSeg.getStartPoint());
1186         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, xAxisSeg.getEndPoint());
1187 
1188         Assertions.assertTrue(yAxisBoundary.getOutsideFacing().isEmpty());
1189         Assertions.assertFalse(yAxisBoundary.getInsideFacing().isEmpty());
1190 
1191         final List<HyperplaneConvexSubset<TestPoint2D>> yAxisInsideFacing = yAxisBoundary.getInsideFacing();
1192         Assertions.assertEquals(1, yAxisInsideFacing.size());
1193 
1194         final TestLineSegment yAxisSeg = (TestLineSegment) yAxisInsideFacing.get(0);
1195         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, yAxisSeg.getStartPoint());
1196         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, Double.POSITIVE_INFINITY), yAxisSeg.getEndPoint());
1197     }
1198 
1199     @Test
1200     void testComplementOf_rootOnly() {
1201         // arrange
1202         final TestRegionBSPTree other = fullTree();
1203         insertSkewedBowtie(other);
1204 
1205         // act
1206         other.complement(tree);
1207 
1208         // assert
1209         Assertions.assertFalse(tree.isEmpty());
1210         Assertions.assertTrue(tree.isFull());
1211 
1212         Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
1213         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
1214 
1215         Assertions.assertTrue(other.isEmpty());
1216         Assertions.assertFalse(other.isFull());
1217 
1218         Assertions.assertEquals(RegionLocation.OUTSIDE, other.getRoot().getLocation());
1219         Assertions.assertEquals(RegionLocation.OUTSIDE, other.classify(TestPoint2D.ZERO));
1220     }
1221 
1222     @Test
1223     void testComplementOf_skewedBowtie() {
1224         // arrange
1225         insertSkewedBowtie(tree);
1226 
1227         final TestRegionBSPTree other = fullTree();
1228 
1229         // act
1230         other.complement(tree);
1231 
1232         // assert
1233         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
1234         Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
1235 
1236         Assertions.assertFalse(other.isEmpty());
1237         Assertions.assertFalse(other.isFull());
1238 
1239         Assertions.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(3, 1)));
1240         Assertions.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(-3, -1)));
1241 
1242         Assertions.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(-3, 1)));
1243         Assertions.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(3, -1)));
1244 
1245         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(4, 5)));
1246         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-4, -5)));
1247 
1248         Assertions.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(5, 0)));
1249         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(4, 0)));
1250         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(3, 0)));
1251         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(2, 0)));
1252         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(1, 0)));
1253         Assertions.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(0, 0)));
1254         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-1, 0)));
1255         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-2, 0)));
1256         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-3, 0)));
1257         Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-4, 0)));
1258         Assertions.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(-5, 0)));
1259     }
1260 
1261     @Test
1262     void testCopy() {
1263         // arrange
1264         insertSkewedBowtie(tree);
1265 
1266         // act
1267         final TestRegionBSPTree copy = fullTree();
1268         copy.copy(tree);
1269 
1270         // assert
1271         Assertions.assertNotSame(tree, copy);
1272         Assertions.assertEquals(tree.count(), copy.count());
1273 
1274         final List<RegionLocation> origLocations = new ArrayList<>();
1275         tree.nodes().forEach(n -> origLocations.add(n.getLocation()));
1276 
1277         final List<RegionLocation> copyLocations = new ArrayList<>();
1278         copy.nodes().forEach(n -> copyLocations.add(n.getLocation()));
1279 
1280         Assertions.assertEquals(origLocations, copyLocations);
1281     }
1282 
1283     @Test
1284     void testExtract() {
1285         // arrange
1286         insertSkewedBowtie(tree);
1287 
1288         final TestRegionBSPTree result = fullTree();
1289 
1290         final TestPoint2D pt = new TestPoint2D(2, 2);
1291 
1292         // act
1293         result.extract(tree.findNode(pt));
1294 
1295         // assert
1296         PartitionTestUtils.assertPointLocations(result, RegionLocation.INSIDE,
1297                 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2));
1298         PartitionTestUtils.assertPointLocations(result, RegionLocation.OUTSIDE,
1299                 new TestPoint2D(-2, 2),
1300                 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5), new TestPoint2D(-2, 2));
1301 
1302         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
1303                 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2),
1304                 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5));
1305         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
1306                 new TestPoint2D(2, -2), new TestPoint2D(-2, 2));
1307     }
1308 
1309     @Test
1310     void testExtract_complementedTree() {
1311         // arrange
1312         insertSkewedBowtie(tree);
1313         tree.complement();
1314 
1315         final TestRegionBSPTree result = fullTree();
1316 
1317         final TestPoint2D pt = new TestPoint2D(2, 2);
1318 
1319         // act
1320         result.extract(tree.findNode(pt));
1321 
1322         // assert
1323         PartitionTestUtils.assertPointLocations(result, RegionLocation.OUTSIDE,
1324                 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2));
1325         PartitionTestUtils.assertPointLocations(result, RegionLocation.INSIDE,
1326                 new TestPoint2D(-2, 2),
1327                 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5), new TestPoint2D(-2, 2));
1328 
1329         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
1330                 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2),
1331                 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5));
1332         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
1333                 new TestPoint2D(2, -2), new TestPoint2D(-2, 2));
1334     }
1335 
1336 
1337 
1338     @Test
1339     void testProject_emptyAndFull() {
1340         // arrange
1341         final TestRegionBSPTree full = fullTree();
1342         final TestRegionBSPTree empty = emptyTree();
1343 
1344         // act/assert
1345         Assertions.assertNull(full.project(new TestPoint2D(0, 0)));
1346         Assertions.assertNull(empty.project(new TestPoint2D(-1, 1)));
1347     }
1348 
1349     @Test
1350     void testProject_halfSpace() {
1351         // arrange
1352         tree.getRoot().cut(TestLine.X_AXIS);
1353 
1354         // act/assert
1355         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(TestPoint2D.ZERO));
1356 
1357         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(0, 7)));
1358         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(0, -7)));
1359 
1360         PartitionTestUtils.assertPointsEqual(new TestPoint2D(4, 0), tree.project(new TestPoint2D(4, 10)));
1361         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-5, 0), tree.project(new TestPoint2D(-5, -2)));
1362     }
1363 
1364     @Test
1365     void testProject_box() {
1366         // arrange
1367         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
1368 
1369         // act/assert
1370         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(TestPoint2D.ZERO));
1371         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(-1, -4)));
1372 
1373         PartitionTestUtils.assertPointsEqual(new TestPoint2D(1, 1), tree.project(new TestPoint2D(2, 9)));
1374 
1375         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.5, 1), tree.project(new TestPoint2D(0.5, 3)));
1376     }
1377 
1378     @Test
1379     void testSplit_empty() {
1380         // arrange
1381         tree = emptyTree();
1382 
1383         // act
1384         final Split<TestRegionBSPTree> split = tree.split(TestLine.X_AXIS);
1385 
1386         // assert
1387         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
1388 
1389         Assertions.assertNull(split.getMinus());
1390         Assertions.assertNull(split.getPlus());
1391     }
1392 
1393     @Test
1394     void testSplit_full() {
1395         // arrange
1396         tree = fullTree();
1397 
1398         // act
1399         final Split<TestRegionBSPTree> split = tree.split(TestLine.X_AXIS);
1400 
1401         // assert
1402         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
1403 
1404         final TestRegionBSPTree minus = split.getMinus();
1405         PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE,
1406                 new TestPoint2D(-1, 1), new TestPoint2D(0, 1), new TestPoint2D(1, 1));
1407         PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
1408                 new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(1, 0));
1409         PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
1410                 new TestPoint2D(-1, -1), new TestPoint2D(0, -1), new TestPoint2D(1, -1));
1411 
1412         final TestRegionBSPTree plus = split.getPlus();
1413         PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
1414                 new TestPoint2D(-1, 1), new TestPoint2D(0, 1), new TestPoint2D(1, 1));
1415         PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
1416                 new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(1, 0));
1417         PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE,
1418                 new TestPoint2D(-1, -1), new TestPoint2D(0, -1), new TestPoint2D(1, -1));
1419     }
1420 
1421     @Test
1422     void testSplit_halfSpace() {
1423         // arrange
1424         tree.getRoot().insertCut(TestLine.X_AXIS);
1425 
1426         final TestLine splitter = TestLine.Y_AXIS;
1427 
1428         // act
1429         final Split<TestRegionBSPTree> split = tree.split(splitter);
1430 
1431         // assert
1432         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
1433 
1434         final TestRegionBSPTree minus = split.getMinus();
1435         PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(-1, 1));
1436         PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
1437                 new TestPoint2D(1, 1), new TestPoint2D(-1, -1), new TestPoint2D(1, -1));
1438 
1439         final TestRegionBSPTree plus = split.getPlus();
1440         PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(1, 1));
1441         PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
1442                 new TestPoint2D(-1, 1), new TestPoint2D(-1, -1), new TestPoint2D(1, -1));
1443     }
1444 
1445     @Test
1446     void testSplit_box() {
1447         // arrange
1448         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
1449 
1450         final TestLine splitter = new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 1));
1451 
1452         // act
1453         final Split<TestRegionBSPTree> split = tree.split(splitter);
1454 
1455         // assert
1456         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
1457 
1458         final TestRegionBSPTree minus = split.getMinus();
1459         PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(0.25, 0.25));
1460         PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
1461                 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5));
1462         PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
1463                 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1), new TestPoint2D(0.75, 0.75));
1464 
1465         final TestRegionBSPTree plus = split.getPlus();
1466         PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(0.75, 0.75));
1467         PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
1468                 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5), new TestPoint2D(0.25, 0.25));
1469         PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
1470                 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
1471     }
1472 
1473     @Test
1474     void testSplit_box_onMinusOnly() {
1475         // arrange
1476         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
1477 
1478         final TestLine splitter = new TestLine(new TestPoint2D(2, 0), new TestPoint2D(1, 1));
1479 
1480         // act
1481         final Split<TestRegionBSPTree> split = tree.split(splitter);
1482 
1483         // assert
1484         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
1485 
1486         final TestRegionBSPTree minus = split.getMinus();
1487         PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(0.5, 0.5));
1488         PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
1489                 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5),
1490                 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
1491 
1492         Assertions.assertNull(split.getPlus());
1493     }
1494 
1495     @Test
1496     void testSplit_box_onPlusOnly() {
1497         // arrange
1498         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
1499 
1500         final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 1));
1501 
1502         // act
1503         final Split<TestRegionBSPTree> split = tree.split(splitter);
1504 
1505         // assert
1506         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
1507 
1508         Assertions.assertNull(split.getMinus());
1509 
1510         final TestRegionBSPTree plus = split.getPlus();
1511         PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(0.5, 0.5));
1512         PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
1513                 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5),
1514                 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
1515     }
1516 
1517     @Test
1518     void testToString() {
1519         // arrange
1520         tree.getRoot().cut(TestLine.X_AXIS);
1521 
1522         // act
1523         final String str = tree.toString();
1524 
1525         // assert
1526         Assertions.assertEquals("TestRegionBSPTree[count= 3, height= 1]", str);
1527         Assertions.assertTrue(tree.getRoot().toString().contains("TestRegionNode"));
1528     }
1529 
1530     private static void insertBox(final TestRegionBSPTree tree, final TestPoint2D upperLeft,
1531             final TestPoint2D lowerRight) {
1532         final TestPoint2D upperRight = new TestPoint2D(lowerRight.getX(), upperLeft.getY());
1533         final TestPoint2D lowerLeft = new TestPoint2D(upperLeft.getX(), lowerRight.getY());
1534 
1535         tree.insert(Arrays.asList(
1536                     new TestLineSegment(lowerRight, upperRight),
1537                     new TestLineSegment(upperRight, upperLeft),
1538                     new TestLineSegment(upperLeft, lowerLeft),
1539                     new TestLineSegment(lowerLeft, lowerRight)
1540                 ));
1541     }
1542 
1543     private static void insertSkewedBowtie(final TestRegionBSPTree tree) {
1544         tree.insert(Arrays.asList(
1545                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1546 
1547                 new TestLineSegment(new TestPoint2D(4, 0), new TestPoint2D(4, 1)),
1548                 new TestLineSegment(new TestPoint2D(-4, 0), new TestPoint2D(-4, -1)),
1549 
1550                 new TestLineSegment(new TestPoint2D(4, 5), new TestPoint2D(-1, 0)),
1551                 new TestLineSegment(new TestPoint2D(-4, -5), new TestPoint2D(1, 0))));
1552     }
1553 
1554     private static void assertCutBoundarySegment(final List<HyperplaneConvexSubset<TestPoint2D>> boundaries,
1555             final TestPoint2D start, final TestPoint2D end) {
1556         Assertions.assertFalse(boundaries.isEmpty(), "Expected boundary to not be empty");
1557 
1558         Assertions.assertEquals(1, boundaries.size());
1559 
1560         final TestLineSegment segment = (TestLineSegment) boundaries.get(0);
1561         PartitionTestUtils.assertPointsEqual(start, segment.getStartPoint());
1562         PartitionTestUtils.assertPointsEqual(end, segment.getEndPoint());
1563     }
1564 
1565     private static void assertContainsSegment(final List<TestLineSegment> boundaries, final TestPoint2D start,
1566             final TestPoint2D end) {
1567         boolean found = false;
1568         for (final TestLineSegment seg : boundaries) {
1569             final TestPoint2D startPt = seg.getStartPoint();
1570             final TestPoint2D endPt = seg.getEndPoint();
1571 
1572             if (PartitionTestUtils.PRECISION.eq(start.getX(), startPt.getX()) &&
1573                     PartitionTestUtils.PRECISION.eq(start.getY(), startPt.getY()) &&
1574                     PartitionTestUtils.PRECISION.eq(end.getX(), endPt.getX()) &&
1575                     PartitionTestUtils.PRECISION.eq(end.getY(), endPt.getY())) {
1576                 found = true;
1577                 break;
1578             }
1579         }
1580 
1581         Assertions.assertTrue(found, "Expected to find segment start= " + start + ", end= " + end);
1582     }
1583 
1584     private static TestRegionBSPTree emptyTree() {
1585         return new TestRegionBSPTree(false);
1586     }
1587 
1588     private static TestRegionBSPTree fullTree() {
1589         return new TestRegionBSPTree(true);
1590     }
1591 }