Repository: commons-math Updated Branches: refs/heads/master 8aec465b4 -> 046e3a2f5
Fixed a problem with vanishing sub-hyperplanes during BSP tree merging. Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/046e3a2f Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/046e3a2f Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/046e3a2f Branch: refs/heads/master Commit: 046e3a2f58decdc3eb9f69e14fc0f5c3a9e6b4c3 Parents: 8aec465 Author: Luc Maisonobe <l...@apache.org> Authored: Sun Nov 23 21:32:06 2014 +0100 Committer: Luc Maisonobe <l...@apache.org> Committed: Sun Nov 23 21:46:22 2014 +0100 ---------------------------------------------------------------------- src/changes/changes.xml | 3 + .../geometry/euclidean/twod/PolygonsSet.java | 3 +- .../math3/geometry/partitioning/BSPTree.java | 109 ++++++++++++++++--- .../geometry/partitioning/RegionFactory.java | 47 ++++++-- .../euclidean/twod/PolygonsSetTest.java | 19 ++++ 5 files changed, 155 insertions(+), 26 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-math/blob/046e3a2f/src/changes/changes.xml ---------------------------------------------------------------------- diff --git a/src/changes/changes.xml b/src/changes/changes.xml index 5377621..c8f0afd 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -73,6 +73,9 @@ 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="fix" issue="MATH-1162" > + Fixed a problem with vanishing cut sub-hyperplanes during BSP tree merging. + </action> <action dev="erans" type="fix" issue="MATH-1167" due-to="Neil Ireson"> "o.a.c.m.stat.regression.OLSMultipleLinearRegression": Use threshold when performing "QRDecomposition". http://git-wip-us.apache.org/repos/asf/commons-math/blob/046e3a2f/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 99ab841..fe7c463 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 @@ -710,7 +710,8 @@ public class PolygonsSet extends AbstractRegion<Euclidean2D, Euclidean1D> { int i = 0; for (final List<ComparableSegment> loop : loops) { - if (loop.size() < 2) { + if (loop.size() < 2 || + (loop.size() == 2 && loop.get(0).getStart() == null && loop.get(1).getEnd() == null)) { // single infinite line final Line line = loop.get(0).getLine(); vertices[i++] = new Vector2D[] { http://git-wip-us.apache.org/repos/asf/commons-math/blob/046e3a2f/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java index 8f32783..b059904 100644 --- a/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/BSPTree.java @@ -465,8 +465,7 @@ public class BSPTree<S extends Space> { minus.merge(merged.minus, leafMerger, merged, false); merged.condense(); if (merged.cut != null) { - merged.cut = - merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane()); + merged.cut = merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane()); } return merged; @@ -526,6 +525,27 @@ public class BSPTree<S extends Space> { } + /** This interface handles the corner cases when an internal node cut sub-hyperplane vanishes. + * <p> + * Such cases happens for example when a cut sub-hyperplane is inserted into + * another tree (during a merge operation), and is split in several parts, + * some of which becomes smaller than the tolerance. The corresponding node + * as then no cut sub-hyperplane anymore, but does have children. This interface + * specifies how to handle this situation. + * setting + * </p> + * @since 3.4 + */ + public interface VanishingCutHandler<S extends Space> { + + /** Fix a node with both vanished cut and children. + * @param node node to fix + * @return fixed node + */ + BSPTree<S> fixNode(BSPTree<S> node); + + } + /** Split a BSP tree by an external sub-hyperplane. * <p>Split a tree in two halves, on each side of the * sub-hyperplane. The instance is not modified.</p> @@ -547,8 +567,7 @@ public class BSPTree<S extends Space> { public BSPTree<S> split(final SubHyperplane<S> sub) { if (cut == null) { - return new BSPTree<S>(sub, copySelf(), - new BSPTree<S>(attribute), null); + return new BSPTree<S>(sub, copySelf(), new BSPTree<S>(attribute), null); } final Hyperplane<S> cHyperplane = cut.getHyperplane(); @@ -612,6 +631,27 @@ public class BSPTree<S extends Space> { } +// /** Insert the instance into another tree. +// * <p>The instance itself is modified so its former parent should +// * not be used anymore.</p> +// * @param parentTree parent tree to connect to (may be null) +// * @param isPlusChild if true and if parentTree is not null, the +// * resulting tree should be the plus child of its parent, ignored if +// * parentTree is null +// * @see LeafMerger +// * @deprecated as of 3.4, replaced with {@link #insertInTree(BSPTree, boolean, VanishingCutHandler)} +// */ +// @Deprecated +// public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) { +// insertInTree(parentTree, isPlusChild, new VanishingCutHandler<S>() { +// /** {@inheritDoc} */ +// public BSPTree<S> fixNode(BSPTree<S> node) { +// // the cut should not be null +// throw new MathIllegalStateException(LocalizedFormats.NULL_NOT_ALLOWED); +// } +// }); +// } + /** Insert the instance into another tree. * <p>The instance itself is modified so its former parent should * not be used anymore.</p> @@ -619,9 +659,13 @@ public class BSPTree<S extends Space> { * @param isPlusChild if true and if parentTree is not null, the * resulting tree should be the plus child of its parent, ignored if * parentTree is null + * @param vanishingHandler handler to use for handling very rare corner + * cases of vanishing cut sub-hyperplanes in internal nodes during merging * @see LeafMerger + * @since 3.4 */ - public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) { + public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild, + final VanishingCutHandler<S> vanishingHandler) { // set up parent/child links parent = parentTree; @@ -646,12 +690,21 @@ public class BSPTree<S extends Space> { // on the wrong side of this parent hyperplane if (tree == tree.parent.plus) { cut = cut.split(hyperplane).getPlus(); - plus.chopOffMinus(hyperplane); - minus.chopOffMinus(hyperplane); + plus.chopOffMinus(hyperplane, vanishingHandler); + minus.chopOffMinus(hyperplane, vanishingHandler); } else { cut = cut.split(hyperplane).getMinus(); - plus.chopOffPlus(hyperplane); - minus.chopOffPlus(hyperplane); + plus.chopOffPlus(hyperplane, vanishingHandler); + minus.chopOffPlus(hyperplane, vanishingHandler); + } + + if (cut == null) { + // the cut sub-hyperplane has vanished + final BSPTree<S> fixed = vanishingHandler.fixNode(this); + cut = fixed.cut; + plus = fixed.plus; + minus = fixed.minus; + attribute = fixed.attribute; } } @@ -710,12 +763,25 @@ public class BSPTree<S extends Space> { * the minus side of the chopping hyperplane are discarded, only the * parts on the plus side remain.</p> * @param hyperplane chopping hyperplane + * @param vanishingHandler handler to use for handling very rare corner + * cases of vanishing cut sub-hyperplanes in internal nodes during merging */ - private void chopOffMinus(final Hyperplane<S> hyperplane) { + private void chopOffMinus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) { if (cut != null) { + cut = cut.split(hyperplane).getPlus(); - plus.chopOffMinus(hyperplane); - minus.chopOffMinus(hyperplane); + plus.chopOffMinus(hyperplane, vanishingHandler); + minus.chopOffMinus(hyperplane, vanishingHandler); + + if (cut == null) { + // the cut sub-hyperplane has vanished + final BSPTree<S> fixed = vanishingHandler.fixNode(this); + cut = fixed.cut; + plus = fixed.plus; + minus = fixed.minus; + attribute = fixed.attribute; + } + } } @@ -724,12 +790,25 @@ public class BSPTree<S extends Space> { * the plus side of the chopping hyperplane are discarded, only the * parts on the minus side remain.</p> * @param hyperplane chopping hyperplane + * @param vanishingHandler handler to use for handling very rare corner + * cases of vanishing cut sub-hyperplanes in internal nodes during merging */ - private void chopOffPlus(final Hyperplane<S> hyperplane) { + private void chopOffPlus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) { if (cut != null) { + cut = cut.split(hyperplane).getMinus(); - plus.chopOffPlus(hyperplane); - minus.chopOffPlus(hyperplane); + plus.chopOffPlus(hyperplane, vanishingHandler); + minus.chopOffPlus(hyperplane, vanishingHandler); + + if (cut == null) { + // the cut sub-hyperplane has vanished + final BSPTree<S> fixed = vanishingHandler.fixNode(this); + cut = fixed.cut; + plus = fixed.plus; + minus = fixed.minus; + attribute = fixed.attribute; + } + } } http://git-wip-us.apache.org/repos/asf/commons-math/blob/046e3a2f/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 1dd9dea..ae9c3dd 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 @@ -17,6 +17,7 @@ package org.apache.commons.math3.geometry.partitioning; import org.apache.commons.math3.geometry.Space; +import org.apache.commons.math3.geometry.partitioning.BSPTree.VanishingCutHandler; /** This class is a factory for {@link Region}. @@ -162,16 +163,16 @@ public class RegionFactory<S extends Space> { final boolean isPlusChild, final boolean leafFromInstance) { if ((Boolean) leaf.getAttribute()) { // the leaf node represents an inside cell - leaf.insertInTree(parentTree, isPlusChild); + leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); return leaf; } // the leaf node represents an outside cell - tree.insertInTree(parentTree, isPlusChild); + tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false)); return tree; } } - /** BSP tree leaf merger computing union of two regions. */ + /** BSP tree leaf merger computing intersection of two regions. */ private class IntersectionMerger implements BSPTree.LeafMerger<S> { /** {@inheritDoc} */ public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, @@ -179,16 +180,16 @@ public class RegionFactory<S extends Space> { final boolean isPlusChild, final boolean leafFromInstance) { if ((Boolean) leaf.getAttribute()) { // the leaf node represents an inside cell - tree.insertInTree(parentTree, isPlusChild); + tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); return tree; } // the leaf node represents an outside cell - leaf.insertInTree(parentTree, isPlusChild); + leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false)); return leaf; } } - /** BSP tree leaf merger computing union of two regions. */ + /** BSP tree leaf merger computing symmetric difference (exclusive or) of two regions. */ private class XorMerger implements BSPTree.LeafMerger<S> { /** {@inheritDoc} */ public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, @@ -199,12 +200,12 @@ public class RegionFactory<S extends Space> { // the leaf node represents an inside cell t = recurseComplement(t); } - t.insertInTree(parentTree, isPlusChild); + t.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); return t; } } - /** BSP tree leaf merger computing union of two regions. */ + /** BSP tree leaf merger computing difference of two regions. */ private class DifferenceMerger implements BSPTree.LeafMerger<S> { /** {@inheritDoc} */ public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, @@ -214,13 +215,13 @@ 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); + argTree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); return argTree; } // the leaf node represents an outside cell final BSPTree<S> instanceTree = leafFromInstance ? leaf : tree; - instanceTree.insertInTree(parentTree, isPlusChild); + instanceTree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false)); return instanceTree; } } @@ -244,4 +245,30 @@ public class RegionFactory<S extends Space> { } + /** Handler replacing nodes with vanishing cuts with leaf nodes. */ + private class VanishingToLeaf implements VanishingCutHandler<S> { + + /** Inside/outside indocator to use for ambiguous nodes. */ + private final boolean inside; + + /** Simple constructor. + * @param inside inside/outside indocator to use for ambiguous nodes + */ + public VanishingToLeaf(final boolean inside) { + this.inside = inside; + } + + /** {@inheritDoc} */ + public BSPTree<S> fixNode(final BSPTree<S> node) { + if (node.getPlus().getAttribute().equals(node.getMinus().getAttribute())) { + // no ambiguity + return new BSPTree<S>(node.getPlus().getAttribute()); + } else { + // ambiguous node + return new BSPTree<S>(inside); + } + } + + } + } http://git-wip-us.apache.org/repos/asf/commons-math/blob/046e3a2f/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java b/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java index 94b51ba..348ace8 100644 --- a/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java +++ b/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java @@ -1088,6 +1088,25 @@ public class PolygonsSetTest { } } + @Test + public void testIssue1162() { + PolygonsSet p = new PolygonsSet(1.0e-10, + new Vector2D(4.267199999996532, -11.928637756014894), + new Vector2D(4.267200000026445, -14.12360595809307), + new Vector2D(9.144000000273694, -14.12360595809307), + new Vector2D(9.144000000233383, -11.928637756020067)); + + PolygonsSet w = new PolygonsSet(1.0e-10, + new Vector2D(2.56735636510452512E-9, -11.933116461089332), + new Vector2D(2.56735636510452512E-9, -12.393225665247766), + new Vector2D(2.56735636510452512E-9, -27.785625665247778), + new Vector2D(4.267200000030211, -27.785625665247778), + new Vector2D(4.267200000030211, -11.933116461089332)); + + Assert.assertFalse(p.contains(w)); + + } + private PolygonsSet buildSet(Vector2D[][] vertices) { ArrayList<SubHyperplane<Euclidean2D>> edges = new ArrayList<SubHyperplane<Euclidean2D>>(); for (int i = 0; i < vertices.length; ++i) {
