commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r1066664 [4/6] - in /commons/sandbox/bsp: branches/ tags/ trunk/ trunk/src/ trunk/src/main/ trunk/src/main/java/ trunk/src/main/java/org/ trunk/src/main/java/org/apache/ trunk/src/main/java/org/apache/commons/ trunk/src/main/java/org/apache...
Date Wed, 02 Feb 2011 22:21:07 GMT
Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTreeVisitor.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTreeVisitor.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTreeVisitor.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTreeVisitor.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,110 @@
+/*
+ * 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.bsp.partitioning;
+
+/** This interface is used to visit {@link BSPTree BSP tree} nodes.
+
+ * <p>Navigation through {@link BSPTree BSP trees} can be done using
+ * two different point of views:</p>
+ * <ul>
+ *   <li>
+ *     the first one is in a node-oriented way using the {@link
+ *     BSPTree#getPlus}, {@link BSPTree#getMinus} and {@link
+ *     BSPTree#getParent} methods. Terminal nodes without associated
+ *     {@link SubHyperplane sub-hyperplanes} can be visited this way,
+ *     there is no constraint in the visit order, and it is possible
+ *     to visit either all nodes or only a subset of the nodes
+ *   </li>
+ *   <li>
+ *     the second one is in a sub-hyperplane-oriented way using
+ *     classes implementing this interface which obeys the visitor
+ *     design pattern. The visit order is provided by the visitor as
+ *     each node is first encountered. Each node is visited exactly
+ *     once.
+ *   </li>
+ * </ul>
+
+ * @see BSPTree
+ * @see SubHyperplane
+
+ * @version $Revision$ $Date$
+ */
+public interface BSPTreeVisitor {
+
+    /** Enumerate for visit order with respect to plus sub-tree, minus sub-tree and cut sub-hyperplane. */
+    enum Order {
+        /** Indicator for visit order plus sub-tree, then minus sub-tree,
+         * and last cut sub-hyperplane.
+         */
+        PLUS_MINUS_SUB,
+
+        /** Indicator for visit order plus sub-tree, then cut sub-hyperplane,
+         * and last minus sub-tree.
+         */
+        PLUS_SUB_MINUS,
+
+        /** Indicator for visit order minus sub-tree, then plus sub-tree,
+         * and last cut sub-hyperplane.
+         */
+        MINUS_PLUS_SUB,
+
+        /** Indicator for visit order minus sub-tree, then cut sub-hyperplane,
+         * and last plus sub-tree.
+         */
+        MINUS_SUB_PLUS,
+
+        /** Indicator for visit order cut sub-hyperplane, then plus sub-tree,
+         * and last minus sub-tree.
+         */
+        SUB_PLUS_MINUS,
+
+        /** Indicator for visit order cut sub-hyperplane, then minus sub-tree,
+         * and last plus sub-tree.
+         */
+        SUB_MINUS_PLUS;
+    }
+
+    /** Determine the visit order for this node.
+     * <p>Before attempting to visit an internal node, this method is
+     * called to determine the desired ordering of the visit. It is
+     * guaranteed that this method will be called before {@link
+     * #visitInternalNode visitInternalNode} for a given node, it will be
+     * called exactly once for each internal node.</p>
+     * @param node BSP node guaranteed to have a non null cut sub-hyperplane
+     * @return desired visit order, must be one of
+     * {@link Order#PLUS_MINUS_SUB}, {@link Order#PLUS_SUB_MINUS},
+     * {@link Order#MINUS_PLUS_SUB}, {@link Order#MINUS_SUB_PLUS},
+     * {@link Order#SUB_PLUS_MINUS}, {@link Order#SUB_MINUS_PLUS}
+     */
+    Order visitOrder(BSPTree node);
+
+    /** Visit a BSP tree node node having a non-null sub-hyperplane.
+     * <p>It is guaranteed that this method will be called after {@link
+     * #visitOrder visitOrder} has been called for a given node,
+     * it wil be called exactly once for each internal node.</p>
+     * @param node BSP node guaranteed to have a non null cut sub-hyperplane
+     * @see #visitLeafNode
+     */
+    void visitInternalNode(BSPTree 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);
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTreeVisitor.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTreeVisitor.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Characterization.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Characterization.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Characterization.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Characterization.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,90 @@
+/*
+ * 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.bsp.partitioning;
+
+/** Characterization of a sub-hyperplane.
+ * @version $Revision$ $Date$
+ */
+class Characterization {
+
+    /** Parts of the sub-hyperplane that have inside cells on the tested side. */
+    private SubHyperplane in;
+
+    /** Parts of the sub-hyperplane that have outside cells on the tested side. */
+    private SubHyperplane out;
+
+    /** Create an empty characterization of a sub-hyperplane.
+     */
+    public Characterization() {
+        in  = null;
+        out = null;
+    }
+
+    /** Check if the sub-hyperplane that have inside cells on the tested side.
+     * @return true if the sub-hyperplane that have inside cells on the tested side
+     */
+    public boolean hasIn() {
+        return (in != null) && (!in.getRemainingRegion().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() {
+        return in;
+    }
+
+    /** Check if the sub-hyperplane that have outside cells on the tested side.
+     * @return true if the sub-hyperplane that have outside cells on the tested side
+     */
+    public boolean hasOut() {
+        return (out != null) && (!out.getRemainingRegion().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() {
+        return out;
+    }
+
+    /** Add a part of the sub-hyperplane known to have inside or outside cell on the tested side.
+     * @param sub part of the sub-hyperplane to add
+     * @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) {
+        if (inside) {
+            if (in == null) {
+                in = sub;
+            } else {
+                in = new SubHyperplane(in.getHyperplane(),
+                                       Region.union(in.getRemainingRegion(),
+                                                    sub.getRemainingRegion()));
+            }
+        } else {
+            if (out == null) {
+                out = sub;
+            } else {
+                out = new SubHyperplane(out.getHyperplane(),
+                                        Region.union(out.getRemainingRegion(),
+                                                     sub.getRemainingRegion()));
+            }
+        }
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Characterization.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Characterization.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Hyperplane.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Hyperplane.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Hyperplane.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Hyperplane.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,159 @@
+/*
+ * 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.bsp.partitioning;
+
+/** This interface represents an hyperplane of a space.
+
+ * <p>The most prominent place where hyperplane appears in space
+ * partitioning is as cutters. Each partitioning node in a {@link
+ * BSPTree BSP tree} has a cut {@link SubHyperplane sub-hyperplane}
+ * which is either an hyperplane or a part of an hyperplane. In an
+ * n-dimensions euclidean space, an hyperplane is an (n-1)-dimensions
+ * hyperplane (for example a traditional plane in the 3D euclidean
+ * space). They can be more exotic objects in specific fields, for
+ * example a circle on the surface of the unit sphere.</p>
+
+ * @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,
+
+        /** 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;
+
+    }
+
+    /** Copy the instance.
+     * <p>The instance created is completely independant of the original
+     * one. A deep copy is used, none of the underlying objects are
+     * shared (except for immutable objects).</p>
+     * @return a new hyperplane, copy of the instance
+     */
+    Hyperplane copySelf();
+
+    /** Get the offset (oriented distance) of a point.
+     * <p>The offset is 0 if the point is on the underlying hyperplane,
+     * it is positive if the point is on one particular side of the
+     * hyperplane, and it is negative if the point is on the other side,
+     * according to the hyperplane natural orientation.</p>
+     * @param point point to check
+     * @return offset of the point
+     */
+    double getOffset(Point point);
+
+    /** Check if the instance has the same orientation as another hyperplane.
+     * <p>This method is expected to be called on parallel hyperplanes
+     * (i.e. when the {@link #side side} method would return {@link
+     * Side#HYPER} for some sub-hyperplane having the specified hyperplane
+     * as its underlying hyperplane). The method should <em>not</em>
+     * re-check for parallelism, only for orientation, typically by
+     * testing something like the sign of the dot-products of
+     * normals.</p>
+     * @param other other hyperplane to check against the instance
+     * @return true if the instance and the other hyperplane have
+     * the same orientation
+     */
+    boolean sameOrientationAs(Hyperplane 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)
+     */
+    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();
+
+    /** 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;
+        }
+
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Hyperplane.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Hyperplane.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Point.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Point.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Point.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Point.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,29 @@
+/*
+ * 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.bsp.partitioning;
+
+/** This interface represents a generic point to be used in a space partition.
+ * <p>Points are completely virtual entities with no specification at
+ * all, so this class is essentially a marker interface with no
+ * methods. This allows to perform partition in traditional euclidean
+ * n-dimensions spaces, but also in more exotic universes like for
+ * example the surface of the unit sphere.</p>
+ * @version $Revision$ $Date$
+ */
+public interface Point {
+    // nothing here, this is only a marker interface
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Point.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Point.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Region.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Region.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Region.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Region.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,1066 @@
+/*
+ * 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.bsp.partitioning;
+
+import java.util.Collection;
+import java.util.TreeSet;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.ArrayList;
+
+/** This class represent 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>
+
+ * @version $Revision$ $Date$
+ */
+public abstract class Region {
+
+    /** 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;
+    }
+
+    /** Inside/Outside BSP tree. */
+    private BSPTree tree;
+
+    /** Size of the instance. */
+    private double size;
+
+    /** Barycenter. */
+    private Point barycenter;
+
+    /** Build a region representing the whole space.
+     */
+    protected Region() {
+        tree = new BSPTree(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 Region(final BSPTree 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(Point) 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 Region(final Collection<SubHyperplane> boundary) {
+
+        if (boundary.size() == 0) {
+
+            // the tree represents the whole space
+            tree = new BSPTree(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> ordered = new TreeSet<SubHyperplane>(new Comparator<SubHyperplane>() {
+                public int compare(final SubHyperplane o1, final SubHyperplane o2) {
+                    final double size1 = o1.getRemainingRegion().getSize();
+                    final double size2 = o2.getRemainingRegion().getSize();
+                    return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1);
+                }
+            });
+            ordered.addAll(boundary);
+
+            // build the tree top-down
+            tree = new BSPTree();
+            insertCuts(tree, ordered);
+
+            // set up the inside/outside flags
+            tree.visit(new BSPTreeVisitor() {
+
+                /** {@inheritDoc} */
+                public Order visitOrder(final BSPTree node) {
+                    return Order.PLUS_SUB_MINUS;
+                }
+
+                /** {@inheritDoc} */
+                public void visitInternalNode(final BSPTree node) {
+                }
+
+                /** {@inheritDoc} */
+                public void visitLeafNode(final BSPTree node) {
+                    node.setAttribute((node == node.getParent().getPlus()) ?
+                                                                            Boolean.FALSE : Boolean.TRUE);
+                }
+            });
+
+        }
+
+    }
+
+    /** 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
+     */
+    public abstract Region buildNew(BSPTree 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 node, final Collection<SubHyperplane> boundary) {
+
+        final Iterator<SubHyperplane> iterator = boundary.iterator();
+
+        // build the current level
+        Hyperplane 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> plusList  = new ArrayList<SubHyperplane>();
+        final ArrayList<SubHyperplane> minusList = new ArrayList<SubHyperplane>();
+        while (iterator.hasNext()) {
+            final SubHyperplane other = iterator.next();
+            switch (inserted.side(other)) {
+            case PLUS:
+                plusList.add(other);
+                break;
+            case MINUS:
+                minusList.add(other);
+                break;
+            case BOTH:
+                final Hyperplane.SplitSubHyperplane split = inserted.split(other);
+                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 a collection of bounding hyperplanes.
+     * @param hyperplanes collection of bounding hyperplanes
+     * @return a new convex region, or null if the collection is empty
+     */
+    public static Region buildConvex(final Collection<Hyperplane> hyperplanes) {
+        if (hyperplanes.isEmpty()) {
+            return null;
+        }
+
+        // use the first hyperplane to build the right class
+        final Region region = hyperplanes.iterator().next().wholeSpace();
+
+        // chop off parts of the space
+        BSPTree node = region.tree;
+        node.setAttribute(Boolean.TRUE);
+        for (final Hyperplane hyperplane : hyperplanes) {
+            if (node.insertCut(hyperplane)) {
+                node.setAttribute(null);
+                node.getPlus().setAttribute(Boolean.FALSE);
+                node = node.getMinus();
+                node.setAttribute(Boolean.TRUE);
+            }
+        }
+
+        return region;
+
+    }
+
+    /** 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
+     */
+    public Region copySelf() {
+        return buildNew(tree.copySelf());
+    }
+
+    /** Check if the instance is empty.
+     * @return true if the instance is empty
+     */
+    public boolean isEmpty() {
+        return isEmpty(tree);
+    }
+
+    /** 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
+     */
+    public static boolean isEmpty(final BSPTree 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 !isInside(node);
+        }
+
+        // check both sides of the sub-tree
+        return isEmpty(node.getMinus()) && isEmpty(node.getPlus());
+
+    }
+
+    /** Check a leaf node inside attribute.
+     * @param node leaf node to check
+     * @return true if the leaf node is an inside node
+     */
+    private static boolean isInside(final BSPTree node) {
+        return (Boolean) node.getAttribute();
+    }
+
+    /** 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
+     */
+    public boolean contains(final Region region) {
+        return difference(region, this).isEmpty();
+    }
+
+    /** 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}
+     */
+    public Location checkPoint(final Point 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 node, final Point point) {
+        final BSPTree cell = node.getCell(point);
+        if (cell.getCut() == null) {
+            // the point is in the interior of a cell, just check the attribute
+            return isInside(cell) ? 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;
+
+    }
+
+    /** Get the complement of the region (exchanged interior/exterior).
+     * <p>The instance is not modified, a new region is built.</p>
+     * @return a new region, complement of the instance
+     */
+    public Region getComplement() {
+        return buildNew(recurseComplement(tree));
+    }
+
+    /** Recursively build the complement of a BSP tree.
+     * @param node current node of the original tree
+     * @return new tree, complement of the node
+     */
+    private static BSPTree recurseComplement(final BSPTree node) {
+        if (node.getCut() == null) {
+            return new BSPTree(isInside(node) ? Boolean.FALSE : Boolean.TRUE);
+        }
+
+        BoundaryAttribute attribute = (BoundaryAttribute) node.getAttribute();
+        if (attribute != null) {
+            final SubHyperplane plusOutside =
+                (attribute.plusInside == null) ? null : attribute.plusInside.copySelf();
+            final SubHyperplane plusInside  =
+                (attribute.plusOutside == null) ? null : attribute.plusOutside.copySelf();
+            attribute = new BoundaryAttribute(plusOutside, plusInside);
+        }
+
+        return new BSPTree(node.getCut().copySelf(),
+                           recurseComplement(node.getPlus()),
+                           recurseComplement(node.getMinus()),
+                           attribute);
+
+    }
+
+    /** 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#plusInside plusInside} and {@link
+     * BoundaryAttribute#plusOutside plusOutside} fields both 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
+     */
+    public BSPTree getTree(final boolean includeBoundaryAttributes) {
+        if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) {
+            // we need to compute the boundary attributes
+            recurseBuildBoundary(tree);
+        }
+        return tree;
+    }
+
+    /** 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>
+     * @see Region#getTree
+     */
+    public static class BoundaryAttribute {
+
+        /** Part of the node cut sub-hyperplane that belongs to the
+         * boundary and has the outside of the region on the plus side of
+         * its underlying hyperplane (may be null).
+         */
+        private final SubHyperplane plusOutside;
+
+        /** Part of the node cut sub-hyperplane that belongs to the
+         * boundary and has the inside of the region on the plus side of
+         * its underlying hyperplane (may be null).
+         */
+        private final SubHyperplane 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 plusOutside,
+                                 final SubHyperplane 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 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 getPlusInside() {
+            return plusInside;
+        }
+
+
+    }
+
+    /** Recursively build the boundary shell tree.
+     * @param node current node in the inout tree
+     */
+    private void recurseBuildBoundary(final BSPTree node) {
+        if (node.getCut() != null) {
+
+            SubHyperplane plusOutside = null;
+            SubHyperplane plusInside  = null;
+
+            // characterize the cut sub-hyperplane,
+            // first with respect to the plus sub-tree
+            final Characterization plusChar = new Characterization();
+            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 minusChar = new Characterization();
+                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 minusChar = new Characterization();
+                characterize(node.getMinus(), plusChar.getIn(), minusChar);
+                if (minusChar.hasOut()) {
+                    plusInside = minusChar.getOut();
+                }
+            }
+
+            node.setAttribute(new BoundaryAttribute(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 static void characterize(final BSPTree node, final SubHyperplane sub,
+                                     final Characterization characterization) {
+        if (node.getCut() == null) {
+            // we have reached a leaf node
+            final boolean inside = (Boolean) node.getAttribute();
+            characterization.add(sub, inside);
+        } else {
+            final Hyperplane hyperplane = node.getCut().getHyperplane();
+            switch (hyperplane.side(sub)) {
+            case PLUS:
+                characterize(node.getPlus(), sub, characterization);
+                break;
+            case MINUS:
+                characterize(node.getMinus(), sub, characterization);
+                break;
+            case BOTH:
+                final Hyperplane.SplitSubHyperplane split = hyperplane.split(sub);
+                characterize(node.getPlus(),  split.getPlus(),  characterization);
+                characterize(node.getMinus(), split.getMinus(), characterization);
+                break;
+            default:
+                // this should not happen
+                throw new RuntimeException("internal error");
+            }
+        }
+    }
+
+    /** 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 ...)
+     */
+    public double getBoundarySize() {
+        final BoundarySizeVisitor visitor = new BoundarySizeVisitor();
+        getTree(true).visit(visitor);
+        return visitor.getSize();
+    }
+
+    /** Visitor computing the boundary size. */
+    private static class BoundarySizeVisitor implements BSPTreeVisitor {
+
+        /** Size of the boundary. */
+        private double boundarySize;
+
+        /** Simple constructor.
+         */
+        public BoundarySizeVisitor() {
+            boundarySize = 0;
+        }
+
+        /** {@inheritDoc}*/
+        public Order visitOrder(final BSPTree node) {
+            return Order.MINUS_SUB_PLUS;
+        }
+
+        /** {@inheritDoc}*/
+        public void visitInternalNode(final BSPTree node) {
+            final BoundaryAttribute attribute = (BoundaryAttribute) node.getAttribute();
+            if (attribute.plusOutside != null) {
+                boundarySize += attribute.plusOutside.getRemainingRegion().getSize();
+            }
+            if (attribute.plusInside != null) {
+                boundarySize += attribute.plusInside.getRemainingRegion().getSize();
+            }
+        }
+
+        /** {@inheritDoc}*/
+        public void visitLeafNode(final BSPTree node) {
+        }
+
+        public double getSize() {
+            return boundarySize;
+        }
+
+    }
+
+    /** 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 ...)
+     */
+    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;
+    }
+
+    /** Get the barycenter of the instance.
+     * @return an object representing the barycenter
+     */
+    public Point getBarycenter() {
+        if (barycenter == null) {
+            computeGeometricalProperties();
+        }
+        return barycenter;
+    }
+
+    /** Set the barycenter of the instance.
+     * @param barycenter barycenter of the instance
+     */
+    protected void setBarycenter(final Point barycenter) {
+        this.barycenter = barycenter;
+    }
+
+    /** Compute some geometrical properties.
+     * <p>The properties to compute are the barycenter and the size.</p>
+     */
+    protected abstract void computeGeometricalProperties();
+
+    /** 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 Region applyTransform(final Transform transform) {
+
+        // transform the BSP tree
+        final Region tRegion = buildNew(recurseTransform(tree, transform));
+
+        // transform the barycenter
+        if (barycenter != null) {
+            tRegion.size = size;
+            tRegion.barycenter = transform.apply(barycenter);
+        }
+
+        return tRegion;
+
+    }
+
+    /** Recursively transform an inside/outside BSP-tree.
+     * @param node current BSP tree node
+     * @param transform transform to apply
+     * @return a new tree
+     */
+    private BSPTree recurseTransform(final BSPTree node, final Transform transform) {
+
+        if (node.getCut() == null) {
+            return new BSPTree(node.getAttribute());
+        }
+
+        final SubHyperplane  sub = node.getCut();
+        final SubHyperplane tSub = sub.applyTransform(transform);
+        BoundaryAttribute attribute = (BoundaryAttribute) node.getAttribute();
+        if (attribute != null) {
+            final SubHyperplane tPO =
+                (attribute.getPlusOutside() == null) ? null : attribute.getPlusOutside().applyTransform(transform);
+            final SubHyperplane tPI =
+                (attribute.getPlusInside()  == null) ? null  : attribute.getPlusInside().applyTransform(transform);
+            attribute = new BoundaryAttribute(tPO, tPI);
+        }
+
+        return new BSPTree(tSub,
+                           recurseTransform(node.getPlus(),  transform),
+                           recurseTransform(node.getMinus(), transform),
+                           attribute);
+
+    }
+
+    /** Compute the relative position of the instance with respect to an
+     * hyperplane.
+     * @param hyperplane reference hyperplane
+     * @return one of {@link Hyperplane.Side#PLUS Hyperplane.Side.PLUS}, {@link
+     * Hyperplane.Side#MINUS Hyperplane.Side.MINUS}, {@link Hyperplane.Side#BOTH
+     * Hyperplane.Side.BOTH} or {@link Hyperplane.Side#HYPER Hyperplane.Side.HYPER}
+     * (the latter result can occur only if the tree contains only one
+     * cut hyperplane)
+     */
+    public Hyperplane.Side side(final Hyperplane hyperplane) {
+        final Sides sides = new Sides();
+        recurseSides(tree, new SubHyperplane(hyperplane), sides);
+        return sides.plusFound() ?
+              (sides.minusFound() ? Hyperplane.Side.BOTH  : Hyperplane.Side.PLUS) :
+              (sides.minusFound() ? Hyperplane.Side.MINUS : Hyperplane.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 node, final SubHyperplane sub, final Sides sides) {
+
+        if (node.getCut() == null) {
+            if (isInside(node)) {
+                // this is an inside cell expanding across the hyperplane
+                sides.rememberPlusFound();
+                sides.rememberMinusFound();
+            }
+            return;
+        }
+
+        final Hyperplane hyperplane = node.getCut().getHyperplane();
+        switch (hyperplane.side(sub)) {
+        case PLUS :
+            // the sub-hyperplane is entirely in the plus sub-tree
+            if (sub.getHyperplane().side(node.getCut()) == Hyperplane.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 (sub.getHyperplane().side(node.getCut()) == Hyperplane.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 Hyperplane.SplitSubHyperplane split = hyperplane.split(sub);
+
+            // 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) || isInside(node.getPlus())) {
+                    sides.rememberPlusFound();
+                }
+                if ((node.getMinus().getCut() != null) || isInside(node.getMinus())) {
+                    sides.rememberMinusFound();
+                }
+            } else {
+                if ((node.getPlus().getCut() != null) || isInside(node.getPlus())) {
+                    sides.rememberMinusFound();
+                }
+                if ((node.getMinus().getCut() != null) || isInside(node.getMinus())) {
+                    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;
+        }
+
+    }
+
+    /** 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
+     */
+    public SubHyperplane intersection(final SubHyperplane 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 recurseIntersection(final BSPTree node, final SubHyperplane sub) {
+
+        if (node.getCut() == null) {
+            return isInside(node) ? sub.copySelf() : null;
+        }
+
+        final Hyperplane hyperplane = node.getCut().getHyperplane();
+        switch (hyperplane.side(sub)) {
+        case PLUS :
+            return recurseIntersection(node.getPlus(), sub);
+        case MINUS :
+            return recurseIntersection(node.getMinus(), sub);
+        case BOTH :
+            final Hyperplane.SplitSubHyperplane split = hyperplane.split(sub);
+            final SubHyperplane plus  = recurseIntersection(node.getPlus(),  split.getPlus());
+            final SubHyperplane minus = recurseIntersection(node.getMinus(), split.getMinus());
+            if (plus == null) {
+                return minus;
+            } else if (minus == null) {
+                return plus;
+            } else {
+                return new SubHyperplane(plus.getHyperplane(),
+                                         Region.union(plus.getRemainingRegion(),
+                                                      minus.getRemainingRegion()));
+            }
+        default :
+            return recurseIntersection(node.getPlus(),
+                                       recurseIntersection(node.getMinus(), sub));
+        }
+
+    }
+
+    /** 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 static Region union(final Region region1, final Region region2) {
+        final BSPTree tree = region1.tree.merge(region2.tree, new UnionMerger());
+        tree.visit(new InternalNodesCleaner());
+        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 static Region intersection(final Region region1, final Region region2) {
+        final BSPTree tree = region1.tree.merge(region2.tree, new IntersectionMerger());
+        tree.visit(new InternalNodesCleaner());
+        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 static Region xor(final Region region1, final Region region2) {
+        final BSPTree tree = region1.tree.merge(region2.tree, new XORMerger());
+        tree.visit(new InternalNodesCleaner());
+        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 static Region difference(final Region region1, final Region region2) {
+        final BSPTree tree = region1.tree.merge(region2.tree, new DifferenceMerger());
+        tree.visit(new InternalNodesCleaner());
+        return region1.buildNew(tree);
+    }
+
+    /** Leaf node / tree merger for union operation. */
+    private static final class UnionMerger implements BSPTree.LeafMerger {
+        /** {@inheritDoc} */
+        public BSPTree merge(final BSPTree leaf, final BSPTree tree,
+                             final BSPTree parentTree, final boolean isPlusChild,
+                             final boolean leafFromInstance) {
+            if (isInside(leaf)) {
+                // the leaf node represents an inside cell
+                leaf.insertInTree(parentTree, isPlusChild);
+                return leaf;
+            }
+            // the leaf node represents an outside cell
+            tree.insertInTree(parentTree, isPlusChild);
+            return tree;
+        }
+    };
+
+    /** Leaf node / tree merger for intersection operation. */
+    private static final class IntersectionMerger implements BSPTree.LeafMerger {
+        /** {@inheritDoc} */
+        public BSPTree merge(final BSPTree leaf, final BSPTree tree,
+                             final BSPTree parentTree, final boolean isPlusChild,
+                             final boolean leafFromInstance) {
+            if (isInside(leaf)) {
+                // the leaf node represents an inside cell
+                tree.insertInTree(parentTree, isPlusChild);
+                return tree;
+            }
+            // the leaf node represents an outside cell
+            leaf.insertInTree(parentTree, isPlusChild);
+            return leaf;
+        }
+    };
+
+    /** Leaf node / tree merger for xor operation. */
+    private static final class XORMerger implements BSPTree.LeafMerger {
+        /** {@inheritDoc} */
+        public BSPTree merge(final BSPTree leaf, final BSPTree tree,
+                             final BSPTree parentTree, final boolean isPlusChild,
+                             final boolean leafFromInstance) {
+            BSPTree t = tree;
+            if (isInside(leaf)) {
+                // the leaf node represents an inside cell
+                t = recurseComplement(t);
+            }
+            t.insertInTree(parentTree, isPlusChild);
+            return t;
+        }
+    };
+
+    /** Leaf node / tree merger for difference operation.
+     * <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 Naylor, Amanatides and Thibault paper. An error
+     * was detected and corrected in the figure 5.1 of the article for
+     * merging leaf nodes with complete trees. Contrary to what is said
+     * in the figure, the {@code ELSE} part of if is not the same
+     * as the first part with {@code T1} and {@codeT2}
+     * swapped. {@code T1} and {@codeT2} must be swapped
+     * everywhere <em>except</em> in the {@code RETURN} part of the
+     * {@code DIFFERENCE} operation: if {@codeT2} is an
+     * in-cell, we must return {@code Complement_Bspt(T2)}, not
+     * {@code Complement_Bspt(T1)}, and if {@codeT2} is an
+     * out-cell, we must return {@code T1}, not {@codeT2}</p>
+     */
+    private static final class DifferenceMerger implements BSPTree.LeafMerger {
+        /** {@inheritDoc} */
+        public BSPTree merge(final BSPTree leaf, final BSPTree tree,
+                             final BSPTree parentTree, final boolean isPlusChild,
+                             final boolean leafFromInstance) {
+            if (isInside(leaf)) {
+                // the leaf node represents an inside cell
+                final BSPTree argTree = recurseComplement(leafFromInstance ? tree : leaf);
+                argTree.insertInTree(parentTree, isPlusChild);
+                return argTree;
+            }
+            // the leaf node represents an outside cell
+            final BSPTree instanceTree = leafFromInstance ? leaf : tree;
+            instanceTree.insertInTree(parentTree, isPlusChild);
+            return instanceTree;
+        }
+    };
+
+    /** Visitor removing internal nodes attributes. */
+    private static final class InternalNodesCleaner implements BSPTreeVisitor {
+
+        /** {@inheritDoc} */
+        public Order visitOrder(final BSPTree node) {
+            return Order.PLUS_SUB_MINUS;
+        }
+
+        /** {@inheritDoc} */
+        public void visitInternalNode(final BSPTree node) {
+            node.setAttribute(null);
+        }
+
+        /** {@inheritDoc} */
+        public void visitLeafNode(final BSPTree node) {
+        }
+
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Region.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Region.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubHyperplane.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubHyperplane.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubHyperplane.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubHyperplane.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,138 @@
+/*
+ * 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.bsp.partitioning;
+
+/** 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>
+
+ * @version $Revision$ $Date$
+ */
+public class SubHyperplane {
+
+    /** Underlying hyperplane. */
+    private final Hyperplane hyperplane;
+
+    /** Remaining region of the hyperplane. */
+    private final Region remainingRegion;
+
+    /** Build a chopped hyperplane that is not chopped at all.
+     * @param hyperplane underlying hyperplane
+     */
+    public SubHyperplane(final Hyperplane hyperplane) {
+        this.hyperplane = hyperplane;
+        remainingRegion = hyperplane.wholeHyperplane();
+    }
+
+    /** Build a sub-hyperplane from an hyperplane and a region.
+     * @param hyperplane underlying hyperplane
+     * @param remainingRegion remaining region of the hyperplane
+     */
+    public SubHyperplane(final Hyperplane hyperplane, final Region remainingRegion) {
+        this.hyperplane      = hyperplane;
+        this.remainingRegion = remainingRegion;
+    }
+
+    /** 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 nodes attributes and immutable
+     * objects).</p>
+     * @return a new sub-hyperplane, copy of the instance
+     */
+    public SubHyperplane copySelf() {
+        return new SubHyperplane(hyperplane.copySelf(), remainingRegion.copySelf());
+    }
+
+    /** Get the underlying hyperplane.
+     * @return underlying hyperplane
+     */
+    public Hyperplane 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 getRemainingRegion() {
+        return 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 SubHyperplane applyTransform(final Transform transform) {
+        final Hyperplane tHyperplane = transform.apply(hyperplane);
+        final BSPTree tTree =
+            recurseTransform(remainingRegion.getTree(false), tHyperplane, transform);
+        return new SubHyperplane(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 recurseTransform(final BSPTree node, final Hyperplane transformed,
+                                     final Transform transform) {
+        if (node.getCut() == null) {
+            return new BSPTree(node.getAttribute());
+        }
+
+        Region.BoundaryAttribute attribute =
+            (Region.BoundaryAttribute) node.getAttribute();
+        if (attribute != null) {
+            final SubHyperplane tPO = (attribute.getPlusOutside() == null) ?
+                                      null :
+                                      transform.apply(attribute.getPlusOutside(),
+                                                      hyperplane, transformed);
+            final SubHyperplane tPI = (attribute.getPlusInside() == null) ?
+                                      null :
+                                      transform.apply(attribute.getPlusInside(),
+                                                      hyperplane, transformed);
+            attribute = new Region.BoundaryAttribute(tPO, tPI);
+        }
+
+        return new BSPTree(transform.apply(node.getCut(),
+                                           hyperplane, transformed),
+                                           recurseTransform(node.getPlus(), transformed,
+                                                            transform),
+                                                            recurseTransform(node.getMinus(), transformed,
+                                                                             transform),
+                                                                             attribute);
+
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubHyperplane.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubHyperplane.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubSpace.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubSpace.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubSpace.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubSpace.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,49 @@
+/*
+ * 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.bsp.partitioning;
+
+/** This interface represents a sub-space of a space.
+
+ * <p>Sub-spaces are the lower dimensions subsets of a n-dimensions
+ * space. The (n-1)-dimension sub-spaces are specific sub-spaces known
+ * as {@link Hyperplane hyperplanes}.</p>
+
+ * <p>In the 3D euclidean space, hyperplanes are 2D planes, and the 1D
+ * sub-spaces are lines.</p>
+
+ * @see Hyperplane
+ * @version $Revision$ $Date$
+ */
+public interface SubSpace {
+
+    /** Transform a space point into a sub-space point.
+     * @param point n-dimension point of the space
+     * @return (n-1)-dimension point of the sub-space corresponding to
+     * the specified space point
+     * @see #toSpace
+     */
+    Point toSubSpace(Point point);
+
+    /** Transform a sub-space point into a space point.
+     * @param point (n-1)-dimension point of the sub-space
+     * @return n-dimension point of the space corresponding to the
+     * specified sub-space point
+     * @see #toSubSpace
+     */
+    Point toSpace(Point point);
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubSpace.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/SubSpace.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Transform.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Transform.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Transform.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Transform.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,73 @@
+/*
+ * 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.bsp.partitioning;
+
+/** 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>
+
+ * @version $Revision$ $Date$
+ */
+public interface Transform {
+
+    /** Transform a point of a space.
+     * @param point point to transform
+     * @return a new object representing the transformed point
+     */
+    Point apply(Point point);
+
+    /** Transform an hyperplane of a space.
+     * @param hyperplane hyperplane to transform
+     * @return a new object representing the transformed hyperplane
+     */
+    Hyperplane apply(Hyperplane 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 apply(SubHyperplane sub, Hyperplane original, Hyperplane transformed);
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Transform.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/Transform.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/package.html
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/package.html?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/package.html (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/package.html Wed Feb  2 22:21:05 2011
@@ -0,0 +1,107 @@
+<!--
+   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.
+  -->
+<html>
+<body>
+This package provides classes to implement Binary Space Partition trees.
+
+<p>
+{@link org.apache.commons.bsp.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.bsp.partitioning.Region Region} class is
+devoted to this representation, it is build on top of the {@link
+org.apache.commons.bsp.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>
+
+</body>
+</html>

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/package.html
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/package.html
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision



Mime
View raw message