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 2014/01/01 18:30:34 UTC
svn commit: r1554655 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSet.java
test/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSetTest.java
Author: luc
Date: Wed Jan 1 17:30:34 2014
New Revision: 1554655
URL: http://svn.apache.org/r1554655
Log:
Improved navigation within sub-arcs.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSet.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSetTest.java
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSet.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSet.java?rev=1554655&r1=1554654&r2=1554655&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSet.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSet.java Wed Jan 1 17:30:34 2014
@@ -176,6 +176,19 @@ public class ArcsSet extends AbstractReg
* or null if there are no internal nodes (i.e. the set is either empty or covers the full circle)
*/
public LimitAngle getSmallestLimit() {
+ final BSPTree<Sphere1D> first = getFirstArcStart();
+ if (first == null) {
+ return null;
+ } else {
+ return (LimitAngle) first.getCut().getHyperplane();
+ }
+ }
+
+ /** Get the node corresponding to the first arc start.
+ * @return smallest internal node (i.e. first after 0.0 radians, in trigonometric direction),
+ * or null if there are no internal nodes (i.e. the set is either empty or covers the full circle)
+ */
+ private BSPTree<Sphere1D> getFirstArcStart() {
// start search at the tree root
BSPTree<Sphere1D> node = getTree(false);
@@ -183,35 +196,73 @@ public class ArcsSet extends AbstractReg
return null;
}
+ // walk tree until we find the smallest internal node
BSPTree<Sphere1D> previous = previousNode(node);
while (previous != null) {
node = previous;
previous = previousNode(node);
}
- return (LimitAngle) node.getCut().getHyperplane();
+ // walk tree until we find an arc start
+ while (node != null && !isArcStart(node)) {
+ node = nextNode(node);
+ }
+
+ return node;
}
- /** Get the largest limit angle in the set.
- * @return largest limit angle (i.e. last before or at \(2 \pi) radians, in trigonometric direction),
- * or null if there are no limits (i.e. the set is either empty or covers the full circle)
+ /** Check if a node corresponds to the start angle of an arc.
+ * @param node node to check
+ * @return true if the node corresponds to the start angle of an arc
*/
- public LimitAngle getLargestLimit() {
+ private boolean isArcStart(final BSPTree<Sphere1D> node) {
- // start search at the tree root
- BSPTree<Sphere1D> node = getTree(false);
if (node.getCut() == null) {
- return null;
+ // it's not even a limit angle, it cannot start an arc!
+ return false;
+ }
+
+ if ((Boolean) leafBefore(node).getAttribute()) {
+ // it has an inside cell before it, it may end an arc but not start it
+ return false;
}
- BSPTree<Sphere1D> next = nextNode(node);
- while (next != null) {
- node = next;
- next = nextNode(node);
+ if (!(Boolean) leafAfter(node).getAttribute()) {
+ // it has an outside cell after it, it is a dummy cut away from real arcs
+ return false;
}
- return (LimitAngle) node.getCut().getHyperplane();
+ // the cell defines a limit angle, with an outside before and an inside after
+ // it is the start of an arc
+ return true;
+
+ }
+
+ /** Check if a node corresponds to the end angle of an arc.
+ * @param node node to check
+ * @return true if the node corresponds to the end angle of an arc
+ */
+ private boolean isArcEnd(final BSPTree<Sphere1D> node) {
+
+ if (node.getCut() == null) {
+ // it's not even a limit angle, it cannot start an arc!
+ return false;
+ }
+
+ if (!(Boolean) leafBefore(node).getAttribute()) {
+ // it has an outside cell before it, it may start an arc but not end it
+ return false;
+ }
+
+ if ((Boolean) leafAfter(node).getAttribute()) {
+ // it has an inside cell after it, it is a dummy cut in the middle of an arc
+ return false;
+ }
+
+ // the cell defines a limit angle, with an inside before and an outside after
+ // it is the end of an arc
+ return true;
}
@@ -222,13 +273,9 @@ public class ArcsSet extends AbstractReg
*/
private BSPTree<Sphere1D> nextNode(BSPTree<Sphere1D> node) {
- final BSPTree<Sphere1D> nextDeeper =
- ((LimitAngle) node.getCut().getHyperplane()).isDirect() ?
- node.getPlus() : node.getMinus();
-
- if (nextDeeper.getCut() != null) {
+ if (childAfter(node).getCut() != null) {
// the next node is in the sub-tree
- return findSmallest(nextDeeper);
+ return leafAfter(node).getParent();
}
// there is nothing left deeper in the tree, we backtrack
@@ -246,13 +293,9 @@ public class ArcsSet extends AbstractReg
*/
private BSPTree<Sphere1D> previousNode(BSPTree<Sphere1D> node) {
- final BSPTree<Sphere1D> nextDeeper =
- ((LimitAngle) node.getCut().getHyperplane()).isDirect() ?
- node.getMinus() : node.getPlus();
-
- if (nextDeeper.getCut() != null) {
+ if (childBefore(node).getCut() != null) {
// the next node is in the sub-tree
- return findLargest(nextDeeper);
+ return leafBefore(node).getParent();
}
// there is nothing left deeper in the tree, we backtrack
@@ -263,6 +306,42 @@ public class ArcsSet extends AbstractReg
}
+ /** Find the leaf node just before an internal node.
+ * @param node node at which the sub-tree starts
+ * @return leaf node just before the internal node
+ */
+ private BSPTree<Sphere1D> leafBefore(BSPTree<Sphere1D> node) {
+
+ if (node.getCut() != null) {
+ node = childBefore(node);
+ }
+
+ while (node.getCut() != null) {
+ node = childAfter(node);
+ }
+
+ return node;
+
+ }
+
+ /** Find the leaf node just after an internal node.
+ * @param node node at which the sub-tree starts
+ * @return leaf node just after the internal node
+ */
+ private BSPTree<Sphere1D> leafAfter(BSPTree<Sphere1D> node) {
+
+ if (node.getCut() != null) {
+ node = childAfter(node);
+ }
+
+ while (node.getCut() != null) {
+ node = childBefore(node);
+ }
+
+ return node;
+
+ }
+
/** Check if a node is the child before its parent in trigonometric order.
* @param node child node considered
* @return true is the node has a parent end is before it in trigonometric order
@@ -271,13 +350,8 @@ public class ArcsSet extends AbstractReg
final BSPTree<Sphere1D> parent = node.getParent();
if (parent == null) {
return false;
- }
- if (((LimitAngle) parent.getCut().getHyperplane()).isDirect()) {
- // smaller angles are on minus side, larger angles are on plus side
- return node == parent.getMinus();
} else {
- // smaller angles are on plus side, larger angles are on minus side
- return node == parent.getPlus();
+ return node == childBefore(parent);
}
}
@@ -289,62 +363,37 @@ public class ArcsSet extends AbstractReg
final BSPTree<Sphere1D> parent = node.getParent();
if (parent == null) {
return false;
- }
- if (((LimitAngle) parent.getCut().getHyperplane()).isDirect()) {
- // smaller angles are on minus side, larger angles are on plus side
- return node == parent.getPlus();
} else {
- // smaller angles are on plus side, larger angles are on minus side
- return node == parent.getMinus();
+ return node == childAfter(parent);
}
}
- /** Find the smallest internal node in a sub-tree.
+ /** Find the child node just before an internal node.
* @param node node at which the sub-tree starts
- * @return smallest internal node (in trigonometric order), may be the
- * provided node if no smaller internal node exist
+ * @return child node just before the internal node
*/
- private BSPTree<Sphere1D> findSmallest(BSPTree<Sphere1D> node) {
-
- BSPTree<Sphere1D> internal = null;
-
- while (node.getCut() != null) {
- internal = node;
- if (((LimitAngle) node.getCut().getHyperplane()).isDirect()) {
- // smaller angles are on minus side, larger angles are on plus side
- node = node.getMinus();
- } else {
- // smaller angles are on plus side, larger angles are on minus side
- node = node.getPlus();
- }
+ private BSPTree<Sphere1D> childBefore(BSPTree<Sphere1D> node) {
+ if (((LimitAngle) node.getCut().getHyperplane()).isDirect()) {
+ // smaller angles are on minus side, larger angles are on plus side
+ return node.getMinus();
+ } else {
+ // smaller angles are on plus side, larger angles are on minus side
+ return node.getPlus();
}
-
- return internal;
-
}
- /** Find the largest internal node in a sub-tree.
+ /** Find the child node just after an internal node.
* @param node node at which the sub-tree starts
- * @return largest internal node (in trigonometric order), may be the
- * provided node if no larger internal node exist
+ * @return child node just after the internal node
*/
- private BSPTree<Sphere1D> findLargest(BSPTree<Sphere1D> node) {
-
- BSPTree<Sphere1D> internal = null;
-
- while (node.getCut() != null) {
- internal = node;
- if (((LimitAngle) node.getCut().getHyperplane()).isDirect()) {
- // smaller angles are on minus side, larger angles are on plus side
- node = node.getPlus();
- } else {
- // smaller angles are on plus side, larger angles are on minus side
- node = node.getMinus();
- }
+ private BSPTree<Sphere1D> childAfter(BSPTree<Sphere1D> node) {
+ if (((LimitAngle) node.getCut().getHyperplane()).isDirect()) {
+ // smaller angles are on minus side, larger angles are on plus side
+ return node.getPlus();
+ } else {
+ // smaller angles are on plus side, larger angles are on minus side
+ return node.getMinus();
}
-
- return internal;
-
}
/** {@inheritDoc} */
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSetTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSetTest.java?rev=1554655&r1=1554654&r2=1554655&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSetTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/spherical/oned/ArcsSetTest.java Wed Jan 1 17:30:34 2014
@@ -48,8 +48,6 @@ public class ArcsSetTest {
Assert.assertEquals(5.7, set.asList().get(0).getSup(), 1.0e-10);
Assert.assertEquals(2.3, set.getSmallestLimit().getLocation().getAlpha(), 1.0e-10);
Assert.assertFalse(set.getSmallestLimit().isDirect());
- Assert.assertEquals(5.7, set.getLargestLimit().getLocation().getAlpha(), 1.0e-10);
- Assert.assertTrue(set.getLargestLimit().isDirect());
}
@Test
@@ -66,10 +64,8 @@ public class ArcsSetTest {
Assert.assertEquals(1, set.asList().size());
Assert.assertEquals(5.7, set.asList().get(0).getInf(), 1.0e-10);
Assert.assertEquals(2.3 + MathUtils.TWO_PI, set.asList().get(0).getSup(), 1.0e-10);
- Assert.assertEquals(2.3, set.getSmallestLimit().getLocation().getAlpha(), 1.0e-10);
- Assert.assertTrue(set.getSmallestLimit().isDirect());
- Assert.assertEquals(5.7, set.getLargestLimit().getLocation().getAlpha(), 1.0e-10);
- Assert.assertFalse(set.getLargestLimit().isDirect());
+ Assert.assertEquals(5.7, set.getSmallestLimit().getLocation().getAlpha(), 1.0e-10);
+ Assert.assertFalse(set.getSmallestLimit().isDirect());
}
@Test(expected=NumberIsTooLargeException.class)
@@ -82,7 +78,6 @@ public class ArcsSetTest {
ArcsSet set = new ArcsSet(1.0, 1.0, 1.0e-10);
Assert.assertEquals(1.0e-10, set.getTolerance(), 1.0e-20);
Assert.assertNull(set.getSmallestLimit());
- Assert.assertNull(set.getLargestLimit());
Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new S1Point(9.0)));
for (double alpha = -20.0; alpha <= 20.0; alpha += 0.1) {
Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new S1Point(alpha)));
@@ -98,7 +93,6 @@ public class ArcsSetTest {
ArcsSet set = new ArcsSet(1.0e-10);
Assert.assertEquals(1.0e-10, set.getTolerance(), 1.0e-20);
Assert.assertNull(set.getSmallestLimit());
- Assert.assertNull(set.getLargestLimit());
Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new S1Point(9.0)));
for (double alpha = -20.0; alpha <= 20.0; alpha += 0.1) {
Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new S1Point(alpha)));
@@ -116,7 +110,6 @@ public class ArcsSetTest {
Assert.assertEquals(0.0, empty.getSize(), 1.0e-10);
Assert.assertTrue(empty.asList().isEmpty());
Assert.assertNull(empty.getSmallestLimit());
- Assert.assertNull(empty.getLargestLimit());
}
@Test
@@ -128,7 +121,6 @@ public class ArcsSetTest {
Assert.assertEquals(0.0, tiny.asList().get(0).getInf(), 1.0e-10);
Assert.assertEquals(Precision.SAFE_MIN / 2, tiny.asList().get(0).getSup(), 1.0e-10);
Assert.assertEquals(0.0, tiny.getSmallestLimit().getLocation().getAlpha(), 1.0e-10);
- Assert.assertEquals(Precision.SAFE_MIN / 2, tiny.getLargestLimit().getLocation().getAlpha(), 1.0e-10);
}
@Test
@@ -144,7 +136,6 @@ public class ArcsSetTest {
Assert.assertEquals(MathUtils.TWO_PI, set.asList().get(0).getSup(), 1.0e-10);
Assert.assertEquals(0.0, set.getSmallestLimit().getLocation().getAlpha(), 1.0e-10);
Assert.assertFalse(set.getSmallestLimit().isDirect());
- Assert.assertEquals(0.0, set.getLargestLimit().getLocation().getAlpha(), 1.0e-10);
}
@Test