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.Test;
    28
    29  public class AbstractRegionBSPTreeBooleanTest {
    30
    31      @Test
    32      public 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      public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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 }