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 org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.ClosestFirstVisitor;
    20  import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.FarthestFirstVisitor;
    21  import org.apache.commons.geometry.core.partitioning.test.TestBSPTree;
    22  import org.apache.commons.geometry.core.partitioning.test.TestBSPTree.TestNode;
    23  import org.apache.commons.geometry.core.partitioning.test.TestLine;
    24  import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
    25  import org.junit.jupiter.api.Assertions;
    26  import org.junit.jupiter.api.Test;
    27
    28  class BSPTreeVisitorTest {
    29
    30      @Test
    31      void testDefaultVisitOrder() {
    32          // arrange
    33          final BSPTreeVisitor<TestPoint2D, TestNode> visitor = n -> BSPTreeVisitor.Result.CONTINUE;
    34
    35          // act/assert
    36          Assertions.assertEquals(BSPTreeVisitor.Order.NODE_MINUS_PLUS, visitor.visitOrder(null));
    37      }
    38
    39      @Test
    40      void testClosestFirst() {
    41          // arrange
    42          final TestBSPTree tree = new TestBSPTree();
    43          final TestNode root = tree.getRoot();
    44          root.cut(TestLine.X_AXIS);
    45          root.getMinus().cut(TestLine.Y_AXIS);
    46          root.getPlus().cut(TestLine.Y_AXIS);
    47
    48          // act
    49          checkClosestFirst(new TestPoint2D(1, 1), root, BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    50          checkClosestFirst(new TestPoint2D(1, 1), root.getMinus(), BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    51          checkClosestFirst(new TestPoint2D(1, 1), root.getPlus(), BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    52
    53          checkClosestFirst(new TestPoint2D(-1, 1), root, BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    54          checkClosestFirst(new TestPoint2D(-1, 1), root.getMinus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    55          checkClosestFirst(new TestPoint2D(-1, 1), root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    56
    57          checkClosestFirst(new TestPoint2D(-1, -1), root, BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    58          checkClosestFirst(new TestPoint2D(-1, -1), root.getMinus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    59          checkClosestFirst(new TestPoint2D(-1, -1), root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    60
    61          checkClosestFirst(new TestPoint2D(1, -1), root, BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    62          checkClosestFirst(new TestPoint2D(1, -1), root.getMinus(), BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    63          checkClosestFirst(new TestPoint2D(1, -1), root.getPlus(), BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    64
    65          checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    66          checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    67          checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    68      }
    69
    70      @Test
    71      void testFarthestFirst() {
    72          // arrange
    73          final TestBSPTree tree = new TestBSPTree();
    74          final TestNode root = tree.getRoot();
    75          root.cut(TestLine.X_AXIS);
    76          root.getMinus().cut(TestLine.Y_AXIS);
    77          root.getPlus().cut(TestLine.Y_AXIS);
    78
    79          // act
    80          checkFarthestFirst(new TestPoint2D(1, 1), root, BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    81          checkFarthestFirst(new TestPoint2D(1, 1), root.getMinus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    82          checkFarthestFirst(new TestPoint2D(1, 1), root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    83
    84          checkFarthestFirst(new TestPoint2D(-1, 1), root, BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    85          checkFarthestFirst(new TestPoint2D(-1, 1), root.getMinus(), BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    86          checkFarthestFirst(new TestPoint2D(-1, 1), root.getPlus(), BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    87
    88          checkFarthestFirst(new TestPoint2D(-1, -1), root, BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    89          checkFarthestFirst(new TestPoint2D(-1, -1), root.getMinus(), BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    90          checkFarthestFirst(new TestPoint2D(-1, -1), root.getPlus(), BSPTreeVisitor.Order.PLUS_NODE_MINUS);
    91
    92          checkFarthestFirst(new TestPoint2D(1, -1), root, BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    93          checkFarthestFirst(new TestPoint2D(1, -1), root.getMinus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    94          checkFarthestFirst(new TestPoint2D(1, -1), root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    95
    96          checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    97          checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    98          checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), BSPTreeVisitor.Order.MINUS_NODE_PLUS);
    99      }
    100
    101     private static void checkClosestFirst(final TestPoint2D target, final TestNode node, final BSPTreeVisitor.Order order) {
    102         final ClosestFirstStubVisitor visitor = new ClosestFirstStubVisitor(target);
    103
    104         Assertions.assertSame(target, visitor.getTarget());
    105         Assertions.assertEquals(order, visitor.visitOrder(node));
    106     }
    107
    108     private static void checkFarthestFirst(final TestPoint2D target, final TestNode node, final BSPTreeVisitor.Order order) {
    109         final FarthestFirstStubVisitor visitor = new FarthestFirstStubVisitor(target);
    110
    111         Assertions.assertSame(target, visitor.getTarget());
    112         Assertions.assertEquals(order, visitor.visitOrder(node));
    113     }
    114
    115     private static class ClosestFirstStubVisitor extends ClosestFirstVisitor<TestPoint2D, TestNode> {
    116
    117         ClosestFirstStubVisitor(final TestPoint2D target) {
    118             super(target);
    119         }
    120
    121         @Override
    122         public Result visit(final TestNode node) {
    123             return Result.CONTINUE;
    124         }
    125     }
    126
    127     private static class FarthestFirstStubVisitor extends FarthestFirstVisitor<TestPoint2D, TestNode> {
    128
    129         FarthestFirstStubVisitor(final TestPoint2D target) {
    130             super(target);
    131         }
    132
    133         @Override
    134         public Result visit(final TestNode node) {
    135             return Result.CONTINUE;
    136         }
    137     }
    138 }