http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/NodesSet.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/NodesSet.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/NodesSet.java deleted file mode 100644 index 688279a..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/NodesSet.java +++ /dev/null @@ -1,72 +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.Iterator; -import java.util.List; - -import org.apache.commons.math3.geometry.Space; - -/** Set of {@link BSPTree BSP tree} nodes. - * @see BoundaryAttribute - * @param <S> Type of the space. - * @since 3.4 - */ -public class NodesSet<S extends Space> implements Iterable<BSPTree<S>> { - - /** List of sub-hyperplanes. */ - private List<BSPTree<S>> list; - - /** Simple constructor. - */ - public NodesSet() { - list = new ArrayList<BSPTree<S>>(); - } - - /** Add a node if not already known. - * @param node node to add - */ - public void add(final BSPTree<S> node) { - - for (final BSPTree<S> existing : list) { - if (node == existing) { - // the node is already known, don't add it - return; - } - } - - // the node was not known, add it - list.add(node); - - } - - /** Add nodes if they are not already known. - * @param iterator nodes iterator - */ - public void addAll(final Iterable<BSPTree<S>> iterator) { - for (final BSPTree<S> node : iterator) { - add(node); - } - } - - /** {@inheritDoc} */ - public Iterator<BSPTree<S>> iterator() { - return list.iterator(); - } - -}
http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java deleted file mode 100644 index 3f4d5f5..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java +++ /dev/null @@ -1,218 +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; -import org.apache.commons.math3.geometry.Point; - -/** This interface represents a region of a space as a partition. - - * <p>Region are subsets of a space, they can be infinite (whole - * space, half space, infinite stripe ...) or finite (polygons in 2D, - * polyhedrons in 3D ...). Their main characteristic is to separate - * points that are considered to be <em>inside</em> the region from - * points considered to be <em>outside</em> of it. In between, there - * may be points on the <em>boundary</em> of the region.</p> - - * <p>This implementation is limited to regions for which the boundary - * is composed of several {@link SubHyperplane sub-hyperplanes}, - * including regions with no boundary at all: the whole space and the - * empty region. They are not necessarily finite and not necessarily - * path-connected. They can contain holes.</p> - - * <p>Regions can be combined using the traditional sets operations : - * union, intersection, difference and symetric difference (exclusive - * or) for the binary operations, complement for the unary - * operation.</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 Region<S extends Space> { - - /** Enumerate for the location of a point with respect to the region. */ - public static enum Location { - /** Code for points inside the partition. */ - INSIDE, - - /** Code for points outside of the partition. */ - OUTSIDE, - - /** Code for points on the partition boundary. */ - BOUNDARY; - } - - /** Build a region using the instance as a prototype. - * <p>This method allow to create new instances without knowing - * exactly the type of the region. It is an application of the - * prototype design pattern.</p> - * <p>The leaf nodes of the BSP tree <em>must</em> have a - * {@code Boolean} attribute representing the inside status of - * the corresponding cell (true for inside cells, false for outside - * cells). In order to avoid building too many small objects, it is - * recommended to use the predefined constants - * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The - * tree also <em>must</em> have either null internal nodes or - * internal nodes representing the boundary as specified in the - * {@link #getTree getTree} method).</p> - * @param newTree inside/outside BSP tree representing the new region - * @return the built region - */ - Region<S> buildNew(BSPTree<S> newTree); - - /** 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 the underlying tree {@code Boolean} - * attributes and immutable objects).</p> - * @return a new region, copy of the instance - */ - Region<S> copySelf(); - - /** Check if the instance is empty. - * @return true if the instance is empty - */ - boolean isEmpty(); - - /** Check if the sub-tree starting at a given node is empty. - * @param node root node of the sub-tree (<em>must</em> have {@link - * Region Region} tree semantics, i.e. the leaf nodes must have - * {@code Boolean} attributes representing an inside/outside - * property) - * @return true if the sub-tree starting at the given node is empty - */ - boolean isEmpty(final BSPTree<S> node); - - /** Check if the instance covers the full space. - * @return true if the instance covers the full space - */ - boolean isFull(); - - /** Check if the sub-tree starting at a given node covers the full space. - * @param node root node of the sub-tree (<em>must</em> have {@link - * Region Region} tree semantics, i.e. the leaf nodes must have - * {@code Boolean} attributes representing an inside/outside - * property) - * @return true if the sub-tree starting at the given node covers the full space - */ - boolean isFull(final BSPTree<S> node); - - /** Check if the instance entirely contains another region. - * @param region region to check against the instance - * @return true if the instance contains the specified tree - */ - boolean contains(final Region<S> region); - - /** Check a point with respect to the region. - * @param point point to check - * @return a code representing the point status: either {@link - * Location#INSIDE}, {@link Location#OUTSIDE} or {@link Location#BOUNDARY} - */ - Location checkPoint(final Point<S> point); - - /** Project a point on the boundary of the region. - * @param point point to check - * @return projection of the point on the boundary - * @since 3.3 - */ - BoundaryProjection<S> projectToBoundary(final Point<S> point); - - /** Get the underlying BSP tree. - - * <p>Regions are represented by an underlying inside/outside BSP - * tree whose leaf attributes are {@code Boolean} instances - * representing inside leaf cells if the attribute value is - * {@code true} and outside leaf cells if the attribute is - * {@code false}. These leaf attributes are always present and - * guaranteed to be non null.</p> - - * <p>In addition to the leaf attributes, the internal nodes which - * correspond to cells split by cut sub-hyperplanes may contain - * {@link BoundaryAttribute BoundaryAttribute} objects representing - * the parts of the corresponding cut sub-hyperplane that belong to - * the boundary. When the boundary attributes have been computed, - * all internal nodes are guaranteed to have non-null - * attributes, however some {@link BoundaryAttribute - * BoundaryAttribute} instances may have their {@link - * BoundaryAttribute#getPlusInside() getPlusInside} and {@link - * BoundaryAttribute#getPlusOutside() getPlusOutside} methods both - * returning null if the corresponding cut sub-hyperplane does not - * have any parts belonging to the boundary.</p> - - * <p>Since computing the boundary is not always required and can be - * time-consuming for large trees, these internal nodes attributes - * are computed using lazy evaluation only when required by setting - * the {@code includeBoundaryAttributes} argument to - * {@code true}. Once computed, these attributes remain in the - * tree, which implies that in this case, further calls to the - * method for the same region will always include these attributes - * regardless of the value of the - * {@code includeBoundaryAttributes} argument.</p> - - * @param includeBoundaryAttributes if true, the boundary attributes - * at internal nodes are guaranteed to be included (they may be - * included even if the argument is false, if they have already been - * computed due to a previous call) - * @return underlying BSP tree - * @see BoundaryAttribute - */ - BSPTree<S> getTree(final boolean includeBoundaryAttributes); - - /** Get the size of the boundary. - * @return the size of the boundary (this is 0 in 1D, a length in - * 2D, an area in 3D ...) - */ - double getBoundarySize(); - - /** Get the size of the instance. - * @return the size of the instance (this is a length in 1D, an area - * in 2D, a volume in 3D ...) - */ - double getSize(); - - /** Get the barycenter of the instance. - * @return an object representing the barycenter - */ - Point<S> getBarycenter(); - - /** Compute the relative position of the instance with respect to an - * hyperplane. - * @param hyperplane reference hyperplane - * @return one of {@link Side#PLUS Side.PLUS}, {@link Side#MINUS - * Side.MINUS}, {@link Side#BOTH Side.BOTH} or {@link Side#HYPER - * Side.HYPER} (the latter result can occur only if the tree - * contains only one cut hyperplane) - */ - Side side(final Hyperplane<S> hyperplane); - - /** Get the parts of a sub-hyperplane that are contained in the region. - * <p>The parts of the sub-hyperplane that belong to the boundary are - * <em>not</em> included in the resulting parts.</p> - * @param sub sub-hyperplane traversing the region - * @return filtered sub-hyperplane - */ - SubHyperplane<S> intersection(final SubHyperplane<S> sub); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java deleted file mode 100644 index 16d4472..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java +++ /dev/null @@ -1,349 +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.HashMap; -import java.util.Map; - -import org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Space; -import org.apache.commons.math3.geometry.partitioning.BSPTree.VanishingCutHandler; -import org.apache.commons.math3.geometry.partitioning.Region.Location; - -/** This class is a factory for {@link Region}. - - * @param <S> Type of the space. - - * @since 3.0 - */ -public class RegionFactory<S extends Space> { - - /** Visitor removing internal nodes attributes. */ - private final NodesCleaner nodeCleaner; - - /** Simple constructor. - */ - public RegionFactory() { - nodeCleaner = new NodesCleaner(); - } - - /** Build a convex region from a collection of bounding hyperplanes. - * @param hyperplanes collection of bounding hyperplanes - * @return a new convex region, or null if the collection is empty - */ - public Region<S> buildConvex(final Hyperplane<S> ... hyperplanes) { - if ((hyperplanes == null) || (hyperplanes.length == 0)) { - return null; - } - - // use the first hyperplane to build the right class - final Region<S> region = hyperplanes[0].wholeSpace(); - - // chop off parts of the space - BSPTree<S> node = region.getTree(false); - node.setAttribute(Boolean.TRUE); - for (final Hyperplane<S> hyperplane : hyperplanes) { - if (node.insertCut(hyperplane)) { - node.setAttribute(null); - node.getPlus().setAttribute(Boolean.FALSE); - node = node.getMinus(); - node.setAttribute(Boolean.TRUE); - } - } - - return region; - - } - - /** Compute the union of two regions. - * @param region1 first region (will be unusable after the operation as - * parts of it will be reused in the new region) - * @param region2 second region (will be unusable after the operation as - * parts of it will be reused in the new region) - * @return a new region, result of {@code region1 union region2} - */ - public Region<S> union(final Region<S> region1, final Region<S> region2) { - final BSPTree<S> tree = - region1.getTree(false).merge(region2.getTree(false), new UnionMerger()); - tree.visit(nodeCleaner); - return region1.buildNew(tree); - } - - /** Compute the intersection of two regions. - * @param region1 first region (will be unusable after the operation as - * parts of it will be reused in the new region) - * @param region2 second region (will be unusable after the operation as - * parts of it will be reused in the new region) - * @return a new region, result of {@code region1 intersection region2} - */ - public Region<S> intersection(final Region<S> region1, final Region<S> region2) { - final BSPTree<S> tree = - region1.getTree(false).merge(region2.getTree(false), new IntersectionMerger()); - tree.visit(nodeCleaner); - return region1.buildNew(tree); - } - - /** Compute the symmetric difference (exclusive or) of two regions. - * @param region1 first region (will be unusable after the operation as - * parts of it will be reused in the new region) - * @param region2 second region (will be unusable after the operation as - * parts of it will be reused in the new region) - * @return a new region, result of {@code region1 xor region2} - */ - public Region<S> xor(final Region<S> region1, final Region<S> region2) { - final BSPTree<S> tree = - region1.getTree(false).merge(region2.getTree(false), new XorMerger()); - tree.visit(nodeCleaner); - return region1.buildNew(tree); - } - - /** Compute the difference of two regions. - * @param region1 first region (will be unusable after the operation as - * parts of it will be reused in the new region) - * @param region2 second region (will be unusable after the operation as - * parts of it will be reused in the new region) - * @return a new region, result of {@code region1 minus region2} - */ - public Region<S> difference(final Region<S> region1, final Region<S> region2) { - final BSPTree<S> tree = - region1.getTree(false).merge(region2.getTree(false), new DifferenceMerger(region1, region2)); - tree.visit(nodeCleaner); - return region1.buildNew(tree); - } - - /** Get the complement of the region (exchanged interior/exterior). - * @param region region to complement, it will not modified, a new - * region independent region will be built - * @return a new region, complement of the specified one - */ - /** Get the complement of the region (exchanged interior/exterior). - * @param region region to complement, it will not modified, a new - * region independent region will be built - * @return a new region, complement of the specified one - */ - public Region<S> getComplement(final Region<S> region) { - return region.buildNew(recurseComplement(region.getTree(false))); - } - - /** Recursively build the complement of a BSP tree. - * @param node current node of the original tree - * @return new tree, complement of the node - */ - private BSPTree<S> recurseComplement(final BSPTree<S> node) { - - // transform the tree, except for boundary attribute splitters - final Map<BSPTree<S>, BSPTree<S>> map = new HashMap<BSPTree<S>, BSPTree<S>>(); - final BSPTree<S> transformedTree = recurseComplement(node, map); - - // set up the boundary attributes splitters - for (final Map.Entry<BSPTree<S>, BSPTree<S>> entry : map.entrySet()) { - if (entry.getKey().getCut() != null) { - @SuppressWarnings("unchecked") - BoundaryAttribute<S> original = (BoundaryAttribute<S>) entry.getKey().getAttribute(); - if (original != null) { - @SuppressWarnings("unchecked") - BoundaryAttribute<S> transformed = (BoundaryAttribute<S>) entry.getValue().getAttribute(); - for (final BSPTree<S> splitter : original.getSplitters()) { - transformed.getSplitters().add(map.get(splitter)); - } - } - } - } - - return transformedTree; - - } - - /** Recursively build the complement of a BSP tree. - * @param node current node of the original tree - * @param map transformed nodes map - * @return new tree, complement of the node - */ - private BSPTree<S> recurseComplement(final BSPTree<S> node, - final Map<BSPTree<S>, BSPTree<S>> map) { - - final BSPTree<S> transformedNode; - if (node.getCut() == null) { - transformedNode = new BSPTree<S>(((Boolean) node.getAttribute()) ? Boolean.FALSE : Boolean.TRUE); - } else { - - @SuppressWarnings("unchecked") - BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute(); - if (attribute != null) { - final SubHyperplane<S> plusOutside = - (attribute.getPlusInside() == null) ? null : attribute.getPlusInside().copySelf(); - final SubHyperplane<S> plusInside = - (attribute.getPlusOutside() == null) ? null : attribute.getPlusOutside().copySelf(); - // we start with an empty list of splitters, it will be filled in out of recursion - attribute = new BoundaryAttribute<S>(plusOutside, plusInside, new NodesSet<S>()); - } - - transformedNode = new BSPTree<S>(node.getCut().copySelf(), - recurseComplement(node.getPlus(), map), - recurseComplement(node.getMinus(), map), - attribute); - } - - map.put(node, transformedNode); - return transformedNode; - - } - - /** BSP tree leaf merger computing union of two regions. */ - private class UnionMerger implements BSPTree.LeafMerger<S> { - /** {@inheritDoc} */ - public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, - final BSPTree<S> parentTree, - final boolean isPlusChild, final boolean leafFromInstance) { - if ((Boolean) leaf.getAttribute()) { - // the leaf node represents an inside cell - leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); - return leaf; - } - // the leaf node represents an outside cell - tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false)); - return tree; - } - } - - /** BSP tree leaf merger computing intersection of two regions. */ - private class IntersectionMerger implements BSPTree.LeafMerger<S> { - /** {@inheritDoc} */ - public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, - final BSPTree<S> parentTree, - final boolean isPlusChild, final boolean leafFromInstance) { - if ((Boolean) leaf.getAttribute()) { - // the leaf node represents an inside cell - tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); - return tree; - } - // the leaf node represents an outside cell - leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false)); - return leaf; - } - } - - /** BSP tree leaf merger computing symmetric difference (exclusive or) of two regions. */ - private class XorMerger implements BSPTree.LeafMerger<S> { - /** {@inheritDoc} */ - public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, - final BSPTree<S> parentTree, final boolean isPlusChild, - final boolean leafFromInstance) { - BSPTree<S> t = tree; - if ((Boolean) leaf.getAttribute()) { - // the leaf node represents an inside cell - t = recurseComplement(t); - } - t.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); - return t; - } - } - - /** BSP tree leaf merger computing difference of two regions. */ - private class DifferenceMerger implements BSPTree.LeafMerger<S>, VanishingCutHandler<S> { - - /** Region to subtract from. */ - private final Region<S> region1; - - /** Region to subtract. */ - private final Region<S> region2; - - /** Simple constructor. - * @param region1 region to subtract from - * @param region2 region to subtract - */ - public DifferenceMerger(final Region<S> region1, final Region<S> region2) { - this.region1 = region1.copySelf(); - this.region2 = region2.copySelf(); - } - - /** {@inheritDoc} */ - public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, - final BSPTree<S> parentTree, final boolean isPlusChild, - final boolean leafFromInstance) { - if ((Boolean) leaf.getAttribute()) { - // the leaf node represents an inside cell - final BSPTree<S> argTree = - recurseComplement(leafFromInstance ? tree : leaf); - argTree.insertInTree(parentTree, isPlusChild, this); - return argTree; - } - // the leaf node represents an outside cell - final BSPTree<S> instanceTree = - leafFromInstance ? leaf : tree; - instanceTree.insertInTree(parentTree, isPlusChild, this); - return instanceTree; - } - - /** {@inheritDoc} */ - public BSPTree<S> fixNode(final BSPTree<S> node) { - // get a representative point in the degenerate cell - final BSPTree<S> cell = node.pruneAroundConvexCell(Boolean.TRUE, Boolean.FALSE, null); - final Region<S> r = region1.buildNew(cell); - final Point<S> p = r.getBarycenter(); - return new BSPTree<S>(region1.checkPoint(p) == Location.INSIDE && - region2.checkPoint(p) == Location.OUTSIDE); - } - - } - - /** Visitor removing internal nodes attributes. */ - private class NodesCleaner implements BSPTreeVisitor<S> { - - /** {@inheritDoc} */ - public Order visitOrder(final BSPTree<S> node) { - return Order.PLUS_SUB_MINUS; - } - - /** {@inheritDoc} */ - public void visitInternalNode(final BSPTree<S> node) { - node.setAttribute(null); - } - - /** {@inheritDoc} */ - public void visitLeafNode(final BSPTree<S> node) { - } - - } - - /** Handler replacing nodes with vanishing cuts with leaf nodes. */ - private class VanishingToLeaf implements VanishingCutHandler<S> { - - /** Inside/outside indocator to use for ambiguous nodes. */ - private final boolean inside; - - /** Simple constructor. - * @param inside inside/outside indicator to use for ambiguous nodes - */ - public VanishingToLeaf(final boolean inside) { - this.inside = inside; - } - - /** {@inheritDoc} */ - public BSPTree<S> fixNode(final BSPTree<S> node) { - if (node.getPlus().getAttribute().equals(node.getMinus().getAttribute())) { - // no ambiguity - return new BSPTree<S>(node.getPlus().getAttribute()); - } else { - // ambiguous node - return new BSPTree<S>(inside); - } - } - - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/Side.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/Side.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/Side.java deleted file mode 100644 index c9a1357..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/Side.java +++ /dev/null @@ -1,37 +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; - -/** Enumerate representing the location of an element with respect to an - * {@link Hyperplane hyperplane} of a space. - * @since 3.0 - */ -public enum Side { - - /** Code for the plus side of the hyperplane. */ - PLUS, - - /** Code for the minus side of the hyperplane. */ - MINUS, - - /** Code for elements crossing the hyperplane from plus to minus side. */ - BOTH, - - /** Code for the hyperplane itself. */ - HYPER; - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/SubHyperplane.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/SubHyperplane.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/SubHyperplane.java deleted file mode 100644 index 70c6043..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/SubHyperplane.java +++ /dev/null @@ -1,131 +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 represents the remaining parts of an hyperplane after - * other parts have been chopped off. - - * <p>sub-hyperplanes are obtained when parts of an {@link - * Hyperplane hyperplane} are chopped off by other hyperplanes that - * intersect it. The remaining part is a convex region. Such objects - * appear in {@link BSPTree BSP trees} as the intersection of a cut - * hyperplane with the convex region which it splits, the chopping - * hyperplanes are the cut hyperplanes closer to the tree root.</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. - - * @since 3.0 - */ -public interface SubHyperplane<S extends Space> { - - /** 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 sub-hyperplane, copy of the instance - */ - SubHyperplane<S> copySelf(); - - /** Get the underlying hyperplane. - * @return underlying hyperplane - */ - Hyperplane<S> getHyperplane(); - - /** Check if the instance is empty. - * @return true if the instance is empty - */ - boolean isEmpty(); - - /** Get the size of the instance. - * @return the size of the instance (this is a length in 1D, an area - * in 2D, a volume in 3D ...) - */ - double getSize(); - - /** Compute the relative position of the instance with respect - * to an hyperplane. - * @param hyperplane hyperplane to check instance against - * @return one of {@link Side#PLUS}, {@link Side#MINUS}, {@link Side#BOTH}, - * {@link Side#HYPER} - */ - Side side(Hyperplane<S> hyperplane); - - /** Split the instance in two parts by an hyperplane. - * @param hyperplane splitting hyperplane - * @return an object containing both the part of the instance - * on the plus side of the hyperplane and the part of the - * instance on the minus side of the hyperplane - */ - SplitSubHyperplane<S> split(Hyperplane<S> hyperplane); - - /** Compute the union of the instance and another sub-hyperplane. - * @param other other sub-hyperplane to union (<em>must</em> be in the - * same hyperplane as the instance) - * @return a new sub-hyperplane, union of the instance and other - */ - SubHyperplane<S> reunite(SubHyperplane<S> other); - - /** Class holding the results of the {@link #split split} method. - * @param <U> Type of the embedding space. - */ - public static class SplitSubHyperplane<U extends Space> { - - /** Part of the sub-hyperplane on the plus side of the splitting hyperplane. */ - private final SubHyperplane<U> plus; - - /** Part of the sub-hyperplane on the minus side of the splitting hyperplane. */ - private final SubHyperplane<U> minus; - - /** Build a SplitSubHyperplane from its parts. - * @param plus part of the sub-hyperplane on the plus side of the - * splitting hyperplane - * @param minus part of the sub-hyperplane on the minus side of the - * splitting hyperplane - */ - public SplitSubHyperplane(final SubHyperplane<U> plus, - final SubHyperplane<U> minus) { - this.plus = plus; - this.minus = minus; - } - - /** Get the part of the sub-hyperplane on the plus side of the splitting hyperplane. - * @return part of the sub-hyperplane on the plus side of the splitting hyperplane - */ - public SubHyperplane<U> getPlus() { - return plus; - } - - /** Get the part of the sub-hyperplane on the minus side of the splitting hyperplane. - * @return part of the sub-hyperplane on the minus side of the splitting hyperplane - */ - public SubHyperplane<U> getMinus() { - return minus; - } - - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/Transform.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/Transform.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/Transform.java deleted file mode 100644 index ba0c1dd..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/Transform.java +++ /dev/null @@ -1,80 +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 inversible affine transform in a space. - * <p>Inversible affine transform include for example scalings, - * translations, rotations.</p> - - * <p>Transforms are dimension-specific. The consistency rules between - * the three {@code apply} methods are the following ones for a - * transformed defined for dimension D:</p> - * <ul> - * <li> - * the transform can be applied to a point in the - * D-dimension space using its {@link #apply(Point)} - * method - * </li> - * <li> - * the transform can be applied to a (D-1)-dimension - * hyperplane in the D-dimension space using its - * {@link #apply(Hyperplane)} method - * </li> - * <li> - * the transform can be applied to a (D-2)-dimension - * sub-hyperplane in a (D-1)-dimension hyperplane using - * its {@link #apply(SubHyperplane, Hyperplane, Hyperplane)} - * method - * </li> - * </ul> - - * @param <S> Type of the embedding space. - * @param <T> Type of the embedded sub-space. - - * @since 3.0 - */ -public interface Transform<S extends Space, T extends Space> { - - /** Transform a point of a space. - * @param point point to transform - * @return a new object representing the transformed point - */ - Point<S> apply(Point<S> point); - - /** Transform an hyperplane of a space. - * @param hyperplane hyperplane to transform - * @return a new object representing the transformed hyperplane - */ - Hyperplane<S> apply(Hyperplane<S> hyperplane); - - /** Transform a sub-hyperplane embedded in an hyperplane. - * @param sub sub-hyperplane to transform - * @param original hyperplane in which the sub-hyperplane is - * defined (this is the original hyperplane, the transform has - * <em>not</em> been applied to it) - * @param transformed hyperplane in which the sub-hyperplane is - * defined (this is the transformed hyperplane, the transform - * <em>has</em> been applied to it) - * @return a new object representing the transformed sub-hyperplane - */ - SubHyperplane<T> apply(SubHyperplane<T> sub, Hyperplane<S> original, Hyperplane<S> transformed); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/package-info.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/package-info.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/package-info.java deleted file mode 100644 index 6e63c73..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/package-info.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. - */ -/** - * - * This package provides classes to implement Binary Space Partition trees. - * - * <p> - * {@link org.apache.commons.math3.geometry.partitioning.BSPTree BSP trees} - * are an efficient way to represent parts of space and in particular - * polytopes (line segments in 1D, polygons in 2D and polyhedrons in 3D) - * and to operate on them. The main principle is to recursively subdivide - * the space using simple hyperplanes (points in 1D, lines in 2D, planes - * in 3D). - * </p> - * - * <p> - * We start with a tree composed of a single node without any cut - * hyperplane: it represents the complete space, which is a convex - * part. If we add a cut hyperplane to this node, this represents a - * partition with the hyperplane at the node level and two half spaces at - * each side of the cut hyperplane. These half-spaces are represented by - * two child nodes without any cut hyperplanes associated, the plus child - * which represents the half space on the plus side of the cut hyperplane - * and the minus child on the other side. Continuing the subdivisions, we - * end up with a tree having internal nodes that are associated with a - * cut hyperplane and leaf nodes without any hyperplane which correspond - * to convex parts. - * </p> - * - * <p> - * When BSP trees are used to represent polytopes, the convex parts are - * known to be completely inside or outside the polytope as long as there - * is no facet in the part (which is obviously the case if the cut - * hyperplanes have been chosen as the underlying hyperplanes of the - * facets (this is called an autopartition) and if the subdivision - * process has been continued until all facets have been processed. It is - * important to note that the polytope is <em>not</em> defined by a - * single part, but by several convex ones. This is the property that - * allows BSP-trees to represent non-convex polytopes despites all parts - * are convex. The {@link - * org.apache.commons.math3.geometry.partitioning.Region Region} class is - * devoted to this representation, it is build on top of the {@link - * org.apache.commons.math3.geometry.partitioning.BSPTree BSPTree} class using - * boolean objects as the leaf nodes attributes to represent the - * inside/outside property of each leaf part, and also adds various - * methods dealing with boundaries (i.e. the separation between the - * inside and the outside parts). - * </p> - * - * <p> - * Rather than simply associating the internal nodes with an hyperplane, - * we consider <em>sub-hyperplanes</em> which correspond to the part of - * the hyperplane that is inside the convex part defined by all the - * parent nodes (this implies that the sub-hyperplane at root node is in - * fact a complete hyperplane, because there is no parent to bound - * it). Since the parts are convex, the sub-hyperplanes are convex, in - * 3D the convex parts are convex polyhedrons, and the sub-hyperplanes - * are convex polygons that cut these polyhedrons in two - * sub-polyhedrons. Using this definition, a BSP tree completely - * partitions the space. Each point either belongs to one of the - * sub-hyperplanes in an internal node or belongs to one of the leaf - * convex parts. - * </p> - * - * <p> - * In order to determine where a point is, it is sufficient to check its - * position with respect to the root cut hyperplane, to select the - * corresponding child tree and to repeat the procedure recursively, - * until either the point appears to be exactly on one of the hyperplanes - * in the middle of the tree or to be in one of the leaf parts. For - * this operation, it is sufficient to consider the complete hyperplanes, - * there is no need to check the points with the boundary of the - * sub-hyperplanes, because this check has in fact already been realized - * by the recursive descent in the tree. This is very easy to do and very - * efficient, especially if the tree is well balanced (the cost is - * <code>O(log(n))</code> where <code>n</code> is the number of facets) - * or if the first tree levels close to the root discriminate large parts - * of the total space. - * </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). The same paper can also be - * found <a - * href="http://www.cs.utexas.edu/users/fussell/courses/cs384g/bsp_treemerge.pdf";>here</a>. - * </p> - * - * <p> - * Note that the interfaces defined in this package are <em>not</em> intended to - * be implemented by Apache Commons Math users, they are 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> - * - */ -package org.apache.commons.math3.geometry.partitioning; http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/AVLTree.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/AVLTree.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/AVLTree.java deleted file mode 100644 index 9412421..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/AVLTree.java +++ /dev/null @@ -1,634 +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.utilities; - -/** This class implements AVL trees. - * - * <p>The purpose of this class is to sort elements while allowing - * duplicate elements (i.e. such that {@code a.equals(b)} is - * true). The {@code SortedSet} interface does not allow this, so - * a specific class is needed. Null elements are not allowed.</p> - * - * <p>Since the {@code equals} method is not sufficient to - * differentiate elements, the {@link #delete delete} method is - * implemented using the equality operator.</p> - * - * <p>In order to clearly mark the methods provided here do not have - * the same semantics as the ones specified in the - * {@code SortedSet} interface, different names are used - * ({@code add} has been replaced by {@link #insert insert} and - * {@code remove} has been replaced by {@link #delete - * delete}).</p> - * - * <p>This class is based on the C implementation Georg Kraml has put - * in the public domain. Unfortunately, his <a - * href="www.purists.org/georg/avltree/index.html">page</a> seems not - * to exist any more.</p> - * - * @param <T> the type of the elements - * - * @since 3.0 - * @deprecated as of 3.4, this class is not used anymore and considered - * to be out of scope of Apache Commons Math - */ -@Deprecated -public class AVLTree<T extends Comparable<T>> { - - /** Top level node. */ - private Node top; - - /** Build an empty tree. - */ - public AVLTree() { - top = null; - } - - /** Insert an element in the tree. - * @param element element to insert (silently ignored if null) - */ - public void insert(final T element) { - if (element != null) { - if (top == null) { - top = new Node(element, null); - } else { - top.insert(element); - } - } - } - - /** Delete an element from the tree. - * <p>The element is deleted only if there is a node {@code n} - * containing exactly the element instance specified, i.e. for which - * {@code n.getElement() == element}. This is purposely - * <em>different</em> from the specification of the - * {@code java.util.Set} {@code remove} method (in fact, - * this is the reason why a specific class has been developed).</p> - * @param element element to delete (silently ignored if null) - * @return true if the element was deleted from the tree - */ - public boolean delete(final T element) { - if (element != null) { - for (Node node = getNotSmaller(element); node != null; node = node.getNext()) { - // loop over all elements neither smaller nor larger - // than the specified one - if (node.element == element) { - node.delete(); - return true; - } else if (node.element.compareTo(element) > 0) { - // all the remaining elements are known to be larger, - // the element is not in the tree - return false; - } - } - } - return false; - } - - /** Check if the tree is empty. - * @return true if the tree is empty - */ - public boolean isEmpty() { - return top == null; - } - - - /** Get the number of elements of the tree. - * @return number of elements contained in the tree - */ - public int size() { - return (top == null) ? 0 : top.size(); - } - - /** Get the node whose element is the smallest one in the tree. - * @return the tree node containing the smallest element in the tree - * or null if the tree is empty - * @see #getLargest - * @see #getNotSmaller - * @see #getNotLarger - * @see Node#getPrevious - * @see Node#getNext - */ - public Node getSmallest() { - return (top == null) ? null : top.getSmallest(); - } - - /** Get the node whose element is the largest one in the tree. - * @return the tree node containing the largest element in the tree - * or null if the tree is empty - * @see #getSmallest - * @see #getNotSmaller - * @see #getNotLarger - * @see Node#getPrevious - * @see Node#getNext - */ - public Node getLargest() { - return (top == null) ? null : top.getLargest(); - } - - /** Get the node whose element is not smaller than the reference object. - * @param reference reference object (may not be in the tree) - * @return the tree node containing the smallest element not smaller - * than the reference object or null if either the tree is empty or - * all its elements are smaller than the reference object - * @see #getSmallest - * @see #getLargest - * @see #getNotLarger - * @see Node#getPrevious - * @see Node#getNext - */ - public Node getNotSmaller(final T reference) { - Node candidate = null; - for (Node node = top; node != null;) { - if (node.element.compareTo(reference) < 0) { - if (node.right == null) { - return candidate; - } - node = node.right; - } else { - candidate = node; - if (node.left == null) { - return candidate; - } - node = node.left; - } - } - return null; - } - - /** Get the node whose element is not larger than the reference object. - * @param reference reference object (may not be in the tree) - * @return the tree node containing the largest element not larger - * than the reference object (in which case the node is guaranteed - * not to be empty) or null if either the tree is empty or all its - * elements are larger than the reference object - * @see #getSmallest - * @see #getLargest - * @see #getNotSmaller - * @see Node#getPrevious - * @see Node#getNext - */ - public Node getNotLarger(final T reference) { - Node candidate = null; - for (Node node = top; node != null;) { - if (node.element.compareTo(reference) > 0) { - if (node.left == null) { - return candidate; - } - node = node.left; - } else { - candidate = node; - if (node.right == null) { - return candidate; - } - node = node.right; - } - } - return null; - } - - /** Enum for tree skew factor. */ - private static enum Skew { - /** Code for left high trees. */ - LEFT_HIGH, - - /** Code for right high trees. */ - RIGHT_HIGH, - - /** Code for Skew.BALANCED trees. */ - BALANCED; - } - - /** This class implements AVL trees nodes. - * <p>AVL tree nodes implement all the logical structure of the - * tree. Nodes are created by the {@link AVLTree AVLTree} class.</p> - * <p>The nodes are not independant from each other but must obey - * specific balancing constraints and the tree structure is - * rearranged as elements are inserted or deleted from the tree. The - * creation, modification and tree-related navigation methods have - * therefore restricted access. Only the order-related navigation, - * reading and delete methods are public.</p> - * @see AVLTree - */ - public class Node { - - /** Element contained in the current node. */ - private T element; - - /** Left sub-tree. */ - private Node left; - - /** Right sub-tree. */ - private Node right; - - /** Parent tree. */ - private Node parent; - - /** Skew factor. */ - private Skew skew; - - /** Build a node for a specified element. - * @param element element - * @param parent parent node - */ - Node(final T element, final Node parent) { - this.element = element; - left = null; - right = null; - this.parent = parent; - skew = Skew.BALANCED; - } - - /** Get the contained element. - * @return element contained in the node - */ - public T getElement() { - return element; - } - - /** Get the number of elements of the tree rooted at this node. - * @return number of elements contained in the tree rooted at this node - */ - int size() { - return 1 + ((left == null) ? 0 : left.size()) + ((right == null) ? 0 : right.size()); - } - - /** Get the node whose element is the smallest one in the tree - * rooted at this node. - * @return the tree node containing the smallest element in the - * tree rooted at this node or null if the tree is empty - * @see #getLargest - */ - Node getSmallest() { - Node node = this; - while (node.left != null) { - node = node.left; - } - return node; - } - - /** Get the node whose element is the largest one in the tree - * rooted at this node. - * @return the tree node containing the largest element in the - * tree rooted at this node or null if the tree is empty - * @see #getSmallest - */ - Node getLargest() { - Node node = this; - while (node.right != null) { - node = node.right; - } - return node; - } - - /** Get the node containing the next smaller or equal element. - * @return node containing the next smaller or equal element or - * null if there is no smaller or equal element in the tree - * @see #getNext - */ - public Node getPrevious() { - - if (left != null) { - final Node node = left.getLargest(); - if (node != null) { - return node; - } - } - - for (Node node = this; node.parent != null; node = node.parent) { - if (node != node.parent.left) { - return node.parent; - } - } - - return null; - - } - - /** Get the node containing the next larger or equal element. - * @return node containing the next larger or equal element (in - * which case the node is guaranteed not to be empty) or null if - * there is no larger or equal element in the tree - * @see #getPrevious - */ - public Node getNext() { - - if (right != null) { - final Node node = right.getSmallest(); - if (node != null) { - return node; - } - } - - for (Node node = this; node.parent != null; node = node.parent) { - if (node != node.parent.right) { - return node.parent; - } - } - - return null; - - } - - /** Insert an element in a sub-tree. - * @param newElement element to insert - * @return true if the parent tree should be re-Skew.BALANCED - */ - boolean insert(final T newElement) { - if (newElement.compareTo(this.element) < 0) { - // the inserted element is smaller than the node - if (left == null) { - left = new Node(newElement, this); - return rebalanceLeftGrown(); - } - return left.insert(newElement) ? rebalanceLeftGrown() : false; - } - - // the inserted element is equal to or greater than the node - if (right == null) { - right = new Node(newElement, this); - return rebalanceRightGrown(); - } - return right.insert(newElement) ? rebalanceRightGrown() : false; - - } - - /** Delete the node from the tree. - */ - public void delete() { - if ((parent == null) && (left == null) && (right == null)) { - // this was the last node, the tree is now empty - element = null; - top = null; - } else { - - Node node; - Node child; - boolean leftShrunk; - if ((left == null) && (right == null)) { - node = this; - element = null; - leftShrunk = node == node.parent.left; - child = null; - } else { - node = (left != null) ? left.getLargest() : right.getSmallest(); - element = node.element; - leftShrunk = node == node.parent.left; - child = (node.left != null) ? node.left : node.right; - } - - node = node.parent; - if (leftShrunk) { - node.left = child; - } else { - node.right = child; - } - if (child != null) { - child.parent = node; - } - - while (leftShrunk ? node.rebalanceLeftShrunk() : node.rebalanceRightShrunk()) { - if (node.parent == null) { - return; - } - leftShrunk = node == node.parent.left; - node = node.parent; - } - - } - } - - /** Re-balance the instance as left sub-tree has grown. - * @return true if the parent tree should be reSkew.BALANCED too - */ - private boolean rebalanceLeftGrown() { - switch (skew) { - case LEFT_HIGH: - if (left.skew == Skew.LEFT_HIGH) { - rotateCW(); - skew = Skew.BALANCED; - right.skew = Skew.BALANCED; - } else { - final Skew s = left.right.skew; - left.rotateCCW(); - rotateCW(); - switch(s) { - case LEFT_HIGH: - left.skew = Skew.BALANCED; - right.skew = Skew.RIGHT_HIGH; - break; - case RIGHT_HIGH: - left.skew = Skew.LEFT_HIGH; - right.skew = Skew.BALANCED; - break; - default: - left.skew = Skew.BALANCED; - right.skew = Skew.BALANCED; - } - skew = Skew.BALANCED; - } - return false; - case RIGHT_HIGH: - skew = Skew.BALANCED; - return false; - default: - skew = Skew.LEFT_HIGH; - return true; - } - } - - /** Re-balance the instance as right sub-tree has grown. - * @return true if the parent tree should be reSkew.BALANCED too - */ - private boolean rebalanceRightGrown() { - switch (skew) { - case LEFT_HIGH: - skew = Skew.BALANCED; - return false; - case RIGHT_HIGH: - if (right.skew == Skew.RIGHT_HIGH) { - rotateCCW(); - skew = Skew.BALANCED; - left.skew = Skew.BALANCED; - } else { - final Skew s = right.left.skew; - right.rotateCW(); - rotateCCW(); - switch (s) { - case LEFT_HIGH: - left.skew = Skew.BALANCED; - right.skew = Skew.RIGHT_HIGH; - break; - case RIGHT_HIGH: - left.skew = Skew.LEFT_HIGH; - right.skew = Skew.BALANCED; - break; - default: - left.skew = Skew.BALANCED; - right.skew = Skew.BALANCED; - } - skew = Skew.BALANCED; - } - return false; - default: - skew = Skew.RIGHT_HIGH; - return true; - } - } - - /** Re-balance the instance as left sub-tree has shrunk. - * @return true if the parent tree should be reSkew.BALANCED too - */ - private boolean rebalanceLeftShrunk() { - switch (skew) { - case LEFT_HIGH: - skew = Skew.BALANCED; - return true; - case RIGHT_HIGH: - if (right.skew == Skew.RIGHT_HIGH) { - rotateCCW(); - skew = Skew.BALANCED; - left.skew = Skew.BALANCED; - return true; - } else if (right.skew == Skew.BALANCED) { - rotateCCW(); - skew = Skew.LEFT_HIGH; - left.skew = Skew.RIGHT_HIGH; - return false; - } else { - final Skew s = right.left.skew; - right.rotateCW(); - rotateCCW(); - switch (s) { - case LEFT_HIGH: - left.skew = Skew.BALANCED; - right.skew = Skew.RIGHT_HIGH; - break; - case RIGHT_HIGH: - left.skew = Skew.LEFT_HIGH; - right.skew = Skew.BALANCED; - break; - default: - left.skew = Skew.BALANCED; - right.skew = Skew.BALANCED; - } - skew = Skew.BALANCED; - return true; - } - default: - skew = Skew.RIGHT_HIGH; - return false; - } - } - - /** Re-balance the instance as right sub-tree has shrunk. - * @return true if the parent tree should be reSkew.BALANCED too - */ - private boolean rebalanceRightShrunk() { - switch (skew) { - case RIGHT_HIGH: - skew = Skew.BALANCED; - return true; - case LEFT_HIGH: - if (left.skew == Skew.LEFT_HIGH) { - rotateCW(); - skew = Skew.BALANCED; - right.skew = Skew.BALANCED; - return true; - } else if (left.skew == Skew.BALANCED) { - rotateCW(); - skew = Skew.RIGHT_HIGH; - right.skew = Skew.LEFT_HIGH; - return false; - } else { - final Skew s = left.right.skew; - left.rotateCCW(); - rotateCW(); - switch (s) { - case LEFT_HIGH: - left.skew = Skew.BALANCED; - right.skew = Skew.RIGHT_HIGH; - break; - case RIGHT_HIGH: - left.skew = Skew.LEFT_HIGH; - right.skew = Skew.BALANCED; - break; - default: - left.skew = Skew.BALANCED; - right.skew = Skew.BALANCED; - } - skew = Skew.BALANCED; - return true; - } - default: - skew = Skew.LEFT_HIGH; - return false; - } - } - - /** Perform a clockwise rotation rooted at the instance. - * <p>The skew factor are not updated by this method, they - * <em>must</em> be updated by the caller</p> - */ - private void rotateCW() { - - final T tmpElt = element; - element = left.element; - left.element = tmpElt; - - final Node tmpNode = left; - left = tmpNode.left; - tmpNode.left = tmpNode.right; - tmpNode.right = right; - right = tmpNode; - - if (left != null) { - left.parent = this; - } - if (right.right != null) { - right.right.parent = right; - } - - } - - /** Perform a counter-clockwise rotation rooted at the instance. - * <p>The skew factor are not updated by this method, they - * <em>must</em> be updated by the caller</p> - */ - private void rotateCCW() { - - final T tmpElt = element; - element = right.element; - right.element = tmpElt; - - final Node tmpNode = right; - right = tmpNode.right; - tmpNode.right = tmpNode.left; - tmpNode.left = left; - left = tmpNode; - - if (right != null) { - right.parent = this; - } - if (left.left != null) { - left.left.parent = left; - } - - } - - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/OrderedTuple.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/OrderedTuple.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/OrderedTuple.java deleted file mode 100644 index 2dad2d7..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/OrderedTuple.java +++ /dev/null @@ -1,431 +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.utilities; - -import java.util.Arrays; - -import org.apache.commons.math3.util.FastMath; - -/** This class implements an ordering operation for T-uples. - * - * <p>Ordering is done by encoding all components of the T-uple into a - * single scalar value and using this value as the sorting - * key. Encoding is performed using the method invented by Georg - * Cantor in 1877 when he proved it was possible to establish a - * bijection between a line and a plane. The binary representations of - * the components of the T-uple are mixed together to form a single - * scalar. This means that the 2<sup>k</sup> bit of component 0 is - * followed by the 2<sup>k</sup> bit of component 1, then by the - * 2<sup>k</sup> bit of component 2 up to the 2<sup>k</sup> bit of - * component {@code t}, which is followed by the 2<sup>k-1</sup> - * bit of component 0, followed by the 2<sup>k-1</sup> bit of - * component 1 ... The binary representations are extended as needed - * to handle numbers with different scales and a suitable - * 2<sup>p</sup> offset is added to the components in order to avoid - * negative numbers (this offset is adjusted as needed during the - * comparison operations).</p> - * - * <p>The more interesting property of the encoding method for our - * purpose is that it allows to select all the points that are in a - * given range. This is depicted in dimension 2 by the following - * picture:</p> - * - * <img src="doc-files/OrderedTuple.png" /> - * - * <p>This picture shows a set of 100000 random 2-D pairs having their - * first component between -50 and +150 and their second component - * between -350 and +50. We wanted to extract all pairs having their - * first component between +30 and +70 and their second component - * between -120 and -30. We built the lower left point at coordinates - * (30, -120) and the upper right point at coordinates (70, -30). All - * points smaller than the lower left point are drawn in red and all - * points larger than the upper right point are drawn in blue. The - * green points are between the two limits. This picture shows that - * all the desired points are selected, along with spurious points. In - * this case, we get 15790 points, 4420 of which really belonging to - * the desired rectangle. It is possible to extract very small - * subsets. As an example extracting from the same 100000 points set - * the points having their first component between +30 and +31 and - * their second component between -91 and -90, we get a subset of 11 - * points, 2 of which really belonging to the desired rectangle.</p> - * - * <p>the previous selection technique can be applied in all - * dimensions, still using two points to define the interval. The - * first point will have all its components set to their lower bounds - * while the second point will have all its components set to their - * upper bounds.</p> - * - * <p>T-uples with negative infinite or positive infinite components - * are sorted logically.</p> - * - * <p>Since the specification of the {@code Comparator} interface - * allows only {@code ClassCastException} errors, some arbitrary - * choices have been made to handle specific cases. The rationale for - * these choices is to keep <em>regular</em> and consistent T-uples - * together.</p> - * <ul> - * <li>instances with different dimensions are sorted according to - * their dimension regardless of their components values</li> - * <li>instances with {@code Double.NaN} components are sorted - * after all other ones (even after instances with positive infinite - * components</li> - * <li>instances with both positive and negative infinite components - * are considered as if they had {@code Double.NaN} - * components</li> - * </ul> - * - * @since 3.0 - * @deprecated as of 3.4, this class is not used anymore and considered - * to be out of scope of Apache Commons Math - */ -@Deprecated -public class OrderedTuple implements Comparable<OrderedTuple> { - - /** Sign bit mask. */ - private static final long SIGN_MASK = 0x8000000000000000L; - - /** Exponent bits mask. */ - private static final long EXPONENT_MASK = 0x7ff0000000000000L; - - /** Mantissa bits mask. */ - private static final long MANTISSA_MASK = 0x000fffffffffffffL; - - /** Implicit MSB for normalized numbers. */ - private static final long IMPLICIT_ONE = 0x0010000000000000L; - - /** Double components of the T-uple. */ - private double[] components; - - /** Offset scale. */ - private int offset; - - /** Least Significant Bit scale. */ - private int lsb; - - /** Ordering encoding of the double components. */ - private long[] encoding; - - /** Positive infinity marker. */ - private boolean posInf; - - /** Negative infinity marker. */ - private boolean negInf; - - /** Not A Number marker. */ - private boolean nan; - - /** Build an ordered T-uple from its components. - * @param components double components of the T-uple - */ - public OrderedTuple(final double ... components) { - this.components = components.clone(); - int msb = Integer.MIN_VALUE; - lsb = Integer.MAX_VALUE; - posInf = false; - negInf = false; - nan = false; - for (int i = 0; i < components.length; ++i) { - if (Double.isInfinite(components[i])) { - if (components[i] < 0) { - negInf = true; - } else { - posInf = true; - } - } else if (Double.isNaN(components[i])) { - nan = true; - } else { - final long b = Double.doubleToLongBits(components[i]); - final long m = mantissa(b); - if (m != 0) { - final int e = exponent(b); - msb = FastMath.max(msb, e + computeMSB(m)); - lsb = FastMath.min(lsb, e + computeLSB(m)); - } - } - } - - if (posInf && negInf) { - // instance cannot be sorted logically - posInf = false; - negInf = false; - nan = true; - } - - if (lsb <= msb) { - // encode the T-upple with the specified offset - encode(msb + 16); - } else { - encoding = new long[] { - 0x0L - }; - } - - } - - /** Encode the T-uple with a given offset. - * @param minOffset minimal scale of the offset to add to all - * components (must be greater than the MSBs of all components) - */ - private void encode(final int minOffset) { - - // choose an offset with some margins - offset = minOffset + 31; - offset -= offset % 32; - - if ((encoding != null) && (encoding.length == 1) && (encoding[0] == 0x0L)) { - // the components are all zeroes - return; - } - - // allocate an integer array to encode the components (we use only - // 63 bits per element because there is no unsigned long in Java) - final int neededBits = offset + 1 - lsb; - final int neededLongs = (neededBits + 62) / 63; - encoding = new long[components.length * neededLongs]; - - // mix the bits from all components - int eIndex = 0; - int shift = 62; - long word = 0x0L; - for (int k = offset; eIndex < encoding.length; --k) { - for (int vIndex = 0; vIndex < components.length; ++vIndex) { - if (getBit(vIndex, k) != 0) { - word |= 0x1L << shift; - } - if (shift-- == 0) { - encoding[eIndex++] = word; - word = 0x0L; - shift = 62; - } - } - } - - } - - /** Compares this ordered T-uple with the specified object. - - * <p>The ordering method is detailed in the general description of - * the class. Its main property is to be consistent with distance: - * geometrically close T-uples stay close to each other when stored - * in a sorted collection using this comparison method.</p> - - * <p>T-uples with negative infinite, positive infinite are sorted - * logically.</p> - - * <p>Some arbitrary choices have been made to handle specific - * cases. The rationale for these choices is to keep - * <em>normal</em> and consistent T-uples together.</p> - * <ul> - * <li>instances with different dimensions are sorted according to - * their dimension regardless of their components values</li> - * <li>instances with {@code Double.NaN} components are sorted - * after all other ones (evan after instances with positive infinite - * components</li> - * <li>instances with both positive and negative infinite components - * are considered as if they had {@code Double.NaN} - * components</li> - * </ul> - - * @param ot T-uple to compare instance with - * @return a negative integer if the instance is less than the - * object, zero if they are equal, or a positive integer if the - * instance is greater than the object - - */ - public int compareTo(final OrderedTuple ot) { - if (components.length == ot.components.length) { - if (nan) { - return +1; - } else if (ot.nan) { - return -1; - } else if (negInf || ot.posInf) { - return -1; - } else if (posInf || ot.negInf) { - return +1; - } else { - - if (offset < ot.offset) { - encode(ot.offset); - } else if (offset > ot.offset) { - ot.encode(offset); - } - - final int limit = FastMath.min(encoding.length, ot.encoding.length); - for (int i = 0; i < limit; ++i) { - if (encoding[i] < ot.encoding[i]) { - return -1; - } else if (encoding[i] > ot.encoding[i]) { - return +1; - } - } - - if (encoding.length < ot.encoding.length) { - return -1; - } else if (encoding.length > ot.encoding.length) { - return +1; - } else { - return 0; - } - - } - } - - return components.length - ot.components.length; - - } - - /** {@inheritDoc} */ - @Override - public boolean equals(final Object other) { - if (this == other) { - return true; - } else if (other instanceof OrderedTuple) { - return compareTo((OrderedTuple) other) == 0; - } else { - return false; - } - } - - /** {@inheritDoc} */ - @Override - public int hashCode() { - // the following constants are arbitrary small primes - final int multiplier = 37; - final int trueHash = 97; - final int falseHash = 71; - - // hash fields and combine them - // (we rely on the multiplier to have different combined weights - // for all int fields and all boolean fields) - int hash = Arrays.hashCode(components); - hash = hash * multiplier + offset; - hash = hash * multiplier + lsb; - hash = hash * multiplier + (posInf ? trueHash : falseHash); - hash = hash * multiplier + (negInf ? trueHash : falseHash); - hash = hash * multiplier + (nan ? trueHash : falseHash); - - return hash; - - } - - /** Get the components array. - * @return array containing the T-uple components - */ - public double[] getComponents() { - return components.clone(); - } - - /** Extract the sign from the bits of a double. - * @param bits binary representation of the double - * @return sign bit (zero if positive, non zero if negative) - */ - private static long sign(final long bits) { - return bits & SIGN_MASK; - } - - /** Extract the exponent from the bits of a double. - * @param bits binary representation of the double - * @return exponent - */ - private static int exponent(final long bits) { - return ((int) ((bits & EXPONENT_MASK) >> 52)) - 1075; - } - - /** Extract the mantissa from the bits of a double. - * @param bits binary representation of the double - * @return mantissa - */ - private static long mantissa(final long bits) { - return ((bits & EXPONENT_MASK) == 0) ? - ((bits & MANTISSA_MASK) << 1) : // subnormal number - (IMPLICIT_ONE | (bits & MANTISSA_MASK)); // normal number - } - - /** Compute the most significant bit of a long. - * @param l long from which the most significant bit is requested - * @return scale of the most significant bit of {@code l}, - * or 0 if {@code l} is zero - * @see #computeLSB - */ - private static int computeMSB(final long l) { - - long ll = l; - long mask = 0xffffffffL; - int scale = 32; - int msb = 0; - - while (scale != 0) { - if ((ll & mask) != ll) { - msb |= scale; - ll >>= scale; - } - scale >>= 1; - mask >>= scale; - } - - return msb; - - } - - /** Compute the least significant bit of a long. - * @param l long from which the least significant bit is requested - * @return scale of the least significant bit of {@code l}, - * or 63 if {@code l} is zero - * @see #computeMSB - */ - private static int computeLSB(final long l) { - - long ll = l; - long mask = 0xffffffff00000000L; - int scale = 32; - int lsb = 0; - - while (scale != 0) { - if ((ll & mask) == ll) { - lsb |= scale; - ll >>= scale; - } - scale >>= 1; - mask >>= scale; - } - - return lsb; - - } - - /** Get a bit from the mantissa of a double. - * @param i index of the component - * @param k scale of the requested bit - * @return the specified bit (either 0 or 1), after the offset has - * been added to the double - */ - private int getBit(final int i, final int k) { - final long bits = Double.doubleToLongBits(components[i]); - final int e = exponent(bits); - if ((k < e) || (k > offset)) { - return 0; - } else if (k == offset) { - return (sign(bits) == 0L) ? 1 : 0; - } else if (k > (e + 52)) { - return (sign(bits) == 0L) ? 0 : 1; - } else { - final long m = (sign(bits) == 0L) ? mantissa(bits) : -mantissa(bits); - return (int) ((m >> (k - e)) & 0x1L); - } - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/doc-files/OrderedTuple.png ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/doc-files/OrderedTuple.png b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/doc-files/OrderedTuple.png deleted file mode 100644 index 4eca233..0000000 Binary files a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/doc-files/OrderedTuple.png and /dev/null differ http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/package-info.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/package-info.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/package-info.java deleted file mode 100644 index 31f57f1..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/utilities/package-info.java +++ /dev/null @@ -1,24 +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. - */ -/** - * - * <p> - * This package provides multidimensional ordering features for partitioning. - * </p> - * - */ -package org.apache.commons.math3.geometry.partitioning.utilities;
