← Back to branch summary

~duyi001/gephi/DSNI

« back to all changes in this revision

Viewing changes to RankingAPI/src/org/gephi/ranking/api/Interpolator.java

  • Committer: sunsnowad
  • Author(s): Yi Du
  • Date: 2011-09-08 16:36:59 UTC
  • mfrom: (1435.1.968 gephi)
  • Revision ID: sunsnowad@www-691ed046717-20110908163659-aorx14ylp8f9qwdx
1.merge with main branch
2.update twitter4j to version 2.2.4
3.fix an existing bug on "twitter user import"

Show diffs side-by-side

added added

removed removed

Lines of Context:
RankingAPI/src/org/gephi/ranking/api/Interpolator.java
17
17
 
18
18
You should have received a copy of the GNU Affero General Public License
19
19
along with Gephi.  If not, see <http://www.gnu.org/licenses/>.
20
 
*/
 
20
 */
21
21
package org.gephi.ranking.api;
22
22
 
23
23
/**
24
 
 * Interface that defines the single {@link #interpolate(float)} method. This interface is implemented by built-in interpolators.
 
24
 * Abstract clas that defines the single {@link #interpolate(float)} method. This 
 
25
 * abstract class is implemented by built-in interpolators.
 
26
 * 
25
27
 * @author Mathieu Bastian
26
28
 */
27
 
public interface Interpolator {
28
 
 
29
 
    /**
30
 
     * This function takes an input value between 0 and 1 and returns another value, also between 0 and 1.
 
29
public abstract class Interpolator {
 
30
 
 
31
    /**
 
32
     * Linear interpolation <code>x = interpolate(x)<code>
 
33
     */
 
34
    public static final Interpolator LINEAR = new Interpolator() {
 
35
 
 
36
        public float interpolate(float x) {
 
37
            return x;
 
38
        }
 
39
    };
 
40
    /**
 
41
     * Log2 interpolation <code>Math.log(1 + x)/Math.log(2) = interpolate(x)</code>
 
42
     */
 
43
    public static final Interpolator LOG2 = new Interpolator() {
 
44
 
 
45
        public float interpolate(float x) {
 
46
            return (float) (Math.log(1 + x) / Math.log(2));
 
47
        }
 
48
    };
 
49
 
 
50
    /**
 
51
     * Builds a bezier interpolator with two control points (px1, py1) and
 
52
     * (px2, py2). The points should all be in range [0, 1].
 
53
     * @param px1 the x-coordinate of first control point, between [0, 1]
 
54
     * @param py1 the y-coordinate of first control point, between [0, 1]
 
55
     * @param px2 the x-coordinate of second control point, between [0, 1]
 
56
     * @param py2 the y-coordinate of second control point, between [0, 1]
 
57
     * @return new bezier interpolator
 
58
     */
 
59
    public static Interpolator newBezierInterpolator(float px1, float py1, float px2, float py2) {
 
60
        return new BezierInterpolator(px1, py1, px2, py2);
 
61
    }
 
62
 
 
63
    /**
 
64
     * This function takes an input value between 0 and 1 and returns another value,
 
65
     * also between 0 and 1.
31
66
     * @param x a value between 0 and 1
32
 
     * @return a value between 0 and 1. Values outside of this boundary may be clamped to the interval [0,1] and cause undefined results.
33
 
     */
34
 
