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.Assert;
    27  import org.junit.Test;
    28
    29  public class AbstractBSPTreeMergeOperatorTest {
    30
    31      @Test
    32      public 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          Assert.assertEquals(1, a.count());
    49          Assert.assertEquals(1, b.count());
    50          Assert.assertEquals(1, c.count());
    51
    52          Assert.assertEquals("A", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    53          Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    54
    55          Assert.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    56          Assert.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    57
    58          Assert.assertEquals("AB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    59          Assert.assertEquals("AB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    60          Assert.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    61          Assert.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      public 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          Assert.assertEquals(3, a.count());
    89          Assert.assertEquals(1, b.count());
    90          Assert.assertEquals(3, c.count());
    91
    92          Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    93          Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    94
    95          Assert.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    96          Assert.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    97
    98          Assert.assertEquals("Ba", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    99          Assert.assertEquals("Ba", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    100         Assert.assertEquals("BA", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    101         Assert.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     public 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         Assert.assertEquals(1, a.count());
    129         Assert.assertEquals(3, b.count());
    130         Assert.assertEquals(3, c.count());
    131
    132         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    133         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    134
    135         Assert.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    136         Assert.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    137
    138         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    139         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    140         Assert.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    141         Assert.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     public 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         Assert.assertEquals(3, a.count());
    172         Assert.assertEquals(3, b.count());
    173         Assert.assertEquals(7, c.count());
    174
    175         Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    176         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    177
    178         Assert.assertEquals("B", b.findNode(new TestPoint2D(1, 0)).getAttribute());
    179         Assert.assertEquals("b", b.findNode(new TestPoint2D(-1, 0)).getAttribute());
    180
    181         Assert.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    182         Assert.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    183         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    184         Assert.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     public 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         Assert.assertEquals(3, a.count());
    215         Assert.assertEquals(3, b.count());
    216         Assert.assertEquals(3, c.count());
    217
    218         Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    219         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    220
    221         Assert.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    222         Assert.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    223
    224         Assert.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    225         Assert.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    226         Assert.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    227         Assert.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     public 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         Assert.assertEquals(3, a.count());
    258         Assert.assertEquals(3, b.count());
    259         Assert.assertEquals(3, c.count());
    260
    261         Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    262         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    263
    264         Assert.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    265         Assert.assertEquals("b", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    266
    267         Assert.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    268         Assert.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    269         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    270         Assert.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     public 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         Assert.assertEquals(3, a.count());
    301         Assert.assertEquals(3, b.count());
    302         Assert.assertEquals(5, c.count());
    303
    304         Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    305         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    306
    307         Assert.assertEquals("b", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    308         Assert.assertEquals("B", b.findNode(new TestPoint2D(0, -3)).getAttribute());
    309
    310         Assert.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    311         Assert.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    312         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    313         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    314
    315         Assert.assertEquals("AB", c.findNode(new TestPoint2D(-1, -3)).getAttribute());
    316         Assert.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     public 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         Assert.assertEquals(3, a.count());
    347         Assert.assertEquals(3, b.count());
    348         Assert.assertEquals(5, c.count());
    349
    350         Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    351         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    352
    353         Assert.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
    354         Assert.assertEquals("b", b.findNode(new TestPoint2D(0, -3)).getAttribute());
    355
    356         Assert.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    357         Assert.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    358         Assert.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    359         Assert.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    360
    361         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -3)).getAttribute());
    362         Assert.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     public 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         Assert.assertEquals(3, a.count());
    393         Assert.assertEquals(3, b.count());
    394         Assert.assertEquals(5, c.count());
    395
    396         Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    397         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    398
    399         Assert.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    400         Assert.assertEquals("b", b.findNode(new TestPoint2D(0, 3)).getAttribute());
    401
    402         Assert.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    403         Assert.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    404         Assert.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    405         Assert.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    406
    407         Assert.assertEquals("ab", c.findNode(new TestPoint2D(-1, 3)).getAttribute());
    408         Assert.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     public 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         Assert.assertEquals(3, a.count());
    439         Assert.assertEquals(3, b.count());
    440         Assert.assertEquals(5, c.count());
    441
    442         Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    443         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    444
    445         Assert.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
    446         Assert.assertEquals("B", b.findNode(new TestPoint2D(0, 3)).getAttribute());
    447
    448         Assert.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
    449         Assert.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
    450         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
    451         Assert.assertEquals("Ab", c.findNode(new TestPoint2D(1, -1)).getAttribute());
    452
    453         Assert.assertEquals("aB", c.findNode(new TestPoint2D(-1, 3)).getAttribute());
    454         Assert.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     public 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         Assert.assertEquals(7, a.count());
    483         Assert.assertEquals(3, b.count());
    484
    485         Assert.assertEquals("B", b.findNode(new TestPoint2D(1, 0)).getAttribute());
    486         Assert.assertEquals("b", b.findNode(new TestPoint2D(-1, 0)).getAttribute());
    487
    488         Assert.assertEquals("aB", a.findNode(new TestPoint2D(1, 1)).getAttribute());
    489         Assert.assertEquals("ab", a.findNode(new TestPoint2D(-1, 1)).getAttribute());
    490         Assert.assertEquals("Ab", a.findNode(new TestPoint2D(-1, -1)).getAttribute());
    491         Assert.assertEquals("AB", a.findNode(new TestPoint2D(1, -1)).getAttribute());
    492
    493         PartitionTestUtils.assertTreeStructure(a);
    494         PartitionTestUtils.assertTreeStructure(b);
    495     }
    496
    497     @Test
    498     public 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         Assert.assertEquals(3, a.count());
    519         Assert.assertEquals(7, b.count());
    520
    521         Assert.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
    522         Assert.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
    523
    524         Assert.assertEquals("aB", b.findNode(new TestPoint2D(1, 1)).getAttribute());
    525         Assert.assertEquals("ab", b.findNode(new TestPoint2D(-1, 1)).getAttribute());
    526         Assert.assertEquals("Ab", b.findNode(new TestPoint2D(-1, -1)).getAttribute());
    527         Assert.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 }