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 2014/12/02 22:20:28 UTC
[2/8] [math] Reorganized code, avoiding too many internal classes.
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 <lu...@apache.org>
Authored: Sun Nov 30 13:37:43 2014 +0100
Committer: Luc Maisonobe <lu...@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;