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 2019/05/12 21:07:18 UTC
[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.
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 <ma...@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);
}