sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject [sis] branch geoapi-4.0 updated: Simplify the Bezier cubic curve to quadratic curve or straight line when possible. This is especially important in the case of the straight line for avoiding a division by zero.
Date Mon, 13 May 2019 19:21:39 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


The following commit(s) were added to refs/heads/geoapi-4.0 by this push:
     new a585d7f  Simplify the Bezier cubic curve to quadratic curve or straight line when
possible. This is especially important in the case of the straight line for avoiding a division
by zero.
a585d7f is described below

commit a585d7f97de7f4c9826ecc356da15764c43056d4
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Mon May 13 21:20:42 2019 +0200

    Simplify the Bezier cubic curve to quadratic curve or straight line when possible.
    This is especially important in the case of the straight line for avoiding a division
by zero.
---
 .../org/apache/sis/distance/DistanceUtils.java     |  1 +
 .../java/org/apache/sis/geometry/Shapes2D.java     |  8 +-
 .../internal/referencing/j2d/ShapeUtilities.java   | 86 ++++++++++++++++++----
 .../referencing/j2d/ShapeUtilitiesTest.java        | 46 +++++++++++-
 .../referencing/j2d/ShapeUtilitiesViewer.java      |  2 +-
 .../sis/referencing/GeodeticCalculatorTest.java    |  6 +-
 6 files changed, 126 insertions(+), 23 deletions(-)

diff --git a/core/sis-referencing/src/main/java/org/apache/sis/distance/DistanceUtils.java
b/core/sis-referencing/src/main/java/org/apache/sis/distance/DistanceUtils.java
index 4bd20f0..4037eeb 100644
--- a/core/sis-referencing/src/main/java/org/apache/sis/distance/DistanceUtils.java
+++ b/core/sis-referencing/src/main/java/org/apache/sis/distance/DistanceUtils.java
@@ -23,6 +23,7 @@ import org.apache.sis.geometry.DirectPosition2D;
  * similar to Apache SIS but refractor to allow use of custom classes.
  *
  * @deprecated Replaced by {@link org.apache.sis.referencing.GeodeticCalculator}.
