You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2011/06/03 20:06:22 UTC
svn commit: r1131125 [1/2] - in
/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning:
./ utilities/
Author: luc
Date: Fri Jun 3 18:06:21 2011
New Revision: 1131125
URL: http://svn.apache.org/viewvc?rev=1131125&view=rev
Log:
Improved type safety for Binary Space Partitioning and reduced complexity,
using generics where it was relevant and reorganizing interfaces.
Added:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java (with props)
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java (with props)
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java (with props)
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java (with props)
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/RegionFactory.java (with props)
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Side.java (with props)
Removed:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/SubSpace.java
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Region.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/SubHyperplane.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Transform.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/utilities/AVLTree.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/utilities/OrderedTuple.java
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java?rev=1131125&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java Fri Jun 3 18:06:21 2011
@@ -0,0 +1,641 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.geometry.partitioning;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.TreeSet;
+
+import org.apache.commons.math.geometry.Space;
+import org.apache.commons.math.geometry.Vector;
+
+/** Abstract class for all regions, independently of geometry type or dimension.
+
+ * @param <S> Type of the space.
+ * @param <T> Type of the sub-space.
+
+ * @version $Id:$
+ * @since 3.0
+ */
+public abstract class AbstractRegion<S extends Space, T extends Space> implements Region<S> {
+
+ /** Inside/Outside BSP tree. */
+ private BSPTree<S> tree;
+
+ /** Size of the instance. */
+ private double size;
+
+ /** Barycenter. */
+ private Vector<S> barycenter;
+
+ /** Build a region representing the whole space.
+ */
+ protected AbstractRegion() {
+ tree = new BSPTree<S>(Boolean.TRUE);
+ }
+
+ /** Build a region from an inside/outside BSP tree.
+ * <p>The leaf nodes of the BSP tree <em>must</em> have a
+ * {@code Boolean} attribute representing the inside status of
+ * the corresponding cell (true for inside cells, false for outside
+ * cells). In order to avoid building too many small objects, it is
+ * recommended to use the predefined constants
+ * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
+ * tree also <em>must</em> have either null internal nodes or
+ * internal nodes representing the boundary as specified in the
+ * {@link #getTree getTree} method).</p>
+ * @param tree inside/outside BSP tree representing the region
+ */
+ protected AbstractRegion(final BSPTree<S> tree) {
+ this.tree = tree;
+ }
+
+ /** Build a Region from a Boundary REPresentation (B-rep).
+ * <p>The boundary is provided as a collection of {@link
+ * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
+ * interior part of the region on its minus side and the exterior on
+ * its plus side.</p>
+ * <p>The boundary elements can be in any order, and can form
+ * several non-connected sets (like for example polygons with holes
+ * or a set of disjoints polyhedrons considered as a whole). In
+ * fact, the elements do not even need to be connected together
+ * (their topological connections are not used here). However, if the
+ * boundary does not really separate an inside open from an outside
+ * open (open having here its topological meaning), then subsequent
+ * calls to the {@link #checkPoint(Vector) checkPoint} method will not be
+ * meaningful anymore.</p>
+ * <p>If the boundary is empty, the region will represent the whole
+ * space.</p>
+ * @param boundary collection of boundary elements, as a
+ * collection of {@link SubHyperplane SubHyperplane} objects
+ */
+ protected AbstractRegion(final Collection<SubHyperplane<S>> boundary) {
+
+ if (boundary.size() == 0) {
+
+ // the tree represents the whole space
+ tree = new BSPTree<S>(Boolean.TRUE);
+
+ } else {
+
+ // sort the boundary elements in decreasing size order
+ // (we don't want equal size elements to be removed, so
+ // we use a trick to fool the TreeSet)
+ final TreeSet<SubHyperplane<S>> ordered = new TreeSet<SubHyperplane<S>>(new Comparator<SubHyperplane<S>>() {
+ public int compare(final SubHyperplane<S> o1, final SubHyperplane<S> o2) {
+ final double size1 = o1.getSize();
+ final double size2 = o2.getSize();
+ return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1);
+ }
+ });
+ ordered.addAll(boundary);
+
+ // build the tree top-down
+ tree = new BSPTree<S>();
+ insertCuts(tree, ordered);
+
+ // set up the inside/outside flags
+ tree.visit(new BSPTreeVisitor<S>() {
+
+ /** {@inheritDoc} */
+ public Order visitOrder(final BSPTree<S> node) {
+ return Order.PLUS_SUB_MINUS;
+ }
+
+ /** {@inheritDoc} */
+ public void visitInternalNode(final BSPTree<S> node) {
+ }
+
+ /** {@inheritDoc} */
+ public void visitLeafNode(final BSPTree<S> node) {
+ node.setAttribute((node == node.getParent().getPlus()) ?
+ Boolean.FALSE : Boolean.TRUE);
+ }
+ });
+
+ }
+
+ }
+
+ /** {@inheritDoc} */
+ public abstract AbstractRegion<S, T> buildNew(BSPTree<S> newTree);
+
+ /** Recursively build a tree by inserting cut sub-hyperplanes.
+ * @param node current tree node (it is a leaf node at the beginning
+ * of the call)
+ * @param boundary collection of edges belonging to the cell defined
+ * by the node
+ */
+ private void insertCuts(final BSPTree<S> node, final Collection<SubHyperplane<S>> boundary) {
+
+ final Iterator<SubHyperplane<S>> iterator = boundary.iterator();
+
+ // build the current level
+ Hyperplane<S> inserted = null;
+ while ((inserted == null) && iterator.hasNext()) {
+ inserted = iterator.next().getHyperplane();
+ if (!node.insertCut(inserted.copySelf())) {
+ inserted = null;
+ }
+ }
+
+ if (!iterator.hasNext()) {
+ return;
+ }
+
+ // distribute the remaining edges in the two sub-trees
+ final ArrayList<SubHyperplane<S>> plusList = new ArrayList<SubHyperplane<S>>();
+ final ArrayList<SubHyperplane<S>> minusList = new ArrayList<SubHyperplane<S>>();
+ while (iterator.hasNext()) {
+ final SubHyperplane<S> other = iterator.next();
+ switch (other.side(inserted)) {
+ case PLUS:
+ plusList.add(other);
+ break;
+ case MINUS:
+ minusList.add(other);
+ break;
+ case BOTH:
+ final SubHyperplane.SplitSubHyperplane<S> split = other.split(inserted);
+ plusList.add(split.getPlus());
+ minusList.add(split.getMinus());
+ break;
+ default:
+ // ignore the sub-hyperplanes belonging to the cut hyperplane
+ }
+ }
+
+ // recurse through lower levels
+ insertCuts(node.getPlus(), plusList);
+ insertCuts(node.getMinus(), minusList);
+
+ }
+
+ /** Build a convex region from an array of bounding hyperplanes.
+ * @param hyperplanes array of bounding hyperplanes (if null, an
+ * empty region will be built)
+ * @return a new convex region, or null if the collection is empty
+ */
+ public AbstractRegion(final Hyperplane<S>[] hyperplanes) {
+ if ((hyperplanes == null) || (hyperplanes.length == 0)) {
+ tree = new BSPTree<S>(Boolean.FALSE);
+ } else {
+
+ // use the first hyperplane to build the right class
+ tree = hyperplanes[0].wholeSpace().getTree(false);
+
+ // chop off parts of the space
+ BSPTree<S> node = tree;
+ node.setAttribute(Boolean.TRUE);
+ for (final Hyperplane<S> hyperplane : hyperplanes) {
+ if (node.insertCut(hyperplane)) {
+ node.setAttribute(null);
+ node.getPlus().setAttribute(Boolean.FALSE);
+ node = node.getMinus();
+ node.setAttribute(Boolean.TRUE);
+ }
+ }
+
+ }
+
+ }
+
+ /** {@inheritDoc} */
+ public AbstractRegion<S, T> copySelf() {
+ return buildNew(tree.copySelf());
+ }
+
+ /** {@inheritDoc} */
+ public boolean isEmpty() {
+ return isEmpty(tree);
+ }
+
+ /** {@inheritDoc} */
+ public boolean isEmpty(final BSPTree<S> node) {
+
+ // we use a recursive function rather than the BSPTreeVisitor
+ // interface because we can stop visiting the tree as soon as we
+ // have found an inside cell
+
+ if (node.getCut() == null) {
+ // if we find an inside node, the region is not empty
+ return !((Boolean) node.getAttribute());
+ }
+
+ // check both sides of the sub-tree
+ return isEmpty(node.getMinus()) && isEmpty(node.getPlus());
+
+ }
+
+ /** {@inheritDoc} */
+ public boolean contains(final Region<S> region) {
+ return new RegionFactory<S>().difference(region, this).isEmpty();
+ }
+
+ /** {@inheritDoc} */
+ public Location checkPoint(final Vector<S> point) {
+ return checkPoint(tree, point);
+ }
+
+ /** Check a point with respect to the region starting at a given node.
+ * @param node root node of the region
+ * @param point point to check
+ * @return a code representing the point status: either {@link
+ * Location#INSIDE}, {@link Location#OUTSIDE} or {@link Location#BOUNDARY}
+ */
+ protected Location checkPoint(final BSPTree<S> node, final Vector<S> point) {
+ final BSPTree<S> cell = node.getCell(point);
+ if (cell.getCut() == null) {
+ // the point is in the interior of a cell, just check the attribute
+ return ((Boolean) cell.getAttribute()) ? Location.INSIDE : Location.OUTSIDE;
+ }
+
+ // the point is on a cut-sub-hyperplane, is it on a boundary ?
+ final Location minusCode = checkPoint(cell.getMinus(), point);
+ final Location plusCode = checkPoint(cell.getPlus(), point);
+ return (minusCode == plusCode) ? minusCode : Location.BOUNDARY;
+
+ }
+
+ /** {@inheritDoc} */
+ public BSPTree<S> getTree(final boolean includeBoundaryAttributes) {
+ if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) {
+ // we need to compute the boundary attributes
+ recurseBuildBoundary(tree);
+ }
+ return tree;
+ }
+
+ /** Recursively build the boundary shell tree.
+ * @param node current node in the inout tree
+ */
+ private void recurseBuildBoundary(final BSPTree<S> node) {
+ if (node.getCut() != null) {
+
+ SubHyperplane<S> plusOutside = null;
+ SubHyperplane<S> plusInside = null;
+
+ // characterize the cut sub-hyperplane,
+ // first with respect to the plus sub-tree
+ final Characterization<S> plusChar = new Characterization<S>();
+ characterize(node.getPlus(), node.getCut().copySelf(), plusChar);
+
+ if (plusChar.hasOut()) {
+ // plusChar.out corresponds to a subset of the cut
+ // sub-hyperplane known to have outside cells on its plus
+ // side, we want to check if parts of this subset do have
+ // inside cells on their minus side
+ final Characterization<S> minusChar = new Characterization<S>();
+ characterize(node.getMinus(), plusChar.getOut(), minusChar);
+ if (minusChar.hasIn()) {
+ plusOutside = minusChar.getIn();
+ }
+ }
+
+ if (plusChar.hasIn()) {
+ // plusChar.in corresponds to a subset of the cut
+ // sub-hyperplane known to have inside cells on its plus
+ // side, we want to check if parts of this subset do have
+ // outside cells on their minus side
+ final Characterization<S> minusChar = new Characterization<S>();
+ characterize(node.getMinus(), plusChar.getIn(), minusChar);
+ if (minusChar.hasOut()) {
+ plusInside = minusChar.getOut();
+ }
+ }
+
+ node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside));
+ recurseBuildBoundary(node.getPlus());
+ recurseBuildBoundary(node.getMinus());
+
+ }
+ }
+
+ /** Filter the parts of an hyperplane belonging to the boundary.
+ * <p>The filtering consist in splitting the specified
+ * sub-hyperplane into several parts lying in inside and outside
+ * cells of the tree. The principle is to call this method twice for
+ * each cut sub-hyperplane in the tree, once one the plus node and
+ * once on the minus node. The parts that have the same flag
+ * (inside/inside or outside/outside) do not belong to the boundary
+ * while parts that have different flags (inside/outside or
+ * outside/inside) do belong to the boundary.</p>
+ * @param node current BSP tree node
+ * @param sub sub-hyperplane to characterize
+ * @param characterization placeholder where to put the characterized parts
+ */
+ private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub,
+ final Characterization<S> characterization) {
+ if (node.getCut() == null) {
+ // we have reached a leaf node
+ final boolean inside = (Boolean) node.getAttribute();
+ characterization.add(sub, inside);
+ } else {
+ final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
+ switch (sub.side(hyperplane)) {
+ case PLUS:
+ characterize(node.getPlus(), sub, characterization);
+ break;
+ case MINUS:
+ characterize(node.getMinus(), sub, characterization);
+ break;
+ case BOTH:
+ final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
+ characterize(node.getPlus(), split.getPlus(), characterization);
+ characterize(node.getMinus(), split.getMinus(), characterization);
+ break;
+ default:
+ // this should not happen
+ throw new RuntimeException("internal error");
+ }
+ }
+ }
+
+ /** {@inheritDoc} */
+ public double getBoundarySize() {
+ final BoundarySizeVisitor<S> visitor = new BoundarySizeVisitor<S>();
+ getTree(true).visit(visitor);
+ return visitor.getSize();
+ }
+
+ /** {@inheritDoc} */
+ public double getSize() {
+ if (barycenter == null) {
+ computeGeometricalProperties();
+ }
+ return size;
+ }
+
+ /** Set the size of the instance.
+ * @param size size of the instance
+ */
+ protected void setSize(final double size) {
+ this.size = size;
+ }
+
+ /** {@inheritDoc} */
+ public Vector<S> getBarycenter() {
+ if (barycenter == null) {
+ computeGeometricalProperties();
+ }
+ return barycenter;
+ }
+
+ /** Set the barycenter of the instance.
+ * @param barycenter barycenter of the instance
+ */
+ protected void setBarycenter(final Vector<S> barycenter) {
+ this.barycenter = barycenter;
+ }
+
+ /** Compute some geometrical properties.
+ * <p>The properties to compute are the barycenter and the size.</p>
+ */
+ protected abstract void computeGeometricalProperties();
+
+ /** {@inheritDoc} */
+ public Side side(final Hyperplane<S> hyperplane) {
+ final Sides sides = new Sides();
+ recurseSides(tree, hyperplane.wholeHyperplane(), sides);
+ return sides.plusFound() ?
+ (sides.minusFound() ? Side.BOTH : Side.PLUS) :
+ (sides.minusFound() ? Side.MINUS : Side.HYPER);
+ }
+
+ /** Search recursively for inside leaf nodes on each side of the given hyperplane.
+
+ * <p>The algorithm used here is directly derived from the one
+ * described in section III (<i>Binary Partitioning of a BSP
+ * Tree</i>) of the Bruce Naylor, John Amanatides and William
+ * Thibault paper <a
+ * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
+ * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph
+ * '90, Computer Graphics 24(4), August 1990, pp 115-124, published
+ * by the Association for Computing Machinery (ACM)..</p>
+
+ * @param node current BSP tree node
+ * @param sub sub-hyperplane
+ * @param sides object holding the sides found
+ */
+ private void recurseSides(final BSPTree<S> node, final SubHyperplane<S> sub, final Sides sides) {
+
+ if (node.getCut() == null) {
+ if ((Boolean) node.getAttribute()) {
+ // this is an inside cell expanding across the hyperplane
+ sides.rememberPlusFound();
+ sides.rememberMinusFound();
+ }
+ return;
+ }
+
+ final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
+ switch (sub.side(hyperplane)) {
+ case PLUS :
+ // the sub-hyperplane is entirely in the plus sub-tree
+ if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) {
+ if (!isEmpty(node.getMinus())) {
+ sides.rememberPlusFound();
+ }
+ } else {
+ if (!isEmpty(node.getMinus())) {
+ sides.rememberMinusFound();
+ }
+ }
+ if (!(sides.plusFound() && sides.minusFound())) {
+ recurseSides(node.getPlus(), sub, sides);
+ }
+ break;
+ case MINUS :
+ // the sub-hyperplane is entirely in the minus sub-tree
+ if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) {
+ if (!isEmpty(node.getPlus())) {
+ sides.rememberPlusFound();
+ }
+ } else {
+ if (!isEmpty(node.getPlus())) {
+ sides.rememberMinusFound();
+ }
+ }
+ if (!(sides.plusFound() && sides.minusFound())) {
+ recurseSides(node.getMinus(), sub, sides);
+ }
+ break;
+ case BOTH :
+ // the sub-hyperplane extends in both sub-trees
+ final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
+
+ // explore first the plus sub-tree
+ recurseSides(node.getPlus(), split.getPlus(), sides);
+
+ // if needed, explore the minus sub-tree
+ if (!(sides.plusFound() && sides.minusFound())) {
+ recurseSides(node.getMinus(), split.getMinus(), sides);
+ }
+ break;
+ default :
+ // the sub-hyperplane and the cut sub-hyperplane share the same hyperplane
+ if (node.getCut().getHyperplane().sameOrientationAs(sub.getHyperplane())) {
+ if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) {
+ sides.rememberPlusFound();
+ }
+ if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) {
+ sides.rememberMinusFound();
+ }
+ } else {
+ if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) {
+ sides.rememberMinusFound();
+ }
+ if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) {
+ sides.rememberPlusFound();
+ }
+ }
+ }
+
+ }
+
+ /** Utility class holding the already found sides. */
+ private static final class Sides {
+
+ /** Indicator of inside leaf nodes found on the plus side. */
+ private boolean plusFound;
+
+ /** Indicator of inside leaf nodes found on the plus side. */
+ private boolean minusFound;
+
+ /** Simple constructor.
+ */
+ public Sides() {
+ plusFound = false;
+ minusFound = false;
+ }
+
+ /** Remember the fact that inside leaf nodes have been found on the plus side.
+ */
+ public void rememberPlusFound() {
+ plusFound = true;
+ }
+
+ /** Check if inside leaf nodes have been found on the plus side.
+ * @return true if inside leaf nodes have been found on the plus side
+ */
+ public boolean plusFound() {
+ return plusFound;
+ }
+
+ /** Remember the fact that inside leaf nodes have been found on the minus side.
+ */
+ public void rememberMinusFound() {
+ minusFound = true;
+ }
+
+ /** Check if inside leaf nodes have been found on the minus side.
+ * @return true if inside leaf nodes have been found on the minus side
+ */
+ public boolean minusFound() {
+ return minusFound;
+ }
+
+ }
+
+ /** {@inheritDoc} */
+ public SubHyperplane<S> intersection(final SubHyperplane<S> sub) {
+ return recurseIntersection(tree, sub);
+ }
+
+ /** Recursively compute the parts of a sub-hyperplane that are
+ * contained in the region.
+ * @param node current BSP tree node
+ * @param sub sub-hyperplane traversing the region
+ * @return filtered sub-hyperplane
+ */
+ private SubHyperplane<S> recurseIntersection(final BSPTree<S> node, final SubHyperplane<S> sub) {
+
+ if (node.getCut() == null) {
+ return (Boolean) node.getAttribute() ? sub.copySelf() : null;
+ }
+
+ final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
+ switch (sub.side(hyperplane)) {
+ case PLUS :
+ return recurseIntersection(node.getPlus(), sub);
+ case MINUS :
+ return recurseIntersection(node.getMinus(), sub);
+ case BOTH :
+ final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
+ final SubHyperplane<S> plus = recurseIntersection(node.getPlus(), split.getPlus());
+ final SubHyperplane<S> minus = recurseIntersection(node.getMinus(), split.getMinus());
+ if (plus == null) {
+ return minus;
+ } else if (minus == null) {
+ return plus;
+ } else {
+ return plus.reunite(minus);
+ }
+ default :
+ return recurseIntersection(node.getPlus(),
+ recurseIntersection(node.getMinus(), sub));
+ }
+
+ }
+
+ /** Transform a region.
+ * <p>Applying a transform to a region consist in applying the
+ * transform to all the hyperplanes of the underlying BSP tree and
+ * of the boundary (and also to the sub-hyperplanes embedded in
+ * these hyperplanes) and to the barycenter. The instance is not
+ * modified, a new instance is built.</p>
+ * @param transform transform to apply
+ * @return a new region, resulting from the application of the
+ * transform to the instance
+ */
+ public AbstractRegion<S, T> applyTransform(final Transform<S, T> transform) {
+ return (AbstractRegion<S, T>) buildNew(recurseTransform(getTree(false), transform));
+ }
+
+ /** Recursively transform an inside/outside BSP-tree.
+ * @param node current BSP tree node
+ * @param transform transform to apply
+ * @return a new tree
+ */
+ @SuppressWarnings("unchecked")
+ private BSPTree<S> recurseTransform(final BSPTree<S> node, final Transform<S, T> transform) {
+
+ if (node.getCut() == null) {
+ return new BSPTree<S>(node.getAttribute());
+ }
+
+ final SubHyperplane<S> sub = node.getCut();
+ final SubHyperplane<S> tSub = ((AbstractSubHyperplane<S, T>) sub).applyTransform(transform);
+ BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute();
+ if (attribute != null) {
+ final SubHyperplane<S> tPO = (attribute.getPlusOutside() == null) ?
+ null : ((AbstractSubHyperplane<S, T>) attribute.getPlusOutside()).applyTransform(transform);
+ final SubHyperplane<S> tPI = (attribute.getPlusInside() == null) ?
+ null : ((AbstractSubHyperplane<S, T>) attribute.getPlusInside()).applyTransform(transform);
+ attribute = new BoundaryAttribute<S>(tPO, tPI);
+ }
+
+ return new BSPTree<S>(tSub,
+ recurseTransform(node.getPlus(), transform),
+ recurseTransform(node.getMinus(), transform),
+ attribute);
+
+ }
+
+}
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractRegion.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java?rev=1131125&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java Fri Jun 3 18:06:21 2011
@@ -0,0 +1,157 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.geometry.partitioning;
+
+import org.apache.commons.math.geometry.Space;
+import org.apache.commons.math.geometry.partitioning.SubHyperplane;
+
+/** This class implements the dimension-independent parts of {@link SubHyperplane}.
+
+ * <p>sub-hyperplanes are obtained when parts of an {@link
+ * Hyperplane hyperplane} are chopped off by other hyperplanes that
+ * intersect it. The remaining part is a convex region. Such objects
+ * appear in {@link BSPTree BSP trees} as the intersection of a cut
+ * hyperplane with the convex region which it splits, the chopping
+ * hyperplanes are the cut hyperplanes closer to the tree root.</p>
+
+ * @param <S> Type of the embedding space.
+
+ * @version $Revision$
+ * @since 3.0
+ */
+public abstract class AbstractSubHyperplane<S extends Space, T extends Space>
+ implements SubHyperplane<S> {
+
+ /** Underlying hyperplane. */
+ private final Hyperplane<S> hyperplane;
+
+ /** Remaining region of the hyperplane. */
+ private final Region<T> remainingRegion;
+
+ /** Build a sub-hyperplane from an hyperplane and a region.
+ * @param hyperplane underlying hyperplane
+ * @param remainingRegion remaining region of the hyperplane
+ */
+ protected AbstractSubHyperplane(final Hyperplane<S> hyperplane,
+ final Region<T> remainingRegion) {
+ this.hyperplane = hyperplane;
+ this.remainingRegion = remainingRegion;
+ }
+
+ /** Build a sub-hyperplane from an hyperplane and a region.
+ * @param hyperplane underlying hyperplane
+ * @param remainingRegion remaining region of the hyperplane
+ */
+ protected abstract AbstractSubHyperplane<S, T> buildNew(final Hyperplane<S> hyperplane,
+ final Region<T> remainingRegion);
+
+ /** {@inheritDoc} */
+ public AbstractSubHyperplane<S, T> copySelf() {
+ return buildNew(hyperplane, remainingRegion);
+ }
+
+ /** Get the underlying hyperplane.
+ * @return underlying hyperplane
+ */
+ public Hyperplane<S> getHyperplane() {
+ return hyperplane;
+ }
+
+ /** Get the remaining region of the hyperplane.
+ * <p>The returned region is expressed in the canonical hyperplane
+ * frame and has the hyperplane dimension. For example a chopped
+ * hyperplane in the 3D euclidean is a 2D plane and the
+ * corresponding region is a convex 2D polygon.</p>
+ * @return remaining region of the hyperplane
+ */
+ public Region<T> getRemainingRegion() {
+ return remainingRegion;
+ }
+
+ /** {@inheritDoc} */
+ public double getSize() {
+ return remainingRegion.getSize();
+ }
+
+ /** {@inheritDoc} */
+ public AbstractSubHyperplane<S, T> reunite(final SubHyperplane<S> other) {
+ @SuppressWarnings("unchecked")
+ AbstractSubHyperplane<S, T> o = (AbstractSubHyperplane<S, T>) other;
+ return buildNew(hyperplane,
+ new RegionFactory<T>().union(remainingRegion, o.remainingRegion));
+ }
+
+ /** Apply a transform to the instance.
+ * <p>The instance must be a (D-1)-dimension sub-hyperplane with
+ * respect to the transform <em>not</em> a (D-2)-dimension
+ * sub-hyperplane the transform knows how to transform by
+ * itself. The transform will consist in transforming first the
+ * hyperplane and then the all region using the various methods
+ * provided by the transform.</p>
+ * @param transform D-dimension transform to apply
+ * @return the transformed instance
+ */
+ public AbstractSubHyperplane<S, T> applyTransform(final Transform<S, T> transform) {
+ final Hyperplane<S> tHyperplane = transform.apply(hyperplane);
+ final BSPTree<T> tTree =
+ recurseTransform(remainingRegion.getTree(false), tHyperplane, transform);
+ return buildNew(tHyperplane, remainingRegion.buildNew(tTree));
+ }
+
+ /** Recursively transform a BSP-tree from a sub-hyperplane.
+ * @param node current BSP tree node
+ * @param transformed image of the instance hyperplane by the transform
+ * @param transform transform to apply
+ * @return a new tree
+ */
+ private BSPTree<T> recurseTransform(final BSPTree<T> node,
+ final Hyperplane<S> transformed,
+ final Transform<S, T> transform) {
+ if (node.getCut() == null) {
+ return new BSPTree<T>(node.getAttribute());
+ }
+
+ @SuppressWarnings("unchecked")
+ BoundaryAttribute<T> attribute =
+ (BoundaryAttribute<T>) node.getAttribute();
+ if (attribute != null) {
+ final SubHyperplane<T> tPO = (attribute.getPlusOutside() == null) ?
+ null : transform.apply(attribute.getPlusOutside(), hyperplane, transformed);
+ final SubHyperplane<T> tPI = (attribute.getPlusInside() == null) ?
+ null : transform.apply(attribute.getPlusInside(), hyperplane, transformed);
+ attribute = new BoundaryAttribute<T>(tPO, tPI);
+ }
+
+ return new BSPTree<T>(transform.apply(node.getCut(), hyperplane, transformed),
+ recurseTransform(node.getPlus(), transformed, transform),
+ recurseTransform(node.getMinus(), transformed, transform),
+ attribute);
+
+ }
+
+ /** {@inheritDoc} */
+ public abstract Side side(Hyperplane<S> hyperplane);
+
+ /** {@inheritDoc} */
+ public abstract SplitSubHyperplane<S> split(Hyperplane<S> hyperplane);
+
+ /** {@inheritDoc} */
+ public boolean isEmpty() {
+ return remainingRegion.isEmpty();
+ }
+
+}
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/AbstractSubHyperplane.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java?rev=1131125&r1=1131124&r2=1131125&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTree.java Fri Jun 3 18:06:21 2011
@@ -16,7 +16,8 @@
*/
package org.apache.commons.math.geometry.partitioning;
-import org.apache.commons.math.geometry.partitioning.Hyperplane.Side;
+import org.apache.commons.math.geometry.Vector;
+import org.apache.commons.math.geometry.Space;
import org.apache.commons.math.util.FastMath;
/** This class represent a Binary Space Partition tree.
@@ -53,21 +54,24 @@ import org.apache.commons.math.util.Fast
* Computer Graphics 24(4), August 1990, pp 115-124, published by the
* Association for Computing Machinery (ACM).</p>
- * @version $Revision$ $Date$
+ * @param <S> Type of the space.
+
+ * @version $Id:$
+ * @since 3.0
*/
-public class BSPTree {
+public class BSPTree<S extends Space> {
/** Cut sub-hyperplane. */
- private SubHyperplane cut;
+ private SubHyperplane<S> cut;
/** Tree at the plus side of the cut hyperplane. */
- private BSPTree plus;
+ private BSPTree<S> plus;
/** Tree at the minus side of the cut hyperplane. */
- private BSPTree minus;
+ private BSPTree<S> minus;
/** Parent tree. */
- private BSPTree parent;
+ private BSPTree<S> parent;
/** Application-defined attribute. */
private Object attribute;
@@ -106,7 +110,7 @@ public class BSPTree {
* @param attribute attribute associated with the node (may be null)
* @see #insertCut
*/
- public BSPTree(final SubHyperplane cut, final BSPTree plus, final BSPTree minus,
+ public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus,
final Object attribute) {
this.cut = cut;
this.plus = plus;
@@ -140,15 +144,15 @@ public class BSPTree {
* the cell now has two leaf child nodes)
* @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
*/
- public boolean insertCut(final Hyperplane hyperplane) {
+ public boolean insertCut(final Hyperplane<S> hyperplane) {
if (cut != null) {
plus.parent = null;
minus.parent = null;
}
- final SubHyperplane chopped = fitToCell(new SubHyperplane(hyperplane));
- if (chopped.getRemainingRegion().isEmpty()) {
+ final SubHyperplane<S> chopped = fitToCell(hyperplane.wholeHyperplane());
+ if (chopped.isEmpty()) {
cut = null;
plus = null;
minus = null;
@@ -156,9 +160,9 @@ public class BSPTree {
}
cut = chopped;
- plus = new BSPTree();
+ plus = new BSPTree<S>();
plus.parent = this;
- minus = new BSPTree();
+ minus = new BSPTree<S>();
minus.parent = this;
return true;
@@ -171,13 +175,13 @@ public class BSPTree {
* objects).</p>
* @return a new tree, copy of the instance
*/
- public BSPTree copySelf() {
+ public BSPTree<S> copySelf() {
if (cut == null) {
- return new BSPTree(attribute);
+ return new BSPTree<S>(attribute);
}
- return new BSPTree(cut.copySelf(), plus.copySelf(), minus.copySelf(),
+ return new BSPTree<S>(cut.copySelf(), plus.copySelf(), minus.copySelf(),
attribute);
}
@@ -185,7 +189,7 @@ public class BSPTree {
/** Get the cut sub-hyperplane.
* @return cut sub-hyperplane, null if this is a leaf tree
*/
- public SubHyperplane getCut() {
+ public SubHyperplane<S> getCut() {
return cut;
}
@@ -193,7 +197,7 @@ public class BSPTree {
* @return tree on the plus side of the cut hyperplane, null if this
* is a leaf tree
*/
- public BSPTree getPlus() {
+ public BSPTree<S> getPlus() {
return plus;
}
@@ -201,14 +205,14 @@ public class BSPTree {
* @return tree on the minus side of the cut hyperplane, null if this
* is a leaf tree
*/
- public BSPTree getMinus() {
+ public BSPTree<S> getMinus() {
return minus;
}
/** Get the parent node.
* @return parent node, null if the node has no parents
*/
- public BSPTree getParent() {
+ public BSPTree<S> getParent() {
return parent;
}
@@ -233,7 +237,7 @@ public class BSPTree {
/** Visit the BSP tree nodes.
* @param visitor object visiting the tree nodes
*/
- public void visit(final BSPTreeVisitor visitor) {
+ public void visit(final BSPTreeVisitor<S> visitor) {
if (cut == null) {
visitor.visitLeafNode(this);
} else {
@@ -283,13 +287,13 @@ public class BSPTree {
* @return a new sub-hyperplane, gueranteed to have no part outside
* of the instance cell
*/
- private SubHyperplane fitToCell(final SubHyperplane sub) {
- SubHyperplane s = sub;
- for (BSPTree tree = this; tree.parent != null; tree = tree.parent) {
+ private SubHyperplane<S> fitToCell(final SubHyperplane<S> sub) {
+ SubHyperplane<S> s = sub;
+ for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
if (tree == tree.parent.plus) {
- s = tree.parent.cut.getHyperplane().split(s).getPlus();
+ s = s.split(tree.parent.cut.getHyperplane()).getPlus();
} else {
- s = tree.parent.cut.getHyperplane().split(s).getMinus();
+ s = s.split(tree.parent.cut.getHyperplane()).getMinus();
}
}
return s;
@@ -302,7 +306,7 @@ public class BSPTree {
* @param point point to check
* @return the tree cell to which the point belongs (can be
*/
- public BSPTree getCell(final Point point) {
+ public BSPTree<S> getCell(final Vector<S> point) {
if (cut == null) {
return this;
@@ -356,7 +360,7 @@ public class BSPTree {
* tree</code>, this value can be ignored if parentTree is not null
* since all connections have already been established
*/
- public BSPTree merge(final BSPTree tree, final LeafMerger leafMerger) {
+ public BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger) {
return merge(tree, leafMerger, null, false);
}
@@ -375,8 +379,8 @@ public class BSPTree {
* tree</code>, this value can be ignored if parentTree is not null
* since all connections have already been established
*/
- private BSPTree merge(final BSPTree tree, final LeafMerger leafMerger,
- final BSPTree parentTree, final boolean isPlusChild) {
+ private BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger,
+ final BSPTree<S> parentTree, final boolean isPlusChild) {
if (cut == null) {
// cell/tree operation
return leafMerger.merge(this, tree, parentTree, isPlusChild, true);
@@ -385,7 +389,7 @@ public class BSPTree {
return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
} else {
// tree/tree operation
- final BSPTree merged = tree.split(cut);
+ final BSPTree<S> merged = tree.split(cut);
if (parentTree != null) {
merged.parent = parentTree;
if (isPlusChild) {
@@ -401,7 +405,7 @@ public class BSPTree {
merged.condense();
if (merged.cut != null) {
merged.cut =
- merged.fitToCell(new SubHyperplane(merged.cut.getHyperplane()));
+ merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane());
}
return merged;
@@ -423,9 +427,11 @@ public class BSPTree {
* cells would use four different objects to implement the final
* merging phase of the four set operations union, intersection,
* difference and symmetric difference (exclusive or).</p>
+ * @param <SpacePoint> Type of the space points.
+ * @param <SubSpacePoint> Type of the sub-space points.
* @version $Revision$ $Date$
*/
- public static interface LeafMerger {
+ public static interface LeafMerger<S extends Space> {
/** Merge a leaf node and a tree node.
* <p>This method is called at the end of a recursive merging
@@ -456,9 +462,8 @@ public class BSPTree {
* @return the BSP tree resulting from the merging (may be one of
* the arguments)
*/
- BSPTree merge(BSPTree leaf, BSPTree tree,
- BSPTree parentTree, boolean isPlusChild,
- boolean leafFromInstance);
+ BSPTree<S> merge(BSPTree<S> leaf, BSPTree<S> tree, BSPTree<S> parentTree,
+ boolean isPlusChild, boolean leafFromInstance);
}
@@ -480,26 +485,27 @@ public class BSPTree {
* sub-hyperplane, the two parts of the split instance as its two
* sub-trees and a null parent
*/
- public BSPTree split(final SubHyperplane sub) {
+ public BSPTree<S> split(final SubHyperplane<S> sub) {
if (cut == null) {
- return new BSPTree(sub, copySelf(), new BSPTree(attribute), null);
+ return new BSPTree<S>(sub, copySelf(),
+ new BSPTree<S>(attribute), null);
}
- final Hyperplane cHyperplane = cut.getHyperplane();
- final Hyperplane sHyperplane = sub.getHyperplane();
- switch (cHyperplane.side(sub)) {
+ final Hyperplane<S> cHyperplane = cut.getHyperplane();
+ final Hyperplane<S> sHyperplane = sub.getHyperplane();
+ switch (sub.side(cHyperplane)) {
case PLUS :
{ // the partitioning sub-hyperplane is entirely in the plus sub-tree
- final BSPTree split = plus.split(sub);
- if (sHyperplane.side(cut) == Side.PLUS) {
- split.plus = new BSPTree(cut.copySelf(),
- split.plus, minus.copySelf(), attribute);
+ final BSPTree<S> split = plus.split(sub);
+ if (cut.side(sHyperplane) == Side.PLUS) {
+ split.plus =
+ new BSPTree<S>(cut.copySelf(), split.plus, minus.copySelf(), attribute);
split.plus.condense();
split.plus.parent = split;
} else {
- split.minus = new BSPTree(cut.copySelf(),
- split.minus, minus.copySelf(), attribute);
+ split.minus =
+ new BSPTree<S>(cut.copySelf(), split.minus, minus.copySelf(), attribute);
split.minus.condense();
split.minus.parent = split;
}
@@ -507,15 +513,15 @@ public class BSPTree {
}
case MINUS :
{ // the partitioning sub-hyperplane is entirely in the minus sub-tree
- final BSPTree split = minus.split(sub);
- if (sHyperplane.side(cut) == Side.PLUS) {
- split.plus = new BSPTree(cut.copySelf(),
- plus.copySelf(), split.plus, attribute);
+ final BSPTree<S> split = minus.split(sub);
+ if (cut.side(sHyperplane) == Side.PLUS) {
+ split.plus =
+ new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.plus, attribute);
split.plus.condense();
split.plus.parent = split;
} else {
- split.minus = new BSPTree(cut.copySelf(),
- plus.copySelf(), split.minus, attribute);
+ split.minus =
+ new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.minus, attribute);
split.minus.condense();
split.minus.parent = split;
}
@@ -523,15 +529,14 @@ public class BSPTree {
}
case BOTH :
{
- final Hyperplane.SplitSubHyperplane cutParts = sHyperplane.split(cut);
- final Hyperplane.SplitSubHyperplane subParts = cHyperplane.split(sub);
- final BSPTree split = new BSPTree(sub,
- plus.split(subParts.getPlus()),
- minus.split(subParts.getMinus()),
- null);
+ final SubHyperplane.SplitSubHyperplane<S> cutParts = cut.split(sHyperplane);
+ final SubHyperplane.SplitSubHyperplane<S> subParts = sub.split(cHyperplane);
+ final BSPTree<S> split =
+ new BSPTree<S>(sub, plus.split(subParts.getPlus()), minus.split(subParts.getMinus()),
+ null);
split.plus.cut = cutParts.getPlus();
split.minus.cut = cutParts.getMinus();
- final BSPTree tmp = split.plus.minus;
+ final BSPTree<S> tmp = split.plus.minus;
split.plus.minus = split.minus.plus;
split.plus.minus.parent = split.plus;
split.minus.plus = tmp;
@@ -542,8 +547,8 @@ public class BSPTree {
}
default :
return cHyperplane.sameOrientationAs(sHyperplane) ?
- new BSPTree(sub, plus.copySelf(), minus.copySelf(), attribute) :
- new BSPTree(sub, minus.copySelf(), plus.copySelf(), attribute);
+ new BSPTree<S>(sub, plus.copySelf(), minus.copySelf(), attribute) :
+ new BSPTree<S>(sub, minus.copySelf(), plus.copySelf(), attribute);
}
}
@@ -557,7 +562,7 @@ public class BSPTree {
* parentTree is null
* @see LeafMerger
*/
- public void insertInTree(final BSPTree parentTree, final boolean isPlusChild) {
+ public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) {
// set up parent/child links
parent = parentTree;
@@ -573,19 +578,19 @@ public class BSPTree {
if (cut != null) {
// explore the parent nodes from here towards tree root
- for (BSPTree tree = this; tree.parent != null; tree = tree.parent) {
+ for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
// this is an hyperplane of some parent node
- final Hyperplane hyperplane = tree.parent.cut.getHyperplane();
+ final Hyperplane<S> hyperplane = tree.parent.cut.getHyperplane();
// chop off the parts of the inserted tree that extend
// on the wrong side of this parent hyperplane
if (tree == tree.parent.plus) {
- cut = hyperplane.split(cut).getPlus();
+ cut = cut.split(hyperplane).getPlus();
plus.chopOffMinus(hyperplane);
minus.chopOffMinus(hyperplane);
} else {
- cut = hyperplane.split(cut).getMinus();
+ cut = cut.split(hyperplane).getMinus();
plus.chopOffPlus(hyperplane);
minus.chopOffPlus(hyperplane);
}
@@ -602,13 +607,13 @@ public class BSPTree {
/** Chop off parts of the tree.
* <p>The instance is modified in place, all the parts that are on
- * the minus side of the chopping hyperplane are disgarded, only the
+ * the minus side of the chopping hyperplane are discarded, only the
* parts on the plus side remain.</p>
* @param hyperplane chopping hyperplane
*/
- private void chopOffMinus(final Hyperplane hyperplane) {
+ private void chopOffMinus(final Hyperplane<S> hyperplane) {
if (cut != null) {
- cut = hyperplane.split(cut).getPlus();
+ cut = cut.split(hyperplane).getPlus();
plus.chopOffMinus(hyperplane);
minus.chopOffMinus(hyperplane);
}
@@ -616,13 +621,13 @@ public class BSPTree {
/** Chop off parts of the tree.
* <p>The instance is modified in place, all the parts that are on
- * the plus side of the chopping hyperplane are disgarded, only the
+ * the plus side of the chopping hyperplane are discarded, only the
* parts on the minus side remain.</p>
* @param hyperplane chopping hyperplane
*/
- private void chopOffPlus(final Hyperplane hyperplane) {
+ private void chopOffPlus(final Hyperplane<S> hyperplane) {
if (cut != null) {
- cut = hyperplane.split(cut).getMinus();
+ cut = cut.split(hyperplane).getMinus();
plus.chopOffPlus(hyperplane);
minus.chopOffPlus(hyperplane);
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java?rev=1131125&r1=1131124&r2=1131125&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BSPTreeVisitor.java Fri Jun 3 18:06:21 2011
@@ -16,6 +16,8 @@
*/
package org.apache.commons.math.geometry.partitioning;
+import org.apache.commons.math.geometry.Space;
+
/** This interface is used to visit {@link BSPTree BSP tree} nodes.
* <p>Navigation through {@link BSPTree BSP trees} can be done using
@@ -38,12 +40,16 @@ package org.apache.commons.math.geometry
* </li>
* </ul>
+ * @param <SpacePoint> Type of the space points.
+ * @param <SubSpacePoint> Type of the sub-space points.
+
* @see BSPTree
* @see SubHyperplane
- * @version $Revision$ $Date$
+ * @version $Id:$
+ * @since 3.0
*/
-public interface BSPTreeVisitor {
+public interface BSPTreeVisitor<S extends Space> {
/** Enumerate for visit order with respect to plus sub-tree, minus sub-tree and cut sub-hyperplane. */
enum Order {
@@ -90,7 +96,7 @@ public interface BSPTreeVisitor {
* {@link Order#MINUS_PLUS_SUB}, {@link Order#MINUS_SUB_PLUS},
* {@link Order#SUB_PLUS_MINUS}, {@link Order#SUB_MINUS_PLUS}
*/
- Order visitOrder(BSPTree node);
+ Order visitOrder(BSPTree<S> node);
/** Visit a BSP tree node node having a non-null sub-hyperplane.
* <p>It is guaranteed that this method will be called after {@link
@@ -99,12 +105,12 @@ public interface BSPTreeVisitor {
* @param node BSP node guaranteed to have a non null cut sub-hyperplane
* @see #visitLeafNode
*/
- void visitInternalNode(BSPTree node);
+ void visitInternalNode(BSPTree<S> node);
/** Visit a leaf BSP tree node node having a null sub-hyperplane.
* @param node leaf BSP node having a null sub-hyperplane
* @see #visitInternalNode
*/
- void visitLeafNode(BSPTree node);
+ void visitLeafNode(BSPTree<S> node);
}
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java?rev=1131125&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java Fri Jun 3 18:06:21 2011
@@ -0,0 +1,84 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.geometry.partitioning;
+
+import org.apache.commons.math.geometry.Space;
+
+/** Class holding boundary attributes.
+ * <p>This class is used for the attributes associated with the
+ * nodes of region boundary shell trees returned by the {@link
+ * Region#getTree Region.getTree}. It contains the
+ * parts of the node cut sub-hyperplane that belong to the
+ * boundary.</p>
+ * <p>This class is a simple placeholder, it does not provide any
+ * processing methods.</p>
+ * @param <S> Type of the space.
+ * @see Region#getTree
+ * @version $Id:$
+ * @since 3.0
+ */
+public class BoundaryAttribute<S extends Space> {
+
+ /** Part of the node cut sub-hyperplane that belongs to the
+ * boundary and has the outside of the region on the plus side of
+ * its underlying hyperplane (may be null).
+ */
+ final SubHyperplane<S> plusOutside;
+
+ /** Part of the node cut sub-hyperplane that belongs to the
+ * boundary and has the inside of the region on the plus side of
+ * its underlying hyperplane (may be null).
+ */
+ final SubHyperplane<S> plusInside;
+
+ /** Simple constructor.
+ * @param plusOutside part of the node cut sub-hyperplane that
+ * belongs to the boundary and has the outside of the region on
+ * the plus side of its underlying hyperplane (may be null)
+ * @param plusInside part of the node cut sub-hyperplane that
+ * belongs to the boundary and has the inside of the region on the
+ * plus side of its underlying hyperplane (may be null)
+ */
+ public BoundaryAttribute(final SubHyperplane<S> plusOutside,
+ final SubHyperplane<S> plusInside) {
+ this.plusOutside = plusOutside;
+ this.plusInside = plusInside;
+ }
+
+ /** Get the part of the node cut sub-hyperplane that belongs to the
+ * boundary and has the outside of the region on the plus side of
+ * its underlying hyperplane.
+ * @return part of the node cut sub-hyperplane that belongs to the
+ * boundary and has the outside of the region on the plus side of
+ * its underlying hyperplane
+ */
+ public SubHyperplane<S> getPlusOutside() {
+ return plusOutside;
+ }
+
+ /** Get the part of the node cut sub-hyperplane that belongs to the
+ * boundary and has the inside of the region on the plus side of
+ * its underlying hyperplane.
+ * @return part of the node cut sub-hyperplane that belongs to the
+ * boundary and has the inside of the region on the plus side of
+ * its underlying hyperplane
+ */
+ public SubHyperplane<S> getPlusInside() {
+ return plusInside;
+ }
+
+}
\ No newline at end of file
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundaryAttribute.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java?rev=1131125&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java Fri Jun 3 18:06:21 2011
@@ -0,0 +1,66 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.geometry.partitioning;
+
+import org.apache.commons.math.geometry.Space;
+
+/** Visitor computing the boundary size.
+ * @param <S> Type of the space.
+ * @version $Id:$
+ * @since 3.0
+ */
+class BoundarySizeVisitor<S extends Space> implements BSPTreeVisitor<S> {
+
+ /** Size of the boundary. */
+ private double boundarySize;
+
+ /** Simple constructor.
+ */
+ public BoundarySizeVisitor() {
+ boundarySize = 0;
+ }
+
+ /** {@inheritDoc}*/
+ public Order visitOrder(final BSPTree<S> node) {
+ return Order.MINUS_SUB_PLUS;
+ }
+
+ /** {@inheritDoc}*/
+ public void visitInternalNode(final BSPTree<S> node) {
+ @SuppressWarnings("unchecked")
+ final BoundaryAttribute<S> attribute =
+ (BoundaryAttribute<S>) node.getAttribute();
+ if (attribute.plusOutside != null) {
+ boundarySize += attribute.plusOutside.getSize();
+ }
+ if (attribute.plusInside != null) {
+ boundarySize += attribute.plusInside.getSize();
+ }
+ }
+
+ /** {@inheritDoc}*/
+ public void visitLeafNode(final BSPTree<S> node) {
+ }
+
+ /** Get the size of the boundary.
+ * @return size of the boundary
+ */
+ public double getSize() {
+ return boundarySize;
+ }
+
+}
\ No newline at end of file
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/BoundarySizeVisitor.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java?rev=1131125&r1=1131124&r2=1131125&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Characterization.java Fri Jun 3 18:06:21 2011
@@ -16,16 +16,20 @@
*/
package org.apache.commons.math.geometry.partitioning;
+import org.apache.commons.math.geometry.Space;
+
/** Characterization of a sub-hyperplane.
- * @version $Revision$ $Date$
+ * @param <S> Type of the space.
+ * @version $Id:$
+ * @since 3.0
*/
-class Characterization {
+class Characterization<S extends Space> {
/** Parts of the sub-hyperplane that have inside cells on the tested side. */
- private SubHyperplane in;
+ private SubHyperplane<S> in;
/** Parts of the sub-hyperplane that have outside cells on the tested side. */
- private SubHyperplane out;
+ private SubHyperplane<S> out;
/** Create an empty characterization of a sub-hyperplane.
*/
@@ -38,13 +42,13 @@ class Characterization {
* @return true if the sub-hyperplane that have inside cells on the tested side
*/
public boolean hasIn() {
- return (in != null) && (!in.getRemainingRegion().isEmpty());
+ return (in != null) && (!in.isEmpty());
}
/** Get the parts of the sub-hyperplane that have inside cells on the tested side.
* @return parts of the sub-hyperplane that have inside cells on the tested side
*/
- public SubHyperplane getIn() {
+ public SubHyperplane<S> getIn() {
return in;
}
@@ -52,13 +56,13 @@ class Characterization {
* @return true if the sub-hyperplane that have outside cells on the tested side
*/
public boolean hasOut() {
- return (out != null) && (!out.getRemainingRegion().isEmpty());
+ return (out != null) && (!out.isEmpty());
}
/** Get the parts of the sub-hyperplane that have outside cells on the tested side.
* @return parts of the sub-hyperplane that have outside cells on the tested side
*/
- public SubHyperplane getOut() {
+ public SubHyperplane<S> getOut() {
return out;
}
@@ -67,22 +71,18 @@ class Characterization {
* @param inside if true, the part added as an inside cell on the tested side, otherwise
* it has an outside cell on the tested side
*/
- public void add(final SubHyperplane sub, final boolean inside) {
+ public void add(final SubHyperplane<S> sub, final boolean inside) {
if (inside) {
if (in == null) {
in = sub;
} else {
- in = new SubHyperplane(in.getHyperplane(),
- Region.union(in.getRemainingRegion(),
- sub.getRemainingRegion()));
+ in = in.reunite(sub);
}
} else {
if (out == null) {
out = sub;
} else {
- out = new SubHyperplane(out.getHyperplane(),
- Region.union(out.getRemainingRegion(),
- sub.getRemainingRegion()));
+ out = out.reunite(sub);
}
}
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java?rev=1131125&r1=1131124&r2=1131125&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/partitioning/Hyperplane.java Fri Jun 3 18:06:21 2011
@@ -16,6 +16,9 @@
*/
package org.apache.commons.math.geometry.partitioning;
+import org.apache.commons.math.geometry.Vector;
+import org.apache.commons.math.geometry.Space;
+
/** This interface represents an hyperplane of a space.
* <p>The most prominent place where hyperplane appears in space
@@ -27,26 +30,12 @@ package org.apache.commons.math.geometry
* space). They can be more exotic objects in specific fields, for
* example a circle on the surface of the unit sphere.</p>
- * @version $Revision$ $Date$
- */
-public interface Hyperplane extends SubSpace {
-
- /** Enumerate for specifying sides of the hyperplane. */
- enum Side {
-
- /** Code for the plus side of the hyperplane. */
- PLUS,
+ * @param <SpacePoint> Type of the space points.
- /** Code for the minus side of the hyperplane. */
- MINUS,
-
- /** Code for elements crossing the hyperplane from plus to minus side. */
- BOTH,
-
- /** Code for the hyperplane itself. */
- HYPER;
-
- }
+ * @version $Id:$
+ * @since 3.0
+ */
+public interface Hyperplane<S extends Space> {
/** Copy the instance.
* <p>The instance created is completely independant of the original
@@ -54,7 +43,7 @@ public interface Hyperplane extends SubS
* shared (except for immutable objects).</p>
* @return a new hyperplane, copy of the instance
*/
- Hyperplane copySelf();
+ Hyperplane<S> copySelf();
/** Get the offset (oriented distance) of a point.
* <p>The offset is 0 if the point is on the underlying hyperplane,
@@ -64,7 +53,7 @@ public interface Hyperplane extends SubS
* @param point point to check
* @return offset of the point
*/
- double getOffset(Point point);
+ double getOffset(Vector<S> point);
/** Check if the instance has the same orientation as another hyperplane.
* <p>This method is expected to be called on parallel hyperplanes
@@ -78,82 +67,16 @@ public interface Hyperplane extends SubS
* @return true if the instance and the other hyperplane have
* the same orientation
*/
- boolean sameOrientationAs(Hyperplane other);
+ boolean sameOrientationAs(Hyperplane<S> other);
- /** Build the sub-space shared by the instance and another hyperplane.
- * @param other other hyperplane
- * @return a sub-space at the intersection of the instance and the
- * other sub-space (it has a dimension one unit less than the
- * instance)
+ /** Build a sub-hyperplane covering the whole hyperplane.
+ * @return a sub-hyperplane covering the whole hyperplane
*/
- SubSpace intersection(Hyperplane other);
-
- /** Build a region covering the whole hyperplane.
- * <p>The region build is restricted to the sub-space defined by the
- * hyperplane. This means that the regions points are consistent
- * with the argument of the {@link SubSpace#toSpace toSpace} method
- * and with the return value of the {@link SubSpace#toSubSpace
- * toSubSpace} method.<p>
- * @return a region covering the whole hyperplane
- */
- Region wholeHyperplane();
+ SubHyperplane<S> wholeHyperplane();
/** Build a region covering the whole space.
* @return a region containing the instance
*/
- Region wholeSpace();
-
- /** Compute the relative position of a sub-hyperplane with respect
- * to the instance.
- * @param sub sub-hyperplane to check
- * @return one of {@link Side#PLUS}, {@link Side#MINUS}, {@link Side#BOTH},
- * {@link Side#HYPER}
- */
- Side side(SubHyperplane sub);
-
- /** Split a sub-hyperplane in two parts by the instance.
- * @param sub sub-hyperplane to split
- * @return an object containing both the part of the sub-hyperplane
- * on the plus side of the instance and the part of the
- * sub-hyperplane on the minus side of the instance
- */
- SplitSubHyperplane split(SubHyperplane sub);
-
- /** Class holding the results of the {@link Hyperplane#split Hyperplane.split}
- * method. */
- class SplitSubHyperplane {
-
- /** Part of the sub-hyperplane on the plus side of the splitting hyperplane. */
- private final SubHyperplane plus;
-
- /** Part of the sub-hyperplane on the minus side of the splitting hyperplane. */
- private final SubHyperplane minus;
-
- /** Build a SplitSubHyperplane from its parts.
- * @param plus part of the sub-hyperplane on the plus side of the
- * splitting hyperplane
- * @param minus part of the sub-hyperplane on the minus side of the
- * splitting hyperplane
- */
- public SplitSubHyperplane(final SubHyperplane plus, final SubHyperplane minus) {
- this.plus = plus;
- this.minus = minus;
- }
-
- /** Get the part of the sub-hyperplane on the plus side of the splitting hyperplane.
- * @return part of the sub-hyperplane on the plus side of the splitting hyperplane
- */
- public SubHyperplane getPlus() {
- return plus;
- }
-
- /** Get the part of the sub-hyperplane on the minus side of the splitting hyperplane.
- * @return part of the sub-hyperplane on the minus side of the splitting hyperplane
- */
- public SubHyperplane getMinus() {
- return minus;
- }
-
- }
+ Region<S> wholeSpace();
}