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 }