http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java ---------------------------------------------------------------------- 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 deleted file mode 100644 index 26ae45f..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java +++ /dev/null @@ -1,817 +0,0 @@ -/* - * 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> - * @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(); - switch (sub.side(cHyperplane)) { - case PLUS : - { // the partitioning sub-hyperplane is entirely in the plus sub-tree - final BSPTree<S> split = plus.split(sub); - if (cut.side(sHyperplane) == 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.side(sHyperplane) == 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 SubHyperplane.SplitSubHyperplane<S> subParts = sub.split(cHyperplane); - 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; - } - - } - - // 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; - } - - } - } - -}
http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTreeVisitor.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTreeVisitor.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTreeVisitor.java deleted file mode 100644 index 3d09939..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTreeVisitor.java +++ /dev/null @@ -1,114 +0,0 @@ -/* - * 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 org.apache.commons.math3.geometry.Space; - -/** This interface is used to visit {@link BSPTree BSP tree} nodes. - - * <p>Navigation through {@link BSPTree BSP trees} can be done using - * two different point of views:</p> - * <ul> - * <li> - * the first one is in a node-oriented way using the {@link - * BSPTree#getPlus}, {@link BSPTree#getMinus} and {@link - * BSPTree#getParent} methods. Terminal nodes without associated - * {@link SubHyperplane sub-hyperplanes} can be visited this way, - * there is no constraint in the visit order, and it is possible - * to visit either all nodes or only a subset of the nodes - * </li> - * <li> - * the second one is in a sub-hyperplane-oriented way using - * classes implementing this interface which obeys the visitor - * design pattern. The visit order is provided by the visitor as - * each node is first encountered. Each node is visited exactly - * once. - * </li> - * </ul> - - * @param <S> Type of the space. - - * @see BSPTree - * @see SubHyperplane - - * @since 3.0 - */ -public interface BSPTreeVisitor<S extends Space> { - - /** Enumerate for visit order with respect to plus sub-tree, minus sub-tree and cut sub-hyperplane. */ - enum Order { - /** Indicator for visit order plus sub-tree, then minus sub-tree, - * and last cut sub-hyperplane. - */ - PLUS_MINUS_SUB, - - /** Indicator for visit order plus sub-tree, then cut sub-hyperplane, - * and last minus sub-tree. - */ - PLUS_SUB_MINUS, - - /** Indicator for visit order minus sub-tree, then plus sub-tree, - * and last cut sub-hyperplane. - */ - MINUS_PLUS_SUB, - - /** Indicator for visit order minus sub-tree, then cut sub-hyperplane, - * and last plus sub-tree. - */ - MINUS_SUB_PLUS, - - /** Indicator for visit order cut sub-hyperplane, then plus sub-tree, - * and last minus sub-tree. - */ - SUB_PLUS_MINUS, - - /** Indicator for visit order cut sub-hyperplane, then minus sub-tree, - * and last plus sub-tree. - */ - SUB_MINUS_PLUS; - } - - /** Determine the visit order for this node. - * <p>Before attempting to visit an internal node, this method is - * called to determine the desired ordering of the visit. It is - * guaranteed that this method will be called before {@link - * #visitInternalNode visitInternalNode} for a given node, it will be - * called exactly once for each internal node.</p> - * @param node BSP node guaranteed to have a non null cut sub-hyperplane - * @return desired visit order, must be one of - * {@link Order#PLUS_MINUS_SUB}, {@link Order#PLUS_SUB_MINUS}, - * {@link Order#MINUS_PLUS_SUB}, {@link Order#MINUS_SUB_PLUS}, - * {@link Order#SUB_PLUS_MINUS}, {@link Order#SUB_MINUS_PLUS} - */ - Order visitOrder(BSPTree<S> node); - - /** Visit a BSP tree node node having a non-null sub-hyperplane. - * <p>It is guaranteed that this method will be called after {@link - * #visitOrder visitOrder} has been called for a given node, - * it wil be called exactly once for each internal node.</p> - * @param node BSP node guaranteed to have a non null cut sub-hyperplane - * @see #visitLeafNode - */ - void visitInternalNode(BSPTree<S> node); - - /** Visit a leaf BSP tree node node having a null sub-hyperplane. - * @param node leaf BSP node having a null sub-hyperplane - * @see #visitInternalNode - */ - void visitLeafNode(BSPTree<S> node); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java deleted file mode 100644 index dad884c..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java +++ /dev/null @@ -1,116 +0,0 @@ -/* - * 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 org.apache.commons.math3.geometry.Space; - -/** Class holding boundary attributes. - * <p>This class is used for the attributes associated with the - * nodes of region boundary shell trees returned by the {@link - * Region#getTree(boolean) Region.getTree(includeBoundaryAttributes)} - * when the boolean {@code includeBoundaryAttributes} parameter is - * set to {@code true}. It contains the parts of the node cut - * sub-hyperplane that belong to the boundary.</p> - * <p>This class is a simple placeholder, it does not provide any - * processing methods.</p> - * @param <S> Type of the space. - * @see Region#getTree - * @since 3.0 - */ -public class BoundaryAttribute<S extends Space> { - - /** Part of the node cut sub-hyperplane that belongs to the - * boundary and has the outside of the region on the plus side of - * its underlying hyperplane (may be null). - */ - private final SubHyperplane<S> plusOutside; - - /** Part of the node cut sub-hyperplane that belongs to the - * boundary and has the inside of the region on the plus side of - * its underlying hyperplane (may be null). - */ - private final SubHyperplane<S> plusInside; - - /** Sub-hyperplanes that were used to split the boundary part. */ - private final NodesSet<S> splitters; - - /** Simple constructor. - * @param plusOutside part of the node cut sub-hyperplane that - * belongs to the boundary and has the outside of the region on - * the plus side of its underlying hyperplane (may be null) - * @param plusInside part of the node cut sub-hyperplane that - * belongs to the boundary and has the inside of the region on the - * plus side of its underlying hyperplane (may be null) - * @deprecated as of 3.4, the constructor has been replaced by a new one - * which is not public anymore, as it is intended to be used only by - * {@link BoundaryBuilder} - */ - @Deprecated - public BoundaryAttribute(final SubHyperplane<S> plusOutside, - final SubHyperplane<S> plusInside) { - this(plusOutside, plusInside, null); - } - - /** Simple constructor. - * @param plusOutside part of the node cut sub-hyperplane that - * belongs to the boundary and has the outside of the region on - * the plus side of its underlying hyperplane (may be null) - * @param plusInside part of the node cut sub-hyperplane that - * belongs to the boundary and has the inside of the region on the - * plus side of its underlying hyperplane (may be null) - * @param splitters sub-hyperplanes that were used to - * split the boundary part (may be null) - * @since 3.4 - */ - BoundaryAttribute(final SubHyperplane<S> plusOutside, - final SubHyperplane<S> plusInside, - final NodesSet<S> splitters) { - this.plusOutside = plusOutside; - this.plusInside = plusInside; - this.splitters = splitters; - } - - /** Get the part of the node cut sub-hyperplane that belongs to the - * boundary and has the outside of the region on the plus side of - * its underlying hyperplane. - * @return part of the node cut sub-hyperplane that belongs to the - * boundary and has the outside of the region on the plus side of - * its underlying hyperplane - */ - public SubHyperplane<S> getPlusOutside() { - return plusOutside; - } - - /** Get the part of the node cut sub-hyperplane that belongs to the - * boundary and has the inside of the region on the plus side of - * its underlying hyperplane. - * @return part of the node cut sub-hyperplane that belongs to the - * boundary and has the inside of the region on the plus side of - * its underlying hyperplane - */ - public SubHyperplane<S> getPlusInside() { - return plusInside; - } - - /** Get the sub-hyperplanes that were used to split the boundary part. - * @return sub-hyperplanes that were used to split the boundary part - */ - public NodesSet<S> getSplitters() { - return splitters; - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java deleted file mode 100644 index cea4de3..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java +++ /dev/null @@ -1,95 +0,0 @@ -/* - * 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 org.apache.commons.math3.geometry.Space; - -/** Visitor building boundary shell tree. - * <p> - * The boundary shell is represented as {@link BoundaryAttribute boundary attributes} - * at each internal node. - * </p> - * @param <S> Type of the space. - * @since 3.4 - */ -class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> { - - /** {@inheritDoc} */ - public Order visitOrder(BSPTree<S> node) { - return Order.PLUS_MINUS_SUB; - } - - /** {@inheritDoc} */ - public void visitInternalNode(BSPTree<S> node) { - - SubHyperplane<S> plusOutside = null; - SubHyperplane<S> plusInside = null; - NodesSet<S> splitters = null; - - // characterize the cut sub-hyperplane, - // first with respect to the plus sub-tree - final Characterization<S> plusChar = new Characterization<S>(node.getPlus(), node.getCut().copySelf()); - - if (plusChar.touchOutside()) { - // plusChar.outsideTouching() corresponds to a subset of the cut sub-hyperplane - // known to have outside cells on its plus side, we want to check if parts - // of this subset do have inside cells on their minus side - final Characterization<S> minusChar = new Characterization<S>(node.getMinus(), plusChar.outsideTouching()); - if (minusChar.touchInside()) { - // this part belongs to the boundary, - // it has the outside on its plus side and the inside on its minus side - plusOutside = minusChar.insideTouching(); - splitters = new NodesSet<S>(); - splitters.addAll(minusChar.getInsideSplitters()); - splitters.addAll(plusChar.getOutsideSplitters()); - } - } - - if (plusChar.touchInside()) { - // plusChar.insideTouching() corresponds to a subset of the cut sub-hyperplane - // known to have inside cells on its plus side, we want to check if parts - // of this subset do have outside cells on their minus side - final Characterization<S> minusChar = new Characterization<S>(node.getMinus(), plusChar.insideTouching()); - if (minusChar.touchOutside()) { - // this part belongs to the boundary, - // it has the inside on its plus side and the outside on its minus side - plusInside = minusChar.outsideTouching(); - if (splitters == null) { - splitters = new NodesSet<S>(); - } - splitters.addAll(minusChar.getOutsideSplitters()); - splitters.addAll(plusChar.getInsideSplitters()); - } - } - - if (splitters != null) { - // the parent nodes are natural splitters for boundary sub-hyperplanes - for (BSPTree<S> up = node.getParent(); up != null; up = up.getParent()) { - splitters.add(up); - } - } - - // set the boundary attribute at non-leaf nodes - node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside, splitters)); - - } - - /** {@inheritDoc} */ - public void visitLeafNode(BSPTree<S> node) { - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryProjection.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryProjection.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryProjection.java deleted file mode 100644 index 03526e4..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryProjection.java +++ /dev/null @@ -1,83 +0,0 @@ -/* - * 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 org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Space; - -/** Class holding the result of point projection on region boundary. - * <p>This class is a simple placeholder, it does not provide any - * processing methods.</p> - * <p>Instances of this class are guaranteed to be immutable</p> - * @param <S> Type of the space. - * @since 3.3 - * @see AbstractRegion#projectToBoundary(Point) - */ -public class BoundaryProjection<S extends Space> { - - /** Original point. */ - private final Point<S> original; - - /** Projected point. */ - private final Point<S> projected; - - /** Offset of the point with respect to the boundary it is projected on. */ - private final double offset; - - /** Constructor from raw elements. - * @param original original point - * @param projected projected point - * @param offset offset of the point with respect to the boundary it is projected on - */ - public BoundaryProjection(final Point<S> original, final Point<S> projected, final double offset) { - this.original = original; - this.projected = projected; - this.offset = offset; - } - - /** Get the original point. - * @return original point - */ - public Point<S> getOriginal() { - return original; - } - - /** Projected point. - * @return projected point, or null if there are no boundary - */ - public Point<S> getProjected() { - return projected; - } - - /** Offset of the point with respect to the boundary it is projected on. - * <p> - * The offset with respect to the boundary is negative if the {@link - * #getOriginal() original point} is inside the region, and positive otherwise. - * </p> - * <p> - * If there are no boundary, the value is set to either {@code - * Double.POSITIVE_INFINITY} if the region is empty (i.e. all points are - * outside of the region) or {@code Double.NEGATIVE_INFINITY} if the region - * covers the whole space (i.e. all points are inside of the region). - * </p> - * @return offset of the point with respect to the boundary it is projected on - */ - public double getOffset() { - return offset; - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryProjector.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryProjector.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryProjector.java deleted file mode 100644 index 9f660bf..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryProjector.java +++ /dev/null @@ -1,200 +0,0 @@ -/* - * 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.geometry.Point; -import org.apache.commons.math3.geometry.Space; -import org.apache.commons.math3.geometry.partitioning.Region.Location; -import org.apache.commons.math3.util.FastMath; - -/** Local tree visitor to compute projection on boundary. - * @param <S> Type of the space. - * @param <T> Type of the sub-space. - * @since 3.3 - */ -class BoundaryProjector<S extends Space, T extends Space> implements BSPTreeVisitor<S> { - - /** Original point. */ - private final Point<S> original; - - /** Current best projected point. */ - private Point<S> projected; - - /** Leaf node closest to the test point. */ - private BSPTree<S> leaf; - - /** Current offset. */ - private double offset; - - /** Simple constructor. - * @param original original point - */ - public BoundaryProjector(final Point<S> original) { - this.original = original; - this.projected = null; - this.leaf = null; - this.offset = Double.POSITIVE_INFINITY; - } - - /** {@inheritDoc} */ - public Order visitOrder(final BSPTree<S> node) { - // we want to visit the tree so that the first encountered - // leaf is the one closest to the test point - if (node.getCut().getHyperplane().getOffset(original) <= 0) { - return Order.MINUS_SUB_PLUS; - } else { - return Order.PLUS_SUB_MINUS; - } - } - - /** {@inheritDoc} */ - public void visitInternalNode(final BSPTree<S> node) { - - // project the point on the cut sub-hyperplane - final Hyperplane<S> hyperplane = node.getCut().getHyperplane(); - final double signedOffset = hyperplane.getOffset(original); - if (FastMath.abs(signedOffset) < offset) { - - // project point - final Point<S> regular = hyperplane.project(original); - - // get boundary parts - final List<Region<T>> boundaryParts = boundaryRegions(node); - - // check if regular projection really belongs to the boundary - boolean regularFound = false; - for (final Region<T> part : boundaryParts) { - if (!regularFound && belongsToPart(regular, hyperplane, part)) { - // the projected point lies in the boundary - projected = regular; - offset = FastMath.abs(signedOffset); - regularFound = true; - } - } - - if (!regularFound) { - // the regular projected point is not on boundary, - // so we have to check further if a singular point - // (i.e. a vertex in 2D case) is a possible projection - for (final Region<T> part : boundaryParts) { - final Point<S> spI = singularProjection(regular, hyperplane, part); - if (spI != null) { - final double distance = original.distance(spI); - if (distance < offset) { - projected = spI; - offset = distance; - } - } - } - - } - - } - - } - - /** {@inheritDoc} */ - public void visitLeafNode(final BSPTree<S> node) { - if (leaf == null) { - // this is the first leaf we visit, - // it is the closest one to the original point - leaf = node; - } - } - - /** Get the projection. - * @return projection - */ - public BoundaryProjection<S> getProjection() { - - // fix offset sign - offset = FastMath.copySign(offset, (Boolean) leaf.getAttribute() ? -1 : +1); - - return new BoundaryProjection<S>(original, projected, offset); - - } - - /** Extract the regions of the boundary on an internal node. - * @param node internal node - * @return regions in the node sub-hyperplane - */ - private List<Region<T>> boundaryRegions(final BSPTree<S> node) { - - final List<Region<T>> regions = new ArrayList<Region<T>>(2); - - @SuppressWarnings("unchecked") - final BoundaryAttribute<S> ba = (BoundaryAttribute<S>) node.getAttribute(); - addRegion(ba.getPlusInside(), regions); - addRegion(ba.getPlusOutside(), regions); - - return regions; - - } - - /** Add a boundary region to a list. - * @param sub sub-hyperplane defining the region - * @param list to fill up - */ - private void addRegion(final SubHyperplane<S> sub, final List<Region<T>> list) { - if (sub != null) { - @SuppressWarnings("unchecked") - final Region<T> region = ((AbstractSubHyperplane<S, T>) sub).getRemainingRegion(); - if (region != null) { - list.add(region); - } - }; - } - - /** Check if a projected point lies on a boundary part. - * @param point projected point to check - * @param hyperplane hyperplane into which the point was projected - * @param part boundary part - * @return true if point lies on the boundary part - */ - private boolean belongsToPart(final Point<S> point, final Hyperplane<S> hyperplane, - final Region<T> part) { - - // there is a non-null sub-space, we can dive into smaller dimensions - @SuppressWarnings("unchecked") - final Embedding<S, T> embedding = (Embedding<S, T>) hyperplane; - return part.checkPoint(embedding.toSubSpace(point)) != Location.OUTSIDE; - - } - - /** Get the projection to the closest boundary singular point. - * @param point projected point to check - * @param hyperplane hyperplane into which the point was projected - * @param part boundary part - * @return projection to a singular point of boundary part (may be null) - */ - private Point<S> singularProjection(final Point<S> point, final Hyperplane<S> hyperplane, - final Region<T> part) { - - // there is a non-null sub-space, we can dive into smaller dimensions - @SuppressWarnings("unchecked") - final Embedding<S, T> embedding = (Embedding<S, T>) hyperplane; - final BoundaryProjection<T> bp = part.projectToBoundary(embedding.toSubSpace(point)); - - // back to initial dimension - return (bp.getProjected() == null) ? null : embedding.toSpace(bp.getProjected()); - - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundarySizeVisitor.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundarySizeVisitor.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundarySizeVisitor.java deleted file mode 100644 index e29083a..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundarySizeVisitor.java +++ /dev/null @@ -1,65 +0,0 @@ -/* - * 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 org.apache.commons.math3.geometry.Space; - -/** Visitor computing the boundary size. - * @param <S> Type of the space. - * @since 3.0 - */ -class BoundarySizeVisitor<S extends Space> implements BSPTreeVisitor<S> { - - /** Size of the boundary. */ - private double boundarySize; - - /** Simple constructor. - */ - public BoundarySizeVisitor() { - boundarySize = 0; - } - - /** {@inheritDoc}*/ - public Order visitOrder(final BSPTree<S> node) { - return Order.MINUS_SUB_PLUS; - } - - /** {@inheritDoc}*/ - public void visitInternalNode(final BSPTree<S> node) { - @SuppressWarnings("unchecked") - final BoundaryAttribute<S> attribute = - (BoundaryAttribute<S>) node.getAttribute(); - if (attribute.getPlusOutside() != null) { - boundarySize += attribute.getPlusOutside().getSize(); - } - if (attribute.getPlusInside() != null) { - boundarySize += attribute.getPlusInside().getSize(); - } - } - - /** {@inheritDoc}*/ - public void visitLeafNode(final BSPTree<S> node) { - } - - /** Get the size of the boundary. - * @return size of the boundary - */ - public double getSize() { - return boundarySize; - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java deleted file mode 100644 index 58efe0f..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java +++ /dev/null @@ -1,190 +0,0 @@ -/* - * 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.MathInternalError; -import org.apache.commons.math3.geometry.Space; - -/** Cut sub-hyperplanes characterization with respect to inside/outside cells. - * @see BoundaryBuilder - * @param <S> Type of the space. - * @since 3.4 - */ -class Characterization<S extends Space> { - - /** Part of the cut sub-hyperplane that touch outside cells. */ - private SubHyperplane<S> outsideTouching; - - /** Part of the cut sub-hyperplane that touch inside cells. */ - private SubHyperplane<S> insideTouching; - - /** Nodes that were used to split the outside touching part. */ - private final NodesSet<S> outsideSplitters; - - /** Nodes that were used to split the outside touching part. */ - private final NodesSet<S> insideSplitters; - - /** Simple constructor. - * <p>Characterization consists in splitting the specified - * sub-hyperplane into several parts lying in inside and outside - * cells of the tree. The principle is to compute characterization - * twice for each cut sub-hyperplane in the tree, once on the plus - * node and once on the minus node. The parts that have the same flag - * (inside/inside or outside/outside) do not belong to the boundary - * while parts that have different flags (inside/outside or - * outside/inside) do belong to the boundary.</p> - * @param node current BSP tree node - * @param sub sub-hyperplane to characterize - */ - public Characterization(final BSPTree<S> node, final SubHyperplane<S> sub) { - outsideTouching = null; - insideTouching = null; - outsideSplitters = new NodesSet<S>(); - insideSplitters = new NodesSet<S>(); - characterize(node, sub, new ArrayList<BSPTree<S>>()); - } - - /** Filter the parts of an hyperplane belonging to the boundary. - * <p>The filtering consist in splitting the specified - * sub-hyperplane into several parts lying in inside and outside - * cells of the tree. The principle is to call this method twice for - * each cut sub-hyperplane in the tree, once on the plus node and - * once on the minus node. The parts that have the same flag - * (inside/inside or outside/outside) do not belong to the boundary - * while parts that have different flags (inside/outside or - * outside/inside) do belong to the boundary.</p> - * @param node current BSP tree node - * @param sub sub-hyperplane to characterize - * @param splitters nodes that did split the current one - */ - private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub, - final List<BSPTree<S>> splitters) { - if (node.getCut() == null) { - // we have reached a leaf node - final boolean inside = (Boolean) node.getAttribute(); - if (inside) { - addInsideTouching(sub, splitters); - } else { - addOutsideTouching(sub, splitters); - } - } else { - final Hyperplane<S> hyperplane = node.getCut().getHyperplane(); - switch (sub.side(hyperplane)) { - case PLUS: - characterize(node.getPlus(), sub, splitters); - break; - case MINUS: - characterize(node.getMinus(), sub, splitters); - break; - case BOTH: - final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane); - splitters.add(node); - characterize(node.getPlus(), split.getPlus(), splitters); - characterize(node.getMinus(), split.getMinus(), splitters); - splitters.remove(splitters.size() - 1); - break; - default: - // this should not happen - throw new MathInternalError(); - } - } - } - - /** Add a part of the cut sub-hyperplane known to touch an outside cell. - * @param sub part of the cut sub-hyperplane known to touch an outside cell - * @param splitters sub-hyperplanes that did split the current one - */ - private void addOutsideTouching(final SubHyperplane<S> sub, - final List<BSPTree<S>> splitters) { - if (outsideTouching == null) { - outsideTouching = sub; - } else { - outsideTouching = outsideTouching.reunite(sub); - } - outsideSplitters.addAll(splitters); - } - - /** Add a part of the cut sub-hyperplane known to touch an inside cell. - * @param sub part of the cut sub-hyperplane known to touch an inside cell - * @param splitters sub-hyperplanes that did split the current one - */ - private void addInsideTouching(final SubHyperplane<S> sub, - final List<BSPTree<S>> splitters) { - if (insideTouching == null) { - insideTouching = sub; - } else { - insideTouching = insideTouching.reunite(sub); - } - insideSplitters.addAll(splitters); - } - - /** Check if the cut sub-hyperplane touches outside cells. - * @return true if the cut sub-hyperplane touches outside cells - */ - public boolean touchOutside() { - return outsideTouching != null && !outsideTouching.isEmpty(); - } - - /** Get all the parts of the cut sub-hyperplane known to touch outside cells. - * @return parts of the cut sub-hyperplane known to touch outside cells - * (may be null or empty) - */ - public SubHyperplane<S> outsideTouching() { - return outsideTouching; - } - - /** Get the nodes that were used to split the outside touching part. - * <p> - * Splitting nodes are internal nodes (i.e. they have a non-null - * cut sub-hyperplane). - * </p> - * @return nodes that were used to split the outside touching part - */ - public NodesSet<S> getOutsideSplitters() { - return outsideSplitters; - } - - /** Check if the cut sub-hyperplane touches inside cells. - * @return true if the cut sub-hyperplane touches inside cells - */ - public boolean touchInside() { - return insideTouching != null && !insideTouching.isEmpty(); - } - - /** Get all the parts of the cut sub-hyperplane known to touch inside cells. - * @return parts of the cut sub-hyperplane known to touch inside cells - * (may be null or empty) - */ - public SubHyperplane<S> insideTouching() { - return insideTouching; - } - - /** Get the nodes that were used to split the inside touching part. - * <p> - * Splitting nodes are internal nodes (i.e. they have a non-null - * cut sub-hyperplane). - * </p> - * @return nodes that were used to split the inside touching part - */ - public NodesSet<S> getInsideSplitters() { - return insideSplitters; - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/Embedding.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/Embedding.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/Embedding.java deleted file mode 100644 index 74e2c00..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/Embedding.java +++ /dev/null @@ -1,68 +0,0 @@ -/* - * 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 org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Space; - -/** This interface defines mappers between a space and one of its sub-spaces. - - * <p>Sub-spaces are the lower dimensions subsets of a n-dimensions - * space. The (n-1)-dimension sub-spaces are specific sub-spaces known - * as {@link Hyperplane hyperplanes}. This interface can be used regardless - * of the dimensions differences. As an example, {@link - * org.apache.commons.math3.geometry.euclidean.threed.Line Line} in 3D - * implements Embedding<{@link - * org.apache.commons.math3.geometry.euclidean.threed.Vector3D Vector3D}, {link - * org.apache.commons.math3.geometry.euclidean.oned.Vector1D Vector1D>, i.e. it - * maps directly dimensions 3 and 1.</p> - - * <p>In the 3D euclidean space, hyperplanes are 2D planes, and the 1D - * sub-spaces are lines.</p> - - * <p> - * Note that this interface is <em>not</em> intended to be implemented - * by Apache Commons Math users, it is only intended to be implemented - * within the library itself. New methods may be added even for minor - * versions, which breaks compatibility for external implementations. - * </p> - - * @param <S> Type of the embedding space. - * @param <T> Type of the embedded sub-space. - - * @see Hyperplane - * @since 3.0 - */ -public interface Embedding<S extends Space, T extends Space> { - - /** Transform a space point into a sub-space point. - * @param point n-dimension point of the space - * @return (n-1)-dimension point of the sub-space corresponding to - * the specified space point - * @see #toSpace - */ - Point<T> toSubSpace(Point<S> point); - - /** Transform a sub-space point into a space point. - * @param point (n-1)-dimension point of the sub-space - * @return n-dimension point of the space corresponding to the - * specified sub-space point - * @see #toSubSpace - */ - Point<S> toSpace(Point<T> point); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/Hyperplane.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/Hyperplane.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/Hyperplane.java deleted file mode 100644 index f90c3bc..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/Hyperplane.java +++ /dev/null @@ -1,98 +0,0 @@ -/* - * 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 org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Space; - -/** This interface represents an hyperplane of a space. - - * <p>The most prominent place where hyperplane appears in space - * partitioning is as cutters. Each partitioning node in a {@link - * BSPTree BSP tree} has a cut {@link SubHyperplane sub-hyperplane} - * which is either an hyperplane or a part of an hyperplane. In an - * n-dimensions euclidean space, an hyperplane is an (n-1)-dimensions - * hyperplane (for example a traditional plane in the 3D euclidean - * space). They can be more exotic objects in specific fields, for - * example a circle on the surface of the unit sphere.</p> - - * <p> - * Note that this interface is <em>not</em> intended to be implemented - * by Apache Commons Math users, it is only intended to be implemented - * within the library itself. New methods may be added even for minor - * versions, which breaks compatibility for external implementations. - * </p> - - * @param <S> Type of the space. - - * @since 3.0 - */ -public interface Hyperplane<S extends Space> { - - /** Copy the instance. - * <p>The instance created is completely independant of the original - * one. A deep copy is used, none of the underlying objects are - * shared (except for immutable objects).</p> - * @return a new hyperplane, copy of the instance - */ - Hyperplane<S> copySelf(); - - /** Get the offset (oriented distance) of a point. - * <p>The offset is 0 if the point is on the underlying hyperplane, - * it is positive if the point is on one particular side of the - * hyperplane, and it is negative if the point is on the other side, - * according to the hyperplane natural orientation.</p> - * @param point point to check - * @return offset of the point - */ - double getOffset(Point<S> point); - - /** Project a point to the hyperplane. - * @param point point to project - * @return projected point - * @since 3.3 - */ - Point<S> project(Point<S> point); - - /** Get the tolerance below which points are considered to belong to the hyperplane. - * @return tolerance below which points are considered to belong to the hyperplane - * @since 3.3 - */ - double getTolerance(); - - /** Check if the instance has the same orientation as another hyperplane. - * <p>This method is expected to be called on parallel hyperplanes. The - * method should <em>not</em> re-check for parallelism, only for - * orientation, typically by testing something like the sign of the - * dot-products of normals.</p> - * @param other other hyperplane to check against the instance - * @return true if the instance and the other hyperplane have - * the same orientation - */ - boolean sameOrientationAs(Hyperplane<S> other); - - /** Build a sub-hyperplane covering the whole hyperplane. - * @return a sub-hyperplane covering the whole hyperplane - */ - SubHyperplane<S> wholeHyperplane(); - - /** Build a region covering the whole space. - * @return a region containing the instance - */ - Region<S> wholeSpace(); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/InsideFinder.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/InsideFinder.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/InsideFinder.java deleted file mode 100644 index 2b0b405..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/InsideFinder.java +++ /dev/null @@ -1,150 +0,0 @@ -/* - * 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 org.apache.commons.math3.geometry.Space; - -/** Utility class checking if inside nodes can be found - * on the plus and minus sides of an hyperplane. - * @param <S> Type of the space. - * @since 3.4 - */ -class InsideFinder<S extends Space> { - - /** Region on which to operate. */ - private final Region<S> region; - - /** Indicator of inside leaf nodes found on the plus side. */ - private boolean plusFound; - - /** Indicator of inside leaf nodes found on the plus side. */ - private boolean minusFound; - - /** Simple constructor. - * @param region region on which to operate - */ - public InsideFinder(final Region<S> region) { - this.region = region; - plusFound = false; - minusFound = false; - } - - /** Search recursively for inside leaf nodes on each side of the given hyperplane. - - * <p>The algorithm used here is directly derived from the one - * described in section III (<i>Binary Partitioning of a BSP - * Tree</i>) of the 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 node current BSP tree node - * @param sub sub-hyperplane - */ - public void recurseSides(final BSPTree<S> node, final SubHyperplane<S> sub) { - - if (node.getCut() == null) { - if ((Boolean) node.getAttribute()) { - // this is an inside cell expanding across the hyperplane - plusFound = true; - minusFound = true; - } - return; - } - - final Hyperplane<S> hyperplane = node.getCut().getHyperplane(); - switch (sub.side(hyperplane)) { - case PLUS : - // the sub-hyperplane is entirely in the plus sub-tree - if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) { - if (!region.isEmpty(node.getMinus())) { - plusFound = true; - } - } else { - if (!region.isEmpty(node.getMinus())) { - minusFound = true; - } - } - if (!(plusFound && minusFound)) { - recurseSides(node.getPlus(), sub); - } - break; - case MINUS : - // the sub-hyperplane is entirely in the minus sub-tree - if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) { - if (!region.isEmpty(node.getPlus())) { - plusFound = true; - } - } else { - if (!region.isEmpty(node.getPlus())) { - minusFound = true; - } - } - if (!(plusFound && minusFound)) { - recurseSides(node.getMinus(), sub); - } - break; - case BOTH : - // the sub-hyperplane extends in both sub-trees - final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane); - - // explore first the plus sub-tree - recurseSides(node.getPlus(), split.getPlus()); - - // if needed, explore the minus sub-tree - if (!(plusFound && minusFound)) { - recurseSides(node.getMinus(), split.getMinus()); - } - break; - default : - // the sub-hyperplane and the cut sub-hyperplane share the same hyperplane - if (node.getCut().getHyperplane().sameOrientationAs(sub.getHyperplane())) { - if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) { - plusFound = true; - } - if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) { - minusFound = true; - } - } else { - if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) { - minusFound = true; - } - if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) { - plusFound = true; - } - } - } - - } - - /** Check if inside leaf nodes have been found on the plus side. - * @return true if inside leaf nodes have been found on the plus side - */ - public boolean plusFound() { - return plusFound; - } - - /** Check if inside leaf nodes have been found on the minus side. - * @return true if inside leaf nodes have been found on the minus side - */ - public boolean minusFound() { - return minusFound; - } - -}