+ * See <a href="https://issues.apache.org/jira/browse/SIS-385">SIS-385</a>.
  */
 @Deprecated
 public final class DistanceUtils {
diff --git a/core/sis-referencing/src/main/java/org/apache/sis/geometry/Shapes2D.java b/core/sis-referencing/src/main/java/org/apache/sis/geometry/Shapes2D.java
index 579e00a..0f799de 100644
--- a/core/sis-referencing/src/main/java/org/apache/sis/geometry/Shapes2D.java
+++ b/core/sis-referencing/src/main/java/org/apache/sis/geometry/Shapes2D.java
@@ -17,11 +17,11 @@
 package org.apache.sis.geometry;
 
 import java.util.Set;
+import java.awt.Shape;
 import java.awt.geom.Point2D;
 import java.awt.geom.Line2D;
 import java.awt.geom.Ellipse2D;
 import java.awt.geom.Rectangle2D;
-import java.awt.geom.CubicCurve2D;
 import java.awt.geom.AffineTransform;
 import org.opengis.geometry.MismatchedDimensionException;
 import org.opengis.referencing.cs.CoordinateSystem;
@@ -167,12 +167,14 @@ public final class Shapes2D extends Static {
      * @param  P2  the end point (<var>t</var> = 1).
      * @param  α1  the derivative (∂y/∂x) at starting point.
      * @param  α2  the derivative (∂y/∂x) at ending point.
+     * @param  εx  maximal distance on <var>x</var> axis between the cubic Bézier
curve and quadratic or linear simplifications.
+     * @param  εy  maximal distance on <var>y</var> axis between the cubic Bézier
curve and quadratic or linear simplifications.
      * @return the Bézier curve passing by the 3 given points and having the given derivatives
at end points.
      *
      * @since 1.0
      */
-    public static CubicCurve2D fitCubicCurve(Point2D P1, Point2D Pm, Point2D P2, double α1,
double α2) {
-        return ShapeUtilities.fitCubicCurve(P1.getX(), P1.getY(), Pm.getX(), Pm.getY(), P2.getX(),
P2.getY(), α1, α2);
+    public static Shape fitCubicCurve(Point2D P1, Point2D Pm, Point2D P2, double α1, double
α2, double εx, double εy) {
+        return ShapeUtilities.fitCubicCurve(P1.getX(), P1.getY(), Pm.getX(), Pm.getY(), P2.getX(),
P2.getY(), α1, α2, εx, εy);
     }
 
     /**
diff --git a/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java
b/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java
index 5d986fe..0a8a4d8 100644
--- a/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java
+++ b/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java
@@ -25,7 +25,10 @@ import java.awt.geom.CubicCurve2D;
 import java.awt.geom.PathIterator;
 import org.apache.sis.util.Static;
 
-import static java.lang.Math.*;
+import static java.lang.Math.abs;
+import static java.lang.Math.sqrt;
+import static java.lang.Math.hypot;
+import static java.lang.Double.isInfinite;
 
 
 /**
@@ -123,10 +126,10 @@ public final class ShapeUtilities extends Static {
                                                             double x,        double y)
     {
         final double slope = (y2-y1) / (x2-x1);
-        if (!Double.isInfinite(slope)) {
-            final double y0 = (y2 - slope*x2);
-            x = ((y - y0) * slope + x) / (slope*slope + 1);
-            y = x*slope + y0;
+        if (!isInfinite(slope)) {
+            final double yx0 = (y2 - slope*x2);                     // Value of y at x=0.
+            x = ((y - yx0) * slope + x) / (slope*slope + 1);
+            y = yx0 + x*slope;
         } else {
             x = x2;
         }
@@ -244,7 +247,7 @@ public final class ShapeUtilities extends Static {
      *
      * <ul>
      *   <li>A value of {@code true} means that the <var>x</var> axis must
be horizontal. The quadratic curve
-     *       will then look like an ordinary parabolic curve as we see in mathematic school
book.</li>
+     *       will then looks like an ordinary parabolic curve as we see in mathematic school
book.</li>
      *   <li>A value of {@code false} means that the <var>x</var> axis
must be parallel to the
      *       line segment joining the {@code P0} and {@code P2} ending points.</li>
      * </ul>
@@ -374,16 +377,47 @@ public final class ShapeUtilities extends Static {
      * @param  y2  <var>y</var> value of the ending point.
      * @param  α1  the derivative (∂y/∂x) at starting point.
      * @param  α2  the derivative (∂y/∂x) at ending point.
+     * @param  εx  maximal distance on <var>x</var> axis between the cubic Bézier
curve and quadratic or linear simplifications.
+     * @param  εy  maximal distance on <var>y</var> axis between the cubic Bézier
curve and quadratic or linear simplifications.
      * @return the Bézier curve passing by the 3 given points and having the given derivatives
at end points.
      *
+     * @see <a href="https://pomax.github.io/bezierinfo/">A Primer on Bézier Curves</a>
+     *
      * @since 1.0
      */
-    public static CubicCurve2D.Double fitCubicCurve(final double x1, final double y1,
-                                                          double xm,       double ym,
-                                                    final double x2, final double y2,
-                                                    final double α1, final double α2)
+    public static Shape fitCubicCurve(final double x1, final double y1,
+                                            double xm,       double ym,
+                                      final double x2, final double y2,
+                                      final double α1, final double α2,
+                                      final double εx, final double εy)
     {
         /*
+         * Equations in this method are simplified as if (x1,y1) coordinates are (0,0).
+         * Adjust (xm,ym) and (x2,y2) consequently. If derivatives are equal, equation
+         * for cubic curve will not work (division by zero). But we can return a line
+         * instead if derivatives are equal to Δy/Δx slope and mid-point is colinear.
+         */
+        xm -= x1;
+        ym -= y1;
+        final double Δx = x2 - x1;
+        final double Δy = y2 - y1;
+        if ((isInfinite(α1) || abs(Δx*α1 - Δy) <= εy) &&
+            (isInfinite(α2) || abs(Δx*α2 - Δy) <= εy))
+        {
+            /*
+             * Following tests are partially redundant with above tests, but may detect a
larger
+             * error than above tests did. They are also necessary is a derivative was infinite.
+             */
+            if ((α1 == 0 || abs(Δy/α1 - Δx) <= εx) &&
+                (α2 == 0 || abs(Δy/α2 - Δx) <= εx))
+            {
+                final double slope = Δy / Δx;
+                if (abs(xm*slope - ym) <= εy && abs(ym/slope - xm) <= εx)
{
+                    return new Line2D.Double(x1, y1, x2, y2);
+                }
+            }
+        }
+        /*
          * Bezier curve equation for starting point P₀, ending point P₃ and control points
P₁ and P₂
          * (note: not the same numbers than the ones in arguments and variables used in this
method):
          *
@@ -419,15 +453,37 @@ public final class ShapeUtilities extends Static {
          * x₀ and x₃ are named x1 and x2 for consistency with Java2D usage.
          * Same changes apply to y.
          */
-        xm -= x1;
-        ym -= y1;
-        final double Δx  = x2 - x1;
-        final double Δy  = y2 - y1;
         final double cx1 = ((8*xm - 4*Δx)*α2 - (8*ym - 4*Δy)) / (3*(α2 - α1));
         final double cy1 = cx1 * α1;
         final double cx2 = (8*xm - Δx)/3 - cx1;
         final double cy2 = Δy - (Δx - cx2)*α2;
-        return new CubicCurve2D.Double(x1, y1, cx1 + x1, cy1 + y1, cx2 + x1, cy2 + y1, x2,
y2);
+        /*
+         * At this point we got the control points (cx1,cy1) and (cx2,cy2). Verify if we
can simplify
+         * cubic curbe to a quadratic curve. If we were elevating the degree from quadratic
to cubic,
+         * the control points C₁ and C₂ would be: (Q is the control point of the quadratic
curve)
+         *
+         *     C₁  =  ⅓P₁ + ⅔Q
+         *     C₂  =  ⅓P₂ + ⅔Q
+         *
+         * We want Q instead, which can be computed in two ways:
+         *
+         *     Q   =  (3C₁ - P₁)/2
+         *     Q   =  (3C₂ - P₂)/2
+         *
+         * We compute Q both ways and check if they are close enough to each other:
+         *
+         *     ΔQ  =  (3⋅(C₂ - C₁) - (P₂ - P₁))/2
+         */
+        final double Δqx = (3*(cx2 - cx1) - Δx)/2;          // P₁ set to zero.
+        if (abs(Δqx) <= εx) {
+            final double Δqy = (3*(cy2 - cy1) - Δy)/2;
+            if (abs(Δqy) <= εy) {
+                final double qx = (3*cx1 + Δqx)/2;          // Take average of 2 control
points.
+                final double qy = (3*cy1 + Δqy)/2;
+                return new QuadCurve2D.Double(x1, y1, qx+x1, qy+y1, x2, y2);
+            }
+        }
+        return new CubicCurve2D.Double(x1, y1, cx1+x1, cy1+y1, cx2+x1, cy2+y1, x2, y2);
     }
 
     /**
diff --git a/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
b/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
index 2ad6a40..e949b49 100644
--- a/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
+++ b/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
@@ -142,7 +142,7 @@ public final strictfp class ShapeUtilitiesTest extends TestCase {
                                                final double x2,  final double y2,
                                                final double α1,  final double α2)
     {
-        final CubicCurve2D p = ShapeUtilities.fitCubicCurve(x1, y1, xm, ym, x2, y2, α1,
α2);
+        final CubicCurve2D p = (CubicCurve2D) ShapeUtilities.fitCubicCurve(x1, y1, xm, ym,
x2, y2, α1, α2, 1, 1);
         assertPointEquals( x1,  y1, p.getP1());
         assertPointEquals( x2,  y2, p.getP2());
         assertPointEquals(cx1, cy1, p.getCtrlP1());
@@ -150,13 +150,53 @@ public final strictfp class ShapeUtilitiesTest extends TestCase {
     }
 
     /**
-     * Tests {@link ShapeUtilities#fitCubicCurve(double, double, double, double, double,
double, double, double)}.
+     * Tests {@link ShapeUtilities#fitCubicCurve(double, double, double, double, double,
double, double, double, double, double)}.
      * This is an anti-regression test with values computed by {@link ShapeUtilitiesViewer}.
      */
     @Test
     public void testFitCubicCurve() {
+        /*
+         * Case when the curve can be simplified to a straight line.
+         * This test uses a line starting from (100,200) with a slope of 1.3333…
+         */
+        final Line2D c1 = (Line2D) ShapeUtilities.fitCubicCurve(
+                100, 200,                           // Start point:  P1
+                175, 300,                           // Midle point:  Pm = P1 + (75,100)
+                250, 400,                           // End point:    P2 = Pm + (75,100)
+                100./75, 100./75,                   // Slope
+                1, 1);                              // Tolerance
+        assertPointEquals(100, 200, c1.getP1());
+        assertPointEquals(250, 400, c1.getP2());
+        /*
+         * Case when the curve can be simplified to a quadratic curve. First we build a quadratic
curve at points
+         *
+         *     P₁=(100,200), Q=(400.0, 300), P₂=(550,600)   where    Q is the control
point (not the midway point).
+         *                  Pm=(362.5, 350)                 where   Pm is the midway point
B(½) = ¼P₁ + ½Q + ¼P₂
+         *
+         * Derivatives are:
+         *
+         *     α₁  =  2(Q - P₁)  =  (600, 200)  = 1/3
+         *     α₂  =  2(P₂ - Q)  =  (300, 600)  = 2
+         *
+         * The control point of a cubic curve are below (can be verified in the debugger):
+         *
+         *     C₁  =  ⅓P₁ + ⅔Q  = (300, 266.666…)
+         *     C₂  =  ⅓P₂ + ⅔Q  = (450, 400.0)
+         */
+        final QuadCurve2D c2 = (QuadCurve2D) ShapeUtilities.fitCubicCurve(
+                100,   200,                         // Start point
+                362.5, 350,                         // Midway point
+                550,   600,                         // End point
+                1./3,    2,                         // Derivatives
+                  1,     1);                        // Tolerance
+        assertPointEquals(100, 200, c2.getP1());
+        assertPointEquals(550, 600, c2.getP2());
+        assertPointEquals(400, 300, c2.getCtrlPt());
+        /*
+         * Cubic case (empirical values from ShapeUtilitiesViewer).
+         */
         assertCubicCurveEquals(886.54566341452,   354.9913859188133,
-                               635.1210032521466, 438.6752807478533,      // Expected control
points.
+                               635.1210032521466, 438.6752807478533,                    
   // Expected control points.
                                1143, 62, 739, 345, 204, 317, -1.14247, 0.282230);
     }
 
diff --git a/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesViewer.java
b/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesViewer.java
index 568f4b5..c11fd5d 100644
--- a/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesViewer.java
+++ b/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesViewer.java
@@ -189,7 +189,7 @@ final strictfp class ShapeUtilitiesViewer extends JPanel {
                 input.moveTo(x1, y1);
                 input.lineTo(x4, y4);
                 input.lineTo(x3, y3);
-                output.append(ShapeUtilities.fitCubicCurve(x1, y1, x2, y2, x3, y3, α1, α2),
false);
+                output.append(ShapeUtilities.fitCubicCurve(x1, y1, x2, y2, x3, y3, α1, α2,
1, 1), false);
                 out.printf(Locale.ENGLISH, "fitCubicCurve(%d, %d, %d, %d, %d, %d, %g, %g)%n",
x1, y1, x2, y2, x3, y3, α1, α2);
                 fillOutput = false;
                 fillInput = false;
diff --git a/core/sis-referencing/src/test/java/org/apache/sis/referencing/GeodeticCalculatorTest.java
b/core/sis-referencing/src/test/java/org/apache/sis/referencing/GeodeticCalculatorTest.java
index 5163e71..9c31de6 100644
--- a/core/sis-referencing/src/test/java/org/apache/sis/referencing/GeodeticCalculatorTest.java
+++ b/core/sis-referencing/src/test/java/org/apache/sis/referencing/GeodeticCalculatorTest.java
@@ -16,12 +16,14 @@
  */
 package org.apache.sis.referencing;
 
+import java.util.Random;
 import org.opengis.geometry.DirectPosition;
 import org.opengis.referencing.operation.TransformException;
 import org.apache.sis.internal.referencing.Formulas;
 import org.apache.sis.geometry.DirectPosition2D;
 import org.apache.sis.measure.Units;
 import org.apache.sis.test.DependsOnMethod;
+import org.apache.sis.test.TestUtilities;
 import org.apache.sis.test.TestCase;
 import org.junit.Test;
 
@@ -87,10 +89,12 @@ public final strictfp class GeodeticCalculatorTest extends TestCase {
      */
     @Test
     public void testEquator() {
+        final Random random = TestUtilities.createRandomNumberGenerator();
         final GeodeticCalculator c = create();
         final double r = c.ellipsoid.getSemiMajorAxis() * (PI / 180);
         c.setStartPoint(0, 0);
-        for (double x=170; x<=180; x+=0.125) {
+        for (double i=0; i<100; i++) {
+            final double x = 180 * random.nextDouble();
             c.setEndPoint(0, x);
             assertEquals(x * r, c.getGeodesicDistance(), Formulas.LINEAR_TOLERANCE);
         }


Mime
View raw message