Author: luc
Date: Mon Jan 13 12:42:40 2014
New Revision: 1557693
URL: http://svn.apache.org/r1557693
Log:
Removed too tight link between edges and BSP tree.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSet.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSetTest.java
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSet.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSet.java?rev=1557693&r1=1557692&r2=1557693&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSet.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSet.java
Mon Jan 13 12:42:40 2014
@@ -19,7 +19,10 @@ package org.apache.commons.math3.geometr
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
import java.util.List;
+import java.util.Map;
import org.apache.commons.math3.exception.MathIllegalStateException;
import org.apache.commons.math3.exception.util.LocalizedFormats;
@@ -225,16 +228,10 @@ public class SphericalPolygonsSet extend
// find an edge with an hyperplane that can be inserted in the node
int index = 0;
- Edge inserted =null;
+ Edge inserted = null;
while (inserted == null && index < edges.size()) {
inserted = edges.get(index++);
- if (inserted.getNode() == null) {
- if (node.insertCut(inserted.getCircle())) {
- inserted.setNode(node);
- } else {
- inserted = null;
- }
- } else {
+ if (!node.insertCut(inserted.getCircle())) {
inserted = null;
}
}
@@ -394,9 +391,6 @@ public class SphericalPolygonsSet extend
/** Circle supporting the edge. */
private final Circle circle;
- /** Node whose cut hyperplane contains this edge. */
- private BSPTree<Sphere2D> node;
-
/** Build an edge not contained in any node yet.
* @param start start vertex
* @param end end vertex
@@ -409,7 +403,6 @@ public class SphericalPolygonsSet extend
this.end = end;
this.length = length;
this.circle = circle;
- this.node = null;
// connect the vertices back to the edge
start.setOutgoing(this);
@@ -459,20 +452,6 @@ public class SphericalPolygonsSet extend
return circle.getPointAt(alpha +
circle.getPhase(start.getLocation().getVector()));
}
- /** Set the node whose cut hyperplane contains this edge.
- * @param node node whose cut hyperplane contains this edge
- */
- private void setNode(final BSPTree<Sphere2D> node) {
- this.node = node;
- }
-
- /** Get the node whose cut hyperplane contains this edge.
- * @return node whose cut hyperplane contains this edge
- */
- private BSPTree<Sphere2D> getNode() {
- return node;
- }
-
/** Connect the instance with a following edge.
* @param next edge following the instance
*/
@@ -584,7 +563,6 @@ public class SphericalPolygonsSet extend
// really add the edge
subEnd.bindWith(splitCircle);
final Edge edge = new Edge(subStart, subEnd, subLength, circle);
- edge.setNode(node);
list.add(edge);
return subEnd;
@@ -708,24 +686,32 @@ public class SphericalPolygonsSet extend
root.visit(visitor);
final List<Edge> edges = visitor.getEdges();
+
// convert the list of all edges into a list of start vertices
loops = new ArrayList<Vertex>();
- for (final Edge edge : edges) {
- if (edge.getNode() != null) {
+ while (!edges.isEmpty()) {
- // this is an edge belonging to a new loop, store it
- final Vertex startVertex = edge.getStart();
- loops.add(startVertex);
-
- // disable all remaining edges in the same loop
- for (Vertex vertex = edge.getEnd();
- vertex != startVertex;
- vertex = vertex.getOutgoing().getEnd()) {
- vertex.getIncoming().setNode(null);
+ // this is an edge belonging to a new loop, store it
+ Edge edge = edges.get(0);
+ final Vertex startVertex = edge.getStart();
+ loops.add(startVertex);
+
+ // remove all remaining edges in the same loop
+ do {
+
+ // remove one edge
+ for (final Iterator<Edge> iterator = edges.iterator();
iterator.hasNext();) {
+ if (iterator.next() == edge) {
+ iterator.remove();
+ break;
+ }
}
- startVertex.getIncoming().setNode(null);
- }
+ // go to next edge following the boundary loop
+ edge = edge.getEnd().getOutgoing();
+
+ } while (edge.getStart() != startVertex);
+
}
}
@@ -744,17 +730,21 @@ public class SphericalPolygonsSet extend
/** Tolerance below which points are consider to be identical. */
private final double tolerance;
- /** Boundary edges. */
- private final List<Edge> edges;
+ /** Built edges and their associated nodes. */
+ private final Map<Edge, BSPTree<Sphere2D>> edgeToNode;
+
+ /** Reversed map. */
+ private final Map<BSPTree<Sphere2D>, List<Edge>> nodeToEdgesList;
/** Simple constructor.
* @param root tree root
* @param tolerance below which points are consider to be identical
*/
public EdgesBuilder(final BSPTree<Sphere2D> root, final double
tolerance) {
- this.root = root;
- this.tolerance = tolerance;
- this.edges = new ArrayList<Edge>();
+ this.root = root;
+ this.tolerance = tolerance;
+ this.edgeToNode = new IdentityHashMap<Edge,
BSPTree<Sphere2D>>();
+ this.nodeToEdgesList = new IdentityHashMap<BSPTree<Sphere2D>,
List<Edge>>();
}
/** {@inheritDoc} */
@@ -764,6 +754,7 @@ public class SphericalPolygonsSet extend
/** {@inheritDoc} */
public void visitInternalNode(final BSPTree<Sphere2D> node) {
+ nodeToEdgesList.put(node, new ArrayList<Edge>());
@SuppressWarnings("unchecked")
final BoundaryAttribute<Sphere2D> attribute =
(BoundaryAttribute<Sphere2D>) node.getAttribute();
if (attribute.getPlusOutside() != null) {
@@ -798,14 +789,14 @@ public class SphericalPolygonsSet extend
} else {
edge = new Edge(start, end, a.getSize(), circle);
}
- edge.setNode(node);
- edges.add(edge);
+ edgeToNode.put(edge, node);
+ nodeToEdgesList.get(node).add(edge);
}
}
/** Get the edge that should naturally follow another one.
* @param previous edge to be continued
- * @return other edge, starting where the other one ends (they
+ * @return other edge, starting where the previous one ends (they
* have not been connected yet)
* @exception MathIllegalStateException if there is not a single other
edge
*/
@@ -816,31 +807,28 @@ public class SphericalPolygonsSet extend
final S2Point point = previous.getEnd().getLocation();
final List<BSPTree<Sphere2D>> candidates =
root.getCloseCuts(point, tolerance);
- // filter the single other node we are interested in
- BSPTree<Sphere2D> selected = null;
+ // the following edge we are looking for must start from one of
the candidates nodes
+ double closest = tolerance;
+ Edge following = null;
for (final BSPTree<Sphere2D> node : candidates) {
- if (node != previous.getNode()) {
- if (selected == null) {
- selected = node;
- } else {
- throw new
MathIllegalStateException(LocalizedFormats.OUTLINE_BOUNDARY_LOOP_OPEN);
+ for (final Edge edge : nodeToEdgesList.get(node)) {
+ if (edge != previous && edge.getStart().getIncoming() ==
null) {
+ final Vector3D edgeStart =
edge.getStart().getLocation().getVector();
+ final double gap =
Vector3D.angle(point.getVector(), edgeStart);
+ if (gap <= closest) {
+ closest = gap;
+ following = edge;
+ }
}
}
}
- if (selected == null) {
- throw new
MathIllegalStateException(LocalizedFormats.OUTLINE_BOUNDARY_LOOP_OPEN);
- }
- // find the edge associated with the selected node
- for (final Edge edge : edges) {
- if (edge.getNode() == selected &&
- Vector3D.angle(point.getVector(),
edge.getStart().getLocation().getVector()) <= tolerance) {
- return edge;
- }
+ if (following == null) {
+ // this should never happen
+ throw new
MathIllegalStateException(LocalizedFormats.OUTLINE_BOUNDARY_LOOP_OPEN);
}
- // we should never reach this point
- throw new
MathIllegalStateException(LocalizedFormats.OUTLINE_BOUNDARY_LOOP_OPEN);
+ return following;
}
@@ -851,11 +839,11 @@ public class SphericalPolygonsSet extend
public List<Edge> getEdges() throws MathIllegalStateException {
// connect the edges
- for (final Edge previous : edges) {
+ for (final Edge previous : edgeToNode.keySet()) {
previous.setNextEdge(getFollowingEdge(previous));
}
- return edges;
+ return new ArrayList<Edge>(edgeToNode.keySet());
}
Modified:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSetTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSetTest.java?rev=1557693&r1=1557692&r2=1557693&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSetTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalPolygonsSetTest.java
Mon Jan 13 12:42:40 2014
@@ -16,14 +16,20 @@
*/
package org.apache.commons.math3.geometry.spherical.twod;
+import java.util.ArrayList;
import java.util.List;
+import org.apache.commons.math3.geometry.euclidean.threed.Rotation;
import org.apache.commons.math3.geometry.euclidean.threed.Vector3D;
import org.apache.commons.math3.geometry.partitioning.Region.Location;
import org.apache.commons.math3.geometry.partitioning.RegionFactory;
+import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
+import org.apache.commons.math3.geometry.spherical.oned.ArcsSet;
+import org.apache.commons.math3.geometry.spherical.oned.Sphere1D;
import org.apache.commons.math3.random.UnitSphereRandomVectorGenerator;
import org.apache.commons.math3.random.Well1024a;
import org.apache.commons.math3.util.FastMath;
+import org.apache.commons.math3.util.MathUtils;
import org.junit.Assert;
import org.junit.Test;
@@ -205,4 +211,74 @@ public class SphericalPolygonsSetTest {
}
+ @Test
+ public void testModeratlyComplexShape() {
+ double tol = 0.01;
+ List<SubHyperplane<Sphere2D>> boundary = new
ArrayList<SubHyperplane<Sphere2D>>();
+ boundary.add(create(Vector3D.MINUS_J, Vector3D.PLUS_I,
Vector3D.PLUS_K, tol, 0.0, 0.5 * FastMath.PI));
+ boundary.add(create(Vector3D.MINUS_I, Vector3D.PLUS_K,
Vector3D.PLUS_J, tol, 0.0, 0.5 * FastMath.PI));
+ boundary.add(create(Vector3D.PLUS_K, Vector3D.PLUS_J,
Vector3D.MINUS_I, tol, 0.0, 0.5 * FastMath.PI));
+ boundary.add(create(Vector3D.MINUS_J, Vector3D.MINUS_I,
Vector3D.MINUS_K, tol, 0.0, 0.5 * FastMath.PI));
+ boundary.add(create(Vector3D.MINUS_I, Vector3D.MINUS_K,
Vector3D.MINUS_J, tol, 0.0, 0.5 * FastMath.PI));
+ boundary.add(create(Vector3D.PLUS_K, Vector3D.MINUS_J,
Vector3D.PLUS_I, tol, 0.0, 0.5 * FastMath.PI));
+ SphericalPolygonsSet polygon = new SphericalPolygonsSet(boundary, tol);
+
+ Assert.assertEquals(Location.OUTSIDE, polygon.checkPoint(new
S2Point(new Vector3D( 1, 1, 1).normalize())));
+ Assert.assertEquals(Location.INSIDE, polygon.checkPoint(new
S2Point(new Vector3D(-1, 1, 1).normalize())));
+ Assert.assertEquals(Location.INSIDE, polygon.checkPoint(new
S2Point(new Vector3D(-1, -1, 1).normalize())));
+ Assert.assertEquals(Location.INSIDE, polygon.checkPoint(new
S2Point(new Vector3D( 1, -1, 1).normalize())));
+ Assert.assertEquals(Location.OUTSIDE, polygon.checkPoint(new
S2Point(new Vector3D( 1, 1, -1).normalize())));
+ Assert.assertEquals(Location.OUTSIDE, polygon.checkPoint(new
S2Point(new Vector3D(-1, 1, -1).normalize())));
+ Assert.assertEquals(Location.INSIDE, polygon.checkPoint(new
S2Point(new Vector3D(-1, -1, -1).normalize())));
+ Assert.assertEquals(Location.OUTSIDE, polygon.checkPoint(new
S2Point(new Vector3D( 1, -1, -1).normalize())));
+
+ Assert.assertEquals(MathUtils.TWO_PI, polygon.getSize(), 1.0e-10);
+ Assert.assertEquals(3 * FastMath.PI, polygon.getBoundarySize(),
1.0e-10);
+
+ List<SphericalPolygonsSet.Vertex> loops = polygon.getBoundaryLoops();
+ Assert.assertEquals(1, loops.size());
+ boolean pXFound = false;
+ boolean mXFound = false;
+ boolean pYFound = false;
+ boolean mYFound = false;
+ boolean pZFound = false;
+ boolean mZFound = false;
+ SphericalPolygonsSet.Vertex first = loops.get(0);
+ int count = 0;
+ for (SphericalPolygonsSet.Vertex v = first; count == 0 || v != first;
v = v.getOutgoing().getEnd()) {
+ ++count;
+ SphericalPolygonsSet.Edge e = v.getIncoming();
+ Assert.assertTrue(v == e.getStart().getOutgoing().getEnd());
+ pXFound = pXFound ||
v.getLocation().getVector().distance(Vector3D.PLUS_I) < 1.0e-10;
+ mXFound = mXFound ||
v.getLocation().getVector().distance(Vector3D.MINUS_I) < 1.0e-10;
+ pYFound = pYFound ||
v.getLocation().getVector().distance(Vector3D.PLUS_J) < 1.0e-10;
+ mYFound = mYFound ||
v.getLocation().getVector().distance(Vector3D.MINUS_J) < 1.0e-10;
+ pZFound = pZFound ||
v.getLocation().getVector().distance(Vector3D.PLUS_K) < 1.0e-10;
+ mZFound = mZFound ||
v.getLocation().getVector().distance(Vector3D.MINUS_K) < 1.0e-10;
+ Assert.assertEquals(0.5 * FastMath.PI, e.getLength(), 1.0e-10);
+ }
+ Assert.assertTrue(pXFound);
+ Assert.assertTrue(mXFound);
+ Assert.assertTrue(pYFound);
+ Assert.assertTrue(mYFound);
+ Assert.assertTrue(pZFound);
+ Assert.assertTrue(mZFound);
+ Assert.assertEquals(6, count);
+
+ }
+
+ private SubCircle create(Vector3D pole, Vector3D x, Vector3D y,
+ double tolerance, double ... limits) {
+ RegionFactory<Sphere1D> factory = new RegionFactory<Sphere1D>();
+ Circle circle = new Circle(pole, tolerance);
+ Circle phased =
+ (Circle) Circle.getTransform(new Rotation(circle.getXAxis(),
circle.getYAxis(), x, y)).apply(circle);
+ ArcsSet set = (ArcsSet) factory.getComplement(new ArcsSet(tolerance));
+ for (int i = 0; i < limits.length; i += 2) {
+ set = (ArcsSet) factory.union(set, new ArcsSet(limits[i], limits[i
+ 1], tolerance));
+ }
+ return new SubCircle(phased, set);
+ }
+
+
}
