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.stream.StreamSupport;
    20
    21  import org.apache.commons.geometry.core.partitioning.test.AttributeBSPTree;
    22  import org.apache.commons.geometry.core.partitioning.test.AttributeBSPTree.AttributeNode;
    23  import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
    24  import org.apache.commons.geometry.core.partitioning.test.TestLine;
    25  import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
    26  import org.junit.jupiter.api.Assertions;
    27  import org.junit.jupiter.api.Test;
    28
    29  class AbstractBSPTreeMergeOperatorTest {
    30
    31      @Test
    32      void testMerge_singleNodeTreeWithSingleNodeTree() {
    33          // arrange
    34          final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    35          a.getRoot().setAttribute("A");
    36
    37          final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    38          b.getRoot().setAttribute("B");
    39
    40          final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    41
    42          final TestMergeOperator mergeOp = new TestMergeOperator();
    43
    44          // act
    45          mergeOp.apply(a, b, c);
    46
    47          // assert
    48          Assertions.assertEquals(1, a.count());
    49          Assertions.assertEquals(1, b.count());
    50          Assertions.assertEquals(1, c.count());
    51
    52          Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    53          Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    54
    55          Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    56          Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    57
    58          Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    59          Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    60          Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    61          Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    62
    63          PartitionTestUtils.assertTreeStructure(a);
    64          PartitionTestUtils.assertTreeStructure(b);
    65          PartitionTestUtils.assertTreeStructure(c);
    66      }
    67
    68      @Test
    69      void testMerge_singleNodeTreeWithMultiNodeTree() {
    70          // arrange
    71          final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    72          a.getRoot().cut(TestLine.X_AXIS)
    73              .getPlus().attr("A")
    74              .getParent()
    75              .getMinus().attr("a");
    76
    77          final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    78          b.getRoot().setAttribute("B");
    79
    80          final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    81
    82          final TestMergeOperator mergeOp = new TestMergeOperator();
    83
    84          // act
    85          mergeOp.apply(a, b, c);
    86
    87          // assert
    88          Assertions.assertEquals(3, a.count());
    89          Assertions.assertEquals(1, b.count());
    90          Assertions.assertEquals(3, c.count());
    91
    92          Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    93          Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    94
    95          Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    96          Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    97
    98          Assertions.assertEquals("Ba", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    99          Assertions.assertEquals("Ba", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    100         Assertions.assertEquals("BA", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    101         Assertions.assertEquals("BA", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    102
    103         PartitionTestUtils.assertTreeStructure(a);
    104         PartitionTestUtils.assertTreeStructure(b);
    105         PartitionTestUtils.assertTreeStructure(c);
    106     }
    107
    108     @Test
    109     void testMerge_multiNodeTreeWithSingleNodeTree() {
    110         // arrange
    111         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    112         a.getRoot().setAttribute("A");
    113
    114         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    115         b.getRoot().cut(TestLine.X_AXIS)
    116             .getPlus().attr("B")
    117             .getParent()
    118             .getMinus().attr("b");
    119
    120         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    121
    122         final TestMergeOperator mergeOp = new TestMergeOperator();
    123
    124         // act
    125         mergeOp.apply(a, b, c);
    126
    127         // assert
    128         Assertions.assertEquals(1, a.count());
    129         Assertions.assertEquals(3, b.count());
    130         Assertions.assertEquals(3, c.count());
    131
    132         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    133         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    134
    135         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    136         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    137
    138         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    139         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    140         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    141         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    142
    143         PartitionTestUtils.assertTreeStructure(a);
    144         PartitionTestUtils.assertTreeStructure(b);
    145         PartitionTestUtils.assertTreeStructure(c);
    146     }
    147
    148     @Test
    149     void testMerge_cutsIntersect() {
    150         // arrange
    151         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    152         a.getRoot().cut(TestLine.X_AXIS)
    153             .getPlus().attr("A")
    154             .getParent()
    155             .getMinus().attr("a");
    156
    157         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    158         b.getRoot().cut(TestLine.Y_AXIS)
    159             .getPlus().attr("B")
    160             .getParent()
    161             .getMinus().attr("b");
    162
    163         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    164
    165         final TestMergeOperator mergeOp = new TestMergeOperator();
    166
    167         // act
    168         mergeOp.apply(a, b, c);
    169
    170         // assert
    171         Assertions.assertEquals(3, a.count());
    172         Assertions.assertEquals(3, b.count());
    173         Assertions.assertEquals(7, c.count());
    174
    175         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    176         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    177
    178         Assertions.assertEquals("B", b.findNode(new TestPoint2D(1, 0)).getAttribute());
    179         Assertions.assertEquals("b", b.findNode(new TestPoint2D(-1, 0)).getAttribute());
    180
    181         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    182         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    183         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    184         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    185
    186         PartitionTestUtils.assertTreeStructure(a);
    187         PartitionTestUtils.assertTreeStructure(b);
    188         PartitionTestUtils.assertTreeStructure(c);
    189     }
    190
    191     @Test
    192     void testMerge_cutsParallel() {
    193         // arrange
    194         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    195         a.getRoot().cut(TestLine.X_AXIS)
    196             .getPlus().attr("A")
    197             .getParent()
    198             .getMinus().attr("a");
    199
    200         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    201         b.getRoot().cut(TestLine.X_AXIS)
    202             .getPlus().attr("B")
    203             .getParent()
    204             .getMinus().attr("b");
    205
    206         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    207
    208         final TestMergeOperator mergeOp = new TestMergeOperator();
    209
    210         // act
    211         mergeOp.apply(a, b, c);
    212
    213         // assert
    214         Assertions.assertEquals(3, a.count());
    215         Assertions.assertEquals(3, b.count());
    216         Assertions.assertEquals(3, c.count());
    217
    218         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    219         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    220
    221         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    222         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    223
    224         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    225         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    226         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    227         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    228
    229         PartitionTestUtils.assertTreeStructure(a);
    230         PartitionTestUtils.assertTreeStructure(b);
    231         PartitionTestUtils.assertTreeStructure(c);
    232     }
    233
    234     @Test
    235     void testMerge_cutsAntiParallel() {
    236         // arrange
    237         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    238         a.getRoot().cut(TestLine.X_AXIS)
    239             .getPlus().attr("A")
    240             .getParent()
    241             .getMinus().attr("a");
    242
    243         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    244         b.getRoot().cut(new TestLine(new TestPoint2D(1, 0), TestPoint2D.ZERO))
    245             .getPlus().attr("B")
    246             .getParent()
    247             .getMinus().attr("b");
    248
    249         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    250
    251         final TestMergeOperator mergeOp = new TestMergeOperator();
    252
    253         // act
    254         mergeOp.apply(a, b, c);
    255
    256         // assert
    257         Assertions.assertEquals(3, a.count());
    258         Assertions.assertEquals(3, b.count());
    259         Assertions.assertEquals(3, c.count());
    260
    261         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    262         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    263
    264         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    265         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    266
    267         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    268         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    269         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    270         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    271
    272         PartitionTestUtils.assertTreeStructure(a);
    273         PartitionTestUtils.assertTreeStructure(b);
    274         PartitionTestUtils.assertTreeStructure(c);
    275     }
    276
    277     @Test
    278     void testMerge_cutOnPlusSide_parallel() {
    279         // arrange
    280         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    281         a.getRoot().cut(TestLine.X_AXIS)
    282             .getPlus().attr("A")
    283             .getParent()
    284             .getMinus().attr("a");
    285
    286         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    287         b.getRoot().cut(new TestLine(new TestPoint2D(0, -2), new TestPoint2D(1, -2)))
    288             .getPlus().attr("B")
    289             .getParent()
    290             .getMinus().attr("b");
    291
    292         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    293
    294         final TestMergeOperator mergeOp = new TestMergeOperator();
    295
    296         // act
    297         mergeOp.apply(a, b, c);
    298
    299         // assert
    300         Assertions.assertEquals(3, a.count());
    301         Assertions.assertEquals(3, b.count());
    302         Assertions.assertEquals(5, c.count());
    303
    304         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    305         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    306
    307         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    308         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -3)).getAttribute());
    309
    310         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    311         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    312         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    313         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    314
    315         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -3)).getAttribute());
    316         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -3)).getAttribute());
    317
    318         PartitionTestUtils.assertTreeStructure(a);
    319         PartitionTestUtils.assertTreeStructure(b);
    320         PartitionTestUtils.assertTreeStructure(c);
    321     }
    322
    323     @Test
    324     void testMerge_cutOnPlusSide_antiParallel() {
    325         // arrange
    326         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    327         a.getRoot().cut(TestLine.X_AXIS)
    328             .getPlus().attr("A")
    329             .getParent()
    330             .getMinus().attr("a");
    331
    332         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    333         b.getRoot().cut(new TestLine(new TestPoint2D(1, -2), new TestPoint2D(0, -2)))
    334             .getPlus().attr("B")
    335             .getParent()
    336             .getMinus().attr("b");
    337
    338         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    339
    340         final TestMergeOperator mergeOp = new TestMergeOperator();
    341
    342         // act
    343         mergeOp.apply(a, b, c);
    344
    345         // assert
    346         Assertions.assertEquals(3, a.count());
    347         Assertions.assertEquals(3, b.count());
    348         Assertions.assertEquals(5, c.count());
    349
    350         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    351         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    352
    353         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    354         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, -3)).getAttribute());
    355
    356         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    357         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    358         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    359         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    360
    361         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -3)).getAttribute());
    362         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, -3)).getAttribute());
    363
    364         PartitionTestUtils.assertTreeStructure(a);
    365         PartitionTestUtils.assertTreeStructure(b);
    366         PartitionTestUtils.assertTreeStructure(c);
    367     }
    368
    369     @Test
    370     void testMerge_cutOnMinusSide_parallel() {
    371         // arrange
    372         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    373         a.getRoot().cut(TestLine.X_AXIS)
    374             .getPlus().attr("A")
    375             .getParent()
    376             .getMinus().attr("a");
    377
    378         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    379         b.getRoot().cut(new TestLine(new TestPoint2D(0, 2), new TestPoint2D(1, 2)))
    380             .getPlus().attr("B")
    381             .getParent()
    382             .getMinus().attr("b");
    383
    384         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    385
    386         final TestMergeOperator mergeOp = new TestMergeOperator();
    387
    388         // act
    389         mergeOp.apply(a, b, c);
    390
    391         // assert
    392         Assertions.assertEquals(3, a.count());
    393         Assertions.assertEquals(3, b.count());
    394         Assertions.assertEquals(5, c.count());
    395
    396         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    397         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    398
    399         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    400         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, 3)).getAttribute());
    401
    402         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    403         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    404         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    405         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    406
    407         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 3)).getAttribute());
    408         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(1, 3)).getAttribute());
    409
    410         PartitionTestUtils.assertTreeStructure(a);
    411         PartitionTestUtils.assertTreeStructure(b);
    412         PartitionTestUtils.assertTreeStructure(c);
    413     }
    414
    415     @Test
    416     void testMerge_cutOnMinusSide_antiParallel() {
    417         // arrange
    418         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    419         a.getRoot().cut(TestLine.X_AXIS)
    420             .getPlus().attr("A")
    421             .getParent()
    422             .getMinus().attr("a");
    423
    424         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    425         b.getRoot().cut(new TestLine(new TestPoint2D(1, 2), new TestPoint2D(0, 2)))
    426             .getPlus().attr("B")
    427             .getParent()
    428             .getMinus().attr("b");
    429
    430         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
    431
    432         final TestMergeOperator mergeOp = new TestMergeOperator();
    433
    434         // act
    435         mergeOp.apply(a, b, c);
    436
    437         // assert
    438         Assertions.assertEquals(3, a.count());
    439         Assertions.assertEquals(3, b.count());
    440         Assertions.assertEquals(5, c.count());
    441
    442         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    443         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    444
    445         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    446         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 3)).getAttribute());
    447
    448         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    449         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    450         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    451         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    452
    453         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(-1, 3)).getAttribute());
    454         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 3)).getAttribute());
    455
    456         PartitionTestUtils.assertTreeStructure(a);
    457         PartitionTestUtils.assertTreeStructure(b);
    458         PartitionTestUtils.assertTreeStructure(c);
    459     }
    460
    461     @Test
    462     void testMerge_outputIsFirstInput() {
    463         // arrange
    464         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    465         a.getRoot().cut(TestLine.X_AXIS)
    466             .getPlus().attr("A")
    467             .getParent()
    468             .getMinus().attr("a");
    469
    470         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    471         b.getRoot().cut(TestLine.Y_AXIS)
    472             .getPlus().attr("B")
    473             .getParent()
    474             .getMinus().attr("b");
    475
    476         final TestMergeOperator mergeOp = new TestMergeOperator();
    477
    478         // act
    479         mergeOp.apply(a, b, a);
    480
    481         // assert
    482         Assertions.assertEquals(7, a.count());
    483         Assertions.assertEquals(3, b.count());
    484
    485         Assertions.assertEquals("B", b.findNode(new TestPoint2D(1, 0)).getAttribute());
    486         Assertions.assertEquals("b", b.findNode(new TestPoint2D(-1, 0)).getAttribute());
    487
    488         Assertions.assertEquals("aB", a.findNode(new TestPoint2D(1, 1)).getAttribute());
    489         Assertions.assertEquals("ab", a.findNode(new TestPoint2D(-1, 1)).getAttribute());
    490         Assertions.assertEquals("Ab", a.findNode(new TestPoint2D(-1, -1)).getAttribute());
    491         Assertions.assertEquals("AB", a.findNode(new TestPoint2D(1, -1)).getAttribute());
    492
    493         PartitionTestUtils.assertTreeStructure(a);
    494         PartitionTestUtils.assertTreeStructure(b);
    495     }
    496
    497     @Test
    498     void testMerge_outputIsSecondInput() {
    499         // arrange
    500         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
    501         a.getRoot().cut(TestLine.X_AXIS)
    502             .getPlus().attr("A")
    503             .getParent()
    504             .getMinus().attr("a");
    505
    506         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
    507         b.getRoot().cut(TestLine.Y_AXIS)
    508             .getPlus().attr("B")
    509             .getParent()
    510             .getMinus().attr("b");
    511
    512         final TestMergeOperator mergeOp = new TestMergeOperator();
    513
    514         // act
    515         mergeOp.apply(a, b, b);
    516
    517         // assert
    518         Assertions.assertEquals(3, a.count());
    519         Assertions.assertEquals(7, b.count());
    520
    521         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    522         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    523
    524         Assertions.assertEquals("aB", b.findNode(new TestPoint2D(1, 1)).getAttribute());
    525         Assertions.assertEquals("ab", b.findNode(new TestPoint2D(-1, 1)).getAttribute());
    526         Assertions.assertEquals("Ab", b.findNode(new TestPoint2D(-1, -1)).getAttribute());
    527         Assertions.assertEquals("AB", b.findNode(new TestPoint2D(1, -1)).getAttribute());
    528
    529         PartitionTestUtils.assertTreeStructure(a);
    530         PartitionTestUtils.assertTreeStructure(b);
    531     }
    532
    533     private static class TestMergeOperator extends AbstractBSPTreeMergeOperator<TestPoint2D, AttributeNode<TestPoint2D, String>> {
    534
    535         /** Perform the test merge operation with the given arguments.
    536          * @param input1
    537          * @param input2
    538          * @param output
    539          */
    540         public void apply(final AttributeBSPTree<TestPoint2D, String> input1, final AttributeBSPTree<TestPoint2D, String> input2,
    541                           final AttributeBSPTree<TestPoint2D, String> output) {
    542             performMerge(input1, input2, output);
    543         }
    544
    545         /** {@inheritDoc} */
    546         @Override
    547         protected AttributeNode<TestPoint2D, String> mergeLeaf(final AttributeNode<TestPoint2D, String> node1,
    548                                                                final AttributeNode<TestPoint2D, String> node2) {
    549
    550             final AttributeNode<TestPoint2D, String> leaf = node1.isLeaf() ? node1 : node2;
    551             final AttributeNode<TestPoint2D, String> subtree = node1.isInternal() ? node1 : node2;
    552
    553             final String attr = leaf.getAttribute();
    554
    555             final AttributeNode<TestPoint2D, String> output = outputSubtree(subtree);
    556             StreamSupport.stream(output.nodes().spliterator(), false)
    557                 .filter(BSPTree.Node::isLeaf)
    558                 .forEach(n -> n.setAttribute(attr + n.getAttribute()));
    559
    560             return output;
    561         }
    562     }
    563 }