    public float interpolate(float x);
 
67
     * @return a value between 0 and 1. Values outside of this boundary may be
 
68
     * clamped to the interval [0,1] and cause undefined results.
 
69
     */
 
70
    public abstract float interpolate(float x);
 
71
 
 
72
    /**
 
73
     * Bezier curve interpolator.
 
74
     * <p>
 
75
     * Basically, a cubic Bezier curve is created with start point (0,0) and
 
76
     * endpoint (1,1).  The other two control points (px1, py1) and (px2, py2) are
 
77
     * given by the user, where px1, py1, px1, and px2 are all in the range [0,1].
 
78
     * </p>
 
79
     */
 
80
    //Author David C. Browne
 
81
    public static class BezierInterpolator extends Interpolator {
 
82
 
 
83
        /**
 
84
         * the coordinates of the 2 2D control points for a cubic Bezier curve,
 
85
         * with implicit start point (0,0) and end point (1,1) -- each individual
 
86
         * coordinate value must be in range [0,1]
 
87
         */
 
88
        private final float x1, y1, x2, y2;
 
89
        /**
 
90
         * do the input control points form a line with (0,0) and (1,1), i.e.,
 
91
         * x1 == y1 and x2 == y2 -- if so, then all x(t) == y(t) for the curve
 
92
         */
 
93
        private final boolean isCurveLinear;
 
94
        /**
 
95
         * power of 2 sample size for lookup table of x values
 
96
         */
 
97
        private static final int SAMPLE_SIZE = 16;
 
98
        /**
 
99
         * difference in t used to calculate each of the xSamples values -- power of
 
100
         * 2 sample size should provide exact representation of this value and its
 
101
         * integer multiples (integer in range of [0..SAMPLE_SIZE]
 
102
         */
 
103
        private static final float SAMPLE_INCREMENT = 1f / SAMPLE_SIZE;
 
104
        /**
 
105
         * x values for the bezier curve, sampled at increments of 1/SAMPLE_SIZE --
 
106
         * this is used to find the good initial guess for parameter t, given an x
 
107
         */
 
108
        private final float[] xSamples = new float[SAMPLE_SIZE + 1];
 
109
 
 
110
        /**
 
111
         * constructor -- cubic bezier curve will be represented by control points
 
112
         * (0,0) (px1,py1) (px2,py2) (1,1) -- px1, py1, px2, py2 all in range [0,1]
 
113
         * @param px1 is x-coordinate of first control point, in range [0,1]
 
114
         * @param py1 is y-coordinate of first control point, in range [0,1]
 
115
         * @param px2 is x-coordinate of second control point, in range [0,1]
 
116
         * @param py2 is y-coordinate of second control point, in range [0,1]
 
117
         */
 
118
        public BezierInterpolator(float px1, float py1, float px2, float py2) {
 
119
            // check user input for precondition
 
120
            if (px1 < 0 || px1 > 1 || py1 < 0 || py1 > 1
 
121
                    || px2 < 0 || px2 > 1 || py2 < 0 || py2 > 1) {
 
122
                throw new IllegalArgumentException("control point coordinates must "
 
123
                        + "all be in range [0,1]");
 
124
            }
 
125
 
 
126
            // save control point data
 
127
            x1 = px1;
 
128
            y1 = py1;
 
129
            x2 = px2;
 
130
            y2 = py2;
 
131
 
 
132
            // calc linearity/identity curve
 
133
            isCurveLinear = ((x1 == y1) && (x2 == y2));
 
134
 
 
135
            // make the array of x value samples
 
136
            if (!isCurveLinear) {
 
137
                for (int i = 0; i < SAMPLE_SIZE + 1; ++i) {
 
138
                    xSamples[i] = eval(i * SAMPLE_INCREMENT, x1, x2);
 
139
                }
 
140
            }
 
141
        }
 
142
 
 
143
        /**
 
144
         * get the y-value of the cubic bezier curve that corresponds to the x input
 
145
         * @param x is x-value of cubic bezier curve, in range [0,1]
 
146
         * @return corresponding y-value of cubic bezier curve -- in range [0,1]
 
147
         */
 
148
        public float interpolate(float x) {
 
149
            // check user input for precondition
 
150
            if (x < 0) {
 
151
                x = 0;
 
152
            } else if (x > 1) {
 
153
                x = 1;
 
154
            }
 
155
 
 
156
            // check quick exit identity cases (linear curve or curve endpoints)
 
157
            if (isCurveLinear || x == 0 || x == 1) {
 
158
                return x;
 
159
            }
 
160
 
 
161
            // find the t parameter for a given x value, and use this t to calculate
 
162
            // the corresponding y value
 
163
            return eval(findTForX(x), y1, y2);
 
164
        }
 
165
 
 
166
        /**
 
167
         * use Bernstein basis to evaluate 1D cubic Bezier curve (quicker and more
 
168
         * numerically stable than power basis) -- 1D control coordinates are
 
169
         * (0, p1, p2, 1), where p1 and p2 are in range [0,1], and there is no
 
170
         * ordering constraint on p1 and p2, i.e., p1 <= p2 does not have to be true
 
171
         * @param t is the paramaterized value in range [0,1]
 
172
         * @param p1 is 1st control point coordinate in range [0,1]
 
173
         * @param p2 is 2nd control point coordinate in range [0,1]
 
174
         * @return the value of the Bezier curve at parameter t
 
175
         */
 
176
        private float eval(float t, float p1, float p2) {
 
177
            // Use optimzied version of the normal Bernstein basis form of Bezier:
 
178
            // (3*(1-t)*(1-t)*t*p1)+(3*(1-t)*t*t*p2)+(t*t*t), since p0=0, p3=1
 
179
            // The above unoptimized version is best using -server, but since we are
 
180
            // probably doing client-side animation, this is faster.
 
181
            float compT = 1 - t;
 
182
            return t * (3 * compT * (compT * p1 + t * p2) + (t * t));
 
183
        }
 
184
 
 
185
        /**
 
186
         * evaluate Bernstein basis derivative of 1D cubic Bezier curve, where 1D
 
187
         * control points are (0, p1, p2, 1), where p1 and p2 are in range [0,1], and
 
188
         * there is no ordering constraint on p1 and p2, i.e., p1 <= p2 does not have
 
189
         * to be true
 
190
         * @param t is the paramaterized value in range [0,1]
 
191
         * @param p1 is 1st control point coordinate in range [0,1]
 
192
         * @param p2 is 2nd control point coordinate in range [0,1]
 
193
         * @return the value of the Bezier curve at parameter t
 
194
         */
 
195
        private float evalDerivative(float t, float p1, float p2) {
 
196
            // use optimzed version of Berstein basis Bezier derivative:
 
197
            // (3*(1-t)*(1-t)*p1)+(6*(1-t)*t*(p2-p1))+(3*t*t*(1-p2)), since p0=0, p3=1
 
198
            // The above unoptimized version is best using -server, but since we are
 
199
            // probably doing client-side animation, this is faster.
 
200
            float compT = 1 - t;
 
201
            return 3 * (compT * (compT * p1 + 2 * t * (p2 - p1)) + t * t * (1 - p2));
 
202
        }
 
203
 
 
204
        /**
 
205
         * find an initial good guess for what parameter t might produce the x-value
 
206
         * on the Bezier curve -- uses linear interpolation on the x-value sample
 
207
         * array that was created on construction
 
208
         * @param x is x-value of cubic bezier curve, in range [0,1]
 
209
         * @return a good initial guess for parameter t (in range [0,1]) that gives x
 
210
         */
 
211
        private float getInitialGuessForT(float x) {
 
212
            // find which places in the array that x would be sandwiched between,
 
213
            // and then linearly interpolate a reasonable value of t -- array values
 
214
            // are ascending (or at least never descending) -- binary search is
 
215
            // probably more trouble than it is worth here
 
216
            for (int i = 1; i < SAMPLE_SIZE + 1; ++i) {
 
217
                if (xSamples[i] >= x) {
 
218
                    float xRange = xSamples[i] - xSamples[i - 1];
 
219
                    if (xRange == 0) {
 
220
                        // no change in value between samples, so use earlier time
 
221
                        return (i - 1) * SAMPLE_INCREMENT;
 
222
                    } else {
 
223
                        // linearly interpolate the time value
 
224
                        return ((i - 1) + ((x - xSamples[i - 1]) / xRange))
 
225
                                * SAMPLE_INCREMENT;
 
226
                    }
 
227
                }
 
228
            }
 
229
 
 
230
            // shouldn't get here since 0 <= x <= 1, and xSamples[0] == 0 and
 
231
            // xSamples[SAMPLE_SIZE] == 1 (using power of 2 SAMPLE_SIZE for more
 
232
            // exact increment arithmetic)
 
233
            return 1;
 
234
        }
 
235
 
 
236
        /**
 
237
         * find the parameter t that produces the given x-value for the curve --
 
238
         * uses Newton-Raphson to refine the value as opposed to subdividing until
 
239
         * we are within some tolerance
 
240
         * @param x is x-value of cubic bezier curve, in range [0,1]
 
241
         * @return the parameter t (in range [0,1]) that produces x
 
242
         */
 
243
        private float findTForX(float x) {
 
244
            // get an initial good guess for t
 
245
            float t = getInitialGuessForT(x);
 
246
 
 
247
            // use Newton-Raphson to refine the value for t -- for this constrained
 
248
            // Bezier with float accuracy (7 digits), any value not converged by 4
 
249
            // iterations is cycling between values, which can minutely affect the
 
250
            // accuracy of the last digit
 
251
            final int numIterations = 4;
 
252
            for (int i = 0; i < numIterations; ++i) {
 
253
                // stop if this value of t gives us exactly x
 
254
                float xT = (eval(t, x1, x2) - x);
 
255
                if (xT == 0) {
 
256
                    break;
 
257
                }
 
258
 
 
259
                // stop if derivative is 0
 
260
                float dXdT = evalDerivative(t, x1, x2);
 
261
                if (dXdT == 0) {
 
262
                    break;
 
263
                }
 
264
 
 
265
                // refine t
 
266
                t -= xT / dXdT;
 
267
            }
 
268
 
 
269
            return t;
 
270
        }
 
271
    }
35
272
}