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:37 UTC
[2/3] [math] Fixed wrong intersection selection in polyhedrons sets.
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