Return-Path: Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: (qmail 43480 invoked from network); 2 Feb 2011 22:21:33 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 2 Feb 2011 22:21:33 -0000 Received: (qmail 17725 invoked by uid 500); 2 Feb 2011 22:21:33 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 17547 invoked by uid 500); 2 Feb 2011 22:21:32 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 17534 invoked by uid 99); 2 Feb 2011 22:21:32 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 02 Feb 2011 22:21:32 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 02 Feb 2011 22:21:28 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 5B8CC2388AC8; Wed, 2 Feb 2011 22:21:08 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: commits@commons.apache.org From: luc@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20110202222108.5B8CC2388AC8@eris.apache.org> 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. + + *

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

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

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.

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

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

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

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 Collection 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 ordered = new TreeSet(new Comparator() { + 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. + *

This method allow to create new instances without knowing + * exactly the type of the region. It is an application of the + * prototype design pattern.

+ *

+ * @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 boundary) { + + final Iterator 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 plusList = new ArrayList(); + final ArrayList minusList = new ArrayList(); + 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 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. + *

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

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

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

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

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

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}

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

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.

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

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

+ + * @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 + * not been applied to it) + * @param transformed hyperplane in which the sub-hyperplane is + * defined (this is the transformed hyperplane, the transform + * has 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 @@ + + + +This package provides classes to implement Binary Space Partition trees. + +

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