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  import org.apache.commons.geometry.core.Transform;
    21  import org.apache.commons.geometry.core.partitioning.Hyperplane;
    22  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    23
    24  /** Interface for Binary Space Partitioning (BSP) trees. BSP trees are spatial data
    25   * structures that recursively subdivide a space using hyperplanes. They can be used
    26   * for a wide variety of purposes, such as representing arbitrary polytopes, storing
    27   * data for fast spatial lookups, determining the correct rendering order for objects
    28   * in a 3D scene, and so on.
    29   *
    30   * <p>This interface contains a number of methods for extracting information from existing
    31   * trees, but it does not include methods for constructing trees or modifying tree structure.
    32   * This is due to the large number of possible use cases for BSP trees. Each use case is likely
    33   * to have its own specific methods and rules for tree construction, making it difficult to define
    34   * a single API at this level. Thus, it is left to implementation classes to define their own
    35   * API for tree construction and modification.</p>
    36   *
    37   * @param <P> Point implementation type
    38   * @param <N> Node implementation type
    39   * @see <a href="https://en.wikipedia.org/wiki/Binary_space_partitioning">Binary space partitioning</a>
    40   */
    41  public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P, N>>
    42      extends BSPSubtree<P, N> {
    43
    44      /** Enum specifying possible behaviors when a point used to locate a node
    45       * falls directly on the cut of an internal node.
    46       */
    47      enum FindNodeCutRule {
    48
    49          /** Choose the minus child of the internal node and continue searching.
    50           * This behavior will result in a leaf node always being returned by the
    51           * node search.
    52           */
    53          MINUS,
    54
    55          /** Choose the plus child of the internal node and continue searching.
    56           * This behavior will result in a leaf node always being returned by the
    57           * node search.
    58           */
    59          PLUS,
    60
    61          /** Choose the internal node and stop searching. This behavior may result
    62           * in non-leaf nodes being returned by the node search.
    63           */
    64          NODE
    65      }
    66
    67      /** Get the root node of the tree.
    68       * @return the root node of the tree
    69       */
    70      N getRoot();
    71
    72      /** Find a node in this subtree containing the given point or its interior or boundary.
    73       * When a point lies directly on the cut of an internal node, the minus child of the
    74       * cut is chosen. This is equivalent to {@code subtree.findNode(pt, FindNodeCutRule.MINUS)}
    75       * and always returns a leaf node.
    76       * @param pt test point used to locate a node in the tree
    77       * @return leaf node containing the point on its interior or boundary
    78       * @see #findNode(Point, FindNodeCutRule)
    79       */
    80      default N findNode(final P pt) {
    81          return findNode(pt, FindNodeCutRule.MINUS);
    82      }
    83
    84      /** Find a node in this subtree containing the given point on its interior or boundary. The
    85       * search should always return a leaf node except in the cases where the given point lies
    86       * exactly on the cut of an internal node. In this case, it is unclear whether
    87       * the search should continue with the minus child, the plus child, or end with the internal
    88       * node. The {@code cutRule} argument specifies what should happen in this case.
    89       * <ul>
    90       *      <li>{@link FindNodeCutRule#MINUS} - continue the search in the minus subtree</li>
    91       *      <li>{@link FindNodeCutRule#PLUS} - continue the search in the plus subtree</li>
    92       *      <li>{@link FindNodeCutRule#NODE} - stop the search and return the internal node</li>
    93       * </ul>
    94       * @param pt test point used to locate a node in the tree
    95       * @param cutRule value used to determine the search behavior when the test point lies
    96       *      exactly on the cut of an internal node
    97       * @return node containing the point on its interior or boundary
    98       * @see #findNode(Point)
    99       */
    100     N findNode(P pt, FindNodeCutRule cutRule);
    101
    102     /** Make the current instance a deep copy of the argument.
    103      * @param src the tree to copy
    104      */
    105     void copy(BSPTree<P, N> src);
    106
    107     /** Set this instance to the region represented by the given node. The
    108      * given node could have come from this tree or a different tree.
    109      * @param node the node to extract
    110      */
    111     void extract(N node);
    112
    113     /** Transform this tree. Each cut in the tree is transformed in place using
    114      * the given {@link Transform}.
    115      * @param transform the transform to apply
    116      */
    117     void transform(Transform<P> transform);
    118
    119     /** Interface for Binary Space Partitioning (BSP) tree nodes.
    120      * @param <P> Point type
    121      * @param <N> BSP tree node implementation type
    122      */
    123     interface Node<P extends Point<P>, N extends Node<P, N>> extends BSPSubtree<P, N> {
    124
    125         /** Get the {@link BSPTree} that owns the node.
    126          * @return the owning tree
    127          */
    128         BSPTree<P, N> getTree();
    129
    130         /** Get the depth of the node in the tree. The root node of the tree
    131          * has a depth of 0.
    132          * @return the depth of the node in the tree
    133          */
    134         int depth();
    135
    136         /** Get the parent of the node. This will be null if the node is the
    137          * root of the tree.
    138          * @return the parent node for this instance
    139          */
    140         N getParent();
    141
    142         /** Get the cut for the node. This is a hyperplane convex subset that splits
    143          * the region for the cell into two disjoint regions, namely the plus and
    144          * minus regions. This will be null for leaf nodes.
    145          * @see #getPlus()
    146          * @see #getMinus()
    147          * @return the cut for the cell
    148          * @see #getCutHyperplane()
    149          */
    150         HyperplaneConvexSubset<P> getCut();
    151
    152         /** Get the hyperplane containing the node cut, if it exists.
    153          * @return the hyperplane containing the node cut, or null if
    154          *      the node does not have a cut
    155          * @see #getCut()
    156          */
    157         Hyperplane<P> getCutHyperplane();
    158
    159         /** Get the node for the minus region of the cell. This will be null if the
    160          * node has not been cut, ie if it is a leaf node.
    161          * @return the node for the minus region of the cell
    162          */
    163         N getMinus();
    164
    165         /** Get the node for the plus region of the cell. This will be null if the
    166          * node has not been cut, ie if it is a leaf node.
    167          * @return the node for the plus region of the cell
    168          */
    169         N getPlus();
    170
    171         /** Return true if the node is a leaf node, meaning that it has no
    172          * binary partitioner (aka "cut") and therefore no child nodes.
    173          * @return true if the node is a leaf node
    174          */
    175         boolean isLeaf();
    176
    177         /** Return true if the node is an internal node, meaning that is
    178          * has a binary partitioner (aka "cut") and therefore two child nodes.
    179          * @return true if the node is an internal node
    180          */
    181         boolean isInternal();
    182
    183         /** Return true if the node has a parent and is the parent's minus
    184          * child.
    185          * @return true if the node is the minus child of its parent
    186          */
    187         boolean isMinus();
    188
    189         /** Return true if the node has a parent and is the parent's plus
    190          * child.
    191          * @return true if the node is the plus child of its parent
    192          */
    193         boolean isPlus();
    194
    195         /** Trim the given hyperplane subset to the region defined by this node by cutting
    196          * the argument with the cut hyperplanes (binary partitioners) of all parent nodes
    197          * up to the root. Null is returned if the hyperplane subset lies outside of the region
    198          * defined by the node.
    199          * @param sub the hyperplane subset to trim
    200          * @return the trimmed hyperplane subset or null if no part of the argument lies
    201          *      within the node's region
    202          */
    203         HyperplaneConvexSubset<P> trim(HyperplaneConvexSubset<P> sub);
    204     }
    205 }