You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by de...@apache.org on 2013/10/25 15:52:20 UTC
svn commit: r1535734 - in /sis/branches/JDK7/core/sis-metadata/src:
main/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBox.java
test/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBoxTest.java
Author: desruisseaux
Date: Fri Oct 25 13:52:19 2013
New Revision: 1535734
URL: http://svn.apache.org/r1535734
Log:
DefaultGeographicBoundingBox.add now support anti-meridian spanning (SIS-143).
Modified:
sis/branches/JDK7/core/sis-metadata/src/main/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBox.java
sis/branches/JDK7/core/sis-metadata/src/test/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBoxTest.java
Modified: sis/branches/JDK7/core/sis-metadata/src/main/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBox.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/core/sis-metadata/src/main/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBox.java?rev=1535734&r1=1535733&r2=1535734&view=diff
==============================================================================
--- sis/branches/JDK7/core/sis-metadata/src/main/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBox.java [UTF-8] (original)
+++ sis/branches/JDK7/core/sis-metadata/src/main/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBox.java [UTF-8] Fri Oct 25 13:52:19 2013
@@ -480,54 +480,86 @@ public class DefaultGeographicBoundingBo
setInclusion(box.getInclusion()); // Set only on success.
}
+ /*
+ * IMPLEMENTATION NOTE: For the handling of anti-meridian spanning in union and intersection operations,
+ * this class applies a different strategy than GeneralEnvelope. Instead than trying to work directly with
+ * the ordinate values without adding or removing offset (which may cause rounding errors), we apply a ±360°
+ * shift on longitude values. This simpler strategy is okay here because the range is fixed in the code (not
+ * an arbitrarily high range), and GeographicBoundingBox are approximative by definition anyway.
+ */
+
/**
- * Returns ±1 if the given range of longitudes spans the anti-meridian, or 0 otherwise.
- * If this method returns a non-zero value, then the sign indicates whether the caller
- * should add 360° to {@code λmin} (+1) or subtract 360° to {@code λmax} (-1).
+ * Returns a code telling how to denormalize this box and/or the other box before to compute union or intersection.
+ * This method may also modify the {@link #westBoundLongitude} and {@link #eastBoundLongitude}. The codes are:
+ *
+ * <ul>
+ * <li> 0 : Do nothing - both boxes are normal.</li>
+ * <li> 3 : Do nothing - both boxes are spanning the anti-meridian.</li>
+ * <li>-1 : Caller will need to subtract 360° from {@code λmin}.</li>
+ * <li>+1 : Caller will need to add 360° to {@code λmax}.</li>
+ * <li>-2 : This method has subtracted 360° from {@link #westBoundLongitude}.</li>
+ * <li>+2 : This method has added 360° to {@link #eastBoundLongitude}.</li>
+ * </ul>
*
* @see #normalize()
*/
private int denormalize(final double λmin, final double λmax) {
- if (!(λmin < λmax) || westBoundLongitude > eastBoundLongitude) {
- return 0;
+ final boolean isSpanningAntiMeridian = westBoundLongitude > eastBoundLongitude;
+ if ((λmin > λmax) == isSpanningAntiMeridian) {
+ return isSpanningAntiMeridian ? 3 : 0;
+ }
+ final double left = westBoundLongitude - λmin;
+ final double right = λmax - eastBoundLongitude;
+ if (!isSpanningAntiMeridian) {
+ /*
+ * If we were computing the union between this bounding box and the other box,
+ * by how much the width would be increased on the left side and on the right
+ * side? (ignore negative values for this first part). What we may get:
+ *
+ * (+1) Left side is positive (-1) Right side is positive
+ *
+ * W┌──────────┐ ┌──────────┐E
+ * ──┐ ┌──┼──────────┼── ──┼──────────┼──┐ ┌──
+ * │ │ └──────────┘ └──────────┘ │ │
+ * ──┘ └──────────────── ────────────────┘ └──
+ * λmin λmax
+ *
+ * For each of the above case, if we apply the translation in the opposite way,
+ * the result would be much wort (for each lower rectangle, imagine translating
+ * the longuest part in the opposite direction instead than the shortest one).
+ *
+ * Note that only one of 'left' and 'right' can be positive, otherwise we would
+ * not be in the case where one box is spanning the anti-meridian while the other
+ * box does not.
+ */
+ if (left >= 0) return +1;
+ if (right >= 0) return -1;
+ /*
+ * Both 'left' and 'right' are negative. For each alternatives (translating λmin
+ * or translating λmax), we will choose the one which give the closest result to
+ * a bound of this box:
+ *
+ * W┌──────────┐E Changes in width of the union compared to this box:
+ * ───┐ │ ┌─┼── ∙ if we move λmax to the right: Δ = (λmax + 360) - E
+ * │ └────────┼─┘ ∙ if we move λmin to the left: Δ = W - (λmin + 360)
+ * ───┘ └────
+ * λmax λmin
+ *
+ * We want the smallest option. We get the condition below after cancelation of both "+ 360" terms.
+ */
+ return (left < right) ? -1 : +1;
}
/*
- * If we were computing the union between this bounding box and the other box,
- * by how much the width would be increased on the left side and on the right
- * side? (ignore negative values for this first part). What we may get:
- *
- * (+1) Left side is positive (-1) Right side is positive
- *
- * W┌──────────┐ ┌──────────┐E
- * ──┐ ┌──┼──────────┼── ──┼──────────┼──┐ ┌──
- * │ │ └──────────┘ └──────────┘ │ │
- * ──┘ └──────────────── ────────────────┘ └──
- * λmin λmax
- *
- * For each of the above case, if we apply the translation in the opposite way,
- * the result would be much wort (for each lower rectangle, imagine translating
- * the longuest part in the opposite direction instead than the shortest one).
- *
- * Note that only one of 'left' and 'right' can be positive, otherwise we would
- * not be in the case where one box is spanning the anti-meridian while the other
- * box does not.
+ * Same algorithm than above, but with the sign of 'left' an 'right' inversed.
+ * The "if" statements have been combined for avoiding to repeat the +/- operations.
*/
- final double left = westBoundLongitude - λmin; if (left >= 0) return +1;
- final double right = λmax - eastBoundLongitude; if (right >= 0) return -1;
- /*
- * Both 'left' and 'right' are negative. For each alternatives (translating λmin
- * or translating λmax), we will choose the one which give the closest result to
- * a bound of this box:
- *
- * W┌──────────┐E Changes in width of the union compared to this box:
- * ───┐ │ ┌─┼── ∙ if we move λmax to the right: Δ = (λmax + 360) - E
- * │ └────────┼─┘ ∙ if we move λmin to the left: Δ = W - (λmin + 360)
- * ───┘ └────
- * λmax λmin
- *
- * We want the smallest option, se we get the condition below after cancelation of both "+ 360" terms.
- */
- return (left < right) ? -1 : +1;
+ if (!(left <= 0) && right <= 0 || left > right) {
+ westBoundLongitude -= Longitude.MAX_VALUE - Longitude.MIN_VALUE;
+ return -2;
+ } else {
+ eastBoundLongitude += Longitude.MAX_VALUE - Longitude.MIN_VALUE;
+ return +2;
+ }
}
/**
@@ -541,10 +573,10 @@ public class DefaultGeographicBoundingBo
*/
public void add(final GeographicBoundingBox box) {
checkWritePermission();
- final double λmin = box.getWestBoundLongitude();
- final double λmax = box.getEastBoundLongitude();
- final double φmin = box.getSouthBoundLatitude();
- final double φmax = box.getNorthBoundLatitude();
+ double λmin = box.getWestBoundLongitude();
+ double λmax = box.getEastBoundLongitude();
+ double φmin = box.getSouthBoundLatitude();
+ double φmax = box.getNorthBoundLatitude();
/*
* Reminder: 'inclusion' is a mandatory attribute, so it should never be null for a
* valid metadata object. If the metadata object is invalid, it is better to get a
@@ -552,6 +584,11 @@ public class DefaultGeographicBoundingBo
*/
final boolean i1 = MetadataUtilities.getInclusion(this.getInclusion());
final boolean i2 = MetadataUtilities.getInclusion(box. getInclusion());
+ final int status = denormalize(λmin, λmax);
+ switch (status) {
+ case -1: λmin -= Longitude.MAX_VALUE - Longitude.MIN_VALUE; break;
+ case +1: λmax += Longitude.MAX_VALUE - Longitude.MIN_VALUE; break;
+ }
if (i1 == i2) {
if (λmin < westBoundLongitude) westBoundLongitude = λmin;
if (λmax > eastBoundLongitude) eastBoundLongitude = λmax;
@@ -567,6 +604,12 @@ public class DefaultGeographicBoundingBo
if (φmax < northBoundLatitude) northBoundLatitude = φmax;
}
}
+ if (status == 3) {
+ if (eastBoundLongitude > westBoundLongitude) {
+ westBoundLongitude = Longitude.MIN_VALUE;
+ eastBoundLongitude = Longitude.MAX_VALUE;
+ }
+ }
normalize();
}
Modified: sis/branches/JDK7/core/sis-metadata/src/test/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBoxTest.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/core/sis-metadata/src/test/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBoxTest.java?rev=1535734&r1=1535733&r2=1535734&view=diff
==============================================================================
--- sis/branches/JDK7/core/sis-metadata/src/test/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBoxTest.java [UTF-8] (original)
+++ sis/branches/JDK7/core/sis-metadata/src/test/java/org/apache/sis/metadata/iso/extent/DefaultGeographicBoundingBoxTest.java [UTF-8] Fri Oct 25 13:52:19 2013
@@ -17,6 +17,7 @@
package org.apache.sis.metadata.iso.extent;
import org.opengis.metadata.extent.GeographicBoundingBox;
+import org.apache.sis.test.DependsOnMethod;
import org.apache.sis.test.TestCase;
import org.junit.Test;
@@ -34,18 +35,17 @@ import static org.junit.Assert.*;
public final strictfp class DefaultGeographicBoundingBoxTest extends TestCase {
/**
* Asserts that the given geographic bounding box is strictly equals to the given values.
+ * The {@link GeographicBoundingBox#getInclusion()} is expected to be {@code true}.
*/
- private static void assertBoxEquals(final double westBoundLongitude,
- final double eastBoundLongitude,
- final double southBoundLatitude,
- final double northBoundLatitude,
+ private static void assertBoxEquals(final double λbgn, final double λend,
+ final double φmin, final double φmax,
final GeographicBoundingBox box)
{
assertEquals("inclusion", Boolean.TRUE, box.getInclusion());
- assertEquals("westBoundLongitude", westBoundLongitude, box.getWestBoundLongitude(), 0);
- assertEquals("eastBoundLongitude", eastBoundLongitude, box.getEastBoundLongitude(), 0);
- assertEquals("southBoundLatitude", southBoundLatitude, box.getSouthBoundLatitude(), 0);
- assertEquals("northBoundLatitude", northBoundLatitude, box.getNorthBoundLatitude(), 0);
+ assertEquals("westBoundLongitude", λbgn, box.getWestBoundLongitude(), 0);
+ assertEquals("eastBoundLongitude", λend, box.getEastBoundLongitude(), 0);
+ assertEquals("southBoundLatitude", φmin, box.getSouthBoundLatitude(), 0);
+ assertEquals("northBoundLatitude", φmax, box.getNorthBoundLatitude(), 0);
}
/**
@@ -94,20 +94,146 @@ public final strictfp class DefaultGeogr
/*
* Special care for the ±180° longitude bounds.
*/
- box.setBounds (-180, +20, -8, 2); assertBoxEquals(-180, +20, -8, 2, box); // Already normalized.
- box.setBounds ( +20, +180, -8, 2); assertBoxEquals( +20, +180, -8, 2, box); // Already normalized.
- box.setBounds (+180, +20, -8, 2); assertBoxEquals(-180, +20, -8, 2, box); // Normalize west bound so we don't need to span anti-meridian.
- box.setBounds ( +20, -180, -8, 2); assertBoxEquals( +20, +180, -8, 2, box); // Normalize east bound so we don't need to span anti-meridian.
- box.setBounds (-180, -180, -8, 2); assertBoxEquals(-180, -180, -8, 2, box); // Empty box shall stay empty.
- box.setBounds (+180, +180, -8, 2); assertBoxEquals(-180, -180, -8, 2, box); // Empty box shall stay empty.
+ box.setBounds(-180, +20, -8, 2); assertBoxEquals(-180, +20, -8, 2, box); // Already normalized.
+ box.setBounds( +20, +180, -8, 2); assertBoxEquals( +20, +180, -8, 2, box); // Already normalized.
+ box.setBounds(+180, +20, -8, 2); assertBoxEquals(-180, +20, -8, 2, box); // Normalize west bound so we don't need to span anti-meridian.
+ box.setBounds( +20, -180, -8, 2); assertBoxEquals( +20, +180, -8, 2, box); // Normalize east bound so we don't need to span anti-meridian.
+ box.setBounds(-180, -180, -8, 2); assertBoxEquals(-180, -180, -8, 2, box); // Empty box shall stay empty.
+ box.setBounds(+180, +180, -8, 2); assertBoxEquals(-180, -180, -8, 2, box); // Empty box shall stay empty.
/*
* Special care for the ±0° longitude bounds.
*/
- box.setBounds (+0.0, +0.0, -8, 2); assertBoxEquals(+0.0, +0.0, -8, 2, box);
- box.setBounds (-0.0, +0.0, -8, 2); assertBoxEquals(-0.0, +0.0, -8, 2, box);
- box.setBounds (-0.0, -0.0, -8, 2); assertBoxEquals(-0.0, -0.0, -8, 2, box);
- box.setBounds (+0.0, -0.0, -8, 2); assertBoxEquals(-180, +180, -8, 2, box);
+ box.setBounds(+0.0, +0.0, -8, 2); assertBoxEquals(+0.0, +0.0, -8, 2, box);
+ box.setBounds(-0.0, +0.0, -8, 2); assertBoxEquals(-0.0, +0.0, -8, 2, box);
+ box.setBounds(-0.0, -0.0, -8, 2); assertBoxEquals(-0.0, -0.0, -8, 2, box);
+ box.setBounds(+0.0, -0.0, -8, 2); assertBoxEquals(-180, +180, -8, 2, box);
}
+ /**
+ * Sets the given box to the given values, and verifies if the box spans or not the anti-meridian as expected.
+ * This is a convenience method for the {@link #testAdd()} and {@link #testIntersect()} methods for checking
+ * that we are really testing the case that we intended to test.
+ *
+ * @param isSpanningAntiMeridian {@code true} if the box shall spans the anti-meridian.
+ * @param box The box to set. Previous values will be overwritten.
+ */
+ private static void setBounds(final boolean isSpanningAntiMeridian,
+ final double λbgn, final double λend,
+ final double φmin, final double φmax,
+ final DefaultGeographicBoundingBox box)
+ {
+ box.setBounds(λbgn, λend, φmin, φmax);
+ assertEquals("isSpanningAntiMeridian", isSpanningAntiMeridian,
+ box.getWestBoundLongitude() > box.getEastBoundLongitude());
+ }
+
+ /**
+ * Flips the given box horizontally. Longitudes are interchanged and their sign reversed.
+ * Union and intersection tests what worked with the given boxes shall work as well with flipped boxes.
+ */
+ private static void flipHorizontally(final DefaultGeographicBoundingBox box) {
+ box.setBounds(-box.getEastBoundLongitude(),
+ -box.getWestBoundLongitude(),
+ box.getSouthBoundLatitude(),
+ box.getNorthBoundLatitude());
+ }
+
+ /**
+ * Tests {@link DefaultGeographicBoundingBox#add(GeographicBoundingBox)}.
+ */
+ @Test
+ @DependsOnMethod("testNormalize")
+ public void testAdd() {
+ /*
+ * Simple cases: no anti-meridian spanning.
+ * ┌─────────────┐ ┌──────────┐
+ * │ ┌───────┐ │ and │ ┌───────┼──┐
+ * │ └───────┘ │ └──┼───────┘ │
+ * └─────────────┘ └──────────┘
+ * -40 30 -40 50
+ */
+ final DefaultGeographicBoundingBox b1 = new DefaultGeographicBoundingBox(-40, 30, -38, 20);
+ final DefaultGeographicBoundingBox b2 = new DefaultGeographicBoundingBox(-20, 10, -30, -25);
+ assertAddEquals( -40, 30, -38, 20, b1, b2);
+ setBounds(false, -30, 50, -42, -20, b2);
+ assertAddEquals( -40, 50, -42, 20, b1, b2);
+ /*
+ * Anti-meridian spanning for only one box.
+ * ──────────┐ ┌───── ─────┐ ┌─────
+ * ┌────┐ │ │ and ┌─┼────┐ │
+ * └────┘ │ │ └─┼────┘ │
+ * ──────────┘ └───── ─────┘ └─────
+ */
+ setBounds(true, 80, -100, -2, 2, b1);
+ setBounds(false, -140, -120, -1, 1, b2);
+ assertAddEquals( 80, -100, -2, 2, b1, b2);
+ setBounds(false, -120, 50, -1, 1, b2);
+ assertAddEquals( 80, 50, -2, 2, b1, b2);
+ /*
+ * To be replaced by the whole world:
+ * ────┐ ┌────
+ * ┌──┼──┼─┐
+ * └──┼──┼─┘
+ * ────┘ └────
+ */
+ setBounds(true, 80, -100, -2, 2, b1);
+ setBounds(false, -120, 90, -1, 1, b2);
+ assertAddEquals( -180, 180, -2, 2, b1, b2);
+ /*
+ * Anti-meridian spanning in both boxes.
+ * The second case shall result in a box spanning the whole world.
+ *
+ * ────┐ ┌──── ────┐ ┌────
+ * ──┐ │ │ ┌── and ────┼──┼─┐┌─
+ * ──┘ │ │ └── ────┼──┼─┘└─
+ * ────┘ └──── ────┘ └────
+ */
+ setBounds(true, 80, -100, -1, 1, b1);
+ setBounds(true, 90, -120, -2, 2, b2);
+ assertAddEquals( 80, -100, -2, 2, b1, b2);
+ setBounds(true, 100, 90, -1, 1, b2);
+ assertAddEquals(-180, 180, -2, 2, b1, b2);
+ }
+ /**
+ * Asserts that the call to {@code b1.add(b2)} and {@code b2.add(b1)} is strictly equals to the given values.
+ * This method tests also with horizontally flipped boxes, and tests with interchanged boxes ({@code b1.add(b2)}).
+ * After this method call, the two boxes are equal to the given values.
+ */
+ private static void assertAddEquals(final double λbgn, final double λend,
+ final double φmin, final double φmax,
+ final DefaultGeographicBoundingBox b1,
+ final DefaultGeographicBoundingBox b2)
+ {
+ final double westBoundLongitude = b1.getWestBoundLongitude();
+ final double eastBoundLongitude = b1.getEastBoundLongitude();
+ final double southBoundLatitude = b1.getSouthBoundLatitude();
+ final double northBoundLatitude = b1.getNorthBoundLatitude();
+ b1.add(b2);
+ assertBoxEquals(λbgn, λend, φmin, φmax, b1);
+ /*
+ * The above tested the boxes as given in argument to this method. Now test again,
+ * but with horizontally flipped boxes - so this is a mirror of above test. A test
+ * failure here would mean that there is some asymmetry in the code.
+ */
+ flipHorizontally(b2);
+ b1.setBounds(-eastBoundLongitude, -westBoundLongitude, southBoundLatitude, northBoundLatitude);
+ b1.add(b2);
+ assertBoxEquals(-λend, -λbgn, φmin, φmax, b1);
+ /*
+ * Reset the boxes to there initial state, then test again with the two boxes interchanged.
+ * The consequence for the implementation is not as smetric than the above test, so there
+ * is more risk of failure here.
+ */
+ flipHorizontally(b2);
+ b1.setBounds(westBoundLongitude, eastBoundLongitude, southBoundLatitude, northBoundLatitude);
+ b2.add(b1);
+ assertBoxEquals(λbgn, λend, φmin, φmax, b2);
+ /*
+ * Following should be equivalent to b1.setBounds(b2), tested opportunistically.
+ */
+ b1.add(b2);
+ assertBoxEquals(λbgn, λend, φmin, φmax, b1);
+ assertEquals(b1, b2);
+ }
}