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.Assert;
    42  import org.junit.Test;
    43
    44  public class AbstractBSPTreeTest {
    45
    46      @Test
    47      public void testInitialization() {
    48          // act
    49          final TestBSPTree tree = new TestBSPTree();
    50
    51          // assert
    52          final TestNode root = tree.getRoot();
    53
    54          Assert.assertNotNull(root);
    55          Assert.assertNull(root.getParent());
    56
    57          PartitionTestUtils.assertIsLeafNode(root);
    58          Assert.assertFalse(root.isPlus());
    59          Assert.assertFalse(root.isMinus());
    60
    61          Assert.assertSame(tree, root.getTree());
    62      }
    63
    64      @Test
    65      public 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          Assert.assertFalse(root.isLeaf());
    77          Assert.assertTrue(root.isInternal());
    78          Assert.assertFalse(root.isPlus());
    79          Assert.assertFalse(root.isMinus());
    80
    81          Assert.assertTrue(plus.isLeaf());
    82          Assert.assertFalse(plus.isInternal());
    83          Assert.assertTrue(plus.isPlus());
    84          Assert.assertFalse(plus.isMinus());
    85
    86          Assert.assertTrue(minus.isLeaf());
    87          Assert.assertFalse(minus.isInternal());
    88          Assert.assertFalse(minus.isPlus());
    89          Assert.assertTrue(minus.isMinus());
    90      }
    91
    92      @Test
    93      public 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         Assert.assertTrue(result);
    103
    104         final TestNode root = tree.getRoot();
    105         PartitionTestUtils.assertIsInternalNode(root);
    106
    107         Assert.assertSame(line, root.getCut().getHyperplane());
    108
    109         PartitionTestUtils.assertIsLeafNode(root.getMinus());
    110         PartitionTestUtils.assertIsLeafNode(root.getPlus());
    111     }
    112
    113     @Test
    114     public 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         Assert.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     public 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         Assert.assertFalse(result);
    153         PartitionTestUtils.assertIsLeafNode(node);
    154     }
    155
    156     @Test
    157     public 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         Assert.assertFalse(result);
    170         PartitionTestUtils.assertIsLeafNode(node);
    171     }
    172
    173     @Test
    174     public 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         Assert.assertFalse(result);
    190         PartitionTestUtils.assertIsLeafNode(node);
    191     }
    192
    193     @Test
    194     public 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         Assert.assertFalse(result);
    210         PartitionTestUtils.assertIsLeafNode(node);
    211     }
    212
    213     @Test
    214     public 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         Assert.assertTrue(result);
    230         PartitionTestUtils.assertIsInternalNode(node);
    231     }
    232
    233     @Test
    234     public 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         Assert.assertTrue(result);
    247
    248         Assert.assertSame(tree.getRoot().getPlus(), tree.findNode(new TestPoint2D(0, -1e-2)));
    249         Assert.assertSame(node.getMinus(), tree.findNode(new TestPoint2D(0, 0)));
    250         Assert.assertSame(node.getPlus(), tree.findNode(new TestPoint2D(0, 1e-2)));
    251     }
    252
    253     @Test
    254     public 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         Assert.assertTrue(result);
    268         Assert.assertTrue(node.isLeaf());
    269         Assert.assertNull(node.getPlus());
    270         Assert.assertNull(node.getMinus());
    271     }
    272
    273     @Test
    274     public 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         Assert.assertFalse(result);
    289         Assert.assertTrue(node.isLeaf());
    290         Assert.assertNull(node.getPlus());
    291         Assert.assertNull(node.getMinus());
    292     }
    293
    294     @Test
    295     public 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         Assert.assertTrue(result);
    310         Assert.assertTrue(node.isLeaf());
    311         Assert.assertNull(node.getPlus());
    312         Assert.assertNull(node.getMinus());
    313
    314         Assert.assertEquals(1, tree.count());
    315     }
    316
    317     @Test
    318     public 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         Assert.assertFalse(result);
    328         Assert.assertTrue(node.isLeaf());
    329         Assert.assertNull(node.getPlus());
    330         Assert.assertNull(node.getMinus());
    331
    332         Assert.assertEquals(1, tree.count());
    333     }
    334
    335     @Test
    336     public 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             Assert.assertSame(root, tree.findNode(pt));
    356         }
    357
    358         for (final TestPoint2D pt : testPoints) {
    359             Assert.assertSame(root, tree.findNode(pt, FindNodeCutRule.NODE));
    360         }
    361
    362         for (final TestPoint2D pt : testPoints) {
    363             Assert.assertSame(root, tree.findNode(pt, FindNodeCutRule.MINUS));
    364         }
    365
    366         for (final TestPoint2D pt : testPoints) {
    367             Assert.assertSame(root, tree.findNode(pt, FindNodeCutRule.PLUS));
    368         }
    369     }
    370
    371     @Test
    372     public 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         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 0)));
    395
    396         Assert.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 0)));
    397         Assert.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(1, 1)));
    398         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 1)));
    399         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1)));
    400         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 0)));
    401         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1)));
    402         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1)));
    403         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1)));
    404
    405         Assert.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5)));
    406         Assert.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3)));
    407     }
    408
    409     @Test
    410     public 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         Assert.assertSame(root, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
    435
    436         Assert.assertSame(root, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
    437         Assert.assertSame(diagonalCut, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
    438         Assert.assertSame(yCut, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
    439         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
    440         Assert.assertSame(root, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
    441         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
    442         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
    443         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
    444
    445         Assert.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
    446         Assert.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
    447     }
    448
    449     @Test
    450     public 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         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
    475
    476         Assert.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
    477         Assert.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
    478         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
    479         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
    480         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
    481         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
    482         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
    483         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
    484
    485         Assert.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
    486         Assert.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
    487     }
    488
    489     @Test
    490     public 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         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
    515
    516         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
    517         Assert.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
    518         Assert.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
    519         Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
    520         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
    521         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
    522         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
    523         Assert.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
    524
    525         Assert.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
    526         Assert.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
    527     }
    528
    529     @Test
    530     public 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         Assert.assertFalse(root.isLeaf());
    540         Assert.assertTrue(root.getMinus().isLeaf());
    541         Assert.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     public 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         Assert.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         Assert.assertTrue(tree.getRoot().getPlus().isLeaf());
    575         Assert.assertTrue(tree.getRoot().getMinus().getMinus().isLeaf());
    576     }
    577
    578     @Test
    579     public 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         Assert.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     public 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         Assert.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     public 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         Assert.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     public 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         Assert.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     public 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         Assert.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     public 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         Assert.assertEquals(1, tree.count());
    769     }
    770
    771     @Test
    772     public void testCount() {
    773         // arrange
    774         final TestBSPTree tree = new TestBSPTree();
    775
    776         // act/assert
    777         Assert.assertEquals(1, tree.count());
    778         Assert.assertEquals(1, tree.getRoot().count());
    779
    780         tree.getRoot().insertCut(TestLine.X_AXIS);
    781         Assert.assertEquals(1, tree.getRoot().getMinus().count());
    782         Assert.assertEquals(1, tree.getRoot().getPlus().count());
    783         Assert.assertEquals(3, tree.count());
    784
    785         tree.getRoot().getPlus().insertCut(TestLine.Y_AXIS);
    786         Assert.assertEquals(1, tree.getRoot().getMinus().count());
    787         Assert.assertEquals(3, tree.getRoot().getPlus().count());
    788         Assert.assertEquals(5, tree.count());
    789
    790         tree.getRoot().getMinus().insertCut(TestLine.Y_AXIS);
    791         Assert.assertEquals(3, tree.getRoot().getMinus().count());
    792         Assert.assertEquals(3, tree.getRoot().getPlus().count());
    793         Assert.assertEquals(7, tree.count());
    794
    795         tree.getRoot().getMinus().insertCut(new TestLine(new TestPoint2D(-1, -1), new TestPoint2D(1, -1)));
    796         Assert.assertEquals(1, tree.getRoot().getMinus().count());
    797         Assert.assertEquals(3, tree.getRoot().getPlus().count());
    798         Assert.assertEquals(5, tree.count());
    799     }
    800
    801     @Test
    802     public void testHeight() {
    803         // arrange
    804         final TestBSPTree tree = new TestBSPTree();
    805
    806         // act/assert
    807         Assert.assertEquals(0, tree.height());
    808         Assert.assertEquals(0, tree.getRoot().height());
    809
    810         tree.getRoot().insertCut(TestLine.X_AXIS);
    811         Assert.assertEquals(0, tree.getRoot().getMinus().height());
    812         Assert.assertEquals(0, tree.getRoot().getPlus().height());
    813         Assert.assertEquals(1, tree.height());
    814
    815         tree.getRoot().getPlus().insertCut(TestLine.Y_AXIS);
    816         Assert.assertEquals(0, tree.getRoot().getMinus().height());
    817         Assert.assertEquals(1, tree.getRoot().getPlus().height());
    818         Assert.assertEquals(2, tree.height());
    819
    820         tree.getRoot().getMinus().insertCut(TestLine.Y_AXIS);
    821         Assert.assertEquals(1, tree.getRoot().getMinus().height());
    822         Assert.assertEquals(1, tree.getRoot().getPlus().height());
    823         Assert.assertEquals(2, tree.height());
    824
    825         tree.getRoot().getMinus().clearCut();
    826         Assert.assertEquals(0, tree.getRoot().getMinus().height());
    827         Assert.assertEquals(1, tree.getRoot().getPlus().height());
    828         Assert.assertEquals(2, tree.height());
    829
    830         tree.getRoot().getPlus().getPlus()
    831             .insertCut(new TestLine(new TestPoint2D(0, -1), new TestPoint2D(1, -1)));
    832
    833         Assert.assertEquals(0, tree.getRoot().getMinus().height());
    834         Assert.assertEquals(2, tree.getRoot().getPlus().height());
    835         Assert.assertEquals(3, tree.height());
    836     }
    837
    838     @Test
    839     public 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         Assert.assertEquals(0, root.depth());
    850
    851         Assert.assertEquals(1, root.getPlus().depth());
    852
    853         Assert.assertEquals(1, root.getMinus().depth());
    854         Assert.assertEquals(2, root.getMinus().getPlus().depth());
    855         Assert.assertEquals(2, root.getMinus().getMinus().depth());
    856     }
    857
    858     @Test
    859     public void testVisit_defaultOrder() {
    860         // arrange
    861         final TestBSPTree tree = new TestBSPTree();
    862         tree.getRoot().cut(TestLine.X_AXIS)
    863             .getMinus().cut(TestLine.Y_AXIS);
    864
    865         final TestNode root = tree.getRoot();
    866         final TestNode minus = root.getMinus();
    867         final TestNode plus = root.getPlus();
    868         final TestNode minusMinus = minus.getMinus();
    869         final TestNode minusPlus = minus.getPlus();
    870
    871         final List<TestNode> nodes = new ArrayList<>();
    872
    873         // act
    874         tree.accept(node -> {
    875             nodes.add(node);
    876             return BSPTreeVisitor.Result.CONTINUE;
    877         });
    878
    879         // assert
    880         Assert.assertEquals(
    881                 Arrays.asList(root, minus, minusMinus, minusPlus, plus),
    882                 nodes);
    883     }
    884
    885     @Test
    886     public void testVisit_specifiedOrder() {
    887         // arrange
    888         final TestBSPTree tree = new TestBSPTree();
    889         tree.getRoot().cut(TestLine.X_AXIS)
    890             .getMinus().cut(TestLine.Y_AXIS);
    891
    892         final TestNode root = tree.getRoot();
    893         final TestNode minus = root.getMinus();
    894         final TestNode plus = root.getPlus();
    895         final TestNode minusMinus = minus.getMinus();
    896         final TestNode minusPlus = minus.getPlus();
    897
    898         // act/assert
    899         final TestVisitor plusMinusNode = new TestVisitor(BSPTreeVisitor.Order.PLUS_MINUS_NODE);
    900         tree.accept(plusMinusNode);
    901         Assert.assertEquals(
    902                 Arrays.asList(plus, minusPlus, minusMinus, minus, root),
    903                 plusMinusNode.getVisited());
    904
    905         final TestVisitor plusNodeMinus = new TestVisitor(BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    906         tree.accept(plusNodeMinus);
    907         Assert.assertEquals(
    908                 Arrays.asList(plus, root, minusPlus, minus, minusMinus),
    909                 plusNodeMinus.getVisited());
    910
    911         final TestVisitor minusPlusNode = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE);
    912         tree.accept(minusPlusNode);
    913         Assert.assertEquals(
    914                 Arrays.asList(minusMinus, minusPlus, minus, plus, root),
    915                 minusPlusNode.getVisited());
    916
    917         final TestVisitor minusNodePlus = new TestVisitor(BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    918         tree.accept(minusNodePlus);
    919         Assert.assertEquals(
    920                 Arrays.asList(minusMinus, minus, minusPlus, root, plus),
    921                 minusNodePlus.getVisited());
    922
    923         final TestVisitor nodeMinusPlus = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS);
    924         tree.accept(nodeMinusPlus);
    925         Assert.assertEquals(
    926                 Arrays.asList(root, minus, minusMinus, minusPlus, plus),
    927                 nodeMinusPlus.getVisited());
    928
    929         final TestVisitor nodePlusMinus = new TestVisitor(BSPTreeVisitor.Order.NODE_PLUS_MINUS);
    930         tree.accept(nodePlusMinus);
    931         Assert.assertEquals(
    932                 Arrays.asList(root, plus, minus, minusPlus, minusMinus),
    933                 nodePlusMinus.getVisited());
    934     }
    935
    936     @Test
    937     public void testVisit_nullVisitOrderSkipsSubtree() {
    938         // arrange
    939         final TestBSPTree tree = new TestBSPTree();
    940         tree.getRoot().cut(TestLine.X_AXIS)
    941             .getMinus().cut(TestLine.Y_AXIS);
    942
    943         final TestNode root = tree.getRoot();
    944         final TestNode plus = root.getPlus();
    945         final TestNode minus = root.getMinus();
    946
    947         final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS) {
    948             @Override
    949             public Order visitOrder(final TestNode node) {
    950                 if (node == minus) {
    951                     return null;
    952                 }
    953                 return super.visitOrder(node);
    954             }
    955         };
    956
    957         // act
    958         tree.accept(visitor);
    959
    960         // assert
    961         Assert.assertEquals(
    962                 Arrays.asList(root, plus),
    963                 visitor.getVisited());
    964     }
    965
    966     @Test
    967     public void testVisit_noneVisitOrderSkipsSubtree() {
    968         // arrange
    969         final TestBSPTree tree = new TestBSPTree();
    970         tree.getRoot().cut(TestLine.X_AXIS)
    971             .getMinus().cut(TestLine.Y_AXIS);
    972
    973         final TestNode root = tree.getRoot();
    974         final TestNode plus = root.getPlus();
    975         final TestNode minus = root.getMinus();
    976
    977         final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS) {
    978             @Override
    979             public Order visitOrder(final TestNode node) {
    980                 if (node == minus) {
    981                     return Order.NONE;
    982                 }
    983                 return super.visitOrder(node);
    984             }
    985         };
    986
    987         // act
    988         tree.accept(visitor);
    989
    990         // assert
    991         Assert.assertEquals(
    992                 Arrays.asList(root, plus),
    993                 visitor.getVisited());
    994     }
    995
    996     @Test
    997     public void testVisit_visitorReturnsNull_terminatesEarly() {
    998         // arrange
    999         final TestBSPTree tree = new TestBSPTree();
    1000         tree.getRoot().cut(TestLine.X_AXIS)
    1001             .getMinus().cut(TestLine.Y_AXIS);
    1002
    1003         final TestNode root = tree.getRoot();
    1004         final TestNode minus = root.getMinus();
    1005         final TestNode minusMinus = minus.getMinus();
    1006         final TestNode minusPlus = minus.getPlus();
    1007
    1008         final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE) {
    1009             @Override
    1010             public Result visit(final TestNode node) {
    1011                 super.visit(node);
    1012
    1013                 if (node == minus) {
    1014                     return null;
    1015                 }
    1016                 return Result.CONTINUE;
    1017             }
    1018         };
    1019
    1020         // act
    1021         tree.accept(visitor);
    1022
    1023         // assert
    1024         Assert.assertEquals(
    1025                 Arrays.asList(minusMinus, minusPlus, minus),
    1026                 visitor.getVisited());
    1027     }
    1028
    1029     @Test
    1030     public void testVisit_visitorReturnsTerminate_terminatesEarly() {
    1031         // arrange
    1032         final TestBSPTree tree = new TestBSPTree();
    1033         tree.getRoot().cut(TestLine.X_AXIS)
    1034             .getMinus().cut(TestLine.Y_AXIS);
    1035
    1036         final TestNode root = tree.getRoot();
    1037         final TestNode minus = root.getMinus();
    1038         final TestNode minusMinus = minus.getMinus();
    1039         final TestNode minusPlus = minus.getPlus();
    1040
    1041         final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE) {
    1042             @Override
    1043             public Result visit(final TestNode node) {
    1044                 super.visit(node);
    1045
    1046                 if (node == minus) {
    1047                     return Result.TERMINATE;
    1048                 }
    1049                 return Result.CONTINUE;
    1050             }
    1051         };
    1052
    1053         // act
    1054         tree.accept(visitor);
    1055
    1056         // assert
    1057         Assert.assertEquals(
    1058                 Arrays.asList(minusMinus, minusPlus, minus),
    1059                 visitor.getVisited());
    1060     }
    1061
    1062     @Test
    1063     public void testVisit_earlyTerminationPermutations() {
    1064         // arrange
    1065         final TestBSPTree tree = new TestBSPTree();
    1066         tree.getRoot().cut(TestLine.X_AXIS)
    1067             .getMinus().cut(TestLine.Y_AXIS);
    1068
    1069         final TestNode root = tree.getRoot();
    1070         final TestNode minus = root.getMinus();
    1071         final TestNode plus = root.getPlus();
    1072         final TestNode minusMinus = minus.getMinus();
    1073         final TestNode minusPlus = minus.getPlus();
    1074
    1075         // act/assert
    1076         final TestVisitor plusMinusNode = new TestVisitor(BSPTreeVisitor.Order.PLUS_MINUS_NODE).withTerminationNode(minus);
    1077         tree.accept(plusMinusNode);
    1078         Assert.assertEquals(
    1079                 Arrays.asList(plus, minusPlus, minusMinus, minus),
    1080                 plusMinusNode.getVisited());
    1081
    1082         final TestVisitor plusNodeMinus = new TestVisitor(BSPTreeVisitor.Order.PLUS_NODE_MINUS).withTerminationNode(minus);
    1083         tree.accept(plusNodeMinus);
    1084         Assert.assertEquals(
    1085                 Arrays.asList(plus, root, minusPlus, minus),
    1086                 plusNodeMinus.getVisited());
    1087
    1088         final TestVisitor minusPlusNode = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE).withTerminationNode(minus);
    1089         tree.accept(minusPlusNode);
    1090         Assert.assertEquals(
    1091                 Arrays.asList(minusMinus, minusPlus, minus),
    1092                 minusPlusNode.getVisited());
    1093
    1094         final TestVisitor minusNodePlus = new TestVisitor(BSPTreeVisitor.Order.MINUS_NODE_PLUS).withTerminationNode(minus);
    1095         tree.accept(minusNodePlus);
    1096         Assert.assertEquals(
    1097                 Arrays.asList(minusMinus, minus),
    1098                 minusNodePlus.getVisited());
    1099
    1100         final TestVisitor nodeMinusPlus = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS).withTerminationNode(minus);
    1101         tree.accept(nodeMinusPlus);
    1102         Assert.assertEquals(
    1103                 Arrays.asList(root, minus),
    1104                 nodeMinusPlus.getVisited());
    1105
    1106         final TestVisitor nodePlusMinus = new TestVisitor(BSPTreeVisitor.Order.NODE_PLUS_MINUS).withTerminationNode(minus);
    1107         tree.accept(nodePlusMinus);
    1108         Assert.assertEquals(
    1109                 Arrays.asList(root, plus, minus),
    1110                 nodePlusMinus.getVisited());
    1111     }
    1112
    1113     @Test
    1114     public void testVisit_visitNode() {
    1115         // arrange
    1116         final TestBSPTree tree = new TestBSPTree();
    1117         tree.getRoot().cut(TestLine.X_AXIS)
    1118             .getMinus().cut(TestLine.Y_AXIS);
    1119
    1120         final TestNode root = tree.getRoot();
    1121         final TestNode minus = root.getMinus();
    1122         final TestNode minusMinus = minus.getMinus();
    1123         final TestNode minusPlus = minus.getPlus();
    1124
    1125         final List<TestNode> nodes = new ArrayList<>();
    1126
    1127         // act
    1128         minus.accept(node -> {
    1129             nodes.add(node);
    1130             return BSPTreeVisitor.Result.CONTINUE;
    1131         });
    1132
    1133         // assert
    1134         Assert.assertEquals(
    1135                 Arrays.asList(minus, minusMinus, minusPlus),
    1136                 nodes);
    1137     }
    1138
    1139     @Test
    1140     public void testNodesIterable_emptyTree() {
    1141         // arrange
    1142         final TestBSPTree tree = new TestBSPTree();
    1143         final List<TestNode> nodes = new ArrayList<>();
    1144
    1145         // act
    1146         for (final TestNode node : tree.nodes()) {
    1147             nodes.add(node);
    1148         }
    1149
    1150         // assert
    1151         Assert.assertEquals(1, nodes.size());
    1152         Assert.assertSame(tree.getRoot(), nodes.get(0));
    1153     }
    1154
    1155     @Test
    1156     public void testNodesIterable_multipleNodes() {
    1157         // arrange
    1158         final TestBSPTree tree = new TestBSPTree();
    1159
    1160         final TestNode root = tree.getRoot();
    1161         root.cut(TestLine.X_AXIS)
    1162                 .getMinus()
    1163                     .cut(TestLine.Y_AXIS)
    1164                  .getParent()
    1165                  .getPlus()
    1166                      .cut(TestLine.Y_AXIS);
    1167
    1168         final List<TestNode> nodes = new ArrayList<>();
    1169
    1170         // act
    1171         for (final TestNode node : tree.nodes()) {
    1172             nodes.add(node);
    1173         }
    1174
    1175         // assert
    1176         Assert.assertEquals(7, nodes.size());
    1177         Assert.assertSame(root, nodes.get(0));
    1178
    1179         Assert.assertSame(root.getMinus(), nodes.get(1));
    1180         Assert.assertSame(root.getMinus().getMinus(), nodes.get(2));
    1181         Assert.assertSame(root.getMinus().getPlus(), nodes.get(3));
    1182
    1183         Assert.assertSame(root.getPlus(), nodes.get(4));
    1184         Assert.assertSame(root.getPlus().getMinus(), nodes.get(5));
    1185         Assert.assertSame(root.getPlus().getPlus(), nodes.get(6));
    1186     }
    1187
    1188
    1189     @Test
    1190     public void testNodesIterable_iteratorThrowsNoSuchElementExceptionAtEnd() {
    1191         // arrange
    1192         final TestBSPTree tree = new TestBSPTree();
    1193
    1194         final Iterator<TestNode> it = tree.nodes().iterator();
    1195         it.next();
    1196
    1197         // act
    1198         try {
    1199             it.next();
    1200             Assert.fail("Operation should have thrown an exception");
    1201         } catch (final NoSuchElementException exc) {
    1202             // expected
    1203         }
    1204     }
    1205
    1206     @Test
    1207     public void testSubtreeNodesIterable_singleNodeSubtree() {
    1208         // arrange
    1209         final TestBSPTree tree = new TestBSPTree();
    1210         final TestNode node = tree.getRoot().cut(TestLine.X_AXIS)
    1211             .getMinus()
    1212                 .cut(TestLine.Y_AXIS)
    1213                 .getMinus();
    1214
    1215         final List<TestNode> nodes = new ArrayList<>();
    1216         // act
    1217         for (final TestNode n : node.nodes()) {
    1218             nodes.add(n);
    1219         }
    1220
    1221         // assert
    1222         Assert.assertEquals(1, nodes.size());
    1223         Assert.assertSame(node, nodes.get(0));
    1224     }
    1225
    1226     @Test
    1227     public void testSubtreeNodesIterable_multipleNodeSubtree() {
    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
    1234         final List<TestNode> nodes = new ArrayList<>();
    1235         // act
    1236         for (final TestNode n : node.nodes()) {
    1237             nodes.add(n);
    1238         }
    1239
    1240         // assert
    1241         Assert.assertEquals(3, nodes.size());
    1242         Assert.assertSame(node, nodes.get(0));
    1243         Assert.assertSame(node.getMinus(), nodes.get(1));
    1244         Assert.assertSame(node.getPlus(), nodes.get(2));
    1245     }
    1246
    1247     @Test
    1248     public void testNodeTrim() {
    1249         // arrange
    1250         final TestBSPTree tree = new TestBSPTree();
    1251         tree.getRoot().cut(TestLine.Y_AXIS)
    1252             .getPlus()
    1253                 .cut(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 1)))
    1254                 .getPlus()
    1255                     .cut(new TestLine(new TestPoint2D(1.5, 1.5), new TestPoint2D(2, 1)));
    1256
    1257         final TestNode root = tree.getRoot();
    1258         final TestNode plus = root.getPlus();
    1259         final TestNode plusMinus = plus.getMinus();
    1260         final TestNode plusPlusPlus = plus.getPlus().getPlus();
    1261
    1262         final TestLineSegment xAxisSeg = TestLine.X_AXIS.span();
    1263         final TestLineSegment shortSeg = new TestLineSegment(new TestPoint2D(2, 0), new TestPoint2D(2, 2));
    1264
    1265         // act/assert
    1266         Assert.assertSame(xAxisSeg, root.trim(xAxisSeg));
    1267         Assert.assertSame(shortSeg, root.trim(shortSeg));
    1268
    1269         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1270                 (TestLineSegment) plus.trim(xAxisSeg));
    1271         Assert.assertSame(shortSeg, plus.trim(shortSeg));
    1272
    1273         Assert.assertNull(plusMinus.trim(xAxisSeg));
    1274         Assert.assertNull(plusMinus.trim(shortSeg));
    1275
    1276         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, 3, TestLine.X_AXIS),
    1277                 (TestLineSegment) plusPlusPlus.trim(xAxisSeg));
    1278         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(new TestPoint2D(2, 0), new TestPoint2D(2, 1)),
    1279                 (TestLineSegment) plusPlusPlus.trim(shortSeg));
    1280     }
    1281
    1282     @Test
    1283     public void testCopy_rootOnly() {
    1284         // arrange
    1285         final TestBSPTree tree = new TestBSPTree();
    1286
    1287         // act
    1288         final TestBSPTree copy = new TestBSPTree();
    1289         copy.copy(tree);
    1290
    1291         // assert
    1292         Assert.assertNotSame(tree, copy);
    1293         Assert.assertNotSame(tree.getRoot(), copy.getRoot());
    1294
    1295         Assert.assertEquals(tree.count(), copy.count());
    1296     }
    1297
    1298     @Test
    1299     public void testCopy_withCuts() {
    1300         // arrange
    1301         final TestBSPTree tree = new TestBSPTree();
    1302         tree.getRoot()
    1303             .cut(TestLine.X_AXIS)
    1304             .getMinus()
    1305                 .cut(TestLine.Y_AXIS);
    1306
    1307         // act
    1308         final TestBSPTree copy = new TestBSPTree();
    1309         copy.copy(tree);
    1310
    1311         // assert
    1312         Assert.assertNotSame(tree, copy);
    1313         assertNodesCopiedRecursive(tree.getRoot(), copy.getRoot());
    1314         Assert.assertEquals(tree.count(), copy.count());
    1315     }
    1316
    1317     @Test
    1318     public void testCopy_changesToOneTreeDoNotAffectCopy() {
    1319         // arrange
    1320         final TestBSPTree tree = new TestBSPTree();
    1321         tree.getRoot()
    1322             .cut(TestLine.X_AXIS)
    1323             .getMinus()
    1324                 .cut(TestLine.Y_AXIS);
    1325
    1326         // act
    1327         final TestBSPTree copy = new TestBSPTree();
    1328         copy.copy(tree);
    1329         tree.getRoot().clearCut();
    1330
    1331         // assert
    1332         Assert.assertEquals(1, tree.count());
    1333         Assert.assertEquals(5, copy.count());
    1334     }
    1335
    1336     @Test
    1337     public void testCopy_instancePassedAsArgument() {
    1338         // arrange
    1339         final TestBSPTree tree = new TestBSPTree();
    1340         tree.getRoot()
    1341             .cut(TestLine.X_AXIS)
    1342             .getMinus()
    1343                 .cut(TestLine.Y_AXIS);
    1344
    1345         // act
    1346         tree.copy(tree);
    1347
    1348         // assert
    1349         Assert.assertEquals(5, tree.count());
    1350     }
    1351
    1352     @Test
    1353     public void testExtract_singleNodeTree() {
    1354         // arrange
    1355         final TestBSPTree tree = new TestBSPTree();
    1356
    1357         final TestBSPTree result = new TestBSPTree();
    1358         result.getRoot().insertCut(TestLine.X_AXIS);
    1359
    1360         // act
    1361         result.extract(tree.getRoot());
    1362
    1363         // assert
    1364         Assert.assertNotSame(tree.getRoot(), result.getRoot());
    1365         Assert.assertEquals(1, tree.count());
    1366         Assert.assertEquals(1, result.count());
    1367
    1368         PartitionTestUtils.assertTreeStructure(tree);
    1369         PartitionTestUtils.assertTreeStructure(result);
    1370     }
    1371
    1372     @Test
    1373     public void testExtract_clearsExistingNodesInCallingTree() {
    1374         // arrange
    1375         final TestBSPTree tree = new TestBSPTree();
    1376
    1377         final TestBSPTree result = new TestBSPTree();
    1378         result.getRoot().cut(TestLine.X_AXIS)
    1379             .getMinus().cut(TestLine.Y_AXIS);
    1380
    1381         // act
    1382         result.extract(tree.getRoot());
    1383
    1384         // assert
    1385         Assert.assertNotSame(tree.getRoot(), result.getRoot());
    1386         Assert.assertEquals(1, tree.count());
    1387         Assert.assertEquals(1, result.count());
    1388
    1389         PartitionTestUtils.assertTreeStructure(tree);
    1390         PartitionTestUtils.assertTreeStructure(result);
    1391     }
    1392
    1393     @Test
    1394     public void testExtract_internalNode() {
    1395         // arrange
    1396         final TestBSPTree tree = new TestBSPTree();
    1397         tree.insert(Arrays.asList(
    1398                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1399                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1400                     new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
    1401                     new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
    1402                     new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
    1403                 ));
    1404
    1405         final TestBSPTree result = new TestBSPTree();
    1406
    1407         // act
    1408         result.extract(tree.getRoot().getPlus());
    1409
    1410         // assert
    1411         Assert.assertEquals(7, result.count());
    1412
    1413         final List<TestLineSegment> resultSegments = getLineSegments(result);
    1414         Assert.assertEquals(3, resultSegments.size());
    1415
    1416         PartitionTestUtils.assertSegmentsEqual(
    1417                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1418                 resultSegments.get(0));
    1419         PartitionTestUtils.assertSegmentsEqual(
    1420                 new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.Y_AXIS),
    1421                 resultSegments.get(1));
    1422         PartitionTestUtils.assertSegmentsEqual(
    1423                 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(new TestPoint2D(0, -2), new TestPoint2D(1, -2))),
    1424                 resultSegments.get(2));
    1425
    1426         Assert.assertEquals(13, tree.count());
    1427
    1428         final List<TestLineSegment> inputSegment = getLineSegments(tree);
    1429         Assert.assertEquals(6, inputSegment.size());
    1430
    1431         PartitionTestUtils.assertTreeStructure(tree);
    1432         PartitionTestUtils.assertTreeStructure(result);
    1433     }
    1434
    1435     @Test
    1436     public void testExtract_leafNode() {
    1437         // arrange
    1438         final TestBSPTree tree = new TestBSPTree();
    1439         tree.insert(Arrays.asList(
    1440                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1441                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1442                     new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
    1443                     new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
    1444                     new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
    1445                 ));
    1446
    1447         final TestPoint2D pt = new TestPoint2D(1, 1);
    1448
    1449         final TestNode node = tree.findNode(pt);
    1450         final TestBSPTree result = new TestBSPTree();
    1451
    1452         // act
    1453         result.extract(node);
    1454
    1455         // assert
    1456         final TestNode resultNode = result.findNode(pt);
    1457         Assert.assertNotNull(resultNode);
    1458         Assert.assertNotSame(node, resultNode);
    1459
    1460         Assert.assertEquals(7, result.count());
    1461
    1462         final List<TestLineSegment> resultSegments = getLineSegments(result);
    1463         Assert.assertEquals(3, resultSegments.size());
    1464
    1465         PartitionTestUtils.assertSegmentsEqual(
    1466                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1467                 resultSegments.get(0));
    1468         PartitionTestUtils.assertSegmentsEqual(
    1469                 new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
    1470                 resultSegments.get(1));
    1471         PartitionTestUtils.assertSegmentsEqual(
    1472                 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0)),
    1473                 resultSegments.get(2));
    1474
    1475         Assert.assertEquals(13, tree.count());
    1476
    1477         final List<TestLineSegment> inputSegment = getLineSegments(tree);
    1478         Assert.assertEquals(6, inputSegment.size());
    1479
    1480         PartitionTestUtils.assertTreeStructure(tree);
    1481         PartitionTestUtils.assertTreeStructure(result);
    1482     }
    1483
    1484     @Test
    1485     public void testExtract_extractFromSameTree() {
    1486         // arrange
    1487         final TestBSPTree tree = new TestBSPTree();
    1488         tree.insert(Arrays.asList(
    1489                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1490                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1491                     new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
    1492                     new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
    1493                     new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
    1494                 ));
    1495
    1496         final TestPoint2D pt = new TestPoint2D(1, 1);
    1497
    1498         final TestNode node = tree.findNode(pt);
    1499
    1500         // act
    1501         tree.extract(node);
    1502
    1503         // assert
    1504         final TestNode resultNode = tree.findNode(pt);
    1505         Assert.assertNotNull(resultNode);
    1506         Assert.assertSame(node, resultNode);
    1507
    1508         Assert.assertEquals(7, tree.count());
    1509
    1510         final List<TestLineSegment> resultSegments = getLineSegments(tree);
    1511         Assert.assertEquals(3, resultSegments.size());
    1512
    1513         PartitionTestUtils.assertSegmentsEqual(
    1514                 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1515                 resultSegments.get(0));
    1516         PartitionTestUtils.assertSegmentsEqual(
    1517                 new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
    1518                 resultSegments.get(1));
    1519         PartitionTestUtils.assertSegmentsEqual(
    1520                 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0)),
    1521                 resultSegments.get(2));
    1522
    1523         PartitionTestUtils.assertTreeStructure(tree);
    1524     }
    1525
    1526     @Test
    1527     public void testTransform_singleNodeTree() {
    1528         // arrange
    1529         final TestBSPTree tree = new TestBSPTree();
    1530
    1531         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
    1532
    1533         // act
    1534         tree.transform(t);
    1535
    1536         // assert
    1537         Assert.assertEquals(1, tree.count());
    1538         Assert.assertTrue(tree.getRoot().isLeaf());
    1539     }
    1540
    1541     @Test
    1542     public void testTransform_singleCut() {
    1543         // arrange
    1544         final TestBSPTree tree = new TestBSPTree();
    1545         tree.getRoot().insertCut(TestLine.X_AXIS);
    1546
    1547         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
    1548
    1549         // act
    1550         tree.transform(t);
    1551
    1552         // assert
    1553         Assert.assertEquals(3, tree.count());
    1554
    1555         final List<TestLineSegment> segments = getLineSegments(tree);
    1556         Assert.assertEquals(1, segments.size());
    1557
    1558         final TestLineSegment seg = segments.get(0);
    1559         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 2), seg.getStartPoint());
    1560         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, 2), seg.getEndPoint());
    1561     }
    1562
    1563     @Test
    1564     public void testTransform_multipleCuts() {
    1565         // arrange
    1566         final TestBSPTree tree = new TestBSPTree();
    1567         tree.insert(Arrays.asList(
    1568                     new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
    1569                     new TestLineSegment(new TestPoint2D(-1, -1), new TestPoint2D(1, 1)),
    1570                     new TestLineSegment(new TestPoint2D(3, 1), new TestPoint2D(3, 2))
    1571                 ));
    1572
    1573         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 2));
    1574
    1575         // act
    1576         tree.transform(t);
    1577
    1578         // assert
    1579         Assert.assertEquals(9, tree.count());
    1580
    1581         final List<TestLineSegment> segments = getLineSegments(tree);
    1582         Assert.assertEquals(4, segments.size());
    1583
    1584         final TestLineSegment segment1 = segments.get(0);
    1585         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 2), segment1.getStartPoint());
    1586         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, 2), segment1.getEndPoint());
    1587
    1588         final TestLineSegment segment2 = segments.get(1);
    1589         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), segment2.getStartPoint());
    1590         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY), segment2.getEndPoint());
    1591
    1592         final TestLineSegment segment3 = segments.get(2);
    1593         PartitionTestUtils.assertPointsEqual(new TestPoint2D(1.5, 2), segment3.getStartPoint());
    1594         PartitionTestUtils.assertPointsEqual(new TestPoint2D(1.5, 5), segment3.getEndPoint());
    1595
    1596         final TestLineSegment segment4 = segments.get(3);
    1597         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY), segment4.getStartPoint());
    1598         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), segment4.getEndPoint());
    1599     }
    1600
    1601     @Test
    1602     public void testTransform_xAxisReflection() {
    1603         // arrange
    1604         final TestBSPTree tree = new TestBSPTree();
    1605         tree.insert(Arrays.asList(
    1606                     new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
    1607                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1608                     new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
    1609                 ));
    1610
    1611         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), p.getY()));
    1612
    1613         final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
    1614
    1615         // act
    1616         tree.transform(t);
    1617
    1618         // assert
    1619         checkTransformedPointNodeMap(tree, t, pointNodeMap);
    1620
    1621         final List<TestLineSegment> segments = getLineSegments(tree);
    1622         Assert.assertEquals(4, segments.size());
    1623     }
    1624
    1625     @Test
    1626     public void testTransform_yAxisReflection() {
    1627         // arrange
    1628         final TestBSPTree tree = new TestBSPTree();
    1629         tree.insert(Arrays.asList(
    1630                     new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
    1631                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1632                     new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
    1633                 ));
    1634
    1635         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), -p.getY()));
    1636
    1637         final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
    1638
    1639         // act
    1640         tree.transform(t);
    1641
    1642         // assert
    1643         checkTransformedPointNodeMap(tree, t, pointNodeMap);
    1644
    1645         final List<TestLineSegment> segments = getLineSegments(tree);
    1646         Assert.assertEquals(4, segments.size());
    1647     }
    1648
    1649     @Test
    1650     public void testTransform_xAndYAxisReflection() {
    1651         // arrange
    1652         final TestBSPTree tree = new TestBSPTree();
    1653         tree.insert(Arrays.asList(
    1654                     new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
    1655                     new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
    1656                     new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
    1657                 ));
    1658
    1659         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), -p.getY()));
    1660
    1661         final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
    1662
    1663         // act
    1664         tree.transform(t);
    1665
    1666         // assert
    1667         checkTransformedPointNodeMap(tree, t, pointNodeMap);
    1668
    1669         final List<TestLineSegment> segments = getLineSegments(tree);
    1670         Assert.assertEquals(4, segments.size());
    1671     }
    1672
    1673     @Test
    1674     public void testTreeString() {
    1675         // arrange
    1676         final TestBSPTree tree = new TestBSPTree();
    1677         tree.getRoot().cut(TestLine.X_AXIS)
    1678             .getMinus().cut(TestLine.Y_AXIS);
    1679
    1680         // act
    1681         final String str = tree.treeString();
    1682
    1683         // assert
    1684         final String[] lines = str.split("\n");
    1685         Assert.assertEquals(5, lines.length);
    1686         Assert.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
    1687         Assert.assertTrue(lines[1].startsWith("    [-] TestNode[cut= TestLineSegment"));
    1688         Assert.assertEquals("        [-] TestNode[cut= null]", lines[2]);
    1689         Assert.assertEquals("        [+] TestNode[cut= null]", lines[3]);
    1690         Assert.assertEquals("    [+] TestNode[cut= null]", lines[4]);
    1691     }
    1692
    1693     @Test
    1694     public void testTreeString_emptyTree() {
    1695         // arrange
    1696         final TestBSPTree tree = new TestBSPTree();
    1697
    1698         // act
    1699         final String str = tree.treeString();
    1700
    1701         // assert
    1702         Assert.assertEquals("TestNode[cut= null]", str);
    1703     }
    1704
    1705     @Test
    1706     public void testTreeString_reachesMaxDepth() {
    1707         // arrange
    1708         final TestBSPTree tree = new TestBSPTree();
    1709         tree.getRoot().cut(TestLine.X_AXIS)
    1710             .getMinus().cut(TestLine.Y_AXIS)
    1711             .getMinus().cut(new TestLine(new TestPoint2D(-2, 1), new TestPoint2D(0, 1)));
    1712
    1713         // act
    1714         final String str = tree.treeString(1);
    1715
    1716         // assert
    1717         final String[] lines = str.split("\n");
    1718         Assert.assertEquals(4, lines.length);
    1719         Assert.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
    1720         Assert.assertTrue(lines[1].startsWith("    [-] TestNode[cut= TestLineSegment"));
    1721         Assert.assertEquals("        ...", lines[2]);
    1722         Assert.assertEquals("    [+] TestNode[cut= null]", lines[3]);
    1723     }
    1724
    1725     @Test
    1726     public void testTreeString_zeroMaxDepth() {
    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(0);
    1735
    1736         // assert
    1737         final String[] lines = str.split("\n");
    1738         Assert.assertEquals(2, lines.length);
    1739         Assert.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
    1740         Assert.assertTrue(lines[1].startsWith("    ..."));
    1741     }
    1742
    1743     @Test
    1744     public void testTreeString_negativeMaxDepth() {
    1745         // arrange
    1746         final TestBSPTree tree = new TestBSPTree();
    1747         tree.getRoot().cut(TestLine.X_AXIS)
    1748             .getMinus().cut(TestLine.Y_AXIS)
    1749             .getMinus().cut(new TestLine(new TestPoint2D(-2, 1), new TestPoint2D(0, 1)));
    1750
    1751         // act
    1752         final String str = tree.treeString(-1);
    1753
    1754         // assert
    1755         Assert.assertEquals("", str);
    1756     }
    1757
    1758     @Test
    1759     public void testToString() {
    1760         // arrange
    1761         final TestBSPTree tree = new TestBSPTree();
    1762         tree.getRoot().insertCut(TestLine.Y_AXIS);
    1763
    1764         // act
    1765         final String str = tree.toString();
    1766
    1767         // assert
    1768         final String msg = "Unexpected toString() representation: " + str;
    1769
    1770         Assert.assertTrue(msg, str.contains("TestBSPTree"));
    1771         Assert.assertTrue(msg, str.contains("count= 3"));
    1772         Assert.assertTrue(msg, str.contains("height= 1"));
    1773     }
    1774
    1775     @Test
    1776     public void testNodeToString() {
    1777         // arrange
    1778         final TestBSPTree tree = new TestBSPTree();
    1779         tree.getRoot().cut(TestLine.X_AXIS);
    1780
    1781         // act
    1782         final String str = tree.getRoot().toString();
    1783
    1784         // assert
    1785         Assert.assertTrue(str.contains("TestNode"));
    1786         Assert.assertTrue(str.contains("cut= TestLineSegment"));
    1787     }
    1788
    1789     @Test
    1790     public void testSplitIntoTree() {
    1791         // arrange
    1792         final TestBSPTree tree = new TestBSPTree();
    1793         tree.getRoot()
    1794             .cut(TestLine.X_AXIS)
    1795             .getMinus()
    1796                 .cut(TestLine.Y_AXIS);
    1797
    1798         final TestBSPTree minus = new TestBSPTree();
    1799         final TestBSPTree plus = new TestBSPTree();
    1800
    1801         final TestLine splitter = new TestLine(new TestPoint2D(0,  0), new TestPoint2D(-1, 1));
    1802
    1803         // act
    1804         tree.splitIntoTrees(splitter, minus, plus);
    1805
    1806         // assert
    1807         final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
    1808                 Double.POSITIVE_INFINITY, splitter);
    1809
    1810         Assert.assertEquals(5, tree.count());
    1811         Assert.assertEquals(2, tree.height());
    1812
    1813         Assert.assertEquals(5, minus.count());
    1814         Assert.assertEquals(2, minus.height());
    1815
    1816         final List<TestLineSegment> minusSegments = getLineSegments(minus);
    1817         Assert.assertEquals(2, minusSegments.size());
    1818         PartitionTestUtils.assertSegmentsEqual(splitSegment, minusSegments.get(0));
    1819         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.X_AXIS),
    1820                 minusSegments.get(1));
    1821
    1822         Assert.assertEquals(7, plus.count());
    1823         Assert.assertEquals(3, plus.height());
    1824
    1825         final List<TestLineSegment> plusSegments = getLineSegments(plus);
    1826         Assert.assertEquals(3, plusSegments.size());
    1827         PartitionTestUtils.assertSegmentsEqual(splitSegment, plusSegments.get(0));
    1828         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1829                 plusSegments.get(1));
    1830         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
    1831                 plusSegments.get(2));
    1832     }
    1833
    1834     @Test
    1835     public void testSplitIntoTree_minusOnly() {
    1836         // arrange
    1837         final TestBSPTree tree = new TestBSPTree();
    1838         tree.getRoot()
    1839             .cut(TestLine.X_AXIS)
    1840             .getMinus()
    1841                 .cut(TestLine.Y_AXIS);
    1842
    1843         final TestBSPTree minus = new TestBSPTree();
    1844
    1845         final TestLine splitter = new TestLine(new TestPoint2D(0,  0), new TestPoint2D(-1, 1));
    1846
    1847         // act
    1848         tree.splitIntoTrees(splitter, minus, null);
    1849
    1850         // assert
    1851         final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
    1852                 Double.POSITIVE_INFINITY, splitter);
    1853
    1854         Assert.assertEquals(5, tree.count());
    1855         Assert.assertEquals(2, tree.height());
    1856
    1857         Assert.assertEquals(5, minus.count());
    1858         Assert.assertEquals(2, minus.height());
    1859
    1860         final List<TestLineSegment> minusSegments = getLineSegments(minus);
    1861         Assert.assertEquals(2, minusSegments.size());
    1862         PartitionTestUtils.assertSegmentsEqual(splitSegment, minusSegments.get(0));
    1863         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.X_AXIS),
    1864                 minusSegments.get(1));
    1865     }
    1866
    1867     @Test
    1868     public void testSplitIntoTree_plusOnly() {
    1869         // arrange
    1870         final TestBSPTree tree = new TestBSPTree();
    1871         tree.getRoot()
    1872             .cut(TestLine.X_AXIS)
    1873             .getMinus()
    1874                 .cut(TestLine.Y_AXIS);
    1875
    1876         final TestBSPTree plus = new TestBSPTree();
    1877
    1878         final TestLine splitter = new TestLine(new TestPoint2D(0,  0), new TestPoint2D(-1, 1));
    1879
    1880         // act
    1881         tree.splitIntoTrees(splitter, null, plus);
    1882
    1883         // assert
    1884         final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
    1885                 Double.POSITIVE_INFINITY, splitter);
    1886
    1887         Assert.assertEquals(5, tree.count());
    1888         Assert.assertEquals(2, tree.height());
    1889
    1890         Assert.assertEquals(7, plus.count());
    1891         Assert.assertEquals(3, plus.height());
    1892
    1893         final List<TestLineSegment> plusSegments = getLineSegments(plus);
    1894         Assert.assertEquals(3, plusSegments.size());
    1895         PartitionTestUtils.assertSegmentsEqual(splitSegment, plusSegments.get(0));
    1896         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
    1897                 plusSegments.get(1));
    1898         PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
    1899                 plusSegments.get(2));
    1900     }
    1901
    1902     private void assertNodesCopiedRecursive(final TestNode orig, final TestNode copy) {
    1903         Assert.assertNotSame(orig, copy);
    1904
    1905         Assert.assertEquals(orig.getCut(), copy.getCut());
    1906
    1907         if (orig.isLeaf()) {
    1908             Assert.assertNull(copy.getMinus());
    1909             Assert.assertNull(copy.getPlus());
    1910         } else {
    1911             Assert.assertNotSame(orig.getMinus(), copy.getMinus());
    1912             Assert.assertNotSame(orig.getPlus(), copy.getPlus());
    1913
    1914             assertNodesCopiedRecursive(orig.getMinus(), copy.getMinus());
    1915             assertNodesCopiedRecursive(orig.getPlus(), copy.getPlus());
    1916         }
    1917
    1918         Assert.assertEquals(orig.depth(), copy.depth());
    1919         Assert.assertEquals(orig.count(), copy.count());
    1920     }
    1921
    1922     private static List<TestLineSegment> getLineSegments(final TestBSPTree tree) {
    1923         return StreamSupport.stream(tree.nodes().spliterator(), false)
    1924             .filter(BSPTree.Node::isInternal)
    1925             .map(n -> (TestLineSegment) n.getCut())
    1926             .collect(Collectors.toList());
    1927     }
    1928
    1929     /** Create a map of points to the nodes that they resolve to in the
    1930      * given tree.
    1931      */
    1932     private static Map<TestPoint2D, TestNode> createPointNodeMap(final TestBSPTree tree, final int min, final int max) {
    1933         final Map<TestPoint2D, TestNode> map = new HashMap<>();
    1934
    1935         for (int x = min; x <= max; ++x) {
    1936             for (int y = min; y <= max; ++y) {
    1937                 final TestPoint2D pt = new TestPoint2D(x, y);
    1938                 final TestNode node = tree.findNode(pt, FindNodeCutRule.NODE);
    1939
    1940                 map.put(pt, node);
    1941             }
    1942         }
    1943
    1944         return map;
    1945     }
    1946
    1947     /** Check that transformed points resolve to the same tree nodes that were found when the original
    1948      * points were resolved in the untransformed tree.
    1949      * @param transformedTree
    1950      * @param transform
    1951      * @param pointNodeMap
    1952      */
    1953     private static void checkTransformedPointNodeMap(final TestBSPTree transformedTree, final Transform<TestPoint2D> transform,
    1954                                                      final Map<TestPoint2D, TestNode> pointNodeMap) {
    1955
    1956         for (final Map.Entry<TestPoint2D, TestNode> entry : pointNodeMap.entrySet()) {
    1957             final TestNode expectedNode = entry.getValue();
    1958             final TestPoint2D transformedPt = transform.apply(entry.getKey());
    1959
    1960             final String msg = "Expected transformed point " + transformedPt + " to resolve to node " + expectedNode;
    1961             Assert.assertSame(msg, expectedNode, transformedTree.findNode(transformedPt, FindNodeCutRule.NODE));
    1962         }
    1963     }
    1964
    1965     private static class TestVisitor implements BSPTreeVisitor<TestPoint2D, TestNode> {
    1966
    1967         private final Order order;
    1968
    1969         private TestNode terminationNode;
    1970
    1971         private final List<TestNode> visited = new ArrayList<>();
    1972
    1973         TestVisitor(final Order order) {
    1974             this.order = order;
    1975         }
    1976
    1977         public TestVisitor withTerminationNode(final TestNode newTerminationNode) {
    1978             this.terminationNode = newTerminationNode;
    1979             return this;
    1980         }
    1981
    1982         @Override
    1983         public Result visit(final TestNode node) {
    1984             visited.add(node);
    1985             return (terminationNode == node) ?
    1986                     Result.TERMINATE :
    1987                     Result.CONTINUE;
    1988         }
    1989
    1990         @Override
    1991         public Order visitOrder(final TestNode node) {
    1992             return order;
    1993         }
    1994
    1995         public List<TestNode> getVisited() {
    1996             return visited;
    1997         }
    1998     }
    1999 }