home | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Java example source code file (BSPTree.java)

This example Java source code file (BSPTree.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

bsptree, bsptreevisitor, deprecated, hyperplane, leafmerger, list, minus, minus_sub_plus, object, point, space, sub_minus_plus, subhyperplane, util, vanishingcuthandler

The BSPTree.java Java example source code

/*
 * 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 not 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 plus, final BSPTree 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 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 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 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 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 getCloseCuts(final Point point, final double maxOffset) {
        final List<BSPTree close = new ArrayList>();
        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 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 such copy is done here!

* <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 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 tree, final LeafMerger 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 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 tree, final LeafMerger 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 leaf, BSPTree tree, BSPTree 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 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 * 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 sub) { if (cut == null) { return new BSPTree<S>(sub, copySelf(), new BSPTree(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 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(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(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 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 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; } } } }

Other Java examples (source code examples)

Here is a short list of links related to this Java BSPTree.java source code file:



my book on functional programming

 

new blog posts

 

Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.