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.Arrays;
    20  import java.util.List;
    21
    22  import org.apache.commons.geometry.core.GeometryTestUtils;
    23  import org.apache.commons.geometry.core.RegionLocation;
    24  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    25  import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
    26  import org.apache.commons.geometry.core.partitioning.test.TestLine;
    27  import org.apache.commons.geometry.core.partitioning.test.TestLineSegment;
    28  import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
    29  import org.apache.commons.geometry.core.partitioning.test.TestRegionBSPTree;
    30  import org.junit.jupiter.api.Assertions;
    31  import org.junit.jupiter.api.Test;
    32
    33  class AbstractPartitionedRegionBuilderTest {
    34
    35      @Test
    36      void testCtor_invalidTree() {
    37          // arrange
    38          final TestRegionBSPTree tree = new TestRegionBSPTree(true);
    39
    40          // act/assert
    41          GeometryTestUtils.assertThrowsWithMessage(() -> {
    42              new TestRegionBuilder(tree);
    43          }, IllegalArgumentException.class, "Tree must be empty");
    44      }
    45
    46      @Test
    47      void testBuildRegion_empty() {
    48          // arrange
    49          final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    50
    51          // act
    52          final TestRegionBSPTree tree = builder.build();
    53
    54          // assert
    55          Assertions.assertTrue(tree.isEmpty());
    56          Assertions.assertEquals(1, tree.count());
    57          Assertions.assertEquals(0, tree.height());
    58      }
    59
    60      @Test
    61      void testInsertPartition_cannotInsertAfterBoundary() {
    62          // arrange
    63          final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    64
    65          builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    66
    67          // act/assert
    68          GeometryTestUtils.assertThrowsWithMessage(() -> {
    69              builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0)).span());
    70          }, IllegalStateException.class, "Cannot insert partitions after boundaries have been inserted");
    71      }
    72
    73      @Test
    74      void testBuildRegion_noPartitions_halfSpace() {
    75          // arrange
    76          final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    77
    78          // act
    79          builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    80          final TestRegionBSPTree tree = builder.build();
    81
    82          // assert
    83          Assertions.assertFalse(tree.isEmpty());
    84          Assertions.assertFalse(tree.isFull());
    85
    86          Assertions.assertEquals(3, tree.count());
    87          Assertions.assertEquals(1, tree.height());
    88
    89          PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    90                  new TestPoint2D(-5, 1), new TestPoint2D(0, 1), new TestPoint2D(5, 1));
    91
    92          PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    93                  new TestPoint2D(-5, 0), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
    94
    95          PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    96                  new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
    97      }
    98
    99      @Test
    100     void testBuildRegion_boundaryOnPartition_sameOrientation() {
    101      // arrange
    102         final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    103
    104         // act
    105         builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0)).span());
    106
    107         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    108         final TestRegionBSPTree tree = builder.build();
    109
    110         // assert
    111         Assertions.assertFalse(tree.isEmpty());
    112         Assertions.assertFalse(tree.isFull());
    113
    114         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    115                 new TestPoint2D(-5, 1), new TestPoint2D(0, 1), new TestPoint2D(5, 1));
    116
    117         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    118                 new TestPoint2D(-5, 0), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
    119
    120         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    121                 new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
    122     }
    123
    124     @Test
    125     void testBuildRegion_boundaryOnPartition_oppositeOrientation() {
    126      // arrange
    127         final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    128
    129         // act
    130         builder.insertPartition(new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 0)).span());
    131
    132         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    133         final TestRegionBSPTree tree = builder.build();
    134
    135         // assert
    136         Assertions.assertFalse(tree.isEmpty());
    137         Assertions.assertFalse(tree.isFull());
    138
    139         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    140                 new TestPoint2D(-5, 1), new TestPoint2D(0, 1), new TestPoint2D(5, 1));
    141
    142         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    143                 new TestPoint2D(-5, 0), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
    144
    145         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    146                 new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
    147     }
    148
    149     @Test
    150     void testBuildRegion_boundaryOnPartition_multipleBoundaries_sameOrientation() {
    151      // arrange
    152         final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    153
    154         // act
    155         builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0)).span());
    156
    157         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0)));
    158         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    159         final TestRegionBSPTree tree = builder.build();
    160
    161         // assert
    162         Assertions.assertFalse(tree.isEmpty());
    163         Assertions.assertFalse(tree.isFull());
    164
    165         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE, new TestPoint2D(5, 1));
    166
    167         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    168                 new TestPoint2D(0, 5), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
    169
    170         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    171                 new TestPoint2D(-5, 1), new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
    172     }
    173
    174     @Test
    175     void testBuildRegion_boundaryOnPartition_multipleBoundaries_oppositeOrientation() {
    176      // arrange
    177         final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    178
    179         // act
    180         builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 0)).span());
    181
    182         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0)));
    183         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    184         final TestRegionBSPTree tree = builder.build();
    185
    186         // assert
    187         Assertions.assertFalse(tree.isEmpty());
    188         Assertions.assertFalse(tree.isFull());
    189
    190         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE, new TestPoint2D(5, 1));
    191
    192         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    193                 new TestPoint2D(0, 5), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
    194
    195         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    196                 new TestPoint2D(-5, 1), new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
    197     }
    198
    199     @Test
    200     void testBuildRegion_multipleBoundariesOnPartition() {
    201         // arrange
    202         final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    203
    204         // act
    205         builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0)).span());
    206
    207         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    208         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0)));
    209         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 0)));
    210         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(-1, 0)));
    211
    212         final TestRegionBSPTree tree = builder.build();
    213
    214         // assert
    215         Assertions.assertFalse(tree.isEmpty());
    216         Assertions.assertFalse(tree.isFull());
    217
    218         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    219                 new TestPoint2D(1, 1), new TestPoint2D(-1, -1));
    220
    221         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    222                 new TestPoint2D(1, 0), new TestPoint2D(-1, 0), new TestPoint2D(0, 1), new TestPoint2D(0, -1));
    223
    224         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    225                 new TestPoint2D(-1, 1), new TestPoint2D(1, -1));
    226     }
    227
    228     @Test
    229     void testBuildRegion_grid_halfSpace_boundaryOnPartition() {
    230         // arrange
    231         final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    232
    233         // act
    234         insertGridRecursive(-2, 2, 5, builder);
    235
    236         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    237         final TestRegionBSPTree tree = builder.build();
    238
    239         // assert
    240         Assertions.assertFalse(tree.isEmpty());
    241         Assertions.assertFalse(tree.isFull());
    242
    243         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    244                 new TestPoint2D(-5, 1), new TestPoint2D(0, 1), new TestPoint2D(5, 1));
    245
    246         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    247                 new TestPoint2D(-5, 0), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
    248
    249         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    250                 new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
    251     }
    252
    253     @Test
    254     void testBuildRegion_boundariesOnPartitionPropagateInsideCorrectly() {
    255         // arrange
    256         final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    257
    258         // act
    259         builder.insertPartition(new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)));
    260         builder.insertPartition(new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)));
    261
    262         builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
    263         builder.insertBoundary(new TestLineSegment(new TestPoint2D(1, 1), new TestPoint2D(1, 0)));
    264         final TestRegionBSPTree tree = builder.build();
    265
    266         // assert
    267         Assertions.assertFalse(tree.isEmpty());
    268         Assertions.assertFalse(tree.isFull());
    269
    270         PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    271                 new TestPoint2D(2, 2), new TestPoint2D(5, 5));
    272
    273         PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    274                 new TestPoint2D(1, 0), new TestPoint2D(1, 10), new TestPoint2D(10, 0));
    275
    276         PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    277                 new TestPoint2D(-1, 1), new TestPoint2D(-10, 10),
    278                 new TestPoint2D(-1, -1), new TestPoint2D(1, -1));
    279     }
    280
    281     @Test
    282     void testBuildRegion_grid_cube() {
    283         // arrange
    284         final int maxCount = 5;
    285
    286         final List<TestLineSegment> boundaries = Arrays.asList(
    287                 new TestLineSegment(new TestPoint2D(-1, -1), new TestPoint2D(1, -1)),
    288                 new TestLineSegment(new TestPoint2D(1, -1), new TestPoint2D(1, 1)),
    289                 new TestLineSegment(new TestPoint2D(1, 1), new TestPoint2D(-1, 1)),
    290                 new TestLineSegment(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
    291             );
    292
    293         for (int c = 0; c <= maxCount; ++c) {
    294             final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    295
    296             // act
    297             insertGridRecursive(-2, 2, c, builder);
    298
    299             for (final TestLineSegment boundary : boundaries) {
    300                 builder.insertBoundary(boundary);
    301             }
    302
    303             final TestRegionBSPTree tree = builder.build();
    304
    305             // assert
    306             Assertions.assertFalse(tree.isEmpty());
    307             Assertions.assertFalse(tree.isFull());
    308
    309             PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    310                     new TestPoint2D(0, 0),
    311                     new TestPoint2D(-0.5, -0.5), new TestPoint2D(0.5, -0.5),
    312                     new TestPoint2D(0.5, 0.5), new TestPoint2D(-0.5, 0.5));
    313
    314             PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    315                     new TestPoint2D(-1, -1), new TestPoint2D(1, -1), new TestPoint2D(1, 1), new TestPoint2D(-1, 1),
    316                     new TestPoint2D(-1, 0), new TestPoint2D(1, 0), new TestPoint2D(0, 1), new TestPoint2D(0, -1));
    317
    318             PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    319                     new TestPoint2D(-2, -2), new TestPoint2D(2, -2), new TestPoint2D(2, 2), new TestPoint2D(-2, 2),
    320                     new TestPoint2D(-2, 0), new TestPoint2D(2, 0), new TestPoint2D(0, 2), new TestPoint2D(0, -2));
    321         }
    322     }
    323
    324     @Test
    325     void testBuildRegion_grid_diamond() {
    326         // arrange
    327         final int maxCount = 5;
    328
    329         final List<TestLineSegment> boundaries = Arrays.asList(
    330                 new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(-1, 0)),
    331                 new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(0, -1)),
    332                 new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(1, 0)),
    333                 new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(0, 1))
    334             );
    335
    336         for (int c = 0; c <= maxCount; ++c) {
    337             final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    338
    339             // act
    340             insertGridRecursive(-2, 2, c, builder);
    341
    342             for (final TestLineSegment boundary : boundaries) {
    343                 builder.insertBoundary(boundary);
    344             }
    345
    346             final TestRegionBSPTree tree = builder.build();
    347
    348             // assert
    349             Assertions.assertFalse(tree.isEmpty());
    350             Assertions.assertFalse(tree.isFull());
    351
    352             PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    353                     new TestPoint2D(0, 0),
    354                     new TestPoint2D(-0.25, -0.25), new TestPoint2D(0.25, -0.25),
    355                     new TestPoint2D(0.25, 0.25), new TestPoint2D(-0.25, 0.25));
    356
    357             PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    358                     new TestPoint2D(-0.5, 0.5), new TestPoint2D(-0.5, -0.5), new TestPoint2D(0.5, -0.5), new TestPoint2D(0.5, 0.5),
    359                     new TestPoint2D(-1, 0), new TestPoint2D(1, 0), new TestPoint2D(0, 1), new TestPoint2D(0, -1));
    360
    361             PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    362                     new TestPoint2D(-2, -2), new TestPoint2D(2, -2), new TestPoint2D(2, 2), new TestPoint2D(-2, 2),
    363                     new TestPoint2D(-2, 0), new TestPoint2D(2, 0), new TestPoint2D(0, 2), new TestPoint2D(0, -2));
    364         }
    365     }
    366
    367     @Test
    368     void testBuildRegion_grid_horseshoe() {
    369         // arrange
    370         final int maxCount = 5;
    371
    372         final List<TestLineSegment> boundaries = Arrays.asList(
    373                 new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(1, 1)),
    374                 new TestLineSegment(new TestPoint2D(1, 1), new TestPoint2D(3, 1)),
    375                 new TestLineSegment(new TestPoint2D(3, 1), new TestPoint2D(3, 2)),
    376                 new TestLineSegment(new TestPoint2D(3, 2), new TestPoint2D(-1, 2)),
    377                 new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-1, -1)),
    378                 new TestLineSegment(new TestPoint2D(-1, -1), new TestPoint2D(3, -1)),
    379                 new TestLineSegment(new TestPoint2D(3, -1), new TestPoint2D(3, 0)),
    380                 new TestLineSegment(new TestPoint2D(3, 0), new TestPoint2D(1, 0))
    381             );
    382
    383         for (int c = 0; c <= maxCount; ++c) {
    384             final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
    385
    386             // act
    387             insertGridRecursive(-2, 2, c, builder);
    388
    389             for (final TestLineSegment boundary : boundaries) {
    390                 builder.insertBoundary(boundary);
    391             }
    392
    393             final TestRegionBSPTree tree = builder.build();
    394
    395             // assert
    396             Assertions.assertFalse(tree.isEmpty());
    397             Assertions.assertFalse(tree.isFull());
    398
    399             PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
    400                     new TestPoint2D(0, 0),
    401                     new TestPoint2D(0, 1.5), new TestPoint2D(2, 1.5),
    402                     new TestPoint2D(0, -0.5), new TestPoint2D(2, -0.5));
    403
    404             PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
    405                     new TestPoint2D(1, 0), new TestPoint2D(1, 1), new TestPoint2D(3, 1), new TestPoint2D(3, 2),
    406                     new TestPoint2D(-1, 2), new TestPoint2D(-1, -1), new TestPoint2D(3, -1), new TestPoint2D(3, 0),
    407                     new TestPoint2D(1, 0.5), new TestPoint2D(2, 1), new TestPoint2D(3, 1.5), new TestPoint2D(1, 2),
    408                     new TestPoint2D(-1, 0.5), new TestPoint2D(3, -0.5), new TestPoint2D(2, 0));
    409
    410             PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
    411                     new TestPoint2D(2, 0.5), new TestPoint2D(4, 0.5), new TestPoint2D(4, 0), new TestPoint2D(4, 1.5),
    412                     new TestPoint2D(1, 4), new TestPoint2D(1, -4), new TestPoint2D(-4, 0.5));
    413         }
    414     }
    415
    416     private static void insertGridRecursive(final double min, final double max, final int count, final TestRegionBuilder builder) {
    417         if (count > 0) {
    418             final double center = (0.5 * (max - min)) + min;
    419
    420             builder.insertPartition(
    421                     new TestLine(new TestPoint2D(center, center), new TestPoint2D(center + 1, center)).span());
    422
    423             builder.insertPartition(
    424                     new TestLine(new TestPoint2D(center, center), new TestPoint2D(center, center + 1)).span());
    425
    426             insertGridRecursive(min, center, count - 1, builder);
    427             insertGridRecursive(center, max, count - 1, builder);
    428         }
    429     }
    430
    431     private static class TestRegionBuilder
    432         extends AbstractPartitionedRegionBuilder<TestPoint2D, TestRegionBSPTree.TestRegionNode> {
    433
    434         TestRegionBuilder(final TestRegionBSPTree tree) {
    435             super(tree);
    436         }
    437
    438         public TestRegionBSPTree build() {
    439             return (TestRegionBSPTree) buildInternal();
    440         }
    441
    442         public void insertPartition(final HyperplaneConvexSubset<TestPoint2D> partition) {
    443             insertPartitionInternal(partition);
    444         }
    445
    446         public void insertBoundary(final HyperplaneConvexSubset<TestPoint2D> boundary) {
    447             insertBoundaryInternal(boundary);
    448         }
    449     }
    450 }