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 }