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 java.util.ArrayList; 020import java.util.Comparator; 021import java.util.HashSet; 022import java.util.List; 023import java.util.Set; 024import java.util.function.BiConsumer; 025 026import org.apache.commons.geometry.core.Point; 027import org.apache.commons.geometry.core.RegionLocation; 028import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset; 029import org.apache.commons.geometry.core.partitioning.Split; 030import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree.SubtreeInitializer; 031import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree.AbstractRegionNode; 032 033/** Class encapsulating logic for building regions by inserting boundaries into a BSP 034 * tree containing structural cuts, i.e. cuts where both sides of the cut have the same region 035 * location. This technique only produces accurate results when the inserted boundaries define 036 * the entire surface of the region. However, for valid input boundaries, significant performance 037 * improvements can be achieved due to the reduced height of the tree, especially where large 038 * numbers of boundaries are involved and/or the defined region is convex. 039 * 040 * <h2>Implementation Notes</h2> 041 * 042 * <p>This class constructs regions in two phases: (1) <em>partition insertion</em> and (2) <em>boundary insertion</em>. 043 * Instances begin in the <em>partition insertion</em> phase. Here, partitions can be inserted into the empty tree 044 * using the standard BSP insertion logic. The {@link RegionCutRule#INHERIT INHERIT} cut rule is used so that the 045 * represented region remains empty even as partitions are inserted. 046 * </p> 047 * 048 * <p>The instance moves into the <em>boundary insertion</em> phase when the caller inserts the first region boundary. 049 * Attempting to insert a partition after this point results in an {@code IllegalStateException}. This ensures that 050 * partitioning cuts are always located higher up the tree than boundary cuts.</p> 051 * 052 * <p>After all boundaries are inserted, the tree undergoes final processing to ensure that the region is consistent 053 * and that unnecessary nodes are removed.</p> 054 * 055 * <p>This class does not expose any public methods so that subclasses can present their own 056 * public API, tailored to the specific types being worked with. In particular, most subclasses 057 * will want to restrict the tree types used with the algorithm, which is difficult to implement 058 * cleanly at this level.</p> 059 * @param <P> Point implementation type 060 * @param <N> BSP tree node implementation type 061 */ 062public abstract class AbstractPartitionedRegionBuilder< 063 P extends Point<P>, 064 N extends AbstractRegionNode<P, N>> { 065 066 /** Comparator for sorting nodes with the deepest nodes first. */ 067 private static final Comparator<BSPTree.Node<?, ?>> DEEPEST_FIRST_ORDER = 068 (a, b) -> Integer.compare(b.depth(), a.depth()); 069 070 /** Tree being constructed. */ 071 private final AbstractRegionBSPTree<P, N> tree; 072 073 /** Subtree initializer for inserted boundaries. */ 074 private final SubtreeInitializer<N> subtreeInit; 075 076 /** Flag indicating whether or not partitions may still be inserted into the tree. */ 077 private boolean insertingPartitions = true; 078 079 /** Set of all internal nodes used as partitioning nodes. */ 080 private final Set<N> partitionNodes = new HashSet<>(); 081 082 /** Construct a new instance that builds a partitioned region in the given tree. The tree must 083 * be empty. 084 * @param tree tree to build the region in; must be empty 085 * @throws IllegalArgumentException if the tree is not empty 086 */ 087 protected AbstractPartitionedRegionBuilder(final AbstractRegionBSPTree<P, N> tree) { 088 if (!tree.isEmpty()) { 089 throw new IllegalArgumentException("Tree must be empty"); 090 } 091 092 this.tree = tree; 093 this.subtreeInit = tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE); 094 } 095 096 /** Internal method to build and return the tree representing the final partitioned region. 097 * @return the partitioned region 098 */ 099 protected AbstractRegionBSPTree<P, N> buildInternal() { 100 // condense to combine homogenous leaf nodes 101 tree.condense(); 102 103 // propagate region interiors to partitioned nodes that have not received 104 // a boundary 105 if (propagateRegionInterior()) { 106 // condense again since some leaf nodes changed 107 tree.condense(); 108 } 109 110 return tree; 111 } 112 113 /** Internal method to insert a partition into the tree. 114 * @param partition partition to insert 115 * @throws IllegalStateException if a boundary has previously been inserted 116 */ 117 protected void insertPartitionInternal(final HyperplaneConvexSubset<P> partition) { 118 ensureInsertingPartitions(); 119 120 tree.insert(partition, RegionCutRule.INHERIT); 121 } 122 123 /** Internal method to insert a region boundary into the tree. 124 * @param boundary boundary to insert 125 */ 126 protected void insertBoundaryInternal(final HyperplaneConvexSubset<P> boundary) { 127 if (insertingPartitions) { 128 // switch to inserting boundaries; place all current internal nodes into 129 // a set for easy identification 130 for (final N node : tree.nodes()) { 131 if (node.isInternal()) { 132 partitionNodes.add(node); 133 } 134 } 135 136 insertingPartitions = false; 137 } 138 139 insertBoundaryRecursive(tree.getRoot(), boundary, boundary.getHyperplane().span(), 140 (leaf, cut) -> tree.setNodeCut(leaf, cut, subtreeInit)); 141 } 142 143 /** Insert a region boundary into the tree. 144 * @param node node to insert into 145 * @param insert the hyperplane convex subset to insert 146 * @param trimmed version of the hyperplane convex subset filling the entire space of {@code node} 147 * @param leafFn function to apply to leaf nodes 148 */ 149 private void insertBoundaryRecursive(final N node, final HyperplaneConvexSubset<P> insert, 150 final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) { 151 if (node.isLeaf()) { 152 leafFn.accept(node, trimmed); 153 } else { 154 insertBoundaryRecursiveInternalNode(node, insert, trimmed, leafFn); 155 } 156 } 157 158 /** Recursive boundary insertion method for internal nodes. 159 * @param node node to insert into 160 * @param insert the hyperplane convex subset to insert 161 * @param trimmed version of the hyperplane convex subset filling the entire space of {@code node} 162 * @param leafFn function to apply to leaf nodes 163 * @see #insertBoundaryRecursive(AbstractRegionNode, HyperplaneConvexSubset, HyperplaneConvexSubset, BiConsumer) 164 */ 165 private void insertBoundaryRecursiveInternalNode(final N node, final HyperplaneConvexSubset<P> insert, 166 final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) { 167 168 final Split<? extends HyperplaneConvexSubset<P>> insertSplit = 169 insert.split(node.getCutHyperplane()); 170 171 final HyperplaneConvexSubset<P> minus = insertSplit.getMinus(); 172 final HyperplaneConvexSubset<P> plus = insertSplit.getPlus(); 173 174 if (minus == null && plus == null && isPartitionNode(node)) { 175 // the inserted boundary lies directly on a partition; proceed down the tree with the 176 // rest of the insertion algorithm but instead of cutting the final leaf nodes, just 177 // set the location 178 179 // remove this node from the set of partition nodes since this is now a boundary cut 180 partitionNodes.remove(node); 181 182 final boolean sameOrientation = node.getCutHyperplane().similarOrientation(insert.getHyperplane()); 183 final N insertMinus = sameOrientation ? node.getMinus() : node.getPlus(); 184 final N insertPlus = sameOrientation ? node.getPlus() : node.getMinus(); 185 186 insertBoundaryRecursive(insertMinus, insert, trimmed, 187 (leaf, cut) -> leaf.setLocation(RegionLocation.INSIDE)); 188 189 insertBoundaryRecursive(insertPlus, insert, trimmed, 190 (leaf, cut) -> leaf.setLocation(RegionLocation.OUTSIDE)); 191 192 } else if (minus != null || plus != null) { 193 final Split<? extends HyperplaneConvexSubset<P>> trimmedSplit = 194 trimmed.split(node.getCutHyperplane()); 195 196 final HyperplaneConvexSubset<P> trimmedMinus = trimmedSplit.getMinus(); 197 final HyperplaneConvexSubset<P> trimmedPlus = trimmedSplit.getPlus(); 198 199 if (minus != null) { 200 insertBoundaryRecursive(node.getMinus(), minus, trimmedMinus, leafFn); 201 } 202 if (plus != null) { 203 insertBoundaryRecursive(node.getPlus(), plus, trimmedPlus, leafFn); 204 } 205 } 206 } 207 208 /** Propagate the region interior to partitioned leaf nodes that have not had a boundary 209 * inserted. 210 * @return true if any nodes were changed 211 */ 212 private boolean propagateRegionInterior() { 213 final List<N> outsidePartitionedLeaves = getOutsidePartitionedLeaves(); 214 outsidePartitionedLeaves.sort(DEEPEST_FIRST_ORDER); 215 216 int changeCount = 0; 217 218 N parent; 219 N sibling; 220 for (final N leaf : outsidePartitionedLeaves) { 221 parent = leaf.getParent(); 222 223 // check if the parent cut touches the inside anywhere on the side opposite of 224 // this leaf; if so, then this node should also be inside 225 sibling = leaf.isMinus() ? 226 parent.getPlus() : 227 parent.getMinus(); 228 229 if (touchesInside(parent.getCut(), sibling)) { 230 leaf.setLocation(RegionLocation.INSIDE); 231 232 ++changeCount; 233 } 234 } 235 236 return changeCount > 0; 237 } 238 239 /** Return a list containing all outside leaf nodes that have a parent marked as a partition node. 240 * @return a list containing all outside leaf nodes that have a parent marked as a partition node 241 */ 242 private List<N> getOutsidePartitionedLeaves() { 243 final List<N> result = new ArrayList<>(); 244 245 final N root = tree.getRoot(); 246 collectOutsidePartitionedLeavesRecursive(root, false, result); 247 248 return result; 249 } 250 251 /** Recursively collect all outside leaf nodes that have a parent marked as a partition node. 252 * @param node root of the subtree to collect nodes from 253 * @param parentIsPartitionNode true if the parent of {@code node} is a partition node 254 * @param result list of accumulated results 255 */ 256 private void collectOutsidePartitionedLeavesRecursive(final N node, final boolean parentIsPartitionNode, 257 final List<N> result) { 258 if (node != null) { 259 if (parentIsPartitionNode && node.isOutside()) { 260 result.add(node); 261 } 262 263 final boolean partitionNode = isPartitionNode(node); 264 265 collectOutsidePartitionedLeavesRecursive(node.getMinus(), partitionNode, result); 266 collectOutsidePartitionedLeavesRecursive(node.getPlus(), partitionNode, result); 267 } 268 } 269 270 /** Return true if {@code sub} touches an inside leaf node anywhere in the subtree rooted at {@code node}. 271 * @param sub convex subset to check 272 * @param node root node of the subtree to test against 273 * @return true if {@code sub} touches an inside leaf node anywhere in the subtree rooted at {@code node} 274 */ 275 private boolean touchesInside(final HyperplaneConvexSubset<P> sub, final N node) { 276 if (sub != null) { 277 if (node.isLeaf()) { 278 return node.isInside(); 279 } else { 280 final Split<? extends HyperplaneConvexSubset<P>> split = sub.split(node.getCutHyperplane()); 281 282 return touchesInside(split.getMinus(), node.getMinus()) || 283 touchesInside(split.getPlus(), node.getPlus()); 284 285 } 286 } 287 288 return false; 289 } 290 291 /** Return true if the given node is marked as a partition node. 292 * @param node node to check 293 * @return true if the given node is marked as a partition node 294 */ 295 private boolean isPartitionNode(final N node) { 296 return partitionNodes.contains(node); 297 } 298 299 /** Throw an exception if the instance is no longer accepting partitions. 300 * @throws IllegalStateException if the instance is no longer accepting partitions 301 */ 302 private void ensureInsertingPartitions() { 303 if (!insertingPartitions) { 304 throw new IllegalStateException("Cannot insert partitions after boundaries have been inserted"); 305 } 306 } 307}