Navigation through {@link BSPTree BSP trees} can be done using + * two different point of views:

+ *-
+ *
- + * 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 + * + *
- + * 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. + * + *

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.

+ * @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. + *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.

+ * @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. + + *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.

+ + * @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. + *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).

+ * @return a new hyperplane, copy of the instance + */ + Hyperplane copySelf(); + + /** Get the offset (oriented distance) of a point. + *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.

+ * @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. + *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 *not*
+ * re-check for parallelism, only for orientation, typically by
+ * testing something like the sign of the dot-products of
+ * normals.

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.

+ * @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. + *

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.

+ * @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. + + *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 *inside* the region from
+ * points considered to be *outside* of it. In between, there
+ * may be points on the *boundary* of the region.

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.

+ + *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.

+ + * @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. + *The leaf nodes of the BSP tree *must* 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 *must* have either null internal nodes or
+ * internal nodes representing the boundary as specified in the
+ * {@link #getTree getTree} method).

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.

+ *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.

+ *If the boundary is empty, the region will represent the whole + * space.

+ * @param boundary collection of boundary elements, as a + * collection of {@link SubHyperplane SubHyperplane} objects + */ + protected Region(final CollectionThis method allow to create new instances without knowing + * exactly the type of the region. It is an application of the + * prototype design pattern.

+ *The leaf nodes of the BSP tree *must* 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 *must* have either null internal nodes or
+ * internal nodes representing the boundary as specified in the
+ * {@link #getTree getTree} method).

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).

+ * @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 (The instance is not modified, a new region is built.

+ * @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. + + *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.

+ + *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.

+ + *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.

+ + * @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. + *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.

+ *This class is a simple placeholder, it does not provide any + * processing methods.

+ * @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. + *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.

+ * @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. + *The properties to compute are the barycenter and the size.

+ */ + protected abstract void computeGeometricalProperties(); + + /** Transform a region. + *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.

+ * @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. + + *The algorithm used here is directly derived from the one
+ * described in section III (*Binary Partitioning of a BSP
+ * Tree*) of the Bruce Naylor, John Amanatides and William
+ * Thibault paper Merging
+ * BSP Trees Yields Polyhedral Set Operations Proc. Siggraph
+ * '90, Computer Graphics 24(4), August 1990, pp 115-124, published
+ * by the Association for Computing Machinery (ACM)..

The parts of the sub-hyperplane that belong to the boundary are
+ * *not* included in the resulting parts.

The algorithm used here is directly derived from the one
+ * described in section III (*Binary Partitioning of a BSP
+ * Tree*) 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 *except* 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}

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.

+ + * @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. + *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).

+ * @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. + *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.

+ * @return remaining region of the hyperplane + */ + public Region getRemainingRegion() { + return remainingRegion; + } + + /** Apply a transform to the instance. + *The instance must be a (D-1)-dimension sub-hyperplane with
+ * respect to the transform *not* 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.

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}.

+ + *In the 3D euclidean space, hyperplanes are 2D planes, and the 1D + * sub-spaces are lines.

+ + * @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. + *Inversible affine transform include for example scalings, + * translations, rotations.

+ + *Transforms are dimension-specific. The consistency rules between + * the three {@code apply} methods are the following ones for a + * transformed defined for dimension D:

+ *-
+ *
- + * the transform can be applied to a point in the + * D-dimension space using its {@link #apply(Point)} + * method + * + *
- + * the transform can be applied to a (D-1)-dimension + * hyperplane in the D-dimension space using its + * {@link #apply(Hyperplane)} method + * + *
- + * 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 + * + *

+{@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). +

+ ++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. +

+ +
+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 *not* 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).
+

+Rather than simply associating the internal nodes with an hyperplane,
+we consider *sub-hyperplanes* 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.
+

+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
+`O(log(n))`

where `n`

is the number of facets)
+or if the first tree levels close to the root discriminate large parts
+of the total space.
+

+One of the main sources for the development of this package was Bruce +Naylor, John Amanatides and William Thibault paper Merging +BSP Trees Yields Polyhedral Set Operations 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 here. +

+ + + 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