sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject svn commit: r1649878 - in /sis/branches/JDK8/core/sis-referencing/src: main/java/org/apache/sis/internal/referencing/j2d/ test/java/org/apache/sis/internal/referencing/j2d/ test/java/org/apache/sis/test/suite/
Date Tue, 06 Jan 2015 17:20:51 GMT
Author: desruisseaux
Date: Tue Jan  6 17:20:51 2015
New Revision: 1649878

URL: http://svn.apache.org/r1649878
Log:
Port more geometric formulas, some of them needed for Envelope transformations (next commit).

Added:
    sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/
    sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
  (with props)
Modified:
    sis/branches/JDK8/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java
    sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/test/suite/ReferencingTestSuite.java

Modified: sis/branches/JDK8/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK8/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java?rev=1649878&r1=1649877&r2=1649878&view=diff
==============================================================================
--- sis/branches/JDK8/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java
[UTF-8] (original)
+++ sis/branches/JDK8/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/j2d/ShapeUtilities.java
[UTF-8] Tue Jan  6 17:20:51 2015
@@ -49,6 +49,224 @@ public final class ShapeUtilities extend
     }
 
     /**
+     * Returns the intersection point between two line segments. The lines do not continue
to infinity;
+     * if the intersection does not occur between the ending points {@linkplain Line2D#getP1()
P1} and
+     * {@linkplain Line2D#getP2() P2} of the two line segments, then this method returns
{@code null}.
+     *
+     * @param  ax1 <var>x</var> value of the first point on the first  line.
+     * @param  ay1 <var>y</var> value of the first point on the first  line.
+     * @param  ax2 <var>x</var> value of the last  point on the first  line.
+     * @param  ay2 <var>y</var> value of the last  point on the first  line.
+     * @param  bx1 <var>x</var> value of the first point on the second line.
+     * @param  by1 <var>y</var> value of the first point on the second line.
+     * @param  bx2 <var>x</var> value of the last  point on the second line.
+     * @param  by2 <var>y</var> value of the last  point on the second line.
+     * @return The intersection point, or {@code null} if none.
+     */
+    public static Point2D.Double intersectionPoint(final double ax1, final double ay1, double
ax2, double ay2,
+                                                   final double bx1, final double by1, double
bx2, double by2)
+    {
+        ax2 -= ax1;
+        ay2 -= ay1;
+        bx2 -= bx1;
+        by2 -= by1;
+        double x = ay2 * bx2;
+        double y = ax2 * by2;
+        /*
+         * The above (x,y) coordinate is temporary. If and only if the two line are parallel,
then x == y.
+         * Following code computes the real (x,y) coordinates of the intersection point.
+         */
+        x = ((by1-ay1) * (ax2*bx2) + x*ax1 - y*bx1) / (x-y);
+        y = abs(bx2) > abs(ax2) ?
+                (by2 / bx2) * (x - bx1) + by1 :
+                (ay2 / ax2) * (x - ax1) + ay1;
+        /*
+         * The '!=0' expressions below are important for avoiding rounding errors with
+         * horizontal or vertical lines. The '!' are important for handling NaN values.
+         */
+        if (ax2 != 0 && !(ax2 < 0 ? (x <= ax1 && x >= ax1 + ax2)
: (x >= ax1 && x <= ax1 + ax2))) return null;
+        if (bx2 != 0 && !(bx2 < 0 ? (x <= bx1 && x >= bx1 + bx2)
: (x >= bx1 && x <= bx1 + bx2))) return null;
+        if (ay2 != 0 && !(ay2 < 0 ? (y <= ay1 && y >= ay1 + ay2)
: (y >= ay1 && y <= ay1 + ay2))) return null;
+        if (by2 != 0 && !(by2 < 0 ? (y <= by1 && y >= by1 + by2)
: (y >= by1 && y <= by1 + by2))) return null;
+        return new Point2D.Double(x,y);
+    }
+
+    /**
+     * Returns the point on the given {@code line} segment which is closest to the given
{@code point}.
+     * Let {@code result} be the returned point. This method guarantees (except for rounding
errors) that:
+     *
+     * <ul>
+     *   <li>{@code result} is a point on the {@code line} segment. It is located between
the
+     *       {@linkplain Line2D#getP1() P1} and {@linkplain Line2D#getP2() P2} ending points
+     *       of that line segment.</li>
+     *   <li>The distance between the {@code result} point and the given {@code point}
is
+     *       the shortest distance among the set of points meeting the previous condition.
+     *       This distance can be obtained with {@code point.distance(result)}.</li>
+     * </ul>
+     *
+     * @param  x1 <var>x</var> value of the first point on the line.
+     * @param  y1 <var>y</var> value of the first point on the line.
+     * @param  x2 <var>x</var> value of the last  point on the line.
+     * @param  y2 <var>y</var> value of the last  point on the line.
+     * @param  x  <var>x</var> value of a point close to the given line.
+     * @param  y  <var>y</var> value of a point close to the given line.
+     * @return The nearest point on the given line.
+     *
+     * @see #colinearPoint(double,double , double,double , double,double , double)
+     */
+    public static Point2D.Double nearestColinearPoint(final double x1, final double y1,
+                                                      final double x2, final double y2,
+                                                            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;
+        } else {
+            x = x2;
+        }
+        if (x1 <= x2) {
+            if (x < x1) x = x1;
+            if (x > x2) x = x2;
+        } else {
+            if (x > x1) x = x1;
+            if (x < x2) x = x2;
+        }
+        if (y1 <= y2) {
+            if (y < y1) y = y1;
+            if (y > y2) y = y2;
+        } else {
+            if (y > y1) y = y1;
+            if (y < y2) y = y2;
+        }
+        return new Point2D.Double(x,y);
+    }
+
+    /**
+     * Returns a point on the given {@code line} segment located at the given {@code distance}
+     * from that line. Let {@code result} be the returned point. If {@code result} is not
null,
+     * then this method guarantees (except for rounding error) that:
+     *
+     * <ul>
+     *   <li>{@code result} is a point on the {@code line} segment. It is located between
+     *       the {@linkplain Line2D#getP1() P1} and {@linkplain Line2D#getP2() P2} ending
+     *       points of that line segment.</li>
+     *   <li>The distance between the {@code result} and the given {@code point} is
exactly
+     *       equal to {@code distance}.</li>
+     * </ul>
+     *
+     * If no result point meets those conditions, then this method returns {@code null}.
+     * If two result points meet those conditions, then this method returns the point
+     * which is the closest to {@code line.getP1()}.
+     *
+     * @param  x1 <var>x</var> value of the first point on the line.
+     * @param  y1 <var>y</var> value of the first point on the line.
+     * @param  x2 <var>x</var> value of the last  point on the line.
+     * @param  y2 <var>y</var> value of the last  point on the line.
+     * @param  x  <var>x</var> value of a point close to the given line.
+     * @param  y  <var>y</var> value of a point close to the given line.
+     * @param  distance The distance between the given point and the point to be returned.
+     * @return A point on the given line located at the given distance from the given point.
+     *
+     * @see #nearestColinearPoint(double,double , double,double , double,double)
+     */
+    public static Point2D.Double colinearPoint(double x1, double y1, double x2, double y2,
+                                               double x, double y, double distance)
+    {
+        final double ox1 = x1;
+        final double oy1 = y1;
+        final double ox2 = x2;
+        final double oy2 = y2;
+        distance *= distance;
+        if (x1 == x2) {
+            double dy = x1 - x;
+            dy = sqrt(distance - dy*dy);
+            y1 = y - dy;
+            y2 = y + dy;
+        } else if (y1 == y2) {
+            double dx = y1 - y;
+            dx = sqrt(distance - dx*dx);
+            x1 = x - dx;
+            x2 = x + dx;
+        } else {
+            final double m  = (y1-y2) / (x2-x1);
+            final double y0 = (y2-y) + m*(x2-x);
+            final double B  = m * y0;
+            final double A  = m*m + 1;
+            final double C  = sqrt(B*B + A*(distance - y0*y0));
+            x1 = (B+C) / A;
+            x2 = (B-C) / A;
+            y1 = y + y0 - m*x1;
+            y2 = y + y0 - m*x2;
+            x1 += x;
+            x2 += x;
+        }
+        boolean in1, in2;
+        if (oy1 > oy2) {
+            in1 = (y1 <= oy1 && y1 >= oy2);
+            in2 = (y2 <= oy1 && y2 >= oy2);
+        } else {
+            in1 = (y1 >= oy1 && y1 <= oy2);
+            in2 = (y2 >= oy1 && y2 <= oy2);
+        }
+        if (ox1 > ox2) {
+            in1 &= (x1 <= ox1 && x1 >= ox2);
+            in2 &= (x2 <= ox1 && x2 >= ox2);
+        } else {
+            in1 &= (x1 >= ox1 && x1 <= ox2);
+            in2 &= (x2 >= ox1 && x2 <= ox2);
+        }
+        if (!in1 && !in2) return null;
+        if (!in1) return new Point2D.Double(x2,y2);
+        if (!in2) return new Point2D.Double(x1,y1);
+        x = x1 - ox1;
+        y = y1 - oy1;
+        final double d1 = x*x + y*y;
+        x = x2 - ox1;
+        y = y2 - oy1;
+        final double d2 = x*x + y*y;
+        if (d1 > d2) return new Point2D.Double(x2,y2);
+        else         return new Point2D.Double(x1,y1);
+    }
+
+    /**
+     * Returns a quadratic curve passing by the 3 given points. There is an infinity of quadratic
curves passing by
+     * 3 points. We can express the curve we are looking for as a parabolic equation of the
form {@code y=ax²+bx+c}
+     * but where the <var>x</var> axis is not necessarily horizontal. The orientation
of the <var>x</var> axis in
+     * the above equation is determined by the {@code horizontal} parameter:
+     *
+     * <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>
+     *   <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>
+     *
+     * Note that if {@code P0.y == P2.y}, then both {@code horizontal} values produce the
same result.
+     *
+     * @param  x0 <var>x</var> value of the starting point.
+     * @param  y0 <var>y</var> value of the starting point.
+     * @param  x1 <var>x</var> value of a passing point.
+     * @param  y1 <var>y</var> value of a passing point.
+     * @param  x2 <var>x</var> value of the ending point.
+     * @param  y2 <var>y</var> value of the ending point.
+     * @param  horizontal If {@code true}, the <var>x</var> axis is considered
horizontal while computing the
+     *         {@code y=ax²+bx+c} equation terms. If {@code false}, it is considered parallel
to the line
+     *         joining the {@code P0} and {@code P2} points.
+     * @return A quadratic curve passing by the given points. The curve starts at {@code
P0} and ends at {@code P2}.
+     *         If two points are too close or if the three points are colinear, then this
method returns {@code null}.
+     */
+    public static QuadCurve2D.Double fitParabol(final double x0, final double y0,
+                                                final double x1, final double y1,
+                                                final double x2, final double y2,
+                                                final boolean horizontal)
+    {
+        final Point2D.Double p = parabolicControlPoint(x0, y0, x1, y1, x2, y2, horizontal);
+        return (p != null) ? new QuadCurve2D.Double(x0, y0, p.x, p.y, x2, y2) : null;
+    }
+
+    /**
      * Returns the control point of a quadratic curve passing by the 3 given points. There
is an infinity of quadratic
      * curves passing by 3 points. We can express the curve we are looking for as a parabolic
equation of the form
      * {@code y = ax²+bx+c}, but the <var>x</var> axis is not necessarily horizontal.
The <var>x</var> axis orientation
@@ -108,7 +326,7 @@ public final class ShapeUtilities extend
             y2 = (x1*rx2 + y1*ry2) / x2; // use 'y2' as a temporary variable for 'x1'
             y1 = (y1*rx2 - x1*ry2) / x2;
             x1 = y2;
-            y2 = 0;
+            y2 = 0; // set as a matter of principle (but not used).
             /*
              * Now compute the control point coordinates in our new coordinate system axis.
              */
