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/10 16:46:52 UTC
[2/2] [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/a06a1584
Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/a06a1584
Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/a06a1584
Branch: refs/heads/master
Commit: a06a15846544681467c040d471d9a2daa281a866
Parents: b8e4612
Author: Luc Maisonobe <lu...@apache.org>
Authored: Fri Apr 10 16:37:18 2015 +0200
Committer: Luc Maisonobe <lu...@apache.org>
Committed: Fri Apr 10 16:37:18 2015 +0200
----------------------------------------------------------------------
.../euclidean/threed/PolyhedronsSet.java | 14 ++++----
.../euclidean/threed/PolyhedronsSetTest.java | 37 ++++++++++++++++++++
.../geometry/euclidean/threed/issue-1211.bsp | 15 ++++++++
3 files changed, 59 insertions(+), 7 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-math/blob/a06a1584/src/main/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSet.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSet.java b/src/main/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSet.java
index 9c46ae3..2f3bfa9 100644
--- a/src/main/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSet.java
+++ b/src/main/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSet.java
@@ -240,9 +240,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);
@@ -252,9 +252,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,
@@ -266,11 +266,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) {
@@ -298,7 +298,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/a06a1584/src/test/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSetTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSetTest.java b/src/test/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSetTest.java
index c5cc9d7..b96c045 100644
--- a/src/test/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSetTest.java
+++ b/src/test/java/org/apache/commons/math4/geometry/euclidean/threed/PolyhedronsSetTest.java
@@ -17,6 +17,9 @@
package org.apache.commons.math4.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;
@@ -43,6 +46,8 @@ import org.apache.commons.math4.geometry.partitioning.RegionDumper;
import org.apache.commons.math4.geometry.partitioning.RegionFactory;
import org.apache.commons.math4.geometry.partitioning.RegionParser;
import org.apache.commons.math4.geometry.partitioning.SubHyperplane;
+import org.apache.commons.math4.random.RandomGenerator;
+import org.apache.commons.math4.random.Well1024a;
import org.apache.commons.math4.util.FastMath;
import org.junit.Assert;
import org.junit.Test;
@@ -370,6 +375,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/a06a1584/src/test/resources/org/apache/commons/math4/geometry/euclidean/threed/issue-1211.bsp
----------------------------------------------------------------------
diff --git a/src/test/resources/org/apache/commons/math4/geometry/euclidean/threed/issue-1211.bsp b/src/test/resources/org/apache/commons/math4/geometry/euclidean/threed/issue-1211.bsp
new file mode 100644
index 0000000..23c2cdb
--- /dev/null
+++ b/src/test/resources/org/apache/commons/math4/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