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 2015/04/09 22:30:36 UTC
[1/3] [math] Added dump/parse utilities for BSP trees.
Repository: commons-math
Updated Branches:
refs/heads/MATH_3_X b4d2c75d3 -> 5c07e5487
Added dump/parse utilities for BSP trees.
These utilities are for test and debug purposes only.
Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/9744a812
Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/9744a812
Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/9744a812
Branch: refs/heads/MATH_3_X
Commit: 9744a812bdca34cdfc3663e4fbcd40df73def460
Parents: b4d2c75
Author: Luc Maisonobe <lu...@apache.org>
Authored: Thu Apr 9 22:13:45 2015 +0200
Committer: Luc Maisonobe <lu...@apache.org>
Committed: Thu Apr 9 22:19:06 2015 +0200
----------------------------------------------------------------------
.../euclidean/threed/PolyhedronsSetTest.java | 57 ++++
.../geometry/partitioning/RegionDumper.java | 244 +++++++++++++++
.../geometry/partitioning/RegionParser.java | 303 +++++++++++++++++++
3 files changed, 604 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-math/blob/9744a812/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java b/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java
index b23fc5d..ce7c49d 100644
--- a/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java
+++ b/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java
@@ -16,7 +16,11 @@
*/
package org.apache.commons.math3.geometry.euclidean.threed;
+import java.io.IOException;
+import java.text.ParseException;
import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Set;
import org.apache.commons.math3.exception.MathArithmeticException;
import org.apache.commons.math3.exception.MathIllegalArgumentException;
@@ -29,7 +33,9 @@ import org.apache.commons.math3.geometry.partitioning.BSPTree;
import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor;
import org.apache.commons.math3.geometry.partitioning.BoundaryAttribute;
import org.apache.commons.math3.geometry.partitioning.Region;
+import org.apache.commons.math3.geometry.partitioning.RegionDumper;
import org.apache.commons.math3.geometry.partitioning.RegionFactory;
+import org.apache.commons.math3.geometry.partitioning.RegionParser;
import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
import org.apache.commons.math3.util.FastMath;
import org.junit.Assert;
@@ -307,6 +313,57 @@ public class PolyhedronsSetTest {
}
}
+ @Test
+ public void testDumpParse() throws IOException, ParseException {
+ double tol=1e-8;
+
+ Vector3D[] verts=new Vector3D[8];
+ double xmin=-1,xmax=1;
+ double ymin=-1,ymax=1;
+ double zmin=-1,zmax=1;
+ verts[0]=new Vector3D(xmin,ymin,zmin);
+ verts[1]=new Vector3D(xmax,ymin,zmin);
+ verts[2]=new Vector3D(xmax,ymax,zmin);
+ verts[3]=new Vector3D(xmin,ymax,zmin);
+ verts[4]=new Vector3D(xmin,ymin,zmax);
+ verts[5]=new Vector3D(xmax,ymin,zmax);
+ verts[6]=new Vector3D(xmax,ymax,zmax);
+ verts[7]=new Vector3D(xmin,ymax,zmax);
+ //
+ int[][] faces=new int[12][];
+ faces[0]=new int[]{3,1,0}; // bottom (-z)
+ faces[1]=new int[]{1,3,2}; // bottom (-z)
+ faces[2]=new int[]{5,7,4}; // top (+z)
+ faces[3]=new int[]{7,5,6}; // top (+z)
+ faces[4]=new int[]{2,5,1}; // right (+x)
+ faces[5]=new int[]{5,2,6}; // right (+x)
+ faces[6]=new int[]{4,3,0}; // left (-x)
+ faces[7]=new int[]{3,4,7}; // left (-x)
+ faces[8]=new int[]{4,1,5}; // front (-y)
+ faces[9]=new int[]{1,4,0}; // front (-y)
+ faces[10]=new int[]{3,6,2}; // back (+y)
+ faces[11]=new int[]{6,3,7}; // back (+y)
+ //
+ Set<SubHyperplane<Euclidean3D>> pset=new HashSet<>();
+ for (int f=0; f<faces.length; f++) {
+ int[] vidx=faces[f];
+ Plane p=new Plane(verts[vidx[0]],verts[vidx[1]],verts[vidx[2]],tol);
+ Vector2D p0=p.toSubSpace(verts[vidx[0]]);
+ Vector2D p1=p.toSubSpace(verts[vidx[1]]);
+ Vector2D p2=p.toSubSpace(verts[vidx[2]]);
+ PolygonsSet lset=new PolygonsSet(tol,p0,p1,p2);
+ pset.add(new SubPlane(p,lset));
+ }
+ PolyhedronsSet polyset=new PolyhedronsSet(pset,tol);
+ Assert.assertEquals(8.0, polyset.getSize(), 1.0e-10);
+ Assert.assertEquals(24.0, polyset.getBoundarySize(), 1.0e-10);
+ String dump = RegionDumper.dump(polyset);
+ PolyhedronsSet parsed = RegionParser.parsePolyhedronsSet(dump);
+ Assert.assertEquals(8.0, parsed.getSize(), 1.0e-10);
+ Assert.assertEquals(24.0, parsed.getBoundarySize(), 1.0e-10);
+ Assert.assertTrue(new RegionFactory<Euclidean3D>().difference(polyset, parsed).isEmpty());
+ }
+
private void checkPoints(Region.Location expected, PolyhedronsSet tree, Vector3D[] points) {
for (int i = 0; i < points.length; ++i) {
Assert.assertEquals(expected, tree.checkPoint(points[i]));
http://git-wip-us.apache.org/repos/asf/commons-math/blob/9744a812/src/test/java/org/apache/commons/math3/geometry/partitioning/RegionDumper.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math3/geometry/partitioning/RegionDumper.java b/src/test/java/org/apache/commons/math3/geometry/partitioning/RegionDumper.java
new file mode 100644
index 0000000..33be9d7
--- /dev/null
+++ b/src/test/java/org/apache/commons/math3/geometry/partitioning/RegionDumper.java
@@ -0,0 +1,244 @@
+/*
+ * 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.Formatter;
+import java.util.Locale;
+
+import org.apache.commons.math3.geometry.Space;
+import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
+import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet;
+import org.apache.commons.math3.geometry.euclidean.oned.OrientedPoint;
+import org.apache.commons.math3.geometry.euclidean.oned.Vector1D;
+import org.apache.commons.math3.geometry.euclidean.threed.Euclidean3D;
+import org.apache.commons.math3.geometry.euclidean.threed.Plane;
+import org.apache.commons.math3.geometry.euclidean.threed.PolyhedronsSet;
+import org.apache.commons.math3.geometry.euclidean.threed.Vector3D;
+import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
+import org.apache.commons.math3.geometry.euclidean.twod.Line;
+import org.apache.commons.math3.geometry.euclidean.twod.PolygonsSet;
+import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
+import org.apache.commons.math3.geometry.spherical.oned.ArcsSet;
+import org.apache.commons.math3.geometry.spherical.oned.LimitAngle;
+import org.apache.commons.math3.geometry.spherical.oned.Sphere1D;
+import org.apache.commons.math3.geometry.spherical.twod.Circle;
+import org.apache.commons.math3.geometry.spherical.twod.Sphere2D;
+import org.apache.commons.math3.geometry.spherical.twod.SphericalPolygonsSet;
+
+/** Class dumping a string representation of an {@link AbstractRegion}.
+ * <p>
+ * This class is intended for tests and debug purposes only.
+ * </p>
+ * @see RegionParser
+ * @since 3.5
+ */
+public class RegionDumper {
+
+ /** Private constructor for a utility class
+ */
+ private RegionDumper() {
+ }
+
+ /** Get a string representation of an {@link ArcsSet}.
+ * @param arcsSet region to dump
+ * @return string representation of the region
+ */
+ public static String dump(final ArcsSet arcsSet) {
+ final TreeDumper<Sphere1D> visitor = new TreeDumper<Sphere1D>("ArcsSet", arcsSet.getTolerance()) {
+
+ /** {@inheritDoc} */
+ @Override
+ protected void formatHyperplane(final Hyperplane<Sphere1D> hyperplane) {
+ final LimitAngle h = (LimitAngle) hyperplane;
+ getFormatter().format("%22.15e %b %22.15e",
+ h.getLocation().getAlpha(), h.isDirect(), h.getTolerance());
+ }
+
+ };
+ arcsSet.getTree(false).visit(visitor);
+ return visitor.getDump();
+ }
+
+ /** Get a string representation of a {@link SphericalPolygonsSet}.
+ * @param sphericalPolygonsSet region to dump
+ * @return string representation of the region
+ */
+ public static String dump(final SphericalPolygonsSet sphericalPolygonsSet) {
+ final TreeDumper<Sphere2D> visitor = new TreeDumper<Sphere2D>("SphericalPolygonsSet", sphericalPolygonsSet.getTolerance()) {
+
+ /** {@inheritDoc} */
+ @Override
+ protected void formatHyperplane(final Hyperplane<Sphere2D> hyperplane) {
+ final Circle h = (Circle) hyperplane;
+ getFormatter().format("%22.15e %22.15e %22.15e %22.15e",
+ h.getPole().getX(), h.getPole().getY(), h.getPole().getZ(),
+ h.getTolerance());
+ }
+
+ };
+ sphericalPolygonsSet.getTree(false).visit(visitor);
+ return visitor.getDump();
+ }
+
+ /** Get a string representation of an {@link IntervalsSet}.
+ * @param intervalsSet region to dump
+ * @return string representation of the region
+ */
+ public static String dump(final IntervalsSet intervalsSet) {
+ final TreeDumper<Euclidean1D> visitor = new TreeDumper<Euclidean1D>("IntervalsSet", intervalsSet.getTolerance()) {
+
+ /** {@inheritDoc} */
+ @Override
+ protected void formatHyperplane(final Hyperplane<Euclidean1D> hyperplane) {
+ final OrientedPoint h = (OrientedPoint) hyperplane;
+ getFormatter().format("%22.15e %b %22.15e",
+ h.getLocation().getX(), h.isDirect(), h.getTolerance());
+ }
+
+ };
+ intervalsSet.getTree(false).visit(visitor);
+ return visitor.getDump();
+ }
+
+ /** Get a string representation of a {@link PolygonsSet}.
+ * @param polygonsSet region to dump
+ * @return string representation of the region
+ */
+ public static String dump(final PolygonsSet polygonsSet) {
+ final TreeDumper<Euclidean2D> visitor = new TreeDumper<Euclidean2D>("PolygonsSet", polygonsSet.getTolerance()) {
+
+ /** {@inheritDoc} */
+ @Override
+ protected void formatHyperplane(final Hyperplane<Euclidean2D> hyperplane) {
+ final Line h = (Line) hyperplane;
+ final Vector2D p = h.toSpace(Vector1D.ZERO);
+ getFormatter().format("%22.15e %22.15e %22.15e %22.15e",
+ p.getX(), p.getY(), h.getAngle(), h.getTolerance());
+ }
+
+ };
+ polygonsSet.getTree(false).visit(visitor);
+ return visitor.getDump();
+ }
+
+ /** Get a string representation of a {@link PolyhedronsSet}.
+ * @param polyhedronsSet region to dump
+ * @return string representation of the region
+ */
+ public static String dump(final PolyhedronsSet polyhedronsSet) {
+ final TreeDumper<Euclidean3D> visitor = new TreeDumper<Euclidean3D>("PolyhedronsSet", polyhedronsSet.getTolerance()) {
+
+ /** {@inheritDoc} */
+ @Override
+ protected void formatHyperplane(final Hyperplane<Euclidean3D> hyperplane) {
+ final Plane h = (Plane) hyperplane;
+ final Vector3D p = h.toSpace(Vector2D.ZERO);
+ getFormatter().format("%22.15e %22.15e %22.15e %22.15e %22.15e %22.15e %22.15e",
+ p.getX(), p.getY(), p.getZ(),
+ h.getNormal().getX(), h.getNormal().getY(), h.getNormal().getZ(),
+ h.getTolerance());
+ }
+
+ };
+ polyhedronsSet.getTree(false).visit(visitor);
+ return visitor.getDump();
+ }
+
+ /** Dumping visitor.
+ * @param <S> Type of the space.
+ */
+ private abstract static class TreeDumper<S extends Space> implements BSPTreeVisitor<S> {
+
+ /** Builder for the string representation of the dumped tree. */
+ private final StringBuilder dump;
+
+ /** Formatter for strings. */
+ private final Formatter formatter;
+
+ /** Current indentation prefix. */
+ private String prefix;
+
+ /** Simple constructor.
+ * @param type type of the region to dump
+ * @param tolerance tolerance of the region
+ */
+ public TreeDumper(final String type, final double tolerance) {
+ this.dump = new StringBuilder();
+ this.formatter = new Formatter(dump, Locale.US);
+ this.prefix = "";
+ formatter.format("%s%n", type);
+ formatter.format("tolerance %22.15e%n", tolerance);
+ }
+
+ /** Get the string representation of the tree.
+ * @return string representation of the tree.
+ */
+ public String getDump() {
+ return dump.toString();
+ }
+
+ /** Get the formatter to use.
+ * @return formatter to use
+ */
+ protected Formatter getFormatter() {
+ return formatter;
+ }
+
+ /** Format a string representation of the hyperplane underlying a cut sub-hyperplane.
+ * @param hyperplane hyperplane to format
+ */
+ protected abstract void formatHyperplane(Hyperplane<S> hyperplane);
+
+ /** {@inheritDoc} */
+ @Override
+ public Order visitOrder(final BSPTree<S> node) {
+ return Order.SUB_MINUS_PLUS;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public void visitInternalNode(final BSPTree<S> node) {
+ formatter.format("%s %s internal ", prefix, type(node));
+ formatHyperplane(node.getCut().getHyperplane());
+ formatter.format("%n");
+ prefix = prefix + " ";
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public void visitLeafNode(final BSPTree<S> node) {
+ formatter.format("%s %s leaf %s%n",
+ prefix, type(node), node.getAttribute());
+ for (BSPTree<S> n = node;
+ n.getParent() != null && n == n.getParent().getPlus();
+ n = n.getParent()) {
+ prefix = prefix.substring(0, prefix.length() - 2);
+ }
+ }
+
+ /** Get the type of the node.
+ * @param node node to check
+ * @return "plus " or "minus" depending on the node being the plus or minus
+ * child of its parent ("plus " is arbitrarily returned for the root node)
+ */
+ private String type(final BSPTree<S> node) {
+ return (node.getParent() != null && node == node.getParent().getMinus()) ? "minus" : "plus ";
+ }
+
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/commons-math/blob/9744a812/src/test/java/org/apache/commons/math3/geometry/partitioning/RegionParser.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math3/geometry/partitioning/RegionParser.java b/src/test/java/org/apache/commons/math3/geometry/partitioning/RegionParser.java
new file mode 100644
index 0000000..8fc1e6e
--- /dev/null
+++ b/src/test/java/org/apache/commons/math3/geometry/partitioning/RegionParser.java
@@ -0,0 +1,303 @@
+/*
+ * 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.io.IOException;
+import java.text.ParseException;
+import java.util.StringTokenizer;
+
+import org.apache.commons.math3.geometry.Space;
+import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
+import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet;
+import org.apache.commons.math3.geometry.euclidean.oned.OrientedPoint;
+import org.apache.commons.math3.geometry.euclidean.oned.Vector1D;
+import org.apache.commons.math3.geometry.euclidean.threed.Euclidean3D;
+import org.apache.commons.math3.geometry.euclidean.threed.Plane;
+import org.apache.commons.math3.geometry.euclidean.threed.PolyhedronsSet;
+import org.apache.commons.math3.geometry.euclidean.threed.Vector3D;
+import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
+import org.apache.commons.math3.geometry.euclidean.twod.Line;
+import org.apache.commons.math3.geometry.euclidean.twod.PolygonsSet;
+import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
+import org.apache.commons.math3.geometry.spherical.oned.ArcsSet;
+import org.apache.commons.math3.geometry.spherical.oned.LimitAngle;
+import org.apache.commons.math3.geometry.spherical.oned.S1Point;
+import org.apache.commons.math3.geometry.spherical.oned.Sphere1D;
+import org.apache.commons.math3.geometry.spherical.twod.Circle;
+import org.apache.commons.math3.geometry.spherical.twod.Sphere2D;
+import org.apache.commons.math3.geometry.spherical.twod.SphericalPolygonsSet;
+
+/** Class parsing a string representation of an {@link AbstractRegion}.
+ * <p>
+ * This class is intended for tests and debug purposes only.
+ * </p>
+ * @see RegionDumper
+ * @since 3.5
+ */
+public class RegionParser {
+
+ /** Private constructor for a utility class
+ */
+ private RegionParser() {
+ }
+
+ /** Parse a string representation of an {@link ArcsSet}.
+ * @param s string to parse
+ * @return parsed region
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ public static ArcsSet parseArcsSet(final String s)
+ throws IOException, ParseException {
+ final TreeBuilder<Sphere1D> builder = new TreeBuilder<Sphere1D>("ArcsSet", s) {
+
+ /** {@inheritDoc} */
+ @Override
+ protected LimitAngle parseHyperplane()
+ throws IOException, ParseException {
+ return new LimitAngle(new S1Point(getNumber()), getBoolean(), getNumber());
+ }
+
+ };
+ return new ArcsSet(builder.getTree(), builder.getTolerance());
+ }
+
+ /** Parse a string representation of a {@link SphericalPolygonsSet}.
+ * @param s string to parse
+ * @return parsed region
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ public static SphericalPolygonsSet parseSphericalPolygonsSet(final String s)
+ throws IOException, ParseException {
+ final TreeBuilder<Sphere2D> builder = new TreeBuilder<Sphere2D>("SphericalPolygonsSet", s) {
+
+ /** {@inheritDoc} */
+ @Override
+ public Circle parseHyperplane()
+ throws IOException, ParseException {
+ return new Circle(new Vector3D(getNumber(), getNumber(), getNumber()), getNumber());
+ }
+
+ };
+ return new SphericalPolygonsSet(builder.getTree(), builder.getTolerance());
+ }
+
+ /** Parse a string representation of an {@link IntervalsSet}.
+ * @param s string to parse
+ * @return parsed region
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ public static IntervalsSet parseIntervalsSet(final String s)
+ throws IOException, ParseException {
+ final TreeBuilder<Euclidean1D> builder = new TreeBuilder<Euclidean1D>("IntervalsSet", s) {
+
+ /** {@inheritDoc} */
+ @Override
+ public OrientedPoint parseHyperplane()
+ throws IOException, ParseException {
+ return new OrientedPoint(new Vector1D(getNumber()), getBoolean(), getNumber());
+ }
+
+ };
+ return new IntervalsSet(builder.getTree(), builder.getTolerance());
+ }
+
+ /** Parse a string representation of a {@link PolygonsSet}.
+ * @param s string to parse
+ * @return parsed region
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ public static PolygonsSet parsePolygonsSet(final String s)
+ throws IOException, ParseException {
+ final TreeBuilder<Euclidean2D> builder = new TreeBuilder<Euclidean2D>("PolygonsSet", s) {
+
+ /** {@inheritDoc} */
+ @Override
+ public Line parseHyperplane()
+ throws IOException, ParseException {
+ return new Line(new Vector2D(getNumber(), getNumber()), getNumber(), getNumber());
+ }
+
+ };
+ return new PolygonsSet(builder.getTree(), builder.getTolerance());
+ }
+
+ /** Parse a string representation of a {@link PolyhedronsSet}.
+ * @param s string to parse
+ * @return parsed region
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ public static PolyhedronsSet parsePolyhedronsSet(final String s)
+ throws IOException, ParseException {
+ final TreeBuilder<Euclidean3D> builder = new TreeBuilder<Euclidean3D>("PolyhedronsSet", s) {
+
+ /** {@inheritDoc} */
+ @Override
+ public Plane parseHyperplane()
+ throws IOException, ParseException {
+ return new Plane(new Vector3D(getNumber(), getNumber(), getNumber()),
+ new Vector3D(getNumber(), getNumber(), getNumber()),
+ getNumber());
+ }
+
+ };
+ return new PolyhedronsSet(builder.getTree(), builder.getTolerance());
+ }
+
+ /** Local class for building an {@link AbstractRegion} tree.
+ * @param <S> Type of the space.
+ */
+ private abstract static class TreeBuilder<S extends Space> {
+
+ /** Keyword for tolerance. */
+ private static final String TOLERANCE = "tolerance";
+
+ /** Keyword for internal nodes. */
+ private static final String INTERNAL = "internal";
+
+ /** Keyword for leaf nodes. */
+ private static final String LEAF = "leaf";
+
+ /** Keyword for plus children trees. */
+ private static final String PLUS = "plus";
+
+ /** Keyword for minus children trees. */
+ private static final String MINUS = "minus";
+
+ /** Keyword for true flags. */
+ private static final String TRUE = "true";
+
+ /** Keyword for false flags. */
+ private static final String FALSE = "false";
+
+ /** Tree root. */
+ private BSPTree<S> root;
+
+ /** Tolerance. */
+ private final double tolerance;
+
+ /** Tokenizer parsing string representation. */
+ private final StringTokenizer tokenizer;
+
+ /** Simple constructor.
+ * @param type type of the expected representation
+ * @param reader reader for the string representation
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ public TreeBuilder(final String type, final String s)
+ throws IOException, ParseException {
+ root = null;
+ tokenizer = new StringTokenizer(s);
+ getWord(type);
+ getWord(TOLERANCE);
+ tolerance = getNumber();
+ getWord(PLUS);
+ root = new BSPTree<S>();
+ parseTree(root);
+ if (tokenizer.hasMoreTokens()) {
+ throw new ParseException("unexpected " + tokenizer.nextToken(), 0);
+ }
+ }
+
+ /** Parse a tree.
+ * @param node start node
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ private void parseTree(final BSPTree<S> node)
+ throws IOException, ParseException {
+ if (INTERNAL.equals(getWord(INTERNAL, LEAF))) {
+ // this is an internal node, it has a cut sub-hyperplane (stored as a whole hyperplane)
+ // then a minus tree, then a plus tree
+ node.insertCut(parseHyperplane());
+ getWord(MINUS);
+ parseTree(node.getMinus());
+ getWord(PLUS);
+ parseTree(node.getPlus());
+ } else {
+ // this is a leaf node, it has only an inside/outside flag
+ node.setAttribute(getBoolean());
+ }
+ }
+
+ /** Get next word.
+ * @param allowed allowed values
+ * @return parsed word
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ protected String getWord(final String ... allowed)
+ throws IOException, ParseException {
+ final String token = tokenizer.nextToken();
+ for (final String a : allowed) {
+ if (a.equals(token)) {
+ return token;
+ }
+ }
+ throw new ParseException(token + " != " + allowed[0], 0);
+ }
+
+ /** Get next number.
+ * @return parsed number
+ * @exception IOException if the string cannot be read
+ * @exception NumberFormatException if the string cannot be parsed
+ */
+ protected double getNumber()
+ throws IOException, NumberFormatException {
+ return Double.parseDouble(tokenizer.nextToken());
+ }
+
+ /** Get next boolean.
+ * @return parsed boolean
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ protected boolean getBoolean()
+ throws IOException, ParseException {
+ return getWord(TRUE, FALSE).equals(TRUE);
+ }
+
+ /** Get the built tree.
+ * @return built tree
+ */
+ public BSPTree<S> getTree() {
+ return root;
+ }
+
+ /** Get the tolerance.
+ * @return tolerance
+ */
+ public double getTolerance() {
+ return tolerance;
+ }
+
+ /** Parse an hyperplane.
+ * @return next hyperplane from the stream
+ * @exception IOException if the string cannot be read
+ * @exception ParseException if the string cannot be parsed
+ */
+ protected abstract Hyperplane<S> parseHyperplane()
+ throws IOException, ParseException;
+
+ }
+
+}
[2/3] [math] Fixed wrong intersection selection in polyhedrons sets.
Posted by lu...@apache.org.
Fixed wrong intersection selection in polyhedrons sets.
Sometimes the selected intersection point was on the wrong side of the
line (i.e. in the opposite of the direction of the line).
Thanks to Mike Zimmerman for identifying and solving the issue.
JIRA: MATH-1211
Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/bcb70e36
Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/bcb70e36
Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/bcb70e36
Branch: refs/heads/MATH_3_X
Commit: bcb70e36cac6c3ec0f3b695118e1f67583b10550
Parents: 9744a81
Author: Luc Maisonobe <lu...@apache.org>
Authored: Thu Apr 9 22:16:49 2015 +0200
Committer: Luc Maisonobe <lu...@apache.org>
Committed: Thu Apr 9 22:22:39 2015 +0200
----------------------------------------------------------------------
src/changes/changes.xml | 8 ++---
.../euclidean/threed/PolyhedronsSet.java | 14 ++++----
.../euclidean/threed/PolyhedronsSetTest.java | 37 ++++++++++++++++++++
.../geometry/euclidean/threed/issue-1211.bsp | 15 ++++++++
4 files changed, 63 insertions(+), 11 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-math/blob/bcb70e36/src/changes/changes.xml
----------------------------------------------------------------------
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index f1595c2..a3bad91 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -50,10 +50,10 @@ If the output is not quite correct, check for invisible trailing spaces!
<title>Commons Math Release Notes</title>
</properties>
<body>
- <release version="TBD" date="TBD" description="TBD">
- </release>
-
- <release version="3.5" date="2015-01-11" description="">
+ <release version="3.5" date="TBD" description="TBD">
+ <action dev="luc" type="fix" issue="MATH-1211" due-to="Mike Zimmerman">
+ Fixed wrong selection of line/polyhedron intersection point.
+ </action>
<action dev="tn" type="fix" issue="MATH-1209" due-to="Jonathan Ogilvie">
Fixed link to algorithm description in "PoissonDistribution#sample()".
</action>
http://git-wip-us.apache.org/repos/asf/commons-math/blob/bcb70e36/src/main/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSet.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSet.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSet.java
index d41d133..69d88b5 100644
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSet.java
+++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSet.java
@@ -305,9 +305,9 @@ public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
/** Get the first sub-hyperplane crossed by a semi-infinite line.
* @param point start point of the part of the line considered
* @param line line to consider (contains point)
- * @return the first sub-hyperplaned crossed by the line after the
+ * @return the first sub-hyperplane crossed by the line after the
* given point, or null if the line does not intersect any
- * sub-hyperplaned
+ * sub-hyperplane
*/
public SubHyperplane<Euclidean3D> firstIntersection(final Vector3D point, final Line line) {
return recurseFirstIntersection(getTree(true), point, line);
@@ -317,9 +317,9 @@ public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
* @param node current node
* @param point start point of the part of the line considered
* @param line line to consider (contains point)
- * @return the first sub-hyperplaned crossed by the line after the
+ * @return the first sub-hyperplane crossed by the line after the
* given point, or null if the line does not intersect any
- * sub-hyperplaned
+ * sub-hyperplane
*/
private SubHyperplane<Euclidean3D> recurseFirstIntersection(final BSPTree<Euclidean3D> node,
final Vector3D point,
@@ -331,11 +331,11 @@ public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
}
final BSPTree<Euclidean3D> minus = node.getMinus();
final BSPTree<Euclidean3D> plus = node.getPlus();
- final Plane plane = (Plane) cut.getHyperplane();
+ final Plane plane = (Plane) cut.getHyperplane();
// establish search order
final double offset = plane.getOffset((Point<Euclidean3D>) point);
- final boolean in = FastMath.abs(offset) < 1.0e-10;
+ final boolean in = FastMath.abs(offset) < getTolerance();
final BSPTree<Euclidean3D> near;
final BSPTree<Euclidean3D> far;
if (offset < 0) {
@@ -363,7 +363,7 @@ public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
if (!in) {
// search in the cut hyperplane
final Vector3D hit3D = plane.intersection(line);
- if (hit3D != null) {
+ if (hit3D != null && line.getAbscissa(hit3D) > line.getAbscissa(point)) {
final SubHyperplane<Euclidean3D> facet = boundaryFacet(hit3D, node);
if (facet != null) {
return facet;
http://git-wip-us.apache.org/repos/asf/commons-math/blob/bcb70e36/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java b/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java
index ce7c49d..6927e42 100644
--- a/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java
+++ b/src/test/java/org/apache/commons/math3/geometry/euclidean/threed/PolyhedronsSetTest.java
@@ -17,6 +17,9 @@
package org.apache.commons.math3.geometry.euclidean.threed;
import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.io.Reader;
import java.text.ParseException;
import java.util.ArrayList;
import java.util.HashSet;
@@ -37,6 +40,8 @@ import org.apache.commons.math3.geometry.partitioning.RegionDumper;
import org.apache.commons.math3.geometry.partitioning.RegionFactory;
import org.apache.commons.math3.geometry.partitioning.RegionParser;
import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
+import org.apache.commons.math3.random.RandomGenerator;
+import org.apache.commons.math3.random.Well1024a;
import org.apache.commons.math3.util.FastMath;
import org.junit.Assert;
import org.junit.Test;
@@ -364,6 +369,38 @@ public class PolyhedronsSetTest {
Assert.assertTrue(new RegionFactory<Euclidean3D>().difference(polyset, parsed).isEmpty());
}
+ @Test
+ public void testIssue1211() throws IOException, ParseException {
+
+ PolyhedronsSet polyset = RegionParser.parsePolyhedronsSet(loadTestData("issue-1211.bsp"));
+ RandomGenerator random = new Well1024a(0xb97c9d1ade21e40al);
+ int nrays = 1000;
+ for (int i = 0; i < nrays; i++) {
+ Vector3D origin = Vector3D.ZERO;
+ Vector3D direction = new Vector3D(2 * random.nextDouble() - 1,
+ 2 * random.nextDouble() - 1,
+ 2 * random.nextDouble() - 1).normalize();
+ Line line = new Line(origin, origin.add(direction), polyset.getTolerance());
+ SubHyperplane<Euclidean3D> plane = polyset.firstIntersection(origin, line);
+ if (plane != null) {
+ Vector3D intersectionPoint = ((Plane)plane.getHyperplane()).intersection(line);
+ double dotProduct = direction.dotProduct(intersectionPoint.subtract(origin));
+ Assert.assertTrue(dotProduct > 0);
+ }
+ }
+ }
+
+ private String loadTestData(final String resourceName)
+ throws IOException {
+ InputStream stream = getClass().getResourceAsStream(resourceName);
+ Reader reader = new InputStreamReader(stream, "UTF-8");
+ StringBuilder builder = new StringBuilder();
+ for (int c = reader.read(); c >= 0; c = reader.read()) {
+ builder.append((char) c);
+ }
+ return builder.toString();
+ }
+
private void checkPoints(Region.Location expected, PolyhedronsSet tree, Vector3D[] points) {
for (int i = 0; i < points.length; ++i) {
Assert.assertEquals(expected, tree.checkPoint(points[i]));
http://git-wip-us.apache.org/repos/asf/commons-math/blob/bcb70e36/src/test/resources/org/apache/commons/math3/geometry/euclidean/threed/issue-1211.bsp
----------------------------------------------------------------------
diff --git a/src/test/resources/org/apache/commons/math3/geometry/euclidean/threed/issue-1211.bsp b/src/test/resources/org/apache/commons/math3/geometry/euclidean/threed/issue-1211.bsp
new file mode 100644
index 0000000..23c2cdb
--- /dev/null
+++ b/src/test/resources/org/apache/commons/math3/geometry/euclidean/threed/issue-1211.bsp
@@ -0,0 +1,15 @@
+PolyhedronsSet
+tolerance 1.0e-8
+ plus internal -1.0 0.0 0.0 -1.0 0.0 0.0 1.0e-8
+ minus internal 0.0 1.0 0.0 0.0 1.0 0.0 1.0e-8
+ minus internal 0.0 0.0 1.0 0.0 0.0 1.0 1.0e-8
+ minus internal 0.0 0.0 -1.0 0.0 0.0 -1.0 1.0e-8
+ minus internal 0.0 -1.0 0.0 0.0 -1.0 0.0 1.0e-8
+ minus internal 1.0 0.0 0.0 1.0 0.0 0.0 1.0e-8
+ minus leaf true
+ plus leaf false
+ plus leaf false
+ plus leaf false
+ plus leaf false
+ plus leaf false
+ plus leaf false
[3/3] [math] Added forgotten message for improved fix.
Posted by lu...@apache.org.
Added forgotten message for improved fix.
Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/5c07e548
Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/5c07e548
Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/5c07e548
Branch: refs/heads/MATH_3_X
Commit: 5c07e5487ab86b25448532bb8a54e026d698a253
Parents: bcb70e3
Author: Luc Maisonobe <lu...@apache.org>
Authored: Thu Apr 9 22:26:17 2015 +0200
Committer: Luc Maisonobe <lu...@apache.org>
Committed: Thu Apr 9 22:28:53 2015 +0200
----------------------------------------------------------------------
src/changes/changes.xml | 3 +++
1 file changed, 3 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-math/blob/5c07e548/src/changes/changes.xml
----------------------------------------------------------------------
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index a3bad91..a89c8cb 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -54,6 +54,9 @@ If the output is not quite correct, check for invisible trailing spaces!
<action dev="luc" type="fix" issue="MATH-1211" due-to="Mike Zimmerman">
Fixed wrong selection of line/polyhedron intersection point.
</action>
+ <action dev="luc" type="fix" issue="MATH-1162">
+ Improved fix for corner cases in BSP-tree merging, when cut sub-hyperplanes vanish.
+ </action>
<action dev="tn" type="fix" issue="MATH-1209" due-to="Jonathan Ogilvie">
Fixed link to algorithm description in "PoissonDistribution#sample()".
</action>