diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java')
| -rw-r--r-- | src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java | 821 |
1 files changed, 821 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java new file mode 100644 index 0000000..1f1a6ea --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java @@ -0,0 +1,821 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.geometry.partitioning; + +import java.util.ArrayList; +import java.util.List; + +import org.apache.commons.math3.exception.MathIllegalStateException; +import org.apache.commons.math3.exception.MathInternalError; +import org.apache.commons.math3.exception.util.LocalizedFormats; +import org.apache.commons.math3.geometry.Point; +import org.apache.commons.math3.geometry.Space; +import org.apache.commons.math3.geometry.Vector; +import org.apache.commons.math3.util.FastMath; + +/** This class represent a Binary Space Partition tree. + + * <p>BSP trees are an efficient way to represent space partitions and + * to associate attributes with each cell. Each node in a BSP tree + * represents a convex region which is partitioned in two convex + * sub-regions at each side of a cut hyperplane. The root tree + * contains the complete space.</p> + + * <p>The main use of such partitions is to use a boolean attribute to + * define an inside/outside property, hence representing arbitrary + * polytopes (line segments in 1D, polygons in 2D and polyhedrons in + * 3D) and to operate on them.</p> + + * <p>Another example would be to represent Voronoi tesselations, the + * attribute of each cell holding the defining point of the cell.</p> + + * <p>The application-defined attributes are shared among copied + * instances and propagated to split parts. These attributes are not + * used by the BSP-tree algorithms themselves, so the application can + * use them for any purpose. Since the tree visiting method holds + * internal and leaf nodes differently, it is possible to use + * different classes for internal nodes attributes and leaf nodes + * attributes. This should be used with care, though, because if the + * tree is modified in any way after attributes have been set, some + * internal nodes may become leaf nodes and some leaf nodes may become + * internal nodes.</p> + + * <p>One of the main sources for the development of this package was + * Bruce Naylor, John Amanatides and William Thibault paper <a + * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging + * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90, + * Computer Graphics 24(4), August 1990, pp 115-124, published by the + * Association for Computing Machinery (ACM).</p> + + * @param <S> Type of the space. + + * @since 3.0 + */ +public class BSPTree<S extends Space> { + + /** Cut sub-hyperplane. */ + private SubHyperplane<S> cut; + + /** Tree at the plus side of the cut hyperplane. */ + private BSPTree<S> plus; + + /** Tree at the minus side of the cut hyperplane. */ + private BSPTree<S> minus; + + /** Parent tree. */ + private BSPTree<S> parent; + + /** Application-defined attribute. */ + private Object attribute; + + /** Build a tree having only one root cell representing the whole space. + */ + public BSPTree() { + cut = null; + plus = null; + minus = null; + parent = null; + attribute = null; + } + + /** Build a tree having only one root cell representing the whole space. + * @param attribute attribute of the tree (may be null) + */ + public BSPTree(final Object attribute) { + cut = null; + plus = null; + minus = null; + parent = null; + this.attribute = attribute; + } + + /** Build a BSPTree from its underlying elements. + * <p>This method does <em>not</em> perform any verification on + * consistency of its arguments, it should therefore be used only + * when then caller knows what it is doing.</p> + * <p>This method is mainly useful to build trees + * bottom-up. Building trees top-down is realized with the help of + * method {@link #insertCut insertCut}.</p> + * @param cut cut sub-hyperplane for the tree + * @param plus plus side sub-tree + * @param minus minus side sub-tree + * @param attribute attribute associated with the node (may be null) + * @see #insertCut + */ + public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus, + final Object attribute) { + this.cut = cut; + this.plus = plus; + this.minus = minus; + this.parent = null; + this.attribute = attribute; + plus.parent = this; + minus.parent = this; + } + + /** Insert a cut sub-hyperplane in a node. + * <p>The sub-tree starting at this node will be completely + * overwritten. The new cut sub-hyperplane will be built from the + * intersection of the provided hyperplane with the cell. If the + * hyperplane does intersect the cell, the cell will have two + * children cells with {@code null} attributes on each side of + * the inserted cut sub-hyperplane. If the hyperplane does not + * intersect the cell then <em>no</em> cut hyperplane will be + * inserted and the cell will be changed to a leaf cell. The + * attribute of the node is never changed.</p> + * <p>This method is mainly useful when called on leaf nodes + * (i.e. nodes for which {@link #getCut getCut} returns + * {@code null}), in this case it provides a way to build a + * tree top-down (whereas the {@link #BSPTree(SubHyperplane, + * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to + * build trees bottom-up).</p> + * @param hyperplane hyperplane to insert, it will be chopped in + * order to fit in the cell defined by the parent nodes of the + * instance + * @return true if a cut sub-hyperplane has been inserted (i.e. if + * the cell now has two leaf child nodes) + * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object) + */ + public boolean insertCut(final Hyperplane<S> hyperplane) { + + if (cut != null) { + plus.parent = null; + minus.parent = null; + } + + final SubHyperplane<S> chopped = fitToCell(hyperplane.wholeHyperplane()); + if (chopped == null || chopped.isEmpty()) { + cut = null; + plus = null; + minus = null; + return false; + } + + cut = chopped; + plus = new BSPTree<S>(); + plus.parent = this; + minus = new BSPTree<S>(); + minus.parent = this; + return true; + + } + + /** Copy the instance. + * <p>The instance created is completely independent of the original + * one. A deep copy is used, none of the underlying objects are + * shared (except for the nodes attributes and immutable + * objects).</p> + * @return a new tree, copy of the instance + */ + public BSPTree<S> copySelf() { + + if (cut == null) { + return new BSPTree<S>(attribute); + } + + return new BSPTree<S>(cut.copySelf(), plus.copySelf(), minus.copySelf(), + attribute); + + } + + /** Get the cut sub-hyperplane. + * @return cut sub-hyperplane, null if this is a leaf tree + */ + public SubHyperplane<S> getCut() { + return cut; + } + + /** Get the tree on the plus side of the cut hyperplane. + * @return tree on the plus side of the cut hyperplane, null if this + * is a leaf tree + */ + public BSPTree<S> getPlus() { + return plus; + } + + /** Get the tree on the minus side of the cut hyperplane. + * @return tree on the minus side of the cut hyperplane, null if this + * is a leaf tree + */ + public BSPTree<S> getMinus() { + return minus; + } + + /** Get the parent node. + * @return parent node, null if the node has no parents + */ + public BSPTree<S> getParent() { + return parent; + } + + /** Associate an attribute with the instance. + * @param attribute attribute to associate with the node + * @see #getAttribute + */ + public void setAttribute(final Object attribute) { + this.attribute = attribute; + } + + /** Get the attribute associated with the instance. + * @return attribute associated with the node or null if no + * attribute has been explicitly set using the {@link #setAttribute + * setAttribute} method + * @see #setAttribute + */ + public Object getAttribute() { + return attribute; + } + + /** Visit the BSP tree nodes. + * @param visitor object visiting the tree nodes + */ + public void visit(final BSPTreeVisitor<S> visitor) { + if (cut == null) { + visitor.visitLeafNode(this); + } else { + switch (visitor.visitOrder(this)) { + case PLUS_MINUS_SUB: + plus.visit(visitor); + minus.visit(visitor); + visitor.visitInternalNode(this); + break; + case PLUS_SUB_MINUS: + plus.visit(visitor); + visitor.visitInternalNode(this); + minus.visit(visitor); + break; + case MINUS_PLUS_SUB: + minus.visit(visitor); + plus.visit(visitor); + visitor.visitInternalNode(this); + break; + case MINUS_SUB_PLUS: + minus.visit(visitor); + visitor.visitInternalNode(this); + plus.visit(visitor); + break; + case SUB_PLUS_MINUS: + visitor.visitInternalNode(this); + plus.visit(visitor); + minus.visit(visitor); + break; + case SUB_MINUS_PLUS: + visitor.visitInternalNode(this); + minus.visit(visitor); + plus.visit(visitor); + break; + default: + throw new MathInternalError(); + } + + } + } + + /** Fit a sub-hyperplane inside the cell defined by the instance. + * <p>Fitting is done by chopping off the parts of the + * sub-hyperplane that lie outside of the cell using the + * cut-hyperplanes of the parent nodes of the instance.</p> + * @param sub sub-hyperplane to fit + * @return a new sub-hyperplane, guaranteed to have no part outside + * of the instance cell + */ + private SubHyperplane<S> fitToCell(final SubHyperplane<S> sub) { + SubHyperplane<S> s = sub; + for (BSPTree<S> tree = this; tree.parent != null && s != null; tree = tree.parent) { + if (tree == tree.parent.plus) { + s = s.split(tree.parent.cut.getHyperplane()).getPlus(); + } else { + s = s.split(tree.parent.cut.getHyperplane()).getMinus(); + } + } + return s; + } + + /** Get the cell to which a point belongs. + * <p>If the returned cell is a leaf node the points belongs to the + * interior of the node, if the cell is an internal node the points + * belongs to the node cut sub-hyperplane.</p> + * @param point point to check + * @return the tree cell to which the point belongs + * @deprecated as of 3.3, replaced with {@link #getCell(Point, double)} + */ + @Deprecated + public BSPTree<S> getCell(final Vector<S> point) { + return getCell((Point<S>) point, 1.0e-10); + } + + /** Get the cell to which a point belongs. + * <p>If the returned cell is a leaf node the points belongs to the + * interior of the node, if the cell is an internal node the points + * belongs to the node cut sub-hyperplane.</p> + * @param point point to check + * @param tolerance tolerance below which points close to a cut hyperplane + * are considered to belong to the hyperplane itself + * @return the tree cell to which the point belongs + */ + public BSPTree<S> getCell(final Point<S> point, final double tolerance) { + + if (cut == null) { + return this; + } + + // position of the point with respect to the cut hyperplane + final double offset = cut.getHyperplane().getOffset(point); + + if (FastMath.abs(offset) < tolerance) { + return this; + } else if (offset <= 0) { + // point is on the minus side of the cut hyperplane + return minus.getCell(point, tolerance); + } else { + // point is on the plus side of the cut hyperplane + return plus.getCell(point, tolerance); + } + + } + + /** Get the cells whose cut sub-hyperplanes are close to the point. + * @param point point to check + * @param maxOffset offset below which a cut sub-hyperplane is considered + * close to the point (in absolute value) + * @return close cells (may be empty if all cut sub-hyperplanes are farther + * than maxOffset from the point) + */ + public List<BSPTree<S>> getCloseCuts(final Point<S> point, final double maxOffset) { + final List<BSPTree<S>> close = new ArrayList<BSPTree<S>>(); + recurseCloseCuts(point, maxOffset, close); + return close; + } + + /** Get the cells whose cut sub-hyperplanes are close to the point. + * @param point point to check + * @param maxOffset offset below which a cut sub-hyperplane is considered + * close to the point (in absolute value) + * @param close list to fill + */ + private void recurseCloseCuts(final Point<S> point, final double maxOffset, + final List<BSPTree<S>> close) { + if (cut != null) { + + // position of the point with respect to the cut hyperplane + final double offset = cut.getHyperplane().getOffset(point); + + if (offset < -maxOffset) { + // point is on the minus side of the cut hyperplane + minus.recurseCloseCuts(point, maxOffset, close); + } else if (offset > maxOffset) { + // point is on the plus side of the cut hyperplane + plus.recurseCloseCuts(point, maxOffset, close); + } else { + // point is close to the cut hyperplane + close.add(this); + minus.recurseCloseCuts(point, maxOffset, close); + plus.recurseCloseCuts(point, maxOffset, close); + } + + } + } + + /** Perform condensation on a tree. + * <p>The condensation operation is not recursive, it must be called + * explicitly from leaves to root.</p> + */ + private void condense() { + if ((cut != null) && (plus.cut == null) && (minus.cut == null) && + (((plus.attribute == null) && (minus.attribute == null)) || + ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) { + attribute = (plus.attribute == null) ? minus.attribute : plus.attribute; + cut = null; + plus = null; + minus = null; + } + } + + /** Merge a BSP tree with the instance. + * <p>All trees are modified (parts of them are reused in the new + * tree), it is the responsibility of the caller to ensure a copy + * has been done before if any of the former tree should be + * preserved, <em>no</em> such copy is done here!</p> + * <p>The algorithm used here is directly derived from the one + * described in the Naylor, Amanatides and Thibault paper (section + * III, Binary Partitioning of a BSP Tree).</p> + * @param tree other tree to merge with the instance (will be + * <em>unusable</em> after the operation, as well as the + * instance itself) + * @param leafMerger object implementing the final merging phase + * (this is where the semantic of the operation occurs, generally + * depending on the attribute of the leaf node) + * @return a new tree, result of <code>instance <op> + * tree</code>, this value can be ignored if parentTree is not null + * since all connections have already been established + */ + public BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger) { + return merge(tree, leafMerger, null, false); + } + + /** Merge a BSP tree with the instance. + * @param tree other tree to merge with the instance (will be + * <em>unusable</em> after the operation, as well as the + * instance itself) + * @param leafMerger object implementing the final merging phase + * (this is where the semantic of the operation occurs, generally + * depending on the attribute of the leaf node) + * @param parentTree parent tree to connect to (may be null) + * @param isPlusChild if true and if parentTree is not null, the + * resulting tree should be the plus child of its parent, ignored if + * parentTree is null + * @return a new tree, result of <code>instance <op> + * tree</code>, this value can be ignored if parentTree is not null + * since all connections have already been established + */ + private BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger, + final BSPTree<S> parentTree, final boolean isPlusChild) { + if (cut == null) { + // cell/tree operation + return leafMerger.merge(this, tree, parentTree, isPlusChild, true); + } else if (tree.cut == null) { + // tree/cell operation + return leafMerger.merge(tree, this, parentTree, isPlusChild, false); + } else { + // tree/tree operation + final BSPTree<S> merged = tree.split(cut); + if (parentTree != null) { + merged.parent = parentTree; + if (isPlusChild) { + parentTree.plus = merged; + } else { + parentTree.minus = merged; + } + } + + // merging phase + plus.merge(merged.plus, leafMerger, merged, true); + minus.merge(merged.minus, leafMerger, merged, false); + merged.condense(); + if (merged.cut != null) { + merged.cut = merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane()); + } + + return merged; + + } + } + + /** This interface gather the merging operations between a BSP tree + * leaf and another BSP tree. + * <p>As explained in Bruce Naylor, John Amanatides and William + * Thibault paper <a + * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging + * BSP Trees Yields Polyhedral Set Operations</a>, + * the operations on {@link BSPTree BSP trees} can be expressed as a + * generic recursive merging operation where only the final part, + * when one of the operand is a leaf, is specific to the real + * operation semantics. For example, a tree representing a region + * using a boolean attribute to identify inside cells and outside + * cells would use four different objects to implement the final + * merging phase of the four set operations union, intersection, + * difference and symmetric difference (exclusive or).</p> + * @param <S> Type of the space. + */ + public interface LeafMerger<S extends Space> { + + /** Merge a leaf node and a tree node. + * <p>This method is called at the end of a recursive merging + * resulting from a {@code tree1.merge(tree2, leafMerger)} + * call, when one of the sub-trees involved is a leaf (i.e. when + * its cut-hyperplane is null). This is the only place where the + * precise semantics of the operation are required. For all upper + * level nodes in the tree, the merging operation is only a + * generic partitioning algorithm.</p> + * <p>Since the final operation may be non-commutative, it is + * important to know if the leaf node comes from the instance tree + * ({@code tree1}) or the argument tree + * ({@code tree2}). The third argument of the method is + * devoted to this. It can be ignored for commutative + * operations.</p> + * <p>The {@link BSPTree#insertInTree BSPTree.insertInTree} method + * may be useful to implement this method.</p> + * @param leaf leaf node (its cut hyperplane is guaranteed to be + * null) + * @param tree tree node (its cut hyperplane may be null or not) + * @param parentTree parent tree to connect to (may be null) + * @param isPlusChild if true and if parentTree is not null, the + * resulting tree should be the plus child of its parent, ignored if + * parentTree is null + * @param leafFromInstance if true, the leaf node comes from the + * instance tree ({@code tree1}) and the tree node comes from + * the argument tree ({@code tree2}) + * @return the BSP tree resulting from the merging (may be one of + * the arguments) + */ + BSPTree<S> merge(BSPTree<S> leaf, BSPTree<S> tree, BSPTree<S> parentTree, + boolean isPlusChild, boolean leafFromInstance); + + } + + /** This interface handles the corner cases when an internal node cut sub-hyperplane vanishes. + * <p> + * Such cases happens for example when a cut sub-hyperplane is inserted into + * another tree (during a merge operation), and is split in several parts, + * some of which becomes smaller than the tolerance. The corresponding node + * as then no cut sub-hyperplane anymore, but does have children. This interface + * specifies how to handle this situation. + * setting + * </p> + * @param <S> Type of the space. + * @since 3.4 + */ + public interface VanishingCutHandler<S extends Space> { + + /** Fix a node with both vanished cut and children. + * @param node node to fix + * @return fixed node + */ + BSPTree<S> fixNode(BSPTree<S> node); + + } + + /** Split a BSP tree by an external sub-hyperplane. + * <p>Split a tree in two halves, on each side of the + * sub-hyperplane. The instance is not modified.</p> + * <p>The tree returned is not upward-consistent: despite all of its + * sub-trees cut sub-hyperplanes (including its own cut + * sub-hyperplane) are bounded to the current cell, it is <em>not</em> + * attached to any parent tree yet. This tree is intended to be + * later inserted into an higher level tree.</p> + * <p>The algorithm used here is the one given in Naylor, Amanatides + * and Thibault paper (section III, Binary Partitioning of a BSP + * Tree).</p> + * @param sub partitioning sub-hyperplane, must be already clipped + * to the convex region represented by the instance, will be used as + * the cut sub-hyperplane of the returned tree + * @return a tree having the specified sub-hyperplane as its cut + * sub-hyperplane, the two parts of the split instance as its two + * sub-trees and a null parent + */ + public BSPTree<S> split(final SubHyperplane<S> sub) { + + if (cut == null) { + return new BSPTree<S>(sub, copySelf(), new BSPTree<S>(attribute), null); + } + + final Hyperplane<S> cHyperplane = cut.getHyperplane(); + final Hyperplane<S> sHyperplane = sub.getHyperplane(); + final SubHyperplane.SplitSubHyperplane<S> subParts = sub.split(cHyperplane); + switch (subParts.getSide()) { + case PLUS : + { // the partitioning sub-hyperplane is entirely in the plus sub-tree + final BSPTree<S> split = plus.split(sub); + if (cut.split(sHyperplane).getSide() == Side.PLUS) { + split.plus = + new BSPTree<S>(cut.copySelf(), split.plus, minus.copySelf(), attribute); + split.plus.condense(); + split.plus.parent = split; + } else { + split.minus = + new BSPTree<S>(cut.copySelf(), split.minus, minus.copySelf(), attribute); + split.minus.condense(); + split.minus.parent = split; + } + return split; + } + case MINUS : + { // the partitioning sub-hyperplane is entirely in the minus sub-tree + final BSPTree<S> split = minus.split(sub); + if (cut.split(sHyperplane).getSide() == Side.PLUS) { + split.plus = + new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.plus, attribute); + split.plus.condense(); + split.plus.parent = split; + } else { + split.minus = + new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.minus, attribute); + split.minus.condense(); + split.minus.parent = split; + } + return split; + } + case BOTH : + { + final SubHyperplane.SplitSubHyperplane<S> cutParts = cut.split(sHyperplane); + final BSPTree<S> split = + new BSPTree<S>(sub, plus.split(subParts.getPlus()), minus.split(subParts.getMinus()), + null); + split.plus.cut = cutParts.getPlus(); + split.minus.cut = cutParts.getMinus(); + final BSPTree<S> tmp = split.plus.minus; + split.plus.minus = split.minus.plus; + split.plus.minus.parent = split.plus; + split.minus.plus = tmp; + split.minus.plus.parent = split.minus; + split.plus.condense(); + split.minus.condense(); + return split; + } + default : + return cHyperplane.sameOrientationAs(sHyperplane) ? + new BSPTree<S>(sub, plus.copySelf(), minus.copySelf(), attribute) : + new BSPTree<S>(sub, minus.copySelf(), plus.copySelf(), attribute); + } + + } + + /** Insert the instance into another tree. + * <p>The instance itself is modified so its former parent should + * not be used anymore.</p> + * @param parentTree parent tree to connect to (may be null) + * @param isPlusChild if true and if parentTree is not null, the + * resulting tree should be the plus child of its parent, ignored if + * parentTree is null + * @see LeafMerger + * @deprecated as of 3.4, replaced with {@link #insertInTree(BSPTree, boolean, VanishingCutHandler)} + */ + @Deprecated + public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) { + insertInTree(parentTree, isPlusChild, new VanishingCutHandler<S>() { + /** {@inheritDoc} */ + public BSPTree<S> fixNode(BSPTree<S> node) { + // the cut should not be null + throw new MathIllegalStateException(LocalizedFormats.NULL_NOT_ALLOWED); + } + }); + } + + /** Insert the instance into another tree. + * <p>The instance itself is modified so its former parent should + * not be used anymore.</p> + * @param parentTree parent tree to connect to (may be null) + * @param isPlusChild if true and if parentTree is not null, the + * resulting tree should be the plus child of its parent, ignored if + * parentTree is null + * @param vanishingHandler handler to use for handling very rare corner + * cases of vanishing cut sub-hyperplanes in internal nodes during merging + * @see LeafMerger + * @since 3.4 + */ + public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild, + final VanishingCutHandler<S> vanishingHandler) { + + // set up parent/child links + parent = parentTree; + if (parentTree != null) { + if (isPlusChild) { + parentTree.plus = this; + } else { + parentTree.minus = this; + } + } + + // make sure the inserted tree lies in the cell defined by its parent nodes + if (cut != null) { + + // explore the parent nodes from here towards tree root + for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) { + + // this is an hyperplane of some parent node + final Hyperplane<S> hyperplane = tree.parent.cut.getHyperplane(); + + // chop off the parts of the inserted tree that extend + // on the wrong side of this parent hyperplane + if (tree == tree.parent.plus) { + cut = cut.split(hyperplane).getPlus(); + plus.chopOffMinus(hyperplane, vanishingHandler); + minus.chopOffMinus(hyperplane, vanishingHandler); + } else { + cut = cut.split(hyperplane).getMinus(); + plus.chopOffPlus(hyperplane, vanishingHandler); + minus.chopOffPlus(hyperplane, vanishingHandler); + } + + if (cut == null) { + // the cut sub-hyperplane has vanished + final BSPTree<S> fixed = vanishingHandler.fixNode(this); + cut = fixed.cut; + plus = fixed.plus; + minus = fixed.minus; + attribute = fixed.attribute; + if (cut == null) { + break; + } + } + + } + + // since we may have drop some parts of the inserted tree, + // perform a condensation pass to keep the tree structure simple + condense(); + + } + + } + + /** Prune a tree around a cell. + * <p> + * This method can be used to extract a convex cell from a tree. + * The original cell may either be a leaf node or an internal node. + * If it is an internal node, it's subtree will be ignored (i.e. the + * extracted cell will be a leaf node in all cases). The original + * tree to which the original cell belongs is not touched at all, + * a new independent tree will be built. + * </p> + * @param cellAttribute attribute to set for the leaf node + * corresponding to the initial instance cell + * @param otherLeafsAttributes attribute to set for the other leaf + * nodes + * @param internalAttributes attribute to set for the internal nodes + * @return a new tree (the original tree is left untouched) containing + * a single branch with the cell as a leaf node, and other leaf nodes + * as the remnants of the pruned branches + * @since 3.3 + */ + public BSPTree<S> pruneAroundConvexCell(final Object cellAttribute, + final Object otherLeafsAttributes, + final Object internalAttributes) { + + // build the current cell leaf + BSPTree<S> tree = new BSPTree<S>(cellAttribute); + + // build the pruned tree bottom-up + for (BSPTree<S> current = this; current.parent != null; current = current.parent) { + final SubHyperplane<S> parentCut = current.parent.cut.copySelf(); + final BSPTree<S> sibling = new BSPTree<S>(otherLeafsAttributes); + if (current == current.parent.plus) { + tree = new BSPTree<S>(parentCut, tree, sibling, internalAttributes); + } else { + tree = new BSPTree<S>(parentCut, sibling, tree, internalAttributes); + } + } + + return tree; + + } + + /** Chop off parts of the tree. + * <p>The instance is modified in place, all the parts that are on + * the minus side of the chopping hyperplane are discarded, only the + * parts on the plus side remain.</p> + * @param hyperplane chopping hyperplane + * @param vanishingHandler handler to use for handling very rare corner + * cases of vanishing cut sub-hyperplanes in internal nodes during merging + */ + private void chopOffMinus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) { + if (cut != null) { + + cut = cut.split(hyperplane).getPlus(); + plus.chopOffMinus(hyperplane, vanishingHandler); + minus.chopOffMinus(hyperplane, vanishingHandler); + + if (cut == null) { + // the cut sub-hyperplane has vanished + final BSPTree<S> fixed = vanishingHandler.fixNode(this); + cut = fixed.cut; + plus = fixed.plus; + minus = fixed.minus; + attribute = fixed.attribute; + } + + } + } + + /** Chop off parts of the tree. + * <p>The instance is modified in place, all the parts that are on + * the plus side of the chopping hyperplane are discarded, only the + * parts on the minus side remain.</p> + * @param hyperplane chopping hyperplane + * @param vanishingHandler handler to use for handling very rare corner + * cases of vanishing cut sub-hyperplanes in internal nodes during merging + */ + private void chopOffPlus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) { + if (cut != null) { + + cut = cut.split(hyperplane).getMinus(); + plus.chopOffPlus(hyperplane, vanishingHandler); + minus.chopOffPlus(hyperplane, vanishingHandler); + + if (cut == null) { + // the cut sub-hyperplane has vanished + final BSPTree<S> fixed = vanishingHandler.fixNode(this); + cut = fixed.cut; + plus = fixed.plus; + minus = fixed.minus; + attribute = fixed.attribute; + } + + } + } + +} |