Reorganized code, avoiding too many internal classes. Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/26ee4819 Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/26ee4819 Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/26ee4819
Branch: refs/heads/master Commit: 26ee48193928f525fe0885cba6b28fdc8eff6af9 Parents: 5f667c0 Author: Luc Maisonobe <l...@apache.org> Authored: Sun Nov 30 13:37:43 2014 +0100 Committer: Luc Maisonobe <l...@apache.org> Committed: Tue Dec 2 15:24:31 2014 +0100 ---------------------------------------------------------------------- .../geometry/euclidean/twod/PolygonsSet.java | 2 +- .../geometry/partitioning/AbstractRegion.java | 266 +------------------ .../geometry/partitioning/BoundaryBuilder.java | 84 ++++++ .../geometry/partitioning/Characterization.java | 147 ++++++++++ .../geometry/partitioning/InsideFinder.java | 150 +++++++++++ .../geometry/partitioning/RegionFactory.java | 47 +++- 6 files changed, 430 insertions(+), 266 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-math/blob/26ee4819/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java index fe7c463..532d6a0 100644 --- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java +++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java @@ -784,7 +784,7 @@ public class PolygonsSet extends AbstractRegion<Euclidean2D, Euclidean1D> { // is this an open or a closed loop ? final boolean open = segment.getStart() == null; - while ((end != null) && (open || (globalStart.distance((Point<Euclidean2D>) end) > 1.0e-10))) { + while ((end != null) && (open || (globalStart.distance((Point<Euclidean2D>) end) > getTolerance()))) { // search the sub-hyperplane starting where the previous one ended AVLTree<ComparableSegment>.Node selectedNode = null; http://git-wip-us.apache.org/repos/asf/commons-math/blob/26ee4819/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 abddb78..3fca476 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 @@ -16,18 +16,15 @@ */ package org.apache.commons.math3.geometry.partitioning; -import java.lang.reflect.Array; import java.util.ArrayList; import java.util.Collection; import java.util.Comparator; import java.util.Iterator; import java.util.TreeSet; -import org.apache.commons.math3.exception.MathInternalError; -import org.apache.commons.math3.geometry.Space; import org.apache.commons.math3.geometry.Point; +import org.apache.commons.math3.geometry.Space; import org.apache.commons.math3.geometry.Vector; -import org.apache.commons.math3.geometry.partitioning.Region.Location; /** Abstract class for all regions, independently of geometry type or dimension. @@ -358,122 +355,6 @@ public abstract class AbstractRegion<S extends Space, T extends Space> implement return tree; } - /** Visitor building boundary shell tree. - * <p> - * The boundary shell is represented as {@link BoundaryAttribute boundary attributes} - * at each internal node. - * </p> - */ - private static class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> { - - /** {@inheritDoc} */ - public Order visitOrder(BSPTree<S> node) { - return Order.PLUS_MINUS_SUB; - } - - /** {@inheritDoc} */ - public void visitInternalNode(BSPTree<S> node) { - - SubHyperplane<S> plusOutside = null; - SubHyperplane<S> plusInside = null; - - // characterize the cut sub-hyperplane, - // first with respect to the plus sub-tree - @SuppressWarnings("unchecked") - final SubHyperplane<S>[] plusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2); - characterize(node.getPlus(), node.getCut().copySelf(), plusChar); - - if (plusChar[0] != null && !plusChar[0].isEmpty()) { - // plusChar[0] 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 - @SuppressWarnings("unchecked") - final SubHyperplane<S>[] minusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2); - characterize(node.getMinus(), plusChar[0], minusChar); - if (minusChar[1] != null && !minusChar[1].isEmpty()) { - // this part belongs to the boundary, - // it has the outside on its plus side and the inside on its minus side - plusOutside = minusChar[1]; - } - } - - if (plusChar[1] != null && !plusChar[1].isEmpty()) { - // plusChar[1] 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 - @SuppressWarnings("unchecked") - final SubHyperplane<S>[] minusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2); - characterize(node.getMinus(), plusChar[1], minusChar); - if (minusChar[0] != null && !minusChar[0].isEmpty()) { - // this part belongs to the boundary, - // it has the inside on its plus side and the outside on its minus side - plusInside = minusChar[0]; - } - } - - // set the boundary attribute at non-leaf nodes - node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside)); - - } - - /** {@inheritDoc} */ - public void visitLeafNode(BSPTree<S> node) { - } - - /** 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 on 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 SubHyperplane<S>[] characterization) { - if (node.getCut() == null) { - // we have reached a leaf node - final boolean inside = (Boolean) node.getAttribute(); - if (inside) { - if (characterization[1] == null) { - characterization[1] = sub; - } else { - characterization[1] = characterization[1].reunite(sub); - } - } else { - if (characterization[0] == null) { - characterization[0] = sub; - } else { - characterization[0] = characterization[0].reunite(sub); - } - } - } 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 MathInternalError(); - } - } - } - - } - /** {@inheritDoc} */ public double getBoundarySize() { final BoundarySizeVisitor<S> visitor = new BoundarySizeVisitor<S>(); @@ -525,146 +406,11 @@ public abstract class AbstractRegion<S extends Space, T extends Space> implement /** {@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; - } - + final InsideFinder<S> finder = new InsideFinder<S>(this); + finder.recurseSides(tree, hyperplane.wholeHyperplane()); + return finder.plusFound() ? + (finder.minusFound() ? Side.BOTH : Side.PLUS) : + (finder.minusFound() ? Side.MINUS : Side.HYPER); } /** {@inheritDoc} */ http://git-wip-us.apache.org/repos/asf/commons-math/blob/26ee4819/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 new file mode 100644 index 0000000..80038f1 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/BoundaryBuilder.java @@ -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.math3.geometry.partitioning; + +import org.apache.commons.math3.geometry.Space; + +/** Visitor building boundary shell tree. + * <p> + * The boundary shell is represented as {@link BoundaryAttribute boundary attributes} + * at each internal node. + * </p> + * @param <S> Type of the space. + * @since 3.4 + */ +class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> { + + /** Simple constructor. + */ + public BoundaryBuilder() { + } + + /** {@inheritDoc} */ + public Order visitOrder(BSPTree<S> node) { + return Order.PLUS_MINUS_SUB; + } + + /** {@inheritDoc} */ + public void visitInternalNode(BSPTree<S> node) { + + 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>(node.getPlus(), node.getCut().copySelf()); + + if (plusChar.touchOutside()) { + // plusChar.outsideTouching() 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>(node.getMinus(), plusChar.outsideTouching()); + if (minusChar.touchInside()) { + // this part belongs to the boundary, + // it has the outside on its plus side and the inside on its minus side + plusOutside = minusChar.insideTouching(); + } + } + + if (plusChar.touchInside()) { + // plusChar.insideTouching() 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>(node.getMinus(), plusChar.insideTouching()); + if (minusChar.touchOutside()) { + // this part belongs to the boundary, + // it has the inside on its plus side and the outside on its minus side + plusInside = minusChar.outsideTouching(); + } + } + + // set the boundary attribute at non-leaf nodes + node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside)); + + } + + /** {@inheritDoc} */ + public void visitLeafNode(BSPTree<S> node) { + } + +} http://git-wip-us.apache.org/repos/asf/commons-math/blob/26ee4819/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 new file mode 100644 index 0000000..a67f873 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java @@ -0,0 +1,147 @@ +/* + * 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 org.apache.commons.math3.exception.MathInternalError; +import org.apache.commons.math3.geometry.Space; + +/** Cut sub-hyperplanes characterization with respect to inside/outside cells. + * @see BoundaryBuilder + * @param <S> Type of the space. + * @since 3.4 + */ +class Characterization<S extends Space> { + + /** Part of the cut sub-hyperplane that touch outside cells. */ + private SubHyperplane<S> outsideTouching; + + /** Part of the cut sub-hyperplane that touch inside cells. */ + private SubHyperplane<S> insideTouching; + + /** Simple constructor. + * <p>Characterization consists in splitting the specified + * sub-hyperplane into several parts lying in inside and outside + * cells of the tree. The principle is to compute characterization + * twice for each cut sub-hyperplane in the tree, once on 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 + */ + public Characterization(final BSPTree<S> node, final SubHyperplane<S> sub) { + outsideTouching = null; + insideTouching = null; + characterize(node, sub); + } + + /** 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 on 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 + */ + private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub) { + if (node.getCut() == null) { + // we have reached a leaf node + final boolean inside = (Boolean) node.getAttribute(); + if (inside) { + addInsideTouching(sub); + } else { + addOutsideTouching(sub); + } + } else { + final Hyperplane<S> hyperplane = node.getCut().getHyperplane(); + switch (sub.side(hyperplane)) { + case PLUS: + characterize(node.getPlus(), sub); + break; + case MINUS: + characterize(node.getMinus(), sub); + break; + case BOTH: + final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane); + characterize(node.getPlus(), split.getPlus()); + characterize(node.getMinus(), split.getMinus()); + break; + default: + // this should not happen + throw new MathInternalError(); + } + } + } + + /** 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 + */ + private void addOutsideTouching(final SubHyperplane<S> sub) { + if (outsideTouching == null) { + outsideTouching = sub; + } else { + outsideTouching = outsideTouching.reunite(sub); + } + } + + /** 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 + */ + private void addInsideTouching(final SubHyperplane<S> sub) { + if (insideTouching == null) { + insideTouching = sub; + } else { + insideTouching = insideTouching.reunite(sub); + } + } + + /** Check if the cut sub-hyperplane touches outside cells. + * @return true if the cut sub-hyperplane touches outside cells + */ + public boolean touchOutside() { + return outsideTouching != null && !outsideTouching.isEmpty(); + } + + /** Get all the parts of the cut sub-hyperplane known to touch outside cells. + * @return parts of the cut sub-hyperplane known to touch outside cells + * (may be null or empty) + */ + public SubHyperplane<S> outsideTouching() { + return outsideTouching; + } + + /** Check if the cut sub-hyperplane touches inside cells. + * @return true if the cut sub-hyperplane touches inside cells + */ + public boolean touchInside() { + return insideTouching != null && !insideTouching.isEmpty(); + } + + /** Get all the parts of the cut sub-hyperplane known to touch inside cells. + * @return parts of the cut sub-hyperplane known to touch inside cells + * (may be null or empty) + */ + public SubHyperplane<S> insideTouching() { + return insideTouching; + } + +} http://git-wip-us.apache.org/repos/asf/commons-math/blob/26ee4819/src/main/java/org/apache/commons/math3/geometry/partitioning/InsideFinder.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/InsideFinder.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/InsideFinder.java new file mode 100644 index 0000000..2b0b405 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/InsideFinder.java @@ -0,0 +1,150 @@ +/* + * 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 org.apache.commons.math3.geometry.Space; + +/** Utility class checking if inside nodes can be found + * on the plus and minus sides of an hyperplane. + * @param <S> Type of the space. + * @since 3.4 + */ +class InsideFinder<S extends Space> { + + /** Region on which to operate. */ + private final Region<S> region; + + /** 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. + * @param region region on which to operate + */ + public InsideFinder(final Region<S> region) { + this.region = region; + plusFound = false; + minusFound = false; + } + + /** 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 + */ + public void recurseSides(final BSPTree<S> node, final SubHyperplane<S> sub) { + + if (node.getCut() == null) { + if ((Boolean) node.getAttribute()) { + // this is an inside cell expanding across the hyperplane + plusFound = true; + minusFound = true; + } + 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 (!region.isEmpty(node.getMinus())) { + plusFound = true; + } + } else { + if (!region.isEmpty(node.getMinus())) { + minusFound = true; + } + } + if (!(plusFound && minusFound)) { + recurseSides(node.getPlus(), sub); + } + break; + case MINUS : + // the sub-hyperplane is entirely in the minus sub-tree + if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) { + if (!region.isEmpty(node.getPlus())) { + plusFound = true; + } + } else { + if (!region.isEmpty(node.getPlus())) { + minusFound = true; + } + } + if (!(plusFound && minusFound)) { + recurseSides(node.getMinus(), sub); + } + 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()); + + // if needed, explore the minus sub-tree + if (!(plusFound && minusFound)) { + recurseSides(node.getMinus(), split.getMinus()); + } + 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())) { + plusFound = true; + } + if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) { + minusFound = true; + } + } else { + if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) { + minusFound = true; + } + if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) { + 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; + } + + /** 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; + } + +} http://git-wip-us.apache.org/repos/asf/commons-math/blob/26ee4819/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 ae9c3dd..47b28bd 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,8 +16,12 @@ */ package org.apache.commons.math3.geometry.partitioning; +import org.apache.commons.math3.geometry.Point; import org.apache.commons.math3.geometry.Space; +import org.apache.commons.math3.geometry.euclidean.twod.PolygonsSet; +import org.apache.commons.math3.geometry.euclidean.twod.Vector2D; import org.apache.commons.math3.geometry.partitioning.BSPTree.VanishingCutHandler; +import org.apache.commons.math3.geometry.partitioning.Region.Location; /** This class is a factory for {@link Region}. @@ -115,7 +119,7 @@ public class RegionFactory<S extends Space> { */ public Region<S> difference(final Region<S> region1, final Region<S> region2) { final BSPTree<S> tree = - region1.getTree(false).merge(region2.getTree(false), new DifferenceMerger()); + region1.getTree(false).merge(region2.getTree(false), new DifferenceMerger(region1, region2)); tree.visit(nodeCleaner); return region1.buildNew(tree); } @@ -206,7 +210,23 @@ public class RegionFactory<S extends Space> { } /** BSP tree leaf merger computing difference of two regions. */ - private class DifferenceMerger implements BSPTree.LeafMerger<S> { + private class DifferenceMerger implements BSPTree.LeafMerger<S>, VanishingCutHandler<S> { + + /** Region to subtract from. */ + private final Region<S> region1; + + /** Region to subtract. */ + private final Region<S> region2; + + /** Simple constructor. + * @param region1 region to subtract from + * @param region2 region to subtract + */ + public DifferenceMerger(final Region<S> region1, final Region<S> region2) { + this.region1 = region1.copySelf(); + this.region2 = region2.copySelf(); + } + /** {@inheritDoc} */ public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, final BSPTree<S> parentTree, final boolean isPlusChild, @@ -215,15 +235,32 @@ public class RegionFactory<S extends Space> { // the leaf node represents an inside cell final BSPTree<S> argTree = recurseComplement(leafFromInstance ? tree : leaf); - argTree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); + argTree.insertInTree(parentTree, isPlusChild, this); return argTree; } // the leaf node represents an outside cell final BSPTree<S> instanceTree = leafFromInstance ? leaf : tree; - instanceTree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false)); + instanceTree.insertInTree(parentTree, isPlusChild, this); return instanceTree; } + + /** {@inheritDoc} */ + public BSPTree<S> fixNode(final BSPTree<S> node) { + // get a representative point in the degenerate cell + final BSPTree<S> cell = node.pruneAroundConvexCell(Boolean.TRUE, Boolean.FALSE, null); + final Region<S> r = region1.buildNew(cell); + for (Vector2D[] loop : ((PolygonsSet) r).getVertices()) { + System.out.format(java.util.Locale.US, "%n"); + for (Vector2D v : loop) { + System.out.format(java.util.Locale.US, "%14.10f %14.10f%n", v.getX(), v.getY()); + } + } + final Point<S> p = r.getBarycenter(); + return new BSPTree<S>(region1.checkPoint(p) == Location.INSIDE && + region2.checkPoint(p) == Location.OUTSIDE); + } + } /** Visitor removing internal nodes attributes. */ @@ -252,7 +289,7 @@ public class RegionFactory<S extends Space> { private final boolean inside; /** Simple constructor. - * @param inside inside/outside indocator to use for ambiguous nodes + * @param inside inside/outside indicator to use for ambiguous nodes */ public VanishingToLeaf(final boolean inside) { this.inside = inside;
