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.Arrays;
20  import java.util.function.Supplier;
21  
22  import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
23  import org.apache.commons.geometry.core.partitioning.test.TestLine;
24  import org.apache.commons.geometry.core.partitioning.test.TestLineSegment;
25  import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
26  import org.apache.commons.geometry.core.partitioning.test.TestRegionBSPTree;
27  import org.junit.jupiter.api.Test;
28  
29  class AbstractRegionBSPTreeBooleanTest {
30  
31      @Test
32      void testUnion_singleNodeTrees() {
33          // act/assert
34          unionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
35              .full(false)
36              .empty(true)
37              .count(1)
38              .check();
39  
40          unionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
41              .full(true)
42              .empty(false)
43              .count(1)
44              .check();
45  
46          unionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::fullTree)
47              .full(true)
48              .empty(false)
49              .count(1)
50              .check();
51  
52          unionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::fullTree)
53              .full(true)
54              .empty(false)
55              .count(1)
56              .check();
57      }
58  
59      @Test
60      void testUnion_simpleCrossingCuts() {
61          // act/assert
62          unionChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
63              .full(false)
64              .empty(false)
65              .count(3)
66              .check();
67  
68          unionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::xAxisTree)
69              .full(false)
70              .empty(false)
71              .count(3)
72              .check();
73  
74          unionChecker(AbstractRegionBSPTreeBooleanTest::yAxisTree, AbstractRegionBSPTreeBooleanTest::fullTree)
75              .full(true)
76              .empty(false)
77              .count(1)
78              .check();
79  
80          unionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
81              .full(true)
82              .empty(false)
83              .count(1)
84              .check();
85  
86          unionChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
87              .full(false)
88              .empty(false)
89              .inside(new TestPoint2D(1, 1), new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
90              .outside(new TestPoint2D(1, -1))
91              .boundary(TestPoint2D.ZERO)
92              .count(5)
93              .check(t -> {
94                  final TestLineSegment seg = (TestLineSegment) t.getRoot().getPlus().getCut();
95  
96                  PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.NEGATIVE_INFINITY), seg.getStartPoint());
97                  PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getEndPoint());
98              });
99      }
100 
101     @Test
102     void testUnion_mixedCutRules() {
103         // arrange
104         final Supplier<TestRegionBSPTree> r1 = () -> {
105             final TestRegionBSPTree tree = new TestRegionBSPTree(false);
106             tree.insert(TestLine.X_AXIS.span(), RegionCutRule.PLUS_INSIDE);
107             tree.insert(new TestLine(new TestPoint2D(5, 0), new TestPoint2D(5, 1)).span(), RegionCutRule.INHERIT);
108 
109             return tree;
110         };
111 
112         final Supplier<TestRegionBSPTree> r2 = () -> {
113             final TestRegionBSPTree tree = new TestRegionBSPTree(false);
114             tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
115 
116             return tree;
117         };
118 
119         // act/assert
120         // Note that the tree node count is different from other tests because one input tree is not condensed.
121         // However, the resulting regions are equivalent.
122         unionChecker(r1, r2)
123             .full(false)
124             .empty(false)
125             .inside(new TestPoint2D(1, -1), new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
126             .outside(new TestPoint2D(1, 1), new TestPoint2D(10, 10))
127             .boundary(TestPoint2D.ZERO)
128             .count(7)
129             .check(t -> {
130                 final TestLineSegment seg = (TestLineSegment) t.getRoot().getMinus().getMinus().getCut();
131 
132                 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getStartPoint());
133                 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), seg.getEndPoint());
134             });
135     }
136 
137     @Test
138     void testUnion_boxTreeWithSingleCutTree() {
139         // arrange
140         final Supplier<TestRegionBSPTree> boxFactory = () -> {
141             final TestRegionBSPTree box = fullTree();
142             insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
143             return box;
144         };
145 
146         final Supplier<TestRegionBSPTree> horizontalFactory = () -> {
147             final TestRegionBSPTree horizontal = fullTree();
148             horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, 2), new TestPoint2D(0, 2)));
149 
150             return horizontal;
151         };
152 
153         // act/assert
154         unionChecker(horizontalFactory, boxFactory)
155             .count(3)
156             .inside(TestPoint2D.ZERO, new TestPoint2D(1, 1), new TestPoint2D(1, -1))
157             .outside(new TestPoint2D(0, 3), new TestPoint2D(3, 3))
158             .boundary(new TestPoint2D(-1, 2), new TestPoint2D(3, 2))
159             .check();
160     }
161 
162     @Test
163     void testUnion_treeWithComplement() {
164         // arrange
165         final Supplier<TestRegionBSPTree> treeFactory = () -> {
166             final TestRegionBSPTree t = fullTree();
167             insertSkewedBowtie(t);
168 
169             return t;
170         };
171         final Supplier<TestRegionBSPTree> complementFactory = () -> {
172             final TestRegionBSPTree t = treeFactory.get();
173             t.complement();
174 
175             return t;
176         };
177 
178         // act/assert
179         unionChecker(treeFactory, complementFactory)
180             .full(true)
181             .empty(false)
182             .count(1)
183             .check();
184     }
185 
186     @Test
187     void testIntersection_singleNodeTrees() {
188         // act/assert
189         intersectionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
190             .full(false)
191             .empty(true)
192             .count(1)
193             .check();
194 
195         intersectionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
196             .full(false)
197             .empty(true)
198             .count(1)
199             .check();
200 
201         intersectionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::fullTree)
202             .full(false)
203             .empty(true)
204             .count(1)
205             .check();
206 
207         intersectionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::fullTree)
208             .full(true)
209             .empty(false)
210             .count(1)
211             .check();
212     }
213 
214     @Test
215     void testIntersection_simpleCrossingCuts() {
216         // act/assert
217         intersectionChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
218             .full(false)
219             .empty(true)
220             .count(1)
221             .check();
222 
223         intersectionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::xAxisTree)
224             .full(false)
225             .empty(true)
226             .count(1)
227             .check();
228 
229         intersectionChecker(AbstractRegionBSPTreeBooleanTest::yAxisTree, AbstractRegionBSPTreeBooleanTest::fullTree)
230             .full(false)
231             .empty(false)
232             .inside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
233             .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
234             .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
235             .count(3)
236             .check();
237 
238         intersectionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
239             .full(false)
240             .empty(false)
241             .inside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
242             .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
243             .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
244             .count(3)
245             .check();
246 
247         intersectionChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
248             .full(false)
249             .empty(false)
250             .inside(new TestPoint2D(-1, 1))
251             .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1), new TestPoint2D(-1, -1))
252             .boundary(TestPoint2D.ZERO)
253             .count(5)
254             .check(t -> {
255                 final TestLineSegment seg = (TestLineSegment) t.getRoot().getMinus().getCut();
256 
257                 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getStartPoint());
258                 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), seg.getEndPoint());
259             });
260     }
261 
262     @Test
263     void testIntersection_boxTreeWithSingleCutTree() {
264         // arrange
265         final Supplier<TestRegionBSPTree> boxFactory = () -> {
266             final TestRegionBSPTree box = fullTree();
267             insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
268             return box;
269         };
270 
271         final Supplier<TestRegionBSPTree> horizontalFactory = () -> {
272             final TestRegionBSPTree horizontal = fullTree();
273             horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
274 
275             return horizontal;
276         };
277 
278         // act/assert
279         intersectionChecker(horizontalFactory, boxFactory)
280             .inside(new TestPoint2D(1, -3))
281             .outside(new TestPoint2D(1, -1), new TestPoint2D(-1, -3),
282                     new TestPoint2D(1, -5), new TestPoint2D(3, -3))
283             .boundary(new TestPoint2D(0, -2), new TestPoint2D(2, -2),
284                     new TestPoint2D(0, -4), new TestPoint2D(2, -4))
285             .count(9)
286             .check();
287     }
288 
289     @Test
290     void testIntersection_treeWithComplement() {
291         // arrange
292         final Supplier<TestRegionBSPTree> treeFactory = () -> {
293             final TestRegionBSPTree t = fullTree();
294             insertSkewedBowtie(t);
295 
296             return t;
297         };
298         final Supplier<TestRegionBSPTree> complementFactory = () -> {
299             final TestRegionBSPTree t = treeFactory.get();
300             t.complement();
301 
302             return t;
303         };
304 
305         // act/assert
306         intersectionChecker(treeFactory, complementFactory)
307             .full(false)
308             .empty(true)
309             .count(1)
310             .check();
311     }
312 
313     @Test
314     void testDifference_singleNodeTrees() {
315         // act/assert
316         differenceChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
317             .full(false)
318             .empty(true)
319             .count(1)
320             .check();
321 
322         differenceChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
323             .full(true)
324             .empty(false)
325             .count(1)
326             .check();
327 
328         differenceChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::fullTree)
329             .full(false)
330             .empty(true)
331             .count(1)
332             .check();
333 
334         differenceChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::fullTree)
335             .full(false)
336             .empty(true)
337             .count(1)
338             .check();
339     }
340 
341     @Test
342     void testDifference_simpleCrossingCuts() {
343         // act/assert
344         differenceChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
345             .full(false)
346             .empty(false)
347             .inside(new TestPoint2D(0, 1))
348             .outside(new TestPoint2D(0, -1))
349             .boundary(TestPoint2D.ZERO)
350             .count(3)
351             .check();
352 
353         differenceChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::xAxisTree)
354             .full(false)
355             .empty(true)
356             .count(1)
357             .check();
358 
359         differenceChecker(AbstractRegionBSPTreeBooleanTest::yAxisTree, AbstractRegionBSPTreeBooleanTest::fullTree)
360             .full(false)
361             .empty(true)
362             .count(1)
363             .check();
364 
365         differenceChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
366             .full(false)
367             .empty(false)
368             .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
369             .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
370             .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
371             .count(3)
372             .check();
373 
374         differenceChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
375             .full(false)
376             .empty(false)
377             .inside(new TestPoint2D(1, 1))
378             .outside(new TestPoint2D(-1, 1), new TestPoint2D(1, -1), new TestPoint2D(-1, -1))
379             .boundary(TestPoint2D.ZERO)
380             .count(5)
381             .check(t -> {
382                 final TestLineSegment seg = (TestLineSegment) t.getRoot().getMinus().getCut();
383 
384                 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getStartPoint());
385                 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), seg.getEndPoint());
386             });
387     }
388 
389     @Test
390     void testDifference_boxTreeWithSingleCutTree() {
391         // arrange
392         final Supplier<TestRegionBSPTree> boxFactory = () -> {
393             final TestRegionBSPTree box = fullTree();
394             insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
395             return box;
396         };
397 
398         final Supplier<TestRegionBSPTree> horizontalFactory = () -> {
399             final TestRegionBSPTree horizontal = fullTree();
400             horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
401 
402             return horizontal;
403         };
404 
405         // act/assert
406         differenceChecker(horizontalFactory, boxFactory)
407             .inside(new TestPoint2D(-1, -3), new TestPoint2D(-1, -5),
408                     new TestPoint2D(1, -5), new TestPoint2D(3, -5),
409                     new TestPoint2D(4, -3))
410             .outside(new TestPoint2D(1, -1), new TestPoint2D(1, -1),
411                     new TestPoint2D(3, -1), new TestPoint2D(1, -3))
412             .boundary(new TestPoint2D(0, -2), new TestPoint2D(0, -4),
413                     new TestPoint2D(2, -4), new TestPoint2D(2, -2))
414             .count(9)
415             .check();
416     }
417 
418     @Test
419     void testDifference_treeWithCopy() {
420         // arrange
421         final Supplier<TestRegionBSPTree> treeFactory = () -> {
422             final TestRegionBSPTree t = fullTree();
423             insertSkewedBowtie(t);
424 
425             return t;
426         };
427 
428         // act/assert
429         differenceChecker(treeFactory, treeFactory)
430             .full(false)
431             .empty(true)
432             .count(1)
433             .check();
434     }
435 
436     @Test
437     void testXor_singleNodeTrees() {
438         // act/assert
439         xorChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
440             .full(false)
441             .empty(true)
442             .count(1)
443             .check();
444 
445         xorChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
446             .full(true)
447             .empty(false)
448             .count(1)
449             .check();
450 
451         xorChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::fullTree)
452             .full(true)
453             .empty(false)
454             .count(1)
455             .check();
456 
457         xorChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::fullTree)
458             .full(false)
459             .empty(true)
460             .count(1)
461             .check();
462     }
463 
464     @Test
465     void testXor_simpleCrossingCuts() {
466         // act/assert
467         xorChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
468             .full(false)
469             .empty(false)
470             .inside(new TestPoint2D(0, 1))
471             .outside(new TestPoint2D(0, -1))
472             .boundary(TestPoint2D.ZERO)
473             .count(3)
474             .check();
475 
476         xorChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::xAxisTree)
477             .full(false)
478             .empty(false)
479             .inside(new TestPoint2D(0, 1))
480             .outside(new TestPoint2D(0, -1))
481             .boundary(TestPoint2D.ZERO)
482             .count(3)
483             .check();
484 
485         xorChecker(AbstractRegionBSPTreeBooleanTest::yAxisTree, AbstractRegionBSPTreeBooleanTest::fullTree)
486             .full(false)
487             .empty(false)
488             .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
489             .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
490             .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
491             .count(3)
492             .check();
493 
494         xorChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
495             .full(false)
496             .empty(false)
497             .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
498             .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
499             .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
500             .count(3)
501             .check();
502 
503         xorChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
504             .full(false)
505             .empty(false)
506             .inside(new TestPoint2D(1, 1), new TestPoint2D(-1, -1))
507             .outside(new TestPoint2D(-1, 1), new TestPoint2D(1, -1))
508             .boundary(TestPoint2D.ZERO)
509             .count(7)
510             .check(t -> {
511                 final TestLineSegment minusSeg = (TestLineSegment) t.getRoot().getMinus().getCut();
512 
513                 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, minusSeg.getStartPoint());
514                 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), minusSeg.getEndPoint());
515 
516                 final TestLineSegment plusSeg = (TestLineSegment) t.getRoot().getPlus().getCut();
517 
518                 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.NEGATIVE_INFINITY), plusSeg.getStartPoint());
519                 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, plusSeg.getEndPoint());
520             });
521     }
522 
523     @Test
524     void testXor_boxTreeWithSingleCutTree() {
525         // arrange
526         final Supplier<TestRegionBSPTree> boxFactory = () -> {
527             final TestRegionBSPTree box = fullTree();
528             insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
529             return box;
530         };
531 
532         final Supplier<TestRegionBSPTree> horizontalFactory = () -> {
533             final TestRegionBSPTree horizontal = fullTree();
534             horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
535 
536             return horizontal;
537         };
538 
539         // act/assert
540         xorChecker(horizontalFactory, boxFactory)
541             .inside(new TestPoint2D(-1, -3), new TestPoint2D(-1, -5),
542                     new TestPoint2D(1, -5), new TestPoint2D(3, -5),
543                     new TestPoint2D(4, -3), new TestPoint2D(1, -1))
544             .outside(new TestPoint2D(3, -1), new TestPoint2D(1, -3),
545                     new TestPoint2D(1, 1), new TestPoint2D(5, -1))
546             .boundary(new TestPoint2D(0, -2), new TestPoint2D(0, -4),
547                     new TestPoint2D(2, -4), new TestPoint2D(2, -2),
548                     TestPoint2D.ZERO, new TestPoint2D(2, 0))
549             .count(15)
550             .check();
551     }
552 
553     @Test
554     void testXor_treeWithComplement() {
555         // arrange
556         final Supplier<TestRegionBSPTree> treeFactory = () -> {
557             final TestRegionBSPTree t = fullTree();
558             insertSkewedBowtie(t);
559 
560             return t;
561         };
562         final Supplier<TestRegionBSPTree> complementFactory = () -> {
563             final TestRegionBSPTree t = treeFactory.get();
564             t.complement();
565 
566             return t;
567         };
568 
569         // act/assert
570         xorChecker(treeFactory, complementFactory)
571             .full(true)
572             .empty(false)
573             .count(1)
574             .check();
575     }
576 
577     private static TestRegionBSPTree emptyTree() {
578         return new TestRegionBSPTree(false);
579     }
580 
581     private static TestRegionBSPTree fullTree() {
582         return new TestRegionBSPTree(true);
583     }
584 
585     private static TestRegionBSPTree xAxisTree() {
586         final TestRegionBSPTree tree = fullTree();
587         tree.getRoot().cut(TestLine.X_AXIS);
588 
589         return tree;
590     }
591 
592     private static TestRegionBSPTree yAxisTree() {
593         final TestRegionBSPTree tree = fullTree();
594         tree.getRoot().cut(TestLine.Y_AXIS);
595 
596         return tree;
597     }
598 
599     private static void insertBox(final TestRegionBSPTree tree, final TestPoint2D upperLeft,
600             final TestPoint2D lowerRight) {
601         final TestPoint2D upperRight = new TestPoint2D(lowerRight.getX(), upperLeft.getY());
602         final TestPoint2D lowerLeft = new TestPoint2D(upperLeft.getX(), lowerRight.getY());
603 
604         tree.insert(Arrays.asList(
605                     new TestLineSegment(lowerRight, upperRight),
606                     new TestLineSegment(upperRight, upperLeft),
607                     new TestLineSegment(upperLeft, lowerLeft),
608                     new TestLineSegment(lowerLeft, lowerRight)
609                 ));
610     }
611 
612     private static void insertSkewedBowtie(final TestRegionBSPTree tree) {
613         tree.insert(Arrays.asList(
614                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
615 
616                 new TestLineSegment(new TestPoint2D(4, 0), new TestPoint2D(4, 1)),
617                 new TestLineSegment(new TestPoint2D(-4, 0), new TestPoint2D(-4, -1)),
618 
619                 new TestLineSegment(new TestPoint2D(4, 5), new TestPoint2D(-1, 0)),
620                 new TestLineSegment(new TestPoint2D(-4, -5), new TestPoint2D(1, 0))));
621     }
622 
623     private static MergeChecker unionChecker(
624             final Supplier<TestRegionBSPTree> r1,
625             final Supplier<TestRegionBSPTree> r2) {
626 
627         final MergeChecker.Operation constOperation = (a, b) -> {
628             final TestRegionBSPTree result = fullTree();
629             result.union(a, b);
630 
631             return result;
632         };
633 
634         final MergeChecker.Operation inPlaceOperation = (a, b) -> {
635             a.union(b);
636             return a;
637         };
638 
639         return new MergeChecker(r1, r2, constOperation, inPlaceOperation);
640     }
641 
642     private static MergeChecker intersectionChecker(
643             final Supplier<TestRegionBSPTree> tree1Factory,
644             final Supplier<TestRegionBSPTree> tree2Factory) {
645 
646         final MergeChecker.Operation constOperation = (a, b) -> {
647             final TestRegionBSPTree result = fullTree();
648             result.intersection(a, b);
649             return result;
650         };
651 
652         final MergeChecker.Operation inPlaceOperation = (a, b) -> {
653             a.intersection(b);
654             return a;
655         };
656 
657         return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
658     }
659 
660     private static MergeChecker differenceChecker(
661             final Supplier<TestRegionBSPTree> tree1Factory,
662             final Supplier<TestRegionBSPTree> tree2Factory) {
663 
664         final MergeChecker.Operation constOperation = (a, b) -> {
665             final TestRegionBSPTree result = fullTree();
666             result.difference(a, b);
667             return result;
668         };
669 
670         final MergeChecker.Operation inPlaceOperation = (a, b) -> {
671             a.difference(b);
672             return a;
673         };
674 
675         return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
676     }
677 
678     private static MergeChecker xorChecker(
679             final Supplier<TestRegionBSPTree> tree1Factory,
680             final Supplier<TestRegionBSPTree> tree2Factory) {
681 
682         final MergeChecker.Operation constOperation = (a, b) -> {
683             final TestRegionBSPTree result = fullTree();
684             result.xor(a, b);
685             return result;
686         };
687 
688         final MergeChecker.Operation inPlaceOperation = (a, b) -> {
689             a.xor(b);
690             return a;
691         };
692 
693         return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
694     }
695 }