sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject [sis] 02/02: Add Bézier curve calculation from two end-points, the mid-point and derivatives at end-point. This will be used as an approximation of geodesic path.
Date Sun, 12 May 2019 21:07:18 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 76befaa8c54150a51ebe782a50d0169f3679afcd
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Sun May 12 23:05:11 2019 +0200

    Add Bézier curve calculation from two end-points, the mid-point and derivatives at end-point.
    This will be used as an approximation of geodesic path.
---
 .../java/org/apache/sis/geometry/Shapes2D.java     | 28 +++++++-
 .../internal/referencing/j2d/ShapeUtilities.java   | 75 ++++++++++++++++++++++
 .../referencing/j2d/ShapeUtilitiesTest.java        | 41 +++++++++++-
 .../referencing/j2d/ShapeUtilitiesViewer.java      | 44 ++++++++++---
 4 files changed, 174 insertions(+), 14 deletions(-)

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 6280a06..579e00a 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
@@ -21,6 +21,7 @@ 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;
@@ -50,7 +51,7 @@ import org.apache.sis.util.Static;
  *
  * @author  Martin Desruisseaux (IRD, Geomatys)
  * @author  Johann Sorel (Geomatys)
- * @version 0.8
+ * @version 1.0
  * @since   0.8
  * @module
  */
