sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject [sis] 01/03: Store isoline coordinates as single-precision floating point numbers, but with a translation for attenuating the precision lost.
Date Thu, 31 Dec 2020 16:17:23 GMT
This is an automated email from the ASF dual-hosted git repository.

desruisseaux pushed a commit to branch geoapi-4.0
in repository https://gitbox.apache.org/repos/asf/sis.git

commit c1278109fc735f18c9e29cc424172cf48c32b520
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Thu Dec 31 12:43:20 2020 +0100

    Store isoline coordinates as single-precision floating point numbers, but with a translation
for attenuating the precision lost.
---
 .../sis/internal/feature/j2d/PathBuilder.java      |   3 +-
 .../apache/sis/internal/feature/j2d/Polygon.java   |   9 +-
 .../apache/sis/internal/feature/j2d/Polyline.java  | 111 ++++++++++++++++-----
 .../sis/internal/feature/j2d/FlatShapeTest.java    |   6 +-
 .../internal/processing/image/IsolinesTest.java    |   7 +-
 5 files changed, 99 insertions(+), 37 deletions(-)

diff --git a/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/PathBuilder.java
b/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/PathBuilder.java
index 129649b..830509c 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/PathBuilder.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/PathBuilder.java
@@ -211,8 +211,7 @@ public class PathBuilder {
                 if (y > ymax) ymax = y;
             }
             final IntervalRectangle bounds = new IntervalRectangle(xmin, ymin, xmax, ymax);
-            final double[] points = Arrays.copyOf(coordinates, size);
-            polylines.add(close ? new Polygon(bounds, points) : new Polyline(bounds, points));
+            polylines.add(close ? new Polygon(bounds, coordinates, size) : new Polyline(bounds,
coordinates, size));
         }
         size = 0;
     }
