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.Point;
    20
    21  /** Interface for visiting the nodes in a {@link BSPTree} or {@link BSPSubtree}.
    22   * @param <P> Point implementation type
    23   * @param <N> BSP tree node implementation type
    24   */
    25  @FunctionalInterface
    26  public interface BSPTreeVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>> {
    27
    28      /** Enum used to specify the order in which visitors should visit the nodes
    29       * in the tree.
    30       */
    31      enum Order {
    32
    33          /** Indicates that the visitor should first visit the plus sub-tree, then
    34           * the minus sub-tree and then the current node.
    35           */
    36          PLUS_MINUS_NODE,
    37
    38          /** Indicates that the visitor should first visit the plus sub-tree, then
    39           * the current node, and then the minus sub-tree.
    40           */
    41          PLUS_NODE_MINUS,
    42
    43          /** Indicates that the visitor should first visit the minus sub-tree, then
    44           * the plus sub-tree, and then the current node.
    45           */
    46          MINUS_PLUS_NODE,
    47
    48          /** Indicates that the visitor should first visit the minus sub-tree, then the
    49           * current node, and then the plus sub-tree.
    50           */
    51          MINUS_NODE_PLUS,
    52
    53          /** Indicates that the visitor should first visit the current node, then the
    54           * plus sub-tree, and then the minus sub-tree.
    55           */
    56          NODE_PLUS_MINUS,
    57
    58          /** Indicates that the visitor should first visit the current node, then the
    59           * minus sub-tree, and then the plus sub-tree.
    60           */
    61          NODE_MINUS_PLUS,
    62
    63          /** Indicates that the visitor should not visit any of the nodes in this subtree. */
    64          NONE
    65      }
    66
    67      /** Enum representing the result of a BSP tree node visit operation.
    68       */
    69      enum Result {
    70
    71          /** Indicates that the visit operation should continue with the remaining nodes in
    72           * the BSP tree.
    73           */
    74          CONTINUE,
    75
    76          /** Indicates that the visit operation should terminate and not visit any further
    77           * nodes in the tree.
    78           */
    79          TERMINATE
    80      }
    81
    82      /** Visit a node in a BSP tree. This method is called for both internal nodes and
    83       * leaf nodes.
    84       * @param node the node being visited
    85       * @return the result of the visit operation
    86       */
    87      Result visit(N node);
    88
    89      /** Determine the visit order for the given internal node. This is called for each
    90       * internal node before {@link #visit(BSPTree.Node)} is called. Returning null
    91       * or {@link Order#NONE}from this method skips the subtree rooted at the given node.
    92       * This method is not called on leaf nodes.
    93       * @param internalNode the internal node to determine the visit order for
    94       * @return the order that the subtree rooted at the given node should be visited
    95       */
    96      default Order visitOrder(final N internalNode) {
    97          return Order.NODE_MINUS_PLUS;
    98      }
    99
    100     /** Abstract class for {@link BSPTreeVisitor} implementations that base their visit
    101      * ordering on a target point.
    102      * @param <P> Point implementation type
    103      * @param <N> BSP tree node implementation type
    104      */
    105     abstract class TargetPointVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
    106         implements BSPTreeVisitor<P, N> {
    107         /** Point serving as the target of the traversal. */
    108         private final P target;
    109
    110         /** Simple constructor.
    111          * @param target the point serving as the target for the tree traversal
    112          */
    113         protected TargetPointVisitor(final P target) {
    114             this.target = target;
    115         }
    116
    117         /** Get the target point for the tree traversal.
    118          * @return the target point for the tree traversal
    119          */
    120         public P getTarget() {
    121             return target;
    122         }
    123     }
    124
    125     /** {@link BSPTreeVisitor} base class that orders tree nodes so that nodes closest to the target point are
    126      * visited first. This is done by choosing {@link Order#MINUS_NODE_PLUS}
    127      * when the target point lies on the minus side of the node's cut hyperplane and {@link Order#PLUS_NODE_MINUS}
    128      * when it lies on the plus side. The order {@link Order#MINUS_NODE_PLUS} order is used when
    129      * the target point lies directly on the node's cut hyerplane and no child node is closer than the other.
    130      * @param <P> Point implementation type
    131      * @param <N> BSP tree node implementation type
    132      */
    133     abstract class ClosestFirstVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
    134         extends TargetPointVisitor<P, N> {
    135         /** Simple constructor.
    136          * @param target the point serving as the target for the traversal
    137          */
    138         protected ClosestFirstVisitor(final P target) {
    139             super(target);
    140         }
    141
    142         /** {@inheritDoc} */
    143         @Override
    144         public Order visitOrder(final N node) {
    145             if (node.getCutHyperplane().offset(getTarget()) > 0) {
    146                 return Order.PLUS_NODE_MINUS;
    147             }
    148             return Order.MINUS_NODE_PLUS;
    149         }
    150     }
    151
    152     /** {@link BSPTreeVisitor} base class that orders tree nodes so that nodes farthest from the target point
    153      * are traversed first. This is done by choosing {@link Order#PLUS_NODE_MINUS}
    154      * when the target point lies on the minus side of the node's cut hyperplane and {@link Order#MINUS_NODE_PLUS}
    155      * when it lies on the plus side. The order {@link Order#MINUS_NODE_PLUS} order is used when
    156      * the target point lies directly on the node's cut hyerplane and no child node is closer than the other.
    157      * @param <P> Point implementation type
    158      * @param <N> BSP tree node implementation type
    159      */
    160     abstract class FarthestFirstVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
    161         extends TargetPointVisitor<P, N> {
    162         /** Simple constructor.
    163          * @param target the point serving as the target for the traversal
    164          */
    165         protected FarthestFirstVisitor(final P target) {
    166             super(target);
    167         }
    168
    169         /** {@inheritDoc} */
    170         @Override
    171         public Order visitOrder(final N node) {
    172             if (node.getCutHyperplane().offset(getTarget()) < 0) {
    173                 return Order.PLUS_NODE_MINUS;
    174             }
    175             return Order.MINUS_NODE_PLUS;
    176         }
    177     }
    178 }