@@ -150,6 +151,31 @@ public final class Shapes2D extends Static {
     }
 
     /**
+     * Returns a Bézier curve passing by the given points and with the given derivatives
at end points.
+     * The curve equation is:
+     *
+     * <blockquote>B(t) = (1-t)³⋅P₁ + 3(1-t)²t⋅C₁ + 3(1-t)t²⋅C₂ + t³⋅P₂</blockquote>
+     *
+     * where t ∈ [0…1], P₁ and P₂ are start and end point respectively (given in
argument to this method)
+     * and C₁ and C₂ are control points (computed by this method) generally not on the
curve.
+     * The P₁ argument give the point on the curve at <var>t</var>=0.
+     * The P<sub>m</sub> argument give the point on the curve at <var>t</var>=½.
+     * The P₂ argument give the point on the curve at <var>t</var>=1.
+     *
+     * @param  P1  the starting point (<var>t</var> = 0).
+     * @param  Pm  the mid-point (<var>t</var> = ½).
+     * @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.
+     * @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);
+    }
+
+    /**
      * Transforms a rectangular envelope using the given math transform.
      * The transformation is only approximated: the returned envelope may be bigger than
      * necessary, or smaller than required if the bounding box contains a pole.
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 49a1f7b..5d986fe 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
@@ -356,6 +356,81 @@ public final class ShapeUtilities extends Static {
     }
 
     /**
+     * Returns a Bézier curve passing by the given points and with the given derivatives
at end points.
+     * The curve equation is:
+     *
+     * <blockquote>B(t) = (1-t)³⋅P₁ + 3(1-t)²t⋅C₁ + 3(1-t)t²⋅C₂ + t³⋅P₂</blockquote>
+     *
+     * where t ∈ [0…1], P₁ and P₂ are end points of the curve and C₁ and C₂ are
control points generally not on the curve.
+     * The (x₁,y₁) arguments give the coordinates of point P₁ at <var>t</var>=0.
+     * The (x<sub>m</sub>,y<sub>m</sub>) arguments give the coordinates
of the point at <var>t</var>=½.
+     * The (x₂,y₂) arguments give the coordinates of point P₂ at <var>t</var>=1.
+     *
+     * @param  x1  <var>x</var> value of the starting point.
+     * @param  y1  <var>y</var> value of the starting point.
+     * @param  xm  <var>x</var> value of the mid-point.
+     * @param  ym  <var>y</var> value of the mid-point.
+     * @param  x2  <var>x</var> value of the ending point.
+     * @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.
+     * @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.Double fitCubicCurve(final double x1, final double y1,
+                                                          double xm,       double ym,
+                                                    final double x2, final double y2,
+                                                    final double α1, final double α2)
+    {
+        /*
+         * 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):
+         *
+         * t ∈ [0…1]:  B(t)  =  (1-t)³⋅P₀ + 3(1-t)²t⋅P₁ + 3(1-t)t²⋅P₂
+ t³⋅P₃
+         * Midpoint:   B(½)  =  ⅛⋅(P₀ + P₃) + ⅜⋅(P₁ + P₂)
+         *
+         * Notation:   (x₀, y₀)   are coordinates of P₀ (same rule for P₁, P₂,
P₃).
+         *             (xm, ym)   are coordinates of midpoint.
+         *             α₀ and α₃  are derivative (∂y/∂x) at P₀ and P₃ respectively.
+         *
+         * Some relationships:
+         *
+         *     xm = ⅛⋅(x₀ + x₃) + ⅜⋅(x₁ + x₂)
+         *     (y₁ - y₀) / (x₁ - x₀) = α₀
+         *     (y₃ - y₂) / (x₃ - x₂) = α₃
+         *
+         * Setting (x₀,y₀) = (0,0) for simplicity and rearranging above equations:
+         *
+         *     x₁ = (8⋅xm - x₃)/3 - x₂              where    x₂ = x₃ - (y₃
- y₂)/α₃
+         *     x₁ = (8⋅xm - 4⋅x₃)/3 + (y₃ - y₂)/α₃
+         *
+         * Doing similar rearrangement for y:
+         *
+         *     y₂ = (8⋅ym - y₃)/3 - y₁    where    y₁ = x₁⋅α₀
+         *     y₂ = (8⋅ym - y₃)/3 - x₁⋅α₀
+         *
+         * Putting together and isolating x₁:
+         *
+         *      x₁ = (8⋅xm - 4⋅x₃)/3 + (x₁⋅α₀ - (8⋅ym - 4⋅y₃)/3)/α₃
+         *      x₁ = (8⋅xm - 4⋅x₃ - (8⋅ym - 4⋅y₃)/α₃) / 3(1 - α₀/α₃)
+         *
+         * x₁ and x₂ are named cx1 and cx2 in the code below ("c" for "control").
+         * 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);
+    }
+
+    /**
      * Returns the center of a circle passing by the 3 given points. The distance between
the returned
      * point and any of the given points will be constant; it is the circle radius.
      *
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 bb63bdf..2ad6a40 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
@@ -53,6 +53,7 @@ public final strictfp class ShapeUtilitiesTest extends TestCase {
 
     /**
      * Tests {@link ShapeUtilities#intersectionPoint(double, double, double, double, double,
double, double, double)}.
+     * This is an anti-regression test with values computed by {@link ShapeUtilitiesViewer}.
      */
     @Test
     public void testIntersectionPoint() {
@@ -67,6 +68,7 @@ public final strictfp class ShapeUtilitiesTest extends TestCase {
 
     /**
      * Tests {@link ShapeUtilities#nearestColinearPoint(double, double, double, double, double,
double)}.
+     * This is an anti-regression test with values computed by {@link ShapeUtilitiesViewer}.
      */
     @Test
     public void testNearestColinearPoint() {
@@ -79,6 +81,7 @@ public final strictfp class ShapeUtilitiesTest extends TestCase {
 
     /**
      * Tests {@link ShapeUtilities#colinearPoint(double, double, double, double, double,
double, double)}.
+     * This is an anti-regression test with values computed by {@link ShapeUtilitiesViewer}.
      */
     @Test
     public void testColinearPoint() {
@@ -91,8 +94,8 @@ public final strictfp class ShapeUtilitiesTest extends TestCase {
     }
 
     /**
-     * Invokes {@code ShapeUtilities.fitParabol(x1, y1, px, py, x2, y2, horizontal)}, then
verifies that the control
-     * point of the returned curve is equals to {@code (cx, cy)}.
+     * Invokes {@code ShapeUtilities.fitParabol(x1, y1, px, py, x2, y2, horizontal)},
+     * then verifies that the control point of the returned curve is equals to {@code (cx,
cy)}.
      */
     private static void assertParabolEquals(final double cx, final double cy,
                                             final double x1, final double y1,
@@ -109,6 +112,7 @@ public final strictfp class ShapeUtilitiesTest extends TestCase {
     /**
      * Tests {@link ShapeUtilities#fitParabol(double, double, double, double, double, double,
boolean)}
      * with a {@code false} boolean argument.
+     * This is an anti-regression test with values computed by {@link ShapeUtilitiesViewer}.
      */
     @Test
     public void testFitParabol() {
@@ -120,14 +124,45 @@ public final strictfp class ShapeUtilitiesTest extends TestCase {
     /**
      * Tests {@link ShapeUtilities#fitParabol(double, double, double, double, double, double,
boolean)}
      * with a {@code true} boolean argument.
+     * This is an anti-regression test with values computed by {@link ShapeUtilitiesViewer}.
      */
     @Test
-    public void testFitHorizontalParabol() {
+    public void testFitParabolHorizontal() {
         assertParabolEquals(327.0, 272.41465201465195, 538, 197, 473, 213, 116, 43, true);
     }
 
     /**
+     * Invokes {@code ShapeUtilities.fitCubicCurve(x1, y1, xm, ym, x2, y2, α1, α2)}, then
verifies that
+     * the control points of the returned curve are equal to {@code (cx1, cy1)} and {@code
(cx2, cy2)}.
+     */
+    private static void assertCubicCurveEquals(final double cx1, final double cy1,
+                                               final double cx2, final double cy2,
+                                               final double x1,  final double y1,
+                                               final double xm,  final double ym,
+                                               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);
+        assertPointEquals( x1,  y1, p.getP1());
+        assertPointEquals( x2,  y2, p.getP2());
+        assertPointEquals(cx1, cy1, p.getCtrlP1());
+        assertPointEquals(cx2, cy2, p.getCtrlP2());
+    }
+
+    /**
+     * Tests {@link ShapeUtilities#fitCubicCurve(double, double, double, double, double,
double, double, double)}.
+     * This is an anti-regression test with values computed by {@link ShapeUtilitiesViewer}.
+     */
+    @Test
+    public void testFitCubicCurve() {
+        assertCubicCurveEquals(886.54566341452,   354.9913859188133,
+                               635.1210032521466, 438.6752807478533,      // Expected control
points.
+                               1143, 62, 739, 345, 204, 317, -1.14247, 0.282230);
+    }
+
+    /**
      * Tests {@link ShapeUtilities#circleCentre(double, double, double, double, double, double)}.
+     * This is an anti-regression test with values computed by {@link ShapeUtilitiesViewer}.
      */
     @Test
     public void testCircleCentre() {
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 252d50a..568f4b5 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
@@ -40,7 +40,7 @@ import org.apache.sis.util.CharSequences;
  * It is rather designed for explicit execution from an IDE or the command line for visual
inspection.
  *
  * @author  Martin Desruisseaux (Geomatys)
- * @version 0.5
+ * @version 1.0
  * @since   0.5
  * @module
  */
@@ -52,9 +52,10 @@ final strictfp class ShapeUtilitiesViewer extends JPanel {
     private enum Method {
         INTERSECTION_POINT,
         NEAREAST_COLINEAR_POINT,
-        COLINEAR_POINT,
+        DISTANCED_COLINEAR_POINT,
         FIT_PARABOL,
-        FIT_HORIZONTAL_PARABOL,
+        FIT_PARABOL_HORIZONTAL,
+        FIT_CUBIC_CURVE,
         CIRCLE_CENTRE
     };
 
@@ -74,9 +75,10 @@ final strictfp class ShapeUtilitiesViewer extends JPanel {
     private final Path2D output;
 
     /**
-     * {@code true} if we should fill the output, or {@code false} for drawing the contour
only.
+     * {@code true} if we should fill the input or output, or {@code false} for drawing the
contour only.
+     * Note that the filling is used also for the little circles representing points.
      */
-    private boolean fillOutput;
+    private boolean fillInput, fillOutput;
 
     /**
      * Random number generator to use in the visual test.
@@ -123,6 +125,7 @@ final strictfp class ShapeUtilitiesViewer extends JPanel {
     final void assignRandomPoints(final Method method) {
         input .reset();
         output.reset();
+        fillInput  = true;
         fillOutput = true;
         boolean horizontal = false;
         final int x      = getX();
@@ -155,7 +158,7 @@ final strictfp class ShapeUtilitiesViewer extends JPanel {
                 out.printf(Locale.ENGLISH, "nearestColinearPoint(%d, %d, %d, %d, %d, %d)%n",
x1, y1, x2, y2, x3, y3);
                 break;
             }
-            case COLINEAR_POINT: {
+            case DISTANCED_COLINEAR_POINT: {
                 final double distance = StrictMath.hypot(x4, y4);
                 input.moveTo(x1, y1);
                 input.lineTo(x2, y2);
@@ -164,7 +167,7 @@ final strictfp class ShapeUtilitiesViewer extends JPanel {
                 out.printf(Locale.ENGLISH, "colinearPoint(%d, %d, %d, %d, %d, %d, %g)%n",
x1, y1, x2, y2, x3, y3, distance);
                 break;
             }
-            case FIT_HORIZONTAL_PARABOL: {
+            case FIT_PARABOL_HORIZONTAL: {
                 horizontal = true;
                 // Fall through
             }
@@ -177,12 +180,31 @@ final strictfp class ShapeUtilitiesViewer extends JPanel {
                 fillOutput = false;
                 break;
             }
+            case FIT_CUBIC_CURVE: {
+                addPoint(input, x1, y1);
+                addPoint(input, x2, y2);
+                addPoint(input, x3, y3);
+                final double α1 = (y4 - y1) / (double) (x4 - x1);      // (x4, y4) used
as a point for computing tangents.
+                final double α2 = (y3 - y4) / (double) (x3 - x4);
+                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);
+                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;
+                break;
+            }
             case CIRCLE_CENTRE: {
                 addPoint(input, x1, y1);
                 addPoint(input, x2, y2);
                 addPoint(input, x3, y3);
-                addPoint(output, ShapeUtilities.circleCentre(x1, y1, x2, y2, x3, y3));
+                final Point2D.Double center = ShapeUtilities.circleCentre(x1, y1, x2, y2,
x3, y3);
+                addPoint(output, center);
+                final double radius = StrictMath.hypot(center.x - x1, center.y - y1);
+                output.append(new Ellipse2D.Double(center.x - radius, center.y - radius,
radius*2, radius*2), false);
                 out.printf(Locale.ENGLISH, "circleCentre(%d, %d, %d, %d, %d, %d)%n", x1,
y1, x2, y2, x3, y3);
+                fillOutput = false;
                 break;
             }
         }
@@ -205,8 +227,10 @@ final strictfp class ShapeUtilitiesViewer extends JPanel {
         }
         g.setColor(Color.RED);
         g.draw(output);
-        g.setColor(Color.CYAN);
-        g.fill(input);
+        if (fillInput) {
+            g.setColor(Color.CYAN);
+            g.fill(input);
+        }
         g.setColor(Color.BLUE);
         g.draw(input);
     }


Mime
View raw message