diff --git a/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/Polygon.java
b/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/Polygon.java
index eb5f633..ad8e022 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/Polygon.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/Polygon.java
@@ -30,12 +30,13 @@ import org.apache.sis.internal.referencing.j2d.IntervalRectangle;
 final class Polygon extends Polyline {
     /**
      * Creates a new polygon with the given coordinates.
-     * The given arguments are stored by reference; they are not cloned.
+     * The {@code coordinates} array shall not be empty.
      *
      * @param  bounds       the polygon bounds (not cloned).
-     * @param  coordinates  the coordinate values as (x,y) tuples (not cloned).
+     * @param  coordinates  the coordinate values as (x,y) tuples.
+     * @param  size         number of valid value in {@code coordinates} array.
      */
-    Polygon(final IntervalRectangle bounds, final double[] coordinates) {
-        super(bounds, coordinates);
+    Polygon(final IntervalRectangle bounds, final double[] coordinates, final int size) {
+        super(bounds, coordinates, size);
     }
 }
diff --git a/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/Polyline.java
b/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/Polyline.java
index c34cc7e..2f22b14 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/Polyline.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/internal/feature/j2d/Polyline.java
@@ -34,10 +34,30 @@ import org.apache.sis.internal.referencing.j2d.IntervalRectangle;
  *   <li>Line segments only (no Bézier curves).</li>
  *   <li>No multi-polylines (e.g. no "move to" operation in the middle).</li>
  *   <li>Naive {@code intersect(…)} and {@code contains(…)} methods.</li>
+ *   <li>Coordinates "compressed" (with a simple translation) as {@code float}.</li>
  * </ul>
  *
  * The {@code intersect(…)} and {@code contains(…)} methods may be improved in a future
version.
  *
+ * <h2>Precision and pseudo-compression</h2>
+ * Coordinates are stored with {@code float} precision for reducing memory usage with large
polylines.
+ * This is okay if coordinates are approximate anyway, for example if they are values interpolated
by
+ * the {@code Isolines} class. For attenuating the precision lost, coordinate values are
converted by
+ * applications of the two following steps:
+ *
+ * <ol class="verbose">
+ *   <li>First, translate coordinates toward zero. For example latitude or longitude
values in the
+ *       [50 … 60]° range have a precision of about 4E-6° (about 0.4 meter). But translating
those
+ *       coordinates to the [-5 … 5]° range increases their precision to 0.05 meter. The
precision
+ *       gain is more important when the original coordinates are projected coordinates with
high
+ *       "false easting" / "false northing" parameters.</li>
+ *   <li>Next, if minimum or maximum coordinate values are outside the range allowed
by {@code float}
+ *       exponent values, multiply coordinates by a power of 2 (<strong>Not yet implemented)</strong>.
+ *       Note that precision gain happens only when values are made closer to zero by a translation.
+ *       Making coordinates closer to zero by a multiplication has no effect on the precision.
+ *       This step is required only for avoiding overflow or underflow.</li>
+ * </ol>
+ *
  * @author  Martin Desruisseaux (Geomatys)
  * @version 1.1
  * @since   1.1
@@ -45,22 +65,42 @@ import org.apache.sis.internal.referencing.j2d.IntervalRectangle;
  */
 class Polyline extends FlatShape {
     /**
-     * The coordinate values as (x,y) tuples.
+     * The "compressed" coordinate values as (x,y) tuples. To get the desired coordinates,
+     * those values must be converted by the {@link #inflate} transform.
+     */
+    private final float[] coordinates;
+
+    /**
+     * The transform from {@link #coordinates} values to the values given by {@link Iter}.
+     * This transform is usually only a translation.
      */
-    private final double[] coordinates;
+    private final AffineTransform inflate;
 
     /**
      * Creates a new polylines with the given coordinates.
-     * The given arguments are stored by reference; they are not cloned.
-     * The array shall not be empty.
+     * The {@code coordinates} array shall not be empty.
      *
      * @param  bounds       the polyline bounds (not cloned).
-     * @param  coordinates  the coordinate values as (x,y) tuples (not cloned).
+     * @param  coordinates  the coordinate values as (x,y) tuples.
+     * @param  size         number of valid value in {@code coordinates} array.
      */
-    Polyline(final IntervalRectangle bounds, final double[] coordinates) {
+    Polyline(final IntervalRectangle bounds, final double[] coordinates, final int size)
{
         super(bounds);
-        assert coordinates.length != 0;         // Required by our PathIterator.
-        this.coordinates = coordinates;
+        assert size >= 2 : size;                // Required by our PathIterator.
+        this.coordinates = new float[size];
+        final double tx = round(bounds.getCenterX(), bounds.xmin, bounds.xmax);
+        final double ty = round(bounds.getCenterY(), bounds.ymin, bounds.ymax);
+        inflate = AffineTransform.getTranslateInstance(tx, ty);
+        AffineTransform.getTranslateInstance(-tx, -ty).transform(coordinates, 0, this.coordinates,
0, size / 2);
+    }
+
+    /**
+     * Rounds the translation to an arbitrary number of bits (currently 8).
+     * The intent is to avoid that zero values become something like 1E-9.
+     */
+    private static double round(final double center, final double min, final double max)
{
+        final int e = Math.getExponent(Math.max(Math.abs(min), Math.abs(max))) - 8;
+        return Math.scalb(Math.round(Math.scalb(center, -e)), e);
     }
 
     /**
@@ -87,9 +127,15 @@ class Polyline extends FlatShape {
      */
     static final class Iter implements PathIterator {
         /**
-         * The transform to apply on each coordinate tuple.
+         * The user-specified transform, or {@code null} if none.
          */
-        private final AffineTransform at;
+        private final AffineTransform toUserSpace;
+
+        /**
+         * The transform to apply on each coordinate tuple. This is the concatenation of
user-specified
+         * transform with {@link Polyline#inflate}. Shall not be null, unless the iterator
is empty.
+         */
+        private AffineTransform inflate;
 
         /**
          * Next polylines on which to iterate, or an empty iterator if none.
@@ -97,9 +143,9 @@ class Polyline extends FlatShape {
         private final Iterator<Polyline> polylines;
 
         /**
-         * Coordinates to return in calls to {@link #currentSegment(double[])}.
+         * Coordinates to return (after conversion by {@link #inflate}) in calls to {@link
#currentSegment(double[])}.
          */
-        private double[] coordinates;
+        private float[] coordinates;
 
         /**
          * Current position in {@link #coordinates} array.
@@ -126,9 +172,9 @@ class Polyline extends FlatShape {
          * Creates an empty iterator.
          */
         Iter() {
-            at        = null;
-            polylines = null;
-            isDone    = true;
+            toUserSpace = null;
+            polylines   = null;
+            isDone      = true;
         }
 
         /**
@@ -139,10 +185,27 @@ class Polyline extends FlatShape {
          * @param  next   all other polylines or polygons.
          */
         Iter(final AffineTransform at, final Polyline first, final Iterator<Polyline>
next) {
-            this.at     = (at != null) ? at : new AffineTransform();
-            polylines   = next;
-            coordinates = first.coordinates;
-            isPolygon   = (first instanceof Polygon);
+            if (at != null) {
+                inflate = new AffineTransform();
+            }
+            toUserSpace = at;
+            polylines = next;
+            setSource(first);
+        }
+
+        /**
+         * Initializes the {@link #coordinates}, {@link #isPolygon} and {@link #inflate}
fields
+         * for iteration over coordinate values given by the specified polyline.
+         */
+        private void setSource(final Polyline polyline) {
+            isPolygon = (polyline instanceof Polygon);
+            coordinates = polyline.coordinates;
+            if (toUserSpace != null) {
+                inflate.setTransform(toUserSpace);
+                inflate.concatenate(polyline.inflate);
+            } else {
+                inflate = polyline.inflate;
+            }
         }
 
         /**
@@ -172,10 +235,8 @@ class Polyline extends FlatShape {
                     if (closing) return;
                 }
                 if (polylines.hasNext()) {
-                    final Polyline next = polylines.next();
-                    isPolygon   = (next instanceof Polygon);
-                    coordinates = next.coordinates;
-                    position    = 0;
+                    setSource(polylines.next());
+                    position = 0;
                 } else {
                     isDone = true;
                 }
@@ -188,7 +249,7 @@ class Polyline extends FlatShape {
         @Override
         public int currentSegment(final float[] coords) {
             if (closing) return SEG_CLOSE;
-            at.transform(coordinates, position, coords, 0, 1);
+            inflate.transform(coordinates, position, coords, 0, 1);
             return (position == 0) ? SEG_MOVETO : SEG_LINETO;
         }
 
@@ -198,7 +259,7 @@ class Polyline extends FlatShape {
         @Override
         public int currentSegment(final double[] coords) {
             if (closing) return SEG_CLOSE;
-            at.transform(coordinates, position, coords, 0, 1);
+            inflate.transform(coordinates, position, coords, 0, 1);
             return (position == 0) ? SEG_MOVETO : SEG_LINETO;
         }
     }
diff --git a/core/sis-feature/src/test/java/org/apache/sis/internal/feature/j2d/FlatShapeTest.java
b/core/sis-feature/src/test/java/org/apache/sis/internal/feature/j2d/FlatShapeTest.java
index 84f3ebc..88b1550 100644
--- a/core/sis-feature/src/test/java/org/apache/sis/internal/feature/j2d/FlatShapeTest.java
+++ b/core/sis-feature/src/test/java/org/apache/sis/internal/feature/j2d/FlatShapeTest.java
@@ -58,8 +58,8 @@ public final strictfp class FlatShapeTest extends TestCase {
             4,5, 6,3, 8,5, -2,5, 10,4
         };
         final IntervalRectangle bounds = new IntervalRectangle(-2,3, 19,5);
-        final Polyline p = closed ? new Polygon (bounds, coordinates)
-                                  : new Polyline(bounds, coordinates);
+        final Polyline p = closed ? new Polygon (bounds, coordinates, coordinates.length)
+                                  : new Polyline(bounds, coordinates, coordinates.length);
 
         final Path2D.Double r = new Path2D.Double(Path2D.WIND_NON_ZERO);
         createReferenceShape(r, coordinates, closed);
@@ -100,7 +100,7 @@ public final strictfp class FlatShapeTest extends TestCase {
         final Polyline[] polylines = new Polyline[coordinates.length];
         final Path2D.Double r = new Path2D.Double(Path2D.WIND_NON_ZERO);
         for (int i=0; i < polylines.length; i++) {
-            polylines[i] = new Polyline(bounds, coordinates[i]);
+            polylines[i] = new Polyline(bounds, coordinates[i], coordinates[i].length);
             createReferenceShape(r, coordinates[i], false);
         }
         final MultiPolylines p = new MultiPolylines(polylines);
diff --git a/core/sis-feature/src/test/java/org/apache/sis/internal/processing/image/IsolinesTest.java
b/core/sis-feature/src/test/java/org/apache/sis/internal/processing/image/IsolinesTest.java
index 85c8a58..8e70e89 100644
--- a/core/sis-feature/src/test/java/org/apache/sis/internal/processing/image/IsolinesTest.java
+++ b/core/sis-feature/src/test/java/org/apache/sis/internal/processing/image/IsolinesTest.java
@@ -41,10 +41,11 @@ import static org.junit.Assert.*;
  */
 public final strictfp class IsolinesTest extends TestCase {
     /**
-     * Tolerance threshold for rounding errors.
-     * Could be zero, but we nevertheless keep a margin for safety.
+     * Tolerance threshold for rounding errors. Needs to take in account that
+     * {@link org.apache.sis.internal.feature.j2d.Polyline} stores coordinate
+     * values a single-precision {@code float} numbers.
      */
-    private static final double TOLERANCE = 1E-14;
+    private static final double TOLERANCE = 1E-8;
 
     /**
      * The threshold value. This is used by {@code generateFromXXX(…)} methods.


Mime
View raw message