@@ -128,6 +346,94 @@ public final class ShapeUtilities extend
     }
 
     /**
+     * Returns 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.
+     *
+     * @param  x1 <var>x</var> value of the first  point.
+     * @param  y1 <var>y</var> value of the first  point.
+     * @param  x2 <var>x</var> value of the second point.
+     * @param  y2 <var>y</var> value of the second point.
+     * @param  x3 <var>x</var> value of the third  point.
+     * @param  y3 <var>y</var> value of the third  point.
+     * @return A circle passing by the given points.
+     */
+    public static Point2D.Double circleCentre(double x1, double y1,
+                                              double x2, double y2,
+                                              double x3, double y3)
+    {
+        x2 -= x1;
+        x3 -= x1;
+        y2 -= y1;
+        y3 -= y1;
+        final double sq2 = (x2*x2 + y2*y2);
+        final double sq3 = (x3*x3 + y3*y3);
+        final double x   = (y2*sq3 - y3*sq2) / (y2*x3 - y3*x2);
+        return new Point2D.Double(x1 + 0.5*x, y1 + 0.5*(sq2 - x*x2)/y2);
+    }
+
+    /**
+     * Finds the extremum of the unique cubic curve which fit the two given points and derivatives.
+     * First, this method finds the A, B, C and D coefficients for the following equation:
+     *
+     * <blockquote><var>y</var> = A + B<var>x</var> + C<var>x</var><sup>2</sup>
+ D<var>x</var><sup>3</sup></blockquote>
+     *
+     * Next, this method finds the extremum by finding the (<var>x</var>,<var>y</var>)
values
+     * that satisfy the following equation (which is the derivative of the above equation):
+     *
+     * <blockquote>B + 2C<var>x</var> + 3D<var>x</var><sup>2</sup>
= 0</blockquote>
+     *
+     * A cubic curve can have two extremum, which are returned in a {@link Line2D} construct
in
+     * no particular order. The length of the returned line is the distance separating the
two
+     * extremum (often a useful information for determining if a quadratic equation would
be a
+     * sufficient approximation).
+     *
+     * <p>The line returned by this method may contains {@linkplain Double#NaN NaN}
values if the
+     * given geometry is actually a line segment ({@code dy1} = {@code dy2} = slope from
P1 to P2).</p>
+     *
+     * @param  x1   The <var>x</var> ordinate of the first point.
+     * @param  y1   The <var>y</var> ordinate of the first point.
+     * @param  dy1  The &part;<var>x</var>/&part;<var>y</var>
value at the first point.
+     * @param  x2   The <var>x</var> ordinate of the second point.
+     * @param  y2   The <var>y</var> ordinate of the second point.
+     * @param  dy2  The &part;<var>x</var>/&part;<var>y</var>
value at the second point.
+     * @return The two points located on the extremum of the fitted cubic curve.
+     */
+    public static Line2D.Double cubicCurveExtremum(double x1, double y1, final double dy1,
+                                                   double x2, double y2, final double dy2)
+    {
+        /*
+         * Equation for a cubic curve is y = A + Bx + Cx² + Dx³.
+         * Before to compute, translate the curve such that (x1,y1) = (0,0),
+         * which simplify a lot the equation. In such case:
+         *
+         *   A = 0
+         *   B = dy1
+         *   C and D: see code below.
+         */
+        x2 -= x1;
+        y2 -= y1;
+        final double d = (dy2 - dy1)   / x2;
+        final double w = (dy1 - y2/x2) / x2;
+        final double D = (2*w + d)     / x2;
+        final double C = -3*w - d;
+        /*
+         * For location the minimum, we search the location where the derivative is null:
+         *
+         *    B + 2Cx + 3Dx² == 0    ⇒    x = (-b ± √(b² - 4ac)) / (2a)
+         *
+         * where, a = 3*D,  b = 2*C  and  c = B = dy1
+         */
+        final double a  = 3*D;
+        final double b  = 2*C;
+        final double q  = -0.5*(b + copySign(sqrt(b*b - 4*a*dy1), b));
+        final double r1 = q / a;
+        final double r2 = dy1 / q;
+        return new Line2D.Double(
+                x1 + r1, y1 + r1*(dy1 + r1*(C + r1*D)),
+                x1 + r2, y1 + r2*(dy1 + r2*(C + r2*D)));
+    }
+
+    /**
      * Attempts to replace an arbitrary shape by one of the standard Java2D constructs.
      * For example if the given {@code path} is a {@link Path2D} containing only a single
      * line or a quadratic curve, then this method replaces it by a {@link Line2D} or

Added: sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java?rev=1649878&view=auto
==============================================================================
--- sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
(added)
+++ sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
[UTF-8] Tue Jan  6 17:20:51 2015
@@ -0,0 +1,67 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sis.internal.referencing.j2d;
+
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import org.apache.sis.test.TestCase;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+
+/**
+ * Tests the {@link ShapeUtilities} class.
+ *
+ * @author  Martin Desruisseaux (Geomatys)
+ * @since   0.5 (derived from geotk-3.20)
+ * @version 0.5
+ * @module
+ */
+public final strictfp class ShapeUtilitiesTest extends TestCase {
+    /**
+     * Tolerance factor for the tests in this class.
+     */
+    private static final double EPS = 1E-8;
+
+    /**
+     * Tests {@link ShapeUtilities#cubicCurveExtremum(double, double, double, double, double,
double)}.
+     */
+    @Test
+    public void testCubicCurveExtremum() {
+        final Point2D.Double P1 = new Point2D.Double();
+        final Point2D.Double P2 = new Point2D.Double();
+        double dy1, dy2;
+        Line2D extremums;
+
+        P1.x =  0; P1.y =  0; dy1 =   7;
+        P2.x = -4; P2.y =  0; dy2 = -12;
+        extremums = ShapeUtilities.cubicCurveExtremum(P1.x, P1.y, dy1, P2.x, P2.y, dy2);
+        assertEquals("X1",   3.31741507, extremums.getX1(), EPS);
+        assertEquals("Y1",  17.31547745, extremums.getY1(), EPS);
+        assertEquals("X2",  -2.25074840, extremums.getX2(), EPS);
+        assertEquals("Y2",  -9.65918115, extremums.getY2(), EPS);
+
+        P1.x = 0; P1.y =  0; dy1 = 5;
+        P2.x = 5; P2.y = 20; dy2 = 1;
+        extremums = ShapeUtilities.cubicCurveExtremum(P1.x, P1.y, dy1, P2.x, P2.y, dy2);
+        assertEquals("X1",   5.47313697, extremums.getX1(), EPS);
+        assertEquals("Y1",  20.24080512, extremums.getY1(), EPS);
+        assertEquals("X2",  -3.80647030, extremums.getX2(), EPS);
+        assertEquals("Y2", -11.72228660, extremums.getY2(), EPS);
+    }
+}

