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.Collections;
    22  import java.util.List;
    23  import java.util.function.Consumer;
    24  import java.util.function.Function;
    25  import java.util.stream.Stream;
    26
    27  import org.apache.commons.geometry.core.GeometryTestUtils;
    28  import org.apache.commons.geometry.core.RegionLocation;
    29  import org.apache.commons.geometry.core.Transform;
    30  import org.apache.commons.geometry.core.partitioning.BoundarySource;
    31  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    32  import org.apache.commons.geometry.core.partitioning.Split;
    33  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    34  import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree.RegionSizeProperties;
    35  import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
    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.TestRegionBSPTree;
    41  import org.apache.commons.geometry.core.partitioning.test.TestRegionBSPTree.TestRegionNode;
    42  import org.apache.commons.geometry.core.partitioning.test.TestTransform2D;
    43  import org.junit.Assert;
    44  import org.junit.Before;
    45  import org.junit.Test;
    46
    47  public class AbstractRegionBSPTreeTest {
    48
    49      private TestRegionBSPTree tree;
    50
    51      private TestRegionNode root;
    52
    53      @Before
    54      public void setup() {
    55          tree = new TestRegionBSPTree();
    56          root = tree.getRoot();
    57      }
    58
    59      @Test
    60      public void testDefaultConstructor() {
    61          // assert
    62          Assert.assertNotNull(root);
    63          Assert.assertNull(root.getParent());
    64
    65          PartitionTestUtils.assertIsLeafNode(root);
    66          Assert.assertFalse(root.isPlus());
    67          Assert.assertFalse(root.isMinus());
    68
    69          Assert.assertSame(tree, root.getTree());
    70
    71          Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
    72      }
    73
    74      @Test
    75      public void testParameterizedConstructor_true() {
    76          // act
    77          tree = new TestRegionBSPTree(true);
    78          root = tree.getRoot();
    79
    80          // assert
    81          Assert.assertNotNull(root);
    82          Assert.assertNull(root.getParent());
    83
    84          PartitionTestUtils.assertIsLeafNode(root);
    85          Assert.assertFalse(root.isPlus());
    86          Assert.assertFalse(root.isMinus());
    87
    88          Assert.assertSame(tree, root.getTree());
    89
    90          Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
    91      }
    92
    93      @Test
    94      public void testParameterizedConstructor_false() {
    95          // act
    96          tree = new TestRegionBSPTree(false);
    97          root = tree.getRoot();
    98
    99          // assert
    100         Assert.assertNotNull(root);
    101         Assert.assertNull(root.getParent());
    102
    103         PartitionTestUtils.assertIsLeafNode(root);
    104         Assert.assertFalse(root.isPlus());
    105         Assert.assertFalse(root.isMinus());
    106
    107         Assert.assertSame(tree, root.getTree());
    108
    109         Assert.assertEquals(RegionLocation.OUTSIDE, root.getLocation());
    110     }
    111
    112     @Test
    113     public void testInsert_hyperplaneSubsets_mixedCutRules() {
    114         // act/assert
    115         checkMixedCutRuleInsertion(segs -> {
    116             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[0])), RegionCutRule.PLUS_INSIDE);
    117             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[1]))); // default rule
    118             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[2])), RegionCutRule.PLUS_INSIDE);
    119             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[3])), RegionCutRule.MINUS_INSIDE);
    120             tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[4])), RegionCutRule.INHERIT);
    121         });
    122
    123     }
    124
    125     @Test
    126     public void testInsert_hyperplaneConvexSubsets_mixedCutRules() {
    127         // act/assert
    128         checkMixedCutRuleInsertion(segs -> {
    129             tree.insert(segs[0], RegionCutRule.PLUS_INSIDE);
    130             tree.insert(segs[1]); // default rule
    131             tree.insert(segs[2], RegionCutRule.PLUS_INSIDE);
    132             tree.insert(segs[3], RegionCutRule.MINUS_INSIDE);
    133             tree.insert(segs[4], RegionCutRule.INHERIT);
    134         });
    135     }
    136
    137     @Test
    138     public void testInsert_hyperplaneConvexSubsetList_mixedCutRules() {
    139         // act/assert
    140         checkMixedCutRuleInsertion(segs -> {
    141             tree.insert(Collections.singletonList(segs[0]), RegionCutRule.PLUS_INSIDE);
    142             tree.insert(Collections.singletonList(segs[1])); // default rule
    143             tree.insert(Collections.singletonList(segs[2]), RegionCutRule.PLUS_INSIDE);
    144             tree.insert(Collections.singletonList(segs[3]), RegionCutRule.MINUS_INSIDE);
    145             tree.insert(Collections.singletonList(segs[4]), RegionCutRule.INHERIT);
    146         });
    147     }
    148
    149     @Test
    150     public void testInsert_boundarySource_mixedCutRules() {
    151         // arrange
    152         final Function<TestLineSegment, BoundarySource<TestLineSegment>> factory = seg -> () -> Stream.of(seg);
    153
    154         // act/assert
    155         checkMixedCutRuleInsertion(segs -> {
    156             tree.insert(factory.apply(segs[0]), RegionCutRule.PLUS_INSIDE);
    157             tree.insert(factory.apply(segs[1])); // default rule
    158             tree.insert(factory.apply(segs[2]), RegionCutRule.PLUS_INSIDE);
    159             tree.insert(factory.apply(segs[3]), RegionCutRule.MINUS_INSIDE);
    160             tree.insert(factory.apply(segs[4]), RegionCutRule.INHERIT);
    161         });
    162     }
    163
    164     /** Helper function to check the insertion of hyperplane subsets using different region cut rules.
    165      * @param fn
    166      */
    167     private void checkMixedCutRuleInsertion(final Consumer<TestLineSegment[]> fn) {
    168         // arrange
    169         final TestLineSegment bottom = new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(0, 0));
    170         final TestLineSegment right = new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(1, 1));
    171         final TestLineSegment top = new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(1, 1));
    172         final TestLineSegment left = new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0));
    173         final TestLineSegment diag = new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 1));
    174
    175         tree = emptyTree();
    176
    177         // act
    178         fn.accept(new TestLineSegment[] {
    179             bottom,
    180             right,
    181             top,
    182             left,
    183             diag
    184         });
    185
    186         // assert
    187         TestRegionNode node = tree.getRoot();
    188         Assert.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
    189
    190         Assert.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
    191         Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
    192
    193         node = node.getPlus();
    194         Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
    195         Assert.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
    196
    197         node = node.getMinus();
    198         Assert.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
    199         Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
    200
    201         node = node.getPlus();
    202         Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
    203         Assert.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
    204
    205         node = node.getMinus();
    206         Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
    207         Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
    208     }
    209
    210     @Test
    211     public void testGetLocation_emptyRoot() {
    212         // act/assert
    213         Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
    214     }
    215
    216     @Test
    217     public void testGetLocation_singleCut() {
    218         // arrange
    219         root.insertCut(TestLine.X_AXIS);
    220
    221         // act/assert
    222         Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
    223         Assert.assertFalse(root.isInside());
    224         Assert.assertFalse(root.isOutside());
    225
    226         final TestRegionNode minus = root.getMinus();
    227         Assert.assertEquals(RegionLocation.INSIDE, minus.getLocation());
    228         Assert.assertTrue(minus.isInside());
    229         Assert.assertFalse(minus.isOutside());
    230
    231         final TestRegionNode plus = root.getPlus();
    232         Assert.assertEquals(RegionLocation.OUTSIDE, plus.getLocation());
    233         Assert.assertFalse(plus.isInside());
    234         Assert.assertTrue(plus.isOutside());
    235     }
    236
    237     @Test
    238     public void testGetLocation_multipleCuts() {
    239         // arrange
    240         tree.insert(Arrays.asList(
    241                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    242                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)),
    243                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, -1))));
    244
    245         // act/assert
    246         Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
    247
    248         final TestRegionNode plus = root.getPlus();
    249         Assert.assertEquals(RegionLocation.OUTSIDE, plus.getLocation());
    250
    251         final TestRegionNode plusPlus = plus.getPlus();
    252         Assert.assertEquals(RegionLocation.OUTSIDE, plusPlus.getLocation());
    253
    254         final TestRegionNode plusMinus = plus.getMinus();
    255         Assert.assertEquals(RegionLocation.INSIDE, plusMinus.getLocation());
    256
    257         final TestRegionNode minus = root.getMinus();
    258         Assert.assertEquals(RegionLocation.INSIDE, minus.getLocation());
    259
    260         final TestRegionNode minusPlus = minus.getPlus();
    261         Assert.assertEquals(RegionLocation.OUTSIDE, minusPlus.getLocation());
    262
    263         final TestRegionNode minusMinus = minus.getMinus();
    264         Assert.assertEquals(RegionLocation.INSIDE, minusMinus.getLocation());
    265     }
    266
    267     @Test
    268     public void testSetLocation() {
    269         // arrange
    270         tree = emptyTree();
    271         tree.insert(TestLine.Y_AXIS.span());
    272
    273         final TestRegionNode node = tree.getRoot().getMinus();
    274
    275         // act
    276         node.setLocation(RegionLocation.OUTSIDE);
    277
    278         // assert
    279         Assert.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
    280         Assert.assertTrue(tree.isEmpty());
    281     }
    282
    283     @Test
    284     public void testSetLocation_invalidatesRegionProperties() {
    285         // arrange
    286         tree = emptyTree();
    287         tree.insert(TestLine.Y_AXIS.span());
    288
    289         final TestRegionNode node = tree.getRoot().getMinus();
    290
    291         final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
    292
    293         // act
    294         node.setLocation(RegionLocation.OUTSIDE);
    295
    296         // assert
    297         Assert.assertNotSame(prevProps, tree.getRegionSizeProperties());
    298     }
    299
    300     @Test
    301     public void testSetLocation_noChange_doesNotInvalidateTree() {
    302         // arrange
    303         tree = emptyTree();
    304         tree.insert(TestLine.Y_AXIS.span());
    305
    306         final TestRegionNode node = tree.getRoot().getMinus();
    307
    308         final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
    309
    310         // act
    311         node.setLocation(RegionLocation.INSIDE);
    312
    313         // assert
    314         Assert.assertSame(prevProps, tree.getRegionSizeProperties());
    315     }
    316
    317     @Test
    318     public void testSetLocation_invalidArgs() {
    319         // act/assert
    320         GeometryTestUtils.assertThrows(() -> root.setLocation(null),
    321                 IllegalArgumentException.class, "Invalid node location: null");
    322         GeometryTestUtils.assertThrows(() -> root.setLocation(RegionLocation.BOUNDARY),
    323                 IllegalArgumentException.class, "Invalid node location: BOUNDARY");
    324     }
    325
    326     @Test
    327     public void testCondense() {
    328         // arrange
    329         tree = emptyTree();
    330         tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
    331         tree.insert(TestLine.X_AXIS.span(), RegionCutRule.INHERIT);
    332
    333         // act
    334         final boolean result = tree.condense();
    335
    336         // assert
    337         Assert.assertTrue(result);
    338
    339         Assert.assertEquals(3, tree.count());
    340         Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
    341         Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getMinus().getLocation());
    342         Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getPlus().getLocation());
    343     }
    344
    345     @Test
    346     public void testCondense_alreadyCondensed() {
    347         // arrange
    348         tree = emptyTree();
    349         tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
    350
    351         // act
    352         final boolean result = tree.condense();
    353
    354         // assert
    355         Assert.assertFalse(result);
    356
    357         Assert.assertEquals(3, tree.count());
    358         Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
    359         Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getMinus().getLocation());
    360         Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getPlus().getLocation());
    361     }
    362
    363     @Test
    364     public void testCondense_invalidatesTreeWhenChanged() {
    365         // arrange
    366         tree = emptyTree();
    367         tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
    368         tree.insert(TestLine.X_AXIS.span(), RegionCutRule.INHERIT);
    369
    370         final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
    371
    372         // act
    373         final boolean result = tree.condense();
    374
    375         // assert
    376         Assert.assertTrue(result);
    377
    378         Assert.assertNotSame(prevProps, tree.getRegionSizeProperties());
    379     }
    380
    381     @Test
    382     public void testCondense_doesNotInvalidateTreeWhenNotChanged() {
    383         // arrange
    384         tree = emptyTree();
    385
    386         final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
    387
    388         // act
    389         final boolean result = tree.condense();
    390
    391         // assert
    392         Assert.assertFalse(result);
    393
    394         Assert.assertSame(prevProps, tree.getRegionSizeProperties());
    395     }
    396
    397     @Test
    398     public void testCut_nodeMethod() {
    399         // arrange
    400         tree = emptyTree();
    401
    402         // act
    403         tree.getRoot().cut(TestLine.X_AXIS, RegionCutRule.PLUS_INSIDE)
    404             .getPlus()
    405                 .cut(TestLine.Y_AXIS, RegionCutRule.MINUS_INSIDE)
    406                 .getMinus()
    407                     .cut(new TestLine(TestPoint2D.ZERO, new TestPoint2D(-1, -1)), RegionCutRule.INHERIT);
    408
    409         // assert
    410         TestRegionNode node = tree.getRoot();
    411         Assert.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
    412
    413         Assert.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
    414         Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
    415
    416         node = node.getPlus();
    417         Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
    418         Assert.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
    419
    420         node = node.getMinus();
    421         Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
    422         Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
    423     }
    424
    425     @Test
    426     public void testBoundaries_fullAndEmpty() {
    427         // act/assert
    428         tree.setFull();
    429         Assert.assertFalse(tree.boundaries().iterator().hasNext());
    430
    431         tree.setEmpty();
    432         Assert.assertFalse(tree.boundaries().iterator().hasNext());
    433     }
    434
    435     @Test
    436     public void testBoundaries_finite() {
    437         // arrange
    438         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
    439
    440         // act
    441         final List<TestLineSegment> segments = new ArrayList<>();
    442         for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.boundaries()) {
    443             segments.add((TestLineSegment) sub);
    444         }
    445
    446         // assert
    447         Assert.assertEquals(4, segments.size());
    448
    449         assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(1, 0));
    450         assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(1, 1));
    451         assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(0, 1));
    452         assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(0, 0));
    453     }
    454
    455     @Test
    456     public void testBoundaries_finite_inverted() {
    457         // arrange
    458         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
    459         tree.complement();
    460
    461         // act
    462         final List<TestLineSegment> segments = new ArrayList<>();
    463         for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.boundaries()) {
    464             segments.add((TestLineSegment) sub);
    465         }
    466
    467         // assert
    468         Assert.assertEquals(4, segments.size());
    469
    470         assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(0, 1));
    471         assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(1, 1));
    472         assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(1, 0));
    473         assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(0, 0));
    474     }
    475
    476     @Test
    477     public void testGetBoundaries_fullAndEmpty() {
    478         // act/assert
    479         tree.setFull();
    480         Assert.assertEquals(0, tree.getBoundaries().size());
    481
    482         tree.setEmpty();
    483         Assert.assertEquals(0, tree.getBoundaries().size());
    484     }
    485
    486     @Test
    487     public void testGetBoundaries_finite() {
    488         // arrange
    489         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
    490
    491         // act
    492         final List<TestLineSegment> segments = new ArrayList<>();
    493         for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.getBoundaries()) {
    494             segments.add((TestLineSegment) sub);
    495         }
    496
    497         // assert
    498         Assert.assertEquals(4, segments.size());
    499
    500         assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(1, 0));
    501         assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(1, 1));
    502         assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(0, 1));
    503         assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(0, 0));
    504     }
    505
    506     @Test
    507     public void testGetBoundaries_finite_inverted() {
    508         // arrange
    509         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
    510         tree.complement();
    511
    512         // act
    513         final List<TestLineSegment> segments = new ArrayList<>();
    514         for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.getBoundaries()) {
    515             segments.add((TestLineSegment) sub);
    516         }
    517
    518         // assert
    519         Assert.assertEquals(4, segments.size());
    520
    521         assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(0, 1));
    522         assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(1, 1));
    523         assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(1, 0));
    524         assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(0, 0));
    525     }
    526
    527     @Test
    528     public void testClassify() {
    529         // arrange
    530         insertSkewedBowtie(tree);
    531
    532         // act/assert
    533         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
    534         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
    535
    536         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, 1)));
    537         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, -1)));
    538
    539         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
    540         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
    541
    542         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(5, 0)));
    543         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
    544         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
    545         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
    546         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
    547         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, 0)));
    548         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
    549         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
    550         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
    551         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
    552         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-5, 0)));
    553     }
    554
    555     @Test
    556     public void testClassify_emptyTree() {
    557         // act/assert
    558         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
    559     }
    560
    561     @Test
    562     public void testClassify_NaN() {
    563         // act/assert
    564         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, Double.NaN)));
    565     }
    566
    567     @Test
    568     public void testContains() {
    569         // arrange
    570         insertSkewedBowtie(tree);
    571
    572         // act/assert
    573         Assert.assertTrue(tree.contains(new TestPoint2D(3, 1)));
    574         Assert.assertTrue(tree.contains(new TestPoint2D(-3, -1)));
    575
    576         Assert.assertFalse(tree.contains(new TestPoint2D(-3, 1)));
    577         Assert.assertFalse(tree.contains(new TestPoint2D(3, -1)));
    578
    579         Assert.assertTrue(tree.contains(new TestPoint2D(4, 5)));
    580         Assert.assertTrue(tree.contains(new TestPoint2D(-4, -5)));
    581
    582         Assert.assertFalse(tree.contains(new TestPoint2D(5, 0)));
    583
    584         Assert.assertTrue(tree.contains(new TestPoint2D(4, 0)));
    585         Assert.assertTrue(tree.contains(new TestPoint2D(3, 0)));
    586         Assert.assertTrue(tree.contains(new TestPoint2D(2, 0)));
    587         Assert.assertTrue(tree.contains(new TestPoint2D(1, 0)));
    588         Assert.assertTrue(tree.contains(new TestPoint2D(0, 0)));
    589         Assert.assertTrue(tree.contains(new TestPoint2D(-1, 0)));
    590         Assert.assertTrue(tree.contains(new TestPoint2D(-2, 0)));
    591         Assert.assertTrue(tree.contains(new TestPoint2D(-3, 0)));
    592         Assert.assertTrue(tree.contains(new TestPoint2D(-4, 0)));
    593
    594         Assert.assertFalse(tree.contains(new TestPoint2D(-5, 0)));
    595     }
    596
    597     @Test
    598     public void testSetFull() {
    599         // arrange
    600         insertSkewedBowtie(tree);
    601
    602         // act
    603         tree.setFull();
    604
    605         // assert
    606         Assert.assertTrue(tree.isFull());
    607         Assert.assertFalse(tree.isEmpty());
    608
    609         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
    610         Assert.assertTrue(tree.contains(TestPoint2D.ZERO));
    611     }
    612
    613     @Test
    614     public void testSetEmpty() {
    615         // arrange
    616         insertSkewedBowtie(tree);
    617
    618         // act
    619         tree.setEmpty();
    620
    621         // assert
    622         Assert.assertFalse(tree.isFull());
    623         Assert.assertTrue(tree.isEmpty());
    624
    625         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
    626         Assert.assertFalse(tree.contains(TestPoint2D.ZERO));
    627     }
    628
    629     @Test
    630     public void testGetRegionSizeProperties_cachesValueBasedOnVersion() {
    631         // act
    632         final RegionSizeProperties<TestPoint2D> first = tree.getRegionSizeProperties();
    633         final RegionSizeProperties<TestPoint2D> second = tree.getRegionSizeProperties();
    634         tree.getRoot().cut(TestLine.X_AXIS);
    635         final RegionSizeProperties<TestPoint2D> third = tree.getRegionSizeProperties();
    636
    637         // assert
    638         Assert.assertSame(first, second);
    639         Assert.assertNotSame(second, third);
    640
    641         Assert.assertEquals(1234, first.getSize(), PartitionTestUtils.EPS);
    642         PartitionTestUtils.assertPointsEqual(new TestPoint2D(12, 34), first.getCentroid());
    643     }
    644
    645     @Test
    646     public void testGetSize() {
    647         // act/assert
    648         // make sure our stub value is pulled
    649         Assert.assertEquals(1234, tree.getSize(), PartitionTestUtils.EPS);
    650     }
    651
    652     @Test
    653     public void testGetCentroid() {
    654         // act/assert
    655         // make sure our stub value is pulled
    656         PartitionTestUtils.assertPointsEqual(new TestPoint2D(12, 34), tree.getCentroid());
    657     }
    658
    659     @Test
    660     public void testGetBoundarySize_fullAndEmpty() {
    661         // act/assert
    662         Assert.assertEquals(0.0, fullTree().getBoundarySize(), PartitionTestUtils.EPS);
    663         Assert.assertEquals(0.0, emptyTree().getBoundarySize(), PartitionTestUtils.EPS);
    664     }
    665
    666     @Test
    667     public void testGetBoundarySize_infinite() {
    668         // arrange
    669         final TestRegionBSPTree halfPos = new TestRegionBSPTree(true);
    670         halfPos.getRoot().cut(TestLine.X_AXIS);
    671
    672         final TestRegionBSPTree halfPosComplement = new TestRegionBSPTree(true);
    673         halfPosComplement.complement(halfPos);
    674
    675         // act/assert
    676         Assert.assertEquals(Double.POSITIVE_INFINITY, halfPos.getBoundarySize(), PartitionTestUtils.EPS);
    677         Assert.assertEquals(Double.POSITIVE_INFINITY, halfPosComplement.getBoundarySize(), PartitionTestUtils.EPS);
    678     }
    679
    680     @Test
    681     public void testGetBoundarySize_alignedCuts() {
    682         // arrange
    683         final TestPoint2D p0 = TestPoint2D.ZERO;
    684         final TestPoint2D p1 = new TestPoint2D(0, 3);
    685
    686         TestRegionNode node = tree.getRoot();
    687
    688         tree.cutNode(node, new TestLineSegment(p0, p1));
    689         node = node.getMinus();
    690
    691         tree.cutNode(node, new TestLineSegment(0, 0, new TestLine(p1, new TestPoint2D(-1, 3))));
    692         node = node.getMinus();
    693
    694         tree.cutNode(node, new TestLineSegment(p1, p0));
    695         node = node.getMinus();
    696
    697         tree.cutNode(node, new TestLineSegment(0, 0, new TestLine(p0, new TestPoint2D(1, 3))));
    698
    699         // act/assert
    700         Assert.assertEquals(6, tree.getBoundarySize(), PartitionTestUtils.EPS);
    701     }
    702
    703     @Test
    704     public void testGetBoundarySize_box() {
    705         // arrange
    706         insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
    707
    708         // act/assert
    709         Assert.assertEquals(6.0, tree.getBoundarySize(), PartitionTestUtils.EPS);
    710     }
    711
    712     @Test
    713     public void testGetBoundarySize_boxComplement() {
    714         // arrange
    715         insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
    716         tree.complement();
    717
    718         // act/assert
    719         Assert.assertEquals(6.0, tree.getBoundarySize(), PartitionTestUtils.EPS);
    720     }
    721
    722     @Test
    723     public void testGetBoundarySize_recomputesAfterChange() {
    724         // arrange
    725         insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
    726
    727         // act
    728         final double first = tree.getBoundarySize();
    729         tree.insert(new TestLineSegment(new TestPoint2D(3, 1), new TestPoint2D(3, 2)));
    730
    731         final double second = tree.getBoundarySize();
    732         final double third = tree.getBoundarySize();
    733
    734         // assert
    735         Assert.assertEquals(6.0, first, PartitionTestUtils.EPS);
    736         Assert.assertEquals(4.0, second, PartitionTestUtils.EPS);
    737         Assert.assertEquals(4.0, third, PartitionTestUtils.EPS);
    738     }
    739
    740     @Test
    741     public void testGetCutBoundary_emptyTree() {
    742         // act
    743         final RegionCutBoundary<TestPoint2D> boundary = root.getCutBoundary();
    744
    745         // assert
    746         Assert.assertNull(boundary);
    747     }
    748
    749     @Test
    750     public void testGetCutBoundary_singleCut() {
    751         // arrange
    752         tree.insert(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    753
    754         // act
    755         final RegionCutBoundary<TestPoint2D> boundary = root.getCutBoundary();
    756
    757         // assert
    758         Assert.assertTrue(boundary.getInsideFacing().isEmpty());
    759
    760         assertCutBoundarySegment(boundary.getOutsideFacing(),
    761                 new TestPoint2D(Double.NEGATIVE_INFINITY, 0.0), new TestPoint2D(Double.POSITIVE_INFINITY, 0.0));
    762     }
    763
    764     @Test
    765     public void testGetCutBoundary_singleCut_leafNode() {
    766         // arrange
    767         tree.insert(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    768
    769         // act
    770         final RegionCutBoundary<TestPoint2D> boundary = root.getMinus().getCutBoundary();
    771
    772         // assert
    773         Assert.assertNull(boundary);
    774     }
    775
    776     @Test
    777     public void testGetCutBoundary_singleCorner() {
    778         // arrange
    779         tree.insert(new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)));
    780         tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
    781
    782         // act/assert
    783         final RegionCutBoundary<TestPoint2D> rootBoundary = root.getCutBoundary();
    784
    785         Assert.assertTrue(rootBoundary.getInsideFacing().isEmpty());
    786         assertCutBoundarySegment(rootBoundary.getOutsideFacing(),
    787                 new TestPoint2D(Double.NEGATIVE_INFINITY, 0.0), TestPoint2D.ZERO);
    788
    789         final RegionCutBoundary<TestPoint2D> childBoundary = tree.getRoot().getMinus().getCutBoundary();
    790         Assert.assertTrue(childBoundary.getInsideFacing().isEmpty());
    791         assertCutBoundarySegment(childBoundary.getOutsideFacing(),
    792                 TestPoint2D.ZERO, new TestPoint2D(0.0, Double.POSITIVE_INFINITY));
    793     }
    794
    795     @Test
    796     public void testGetCutBoundary_leafNode() {
    797         // arrange
    798         tree.insert(new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)));
    799         tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
    800
    801         // act/assert
    802         Assert.assertNull(root.getPlus().getCutBoundary());
    803         Assert.assertNull(root.getMinus().getMinus().getCutHyperplane());
    804         Assert.assertNull(root.getMinus().getPlus().getCutHyperplane());
    805     }
    806
    807     @Test
    808     public void testFullEmpty_fullTree() {
    809         // act/assert
    810         Assert.assertTrue(tree.isFull());
    811         Assert.assertFalse(tree.isEmpty());
    812         Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
    813     }
    814
    815     @Test
    816     public void testFullEmpty_emptyTree() {
    817         // arrange
    818         tree.complement();
    819
    820         // act/assert
    821         Assert.assertFalse(tree.isFull());
    822         Assert.assertTrue(tree.isEmpty());
    823         Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
    824     }
    825
    826     @Test
    827     public void testTransform_noCuts() {
    828         // arrange
    829         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
    830
    831         // act
    832         tree.transform(t);
    833
    834         // assert
    835         Assert.assertTrue(tree.isFull());
    836         Assert.assertFalse(tree.isEmpty());
    837
    838         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE, TestPoint2D.ZERO);
    839     }
    840
    841     @Test
    842     public void testTransform_singleCut() {
    843         // arrange
    844         tree.getRoot().insertCut(TestLine.X_AXIS);
    845
    846         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
    847
    848         // act
    849         tree.transform(t);
    850
    851         // assert
    852         Assert.assertFalse(tree.isFull());
    853         Assert.assertFalse(tree.isEmpty());
    854
    855         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    856                 new TestPoint2D(0, -1), TestPoint2D.ZERO, new TestPoint2D(0, 1));
    857
    858         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY, new TestPoint2D(0, 2));
    859
    860         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    861                 new TestPoint2D(0, 3), new TestPoint2D(0, 4));
    862     }
    863
    864     @Test
    865     public void testTransform_multipleCuts() {
    866         // arrange
    867         insertSkewedBowtie(tree);
    868
    869         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 5));
    870
    871         // act
    872         tree.transform(t);
    873
    874         // assert
    875         Assert.assertFalse(tree.isFull());
    876         Assert.assertFalse(tree.isEmpty());
    877
    878         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    879                 new TestPoint2D(0, 5), new TestPoint2D(-1, 4), new TestPoint2D(1, 6));
    880
    881         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    882                 new TestPoint2D(-2, 4), new TestPoint2D(2, 6));
    883
    884         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    885                 new TestPoint2D(-3, 5), new TestPoint2D(3, 5));
    886     }
    887
    888     @Test
    889     public void testTransform_xAxisReflection() {
    890         // arrange
    891         insertSkewedBowtie(tree);
    892
    893         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), p.getY()));
    894
    895         // act
    896         tree.transform(t);
    897
    898         // assert
    899         Assert.assertFalse(tree.isFull());
    900         Assert.assertFalse(tree.isEmpty());
    901
    902         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    903                 TestPoint2D.ZERO, new TestPoint2D(-1, 1), new TestPoint2D(1, -1));
    904
    905         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    906                 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
    907                 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
    908
    909         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    910                 new TestPoint2D(1, 1), new TestPoint2D(-1, -1));
    911     }
    912
    913     @Test
    914     public void testTransform_yAxisReflection() {
    915         // arrange
    916         insertSkewedBowtie(tree);
    917
    918         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), -p.getY()));
    919
    920         // act
    921         tree.transform(t);
    922
    923         // assert
    924         Assert.assertFalse(tree.isFull());
    925         Assert.assertFalse(tree.isEmpty());
    926
    927         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    928                 TestPoint2D.ZERO, new TestPoint2D(1, -1), new TestPoint2D(-1, 1));
    929
    930         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    931                 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
    932                 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
    933
    934         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    935                 new TestPoint2D(-1, -1), new TestPoint2D(1, 1));
    936     }
    937
    938     @Test
    939     public void testTransform_xAndYAxisReflection() {
    940         // arrange
    941         insertSkewedBowtie(tree);
    942
    943         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), -p.getY()));
    944
    945         // act
    946         tree.transform(t);
    947
    948         // assert
    949         Assert.assertFalse(tree.isFull());
    950         Assert.assertFalse(tree.isEmpty());
    951
    952         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    953                 TestPoint2D.ZERO, new TestPoint2D(1, 1), new TestPoint2D(-1, -1));
    954
    955         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    956                 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
    957                 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
    958
    959         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    960                 new TestPoint2D(-1, 1), new TestPoint2D(1, -1));
    961     }
    962
    963     @Test
    964     public void testTransform_resetsCutBoundary() {
    965         // arrange
    966         insertSkewedBowtie(tree);
    967
    968         final TestRegionNode node = tree.findNode(new TestPoint2D(1, 1)).getParent();
    969
    970
    971         final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 5));
    972
    973         // act
    974         final RegionCutBoundary<TestPoint2D> origBoundary = node.getCutBoundary();
    975
    976         tree.transform(t);
    977
    978         final RegionCutBoundary<TestPoint2D> resultBoundary = node.getCutBoundary();
    979
    980         // assert
    981         Assert.assertNotSame(origBoundary, resultBoundary);
    982
    983         assertCutBoundarySegment(origBoundary.getOutsideFacing(), new TestPoint2D(4, 5), new TestPoint2D(-1, 0));
    984
    985         assertCutBoundarySegment(resultBoundary.getOutsideFacing(), new TestPoint2D(2, 10), new TestPoint2D(-0.5, 5));
    986     }
    987
    988     @Test
    989     public void testComplement_rootOnly() {
    990         // act
    991         tree.complement();
    992
    993         // assert
    994         Assert.assertTrue(tree.isEmpty());
    995         Assert.assertFalse(tree.isFull());
    996
    997         Assert.assertEquals(RegionLocation.OUTSIDE, root.getLocation());
    998         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
    999     }
    1000
    1001     @Test
    1002     public void testComplement_singleCut() {
    1003         // arrange
    1004         root.insertCut(TestLine.X_AXIS);
    1005
    1006         // act
    1007         tree.complement();
    1008
    1009         // assert
    1010         Assert.assertFalse(tree.isEmpty());
    1011         Assert.assertFalse(tree.isFull());
    1012
    1013         Assert.assertEquals(RegionLocation.OUTSIDE, root.getMinus().getLocation());
    1014         Assert.assertEquals(RegionLocation.INSIDE, root.getPlus().getLocation());
    1015
    1016         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, 1)));
    1017         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
    1018         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, -1)));
    1019     }
    1020
    1021     @Test
    1022     public void testComplement_skewedBowtie() {
    1023         // arrange
    1024         insertSkewedBowtie(tree);
    1025
    1026         // act
    1027         tree.complement();
    1028
    1029         // assert
    1030         Assert.assertFalse(tree.isEmpty());
    1031         Assert.assertFalse(tree.isFull());
    1032
    1033         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, 1)));
    1034         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, -1)));
    1035
    1036         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, 1)));
    1037         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, -1)));
    1038
    1039         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
    1040         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
    1041
    1042         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(5, 0)));
    1043         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
    1044         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
    1045         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
    1046         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
    1047         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, 0)));
    1048         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
    1049         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
    1050         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
    1051         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
    1052         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-5, 0)));
    1053     }
    1054
    1055     @Test
    1056     public void testComplement_addCutAfterComplement() {
    1057         // arrange
    1058         tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)));
    1059         tree.complement();
    1060
    1061         // act
    1062         tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
    1063
    1064         // assert
    1065         Assert.assertFalse(tree.isEmpty());
    1066         Assert.assertFalse(tree.isFull());
    1067
    1068         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
    1069
    1070         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(1, 1)));
    1071         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, 1)));
    1072         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(1, -1)));
    1073         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, -1)));
    1074     }
    1075
    1076     @Test
    1077     public void testComplement_clearCutAfterComplement() {
    1078         // arrange
    1079         tree.insert(Arrays.asList(
    1080                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1081                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))
    1082                 ));
    1083         tree.complement();
    1084
    1085         // act
    1086         root.getMinus().clearCut();
    1087
    1088         // assert
    1089         Assert.assertFalse(tree.isEmpty());
    1090         Assert.assertFalse(tree.isFull());
    1091
    1092         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
    1093
    1094         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(1, 1)));
    1095         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-1, 1)));
    1096         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(1, -1)));
    1097         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, -1)));
    1098     }
    1099
    1100     @Test
    1101     public void testComplement_clearRootAfterComplement() {
    1102         // arrange
    1103         tree.insert(Arrays.asList(
    1104                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1105                     new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))
    1106                 ));
    1107         tree.complement();
    1108
    1109         // act
    1110         root.clearCut();
    1111
    1112         // assert
    1113         Assert.assertTrue(tree.isEmpty());
    1114         Assert.assertFalse(tree.isFull());
    1115
    1116         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
    1117     }
    1118
    1119     @Test
    1120     public void testComplement_isReversible_root() {
    1121         // act
    1122         tree.complement();
    1123         tree.complement();
    1124
    1125         // assert
    1126         Assert.assertFalse(tree.isEmpty());
    1127         Assert.assertTrue(tree.isFull());
    1128
    1129         Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
    1130         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
    1131     }
    1132
    1133     @Test
    1134     public void testComplement_isReversible_skewedBowtie() {
    1135         // arrange
    1136         insertSkewedBowtie(tree);
    1137
    1138         // act
    1139         tree.complement();
    1140         tree.complement();
    1141
    1142         // assert
    1143         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
    1144         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
    1145
    1146         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, 1)));
    1147         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, -1)));
    1148
    1149         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
    1150         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
    1151
    1152         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(5, 0)));
    1153         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
    1154         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
    1155         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
    1156         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
    1157         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, 0)));
    1158         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
    1159         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
    1160         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
    1161         Assert.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
    1162         Assert.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-5, 0)));
    1163     }
    1164
    1165     @Test
    1166     public void testComplement_getCutBoundary() {
    1167         // arrange
    1168         tree.insert(Arrays.asList(
    1169                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1170                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))));
    1171         tree.complement();
    1172
    1173         // act
    1174         final RegionCutBoundary<TestPoint2D> xAxisBoundary = root.getCutBoundary();
    1175         final RegionCutBoundary<TestPoint2D> yAxisBoundary = root.getMinus().getCutBoundary();
    1176
    1177         // assert
    1178         Assert.assertTrue(xAxisBoundary.getOutsideFacing().isEmpty());
    1179         Assert.assertFalse(xAxisBoundary.getInsideFacing().isEmpty());
    1180
    1181         final List<HyperplaneConvexSubset<TestPoint2D>> xAxisInsideFacing = xAxisBoundary.getInsideFacing();
    1182         Assert.assertEquals(1, xAxisInsideFacing.size());
    1183
    1184         final TestLineSegment xAxisSeg = (TestLineSegment) xAxisInsideFacing.get(0);
    1185         PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 0), xAxisSeg.getStartPoint());
    1186         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, xAxisSeg.getEndPoint());
    1187
    1188         Assert.assertTrue(yAxisBoundary.getOutsideFacing().isEmpty());
    1189         Assert.assertFalse(yAxisBoundary.getInsideFacing().isEmpty());
    1190
    1191         final List<HyperplaneConvexSubset<TestPoint2D>> yAxisInsideFacing = yAxisBoundary.getInsideFacing();
    1192         Assert.assertEquals(1, yAxisInsideFacing.size());
    1193
    1194         final TestLineSegment yAxisSeg = (TestLineSegment) yAxisInsideFacing.get(0);
    1195         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, yAxisSeg.getStartPoint());
    1196         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, Double.POSITIVE_INFINITY), yAxisSeg.getEndPoint());
    1197     }
    1198
    1199     @Test
    1200     public void testComplementOf_rootOnly() {
    1201         // arrange
    1202         final TestRegionBSPTree other = fullTree();
    1203         insertSkewedBowtie(other);
    1204
    1205         // act
    1206         other.complement(tree);
    1207
    1208         // assert
    1209         Assert.assertFalse(tree.isEmpty());
    1210         Assert.assertTrue(tree.isFull());
    1211
    1212         Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
    1213         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
    1214
    1215         Assert.assertTrue(other.isEmpty());
    1216         Assert.assertFalse(other.isFull());
    1217
    1218         Assert.assertEquals(RegionLocation.OUTSIDE, other.getRoot().getLocation());
    1219         Assert.assertEquals(RegionLocation.OUTSIDE, other.classify(TestPoint2D.ZERO));
    1220     }
    1221
    1222     @Test
    1223     public void testComplementOf_skewedBowtie() {
    1224         // arrange
    1225         insertSkewedBowtie(tree);
    1226
    1227         final TestRegionBSPTree other = fullTree();
    1228
    1229         // act
    1230         other.complement(tree);
    1231
    1232         // assert
    1233         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
    1234         Assert.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
    1235
    1236         Assert.assertFalse(other.isEmpty());
    1237         Assert.assertFalse(other.isFull());
    1238
    1239         Assert.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(3, 1)));
    1240         Assert.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(-3, -1)));
    1241
    1242         Assert.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(-3, 1)));
    1243         Assert.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(3, -1)));
    1244
    1245         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(4, 5)));
    1246         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-4, -5)));
    1247
    1248         Assert.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(5, 0)));
    1249         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(4, 0)));
    1250         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(3, 0)));
    1251         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(2, 0)));
    1252         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(1, 0)));
    1253         Assert.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(0, 0)));
    1254         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-1, 0)));
    1255         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-2, 0)));
    1256         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-3, 0)));
    1257         Assert.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-4, 0)));
    1258         Assert.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(-5, 0)));
    1259     }
    1260
    1261     @Test
    1262     public void testCopy() {
    1263         // arrange
    1264         insertSkewedBowtie(tree);
    1265
    1266         // act
    1267         final TestRegionBSPTree copy = fullTree();
    1268         copy.copy(tree);
    1269
    1270         // assert
    1271         Assert.assertNotSame(tree, copy);
    1272         Assert.assertEquals(tree.count(), copy.count());
    1273
    1274         final List<RegionLocation> origLocations = new ArrayList<>();
    1275         tree.nodes().forEach(n -> origLocations.add(n.getLocation()));
    1276
    1277         final List<RegionLocation> copyLocations = new ArrayList<>();
    1278         copy.nodes().forEach(n -> copyLocations.add(n.getLocation()));
    1279
    1280         Assert.assertEquals(origLocations, copyLocations);
    1281     }
    1282
    1283     @Test
    1284     public void testExtract() {
    1285         // arrange
    1286         insertSkewedBowtie(tree);
    1287
    1288         final TestRegionBSPTree result = fullTree();
    1289
    1290         final TestPoint2D pt = new TestPoint2D(2, 2);
    1291
    1292         // act
    1293         result.extract(tree.findNode(pt));
    1294
    1295         // assert
    1296         PartitionTestUtils.assertPointLocations(result, RegionLocation.INSIDE,
    1297                 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2));
    1298         PartitionTestUtils.assertPointLocations(result, RegionLocation.OUTSIDE,
    1299                 new TestPoint2D(-2, 2),
    1300                 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5), new TestPoint2D(-2, 2));
    1301
    1302         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    1303                 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2),
    1304                 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5));
    1305         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    1306                 new TestPoint2D(2, -2), new TestPoint2D(-2, 2));
    1307     }
    1308
    1309     @Test
    1310     public void testExtract_complementedTree() {
    1311         // arrange
    1312         insertSkewedBowtie(tree);
    1313         tree.complement();
    1314
    1315         final TestRegionBSPTree result = fullTree();
    1316
    1317         final TestPoint2D pt = new TestPoint2D(2, 2);
    1318
    1319         // act
    1320         result.extract(tree.findNode(pt));
    1321
    1322         // assert
    1323         PartitionTestUtils.assertPointLocations(result, RegionLocation.OUTSIDE,
    1324                 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2));
    1325         PartitionTestUtils.assertPointLocations(result, RegionLocation.INSIDE,
    1326                 new TestPoint2D(-2, 2),
    1327                 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5), new TestPoint2D(-2, 2));
    1328
    1329         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    1330                 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2),
    1331                 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5));
    1332         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    1333                 new TestPoint2D(2, -2), new TestPoint2D(-2, 2));
    1334     }
    1335
    1336
    1337
    1338     @Test
    1339     public void testProject_emptyAndFull() {
    1340         // arrange
    1341         final TestRegionBSPTree full = fullTree();
    1342         final TestRegionBSPTree empty = emptyTree();
    1343
    1344         // act/assert
    1345         Assert.assertNull(full.project(new TestPoint2D(0, 0)));
    1346         Assert.assertNull(empty.project(new TestPoint2D(-1, 1)));
    1347     }
    1348
    1349     @Test
    1350     public void testProject_halfSpace() {
    1351         // arrange
    1352         tree.getRoot().cut(TestLine.X_AXIS);
    1353
    1354         // act/assert
    1355         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(TestPoint2D.ZERO));
    1356
    1357         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(0, 7)));
    1358         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(0, -7)));
    1359
    1360         PartitionTestUtils.assertPointsEqual(new TestPoint2D(4, 0), tree.project(new TestPoint2D(4, 10)));
    1361         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-5, 0), tree.project(new TestPoint2D(-5, -2)));
    1362     }
    1363
    1364     @Test
    1365     public void testProject_box() {
    1366         // arrange
    1367         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
    1368
    1369         // act/assert
    1370         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(TestPoint2D.ZERO));
    1371         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(-1, -4)));
    1372
    1373         PartitionTestUtils.assertPointsEqual(new TestPoint2D(1, 1), tree.project(new TestPoint2D(2, 9)));
    1374
    1375         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.5, 1), tree.project(new TestPoint2D(0.5, 3)));
    1376     }
    1377
    1378     @Test
    1379     public void testSplit_empty() {
    1380         // arrange
    1381         tree = emptyTree();
    1382
    1383         // act
    1384         final Split<TestRegionBSPTree> split = tree.split(TestLine.X_AXIS);
    1385
    1386         // assert
    1387         Assert.assertEquals(SplitLocation.NEITHER, split.getLocation());
    1388
    1389         Assert.assertNull(split.getMinus());
    1390         Assert.assertNull(split.getPlus());
    1391     }
    1392
    1393     @Test
    1394     public void testSplit_full() {
    1395         // arrange
    1396         tree = fullTree();
    1397
    1398         // act
    1399         final Split<TestRegionBSPTree> split = tree.split(TestLine.X_AXIS);
    1400
    1401         // assert
    1402         Assert.assertEquals(SplitLocation.BOTH, split.getLocation());
    1403
    1404         final TestRegionBSPTree minus = split.getMinus();
    1405         PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE,
    1406                 new TestPoint2D(-1, 1), new TestPoint2D(0, 1), new TestPoint2D(1, 1));
    1407         PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
    1408                 new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(1, 0));
    1409         PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
    1410                 new TestPoint2D(-1, -1), new TestPoint2D(0, -1), new TestPoint2D(1, -1));
    1411
    1412         final TestRegionBSPTree plus = split.getPlus();
    1413         PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
    1414                 new TestPoint2D(-1, 1), new TestPoint2D(0, 1), new TestPoint2D(1, 1));
    1415         PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
    1416                 new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(1, 0));
    1417         PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE,
    1418                 new TestPoint2D(-1, -1), new TestPoint2D(0, -1), new TestPoint2D(1, -1));
    1419     }
    1420
    1421     @Test
    1422     public void testSplit_halfSpace() {
    1423         // arrange
    1424         tree.getRoot().insertCut(TestLine.X_AXIS);
    1425
    1426         final TestLine splitter = TestLine.Y_AXIS;
    1427
    1428         // act
    1429         final Split<TestRegionBSPTree> split = tree.split(splitter);
    1430
    1431         // assert
    1432         Assert.assertEquals(SplitLocation.BOTH, split.getLocation());
    1433
    1434         final TestRegionBSPTree minus = split.getMinus();
    1435         PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(-1, 1));
    1436         PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
    1437                 new TestPoint2D(1, 1), new TestPoint2D(-1, -1), new TestPoint2D(1, -1));
    1438
    1439         final TestRegionBSPTree plus = split.getPlus();
    1440         PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(1, 1));
    1441         PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
    1442                 new TestPoint2D(-1, 1), new TestPoint2D(-1, -1), new TestPoint2D(1, -1));
    1443     }
    1444
    1445     @Test
    1446     public void testSplit_box() {
    1447         // arrange
    1448         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
    1449
    1450         final TestLine splitter = new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 1));
    1451
    1452         // act
    1453         final Split<TestRegionBSPTree> split = tree.split(splitter);
    1454
    1455         // assert
    1456         Assert.assertEquals(SplitLocation.BOTH, split.getLocation());
    1457
    1458         final TestRegionBSPTree minus = split.getMinus();
    1459         PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(0.25, 0.25));
    1460         PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
    1461                 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5));
    1462         PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
    1463                 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1), new TestPoint2D(0.75, 0.75));
    1464
    1465         final TestRegionBSPTree plus = split.getPlus();
    1466         PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(0.75, 0.75));
    1467         PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
    1468                 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5), new TestPoint2D(0.25, 0.25));
    1469         PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
    1470                 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
    1471     }
    1472
    1473     @Test
    1474     public void testSplit_box_onMinusOnly() {
    1475         // arrange
    1476         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
    1477
    1478         final TestLine splitter = new TestLine(new TestPoint2D(2, 0), new TestPoint2D(1, 1));
    1479
    1480         // act
    1481         final Split<TestRegionBSPTree> split = tree.split(splitter);
    1482
    1483         // assert
    1484         Assert.assertEquals(SplitLocation.MINUS, split.getLocation());
    1485
    1486         final TestRegionBSPTree minus = split.getMinus();
    1487         PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(0.5, 0.5));
    1488         PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
    1489                 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5),
    1490                 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
    1491
    1492         Assert.assertNull(split.getPlus());
    1493     }
    1494
    1495     @Test
    1496     public void testSplit_box_onPlusOnly() {
    1497         // arrange
    1498         insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
    1499
    1500         final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 1));
    1501
    1502         // act
    1503         final Split<TestRegionBSPTree> split = tree.split(splitter);
    1504
    1505         // assert
    1506         Assert.assertEquals(SplitLocation.PLUS, split.getLocation());
    1507
    1508         Assert.assertNull(split.getMinus());
    1509
    1510         final TestRegionBSPTree plus = split.getPlus();
    1511         PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(0.5, 0.5));
    1512         PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
    1513                 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5),
    1514                 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
    1515     }
    1516
    1517     @Test
    1518     public void testToString() {
    1519         // arrange
    1520         tree.getRoot().cut(TestLine.X_AXIS);
    1521
    1522         // act
    1523         final String str = tree.toString();
    1524
    1525         // assert
    1526         Assert.assertEquals("TestRegionBSPTree[count= 3, height= 1]", str);
    1527         Assert.assertTrue(tree.getRoot().toString().contains("TestRegionNode"));
    1528     }
    1529
    1530     private static void insertBox(final TestRegionBSPTree tree, final TestPoint2D upperLeft,
    1531             final TestPoint2D lowerRight) {
    1532         final TestPoint2D upperRight = new TestPoint2D(lowerRight.getX(), upperLeft.getY());
    1533         final TestPoint2D lowerLeft = new TestPoint2D(upperLeft.getX(), lowerRight.getY());
    1534
    1535         tree.insert(Arrays.asList(
    1536                     new TestLineSegment(lowerRight, upperRight),
    1537                     new TestLineSegment(upperRight, upperLeft),
    1538                     new TestLineSegment(upperLeft, lowerLeft),
    1539                     new TestLineSegment(lowerLeft, lowerRight)
    1540                 ));
    1541     }
    1542
    1543     private static void insertSkewedBowtie(final TestRegionBSPTree tree) {
    1544         tree.insert(Arrays.asList(
    1545                 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
    1546
    1547                 new TestLineSegment(new TestPoint2D(4, 0), new TestPoint2D(4, 1)),
    1548                 new TestLineSegment(new TestPoint2D(-4, 0), new TestPoint2D(-4, -1)),
    1549
    1550                 new TestLineSegment(new TestPoint2D(4, 5), new TestPoint2D(-1, 0)),
    1551                 new TestLineSegment(new TestPoint2D(-4, -5), new TestPoint2D(1, 0))));
    1552     }
    1553
    1554     private static void assertCutBoundarySegment(final List<HyperplaneConvexSubset<TestPoint2D>> boundaries,
    1555             final TestPoint2D start, final TestPoint2D end) {
    1556         Assert.assertFalse("Expected boundary to not be empty", boundaries.isEmpty());
    1557
    1558         Assert.assertEquals(1, boundaries.size());
    1559
    1560         final TestLineSegment segment = (TestLineSegment) boundaries.get(0);
    1561         PartitionTestUtils.assertPointsEqual(start, segment.getStartPoint());
    1562         PartitionTestUtils.assertPointsEqual(end, segment.getEndPoint());
    1563     }
    1564
    1565     private static void assertContainsSegment(final List<TestLineSegment> boundaries, final TestPoint2D start,
    1566             final TestPoint2D end) {
    1567         boolean found = false;
    1568         for (final TestLineSegment seg : boundaries) {
    1569             final TestPoint2D startPt = seg.getStartPoint();
    1570             final TestPoint2D endPt = seg.getEndPoint();
    1571
    1572             if (PartitionTestUtils.PRECISION.eq(start.getX(), startPt.getX()) &&
    1573                     PartitionTestUtils.PRECISION.eq(start.getY(), startPt.getY()) &&
    1574                     PartitionTestUtils.PRECISION.eq(end.getX(), endPt.getX()) &&
    1575                     PartitionTestUtils.PRECISION.eq(end.getY(), endPt.getY())) {
    1576                 found = true;
    1577                 break;
    1578             }
    1579         }
    1580
    1581         Assert.assertTrue("Expected to find segment start= " + start + ", end= " + end, found);
    1582     }
    1583
    1584     private static TestRegionBSPTree emptyTree() {
    1585         return new TestRegionBSPTree(false);
    1586     }
    1587
    1588     private static TestRegionBSPTree fullTree() {
    1589         return new TestRegionBSPTree(true);
    1590     }
    1591 }