commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r1131125 [1/2] - in /commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning: ./ utilities/
Date Fri, 03 Jun 2011 18:06:22 GMT
Author: luc
Date: Fri Jun  3 18:06:21 2011
New Revision: 1131125

URL: http://svn.apache.org/viewvc?rev=1131125&view=rev
Log:
Improved type safety for Binary Space Partitioning and reduced complexity,
using generics where it was relevant and reorganizing interfaces.

Added:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java   (with props)
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java   (with props)
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java   (with props)
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java   (with props)
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/RegionFactory.java   (with props)
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Side.java   (with props)
Removed:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/SubSpace.java
Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Region.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/SubHyperplane.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Transform.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/utilities/AVLTree.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/utilities/OrderedTuple.java

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java?rev=1131125&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java Fri Jun  3 18:06:21 2011
@@ -0,0 +1,641 @@
+/*
+ * 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.math.geometry.partitioning;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.TreeSet;
+
+import org.apache.commons.math.geometry.Space;
+import org.apache.commons.math.geometry.Vector;
+
+/** Abstract class for all regions, independently of geometry type or dimension.
+
+ * @param <S> Type of the space.
+ * @param <T> Type of the sub-space.
+
+ * @version $Id:$
+ * @since 3.0
+ */
+public abstract class AbstractRegion<S extends Space, T extends Space> implements Region<S> {
+
+    /** Inside/Outside BSP tree. */
+    private BSPTree<S> tree;
+
+    /** Size of the instance. */
+    private double size;
+
+    /** Barycenter. */
+    private Vector<S> barycenter;
+
+    /** Build a region representing the whole space.
+     */
+    protected AbstractRegion() {
+        tree = new BSPTree<S>(Boolean.TRUE);
+    }
+
+    /** Build a region from an inside/outside BSP tree.
+     * <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 tree inside/outside BSP tree representing the region
+     */
+    protected AbstractRegion(final BSPTree<S> tree) {
+        this.tree = tree;
+    }
+
+    /** Build a Region from a Boundary REPresentation (B-rep).
+     * <p>The boundary is provided as a collection of {@link
+     * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
+     * interior part of the region on its minus side and the exterior on
+     * its plus side.</p>
+     * <p>The boundary elements can be in any order, and can form
+     * several non-connected sets (like for example polygons with holes
+     * or a set of disjoints polyhedrons considered as a whole). In
+     * fact, the elements do not even need to be connected together
+     * (their topological connections are not used here). However, if the
+     * boundary does not really separate an inside open from an outside
+     * open (open having here its topological meaning), then subsequent
+     * calls to the {@link #checkPoint(Vector) checkPoint} method will not be
+     * meaningful anymore.</p>
+     * <p>If the boundary is empty, the region will represent the whole
+     * space.</p>
+     * @param boundary collection of boundary elements, as a
+     * collection of {@link SubHyperplane SubHyperplane} objects
+     */
+    protected AbstractRegion(final Collection<SubHyperplane<S>> boundary) {
+
+        if (boundary.size() == 0) {
+
+            // the tree represents the whole space
+            tree = new BSPTree<S>(Boolean.TRUE);
+
+        } else {
+
+            // sort the boundary elements in decreasing size order
+            // (we don't want equal size elements to be removed, so
+            // we use a trick to fool the TreeSet)
+            final TreeSet<SubHyperplane<S>> ordered = new TreeSet<SubHyperplane<S>>(new Comparator<SubHyperplane<S>>() {
+                public int compare(final SubHyperplane<S> o1, final SubHyperplane<S> o2) {
+                    final double size1 = o1.getSize();
+                    final double size2 = o2.getSize();
+                    return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1);
+                }
+            });
+            ordered.addAll(boundary);
+
+            // build the tree top-down
+            tree = new BSPTree<S>();
+            insertCuts(tree, ordered);
+
+            // set up the inside/outside flags
+            tree.visit(new BSPTreeVisitor<S>() {
+
+                /** {@inheritDoc} */
+                public Order visitOrder(final BSPTree<S> node) {
+                    return Order.PLUS_SUB_MINUS;
+                }
+
+                /** {@inheritDoc} */
+                public void visitInternalNode(final BSPTree<S> node) {
+                }
+
+                /** {@inheritDoc} */
+                public void visitLeafNode(final BSPTree<S> node) {
+                    node.setAttribute((node == node.getParent().getPlus()) ?
+                                                                            Boolean.FALSE : Boolean.TRUE);
+                }
+            });
+
+        }
+
+    }
+
+    /** {@inheritDoc} */
+    public abstract AbstractRegion<S, T> buildNew(BSPTree<S> newTree);
+
+    /** Recursively build a tree by inserting cut sub-hyperplanes.
+     * @param node current tree node (it is a leaf node at the beginning
+     * of the call)
+     * @param boundary collection of edges belonging to the cell defined
+     * by the node
+     */
+    private void insertCuts(final BSPTree<S> node, final Collection<SubHyperplane<S>> boundary) {
+
+        final Iterator<SubHyperplane<S>> iterator = boundary.iterator();
+
+        // build the current level
+        Hyperplane<S> inserted = null;
+        while ((inserted == null) && iterator.hasNext()) {
+            inserted = iterator.next().getHyperplane();
+            if (!node.insertCut(inserted.copySelf())) {
+                inserted = null;
+            }
+        }
+
+        if (!iterator.hasNext()) {
+            return;
+        }
+
+        // distribute the remaining edges in the two sub-trees
+        final ArrayList<SubHyperplane<S>> plusList  = new ArrayList<SubHyperplane<S>>();
+        final ArrayList<SubHyperplane<S>> minusList = new ArrayList<SubHyperplane<S>>();
+        while (iterator.hasNext()) {
+            final SubHyperplane<S> other = iterator.next();
+            switch (other.side(inserted)) {
+            case PLUS:
+                plusList.add(other);
+                break;
+            case MINUS:
+                minusList.add(other);
+                break;
+            case BOTH:
+                final SubHyperplane.SplitSubHyperplane<S> split = other.split(inserted);
+                plusList.add(split.getPlus());
+                minusList.add(split.getMinus());
+                break;
+            default:
+                // ignore the sub-hyperplanes belonging to the cut hyperplane
+            }
+        }
+
+        // recurse through lower levels
+        insertCuts(node.getPlus(),  plusList);
+        insertCuts(node.getMinus(), minusList);
+
+    }
+
+    /** Build a convex region from an array of bounding hyperplanes.
+     * @param hyperplanes array of bounding hyperplanes (if null, an
+     * empty region will be built)
+     * @return a new convex region, or null if the collection is empty
+     */
+    public AbstractRegion(final Hyperplane<S>[] hyperplanes) {
+        if ((hyperplanes == null) || (hyperplanes.length == 0)) {
+            tree = new BSPTree<S>(Boolean.FALSE);
+        } else {
+
+            // use the first hyperplane to build the right class
+            tree = hyperplanes[0].wholeSpace().getTree(false);
+
+            // chop off parts of the space
+            BSPTree<S> node = tree;
+            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);
+                }
+            }
+
+        }
+
+    }
+
+    /** {@inheritDoc} */
+    public AbstractRegion<S, T> copySelf() {
+        return buildNew(tree.copySelf());
+    }
+
+    /** {@inheritDoc} */
+    public boolean isEmpty() {
+        return isEmpty(tree);
+    }
+
+    /** {@inheritDoc} */
+    public boolean isEmpty(final BSPTree<S> node) {
+
+        // we use a recursive function rather than the BSPTreeVisitor
+        // interface because we can stop visiting the tree as soon as we
+        // have found an inside cell
+
+        if (node.getCut() == null) {
+            // if we find an inside node, the region is not empty
+            return !((Boolean) node.getAttribute());
+        }
+
+        // check both sides of the sub-tree
+        return isEmpty(node.getMinus()) && isEmpty(node.getPlus());
+
+    }
+
+    /** {@inheritDoc} */
+    public boolean contains(final Region<S> region) {
+        return new RegionFactory<S>().difference(region, this).isEmpty();
+    }
+
+    /** {@inheritDoc} */
+    public Location checkPoint(final Vector<S> point) {
+        return checkPoint(tree, point);
+    }
+
+    /** Check a point with respect to the region starting at a given node.
+     * @param node root node of 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}
+     */
+    protected Location checkPoint(final BSPTree<S> node, final Vector<S> point) {
+        final BSPTree<S> cell = node.getCell(point);
+        if (cell.getCut() == null) {
+            // the point is in the interior of a cell, just check the attribute
+            return ((Boolean) cell.getAttribute()) ? Location.INSIDE : Location.OUTSIDE;
+        }
+
+        // the point is on a cut-sub-hyperplane, is it on a boundary ?
+        final Location minusCode = checkPoint(cell.getMinus(), point);
+        final Location plusCode  = checkPoint(cell.getPlus(),  point);
+        return (minusCode == plusCode) ? minusCode : Location.BOUNDARY;
+
+    }
+
+    /** {@inheritDoc} */
+    public BSPTree<S> getTree(final boolean includeBoundaryAttributes) {
+        if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) {
+            // we need to compute the boundary attributes
+            recurseBuildBoundary(tree);
+        }
+        return tree;
+    }
+
+    /** Recursively build the boundary shell tree.
+     * @param node current node in the inout tree
+     */
+    private void recurseBuildBoundary(final BSPTree<S> node) {
+        if (node.getCut() != null) {
+
+            SubHyperplane<S> plusOutside = null;
+            SubHyperplane<S> plusInside  = null;
+
+            // characterize the cut sub-hyperplane,
+            // first with respect to the plus sub-tree
+            final Characterization<S> plusChar = new Characterization<S>();
+            characterize(node.getPlus(), node.getCut().copySelf(), plusChar);
+
+            if (plusChar.hasOut()) {
+                // plusChar.out 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>();
+                characterize(node.getMinus(), plusChar.getOut(), minusChar);
+                if (minusChar.hasIn()) {
+                    plusOutside = minusChar.getIn();
+                }
+            }
+
+            if (plusChar.hasIn()) {
+                // plusChar.in 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>();
+                characterize(node.getMinus(), plusChar.getIn(), minusChar);
+                if (minusChar.hasOut()) {
+                    plusInside = minusChar.getOut();
+                }
+            }
+
+            node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside));
+            recurseBuildBoundary(node.getPlus());
+            recurseBuildBoundary(node.getMinus());
+
+        }
+    }
+
+    /** 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 one 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 characterization placeholder where to put the characterized parts
+     */
+    private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub,
+                              final Characterization<S> characterization) {
+        if (node.getCut() == null) {
+            // we have reached a leaf node
+            final boolean inside = (Boolean) node.getAttribute();
+            characterization.add(sub, inside);
+        } else {
+            final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
+            switch (sub.side(hyperplane)) {
+            case PLUS:
+                characterize(node.getPlus(), sub, characterization);
+                break;
+            case MINUS:
+                characterize(node.getMinus(), sub, characterization);
+                break;
+            case BOTH:
+                final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
+                characterize(node.getPlus(),  split.getPlus(),  characterization);
+                characterize(node.getMinus(), split.getMinus(), characterization);
+                break;
+            default:
+                // this should not happen
+                throw new RuntimeException("internal error");
+            }
+        }
+    }
+
+    /** {@inheritDoc} */
+    public double getBoundarySize() {
+        final BoundarySizeVisitor<S> visitor = new BoundarySizeVisitor<S>();
+        getTree(true).visit(visitor);
+        return visitor.getSize();
+    }
+
+    /** {@inheritDoc} */
+    public double getSize() {
+        if (barycenter == null) {
+            computeGeometricalProperties();
+        }
+        return size;
+    }
+
+    /** Set the size of the instance.
+     * @param size size of the instance
+     */
+    protected void setSize(final double size) {
+        this.size = size;
+    }
+
+    /** {@inheritDoc} */
+    public Vector<S> getBarycenter() {
+        if (barycenter == null) {
+            computeGeometricalProperties();
+        }
+        return barycenter;
+    }
+
+    /** Set the barycenter of the instance.
+     * @param barycenter barycenter of the instance
+     */
+    protected void setBarycenter(final Vector<S> barycenter) {
+        this.barycenter = barycenter;
+    }
+
+    /** Compute some geometrical properties.
+     * <p>The properties to compute are the barycenter and the size.</p>
+     */
+    protected abstract void computeGeometricalProperties();
+
+    /** {@inheritDoc} */
+    public Side side(final Hyperplane<S> hyperplane) {
+        final Sides sides = new Sides();
+        recurseSides(tree, hyperplane.wholeHyperplane(), sides);
+        return sides.plusFound() ?
+              (sides.minusFound() ? Side.BOTH  : Side.PLUS) :
+              (sides.minusFound() ? Side.MINUS : Side.HYPER);
+    }
+
+    /** 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
+     * @param sides object holding the sides found
+     */
+    private void recurseSides(final BSPTree<S> node, final SubHyperplane<S> sub, final Sides sides) {
+
+        if (node.getCut() == null) {
+            if ((Boolean) node.getAttribute()) {
+                // this is an inside cell expanding across the hyperplane
+                sides.rememberPlusFound();
+                sides.rememberMinusFound();
+            }
+            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 (!isEmpty(node.getMinus())) {
+                    sides.rememberPlusFound();
+                }
+            } else {
+                if (!isEmpty(node.getMinus())) {
+                    sides.rememberMinusFound();
+                }
+            }
+            if (!(sides.plusFound() && sides.minusFound())) {
+                recurseSides(node.getPlus(), sub, sides);
+            }
+            break;
+        case MINUS :
+            // the sub-hyperplane is entirely in the minus sub-tree
+            if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) {
+                if (!isEmpty(node.getPlus())) {
+                    sides.rememberPlusFound();
+                }
+            } else {
+                if (!isEmpty(node.getPlus())) {
+                    sides.rememberMinusFound();
+                }
+            }
+            if (!(sides.plusFound() && sides.minusFound())) {
+                recurseSides(node.getMinus(), sub, sides);
+            }
+            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(), sides);
+
+            // if needed, explore the minus sub-tree
+            if (!(sides.plusFound() && sides.minusFound())) {
+                recurseSides(node.getMinus(), split.getMinus(), sides);
+            }
+            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())) {
+                    sides.rememberPlusFound();
+                }
+                if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) {
+                    sides.rememberMinusFound();
+                }
+            } else {
+                if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) {
+                    sides.rememberMinusFound();
+                }
+                if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) {
+                    sides.rememberPlusFound();
+                }
+            }
+        }
+
+    }
+
+    /** Utility class holding the already found sides. */
+    private static final class Sides {
+
+        /** 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.
+         */
+        public Sides() {
+            plusFound  = false;
+            minusFound = false;
+        }
+
+        /** Remember the fact that inside leaf nodes have been found on the plus side.
+         */
+        public void rememberPlusFound() {
+            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;
+        }
+
+        /** Remember the fact that inside leaf nodes have been found on the minus side.
+         */
+        public void rememberMinusFound() {
+            minusFound = true;
+        }
+
+        /** 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;
+        }
+
+    }
+
+    /** {@inheritDoc} */
+    public SubHyperplane<S> intersection(final SubHyperplane<S> sub) {
+        return recurseIntersection(tree, sub);
+    }
+
+    /** Recursively compute the parts of a sub-hyperplane that are
+     * contained in the region.
+     * @param node current BSP tree node
+     * @param sub sub-hyperplane traversing the region
+     * @return filtered sub-hyperplane
+     */
+    private SubHyperplane<S> recurseIntersection(final BSPTree<S> node, final SubHyperplane<S> sub) {
+
+        if (node.getCut() == null) {
+            return (Boolean) node.getAttribute() ? sub.copySelf() : null;
+        }
+
+        final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
+        switch (sub.side(hyperplane)) {
+        case PLUS :
+            return recurseIntersection(node.getPlus(), sub);
+        case MINUS :
+            return recurseIntersection(node.getMinus(), sub);
+        case BOTH :
+            final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
+            final SubHyperplane<S> plus  = recurseIntersection(node.getPlus(),  split.getPlus());
+            final SubHyperplane<S> minus = recurseIntersection(node.getMinus(), split.getMinus());
+            if (plus == null) {
+                return minus;
+            } else if (minus == null) {
+                return plus;
+            } else {
+                return plus.reunite(minus);
+            }
+        default :
+            return recurseIntersection(node.getPlus(),
+                                       recurseIntersection(node.getMinus(), sub));
+        }
+
+    }
+
+    /** Transform a region.
+     * <p>Applying a transform to a region consist in applying the
+     * transform to all the hyperplanes of the underlying BSP tree and
+     * of the boundary (and also to the sub-hyperplanes embedded in
+     * these hyperplanes) and to the barycenter. The instance is not
+     * modified, a new instance is built.</p>
+     * @param transform transform to apply
+     * @return a new region, resulting from the application of the
+     * transform to the instance
+     */
+    public AbstractRegion<S, T> applyTransform(final Transform<S, T> transform) {
+        return (AbstractRegion<S, T>) buildNew(recurseTransform(getTree(false), transform));
+    }
+
+    /** Recursively transform an inside/outside BSP-tree.
+     * @param node current BSP tree node
+     * @param transform transform to apply
+     * @return a new tree
+     */
+    @SuppressWarnings("unchecked")
+    private BSPTree<S> recurseTransform(final BSPTree<S> node, final Transform<S, T> transform) {
+
+        if (node.getCut() == null) {
+            return new BSPTree<S>(node.getAttribute());
+        }
+
+        final SubHyperplane<S>  sub = node.getCut();
+        final SubHyperplane<S> tSub = ((AbstractSubHyperplane<S, T>) sub).applyTransform(transform);
+        BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute();
+        if (attribute != null) {
+            final SubHyperplane<S> tPO = (attribute.getPlusOutside() == null) ?
+                null : ((AbstractSubHyperplane<S, T>) attribute.getPlusOutside()).applyTransform(transform);
+            final SubHyperplane<S> tPI = (attribute.getPlusInside()  == null) ?
+                null  : ((AbstractSubHyperplane<S, T>) attribute.getPlusInside()).applyTransform(transform);
+            attribute = new BoundaryAttribute<S>(tPO, tPI);
+        }
+
+        return new BSPTree<S>(tSub,
+                                    recurseTransform(node.getPlus(),  transform),
+                                    recurseTransform(node.getMinus(), transform),
+                                    attribute);
+
+    }
+
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java?rev=1131125&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java Fri Jun  3 18:06:21 2011
@@ -0,0 +1,157 @@
+/*
+ * 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.math.geometry.partitioning;
+
+import org.apache.commons.math.geometry.Space;
+import org.apache.commons.math.geometry.partitioning.SubHyperplane;
+
+/** This class implements the dimension-independent parts of {@link SubHyperplane}.
+
+ * <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>
+
+ * @param <S> Type of the embedding space.
+
+ * @version $Revision$
+ * @since 3.0
+ */
+public abstract class AbstractSubHyperplane<S extends Space, T extends Space>
+    implements SubHyperplane<S> {
+
+    /** Underlying hyperplane. */
+    private final Hyperplane<S> hyperplane;
+
+    /** Remaining region of the hyperplane. */
+    private final Region<T> remainingRegion;
+
+    /** Build a sub-hyperplane from an hyperplane and a region.
+     * @param hyperplane underlying hyperplane
+     * @param remainingRegion remaining region of the hyperplane
+     */
+    protected AbstractSubHyperplane(final Hyperplane<S> hyperplane,
+                                    final Region<T> remainingRegion) {
+        this.hyperplane      = hyperplane;
+        this.remainingRegion = remainingRegion;
+    }
+
+    /** Build a sub-hyperplane from an hyperplane and a region.
+     * @param hyperplane underlying hyperplane
+     * @param remainingRegion remaining region of the hyperplane
+     */
+    protected abstract AbstractSubHyperplane<S, T> buildNew(final Hyperplane<S> hyperplane,
+                                                            final Region<T> remainingRegion);
+
+    /** {@inheritDoc} */
+    public AbstractSubHyperplane<S, T> copySelf() {
+        return buildNew(hyperplane, remainingRegion);
+    }
+
+    /** Get the underlying hyperplane.
+     * @return underlying hyperplane
+     */
+    public Hyperplane<S> getHyperplane() {
+        return hyperplane;
+    }
+
+    /** Get the remaining region of the hyperplane.
+     * <p>The returned region is expressed in the canonical hyperplane
+     * frame and has the hyperplane dimension. For example a chopped
+     * hyperplane in the 3D euclidean is a 2D plane and the
+     * corresponding region is a convex 2D polygon.</p>
+     * @return remaining region of the hyperplane
+     */
+    public Region<T> getRemainingRegion() {
+        return remainingRegion;
+    }
+
+    /** {@inheritDoc} */
+    public double getSize() {
+        return remainingRegion.getSize();
+    }
+
+    /** {@inheritDoc} */
+    public AbstractSubHyperplane<S, T> reunite(final SubHyperplane<S> other) {
+        @SuppressWarnings("unchecked")
+        AbstractSubHyperplane<S, T> o = (AbstractSubHyperplane<S, T>) other;
+        return buildNew(hyperplane,
+                        new RegionFactory<T>().union(remainingRegion, o.remainingRegion));
+    }
+
+    /** Apply a transform to the instance.
+     * <p>The instance must be a (D-1)-dimension sub-hyperplane with
+     * respect to the transform <em>not</em> a (D-2)-dimension
+     * sub-hyperplane the transform knows how to transform by
+     * itself. The transform will consist in transforming first the
+     * hyperplane and then the all region using the various methods
+     * provided by the transform.</p>
+     * @param transform D-dimension transform to apply
+     * @return the transformed instance
+     */
+    public AbstractSubHyperplane<S, T> applyTransform(final Transform<S, T> transform) {
+        final Hyperplane<S> tHyperplane = transform.apply(hyperplane);
+        final BSPTree<T> tTree =
+            recurseTransform(remainingRegion.getTree(false), tHyperplane, transform);
+        return buildNew(tHyperplane, remainingRegion.buildNew(tTree));
+    }
+
+    /** Recursively transform a BSP-tree from a sub-hyperplane.
+     * @param node current BSP tree node
+     * @param transformed image of the instance hyperplane by the transform
+     * @param transform transform to apply
+     * @return a new tree
+     */
+    private BSPTree<T> recurseTransform(final BSPTree<T> node,
+                                        final Hyperplane<S> transformed,
+                                        final Transform<S, T> transform) {
+        if (node.getCut() == null) {
+            return new BSPTree<T>(node.getAttribute());
+        }
+
+        @SuppressWarnings("unchecked")
+        BoundaryAttribute<T> attribute =
+            (BoundaryAttribute<T>) node.getAttribute();
+        if (attribute != null) {
+            final SubHyperplane<T> tPO = (attribute.getPlusOutside() == null) ?
+                null : transform.apply(attribute.getPlusOutside(), hyperplane, transformed);
+            final SubHyperplane<T> tPI = (attribute.getPlusInside() == null) ?
+                null : transform.apply(attribute.getPlusInside(), hyperplane, transformed);
+            attribute = new BoundaryAttribute<T>(tPO, tPI);
+        }
+
+        return new BSPTree<T>(transform.apply(node.getCut(), hyperplane, transformed),
+                              recurseTransform(node.getPlus(), transformed, transform),
+                              recurseTransform(node.getMinus(), transformed, transform),
+                              attribute);
+
+    }
+
+    /** {@inheritDoc} */
+    public abstract Side side(Hyperplane<S> hyperplane);
+
+    /** {@inheritDoc} */
+    public abstract SplitSubHyperplane<S> split(Hyperplane<S> hyperplane);
+
+    /** {@inheritDoc} */
+    public boolean isEmpty() {
+        return remainingRegion.isEmpty();
+    }
+
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java?rev=1131125&r1=1131124&r2=1131125&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java Fri Jun  3 18:06:21 2011
@@ -16,7 +16,8 @@
  */
 package org.apache.commons.math.geometry.partitioning;
 
-import org.apache.commons.math.geometry.partitioning.Hyperplane.Side;
+import org.apache.commons.math.geometry.Vector;
+import org.apache.commons.math.geometry.Space;
 import org.apache.commons.math.util.FastMath;
 
 /** This class represent a Binary Space Partition tree.
@@ -53,21 +54,24 @@ import org.apache.commons.math.util.Fast
  * Computer Graphics 24(4), August 1990, pp 115-124, published by the
  * Association for Computing Machinery (ACM).</p>
 
- * @version $Revision$ $Date$
+ * @param <S> Type of the space.
+
+ * @version $Id:$
+ * @since 3.0
  */
-public class BSPTree {
+public class BSPTree<S extends Space> {
 
     /** Cut sub-hyperplane. */
-    private SubHyperplane cut;
+    private SubHyperplane<S> cut;
 
     /** Tree at the plus side of the cut hyperplane. */
-    private BSPTree plus;
+    private BSPTree<S> plus;
 
     /** Tree at the minus side of the cut hyperplane. */
-    private BSPTree minus;
+    private BSPTree<S> minus;
 
     /** Parent tree. */
-    private BSPTree parent;
+    private BSPTree<S> parent;
 
     /** Application-defined attribute. */
     private Object attribute;
@@ -106,7 +110,7 @@ public class BSPTree {
      * @param attribute attribute associated with the node (may be null)
      * @see #insertCut
      */
-    public BSPTree(final SubHyperplane cut, final BSPTree plus, final BSPTree minus,
+    public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus,
                    final Object attribute) {
         this.cut       = cut;
         this.plus      = plus;
@@ -140,15 +144,15 @@ public class BSPTree {
      * the cell now has two leaf child nodes)
      * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
      */
-    public boolean insertCut(final Hyperplane hyperplane) {
+    public boolean insertCut(final Hyperplane<S> hyperplane) {
 
         if (cut != null) {
             plus.parent  = null;
             minus.parent = null;
         }
 
-        final SubHyperplane chopped = fitToCell(new SubHyperplane(hyperplane));
-        if (chopped.getRemainingRegion().isEmpty()) {
+        final SubHyperplane<S> chopped = fitToCell(hyperplane.wholeHyperplane());
+        if (chopped.isEmpty()) {
             cut          = null;
             plus         = null;
             minus        = null;
@@ -156,9 +160,9 @@ public class BSPTree {
         }
 
         cut          = chopped;
-        plus         = new BSPTree();
+        plus         = new BSPTree<S>();
         plus.parent  = this;
-        minus        = new BSPTree();
+        minus        = new BSPTree<S>();
         minus.parent = this;
         return true;
 
@@ -171,13 +175,13 @@ public class BSPTree {
      * objects).</p>
      * @return a new tree, copy of the instance
      */
-    public BSPTree copySelf() {
+    public BSPTree<S> copySelf() {
 
         if (cut == null) {
-            return new BSPTree(attribute);
+            return new BSPTree<S>(attribute);
         }
 
-        return new BSPTree(cut.copySelf(), plus.copySelf(), minus.copySelf(),
+        return new BSPTree<S>(cut.copySelf(), plus.copySelf(), minus.copySelf(),
                            attribute);
 
     }
@@ -185,7 +189,7 @@ public class BSPTree {
     /** Get the cut sub-hyperplane.
      * @return cut sub-hyperplane, null if this is a leaf tree
      */
-    public SubHyperplane getCut() {
+    public SubHyperplane<S> getCut() {
         return cut;
     }
 
@@ -193,7 +197,7 @@ public class BSPTree {
      * @return tree on the plus side of the cut hyperplane, null if this
      * is a leaf tree
      */
-    public BSPTree getPlus() {
+    public BSPTree<S> getPlus() {
         return plus;
     }
 
@@ -201,14 +205,14 @@ public class BSPTree {
      * @return tree on the minus side of the cut hyperplane, null if this
      * is a leaf tree
      */
-    public BSPTree getMinus() {
+    public BSPTree<S> getMinus() {
         return minus;
     }
 
     /** Get the parent node.
      * @return parent node, null if the node has no parents
      */
-    public BSPTree getParent() {
+    public BSPTree<S> getParent() {
         return parent;
     }
 
@@ -233,7 +237,7 @@ public class BSPTree {
     /** Visit the BSP tree nodes.
      * @param visitor object visiting the tree nodes
      */
-    public void visit(final BSPTreeVisitor visitor) {
+    public void visit(final BSPTreeVisitor<S> visitor) {
         if (cut == null) {
             visitor.visitLeafNode(this);
         } else {
@@ -283,13 +287,13 @@ public class BSPTree {
      * @return a new sub-hyperplane, gueranteed to have no part outside
      * of the instance cell
      */
-    private SubHyperplane fitToCell(final SubHyperplane sub) {
-        SubHyperplane s = sub;
-        for (BSPTree tree = this; tree.parent != null; tree = tree.parent) {
+    private SubHyperplane<S> fitToCell(final SubHyperplane<S> sub) {
+        SubHyperplane<S> s = sub;
+        for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
             if (tree == tree.parent.plus) {
-                s = tree.parent.cut.getHyperplane().split(s).getPlus();
+                s = s.split(tree.parent.cut.getHyperplane()).getPlus();
             } else {
-                s = tree.parent.cut.getHyperplane().split(s).getMinus();
+                s = s.split(tree.parent.cut.getHyperplane()).getMinus();
             }
         }
         return s;
@@ -302,7 +306,7 @@ public class BSPTree {
      * @param point point to check
      * @return the tree cell to which the point belongs (can be
      */
-    public BSPTree getCell(final Point point) {
+    public BSPTree<S> getCell(final Vector<S> point) {
 
         if (cut == null) {
             return this;
@@ -356,7 +360,7 @@ public class BSPTree {
      * tree</code>, this value can be ignored if parentTree is not null
      * since all connections have already been established
      */
-    public BSPTree merge(final BSPTree tree, final LeafMerger leafMerger) {
+    public BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger) {
         return merge(tree, leafMerger, null, false);
     }
 
@@ -375,8 +379,8 @@ public class BSPTree {
      * tree</code>, this value can be ignored if parentTree is not null
      * since all connections have already been established
      */
-    private BSPTree merge(final BSPTree tree, final LeafMerger leafMerger,
-                          final BSPTree parentTree, final boolean isPlusChild) {
+    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);
@@ -385,7 +389,7 @@ public class BSPTree {
             return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
         } else {
             // tree/tree operation
-            final BSPTree merged = tree.split(cut);
+            final BSPTree<S> merged = tree.split(cut);
             if (parentTree != null) {
                 merged.parent = parentTree;
                 if (isPlusChild) {
@@ -401,7 +405,7 @@ public class BSPTree {
             merged.condense();
             if (merged.cut != null) {
                 merged.cut =
-                    merged.fitToCell(new SubHyperplane(merged.cut.getHyperplane()));
+                    merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane());
             }
 
             return merged;
@@ -423,9 +427,11 @@ public class BSPTree {
      * 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 <SpacePoint> Type of the space points.
+     * @param <SubSpacePoint> Type of the sub-space points.
      * @version $Revision$ $Date$
      */
-    public static interface LeafMerger {
+    public static 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
@@ -456,9 +462,8 @@ public class BSPTree {
          * @return the BSP tree resulting from the merging (may be one of
          * the arguments)
          */
-        BSPTree merge(BSPTree leaf, BSPTree tree,
-                      BSPTree parentTree, boolean isPlusChild,
-                      boolean leafFromInstance);
+        BSPTree<S> merge(BSPTree<S> leaf, BSPTree<S> tree, BSPTree<S> parentTree,
+                         boolean isPlusChild, boolean leafFromInstance);
 
     }
 
@@ -480,26 +485,27 @@ public class BSPTree {
      * sub-hyperplane, the two parts of the split instance as its two
      * sub-trees and a null parent
      */
-    public BSPTree split(final SubHyperplane sub) {
+    public BSPTree<S> split(final SubHyperplane<S> sub) {
 
         if (cut == null) {
-            return new BSPTree(sub, copySelf(), new BSPTree(attribute), null);
+            return new BSPTree<S>(sub, copySelf(),
+                    new BSPTree<S>(attribute), null);
         }
 
-        final Hyperplane cHyperplane = cut.getHyperplane();
-        final Hyperplane sHyperplane = sub.getHyperplane();
-        switch (cHyperplane.side(sub)) {
+        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 split = plus.split(sub);
-            if (sHyperplane.side(cut) == Side.PLUS) {
-                split.plus = new BSPTree(cut.copySelf(),
-                                         split.plus, minus.copySelf(), attribute);
+            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(cut.copySelf(),
-                                          split.minus, minus.copySelf(), attribute);
+                split.minus =
+                    new BSPTree<S>(cut.copySelf(), split.minus, minus.copySelf(), attribute);
                 split.minus.condense();
                 split.minus.parent = split;
             }
@@ -507,15 +513,15 @@ public class BSPTree {
         }
         case MINUS :
         { // the partitioning sub-hyperplane is entirely in the minus sub-tree
-            final BSPTree split = minus.split(sub);
-            if (sHyperplane.side(cut) == Side.PLUS) {
-                split.plus = new BSPTree(cut.copySelf(),
-                                         plus.copySelf(), split.plus, attribute);
+            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(cut.copySelf(),
-                                          plus.copySelf(), split.minus, attribute);
+                split.minus =
+                    new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.minus, attribute);
                 split.minus.condense();
                 split.minus.parent = split;
             }
@@ -523,15 +529,14 @@ public class BSPTree {
         }
         case BOTH :
         {
-            final Hyperplane.SplitSubHyperplane cutParts = sHyperplane.split(cut);
-            final Hyperplane.SplitSubHyperplane subParts = cHyperplane.split(sub);
-            final BSPTree split = new BSPTree(sub,
-                                              plus.split(subParts.getPlus()),
-                                              minus.split(subParts.getMinus()),
-                                              null);
+            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 tmp       = split.plus.minus;
+            final BSPTree<S> tmp    = split.plus.minus;
             split.plus.minus        = split.minus.plus;
             split.plus.minus.parent = split.plus;
             split.minus.plus        = tmp;
@@ -542,8 +547,8 @@ public class BSPTree {
         }
         default :
             return cHyperplane.sameOrientationAs(sHyperplane) ?
-                    new BSPTree(sub, plus.copySelf(), minus.copySelf(), attribute) :
-                        new BSPTree(sub, minus.copySelf(), plus.copySelf(), attribute);
+                   new BSPTree<S>(sub, plus.copySelf(),  minus.copySelf(), attribute) :
+                   new BSPTree<S>(sub, minus.copySelf(), plus.copySelf(),  attribute);
         }
 
     }
@@ -557,7 +562,7 @@ public class BSPTree {
      * parentTree is null
      * @see LeafMerger
      */
-    public void insertInTree(final BSPTree parentTree, final boolean isPlusChild) {
+    public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) {
 
         // set up parent/child links
         parent = parentTree;
@@ -573,19 +578,19 @@ public class BSPTree {
         if (cut != null) {
 
             // explore the parent nodes from here towards tree root
-            for (BSPTree tree = this; tree.parent != null; tree = tree.parent) {
+            for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
 
                 // this is an hyperplane of some parent node
-                final Hyperplane hyperplane = tree.parent.cut.getHyperplane();
+                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 = hyperplane.split(cut).getPlus();
+                    cut = cut.split(hyperplane).getPlus();
                     plus.chopOffMinus(hyperplane);
                     minus.chopOffMinus(hyperplane);
                 } else {
-                    cut = hyperplane.split(cut).getMinus();
+                    cut = cut.split(hyperplane).getMinus();
                     plus.chopOffPlus(hyperplane);
                     minus.chopOffPlus(hyperplane);
                 }
@@ -602,13 +607,13 @@ public class BSPTree {
 
     /** 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 disgarded, only the
+     * the minus side of the chopping hyperplane are discarded, only the
      * parts on the plus side remain.</p>
      * @param hyperplane chopping hyperplane
      */
-    private void chopOffMinus(final Hyperplane hyperplane) {
+    private void chopOffMinus(final Hyperplane<S> hyperplane) {
         if (cut != null) {
-            cut = hyperplane.split(cut).getPlus();
+            cut = cut.split(hyperplane).getPlus();
             plus.chopOffMinus(hyperplane);
             minus.chopOffMinus(hyperplane);
         }
@@ -616,13 +621,13 @@ public class BSPTree {
 
     /** 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 disgarded, only the
+     * the plus side of the chopping hyperplane are discarded, only the
      * parts on the minus side remain.</p>
      * @param hyperplane chopping hyperplane
      */
-    private void chopOffPlus(final Hyperplane hyperplane) {
+    private void chopOffPlus(final Hyperplane<S> hyperplane) {
         if (cut != null) {
-            cut = hyperplane.split(cut).getMinus();
+            cut = cut.split(hyperplane).getMinus();
             plus.chopOffPlus(hyperplane);
             minus.chopOffPlus(hyperplane);
         }

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java?rev=1131125&r1=1131124&r2=1131125&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java Fri Jun  3 18:06:21 2011
@@ -16,6 +16,8 @@
  */
 package org.apache.commons.math.geometry.partitioning;
 
+import org.apache.commons.math.geometry.Space;
+
 /** This interface is used to visit {@link BSPTree BSP tree} nodes.
 
  * <p>Navigation through {@link BSPTree BSP trees} can be done using
@@ -38,12 +40,16 @@ package org.apache.commons.math.geometry
  *   </li>
  * </ul>
 
+ * @param <SpacePoint> Type of the space points.
+ * @param <SubSpacePoint> Type of the sub-space points.
+
  * @see BSPTree
  * @see SubHyperplane
 
- * @version $Revision$ $Date$
+ * @version $Id:$
+ * @since 3.0
  */
-public interface BSPTreeVisitor {
+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 {
@@ -90,7 +96,7 @@ public interface BSPTreeVisitor {
      * {@link Order#MINUS_PLUS_SUB}, {@link Order#MINUS_SUB_PLUS},
      * {@link Order#SUB_PLUS_MINUS}, {@link Order#SUB_MINUS_PLUS}
      */
-    Order visitOrder(BSPTree node);
+    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
@@ -99,12 +105,12 @@ public interface BSPTreeVisitor {
      * @param node BSP node guaranteed to have a non null cut sub-hyperplane
      * @see #visitLeafNode
      */
-    void visitInternalNode(BSPTree node);
+    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 node);
+    void visitLeafNode(BSPTree<S> node);
 
 }

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java?rev=1131125&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java Fri Jun  3 18:06:21 2011
@@ -0,0 +1,84 @@
+/*
+ * 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.math.geometry.partitioning;
+
+import org.apache.commons.math.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 Region.getTree}. 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
+ * @version $Id:$
+ * @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).
+     */
+    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).
+     */
+    final SubHyperplane<S> plusInside;
+
+    /** 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)
+     */
+    public BoundaryAttribute(final SubHyperplane<S> plusOutside,
+                             final SubHyperplane<S> plusInside) {
+        this.plusOutside = plusOutside;
+        this.plusInside  = plusInside;
+    }
+
+    /** 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;
+    }
+
+}
\ No newline at end of file

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java?rev=1131125&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java Fri Jun  3 18:06:21 2011
@@ -0,0 +1,66 @@
+/*
+ * 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.math.geometry.partitioning;
+
+import org.apache.commons.math.geometry.Space;
+
+/** Visitor computing the boundary size.
+ * @param <S> Type of the space.
+ * @version $Id:$
+ * @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.plusOutside != null) {
+            boundarySize += attribute.plusOutside.getSize();
+        }
+        if (attribute.plusInside != null) {
+            boundarySize += attribute.plusInside.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;
+    }
+
+}
\ No newline at end of file

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java?rev=1131125&r1=1131124&r2=1131125&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java Fri Jun  3 18:06:21 2011
@@ -16,16 +16,20 @@
  */
 package org.apache.commons.math.geometry.partitioning;
 
+import org.apache.commons.math.geometry.Space;
+
 /** Characterization of a sub-hyperplane.
- * @version $Revision$ $Date$
+ * @param <S> Type of the space.
+ * @version $Id:$
+ * @since 3.0
  */
-class Characterization {
+class Characterization<S extends Space> {
 
     /** Parts of the sub-hyperplane that have inside cells on the tested side. */
-    private SubHyperplane in;
+    private SubHyperplane<S> in;
 
     /** Parts of the sub-hyperplane that have outside cells on the tested side. */
-    private SubHyperplane out;
+    private SubHyperplane<S> out;
 
     /** Create an empty characterization of a sub-hyperplane.
      */
@@ -38,13 +42,13 @@ class Characterization {
      * @return true if the sub-hyperplane that have inside cells on the tested side
      */
     public boolean hasIn() {
-        return (in != null) && (!in.getRemainingRegion().isEmpty());
+        return (in != null) && (!in.isEmpty());
     }
 
     /** Get the parts of the sub-hyperplane that have inside cells on the tested side.
      * @return parts of the sub-hyperplane that have inside cells on the tested side
      */
-    public SubHyperplane getIn() {
+    public SubHyperplane<S> getIn() {
         return in;
     }
 
@@ -52,13 +56,13 @@ class Characterization {
      * @return true if the sub-hyperplane that have outside cells on the tested side
      */
     public boolean hasOut() {
-        return (out != null) && (!out.getRemainingRegion().isEmpty());
+        return (out != null) && (!out.isEmpty());
     }
 
     /** Get the parts of the sub-hyperplane that have outside cells on the tested side.
      * @return parts of the sub-hyperplane that have outside cells on the tested side
      */
-    public SubHyperplane getOut() {
+    public SubHyperplane<S> getOut() {
         return out;
     }
 
@@ -67,22 +71,18 @@ class Characterization {
      * @param inside if true, the part added as an inside cell on the tested side, otherwise
      * it has an outside cell on the tested side
      */
-    public void add(final SubHyperplane sub, final boolean inside) {
+    public void add(final SubHyperplane<S> sub, final boolean inside) {
         if (inside) {
             if (in == null) {
                 in = sub;
             } else {
-                in = new SubHyperplane(in.getHyperplane(),
-                                       Region.union(in.getRemainingRegion(),
-                                                    sub.getRemainingRegion()));
+                in = in.reunite(sub);
             }
         } else {
             if (out == null) {
                 out = sub;
             } else {
-                out = new SubHyperplane(out.getHyperplane(),
-                                        Region.union(out.getRemainingRegion(),
-                                                     sub.getRemainingRegion()));
+                out = out.reunite(sub);
             }
         }
     }

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java?rev=1131125&r1=1131124&r2=1131125&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java Fri Jun  3 18:06:21 2011
@@ -16,6 +16,9 @@
  */
 package org.apache.commons.math.geometry.partitioning;
 
+import org.apache.commons.math.geometry.Vector;
+import org.apache.commons.math.geometry.Space;
+
 /** This interface represents an hyperplane of a space.
 
  * <p>The most prominent place where hyperplane appears in space
@@ -27,26 +30,12 @@ package org.apache.commons.math.geometry
  * space). They can be more exotic objects in specific fields, for
  * example a circle on the surface of the unit sphere.</p>
 
- * @version $Revision$ $Date$
- */
-public interface Hyperplane extends SubSpace {
-
-    /** Enumerate for specifying sides of the hyperplane. */
-    enum Side {
-
-        /** Code for the plus side of the hyperplane. */
-        PLUS,
+ * @param <SpacePoint> Type of the space points.
 
-        /** 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;
-
-    }
+ * @version $Id:$
+ * @since 3.0
+ */
+public interface Hyperplane<S extends Space> {
 
     /** Copy the instance.
      * <p>The instance created is completely independant of the original
@@ -54,7 +43,7 @@ public interface Hyperplane extends SubS
      * shared (except for immutable objects).</p>
      * @return a new hyperplane, copy of the instance
      */
-    Hyperplane copySelf();
+    Hyperplane<S> copySelf();
 
     /** Get the offset (oriented distance) of a point.
      * <p>The offset is 0 if the point is on the underlying hyperplane,
@@ -64,7 +53,7 @@ public interface Hyperplane extends SubS
      * @param point point to check
      * @return offset of the point
      */
-    double getOffset(Point point);
+    double getOffset(Vector<S> point);
 
     /** Check if the instance has the same orientation as another hyperplane.
      * <p>This method is expected to be called on parallel hyperplanes
@@ -78,82 +67,16 @@ public interface Hyperplane extends SubS
      * @return true if the instance and the other hyperplane have
      * the same orientation
      */
-    boolean sameOrientationAs(Hyperplane other);
+    boolean sameOrientationAs(Hyperplane<S> other);
 
-    /** Build the sub-space shared by the instance and another hyperplane.
-     * @param other other hyperplane
-     * @return a sub-space at the intersection of the instance and the
-     * other sub-space (it has a dimension one unit less than the
-     * instance)
+    /** Build a sub-hyperplane covering the whole hyperplane.
+     * @return a sub-hyperplane covering the whole hyperplane
      */
-    SubSpace intersection(Hyperplane other);
-
-    /** Build a region covering the whole hyperplane.
-     * <p>The region build is restricted to the sub-space defined by the
-     * hyperplane. This means that the regions points are consistent
-     * with the argument of the {@link SubSpace#toSpace toSpace} method
-     * and with the return value of the {@link SubSpace#toSubSpace
-     * toSubSpace} method.<p>
-     * @return a region covering the whole hyperplane
-     */
-    Region wholeHyperplane();
+    SubHyperplane<S> wholeHyperplane();
 
     /** Build a region covering the whole space.
      * @return a region containing the instance
      */
-    Region wholeSpace();
-
-    /** Compute the relative position of a sub-hyperplane with respect
-     * to the instance.
-     * @param sub sub-hyperplane to check
-     * @return one of {@link Side#PLUS}, {@link Side#MINUS}, {@link Side#BOTH},
-     * {@link Side#HYPER}
-     */
-    Side side(SubHyperplane sub);
-
-    /** Split a sub-hyperplane in two parts by the instance.
-     * @param sub sub-hyperplane to split
-     * @return an object containing both the part of the sub-hyperplane
-     * on the plus side of the instance and the part of the
-     * sub-hyperplane on the minus side of the instance
-     */
-    SplitSubHyperplane split(SubHyperplane sub);
-
-    /** Class holding the results of the {@link Hyperplane#split Hyperplane.split}
-     * method. */
-    class SplitSubHyperplane {
-
-        /** Part of the sub-hyperplane on the plus side of the splitting hyperplane. */
-        private final SubHyperplane plus;
-
-        /** Part of the sub-hyperplane on the minus side of the splitting hyperplane. */
-        private final SubHyperplane 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 plus, final SubHyperplane 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 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 getMinus() {
-            return minus;
-        }
-
-    }
+    Region<S> wholeSpace();
 
 }



Mime
View raw message