001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.geometry.core.partitioning.bsp; 018 019import org.apache.commons.geometry.core.Point; 020import org.apache.commons.geometry.core.Transform; 021import org.apache.commons.geometry.core.partitioning.Hyperplane; 022import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset; 023 024/** Interface for Binary Space Partitioning (BSP) trees. BSP trees are spatial data 025 * structures that recursively subdivide a space using hyperplanes. They can be used 026 * for a wide variety of purposes, such as representing arbitrary polytopes, storing 027 * data for fast spatial lookups, determining the correct rendering order for objects 028 * in a 3D scene, and so on. 029 * 030 * <p>This interface contains a number of methods for extracting information from existing 031 * trees, but it does not include methods for constructing trees or modifying tree structure. 032 * This is due to the large number of possible use cases for BSP trees. Each use case is likely 033 * to have its own specific methods and rules for tree construction, making it difficult to define 034 * a single API at this level. Thus, it is left to implementation classes to define their own 035 * API for tree construction and modification.</p> 036 * 037 * @param <P> Point implementation type 038 * @param <N> Node implementation type 039 * @see <a href="https://en.wikipedia.org/wiki/Binary_space_partitioning">Binary space partitioning</a> 040 */ 041public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P, N>> 042 extends BSPSubtree<P, N> { 043 044 /** Enum specifying possible behaviors when a point used to locate a node 045 * falls directly on the cut of an internal node. 046 */ 047 enum FindNodeCutRule { 048 049 /** Choose the minus child of the internal node and continue searching. 050 * This behavior will result in a leaf node always being returned by the 051 * node search. 052 */ 053 MINUS, 054 055 /** Choose the plus child of the internal node and continue searching. 056 * This behavior will result in a leaf node always being returned by the 057 * node search. 058 */ 059 PLUS, 060 061 /** Choose the internal node and stop searching. This behavior may result 062 * in non-leaf nodes being returned by the node search. 063 */ 064 NODE 065 } 066 067 /** Get the root node of the tree. 068 * @return the root node of the tree 069 */ 070 N getRoot(); 071 072 /** Find a node in this subtree containing the given point or its interior or boundary. 073 * When a point lies directly on the cut of an internal node, the minus child of the 074 * cut is chosen. This is equivalent to {@code subtree.findNode(pt, FindNodeCutRule.MINUS)} 075 * and always returns a leaf node. 076 * @param pt test point used to locate a node in the tree 077 * @return leaf node containing the point on its interior or boundary 078 * @see #findNode(Point, FindNodeCutRule) 079 */ 080 default N findNode(final P pt) { 081 return findNode(pt, FindNodeCutRule.MINUS); 082 } 083 084 /** Find a node in this subtree containing the given point on its interior or boundary. The 085 * search should always return a leaf node except in the cases where the given point lies 086 * exactly on the cut of an internal node. In this case, it is unclear whether 087 * the search should continue with the minus child, the plus child, or end with the internal 088 * node. The {@code cutRule} argument specifies what should happen in this case. 089 * <ul> 090 * <li>{@link FindNodeCutRule#MINUS} - continue the search in the minus subtree</li> 091 * <li>{@link FindNodeCutRule#PLUS} - continue the search in the plus subtree</li> 092 * <li>{@link FindNodeCutRule#NODE} - stop the search and return the internal node</li> 093 * </ul> 094 * @param pt test point used to locate a node in the tree 095 * @param cutRule value used to determine the search behavior when the test point lies 096 * exactly on the cut of an internal node 097 * @return node containing the point on its interior or boundary 098 * @see #findNode(Point) 099 */ 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}