View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  package org.apache.commons.geometry.core.partitioning.bsp;
    18
    19  import java.util.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.HashMap;
    22  import java.util.Iterator;
    23  import java.util.List;
    24  import java.util.Map;
    25  import java.util.NoSuchElementException;
    26  import java.util.stream.Collectors;
    27  import java.util.stream.Stream;
    28  import java.util.stream.StreamSupport;
    29
    30  import org.apache.commons.geometry.core.Transform;
    31  import org.apache.commons.geometry.core.partitioning.BoundarySource;
    32  import org.apache.commons.geometry.core.partitioning.bsp.BSPTree.FindNodeCutRule;
    33  import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
    34  import org.apache.commons.geometry.core.partitioning.test.TestBSPTree;
    35  import org.apache.commons.geometry.core.partitioning.test.TestBSPTree.TestNode;
    36  import org.apache.commons.geometry.core.partitioning.test.TestLine;
    37  import org.apache.commons.geometry.core.partitioning.test.TestLineSegment;
    38  import org.apache.commons.geometry.core.partitioning.test.TestLineSegmentCollection;
    39  import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
    40  import org.apache.commons.geometry.core.partitioning.test.TestTransform2D;
    41  import org.junit.jupiter.api.Assertions;
    42  import org.junit.jupiter.api.Test;
    43
    44  class AbstractBSPTreeTest {
    45
    46      @Test
    47      void testInitialization() {
    48          // act
    49          final TestBSPTree tree = new TestBSPTree();
    50
    51          // assert
    52          final TestNode root = tree.getRoot();
    53
    54          Assertions.assertNotNull(root);
    55          Assertions.assertNull(root.getParent());
    56
    57          PartitionTestUtils.assertIsLeafNode(root);
    58          Assertions.assertFalse(root.isPlus());
    59          Assertions.assertFalse(root.isMinus());
    60
    61          Assertions.assertSame(tree, root.getTree());
    62      }
    63
    64      @Test
    65      void testNodeStateGetters() {
    66          // arrange
    67          final TestBSPTree tree = new TestBSPTree();
    68
    69          final TestNode root = tree.getRoot();
    70          root.cut(TestLine.X_AXIS);
    71
    72          final TestNode plus = root.getPlus();
    73          final TestNode minus = root.getMinus();
    74
    75          // act/assert
    76          Assertions.assertFalse(root.isLeaf());
    77          Assertions.assertTrue(root.isInternal());
    78          Assertions.assertFalse(root.isPlus());
    79          Assertions.assertFalse(root.isMinus());
    80
    81          Assertions.assertTrue(plus.isLeaf());
    82          Assertions.assertFalse(plus.isInternal());
    83          Assertions.assertTrue(plus.isPlus());
    84          Assertions.assertFalse(plus.isMinus());
    85
    86          Assertions.assertTrue(minus.isLeaf());
    87          Assertions.assertFalse(minus.isInternal());
    88          Assertions.assertFalse(minus.isPlus());
    89          Assertions.assertTrue(minus.isMinus());
    90      }
    91
    92      @Test
    93      void testInsertCut() {
    94          // arrange
    95          final TestBSPTree tree = new TestBSPTree();
    96          final TestLine line = TestLine.X_AXIS;
    97
    98          // act
    99          final boolean result = tree.getRoot().insertCut(line);
    100
    101         // assert
    102         Assertions.assertTrue(result);
    103
    104         final TestNode root = tree.getRoot();
    105         PartitionTestUtils.assertIsInternalNode(root);
    106
    107         Assertions.assertSame(line, root.getCut().getHyperplane());
    108
    109         PartitionTestUtils.assertIsLeafNode(root.getMinus());
    110         PartitionTestUtils.assertIsLeafNode(root.getPlus());
    111     }
    112
    113     @Test
    114     void testInsertCut_fitsCutterToCell() {
    115         // arrange
    116         final TestBSPTree tree = new TestBSPTree();
    117
    118         final TestNode node = tree.getRoot()
    119             .cut(TestLine.X_AXIS)
    120             .getMinus()
    121                 .cut(TestLine.Y_AXIS)
    122                 .getPlus();
    123
    124         // act
    125         final boolean result = node.insertCut(new TestLine(0.5, 1.5, 1.5, 0.5));
    126
    127         // assert
    128         Assertions.assertTrue(result);
    129         PartitionTestUtils.assertIsInternalNode(node);
    130
    131         final TestLineSegment segment = (TestLineSegment) node.getCut();
    132
    133         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), segment.getStartPoint());
    134         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0), segment.getEndPoint());
    135     }
    136
    137     @Test
    138     void testInsertCut_doesNotPassThroughCell_intersects() {
    139         // arrange
    140         final TestBSPTree tree = new TestBSPTree();
    141
    142         final TestNode node = tree.getRoot()
    143             .cut(TestLine.X_AXIS)
    144                 .getMinus()
    145                     .cut(TestLine.Y_AXIS)
    146                     .getPlus();
    147
    148         // act
    149         final boolean result = node.insertCut(new TestLine(-2, 0, 0, -2));
    150
    151         // assert
    152         Assertions.assertFalse(result);
    153         PartitionTestUtils.assertIsLeafNode(node);
    154     }
    155
    156     @Test
    157     void testInsertCut_doesNotPassThroughCell_parallel() {
    158         // arrange
    159         final TestBSPTree tree = new TestBSPTree();
    160
    161         final TestNode node = tree.getRoot()
    162             .cut(TestLine.X_AXIS)
    163                 .getMinus();
    164
    165         // act
    166         final boolean result = node.insertCut(new TestLine(0, -1, 1, -1));
    167
    168         // assert
    169         Assertions.assertFalse(result);
    170         PartitionTestUtils.assertIsLeafNode(node);
    171     }
    172
    173     @Test
    174     void testInsertCut_doesNotPassThroughCell_removesExistingChildren() {
    175         // arrange
    176         final TestBSPTree tree = new TestBSPTree();
    177
    178         final TestNode node = tree.getRoot()
    179             .cut(TestLine.X_AXIS)
    180                 .getMinus()
    181                     .cut(TestLine.Y_AXIS)
    182                     .getPlus()
    183                         .cut(new TestLine(0, 2, 2, 0));
    184
    185         // act
    186         final boolean result = node.insertCut(new TestLine(-2, 0, 0, -2));
    187
    188         // assert
    189         Assertions.assertFalse(result);
    190         PartitionTestUtils.assertIsLeafNode(node);
    191     }
    192
    193     @Test
    194     void testInsertCut_cutExistsInTree_sameOrientation() {
    195         // arrange
    196         final TestBSPTree tree = new TestBSPTree();
    197
    198         final TestNode node = tree.getRoot()
    199                 .cut(TestLine.X_AXIS)
    200                     .getMinus()
    201                         .cut(TestLine.Y_AXIS)
    202                         .getPlus()
    203                             .cut(new TestLine(0, 2, 2, 0));
    204
    205         // act
    206         final boolean result = node.insertCut(new TestLine(0, 2, 0, 3));
    207
    208         // assert
    209         Assertions.assertFalse(result);
    210         PartitionTestUtils.assertIsLeafNode(node);
    211     }
    212
    213     @Test
    214     void testInsertCut_cutExistsInTree_oppositeOrientation() {
    215         // arrange
    216         final TestBSPTree tree = new TestBSPTree();
    217
    218         final TestNode node = tree.getRoot()
    219                 .cut(TestLine.X_AXIS)
    220                     .getMinus()
    221                         .cut(TestLine.Y_AXIS)
    222                         .getPlus()
    223                             .cut(new TestLine(0, 2, 2, 0));
    224
    225         // act
    226         final boolean result = node.insertCut(new TestLine(0, 3, 0, 2));
    227
    228         // assert
    229         Assertions.assertTrue(result);
    230         PartitionTestUtils.assertIsInternalNode(node);
    231     }
    232
    233     @Test
    234     void testInsertCut_createRegionWithThicknessOfHyperplane() {
    235         // arrange
    236         final TestBSPTree tree = new TestBSPTree();
    237
    238         final TestNode node = tree.getRoot()
    239                 .cut(TestLine.X_AXIS)
    240                     .getMinus();
    241
    242         // act
    243         final boolean result = node.insertCut(new TestLine(0, 0, -1, 0));
    244
    245         // assert
    246         Assertions.assertTrue(result);
    247
    248         Assertions.assertSame(tree.getRoot().getPlus(), tree.findNode(new TestPoint2D(0, -1e-2)));
    249         Assertions.assertSame(node.getMinus(), tree.findNode(new TestPoint2D(0, 0)));
    250         Assertions.assertSame(node.getPlus(), tree.findNode(new TestPoint2D(0, 1e-2)));
    251     }
    252
    253     @Test
    254     void testClearCut_cutExists() {
    255         // arrange
    256         final TestBSPTree tree = new TestBSPTree();
    257
    258         final TestNode node = tree.getRoot()
    259             .cut(TestLine.X_AXIS)
    260                 .getMinus()
    261                 .cut(TestLine.Y_AXIS);
    262
    263         // act
    264         final boolean result = node.clearCut();
    265
    266         // assert
    267         Assertions.assertTrue(result);
    268         Assertions.assertTrue(node.isLeaf());
    269         Assertions.assertNull(node.getPlus());
    270         Assertions.assertNull(node.getMinus());
    271     }
    272
    273     @Test
    274     void testClearCut_cutDoesNotExist() {
    275         // arrange
    276         final TestBSPTree tree = new TestBSPTree();
    277
    278         final TestNode node = tree.getRoot()
    279             .cut(TestLine.X_AXIS)
    280                 .getMinus()
    281                 .cut(TestLine.Y_AXIS)
    282                 .getMinus();
    283
    284         // act
    285         final boolean result = node.clearCut();
    286
    287         // assert
    288         Assertions.assertFalse(result);
    289         Assertions.assertTrue(node.isLeaf());
    290         Assertions.assertNull(node.getPlus());
    291         Assertions.assertNull(node.getMinus());
    292     }
    293
    294     @Test
    295     void testClearCut_root_fullTree() {
    296         // arrange
    297         final TestBSPTree tree = new TestBSPTree();
    298
    299         final TestNode node = tree.getRoot()
    300             .cut(TestLine.X_AXIS)
    301                 .getMinus()
    302                 .cut(TestLine.Y_AXIS)
    303                 .getMinus();
    304
    305         // act
    306         final boolean result = tree.getRoot().clearCut();
    307
    308         // assert
    309         Assertions.assertTrue(result);
    310         Assertions.assertTrue(node.isLeaf());
    311         Assertions.assertNull(node.getPlus());
    312         Assertions.assertNull(node.getMinus());
    313
    314         Assertions.assertEquals(1, tree.count());
    315     }
    316
    317     @Test
    318     void testClearCut_root_emptyTree() {
    319         // arrange
    320         final TestBSPTree tree = new TestBSPTree();
    321         final TestNode node = tree.getRoot();
    322
    323         // act
    324         final boolean result = node.clearCut();
    325
    326         // assert
    327         Assertions.assertFalse(result);
    328         Assertions.assertTrue(node.isLeaf());
    329         Assertions.assertNull(node.getPlus());
    330         Assertions.assertNull(node.getMinus());
    331
    332         Assertions.assertEquals(1, tree.count());
    333     }
    334
    335     @Test
    336     void testFindNode_emptyTree() {
    337         // arrange
    338         final TestBSPTree tree = new TestBSPTree();
    339         final TestNode root = tree.getRoot();
    340
    341         final List<TestPoint2D> testPoints = Arrays.asList(
    342                     new TestPoint2D(0, 0),
    343                     new TestPoint2D(1, 0),
    344                     new TestPoint2D(1, 1),
    345                     new TestPoint2D(0, 1),
    346                     new TestPoint2D(-1, 1),
    347                     new TestPoint2D(-1, 0),
    348                     new TestPoint2D(-1, -1),
    349                     new TestPoint2D(0, -1),
    350                     new TestPoint2D(1, -1)
    351                 );
    352
    353         // act/assert
    354         for (final TestPoint2D pt : testPoints) {
    355             Assertions.assertSame(root, tree.findNode(pt));
    356         }
    357
    358         for (final TestPoint2D pt : testPoints) {
    359             Assertions.assertSame(root, tree.findNode(pt, FindNodeCutRule.NODE));
    360         }
    361
    362         for (final TestPoint2D pt : testPoints) {
    363             Assertions.assertSame(root, tree.findNode(pt, FindNodeCutRule.MINUS));
    364         }
    365
    366         for (final TestPoint2D pt : testPoints) {
    367             Assertions.assertSame(root, tree.findNode(pt, FindNodeCutRule.PLUS));
    368         }
    369     }
    370
    371     @Test
    372     void testFindNode_singleArg() {
    373         // arrange
    374         final TestBSPTree tree = new TestBSPTree();
    375
    376         tree.getRoot()
    377                 .cut(TestLine.X_AXIS)
    378                 .getMinus()
    379                     .cut(TestLine.Y_AXIS)
    380                     .getPlus()
    381                         .cut(new TestLine(0, 2, 2, 0));
    382
    383         final TestNode root = tree.getRoot();
    384         final TestNode minusY = root.getPlus();
    385
    386         final TestNode yCut = root.getMinus();
    387         final TestNode minusXPlusY = yCut.getMinus();
    388
    389         final TestNode diagonalCut = yCut.getPlus();
    390         final TestNode underDiagonal = diagonalCut.getPlus();
    391         final TestNode aboveDiagonal = diagonalCut.getMinus();
    392
    393         // act/assert
    394         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 0)));
    395
    396         Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 0)));
    397         Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(1, 1)));
    398         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 1)));
    399         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1)));
    400         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 0)));
    401         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1)));
    402         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1)));
    403         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1)));
    404
    405         Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5)));
    406         Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3)));
    407     }
    408
    409     @Test
    410     void testFindNode_nodeCutBehavior() {
    411         // arrange
    412         final TestBSPTree tree = new TestBSPTree();
    413
    414         tree.getRoot()
    415                 .cut(TestLine.X_AXIS)
    416                 .getMinus()
    417                     .cut(TestLine.Y_AXIS)
    418                     .getPlus()
    419                         .cut(new TestLine(0, 2, 2, 0));
    420
    421         final TestNode root = tree.getRoot();
    422         final TestNode minusY = root.getPlus();
    423
    424         final TestNode yCut = root.getMinus();
    425         final TestNode minusXPlusY = yCut.getMinus();
    426
    427         final TestNode diagonalCut = yCut.getPlus();
    428         final TestNode underDiagonal = diagonalCut.getPlus();
    429         final TestNode aboveDiagonal = diagonalCut.getMinus();
    430
    431         final FindNodeCutRule cutBehavior = FindNodeCutRule.NODE;
    432
    433         // act/assert
    434         Assertions.assertSame(root, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
    435
    436         Assertions.assertSame(root, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
    437         Assertions.assertSame(diagonalCut, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
    438         Assertions.assertSame(yCut, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
    439         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
    440         Assertions.assertSame(root, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
    441         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
    442         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
    443         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
    444
    445         Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
    446         Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
    447     }
    448
    449     @Test
    450     void testFindNode_minusCutBehavior() {
    451         // arrange
    452         final TestBSPTree tree = new TestBSPTree();
    453
    454         tree.getRoot()
    455                 .cut(TestLine.X_AXIS)
    456                 .getMinus()
    457                     .cut(TestLine.Y_AXIS)
    458                     .getPlus()
    459                         .cut(new TestLine(0, 2, 2, 0));
    460
    461         final TestNode root = tree.getRoot();
    462         final TestNode minusY = root.getPlus();
    463
    464         final TestNode yCut = root.getMinus();
    465         final TestNode minusXPlusY = yCut.getMinus();
    466
    467         final TestNode diagonalCut = yCut.getPlus();
    468         final TestNode underDiagonal = diagonalCut.getPlus();
    469         final TestNode aboveDiagonal = diagonalCut.getMinus();
    470
    471         final FindNodeCutRule cutBehavior = FindNodeCutRule.MINUS;
    472
    473         // act/assert
    474         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
    475
    476         Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
    477         Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
    478         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
    479         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
    480         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
    481         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
    482         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
    483         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
    484
    485         Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
    486         Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
    487     }
    488
    489     @Test
    490     void testFindNode_plusCutBehavior() {
    491         // arrange
    492         final TestBSPTree tree = new TestBSPTree();
    493
    494         tree.getRoot()
    495                 .cut(TestLine.X_AXIS)
    496                 .getMinus()
    497                     .cut(TestLine.Y_AXIS)
    498                     .getPlus()
    499                         .cut(new TestLine(0, 2, 2, 0));
    500
    501         final TestNode root = tree.getRoot();
    502         final TestNode minusY = root.getPlus();
    503
    504         final TestNode yCut = root.getMinus();
    505         final TestNode minusXPlusY = yCut.getMinus();
    506
    507         final TestNode diagonalCut = yCut.getPlus();
    508         final TestNode underDiagonal = diagonalCut.getPlus();
    509         final TestNode aboveDiagonal = diagonalCut.getMinus();
    510
    511         final FindNodeCutRule cutBehavior = FindNodeCutRule.PLUS;
    512
    513         // act/assert
    514         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
    515
    516         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
    517         Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
    518         Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
    519         Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
    520         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
    521         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
    522         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
    523         Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
    524
    525         Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
    526         Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
    527     }
    528
    529     @Test
    530     void testInsert_convex_emptyTree() {
    531         // arrange
    532         final TestBSPTree tree = new TestBSPTree();
    533
    534         // act
    535         tree.insert(new TestLineSegment(1, 0, 1, 1));
    536
    537         // assert
    538         final TestNode root = tree.getRoot();
    539         Assertions.assertFalse(root.isLeaf());
    540         Assertions.assertTrue(root.getMinus().isLeaf());
    541         Assertions.assertTrue(root.getPlus().isLeaf());
    542
    543         final TestLineSegment seg = (TestLineSegment) root.getCut();
    544         PartitionTestUtils.assertPointsEqual(
    545                 new TestPoint2D(1, Double.NEGATIVE_INFINITY),
    546                 seg.getStartPoint());
    547         PartitionTestUtils.assertPointsEqual(
    548                 new TestPoint2D(1, Double.POSITIVE_INFINITY),
    549                 seg.getEndPoint());
    550     }
    551
    552     @Test
    553     void testInsert_convex_noSplit() {
    554         // arrange
    555         final TestBSPTree tree = new TestBSPTree();
    556         tree.getRoot()
    557             .cut(TestLine.X_AXIS)
    558             .getMinus()
    559                 .cut(TestLine.Y_AXIS);
    560
    561         // act
    562         tree.insert(new TestLineSegment(0.5, 1.5, 1.5, 0.5));
    563
    564         // assert
    565         final TestNode root = tree.getRoot();
    566         Assertions.assertFalse(root.isLeaf());
    567
    568         final TestNode node = tree.findNode(new TestPoint2D(0.5, 0.5));
    569         final TestLineSegment seg = (TestLineSegment) node.getParent().getCut();
    570
    571         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), seg.getStartPoint());
    572         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0), seg.getEndPoint());
    573
    574         Assertions.assertTrue(tree.getRoot().getPlus().isLeaf());
    575         Assertions.assertTrue(tree.getRoot().getMinus().getMinus().isLeaf());
    576     }
    577
    578     @Test
    579     void testInsert_convex_split() {
    580         // arrange
    581         final TestBSPTree tree = new TestBSPTree();
    582         tree.getRoot()
    583             .cut(TestLine.X_AXIS)
    584             .getMinus()
    585                 .cut(TestLine.Y_AXIS);
    586
    587         // act
    588         tree.insert(new TestLineSegment(-0.5, 2.5, 2.5, -0.5));
    589
    590         // assert
    591         final TestNode root = tree.getRoot();
    592         Assertions.assertFalse(root.isLeaf());
    593
    594         final TestNode plusXPlusY = tree.getRoot().getMinus().getPlus();
    595         final TestLineSegment plusXPlusYSeg = (TestLineSegment) plusXPlusY.getCut();
    596
    597         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), plusXPlusYSeg.getStartPoint());
    598         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0), plusXPlusYSeg.getEndPoint());
    599
    600         final TestNode minusY = tree.getRoot().getPlus();
    601         final TestLineSegment minusYSeg = (TestLineSegment) minusY.getCut();
    602
    603         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0), minusYSeg.getStartPoint());
    604         PartitionTestUtils.assertPointsEqual(
    605                 new TestPoint2D(Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY), minusYSeg.getEndPoint());
    606
    607         final TestNode minusXPlusY = tree.getRoot().getMinus().getMinus();
    608         final TestLineSegment minusXPlusYSeg = (TestLineSegment) minusXPlusY.getCut();
    609
    610         PartitionTestUtils.assertPointsEqual(
    611                 new TestPoint2D(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY), minusXPlusYSeg.getStartPoint());
    612         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), minusXPlusYSeg.getEndPoint());
    613     }
    614
    615     @Test
    616     void testInsert_convexList_convexRegion() {
    617         // arrange
    618         final TestBSPTree tree = new TestBSPTree();
    619
    620         final TestLineSegment a = new TestLineSegment(0, 0, 1, 0);
    621         final TestLineSegment b = new TestLineSegment(1, 0, 0, 1);
    622         final TestLineSegment c = new TestLineSegment(0, 1, 0, 0);
    623
    624         // act
    625         tree.insert(Arrays.asList(a, b, c));
    626
    627         // assert
    628         final List<TestLineSegment> segments = getLineSegments(tree);
    629
    630         Assertions.assertEquals(3, segments.size());
    631
    632         PartitionTestUtils.assertSegmentsEqual(
    633                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    634                 segments.get(0));
    635         PartitionTestUtils.assertSegmentsEqual(
    636                 new TestLineSegment(-Math.sqrt(0.5), Double.POSITIVE_INFINITY, new TestLine(1, 0, 0, 1)),
    637                 segments.get(1));
    638         PartitionTestUtils.assertSegmentsEqual(c, segments.get(2));
    639     }
    640
    641     @Test
    642     void testInsert_convexList_concaveRegion() {
    643         // arrange
    644         final TestBSPTree tree = new TestBSPTree();
    645
    646         final TestLineSegment a = new TestLineSegment(-1, -1, 1, -1);
    647         final TestLineSegment b = new TestLineSegment(1, -1, 0, 0);
    648         final TestLineSegment c = new TestLineSegment(0, 0, 1, 1);
    649         final TestLineSegment d = new TestLineSegment(1, 1, -1, 1);
    650         final TestLineSegment e = new TestLineSegment(-1, 1, -1, -1);
    651
    652         // act
    653         tree.insert(Arrays.asList(a, b, c, d, e));
    654
    655         // assert
    656         final List<TestLineSegment> segments = getLineSegments(tree);
    657
    658         Assertions.assertEquals(5, segments.size());
    659
    660         PartitionTestUtils.assertSegmentsEqual(
    661                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, new TestLine(-1, -1, 1, -1)),
    662                 segments.get(0));
    663         PartitionTestUtils.assertSegmentsEqual(
    664                 new TestLineSegment(-Math.sqrt(2), Double.POSITIVE_INFINITY, new TestLine(1, -1, 0, 0)),
    665                 segments.get(1));
    666         PartitionTestUtils.assertSegmentsEqual(
    667                 new TestLineSegment(-1, 1, -1, -1),
    668                 segments.get(2));
    669
    670         PartitionTestUtils.assertSegmentsEqual(
    671                 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(0, 0, 1, 1)),
    672                 segments.get(3));
    673         PartitionTestUtils.assertSegmentsEqual(
    674                 new TestLineSegment(1, 1, -1, 1),
    675                 segments.get(4));
    676     }
    677
    678     @Test
    679     void testInsert_hyperplaneSubset_concaveRegion() {
    680         // arrange
    681         final TestBSPTree tree = new TestBSPTree();
    682
    683         final TestLineSegment a = new TestLineSegment(-1, -1, 1, -1);
    684         final TestLineSegment b = new TestLineSegment(1, -1, 0, 0);
    685         final TestLineSegment c = new TestLineSegment(0, 0, 1, 1);
    686         final TestLineSegment d = new TestLineSegment(1, 1, -1, 1);
    687         final TestLineSegment e = new TestLineSegment(-1, 1, -1, -1);
    688
    689         final TestLineSegmentCollection coll = new TestLineSegmentCollection(
    690                 Arrays.asList(a, b, c, d, e));
    691
    692         // act
    693         tree.insert(coll);
    694
    695         // assert
    696         final List<TestLineSegment> segments = getLineSegments(tree);
    697
    698         Assertions.assertEquals(5, segments.size());
    699
    700         PartitionTestUtils.assertSegmentsEqual(
    701                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, new TestLine(-1, -1, 1, -1)),
    702                 segments.get(0));
    703         PartitionTestUtils.assertSegmentsEqual(
    704                 new TestLineSegment(-Math.sqrt(2), Double.POSITIVE_INFINITY, new TestLine(1, -1, 0, 0)),
    705                 segments.get(1));
    706         PartitionTestUtils.assertSegmentsEqual(
    707                 new TestLineSegment(-1, 1, -1, -1),
    708                 segments.get(2));
    709
    710         PartitionTestUtils.assertSegmentsEqual(
    711                 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(0, 0, 1, 1)),
    712                 segments.get(3));
    713         PartitionTestUtils.assertSegmentsEqual(
    714                 new TestLineSegment(1, 1, -1, 1),
    715                 segments.get(4));
    716     }
    717
    718     @Test
    719     void testInsert_boundarySource() {
    720         // arrange
    721         final TestBSPTree tree = new TestBSPTree();
    722
    723         final TestLineSegment a = new TestLineSegment(-1, -1, 1, -1);
    724         final TestLineSegment b = new TestLineSegment(1, -1, 0, 0);
    725         final TestLineSegment c = new TestLineSegment(0, 0, 1, 1);
    726         final TestLineSegment d = new TestLineSegment(1, 1, -1, 1);
    727         final TestLineSegment e = new TestLineSegment(-1, 1, -1, -1);
    728
    729         final BoundarySource<TestLineSegment> src = () -> Stream.of(a, b, c, d, e);
    730
    731         // act
    732         tree.insert(src);
    733
    734         // assert
    735         final List<TestLineSegment> segments = getLineSegments(tree);
    736
    737         Assertions.assertEquals(5, segments.size());
    738
    739         PartitionTestUtils.assertSegmentsEqual(
    740                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, new TestLine(-1, -1, 1, -1)),
    741                 segments.get(0));
    742         PartitionTestUtils.assertSegmentsEqual(
    743                 new TestLineSegment(-Math.sqrt(2), Double.POSITIVE_INFINITY, new TestLine(1, -1, 0, 0)),
    744                 segments.get(1));
    745         PartitionTestUtils.assertSegmentsEqual(
    746                 new TestLineSegment(-1, 1, -1, -1),
    747                 segments.get(2));
    748
    749         PartitionTestUtils.assertSegmentsEqual(
    750                 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(0, 0, 1, 1)),
    751                 segments.get(3));
    752         PartitionTestUtils.assertSegmentsEqual(
    753                 new TestLineSegment(1, 1, -1, 1),
    754                 segments.get(4));
    755     }
    756
    757     @Test
    758     void testInsert_boundarySource_emptySource() {
    759         // arrange
    760         final TestBSPTree tree = new TestBSPTree();
    761
    762         final BoundarySource<TestLineSegment> src = Stream::empty;
    763
    764         // act
    765         tree.insert(src);
    766
    767         // assert
    768         Assertions.assertEquals(1, tree.count());
    769     }
    770
    771     @Test
    772     void testCount() {
    773         // arrange
    774         final TestBSPTree tree = new TestBSPTree();
    775
    776         // act/assert
    777         Assertions.assertEquals(1, tree.count());
    778         Assertions.assertEquals(1, tree.getRoot().count());
    779
    780         tree.getRoot().insertCut(TestLine.X_AXIS);
    781         Assertions.assertEquals(1, tree.getRoot().getMinus().count());
    782         Assertions.assertEquals(1, tree.getRoot().getPlus().count());
    783         Assertions.assertEquals(3, tree.count());
    784
    785         tree.getRoot().getPlus().insertCut(TestLine.Y_AXIS);
    786         Assertions.assertEquals(1, tree.getRoot().getMinus().count());
    787         Assertions.assertEquals(3, tree.getRoot().getPlus().count());
    788         Assertions.assertEquals(5, tree.count());
    789
    790         tree.getRoot().getMinus().insertCut(TestLine.Y_AXIS);
    791         Assertions.assertEquals(3, tree.getRoot().getMinus().count());
    792         Assertions.assertEquals(3, tree.getRoot().getPlus().count());
    793         Assertions.assertEquals(7, tree.count());
    794
    795         tree.getRoot().getMinus().insertCut(new TestLine(new TestPoint2D(-1, -1), new TestPoint2D(1, -1)));
    796         Assertions.assertEquals(1, tree.getRoot().getMinus().count());
    797         Assertions.assertEquals(3, tree.getRoot().getPlus().count());
    798         Assertions.assertEquals(5, tree.count());
    799     }
    800
    801     @Test
    802     void testHeight() {
    803         // arrange
    804         final TestBSPTree tree = new TestBSPTree();
    805
    806         // act/assert
    807         Assertions.assertEquals(0, tree.height());
    808         Assertions.assertEquals(0, tree.getRoot().height());
    809
    810         tree.getRoot().insertCut(TestLine.X_AXIS);
    811         Assertions.assertEquals(0, tree.getRoot().getMinus().height());
    812         Assertions.assertEquals(0, tree.getRoot().getPlus().height());
    813         Assertions.assertEquals(1, tree.height());
    814
    815         tree.getRoot().getPlus().insertCut(TestLine.Y_AXIS);
    816         Assertions.assertEquals(0, tree.getRoot().getMinus().height());
    817         Assertions.assertEquals(1, tree.getRoot().getPlus().height());
    818         Assertions.assertEquals(2, tree.height());
    819
    820         tree.getRoot().getMinus().insertCut(TestLine.Y_AXIS);
    821         Assertions.assertEquals(1, tree.getRoot().getMinus().height());
    822         Assertions.assertEquals(1, tree.getRoot().getPlus().height());
    823         Assertions.assertEquals(2, tree.height());
    824
    825         tree.getRoot().getMinus().clearCut();
    826         Assertions.assertEquals(0, tree.getRoot().getMinus().height());
    827         Assertions.assertEquals(1, tree.getRoot().getPlus().height());
    828         Assertions.assertEquals(2, tree.height());
    829
    830         tree.getRoot().getPlus().getPlus()
    831             .insertCut(new TestLine(new TestPoint2D(0, -1), new TestPoint2D(1, -1)));
    832
    833         Assertions.assertEquals(0, tree.getRoot().getMinus().height());
    834         Assertions.assertEquals(2, tree.getRoot().getPlus().height());
    835         Assertions.assertEquals(3, tree.height());
    836     }
    837
    838     @Test
    839     void testDepth() {
    840         // arrange
    841         final TestBSPTree tree = new TestBSPTree();
    842
    843         final TestNode root = tree.getRoot();
    844         root.cut(TestLine.X_AXIS)
    845                 .getMinus()
    846                     .cut(TestLine.Y_AXIS);
    847
    848         // act/assert
    849         Assertions.assertEquals(0, root.depth());
    850
    851         Assertions.assertEquals(1, root.getPlus().depth());
    852
    853         Assertions.assertEquals(1, root.getMinus().depth());
    854         Assertions.assertEquals(2, root.getMinus().getPlus().depth());
    855         Assertions.assertEquals(2, root.getMinus().getMinus().depth());
    856     }
    857
    858     @Test
    859     void testDepth_detachedNodes() {
    860         // arrange
    861         final TestBSPTree tree = new TestBSPTree();
    862
    863         final TestNode detached = new TestNode(tree);
    864         detached.cut(TestLine.X_AXIS)
    865             .getMinus()
    866                 .cut(TestLine.Y_AXIS);
    867
    868         // act/assert
    869         Assertions.assertEquals(-1, detached.depth());
    870
    871         Assertions.assertEquals(-1, detached.getPlus().depth());
    872
    873         Assertions.assertEquals(-1, detached.getMinus().depth());
    874         Assertions.assertEquals(-1, detached.getMinus().getPlus().depth());
    875         Assertions.assertEquals(-1, detached.getMinus().getMinus().depth());
    876     }
    877
    878     @Test
    879     void testVisit_defaultOrder() {
    880         // arrange
    881         final TestBSPTree tree = new TestBSPTree();
    882         tree.getRoot().cut(TestLine.X_AXIS)
    883             .getMinus().cut(TestLine.Y_AXIS);
    884
    885         final TestNode root = tree.getRoot();
    886         final TestNode minus = root.getMinus();
    887         final TestNode plus = root.getPlus();
    888         final TestNode minusMinus = minus.getMinus();
    889         final TestNode minusPlus = minus.getPlus();
    890
    891         final List<TestNode> nodes = new ArrayList<>();
    892
    893         // act
    894         tree.accept(node -> {
    895             nodes.add(node);
    896             return BSPTreeVisitor.Result.CONTINUE;
    897         });
    898
    899         // assert
    900         Assertions.assertEquals(
    901                 Arrays.asList(root, minus, minusMinus, minusPlus, plus),
    902                 nodes);
    903     }
    904
    905     @Test
    906     void testVisit_specifiedOrder() {
    907         // arrange
    908         final TestBSPTree tree = new TestBSPTree();
    909         tree.getRoot().cut(TestLine.X_AXIS)
    910             .getMinus().cut(TestLine.Y_AXIS);
    911
    912         final TestNode root = tree.getRoot();
    913         final TestNode minus = root.getMinus();
    914         final TestNode plus = root.getPlus();
    915         final TestNode minusMinus = minus.getMinus();
    916         final TestNode minusPlus = minus.getPlus();
    917
    918         // act/assert
    919         final TestVisitor plusMinusNode = new TestVisitor(BSPTreeVisitor.Order.PLUS_MINUS_NODE);
    920         tree.accept(plusMinusNode);
    921         Assertions.assertEquals(
    922                 Arrays.asList(plus, minusPlus, minusMinus, minus, root),
    923                 plusMinusNode.getVisited());
    924
    925         final TestVisitor plusNodeMinus = new TestVisitor(BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    926         tree.accept(plusNodeMinus);
    927         Assertions.assertEquals(
    928                 Arrays.asList(plus, root, minusPlus, minus, minusMinus),
    929                 plusNodeMinus.getVisited());
    930
    931         final TestVisitor minusPlusNode = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE);
    932         tree.accept(minusPlusNode);
    933         Assertions.assertEquals(
    934                 Arrays.asList(minusMinus, minusPlus, minus, plus, root),
    935                 minusPlusNode.getVisited());
    936
    937         final TestVisitor minusNodePlus = new TestVisitor(BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    938         tree.accept(minusNodePlus);
    939         Assertions.assertEquals(
    940                 Arrays.asList(minusMinus, minus, minusPlus, root, plus),
    941                 minusNodePlus.getVisited());
    942
    943         final TestVisitor nodeMinusPlus = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS);
    944         tree.accept(nodeMinusPlus);
    945         Assertions.assertEquals(
    946                 Arrays.asList(root, minus, minusMinus, minusPlus, plus),
    947                 nodeMinusPlus.getVisited());
    948
    949         final TestVisitor nodePlusMinus = new TestVisitor(BSPTreeVisitor.Order.NODE_PLUS_MINUS);
    950         tree.accept(nodePlusMinus);
    951         Assertions.assertEquals(
    952                 Arrays.asList(root, plus, minus, minusPlus, minusMinus),
    953                 nodePlusMinus.getVisited());
    954     }
    955
    956     @Test
    957     void testVisit_nullVisitOrderSkipsSubtree() {
    958         // arrange
    959         final TestBSPTree tree = new TestBSPTree();
    960         tree.getRoot().cut(TestLine.X_AXIS)
    961             .getMinus().cut(TestLine.Y_AXIS);
    962
    963         final TestNode root = tree.getRoot();
    964         final TestNode plus = root.getPlus();
    965         final TestNode minus = root.getMinus();
    966
    967         final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS) {
    968             @Override
    969             public Order visitOrder(final TestNode node) {
    970                 if (node == minus) {
    971                     return null;
    972                 }
    973                 return super.visitOrder(node);
    974             }
    975         };
    976
    977         // act
    978         tree.accept(visitor);
    979
    980         // assert
    981         Assertions.assertEquals(
    982                 Arrays.asList(root, plus),
    983                 visitor.getVisited());
    984     }
    985
    986     @Test
    987     void testVisit_noneVisitOrderSkipsSubtree() {
    988         // arrange
    989         final TestBSPTree tree = new TestBSPTree();
    990         tree.getRoot().cut(TestLine.X_AXIS)
    991             .getMinus().cut(TestLine.Y_AXIS);
    992
    993         final TestNode root = tree.getRoot();
    994         final TestNode plus = root.getPlus();
    995         final TestNode minus = root.getMinus();
    996
    997         final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS) {
    998             @Override
    999             public Order visitOrder(final TestNode node) {
    1000                 if (node == minus) {
    1001                     return Order.NONE;
    1002                 }
    1003                 return super.visitOrder(node);
    1004             }
    1005         };
    1006
    1007         // act
    1008         tree.accept(visitor);
    1009
    1010         // assert
    1011         Assertions.assertEquals(
    1012                 Arrays.asList(root, plus),
    1013                 visitor.getVisited());
    1014     }
    1015
    1016     @Test
    1017     void testVisit_visitorReturnsNull_terminatesEarly() {
    1018         // arrange
    1019         final TestBSPTree tree = new TestBSPTree();
    1020         tree.getRoot().cut(TestLine.X_AXIS)
    1021             .getMinus().cut(TestLine.Y_AXIS);
    1022
    1023         final TestNode root = tree.getRoot();
    1024         final TestNode minus = root.getMinus();
    1025         final TestNode minusMinus = minus.getMinus();
    1026         final TestNode minusPlus = minus.getPlus();
    1027
    1028         final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE) {
    1029             @Override
    1030             public Result visit(final TestNode node) {
    1031                 super.visit(node);
    1032
    1033                 if (node == minus) {
    1034                     return null;
    1035                 }
    1036                 return Result.CONTINUE;
    1037             }
    1038         };
    1039
    1040         // act
    1041         tree.accept(visitor);
    1042
    1043         // assert
    1044         Assertions.assertEquals(
    1045                 Arrays.asList(minusMinus, minusPlus, minus),
    1046                 visitor.getVisited());
    1047     }
    1048
    1049     @Test
    1050     void testVisit_visitorReturnsTerminate_terminatesEarly() {
    1051         // arrange
    1052         final TestBSPTree tree = new TestBSPTree();
    1053         tree.getRoot().cut(TestLine.X_AXIS)
    1054             .getMinus().cut(TestLine.Y_AXIS);
    1055
    1056         final TestNode root = tree.getRoot();
    1057         final TestNode minus = root.getMinus();
    1058         final TestNode minusMinus = minus.getMinus();
    1059         final TestNode minusPlus = minus.getPlus();
    1060
    1061         final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE) {
    1062             @Override
    1063             public Result visit(final TestNode node) {
    1064                 super.visit(node);
    1065
    1066                 if (node == minus) {
    1067                     return Result.TERMINATE;
    1068                 }
    1069                 return Result.CONTINUE;
    1070             }
    1071         };
    1072
    1073         // act
    1074         tree.accept(visitor);
    1075
    1076         // assert
    1077         Assertions.assertEquals(
    1078                 Arrays.asList(minusMinus, minusPlus, minus),
    1079                 visitor.getVisited());
    1080     }
    1081
    1082     @Test
    1083     void testVisit_earlyTerminationPermutations() {
    1084         // arrange
    1085         final TestBSPTree tree = new TestBSPTree();
    1086         tree.getRoot().cut(TestLine.X_AXIS)
    1087             .getMinus().cut(TestLine.Y_AXIS);
    1088
    1089         final TestNode root = tree.getRoot();
    1090         final TestNode minus = root.getMinus();
    1091         final TestNode plus = root.getPlus();
    1092         final TestNode minusMinus = minus.getMinus();
    1093         final TestNode minusPlus = minus.getPlus();
    1094
    1095         // act/assert
    1096         final TestVisitor plusMinusNode = new TestVisitor(BSPTreeVisitor.Order.PLUS_MINUS_NODE).withTerminationNode(minus);
    1097         tree.accept(plusMinusNode);
    1098         Assertions.assertEquals(
    1099                 Arrays.asList(plus, minusPlus, minusMinus, minus),
    1100                 plusMinusNode.getVisited());
    1101
    1102         final TestVisitor plusNodeMinus = new TestVisitor(BSPTreeVisitor.Order.PLUS_NODE_MINUS).withTerminationNode(minus);
    1103         tree.accept(plusNodeMinus);
    1104         Assertions.assertEquals(
    1105                 Arrays.asList(plus, root, minusPlus, minus),
    1106                 plusNodeMinus.getVisited());
    1107
    1108         final TestVisitor minusPlusNode = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE).withTerminationNode(minus);
    1109         tree.accept(minusPlusNode);
    1110         Assertions.assertEquals(
    1111                 Arrays.asList(minusMinus, minusPlus, minus),
    1112                 minusPlusNode.getVisited());
    1113
    1114         final TestVisitor minusNodePlus = new TestVisitor(BSPTreeVisitor.Order.MINUS_NODE_PLUS).withTerminationNode(minus);
    1115         tree.accept(minusNodePlus);
    1116         Assertions.assertEquals(
    1117                 Arrays.asList(minusMinus, minus),
    1118                 minusNodePlus.getVisited());
    1119
    1120         final TestVisitor nodeMinusPlus = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS).withTerminationNode(minus);
    1121         tree.accept(nodeMinusPlus);
    1122         Assertions.assertEquals(
    1123                 Arrays.asList(root, minus),
    1124                 nodeMinusPlus.getVisited());
    1125
    1126         final TestVisitor nodePlusMinus = new TestVisitor(BSPTreeVisitor.Order.NODE_PLUS_MINUS).withTerminationNode(minus);
    1127         tree.accept(nodePlusMinus);
    1128         Assertions.assertEquals(
    1129                 Arrays.asList(root, plus, minus),
    1130                 nodePlusMinus.getVisited());
    1131     }
    1132
    1133     @Test
    1134     void testVisit_visitNode() {
    1135         // arrange
    1136         final TestBSPTree tree = new TestBSPTree();
    1137         tree.getRoot().cut(TestLine.X_AXIS)
    1138             .getMinus().cut(TestLine.Y_AXIS);
    1139
    1140         final TestNode root = tree.getRoot();
    1141         final TestNode minus = root.getMinus();
    1142         final TestNode minusMinus = minus.getMinus();
    1143         final TestNode minusPlus = minus.getPlus();
    1144
    1145         final List<TestNode> nodes = new ArrayList<>();
    1146
    1147         // act
    1148         minus.accept(node -> {
    1149             nodes.add(node);
    1150             return BSPTreeVisitor.Result.CONTINUE;
    1151         });
    1152
    1153         // assert
    1154         Assertions.assertEquals(
    1155                 Arrays.asList(minus, minusMinus, minusPlus),
    1156                 nodes);
    1157     }
    1158
    1159     @Test
    1160     void testNodesIterable_emptyTree() {
    1161         // arrange
    1162         final TestBSPTree tree = new TestBSPTree();
    1163         final List<TestNode> nodes = new ArrayList<>();
    1164
    1165         // act
    1166         for (final TestNode node : tree.nodes()) {
    1167             nodes.add(node);
    1168         }
    1169
    1170         // assert
    1171         Assertions.assertEquals(1, nodes.size());
    1172         Assertions.assertSame(tree.getRoot(), nodes.get(0));
    1173     }
    1174
    1175     @Test
    1176     void testNodesIterable_multipleNodes() {
    1177         // arrange
    1178         final TestBSPTree tree = new TestBSPTree();
    1179
    1180         final TestNode root = tree.getRoot();
    1181         root.cut(TestLine.X_AXIS)
    1182                 .getMinus()
    1183                     .cut(TestLine.Y_AXIS)
    1184                  .getParent()
    1185                  .getPlus()
    1186                      .cut(TestLine.Y_AXIS);
    1187
    1188         final List<TestNode> nodes = new ArrayList<>();
    1189
    1190         // act
    1191         for (final TestNode node : tree.nodes()) {
    1192             nodes.add(node);
    1193         }
    1194
    1195         // assert
    1196         Assertions.assertEquals(7, nodes.size());
    1197         Assertions.assertSame(root, nodes.get(0));
    1198
    1199         Assertions.assertSame(root.getMinus(), nodes.get(1));
    1200         Assertions.assertSame(root.getMinus().getMinus(), nodes.get(2));
    1201         Assertions.assertSame(root.getMinus().getPlus(), nodes.get(3));
    1202
    1203         Assertions.assertSame(root.getPlus(), nodes.get(4));
    1204         Assertions.assertSame(root.getPlus().getMinus(), nodes.get(5));
    1205         Assertions.assertSame(root.getPlus().getPlus(), nodes.get(6));
    1206     }
    1207
    1208
    1209     @Test
    1210     void testNodesIterable_iteratorThrowsNoSuchElementExceptionAtEnd() {
    1211         // arrange
    1212         final TestBSPTree tree = new TestBSPTree();
    1213
    1214         final Iterator<TestNode> it = tree.nodes().iterator();
    1215         it.next();
    1216
    1217         // act
    1218         try {
    1219             it.next();
    1220             Assertions.fail("Operation should have thrown an exception");
    1221         } catch (final NoSuchElementException exc) {
    1222             // expected
    1223         }
    1224     }
    1225
    1226     @Test
    1227     void testSubtreeNodesIterable_singleNodeSubtree() {
    1228         // arrange
    1229         final TestBSPTree tree = new TestBSPTree();
    1230         final TestNode node = tree.getRoot().cut(TestLine.X_AXIS)
    1231             .getMinus()
    1232                 .cut(TestLine.Y_AXIS)
    1233                 .getMinus();
    1234
    1235         final List<TestNode> nodes = new ArrayList<>();
    1236         // act
    1237         for (final TestNode n : node.nodes()) {
    1238             nodes.add(n);
    1239         }
    1240
    1241         // assert
    1242         Assertions.assertEquals(1, nodes.size());
    1243         Assertions.assertSame(node, nodes.get(0));
    1244     }
    1245
    1246     @Test
    1247     void testSubtreeNodesIterable_multipleNodeSubtree() {
    1248         // arrange
    1249         final TestBSPTree tree = new TestBSPTree();
    1250         final TestNode node = tree.getRoot().cut(TestLine.X_AXIS)
    1251             .getMinus()
    1252                 .cut(TestLine.Y_AXIS);
    1253
    1254         final List<TestNode> nodes = new ArrayList<>();
    1255         // act
    1256         for (final TestNode n : node.nodes()) {
    1257             nodes.add(n);
    1258         }
    1259
    1260         // assert
    1261         Assertions.assertEquals(3, nodes.size());
    1262         Assertions.assertSame(node, nodes.get(0));
    1263         Assertions.assertSame(node.getMinus(), nodes.get(1));
    1264         Assertions.assertSame(node.getPlus(), nodes.get(2));
    1265     }
    1266
    1267     @Test
    1268     void testNodeTrim() {
    1269         // arrange
    1270         final TestBSPTree tree = new TestBSPTree();
    1271         tree.getRoot().cut(TestLine.Y_AXIS)
    1272             .getPlus()
    1273                 .cut(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 1)))
    1274                 .getPlus()
    1275                     .cut(new TestLine(new TestPoint2D(1.5, 1.5), new TestPoint2D(2, 1)));
    1276
    1277         final TestNode root = tree.getRoot();
    1278         final TestNode plus = root.getPlus();
    1279         final TestNode plusMinus = plus.getMinus();
    1280         final TestNode plusPlusPlus = plus.getPlus().getPlus();
    1281
    1282         final TestLineSegment xAxisSeg = TestLine.X_AXIS.span();
    1283         final TestLineSegment shortSeg = new TestLineSegment(new TestPoint2D(2, 0), new TestPoint2D(2, 2));
    1284
    1285         // act/assert
    1286         Assertions.assertSame(xAxisSeg, root.trim(xAxisSeg));
    1287         Assertions.assertSame(shortSeg, root.trim(shortSeg));
    1288
    1289         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1290                 (TestLineSegment) plus.trim(xAxisSeg));
    1291         Assertions.assertSame(shortSeg, plus.trim(shortSeg));
    1292
    1293         Assertions.assertNull(plusMinus.trim(xAxisSeg));
    1294         Assertions.assertNull(plusMinus.trim(shortSeg));
    1295
    1296         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, 3, TestLine.X_AXIS),
    1297                 (TestLineSegment) plusPlusPlus.trim(xAxisSeg));
    1298         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(new TestPoint2D(2, 0), new TestPoint2D(2, 1)),
    1299                 (TestLineSegment) plusPlusPlus.trim(shortSeg));
    1300     }
    1301
    1302     @Test
    1303     void testCopy_rootOnly() {
    1304         // arrange
    1305         final TestBSPTree tree = new TestBSPTree();
    1306
    1307         // act
    1308         final TestBSPTree copy = new TestBSPTree();
    1309         copy.copy(tree);
    1310
    1311         // assert
    1312         Assertions.assertNotSame(tree, copy);
    1313         Assertions.assertNotSame(tree.getRoot(), copy.getRoot());
    1314
    1315         Assertions.assertEquals(tree.count(), copy.count());
    1316     }
    1317
    1318     @Test
    1319     void testCopy_withCuts() {
    1320         // arrange
    1321         final TestBSPTree tree = new TestBSPTree();
    1322         tree.getRoot()
    1323             .cut(TestLine.X_AXIS)
    1324             .getMinus()
    1325                 .cut(TestLine.Y_AXIS);
    1326
    1327         // act
    1328         final TestBSPTree copy = new TestBSPTree();
    1329         copy.copy(tree);
    1330
    1331         // assert
    1332         Assertions.assertNotSame(tree, copy);
    1333         assertNodesCopiedRecursive(tree.getRoot(), copy.getRoot());
    1334         Assertions.assertEquals(tree.count(), copy.count());
    1335     }
    1336
    1337     @Test
    1338     void testCopy_changesToOneTreeDoNotAffectCopy() {
    1339         // arrange
    1340         final TestBSPTree tree = new TestBSPTree();
    1341         tree.getRoot()
    1342             .cut(TestLine.X_AXIS)
    1343             .getMinus()
    1344                 .cut(TestLine.Y_AXIS);
    1345
    1346         // act
    1347         final TestBSPTree copy = new TestBSPTree();
    1348         copy.copy(tree);
    1349         tree.getRoot().clearCut();
    1350
    1351         // assert
    1352         Assertions.assertEquals(1, tree.count());
    1353         Assertions.assertEquals(5, copy.count());
    1354     }
    1355
    1356     @Test
    1357     void testCopy_instancePassedAsArgument() {
    1358         // arrange
    1359         final TestBSPTree tree = new TestBSPTree();
    1360         tree.getRoot()
    1361             .cut(TestLine.X_AXIS)
    1362             .getMinus()
    1363                 .cut(TestLine.Y_AXIS);
    1364
    1365         // act
    1366         tree.copy(tree);
    1367
    1368         // assert
    1369         Assertions.assertEquals(5, tree.count());
    1370     }
    1371
    1372     @Test
    1373     void testExtract_singleNodeTree() {
    1374         // arrange
    1375         final TestBSPTree tree = new TestBSPTree();
    1376
    1377         final TestBSPTree result = new TestBSPTree();
    1378         result.getRoot().insertCut(TestLine.X_AXIS);
    1379
    1380         // act
    1381         result.extract(tree.getRoot());
    1382
    1383         // assert
    1384         Assertions.assertNotSame(tree.getRoot(), result.getRoot());
    1385         Assertions.assertEquals(1, tree.count());
    1386         Assertions.assertEquals(1, result.count());
    1387
    1388         PartitionTestUtils.assertTreeStructure(tree);
    1389         PartitionTestUtils.assertTreeStructure(result);
    1390     }
    1391
    1392     @Test
    1393     void testExtract_clearsExistingNodesInCallingTree() {
    1394         // arrange
    1395         final TestBSPTree tree = new TestBSPTree();
    1396
    1397         final TestBSPTree result = new TestBSPTree();
    1398         result.getRoot().cut(TestLine.X_AXIS)
    1399             .getMinus().cut(TestLine.Y_AXIS);
    1400
    1401         // act
    1402         result.extract(tree.getRoot());
    1403
    1404         // assert
    1405         Assertions.assertNotSame(tree.getRoot(), result.getRoot());
    1406         Assertions.assertEquals(1, tree.count());
    1407         Assertions.assertEquals(1, result.count());
    1408
    1409         PartitionTestUtils.assertTreeStructure(tree);
    1410         PartitionTestUtils.assertTreeStructure(result);
    1411     }
    1412
    1413     @Test
    1414     void testExtract_internalNode() {
    1415         // arrange
    1416         final TestBSPTree tree = new TestBSPTree();
    1417         tree.insert(Arrays.asList(
    1418                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1419                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1420                     new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
    1421                     new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
    1422                     new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
    1423                 ));
    1424
    1425         final TestBSPTree result = new TestBSPTree();
    1426
    1427         // act
    1428         result.extract(tree.getRoot().getPlus());
    1429
    1430         // assert
    1431         Assertions.assertEquals(7, result.count());
    1432
    1433         final List<TestLineSegment> resultSegments = getLineSegments(result);
    1434         Assertions.assertEquals(3, resultSegments.size());
    1435
    1436         PartitionTestUtils.assertSegmentsEqual(
    1437                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1438                 resultSegments.get(0));
    1439         PartitionTestUtils.assertSegmentsEqual(
    1440                 new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.Y_AXIS),
    1441                 resultSegments.get(1));
    1442         PartitionTestUtils.assertSegmentsEqual(
    1443                 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(new TestPoint2D(0, -2), new TestPoint2D(1, -2))),
    1444                 resultSegments.get(2));
    1445
    1446         Assertions.assertEquals(13, tree.count());
    1447
    1448         final List<TestLineSegment> inputSegment = getLineSegments(tree);
    1449         Assertions.assertEquals(6, inputSegment.size());
    1450
    1451         PartitionTestUtils.assertTreeStructure(tree);
    1452         PartitionTestUtils.assertTreeStructure(result);
    1453     }
    1454
    1455     @Test
    1456     void testExtract_leafNode() {
    1457         // arrange
    1458         final TestBSPTree tree = new TestBSPTree();
    1459         tree.insert(Arrays.asList(
    1460                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1461                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1462                     new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
    1463                     new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
    1464                     new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
    1465                 ));
    1466
    1467         final TestPoint2D pt = new TestPoint2D(1, 1);
    1468
    1469         final TestNode node = tree.findNode(pt);
    1470         final TestBSPTree result = new TestBSPTree();
    1471
    1472         // act
    1473         result.extract(node);
    1474
    1475         // assert
    1476         final TestNode resultNode = result.findNode(pt);
    1477         Assertions.assertNotNull(resultNode);
    1478         Assertions.assertNotSame(node, resultNode);
    1479
    1480         Assertions.assertEquals(7, result.count());
    1481
    1482         final List<TestLineSegment> resultSegments = getLineSegments(result);
    1483         Assertions.assertEquals(3, resultSegments.size());
    1484
    1485         PartitionTestUtils.assertSegmentsEqual(
    1486                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1487                 resultSegments.get(0));
    1488         PartitionTestUtils.assertSegmentsEqual(
    1489                 new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
    1490                 resultSegments.get(1));
    1491         PartitionTestUtils.assertSegmentsEqual(
    1492                 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0)),
    1493                 resultSegments.get(2));
    1494
    1495         Assertions.assertEquals(13, tree.count());
    1496
    1497         final List<TestLineSegment> inputSegment = getLineSegments(tree);
    1498         Assertions.assertEquals(6, inputSegment.size());
    1499
    1500         PartitionTestUtils.assertTreeStructure(tree);
    1501         PartitionTestUtils.assertTreeStructure(result);
    1502     }
    1503
    1504     @Test
    1505     void testExtract_extractFromSameTree() {
    1506         // arrange
    1507         final TestBSPTree tree = new TestBSPTree();
    1508         tree.insert(Arrays.asList(
    1509                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1510                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1511                     new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
    1512                     new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
    1513                     new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
    1514                 ));
    1515
    1516         final TestPoint2D pt = new TestPoint2D(1, 1);
    1517
    1518         final TestNode node = tree.findNode(pt);
    1519
    1520         // act
    1521         tree.extract(node);
    1522
    1523         // assert
    1524         final TestNode resultNode = tree.findNode(pt);
    1525         Assertions.assertNotNull(resultNode);
    1526         Assertions.assertSame(node, resultNode);
    1527
    1528         Assertions.assertEquals(7, tree.count());
    1529
    1530         final List<TestLineSegment> resultSegments = getLineSegments(tree);
    1531         Assertions.assertEquals(3, resultSegments.size());
    1532
    1533         PartitionTestUtils.assertSegmentsEqual(
    1534                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1535                 resultSegments.get(0));
    1536         PartitionTestUtils.assertSegmentsEqual(
    1537                 new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
    1538                 resultSegments.get(1));
    1539         PartitionTestUtils.assertSegmentsEqual(
    1540                 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0)),
    1541                 resultSegments.get(2));
    1542
    1543         PartitionTestUtils.assertTreeStructure(tree);
    1544     }
    1545
    1546     @Test
    1547     void testTransform_singleNodeTree() {
    1548         // arrange
    1549         final TestBSPTree tree = new TestBSPTree();
    1550
    1551         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
    1552
    1553         // act
    1554         tree.transform(t);
    1555
    1556         // assert
    1557         Assertions.assertEquals(1, tree.count());
    1558         Assertions.assertTrue(tree.getRoot().isLeaf());
    1559     }
    1560
    1561     @Test
    1562     void testTransform_singleCut() {
    1563         // arrange
    1564         final TestBSPTree tree = new TestBSPTree();
    1565         tree.getRoot().insertCut(TestLine.X_AXIS);
    1566
    1567         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
    1568
    1569         // act
    1570         tree.transform(t);
    1571
    1572         // assert
    1573         Assertions.assertEquals(3, tree.count());
    1574
    1575         final List<TestLineSegment> segments = getLineSegments(tree);
    1576         Assertions.assertEquals(1, segments.size());
    1577
    1578         final TestLineSegment seg = segments.get(0);
    1579         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 2), seg.getStartPoint());
    1580         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, 2), seg.getEndPoint());
    1581     }
    1582
    1583     @Test
    1584     void testTransform_multipleCuts() {
    1585         // arrange
    1586         final TestBSPTree tree = new TestBSPTree();
    1587         tree.insert(Arrays.asList(
    1588                     new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
    1589                     new TestLineSegment(new TestPoint2D(-1, -1), new TestPoint2D(1, 1)),
    1590                     new TestLineSegment(new TestPoint2D(3, 1), new TestPoint2D(3, 2))
    1591                 ));
    1592
    1593         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 2));
    1594
    1595         // act
    1596         tree.transform(t);
    1597
    1598         // assert
    1599         Assertions.assertEquals(9, tree.count());
    1600
    1601         final List<TestLineSegment> segments = getLineSegments(tree);
    1602         Assertions.assertEquals(4, segments.size());
    1603
    1604         final TestLineSegment segment1 = segments.get(0);
    1605         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 2), segment1.getStartPoint());
    1606         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, 2), segment1.getEndPoint());
    1607
    1608         final TestLineSegment segment2 = segments.get(1);
    1609         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), segment2.getStartPoint());
    1610         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY), segment2.getEndPoint());
    1611
    1612         final TestLineSegment segment3 = segments.get(2);
    1613         PartitionTestUtils.assertPointsEqual(new TestPoint2D(1.5, 2), segment3.getStartPoint());
    1614         PartitionTestUtils.assertPointsEqual(new TestPoint2D(1.5, 5), segment3.getEndPoint());
    1615
    1616         final TestLineSegment segment4 = segments.get(3);
    1617         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY), segment4.getStartPoint());
    1618         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), segment4.getEndPoint());
    1619     }
    1620
    1621     @Test
    1622     void testTransform_xAxisReflection() {
    1623         // arrange
    1624         final TestBSPTree tree = new TestBSPTree();
    1625         tree.insert(Arrays.asList(
    1626                     new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
    1627                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1628                     new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
    1629                 ));
    1630
    1631         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), p.getY()));
    1632
    1633         final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
    1634
    1635         // act
    1636         tree.transform(t);
    1637
    1638         // assert
    1639         checkTransformedPointNodeMap(tree, t, pointNodeMap);
    1640
    1641         final List<TestLineSegment> segments = getLineSegments(tree);
    1642         Assertions.assertEquals(4, segments.size());
    1643     }
    1644
    1645     @Test
    1646     void testTransform_yAxisReflection() {
    1647         // arrange
    1648         final TestBSPTree tree = new TestBSPTree();
    1649         tree.insert(Arrays.asList(
    1650                     new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
    1651                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1652                     new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
    1653                 ));
    1654
    1655         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), -p.getY()));
    1656
    1657         final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
    1658
    1659         // act
    1660         tree.transform(t);
    1661
    1662         // assert
    1663         checkTransformedPointNodeMap(tree, t, pointNodeMap);
    1664
    1665         final List<TestLineSegment> segments = getLineSegments(tree);
    1666         Assertions.assertEquals(4, segments.size());
    1667     }
    1668
    1669     @Test
    1670     void testTransform_xAndYAxisReflection() {
    1671         // arrange
    1672         final TestBSPTree tree = new TestBSPTree();
    1673         tree.insert(Arrays.asList(
    1674                     new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
    1675                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1676                     new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
    1677                 ));
    1678
    1679         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), -p.getY()));
    1680
    1681         final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
    1682
    1683         // act
    1684         tree.transform(t);
    1685
    1686         // assert
    1687         checkTransformedPointNodeMap(tree, t, pointNodeMap);
    1688
    1689         final List<TestLineSegment> segments = getLineSegments(tree);
    1690         Assertions.assertEquals(4, segments.size());
    1691     }
    1692
    1693     @Test
    1694     void testTreeString() {
    1695         // arrange
    1696         final TestBSPTree tree = new TestBSPTree();
    1697         tree.getRoot().cut(TestLine.X_AXIS)
    1698             .getMinus().cut(TestLine.Y_AXIS);
    1699
    1700         // act
    1701         final String str = tree.treeString();
    1702
    1703         // assert
    1704         final String[] lines = str.split("\n");
    1705         Assertions.assertEquals(5, lines.length);
    1706         Assertions.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
    1707         Assertions.assertTrue(lines[1].startsWith("    [-] TestNode[cut= TestLineSegment"));
    1708         Assertions.assertEquals("        [-] TestNode[cut= null]", lines[2]);
    1709         Assertions.assertEquals("        [+] TestNode[cut= null]", lines[3]);
    1710         Assertions.assertEquals("    [+] TestNode[cut= null]", lines[4]);
    1711     }
    1712
    1713     @Test
    1714     void testTreeString_emptyTree() {
    1715         // arrange
    1716         final TestBSPTree tree = new TestBSPTree();
    1717
    1718         // act
    1719         final String str = tree.treeString();
    1720
    1721         // assert
    1722         Assertions.assertEquals("TestNode[cut= null]", str);
    1723     }
    1724
    1725     @Test
    1726     void testTreeString_reachesMaxDepth() {
    1727         // arrange
    1728         final TestBSPTree tree = new TestBSPTree();
    1729         tree.getRoot().cut(TestLine.X_AXIS)
    1730             .getMinus().cut(TestLine.Y_AXIS)
    1731             .getMinus().cut(new TestLine(new TestPoint2D(-2, 1), new TestPoint2D(0, 1)));
    1732
    1733         // act
    1734         final String str = tree.treeString(1);
    1735
    1736         // assert
    1737         final String[] lines = str.split("\n");
    1738         Assertions.assertEquals(4, lines.length);
    1739         Assertions.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
    1740         Assertions.assertTrue(lines[1].startsWith("    [-] TestNode[cut= TestLineSegment"));
    1741         Assertions.assertEquals("        ...", lines[2]);
    1742         Assertions.assertEquals("    [+] TestNode[cut= null]", lines[3]);
    1743     }
    1744
    1745     @Test
    1746     void testTreeString_zeroMaxDepth() {
    1747         // arrange
    1748         final TestBSPTree tree = new TestBSPTree();
    1749         tree.getRoot().cut(TestLine.X_AXIS)
    1750             .getMinus().cut(TestLine.Y_AXIS)
    1751             .getMinus().cut(new TestLine(new TestPoint2D(-2, 1), new TestPoint2D(0, 1)));
    1752
    1753         // act
    1754         final String str = tree.treeString(0);
    1755
    1756         // assert
    1757         final String[] lines = str.split("\n");
    1758         Assertions.assertEquals(2, lines.length);
    1759         Assertions.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
    1760         Assertions.assertTrue(lines[1].startsWith("    ..."));
    1761     }
    1762
    1763     @Test
    1764     void testTreeString_negativeMaxDepth() {
    1765         // arrange
    1766         final TestBSPTree tree = new TestBSPTree();
    1767         tree.getRoot().cut(TestLine.X_AXIS)
    1768             .getMinus().cut(TestLine.Y_AXIS)
    1769             .getMinus().cut(new TestLine(new TestPoint2D(-2, 1), new TestPoint2D(0, 1)));
    1770
    1771         // act
    1772         final String str = tree.treeString(-1);
    1773
    1774         // assert
    1775         Assertions.assertEquals("", str);
    1776     }
    1777
    1778     @Test
    1779     void testToString() {
    1780         // arrange
    1781         final TestBSPTree tree = new TestBSPTree();
    1782         tree.getRoot().insertCut(TestLine.Y_AXIS);
    1783
    1784         // act
    1785         final String str = tree.toString();
    1786
    1787         // assert
    1788         final String msg = "Unexpected toString() representation: " + str;
    1789
    1790         Assertions.assertTrue(str.contains("TestBSPTree"), msg);
    1791         Assertions.assertTrue(str.contains("count= 3"), msg);
    1792         Assertions.assertTrue(str.contains("height= 1"), msg);
    1793     }
    1794
    1795     @Test
    1796     void testNodeToString() {
    1797         // arrange
    1798         final TestBSPTree tree = new TestBSPTree();
    1799         tree.getRoot().cut(TestLine.X_AXIS);
    1800
    1801         // act
    1802         final String str = tree.getRoot().toString();
    1803
    1804         // assert
    1805         Assertions.assertTrue(str.contains("TestNode"));
    1806         Assertions.assertTrue(str.contains("cut= TestLineSegment"));
    1807     }
    1808
    1809     @Test
    1810     void testSplitIntoTree() {
    1811         // arrange
    1812         final TestBSPTree tree = new TestBSPTree();
    1813         tree.getRoot()
    1814             .cut(TestLine.X_AXIS)
    1815             .getMinus()
    1816                 .cut(TestLine.Y_AXIS);
    1817
    1818         final TestBSPTree minus = new TestBSPTree();
    1819         final TestBSPTree plus = new TestBSPTree();
    1820
    1821         final TestLine splitter = new TestLine(new TestPoint2D(0,  0), new TestPoint2D(-1, 1));
    1822
    1823         // act
    1824         tree.splitIntoTrees(splitter, minus, plus);
    1825
    1826         // assert
    1827         final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
    1828                 Double.POSITIVE_INFINITY, splitter);
    1829
    1830         Assertions.assertEquals(5, tree.count());
    1831         Assertions.assertEquals(2, tree.height());
    1832
    1833         Assertions.assertEquals(5, minus.count());
    1834         Assertions.assertEquals(2, minus.height());
    1835
    1836         final List<TestLineSegment> minusSegments = getLineSegments(minus);
    1837         Assertions.assertEquals(2, minusSegments.size());
    1838         PartitionTestUtils.assertSegmentsEqual(splitSegment, minusSegments.get(0));
    1839         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.X_AXIS),
    1840                 minusSegments.get(1));
    1841
    1842         Assertions.assertEquals(7, plus.count());
    1843         Assertions.assertEquals(3, plus.height());
    1844
    1845         final List<TestLineSegment> plusSegments = getLineSegments(plus);
    1846         Assertions.assertEquals(3, plusSegments.size());
    1847         PartitionTestUtils.assertSegmentsEqual(splitSegment, plusSegments.get(0));
    1848         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1849                 plusSegments.get(1));
    1850         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
    1851                 plusSegments.get(2));
    1852     }
    1853
    1854     @Test
    1855     void testSplitIntoTree_minusOnly() {
    1856         // arrange
    1857         final TestBSPTree tree = new TestBSPTree();
    1858         tree.getRoot()
    1859             .cut(TestLine.X_AXIS)
    1860             .getMinus()
    1861                 .cut(TestLine.Y_AXIS);
    1862
    1863         final TestBSPTree minus = new TestBSPTree();
    1864
    1865         final TestLine splitter = new TestLine(new TestPoint2D(0,  0), new TestPoint2D(-1, 1));
    1866
    1867         // act
    1868         tree.splitIntoTrees(splitter, minus, null);
    1869
    1870         // assert
    1871         final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
    1872                 Double.POSITIVE_INFINITY, splitter);
    1873
    1874         Assertions.assertEquals(5, tree.count());
    1875         Assertions.assertEquals(2, tree.height());
    1876
    1877         Assertions.assertEquals(5, minus.count());
    1878         Assertions.assertEquals(2, minus.height());
    1879
    1880         final List<TestLineSegment> minusSegments = getLineSegments(minus);
    1881         Assertions.assertEquals(2, minusSegments.size());
    1882         PartitionTestUtils.assertSegmentsEqual(splitSegment, minusSegments.get(0));
    1883         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.X_AXIS),
    1884                 minusSegments.get(1));
    1885     }
    1886
    1887     @Test
    1888     void testSplitIntoTree_plusOnly() {
    1889         // arrange
    1890         final TestBSPTree tree = new TestBSPTree();
    1891         tree.getRoot()
    1892             .cut(TestLine.X_AXIS)
    1893             .getMinus()
    1894                 .cut(TestLine.Y_AXIS);
    1895
    1896         final TestBSPTree plus = new TestBSPTree();
    1897
    1898         final TestLine splitter = new TestLine(new TestPoint2D(0,  0), new TestPoint2D(-1, 1));
    1899
    1900         // act
    1901         tree.splitIntoTrees(splitter, null, plus);
    1902
    1903         // assert
    1904         final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
    1905                 Double.POSITIVE_INFINITY, splitter);
    1906
    1907         Assertions.assertEquals(5, tree.count());
    1908         Assertions.assertEquals(2, tree.height());
    1909
    1910         Assertions.assertEquals(7, plus.count());
    1911         Assertions.assertEquals(3, plus.height());
    1912
    1913         final List<TestLineSegment> plusSegments = getLineSegments(plus);
    1914         Assertions.assertEquals(3, plusSegments.size());
    1915         PartitionTestUtils.assertSegmentsEqual(splitSegment, plusSegments.get(0));
    1916         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1917                 plusSegments.get(1));
    1918         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
    1919                 plusSegments.get(2));
    1920     }
    1921
    1922     private void assertNodesCopiedRecursive(final TestNode orig, final TestNode copy) {
    1923         Assertions.assertNotSame(orig, copy);
    1924
    1925         Assertions.assertEquals(orig.getCut(), copy.getCut());
    1926
    1927         if (orig.isLeaf()) {
    1928             Assertions.assertNull(copy.getMinus());
    1929             Assertions.assertNull(copy.getPlus());
    1930         } else {
    1931             Assertions.assertNotSame(orig.getMinus(), copy.getMinus());
    1932             Assertions.assertNotSame(orig.getPlus(), copy.getPlus());
    1933
    1934             assertNodesCopiedRecursive(orig.getMinus(), copy.getMinus());
    1935             assertNodesCopiedRecursive(orig.getPlus(), copy.getPlus());
    1936         }
    1937
    1938         Assertions.assertEquals(orig.depth(), copy.depth());
    1939         Assertions.assertEquals(orig.count(), copy.count());
    1940     }
    1941
    1942     private static List<TestLineSegment> getLineSegments(final TestBSPTree tree) {
    1943         return StreamSupport.stream(tree.nodes().spliterator(), false)
    1944             .filter(BSPTree.Node::isInternal)
    1945             .map(n -> (TestLineSegment) n.getCut())
    1946             .collect(Collectors.toList());
    1947     }
    1948
    1949     /** Create a map of points to the nodes that they resolve to in the
    1950      * given tree.
    1951      */
    1952     private static Map<TestPoint2D, TestNode> createPointNodeMap(final TestBSPTree tree, final int min, final int max) {
    1953         final Map<TestPoint2D, TestNode> map = new HashMap<>();
    1954
    1955         for (int x = min; x <= max; ++x) {
    1956             for (int y = min; y <= max; ++y) {
    1957                 final TestPoint2D pt = new TestPoint2D(x, y);
    1958                 final TestNode node = tree.findNode(pt, FindNodeCutRule.NODE);
    1959
    1960                 map.put(pt, node);
    1961             }
    1962         }
    1963
    1964         return map;
    1965     }
    1966
    1967     /** Check that transformed points resolve to the same tree nodes that were found when the original
    1968      * points were resolved in the untransformed tree.
    1969      * @param transformedTree
    1970      * @param transform
    1971      * @param pointNodeMap
    1972      */
    1973     private static void checkTransformedPointNodeMap(final TestBSPTree transformedTree, final Transform<TestPoint2D> transform,
    1974                                                      final Map<TestPoint2D, TestNode> pointNodeMap) {
    1975
    1976         for (final Map.Entry<TestPoint2D, TestNode> entry : pointNodeMap.entrySet()) {
    1977             final TestNode expectedNode = entry.getValue();
    1978             final TestPoint2D transformedPt = transform.apply(entry.getKey());
    1979
    1980             final String msg = "Expected transformed point " + transformedPt + " to resolve to node " + expectedNode;
    1981             Assertions.assertSame(expectedNode, transformedTree.findNode(transformedPt, FindNodeCutRule.NODE), msg);
    1982         }
    1983     }
    1984
    1985     private static class TestVisitor implements BSPTreeVisitor<TestPoint2D, TestNode> {
    1986
    1987         private final Order order;
    1988
    1989         private TestNode terminationNode;
    1990
    1991         private final List<TestNode> visited = new ArrayList<>();
    1992
    1993         TestVisitor(final Order order) {
    1994             this.order = order;
    1995         }
    1996
    1997         public TestVisitor withTerminationNode(final TestNode newTerminationNode) {
    1998             this.terminationNode = newTerminationNode;
    1999             return this;
    2000         }
    2001
    2002         @Override
    2003         public Result visit(final TestNode node) {
    2004             visited.add(node);
    2005             return (terminationNode == node) ?
    2006                     Result.TERMINATE :
    2007                     Result.CONTINUE;
    2008         }
    2009
    2010         @Override
    2011         public Order visitOrder(final TestNode node) {
    2012             return order;
    2013         }
    2014
    2015         public List<TestNode> getVisited() {
    2016             return visited;
    2017         }
    2018     }
    2019 }