Author: luc
Date: Sun Feb 9 19:17:55 2014
New Revision: 1566358
URL: http://svn.apache.org/r1566358
Log:
Added a getEnclosingCap method for spherical polygons.
In simple cases (small polygon, one piece only, no holes), the enclosing
cap will be the smallest one, but this is not guaranteed in the general
case.
The enclosing cap can be used to speed up inside/outside points when the
region is small with respect to the sphere as with only one check of an
angular separation, most points of the sphere can be safely identified
as outside. The more time-consuming checks involving the full boundary
are therefore done only for a small portion of the sphere.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/PropertiesComputer.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGenerator.java
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/SphericalCapGeneratorTest.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/partitioning/AbstractRegion.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java?rev=1566358&r1=1566357&r2=1566358&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java
Sun Feb 9 19:17:55 2014
@@ -269,6 +269,28 @@ public abstract class AbstractRegion<S e
}
/** {@inheritDoc} */
+ public boolean isFull() {
+ return isFull(tree);
+ }
+
+ /** {@inheritDoc} */
+ public boolean isFull(final BSPTree<S> node) {
+
+ // we use a recursive function rather than the BSPTreeVisitor
+ // interface because we can stop visiting the tree as soon as we
+ // have found an outside cell
+
+ if (node.getCut() == null) {
+ // if we find an outside node, the region does not cover full space
+ return (Boolean) node.getAttribute();
+ }
+
+ // check both sides of the sub-tree
+ return isFull(node.getMinus()) && isFull(node.getPlus());
+
+ }
+
+ /** {@inheritDoc} */
public boolean contains(final Region<S> region) {
return new RegionFactory<S>().difference(region, this).isEmpty();
}
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java?rev=1566358&r1=1566357&r2=1566358&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/partitioning/Region.java
Sun Feb 9 19:17:55 2014
@@ -99,6 +99,20 @@ public interface Region<S extends Space>
*/
boolean isEmpty(final BSPTree<S> node);
+ /** Check if the instance covers the full space.
+ * @return true if the instance covers the full space
+ */
+ boolean isFull();
+
+ /** Check if the sub-tree starting at a given node covers the full space.
+ * @param node root node of the sub-tree (<em>must</em> have {@link
+ * Region Region} tree semantics, i.e. the leaf nodes must have
+ * {@code Boolean} attributes representing an inside/outside
+ * property)
+ * @return true if the sub-tree starting at the given node covers the full
space
+ */
+ boolean isFull(final BSPTree<S> node);
+
/** Check if the instance entirely contains another region.
* @param region region to check against the instance
* @return true if the instance contains the specified tree
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/PropertiesComputer.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/PropertiesComputer.java?rev=1566358&r1=1566357&r2=1566358&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/PropertiesComputer.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/PropertiesComputer.java
Sun Feb 9 19:17:55 2014
@@ -132,8 +132,7 @@ class PropertiesComputer implements BSPT
// loop around the cell
for (Edge e = start.getOutgoing(); n == 0 || e.getStart() != start; e
= e.getEnd().getOutgoing()) {
- final Vector3D middle = e.getPointAt(0.5 * e.getLength());
- sumB = new Vector3D(1, sumB, e.getLength(), middle);
+ sumB = new Vector3D(1, sumB, e.getLength(),
e.getCircle().getPole());
n++;
}
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGenerator.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGenerator.java?rev=1566358&r1=1566357&r2=1566358&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGenerator.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGenerator.java
Sun Feb 9 19:17:55 2014
@@ -41,7 +41,7 @@ import org.apache.commons.math3.util.Fas
* boundary points only is ambiguous: one cannot say if what has been
* computed is the cap or its complement without further information. For
* this reason, the generator must be built with a point known to lie
- * outside of the spherical cap to generate, so it can decide which of the
+ * inside of the spherical cap to generate, so it can decide which of the
* two caps should be generated.
* </p>
* @version $Id$
@@ -49,21 +49,21 @@ import org.apache.commons.math3.util.Fas
*/
public class SphericalCapGenerator implements SupportBallGenerator<Sphere2D,
S2Point> {
- /** Reference point that must be outside of the cap. */
- private final Vector3D outside;
+ /** Reference point that must be inside of the cap. */
+ private final Vector3D inside;
/** Simple constructor.
- * @param outside reference point that must be outside of generated caps
+ * @param inside reference point that must be inside of generated caps
*/
- public SphericalCapGenerator(final Vector3D outside) {
- this.outside = outside;
+ public SphericalCapGenerator(final Vector3D inside) {
+ this.inside = inside;
}
/** {@inheritDoc} */
public EnclosingBall<Sphere2D, S2Point> ballOnSupport(final List<S2Point>
support) {
if (support.size() < 1) {
- return new EnclosingBall<Sphere2D, S2Point>(new
S2Point(outside.negate()), -1.0);
+ return new EnclosingBall<Sphere2D, S2Point>(new S2Point(inside),
-1.0);
} else {
final S2Point vA = support.get(0);
if (support.size() < 2) {
@@ -92,6 +92,32 @@ public class SphericalCapGenerator imple
}
}
+ /** Generate a spherical cap enclosing three circles.
+ * @param c1 first circle
+ * @param c2 second circle
+ * @param c3 third circle
+ * @return spherical cap enclosing the circles
+ */
+ public EnclosingBall<Sphere2D, S2Point> ballOnSupport(final Circle c1,
+ final Circle c2,
+ final Circle c3) {
+ final BigFraction[] p1 = convert(c1.getPole());
+ final BigFraction[] p2 = convert(c2.getPole());
+ final BigFraction[] p3 = convert(c3.getPole());
+ final BigFraction[] bfPole = crossProduct(subtract(p1, p2),
+ subtract(p2, p3));
+ if (dotProduct(bfPole, p1).doubleValue() < 0) {
+ bfPole[0] = bfPole[0].negate();
+ bfPole[1] = bfPole[1].negate();
+ bfPole[2] = bfPole[2].negate();
+ }
+ final Vector3D pole = convert(bfPole);
+
+ return new EnclosingBall<Sphere2D, S2Point>(new S2Point(pole),
+ Vector3D.angle(pole,
c1.getPole()) + 0.5 * FastMath.PI);
+
+ }
+
/** Convert a vector to exact arithmetic array of Cartesian coordinates.
* @param v vector to convert
* @return exact arithmetic coordinates array
@@ -132,6 +158,19 @@ public class SphericalCapGenerator imple
};
}
+ /** Subtract two vectors
+ * @param u first vector
+ * @param v second vector
+ * @return u - v
+ */
+ private BigFraction[] subtract(final BigFraction[] u, final BigFraction[]
v) {
+ return new BigFraction[] {
+ u[0].subtract(v[0]),
+ u[1].subtract(v[1]),
+ u[2].subtract(v[2]),
+ };
+ }
+
/** Compute cross product of two vectors
* @param u first vector
* @param v second vector
@@ -145,6 +184,15 @@ public class SphericalCapGenerator imple
};
}
+ /** Compute dot product of two vectors
+ * @param u first vector
+ * @param v second vector
+ * @return u.v
+ */
+ private BigFraction dotProduct(final BigFraction[] u, final BigFraction[]
v) {
+ return
u[0].multiply(v[0]).add(u[1].multiply(v[1])).add(u[2].multiply(v[2]));
+ }
+
/** Select the spherical cap or its complement to ensure outside point is
outside.
* @param pole spherical cap pole (or its opposite)
* @param radius spherical cap angular radius (or its complement to \( \pi
\))
@@ -153,7 +201,7 @@ public class SphericalCapGenerator imple
*/
private EnclosingBall<Sphere2D, S2Point> selectCap(final Vector3D pole,
final double radius,
final S2Point ...
support) {
- if (Vector3D.angle(pole, outside) >= radius) {
+ if (Vector3D.angle(pole, inside) <= radius) {
// it is already the good pole and radius
return new EnclosingBall<Sphere2D, S2Point>(new S2Point(pole),
radius, support);
} else {
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=1566358&r1=1566357&r2=1566358&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
Sun Feb 9 19:17:55 2014
@@ -19,10 +19,14 @@ package org.apache.commons.math3.geometr
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import org.apache.commons.math3.exception.MathIllegalStateException;
+import org.apache.commons.math3.exception.MathInternalError;
+import org.apache.commons.math3.geometry.enclosing.EnclosingBall;
+import org.apache.commons.math3.geometry.enclosing.WelzlEncloser;
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.AbstractRegion;
@@ -410,4 +414,313 @@ public class SphericalPolygonsSet extend
}
+ /** Get a spherical cap enclosing the polygon.
+ * <p>
+ * This method is intended as a first test to quickly identify points
+ * that are guaranteed to be outside of the region, hence performing a full
+ * {@link #checkPoint(org.apache.commons.math3.geometry.Vector) checkPoint}
+ * only if the point status remains undecided after the quick check. It is
+ * is therefore mostly useful to speed up computation for small polygons
with
+ * complex shapes (say a country boundary on Earth), as the spherical cap
will
+ * be small and hence will reliably identify a large part of the sphere as
outside,
+ * whereas the full check can be more computing intensive. A typical use
case is
+ * therefore:
+ * </p>
+ * <pre>
+ * // compute region, plus an enclosing spherical cap
+ * SphericalPolygonsSet complexShape = ...;
+ * EnclosingBall<Sphere2D, S2Point> cap = complexShape.getEnclosingCap();
+ *
+ * // check lots of points
+ * for (Vector3D p : points) {
+ *
+ * final Location l;
+ * if (cap.contains(p)) {
+ * // we cannot be sure where the point is
+ * // we need to perform the full computation
+ * l = complexShape.checkPoint(v);
+ * } else {
+ * // no need to do further computation,
+ * // we already know the point is outside
+ * l = Location.OUTSIDE;
+ * }
+ *
+ * // use l ...
+ *
+ * }
+ * </pre>
+ * <p>
+ * In the special cases of empty or whole sphere polygons, special
+ * spherical caps are returned, with angular radius set to negative
+ * or positive infinity so the {@link
+ * EnclosingBall#contains(org.apache.commons.math3.geometry.Point)
ball.contains(point)}
+ * method return always false or true.
+ * </p>
+ * <p>
+ * This method is <em>not</em> guaranteed to return the smallest enclosing
cap. It
+ * will do so for small polygons without holes, but may select a very
large spherical
+ * cap in other cases.
+ * </p>
+ * @return a spherical cap enclosing the polygon
+ */
+ public EnclosingBall<Sphere2D, S2Point> getEnclosingCap() {
+
+ // handle special cases first
+ if (isEmpty()) {
+ return new EnclosingBall<Sphere2D, S2Point>(S2Point.PLUS_K,
Double.NEGATIVE_INFINITY);
+ }
+ if (isFull()) {
+ return new EnclosingBall<Sphere2D, S2Point>(S2Point.PLUS_K,
Double.POSITIVE_INFINITY);
+ }
+
+ // as the polygons is neither empty nor full, it has some boundaries
and cut hyperplanes
+ final BSPTree<Sphere2D> root = getTree(false);
+ if (isEmpty(root.getMinus()) && isFull(root.getPlus())) {
+ // the polygon covers an hemisphere, and its boundary is one 2Ï
long edge
+ final Circle circle = (Circle) root.getCut().getHyperplane();
+ return new EnclosingBall<Sphere2D, S2Point>(new
S2Point(circle.getPole()).negate(),
+ 0.5 * FastMath.PI);
+ }
+ if (isFull(root.getMinus()) && isEmpty(root.getPlus())) {
+ // the polygon covers an hemisphere, and its boundary is one 2Ï
long edge
+ final Circle circle = (Circle) root.getCut().getHyperplane();
+ return new EnclosingBall<Sphere2D, S2Point>(new
S2Point(circle.getPole()),
+ 0.5 * FastMath.PI);
+ }
+
+ // extract boundary
+ final List<Vertex> boundary = getBoundaryLoops();
+
+ final List<S2Point> points = new ArrayList<S2Point>();
+ for (final Vertex loopStart : boundary) {
+ // extract points from the boundary loops, to be used by the
encloser
+ for (Vertex v = loopStart; points.isEmpty() || v != loopStart; v =
v.getOutgoing().getEnd()) {
+ points.add(v.getLocation());
+ }
+ }
+
+ // find the smallest enclosing spherical cap
+ final SphericalCapGenerator capGenerator = new
SphericalCapGenerator(getInsidePoint(boundary));
+ final WelzlEncloser<Sphere2D, S2Point> encloser =
+ new WelzlEncloser<Sphere2D, S2Point>(getTolerance(),
capGenerator);
+ EnclosingBall<Sphere2D, S2Point> enclosing = encloser.enclose(points);
+
+ // ensure that the spherical cap (which was defined using only a few
points)
+ // does not cross any edges
+ if (enclosing.getRadius() >= 0.5 * FastMath.PI) {
+ final List<Edge> notEnclosed = notEnclosed(boundary, enclosing);
+ if (!notEnclosed.isEmpty()) {
+ // the vertex-based spherical cap is too small
+ // it does not fully enclose some edges
+
+ // add the edges converging to the support points if any
+ for (final S2Point point : enclosing.getSupport()) {
+ final Vertex vertex = associatedVertex(point, boundary);
+ if (vertex != null) {
+ addEdge(vertex.getIncoming(), notEnclosed);
+ addEdge(vertex.getOutgoing(), notEnclosed);
+ }
+ }
+ if (notEnclosed.size() < 3) {
+ // this should never happen
+ throw new MathInternalError();
+ }
+
+ // enlarge the spherical cap so it encloses even the three
farthest edges
+ Collections.sort(notEnclosed, new
DistanceComparator(enclosing.getCenter().getVector()));
+ enclosing =
capGenerator.ballOnSupport(notEnclosed.get(notEnclosed.size() - 1).getCircle(),
+
notEnclosed.get(notEnclosed.size() - 2).getCircle(),
+
notEnclosed.get(notEnclosed.size() - 3).getCircle());
+
+ }
+ }
+
+ // return the spherical cap found
+ return enclosing;
+
+ }
+
+ /** Get an inside point.
+ * @param boundary boundary loops (known to be non-empty)
+ * @return an inside point
+ */
+ private Vector3D getInsidePoint(final List<Vertex> boundary) {
+
+ // search for a leaf inside cell bounded by the loop
+ final BSPTree<Sphere2D> leaf =
getInsideLeaf(boundary.get(0).getOutgoing());
+
+ // build a convex region from this inside leaf
+ final SphericalPolygonsSet convex =
+ new SphericalPolygonsSet(leaf.pruneAroundConvexCell(Boolean.TRUE,
Boolean.FALSE, null),
+ getTolerance());
+
+ // select the convex region barycenter as the inside point
+ return ((S2Point) convex.getBarycenter()).getVector();
+
+ }
+
+ /** Get an inside leaf cell relative to a single boundary loop.
+ * @param edge edge belonging to the loop
+ * @return an inside leaf cell
+ */
+ private BSPTree<Sphere2D> getInsideLeaf(final Edge edge) {
+
+ // search for the node whose cut sub-hyperplane contains the edge
+ final S2Point middlePoint = new S2Point(edge.getPointAt(0.5 *
edge.getLength()));
+ final BSPTree<Sphere2D> cuttingNode =
getTree(true).getCell(middlePoint, getTolerance());
+ if (cuttingNode.getCut() == null) {
+ // this should never happen
+ throw new MathInternalError();
+ }
+
+ final Vector3D cutPole = ((Circle)
cuttingNode.getCut().getHyperplane()).getPole();
+ final Vector3D edgePole = edge.getCircle().getPole();
+
+ if (Vector3D.dotProduct(cutPole, edgePole) > 0) {
+ // the inside part is on the minus part of the cut
+ return cuttingNode.getMinus().getCell(middlePoint, getTolerance());
+ } else {
+ // the inside part is on the plus part of the cut
+ return cuttingNode.getPlus().getCell(middlePoint, getTolerance());
+ }
+
+ }
+
+ /** Get the edges that fails to be in an enclosing spherical cap.
+ * <p>
+ * This method must be called <em>only</em> when the edges endpoints
+ * are already known to be all inside of the spherical cap.
+ * </p>
+ * @param boundary boundary loops
+ * @param cap spherical cap that already encloses all vertices
+ * @return the edges that are not fully in the cap, despite their
endpoints are
+ */
+ private List<Edge> notEnclosed(final List<Vertex> boundary,
+ final EnclosingBall<Sphere2D, S2Point>
cap) {
+
+ final List<Edge> edges = new ArrayList<Edge>();
+
+ for (final Vertex loopStart : boundary) {
+ int count = 0;
+ Edge edge = null;
+ for (Vertex vertex = loopStart; count == 0 || vertex != loopStart;
vertex = edge.getEnd()) {
+
+ ++count;
+ edge = vertex.getOutgoing();
+
+ // find the intersection of the circle containing the edge and
the cap boundary
+ // let (u, α) and (v, β) be the poles and angular radii of
the two circles
+ // the intersection is computed as p = a u + b v + c u^v, with
||p|| = 1, so:
+ // a = (cos α - u.v cos β) / (1 - (u.v)²)
+ // b = (cos β - u.v cos α) / (1 - (u.v)²)
+ // c = ±â[(1 - (a u + b v)²) / (1 - (u.v)²)]
+ // here, α = Ï/2, hence cos α = 0
+ // a u + b v is the part of the p vector in the (u, v) plane
+ // c u^v is the part of the p vector orthogonal to the (u, v)
plane
+ final Vector3D u = edge.getCircle().getPole();
+ final Vector3D v = cap.getCenter().getVector();
+ final double cosBeta = FastMath.cos(cap.getRadius());
+ final double s = Vector3D.dotProduct(u, v);
+ final double f = 1.0 / ((1 - s) * (1 + s));
+ final double b = cosBeta * f;
+ final double a = -s * b;
+ final Vector3D inPlane = new Vector3D(a, u, b, v);
+ final double aubv2 = inPlane.getNormSq();
+ if (aubv2 < 1.0) {
+
+ // the two circles have two intersection points
+ final double c = FastMath.sqrt((1 - aubv2) * f);
+ final Vector3D crossPlane = Vector3D.crossProduct(u, v);
+ final Vector3D pPlus = new Vector3D(1, inPlane, +c,
crossPlane);
+ final Vector3D pMinus = new Vector3D(1, inPlane, -c,
crossPlane);
+ if (Vector3D.angle(pPlus,
edge.getStart().getLocation().getVector()) <= getTolerance() ||
+ Vector3D.angle(pPlus,
edge.getStart().getLocation().getVector()) <= getTolerance() ||
+ Vector3D.angle(pPlus,
edge.getStart().getLocation().getVector()) <= getTolerance() ||
+ Vector3D.angle(pPlus,
edge.getStart().getLocation().getVector()) <= getTolerance()) {
+ // the edge endpoints are really close, we select the
edge
+ edges.add(edge);
+ } else {
+ // the edge is limited to a part of the circle, check
its extension
+ final double startPhase =
edge.getCircle().getPhase(edge.getStart().getLocation().getVector());
+ final double pPlusRelativePhase =
MathUtils.normalizeAngle(edge.getCircle().getPhase(pPlus),
+
startPhase + FastMath.PI);
+ final double pMinusRelativePhase =
MathUtils.normalizeAngle(edge.getCircle().getPhase(pMinus),
+
startPhase + FastMath.PI);
+ if (FastMath.min(pPlusRelativePhase,
pMinusRelativePhase) < edge.getLength()) {
+ // the edge really goes out of the cap and enter
it again,
+ // it is not entirely contained in the cap
+ edges.add(edge);
+ }
+ }
+
+ }
+
+ }
+ }
+
+ return edges;
+
+ }
+
+ /** Find the vertex associated to a point.
+ * @param point point to associate to a vertex
+ * @param boundary boundary loops
+ * @return vertex associated to point, or null if the point is not a vertex
+ */
+ private Vertex associatedVertex(final S2Point point, final List<Vertex>
boundary) {
+ for (final Vertex loopStart : boundary) {
+ int count = 0;
+ for (Vertex vertex = loopStart; count == 0 || vertex != loopStart;
vertex = vertex.getOutgoing().getEnd()) {
+ ++count;
+ if (point == vertex.getLocation()) {
+ return vertex;
+ }
+ }
+ }
+ return null;
+ }
+
+ /** Add an edge to a list if not already present.
+ * @param edge edge to add
+ * @param list to which edge must be added
+ */
+ private void addEdge(final Edge edge, final List<Edge> list) {
+ for (final Edge present : list) {
+ if (present == edge) {
+ // the edge was already in the list
+ return;
+ }
+ }
+ list.add(edge);
+ }
+
+ /** Comparator for sorting edges according to distance wrt a spherical cap
pole. */
+ private static class DistanceComparator implements Comparator<Edge> {
+
+ /** Pole of the spherical cap. */
+ private final Vector3D pole;
+
+ /** Simple constructor.
+ * @param pole pole of the spherical cap
+ */
+ public DistanceComparator(final Vector3D pole) {
+ this.pole = pole;
+ }
+
+ /** {@inheritDoc} */
+ public int compare(final Edge o1, final Edge o2) {
+ return Double.compare(distance(o1), distance(o2));
+ }
+
+ /** Compute distance between edge and pole.
+ * @param edge edge
+ * @return distance between adged and pole
+ */
+ private double distance(final Edge edge) {
+ final double alpha = edge.getCircle().getPole().distance(pole);
+ return FastMath.max(alpha + 0.5 * FastMath.PI, 1.5 * FastMath.PI -
alpha);
+ }
+
+ }
+
}
Modified:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGeneratorTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGeneratorTest.java?rev=1566358&r1=1566357&r2=1566358&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGeneratorTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/twod/SphericalCapGeneratorTest.java
Sun Feb 9 19:17:55 2014
@@ -36,7 +36,7 @@ public class SphericalCapGeneratorTest {
@Test
public void testSupport0Point() {
List<S2Point> support = Arrays.asList(new S2Point[0]);
- EnclosingBall<Sphere2D, S2Point> cap = new
SphericalCapGenerator(Vector3D.MINUS_K).ballOnSupport(support);
+ EnclosingBall<Sphere2D, S2Point> cap = new
SphericalCapGenerator(Vector3D.PLUS_K).ballOnSupport(support);
Assert.assertTrue(cap.getRadius() < 0);
Assert.assertEquals(0, cap.getSupportSize());
Assert.assertEquals(0, cap.getSupport().length);
@@ -45,7 +45,7 @@ public class SphericalCapGeneratorTest {
@Test
public void testSupport1Point() {
List<S2Point> support = Arrays.asList(new S2Point(1, 2));
- EnclosingBall<Sphere2D, S2Point> cap = new
SphericalCapGenerator(Vector3D.MINUS_K).ballOnSupport(support);
+ EnclosingBall<Sphere2D, S2Point> cap = new
SphericalCapGenerator(Vector3D.PLUS_K).ballOnSupport(support);
Assert.assertEquals(0.0, cap.getRadius(), 1.0e-10);
Assert.assertTrue(cap.contains(support.get(0)));
Assert.assertTrue(cap.contains(support.get(0), 0.5));
@@ -65,7 +65,7 @@ public class SphericalCapGeneratorTest {
double phi = 1.0;
List<S2Point> support = Arrays.asList(new S2Point(0, phi), new
S2Point(0.5 * FastMath.PI, phi));
EnclosingBall<Sphere2D, S2Point> cap =
- new SphericalCapGenerator(new Vector3D(-1, -1,
-1)).ballOnSupport(support);
+ new SphericalCapGenerator(new Vector3D(1, 1,
1)).ballOnSupport(support);
double cosPhi = FastMath.cos(phi);
Assert.assertEquals(0.5 * FastMath.acos(cosPhi * cosPhi),
cap.getRadius(), 1.0e-10);
int i = 0;
@@ -87,7 +87,7 @@ public class SphericalCapGeneratorTest {
double phi = 1.0;
List<S2Point> support = Arrays.asList(new S2Point(0, phi), new
S2Point(0.5 * FastMath.PI, phi));
EnclosingBall<Sphere2D, S2Point> cap =
- new SphericalCapGenerator(new Vector3D(1, 1,
1)).ballOnSupport(support);
+ new SphericalCapGenerator(new Vector3D(-1, -1,
-1)).ballOnSupport(support);
double cosPhi = FastMath.cos(phi);
Assert.assertEquals(FastMath.PI - 0.5 * FastMath.acos(cosPhi *
cosPhi), cap.getRadius(), 1.0e-10);
int i = 0;
@@ -108,7 +108,7 @@ public class SphericalCapGeneratorTest {
public void testSupport3Points() {
List<S2Point> support = Arrays.asList(new S2Point(0, 1), new
S2Point(0, 1.6), new S2Point(2, 2));
EnclosingBall<Sphere2D, S2Point> cap =
- new
SphericalCapGenerator(Vector3D.MINUS_I).ballOnSupport(support);
+ new
SphericalCapGenerator(Vector3D.PLUS_I).ballOnSupport(support);
// reference value computed using expression found in I. Todhunter book
// Spherical Trigonometry: For the Use of Colleges and Schools
@@ -162,13 +162,13 @@ public class SphericalCapGeneratorTest {
sinR *
FastMath.sin(alpha), y)));
}
EnclosingBall<Sphere2D, S2Point> cap =
- new
SphericalCapGenerator(Vector3D.MINUS_K).ballOnSupport(support);
- if (refCenter.distance(S2Point.MINUS_K) > refRadius) {
- Assert.assertEquals(0.0, refCenter.distance(cap.getCenter()), 3e-9
* refRadius);
- Assert.assertEquals(refRadius, cap.getRadius(), 7e-10 * refRadius);
+ new
SphericalCapGenerator(Vector3D.PLUS_K).ballOnSupport(support);
+ if (refCenter.distance(S2Point.PLUS_K) < refRadius) {
+ Assert.assertEquals(0.0, refCenter.distance(cap.getCenter()),
3e-9 * refRadius);
+ Assert.assertEquals(refRadius, cap.getRadius(), 7e-10 *
refRadius);
} else {
Assert.assertEquals(FastMath.PI,
refCenter.distance(cap.getCenter()), 3e-9 * refRadius);
- Assert.assertEquals(FastMath.PI - refRadius, cap.getRadius(),
7e-10 * refRadius);
+ Assert.assertEquals(FastMath.PI - refRadius, cap.getRadius(),
7e-10 * refRadius);
}
}
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=1566358&r1=1566357&r2=1566358&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
Sun Feb 9 19:17:55 2014
@@ -19,6 +19,7 @@ package org.apache.commons.math3.geometr
import java.util.ArrayList;
import java.util.List;
+import org.apache.commons.math3.geometry.enclosing.EnclosingBall;
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;
@@ -47,6 +48,25 @@ public class SphericalPolygonsSetTest {
Assert.assertEquals(4 * FastMath.PI, new SphericalPolygonsSet(0.01,
new S2Point[0]).getSize(), 1.0e-10);
Assert.assertEquals(0, new SphericalPolygonsSet(0.01, new
S2Point[0]).getBoundarySize(), 1.0e-10);
Assert.assertEquals(0, full.getBoundaryLoops().size());
+ Assert.assertTrue(full.getEnclosingCap().getRadius() > 0);
+
Assert.assertTrue(Double.isInfinite(full.getEnclosingCap().getRadius()));
+ }
+
+ @Test
+ public void testEmpty() {
+ SphericalPolygonsSet empty =
+ (SphericalPolygonsSet) new
RegionFactory<Sphere2D>().getComplement(new SphericalPolygonsSet(1.0e-10));
+ UnitSphereRandomVectorGenerator random =
+ new UnitSphereRandomVectorGenerator(3, new
Well1024a(0x76d9205d6167b6ddl));
+ for (int i = 0; i < 1000; ++i) {
+ Vector3D v = new Vector3D(random.nextVector());
+ Assert.assertEquals(Location.OUTSIDE, empty.checkPoint(new
S2Point(v)));
+ }
+ Assert.assertEquals(0, empty.getSize(), 1.0e-10);
+ Assert.assertEquals(0, empty.getBoundarySize(), 1.0e-10);
+ Assert.assertEquals(0, empty.getBoundaryLoops().size());
+ Assert.assertTrue(empty.getEnclosingCap().getRadius() < 0);
+
Assert.assertTrue(Double.isInfinite(empty.getEnclosingCap().getRadius()));
}
@Test
@@ -67,6 +87,16 @@ public class SphericalPolygonsSetTest {
}
}
Assert.assertEquals(1, south.getBoundaryLoops().size());
+
+ EnclosingBall<Sphere2D, S2Point> southCap = south.getEnclosingCap();
+ Assert.assertEquals(0.0,
S2Point.MINUS_K.distance(southCap.getCenter()), 1.0e-10);
+ Assert.assertEquals(0.5 * FastMath.PI, southCap.getRadius(), 1.0e-10);
+
+ EnclosingBall<Sphere2D, S2Point> northCap =
+ ((SphericalPolygonsSet) new
RegionFactory<Sphere2D>().getComplement(south)).getEnclosingCap();
+ Assert.assertEquals(0.0,
S2Point.PLUS_K.distance(northCap.getCenter()), 1.0e-10);
+ Assert.assertEquals(0.5 * FastMath.PI, northCap.getRadius(), 1.0e-10);
+
}
@Test
@@ -123,10 +153,19 @@ public class SphericalPolygonsSetTest {
Assert.assertEquals(3, count);
Assert.assertEquals(0.0,
- new Vector3D(1, 1,
1).normalize().distance(((S2Point) octant.getBarycenter()).getVector()),
+ ((S2Point) octant.getBarycenter()).distance(new
S2Point(new Vector3D(1, 1, 1))),
1.0e-10);
Assert.assertEquals(0.5 * FastMath.PI, octant.getSize(), 1.0e-10);
+ EnclosingBall<Sphere2D, S2Point> cap = octant.getEnclosingCap();
+ Assert.assertEquals(0.0,
octant.getBarycenter().distance(cap.getCenter()), 1.0e-10);
+ Assert.assertEquals(FastMath.acos(1.0 / FastMath.sqrt(3)),
cap.getRadius(), 1.0e-10);
+
+ EnclosingBall<Sphere2D, S2Point> reversedCap =
+ ((SphericalPolygonsSet)
factory.getComplement(octant)).getEnclosingCap();
+ Assert.assertEquals(0, reversedCap.getCenter().distance(new
S2Point(new Vector3D(-1, -1, -1))), 1.0e-10);
+ Assert.assertEquals(FastMath.PI - FastMath.asin(1.0 /
FastMath.sqrt(3)), reversedCap.getRadius(), 1.0e-10);
+
}
@Test
@@ -393,6 +432,7 @@ public class SphericalPolygonsSetTest {
Assert.assertEquals(+0.027, concentric.projectToBoundary(new S2Point(
1.67, phi)).getOffset(), 0.01);
Assert.assertEquals(-0.044, concentric.projectToBoundary(new S2Point(
1.79, phi)).getOffset(), 0.01);
Assert.assertEquals(+0.201, concentric.projectToBoundary(new S2Point(
2.16, phi)).getOffset(), 0.01);
+
}
private SubCircle create(Vector3D pole, Vector3D x, Vector3D y,
