Repository: commons-math Updated Branches: refs/heads/master e11c00085 -> d21d3a94a
Added splitters in Boundary attributes. Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/6525cc40 Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/6525cc40 Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/6525cc40 Branch: refs/heads/master Commit: 6525cc4035fe8df3308c03f0ca9f450728e122ac Parents: 26ee481 Author: Luc Maisonobe <l...@apache.org> Authored: Sun Nov 30 18:09:06 2014 +0100 Committer: Luc Maisonobe <l...@apache.org> Committed: Tue Dec 2 15:24:31 2014 +0100 ---------------------------------------------------------------------- src/changes/changes.xml | 4 ++ .../geometry/partitioning/AbstractRegion.java | 67 +++++++++++++----- .../partitioning/AbstractSubHyperplane.java | 67 +++++++++++++----- .../partitioning/BoundaryAttribute.java | 32 +++++++++ .../geometry/partitioning/BoundaryBuilder.java | 23 ++++-- .../geometry/partitioning/Characterization.java | 67 ++++++++++++++---- .../math3/geometry/partitioning/NodesSet.java | 72 +++++++++++++++++++ .../geometry/partitioning/RegionFactory.java | 74 ++++++++++++++++---- 8 files changed, 338 insertions(+), 68 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-math/blob/6525cc40/src/changes/changes.xml ---------------------------------------------------------------------- diff --git a/src/changes/changes.xml b/src/changes/changes.xml index c8f0afd..46ad704 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -73,6 +73,10 @@ Users are encouraged to upgrade to this version as this release not 2. A few methods in the FastMath class are in fact slower that their counterpart in either Math or StrictMath (cf. MATH-740 and MATH-901). "> + <action dev="luc" type="add" > + Boundary attributes in regions now provides the BSP tree nodes that + were used to split the sub-hyperplane froming the boundary part of the facet. + </action> <action dev="luc" type="fix" issue="MATH-1162" > Fixed a problem with vanishing cut sub-hyperplanes during BSP tree merging. </action> http://git-wip-us.apache.org/repos/asf/commons-math/blob/6525cc40/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java index 3fca476..fd3dcc7 100644 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java @@ -19,7 +19,9 @@ package org.apache.commons.math3.geometry.partitioning; import java.util.ArrayList; import java.util.Collection; import java.util.Comparator; +import java.util.HashMap; import java.util.Iterator; +import java.util.Map; import java.util.TreeSet; import org.apache.commons.math3.geometry.Point; @@ -349,7 +351,7 @@ public abstract class AbstractRegion<S extends Space, T extends Space> implement /** {@inheritDoc} */ public BSPTree<S> getTree(final boolean includeBoundaryAttributes) { if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) { - // we need to compute the boundary attributes + // compute the boundary attributes tree.visit(new BoundaryBuilder<S>()); } return tree; @@ -465,36 +467,65 @@ public abstract class AbstractRegion<S extends Space, T extends Space> implement * transform to the instance */ public AbstractRegion<S, T> applyTransform(final Transform<S, T> transform) { - return buildNew(recurseTransform(getTree(false), transform)); + + // transform the tree, except for boundary attribute splitters + final Map<BSPTree<S>, BSPTree<S>> map = new HashMap<BSPTree<S>, BSPTree<S>>(); + final BSPTree<S> transformedTree = recurseTransform(getTree(false), transform, map); + + // set up the boundary attributes splitters + for (final Map.Entry<BSPTree<S>, BSPTree<S>> entry : map.entrySet()) { + if (entry.getKey().getCut() != null) { + @SuppressWarnings("unchecked") + BoundaryAttribute<S> original = (BoundaryAttribute<S>) entry.getKey().getAttribute(); + if (original != null) { + @SuppressWarnings("unchecked") + BoundaryAttribute<S> transformed = (BoundaryAttribute<S>) entry.getValue().getAttribute(); + for (final BSPTree<S> splitter : original.getSplitters()) { + transformed.getSplitters().add(map.get(splitter)); + } + } + } + } + + return buildNew(transformedTree); + } /** Recursively transform an inside/outside BSP-tree. * @param node current BSP tree node * @param transform transform to apply + * @param map transformed nodes map * @return a new tree */ @SuppressWarnings("unchecked") - private BSPTree<S> recurseTransform(final BSPTree<S> node, final Transform<S, T> transform) { + private BSPTree<S> recurseTransform(final BSPTree<S> node, final Transform<S, T> transform, + final Map<BSPTree<S>, BSPTree<S>> map) { + final BSPTree<S> transformedNode; if (node.getCut() == null) { - return new BSPTree<S>(node.getAttribute()); - } + transformedNode = new BSPTree<S>(node.getAttribute()); + } else { + + 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); + // we start with an empty list of splitters, it will be filled in out of recursion + attribute = new BoundaryAttribute<S>(tPO, tPI, new NodesSet<S>()); + } - 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); + transformedNode = new BSPTree<S>(tSub, + recurseTransform(node.getPlus(), transform, map), + recurseTransform(node.getMinus(), transform, map), + attribute); } - return new BSPTree<S>(tSub, - recurseTransform(node.getPlus(), transform), - recurseTransform(node.getMinus(), transform), - attribute); + map.put(node, transformedNode); + return transformedNode; } http://git-wip-us.apache.org/repos/asf/commons-math/blob/6525cc40/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java index 8a4931f..3fd6b54 100644 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java @@ -16,6 +16,9 @@ */ package org.apache.commons.math3.geometry.partitioning; +import java.util.HashMap; +import java.util.Map; + import org.apache.commons.math3.geometry.Space; /** This class implements the dimension-independent parts of {@link SubHyperplane}. @@ -107,39 +110,67 @@ public abstract class AbstractSubHyperplane<S extends Space, T extends Space> */ public AbstractSubHyperplane<S, T> applyTransform(final Transform<S, T> transform) { final Hyperplane<S> tHyperplane = transform.apply(hyperplane); + + // transform the tree, except for boundary attribute splitters + final Map<BSPTree<T>, BSPTree<T>> map = new HashMap<BSPTree<T>, BSPTree<T>>(); final BSPTree<T> tTree = - recurseTransform(remainingRegion.getTree(false), tHyperplane, transform); + recurseTransform(remainingRegion.getTree(false), tHyperplane, transform, map); + + // set up the boundary attributes splitters + for (final Map.Entry<BSPTree<T>, BSPTree<T>> entry : map.entrySet()) { + if (entry.getKey().getCut() != null) { + @SuppressWarnings("unchecked") + BoundaryAttribute<T> original = (BoundaryAttribute<T>) entry.getKey().getAttribute(); + if (original != null) { + @SuppressWarnings("unchecked") + BoundaryAttribute<T> transformed = (BoundaryAttribute<T>) entry.getValue().getAttribute(); + for (final BSPTree<T> splitter : original.getSplitters()) { + transformed.getSplitters().add(map.get(splitter)); + } + } + } + } + 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 + * @param map transformed nodes map * @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()); - } + final Transform<S, T> transform, + final Map<BSPTree<T>, BSPTree<T>> map) { - @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); + final BSPTree<T> transformedNode; + if (node.getCut() == null) { + transformedNode = new BSPTree<T>(node.getAttribute()); + } else { + + @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); + // we start with an empty list of splitters, it will be filled in out of recursion + attribute = new BoundaryAttribute<T>(tPO, tPI, new NodesSet<T>()); + } + + transformedNode = new BSPTree<T>(transform.apply(node.getCut(), hyperplane, transformed), + recurseTransform(node.getPlus(), transformed, transform, map), + recurseTransform(node.getMinus(), transformed, transform, map), + attribute); } - return new BSPTree<T>(transform.apply(node.getCut(), hyperplane, transformed), - recurseTransform(node.getPlus(), transformed, transform), - recurseTransform(node.getMinus(), transformed, transform), - attribute); + map.put(node, transformedNode); + return transformedNode; } http://git-wip-us.apache.org/repos/asf/commons-math/blob/6525cc40/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java index ea7d9a7..dad884c 100644 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.java @@ -45,6 +45,9 @@ public class BoundaryAttribute<S extends Space> { */ private final SubHyperplane<S> plusInside; + /** Sub-hyperplanes that were used to split the boundary part. */ + private final NodesSet<S> splitters; + /** Simple constructor. * @param plusOutside part of the node cut sub-hyperplane that * belongs to the boundary and has the outside of the region on @@ -52,11 +55,33 @@ public class BoundaryAttribute<S extends Space> { * @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) + * @deprecated as of 3.4, the constructor has been replaced by a new one + * which is not public anymore, as it is intended to be used only by + * {@link BoundaryBuilder} */ + @Deprecated public BoundaryAttribute(final SubHyperplane<S> plusOutside, final SubHyperplane<S> plusInside) { + this(plusOutside, plusInside, null); + } + + /** 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) + * @param splitters sub-hyperplanes that were used to + * split the boundary part (may be null) + * @since 3.4 + */ + BoundaryAttribute(final SubHyperplane<S> plusOutside, + final SubHyperplane<S> plusInside, + final NodesSet<S> splitters) { this.plusOutside = plusOutside; this.plusInside = plusInside; + this.splitters = splitters; } /** Get the part of the node cut sub-hyperplane that belongs to the @@ -81,4 +106,11 @@ public class BoundaryAttribute<S extends Space> { return plusInside; } + /** Get the sub-hyperplanes that were used to split the boundary part. + * @return sub-hyperplanes that were used to split the boundary part + */ + public NodesSet<S> getSplitters() { + return splitters; + } + } http://git-wip-us.apache.org/repos/asf/commons-math/blob/6525cc40/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java index 80038f1..cea4de3 100644 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java @@ -28,11 +28,6 @@ import org.apache.commons.math3.geometry.Space; */ class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> { - /** Simple constructor. - */ - public BoundaryBuilder() { - } - /** {@inheritDoc} */ public Order visitOrder(BSPTree<S> node) { return Order.PLUS_MINUS_SUB; @@ -43,6 +38,7 @@ class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> { SubHyperplane<S> plusOutside = null; SubHyperplane<S> plusInside = null; + NodesSet<S> splitters = null; // characterize the cut sub-hyperplane, // first with respect to the plus sub-tree @@ -57,6 +53,9 @@ class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> { // this part belongs to the boundary, // it has the outside on its plus side and the inside on its minus side plusOutside = minusChar.insideTouching(); + splitters = new NodesSet<S>(); + splitters.addAll(minusChar.getInsideSplitters()); + splitters.addAll(plusChar.getOutsideSplitters()); } } @@ -69,11 +68,23 @@ class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> { // this part belongs to the boundary, // it has the inside on its plus side and the outside on its minus side plusInside = minusChar.outsideTouching(); + if (splitters == null) { + splitters = new NodesSet<S>(); + } + splitters.addAll(minusChar.getOutsideSplitters()); + splitters.addAll(plusChar.getInsideSplitters()); + } + } + + if (splitters != null) { + // the parent nodes are natural splitters for boundary sub-hyperplanes + for (BSPTree<S> up = node.getParent(); up != null; up = up.getParent()) { + splitters.add(up); } } // set the boundary attribute at non-leaf nodes - node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside)); + node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside, splitters)); } http://git-wip-us.apache.org/repos/asf/commons-math/blob/6525cc40/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java index a67f873..58efe0f 100644 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java @@ -16,6 +16,9 @@ */ package org.apache.commons.math3.geometry.partitioning; +import java.util.ArrayList; +import java.util.List; + import org.apache.commons.math3.exception.MathInternalError; import org.apache.commons.math3.geometry.Space; @@ -32,6 +35,12 @@ class Characterization<S extends Space> { /** Part of the cut sub-hyperplane that touch inside cells. */ private SubHyperplane<S> insideTouching; + /** Nodes that were used to split the outside touching part. */ + private final NodesSet<S> outsideSplitters; + + /** Nodes that were used to split the outside touching part. */ + private final NodesSet<S> insideSplitters; + /** Simple constructor. * <p>Characterization consists in splitting the specified * sub-hyperplane into several parts lying in inside and outside @@ -45,9 +54,11 @@ class Characterization<S extends Space> { * @param sub sub-hyperplane to characterize */ public Characterization(final BSPTree<S> node, final SubHyperplane<S> sub) { - outsideTouching = null; - insideTouching = null; - characterize(node, sub); + outsideTouching = null; + insideTouching = null; + outsideSplitters = new NodesSet<S>(); + insideSplitters = new NodesSet<S>(); + characterize(node, sub, new ArrayList<BSPTree<S>>()); } /** Filter the parts of an hyperplane belonging to the boundary. @@ -61,29 +72,33 @@ class Characterization<S extends Space> { * outside/inside) do belong to the boundary.</p> * @param node current BSP tree node * @param sub sub-hyperplane to characterize + * @param splitters nodes that did split the current one */ - private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub) { + private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub, + final List<BSPTree<S>> splitters) { if (node.getCut() == null) { // we have reached a leaf node final boolean inside = (Boolean) node.getAttribute(); if (inside) { - addInsideTouching(sub); + addInsideTouching(sub, splitters); } else { - addOutsideTouching(sub); + addOutsideTouching(sub, splitters); } } else { final Hyperplane<S> hyperplane = node.getCut().getHyperplane(); switch (sub.side(hyperplane)) { case PLUS: - characterize(node.getPlus(), sub); + characterize(node.getPlus(), sub, splitters); break; case MINUS: - characterize(node.getMinus(), sub); + characterize(node.getMinus(), sub, splitters); break; case BOTH: final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane); - characterize(node.getPlus(), split.getPlus()); - characterize(node.getMinus(), split.getMinus()); + splitters.add(node); + characterize(node.getPlus(), split.getPlus(), splitters); + characterize(node.getMinus(), split.getMinus(), splitters); + splitters.remove(splitters.size() - 1); break; default: // this should not happen @@ -94,24 +109,30 @@ class Characterization<S extends Space> { /** Add a part of the cut sub-hyperplane known to touch an outside cell. * @param sub part of the cut sub-hyperplane known to touch an outside cell + * @param splitters sub-hyperplanes that did split the current one */ - private void addOutsideTouching(final SubHyperplane<S> sub) { + private void addOutsideTouching(final SubHyperplane<S> sub, + final List<BSPTree<S>> splitters) { if (outsideTouching == null) { outsideTouching = sub; } else { outsideTouching = outsideTouching.reunite(sub); } + outsideSplitters.addAll(splitters); } /** Add a part of the cut sub-hyperplane known to touch an inside cell. * @param sub part of the cut sub-hyperplane known to touch an inside cell + * @param splitters sub-hyperplanes that did split the current one */ - private void addInsideTouching(final SubHyperplane<S> sub) { + private void addInsideTouching(final SubHyperplane<S> sub, + final List<BSPTree<S>> splitters) { if (insideTouching == null) { insideTouching = sub; } else { insideTouching = insideTouching.reunite(sub); } + insideSplitters.addAll(splitters); } /** Check if the cut sub-hyperplane touches outside cells. @@ -129,6 +150,17 @@ class Characterization<S extends Space> { return outsideTouching; } + /** Get the nodes that were used to split the outside touching part. + * <p> + * Splitting nodes are internal nodes (i.e. they have a non-null + * cut sub-hyperplane). + * </p> + * @return nodes that were used to split the outside touching part + */ + public NodesSet<S> getOutsideSplitters() { + return outsideSplitters; + } + /** Check if the cut sub-hyperplane touches inside cells. * @return true if the cut sub-hyperplane touches inside cells */ @@ -144,4 +176,15 @@ class Characterization<S extends Space> { return insideTouching; } + /** Get the nodes that were used to split the inside touching part. + * <p> + * Splitting nodes are internal nodes (i.e. they have a non-null + * cut sub-hyperplane). + * </p> + * @return nodes that were used to split the inside touching part + */ + public NodesSet<S> getInsideSplitters() { + return insideSplitters; + } + } http://git-wip-us.apache.org/repos/asf/commons-math/blob/6525cc40/src/main/java/org/apache/commons/math3/geometry/partitioning/NodesSet.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/NodesSet.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/NodesSet.java new file mode 100644 index 0000000..688279a --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/NodesSet.java @@ -0,0 +1,72 @@ +/* + * 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.math3.geometry.partitioning; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +import org.apache.commons.math3.geometry.Space; + +/** Set of {@link BSPTree BSP tree} nodes. + * @see BoundaryAttribute + * @param <S> Type of the space. + * @since 3.4 + */ +public class NodesSet<S extends Space> implements Iterable<BSPTree<S>> { + + /** List of sub-hyperplanes. */ + private List<BSPTree<S>> list; + + /** Simple constructor. + */ + public NodesSet() { + list = new ArrayList<BSPTree<S>>(); + } + + /** Add a node if not already known. + * @param node node to add + */ + public void add(final BSPTree<S> node) { + + for (final BSPTree<S> existing : list) { + if (node == existing) { + // the node is already known, don't add it + return; + } + } + + // the node was not known, add it + list.add(node); + + } + + /** Add nodes if they are not already known. + * @param iterator nodes iterator + */ + public void addAll(final Iterable<BSPTree<S>> iterator) { + for (final BSPTree<S> node : iterator) { + add(node); + } + } + + /** {@inheritDoc} */ + public Iterator<BSPTree<S>> iterator() { + return list.iterator(); + } + +} http://git-wip-us.apache.org/repos/asf/commons-math/blob/6525cc40/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java index 47b28bd..8cf2603 100644 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/RegionFactory.java @@ -16,6 +16,9 @@ */ package org.apache.commons.math3.geometry.partitioning; +import java.util.HashMap; +import java.util.Map; + import org.apache.commons.math3.geometry.Point; import org.apache.commons.math3.geometry.Space; import org.apache.commons.math3.geometry.euclidean.twod.PolygonsSet; @@ -129,6 +132,11 @@ public class RegionFactory<S extends Space> { * region independent region will be built * @return a new region, complement of the specified one */ + /** Get the complement of the region (exchanged interior/exterior). + * @param region region to complement, it will not modified, a new + * region independent region will be built + * @return a new region, complement of the specified one + */ public Region<S> getComplement(final Region<S> region) { return region.buildNew(recurseComplement(region.getTree(false))); } @@ -138,24 +146,62 @@ public class RegionFactory<S extends Space> { * @return new tree, complement of the node */ private BSPTree<S> recurseComplement(final BSPTree<S> node) { - if (node.getCut() == null) { - return new BSPTree<S>(((Boolean) node.getAttribute()) ? Boolean.FALSE : Boolean.TRUE); + + // transform the tree, except for boundary attribute splitters + final Map<BSPTree<S>, BSPTree<S>> map = new HashMap<BSPTree<S>, BSPTree<S>>(); + final BSPTree<S> transformedTree = recurseComplement(node, map); + + // set up the boundary attributes splitters + for (final Map.Entry<BSPTree<S>, BSPTree<S>> entry : map.entrySet()) { + if (entry.getKey().getCut() != null) { + @SuppressWarnings("unchecked") + BoundaryAttribute<S> original = (BoundaryAttribute<S>) entry.getKey().getAttribute(); + if (original != null) { + @SuppressWarnings("unchecked") + BoundaryAttribute<S> transformed = (BoundaryAttribute<S>) entry.getValue().getAttribute(); + for (final BSPTree<S> splitter : original.getSplitters()) { + transformed.getSplitters().add(map.get(splitter)); + } + } + } } - @SuppressWarnings("unchecked") - BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute(); - if (attribute != null) { - final SubHyperplane<S> plusOutside = - (attribute.getPlusInside() == null) ? null : attribute.getPlusInside().copySelf(); - final SubHyperplane<S> plusInside = - (attribute.getPlusOutside() == null) ? null : attribute.getPlusOutside().copySelf(); - attribute = new BoundaryAttribute<S>(plusOutside, plusInside); + return transformedTree; + + } + + /** Recursively build the complement of a BSP tree. + * @param node current node of the original tree + * @param map transformed nodes map + * @return new tree, complement of the node + */ + private BSPTree<S> recurseComplement(final BSPTree<S> node, + final Map<BSPTree<S>, BSPTree<S>> map) { + + final BSPTree<S> transformedNode; + if (node.getCut() == null) { + transformedNode = new BSPTree<S>(((Boolean) node.getAttribute()) ? Boolean.FALSE : Boolean.TRUE); + } else { + + @SuppressWarnings("unchecked") + BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute(); + if (attribute != null) { + final SubHyperplane<S> plusOutside = + (attribute.getPlusInside() == null) ? null : attribute.getPlusInside().copySelf(); + final SubHyperplane<S> plusInside = + (attribute.getPlusOutside() == null) ? null : attribute.getPlusOutside().copySelf(); + // we start with an empty list of splitters, it will be filled in out of recursion + attribute = new BoundaryAttribute<S>(plusOutside, plusInside, new NodesSet<S>()); + } + + transformedNode = new BSPTree<S>(node.getCut().copySelf(), + recurseComplement(node.getPlus(), map), + recurseComplement(node.getMinus(), map), + attribute); } - return new BSPTree<S>(node.getCut().copySelf(), - recurseComplement(node.getPlus()), - recurseComplement(node.getMinus()), - attribute); + map.put(node, transformedNode); + return transformedNode; }