Propchange: sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/internal/referencing/j2d/ShapeUtilitiesTest.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain;charset=UTF-8

Modified: sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/test/suite/ReferencingTestSuite.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/test/suite/ReferencingTestSuite.java?rev=1649878&r1=1649877&r2=1649878&view=diff
==============================================================================
--- sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/test/suite/ReferencingTestSuite.java
[UTF-8] (original)
+++ sis/branches/JDK8/core/sis-referencing/src/test/java/org/apache/sis/test/suite/ReferencingTestSuite.java
[UTF-8] Tue Jan  6 17:20:51 2015
@@ -30,7 +30,10 @@ import org.junit.BeforeClass;
  * @module
  */
 @Suite.SuiteClasses({
-    // Test matrix first because they may be used in about every SIS corners.
+    org.apache.sis.internal.referencing.FormulasTest.class,
+    org.apache.sis.internal.referencing.j2d.ShapeUtilitiesTest.class,
+
+    // Test matrix early because they may be used in about every SIS corners.
     org.apache.sis.referencing.operation.matrix.GeneralMatrixTest.class,
     org.apache.sis.referencing.operation.matrix.SolverTest.class,
     org.apache.sis.referencing.operation.matrix.Matrix1Test.class,
@@ -51,7 +54,6 @@ import org.junit.BeforeClass;
     org.apache.sis.referencing.operation.transform.ConcatenatedTransformTest.class,
     org.apache.sis.referencing.operation.transform.TransferFunctionTest.class,
 
-    org.apache.sis.internal.referencing.FormulasTest.class,
     org.apache.sis.internal.referencing.VerticalDatumTypesTest.class,
     org.apache.sis.internal.referencing.AxisDirectionsTest.class,
     org.apache.sis.internal.referencing.PositionalAccuracyConstantTest.class,



Mime
View raw message