1 /*
2 * Copyright (c) 1998, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.javafx.geom;
27
28 import java.util.Vector;
29
30 public abstract class Curve {
31 public static final int INCREASING = 1;
32 public static final int DECREASING = -1;
33
34 protected int direction;
35
36 public static void insertMove(Vector curves, double x, double y) {
37 curves.add(new Order0(x, y));
38 }
39
40 public static void insertLine(Vector curves,
41 double x0, double y0,
42 double x1, double y1)
43 {
44 if (y0 < y1) {
45 curves.add(new Order1(x0, y0,
46 x1, y1,
47 INCREASING));
48 } else if (y0 > y1) {
49 curves.add(new Order1(x1, y1,
50 x0, y0,
51 DECREASING));
52 } else {
53 // Do not add horizontal lines
54 }
55 }
56
57 public static void insertQuad(Vector curves, double tmp[],
58 double x0, double y0,
59 double cx0, double cy0,
60 double x1, double y1)
61 {
62 if (y0 > y1) {
63 Order2.insert(curves, tmp,
64 x1, y1, cx0, cy0, x0, y0,
65 DECREASING);
66 } else if (y0 == y1 && y0 == cy0) {
67 // Do not add horizontal lines
68 return;
69 } else {
70 Order2.insert(curves, tmp,
71 x0, y0, cx0, cy0, x1, y1,
72 INCREASING);
73 }
74 }
75
76 public static void insertCubic(Vector curves, double tmp[],
77 double x0, double y0,
78 double cx0, double cy0,
79 double cx1, double cy1,
80 double x1, double y1)
81 {
82 if (y0 > y1) {
83 Order3.insert(curves, tmp,
84 x1, y1, cx1, cy1, cx0, cy0, x0, y0,
85 DECREASING);
86 } else if (y0 == y1 && y0 == cy0 && y0 == cy1) {
87 // Do not add horizontal lines
88 return;
89 } else {
90 Order3.insert(curves, tmp,
91 x0, y0, cx0, cy0, cx1, cy1, x1, y1,
92 INCREASING);
93 }
94 }
95
96 public Curve(int direction) {
97 this.direction = direction;
98 }
99
100 public final int getDirection() {
101 return direction;
102 }
103
104 public final Curve getWithDirection(int direction) {
105 return (this.direction == direction ? this : getReversedCurve());
106 }
107
108 public static double round(double v) {
109 //return Math.rint(v*10)/10;
110 return v;
111 }
112
113 public static int orderof(double x1, double x2) {
114 if (x1 < x2) {
115 return -1;
116 }
117 if (x1 > x2) {
118 return 1;
119 }
120 return 0;
121 }
122
123 public static long signeddiffbits(double y1, double y2) {
124 return (Double.doubleToLongBits(y1) - Double.doubleToLongBits(y2));
125 }
126 public static long diffbits(double y1, double y2) {
127 return Math.abs(Double.doubleToLongBits(y1) -
128 Double.doubleToLongBits(y2));
129 }
130 public static double prev(double v) {
131 return Double.longBitsToDouble(Double.doubleToLongBits(v)-1);
132 }
133 public static double next(double v) {
134 return Double.longBitsToDouble(Double.doubleToLongBits(v)+1);
135 }
136
137 @Override
138 public String toString() {
139 return ("Curve["+
140 getOrder()+", "+
141 ("("+round(getX0())+", "+round(getY0())+"), ")+
142 controlPointString()+
143 ("("+round(getX1())+", "+round(getY1())+"), ")+
144 (direction == INCREASING ? "D" : "U")+
145 "]");
146 }
147
148 public String controlPointString() {
149 return "";
150 }
151
152 public abstract int getOrder();
153
154 public abstract double getXTop();
155 public abstract double getYTop();
156 public abstract double getXBot();
157 public abstract double getYBot();
158
159 public abstract double getXMin();
160 public abstract double getXMax();
161
162 public abstract double getX0();
163 public abstract double getY0();
164 public abstract double getX1();
165 public abstract double getY1();
166
167 public abstract double XforY(double y);
168 public abstract double TforY(double y);
169 public abstract double XforT(double t);
170 public abstract double YforT(double t);
171 public abstract double dXforT(double t, int deriv);
172 public abstract double dYforT(double t, int deriv);
173
174 public abstract double nextVertical(double t0, double t1);
175
176 public int crossingsFor(double x, double y) {
177 if (y >= getYTop() && y < getYBot()) {
178 if (x < getXMax() && (x < getXMin() || x < XforY(y))) {
179 return 1;
180 }
181 }
182 return 0;
183 }
184
185 public boolean accumulateCrossings(Crossings c) {
186 double xhi = c.getXHi();
187 if (getXMin() >= xhi) {
188 return false;
189 }
190 double xlo = c.getXLo();
191 double ylo = c.getYLo();
192 double yhi = c.getYHi();
193 double y0 = getYTop();
194 double y1 = getYBot();
195 double tstart, ystart, tend, yend;
196 if (y0 < ylo) {
197 if (y1 <= ylo) {
198 return false;
199 }
200 ystart = ylo;
201 tstart = TforY(ylo);
202 } else {
203 if (y0 >= yhi) {
204 return false;
205 }
206 ystart = y0;
207 tstart = 0;
208 }
209 if (y1 > yhi) {
210 yend = yhi;
211 tend = TforY(yhi);
212 } else {
213 yend = y1;
214 tend = 1;
215 }
216 boolean hitLo = false;
217 boolean hitHi = false;
218 while (true) {
219 double x = XforT(tstart);
220 if (x < xhi) {
221 if (hitHi || x > xlo) {
222 return true;
223 }
224 hitLo = true;
225 } else {
226 if (hitLo) {
227 return true;
228 }
229 hitHi = true;
230 }
231 if (tstart >= tend) {
232 break;
233 }
234 tstart = nextVertical(tstart, tend);
235 }
236 if (hitLo) {
237 c.record(ystart, yend, direction);
238 }
239 return false;
240 }
241
242 public abstract void enlarge(RectBounds r);
243
244 public Curve getSubCurve(double ystart, double yend) {
245 return getSubCurve(ystart, yend, direction);
246 }
247
248 public abstract Curve getReversedCurve();
249 public abstract Curve getSubCurve(double ystart, double yend, int dir);
250
251 public int compareTo(Curve that, double yrange[]) {
252 /*
253 System.out.println(this+".compareTo("+that+")");
254 System.out.println("target range = "+yrange[0]+"=>"+yrange[1]);
255 */
256 double y0 = yrange[0];
257 double y1 = yrange[1];
258 y1 = Math.min(Math.min(y1, this.getYBot()), that.getYBot());
259 if (y1 <= yrange[0]) {
260 System.err.println("this == "+this);
261 System.err.println("that == "+that);
262 System.out.println("target range = "+yrange[0]+"=>"+yrange[1]);
263 throw new InternalError("backstepping from "+yrange[0]+" to "+y1);
264 }
265 yrange[1] = y1;
266 if (this.getXMax() <= that.getXMin()) {
267 if (this.getXMin() == that.getXMax()) {
268 return 0;
269 }
270 return -1;
271 }
272 if (this.getXMin() >= that.getXMax()) {
273 return 1;
274 }
275 // Parameter s for thi(s) curve and t for tha(t) curve
276 // [st]0 = parameters for top of current section of interest
277 // [st]1 = parameters for bottom of valid range
278 // [st]h = parameters for hypothesis point
279 // [d][xy]s = valuations of thi(s) curve at sh
280 // [d][xy]t = valuations of tha(t) curve at th
281 double s0 = this.TforY(y0);
282 double ys0 = this.YforT(s0);
283 if (ys0 < y0) {
284 s0 = refineTforY(s0, y0);
285 ys0 = this.YforT(s0);
286 }
287 double s1 = this.TforY(y1);
288 if (this.YforT(s1) < y0) {
289 s1 = refineTforY(s1, y0);
290 //System.out.println("s1 problem!");
291 }
292 double t0 = that.TforY(y0);
293 double yt0 = that.YforT(t0);
294 if (yt0 < y0) {
295 t0 = that.refineTforY(t0, y0);
296 yt0 = that.YforT(t0);
297 }
298 double t1 = that.TforY(y1);
299 if (that.YforT(t1) < y0) {
300 t1 = that.refineTforY(t1, y0);
301 //System.out.println("t1 problem!");
302 }
303 double xs0 = this.XforT(s0);
304 double xt0 = that.XforT(t0);
305 double scale = Math.max(Math.abs(y0), Math.abs(y1));
306 double ymin = Math.max(scale * 1E-14, 1E-300);
307 if (fairlyClose(xs0, xt0)) {
308 double bump = ymin;
309 double maxbump = Math.min(ymin * 1E13, (y1 - y0) * .1);
310 double y = y0 + bump;
311 while (y <= y1) {
312 if (fairlyClose(this.XforY(y), that.XforY(y))) {
313 if ((bump *= 2) > maxbump) {
314 bump = maxbump;
315 }
316 } else {
317 y -= bump;
318 while (true) {
319 bump /= 2;
320 double newy = y + bump;
321 if (newy <= y) {
322 break;
323 }
324 if (fairlyClose(this.XforY(newy), that.XforY(newy))) {
325 y = newy;
326 }
327 }
328 break;
329 }
330 y += bump;
331 }
332 if (y > y0) {
333 if (y < y1) {
334 yrange[1] = y;
335 }
336 return 0;
337 }
338 }
339 //double ymin = y1 * 1E-14;
340 if (ymin <= 0) {
341 System.out.println("ymin = "+ymin);
342 }
343 /*
344 System.out.println("s range = "+s0+" to "+s1);
345 System.out.println("t range = "+t0+" to "+t1);
346 */
347 while (s0 < s1 && t0 < t1) {
348 double sh = this.nextVertical(s0, s1);
349 double xsh = this.XforT(sh);
350 double ysh = this.YforT(sh);
351 double th = that.nextVertical(t0, t1);
352 double xth = that.XforT(th);
353 double yth = that.YforT(th);
354 /*
355 System.out.println("sh = "+sh);
356 System.out.println("th = "+th);
357 */
358 try {
359 if (findIntersect(that, yrange, ymin, 0, 0,
360 s0, xs0, ys0, sh, xsh, ysh,
361 t0, xt0, yt0, th, xth, yth)) {
362 break;
363 }
364 } catch (Throwable t) {
365 System.err.println("Error: "+t);
366 System.err.println("y range was "+yrange[0]+"=>"+yrange[1]);
367 System.err.println("s y range is "+ys0+"=>"+ysh);
368 System.err.println("t y range is "+yt0+"=>"+yth);
369 System.err.println("ymin is "+ymin);
370 return 0;
371 }
372 if (ysh < yth) {
373 if (ysh > yrange[0]) {
374 if (ysh < yrange[1]) {
375 yrange[1] = ysh;
376 }
377 break;
378 }
379 s0 = sh;
380 xs0 = xsh;
381 ys0 = ysh;
382 } else {
383 if (yth > yrange[0]) {
384 if (yth < yrange[1]) {
385 yrange[1] = yth;
386 }
387 break;
388 }
389 t0 = th;
390 xt0 = xth;
391 yt0 = yth;
392 }
393 }
394 double ymid = (yrange[0] + yrange[1]) / 2;
395 /*
396 System.out.println("final this["+s0+", "+sh+", "+s1+"]");
397 System.out.println("final y["+ys0+", "+ysh+"]");
398 System.out.println("final that["+t0+", "+th+", "+t1+"]");
399 System.out.println("final y["+yt0+", "+yth+"]");
400 System.out.println("final order = "+orderof(this.XforY(ymid),
401 that.XforY(ymid)));
402 System.out.println("final range = "+yrange[0]+"=>"+yrange[1]);
403 */
404 /*
405 System.out.println("final sx = "+this.XforY(ymid));
406 System.out.println("final tx = "+that.XforY(ymid));
407 System.out.println("final order = "+orderof(this.XforY(ymid),
408 that.XforY(ymid)));
409 */
410 return orderof(this.XforY(ymid), that.XforY(ymid));
411 }
412
413 public static final double TMIN = 1E-3;
414
415 public boolean findIntersect(Curve that, double yrange[], double ymin,
416 int slevel, int tlevel,
417 double s0, double xs0, double ys0,
418 double s1, double xs1, double ys1,
419 double t0, double xt0, double yt0,
420 double t1, double xt1, double yt1)
421 {
422 /*
423 String pad = " ";
424 pad = pad+pad+pad+pad+pad;
425 pad = pad+pad;
426 System.out.println("----------------------------------------------");
427 System.out.println(pad.substring(0, slevel)+ys0);
428 System.out.println(pad.substring(0, slevel)+ys1);
429 System.out.println(pad.substring(0, slevel)+(s1-s0));
430 System.out.println("-------");
431 System.out.println(pad.substring(0, tlevel)+yt0);
432 System.out.println(pad.substring(0, tlevel)+yt1);
433 System.out.println(pad.substring(0, tlevel)+(t1-t0));
434 */
435 if (ys0 > yt1 || yt0 > ys1) {
436 return false;
437 }
438 if (Math.min(xs0, xs1) > Math.max(xt0, xt1) ||
439 Math.max(xs0, xs1) < Math.min(xt0, xt1))
440 {
441 return false;
442 }
443 // Bounding boxes intersect - back off the larger of
444 // the two subcurves by half until they stop intersecting
445 // (or until they get small enough to switch to a more
446 // intensive algorithm).
447 if (s1 - s0 > TMIN) {
448 double s = (s0 + s1) / 2;
449 double xs = this.XforT(s);
450 double ys = this.YforT(s);
451 if (s == s0 || s == s1) {
452 System.out.println("s0 = "+s0);
453 System.out.println("s1 = "+s1);
454 throw new InternalError("no s progress!");
455 }
456 if (t1 - t0 > TMIN) {
457 double t = (t0 + t1) / 2;
458 double xt = that.XforT(t);
459 double yt = that.YforT(t);
460 if (t == t0 || t == t1) {
461 System.out.println("t0 = "+t0);
462 System.out.println("t1 = "+t1);
463 throw new InternalError("no t progress!");
464 }
465 if (ys >= yt0 && yt >= ys0) {
466 if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1,
467 s0, xs0, ys0, s, xs, ys,
468 t0, xt0, yt0, t, xt, yt)) {
469 return true;
470 }
471 }
472 if (ys >= yt) {
473 if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1,
474 s0, xs0, ys0, s, xs, ys,
475 t, xt, yt, t1, xt1, yt1)) {
476 return true;
477 }
478 }
479 if (yt >= ys) {
480 if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1,
481 s, xs, ys, s1, xs1, ys1,
482 t0, xt0, yt0, t, xt, yt)) {
483 return true;
484 }
485 }
486 if (ys1 >= yt && yt1 >= ys) {
487 if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1,
488 s, xs, ys, s1, xs1, ys1,
489 t, xt, yt, t1, xt1, yt1)) {
490 return true;
491 }
492 }
493 } else {
494 if (ys >= yt0) {
495 if (findIntersect(that, yrange, ymin, slevel+1, tlevel,
496 s0, xs0, ys0, s, xs, ys,
497 t0, xt0, yt0, t1, xt1, yt1)) {
498 return true;
499 }
500 }
501 if (yt1 >= ys) {
502 if (findIntersect(that, yrange, ymin, slevel+1, tlevel,
503 s, xs, ys, s1, xs1, ys1,
504 t0, xt0, yt0, t1, xt1, yt1)) {
505 return true;
506 }
507 }
508 }
509 } else if (t1 - t0 > TMIN) {
510 double t = (t0 + t1) / 2;
511 double xt = that.XforT(t);
512 double yt = that.YforT(t);
513 if (t == t0 || t == t1) {
514 System.out.println("t0 = "+t0);
515 System.out.println("t1 = "+t1);
516 throw new InternalError("no t progress!");
517 }
518 if (yt >= ys0) {
519 if (findIntersect(that, yrange, ymin, slevel, tlevel+1,
520 s0, xs0, ys0, s1, xs1, ys1,
521 t0, xt0, yt0, t, xt, yt)) {
522 return true;
523 }
524 }
525 if (ys1 >= yt) {
526 if (findIntersect(that, yrange, ymin, slevel, tlevel+1,
527 s0, xs0, ys0, s1, xs1, ys1,
528 t, xt, yt, t1, xt1, yt1)) {
529 return true;
530 }
531 }
532 } else {
533 // No more subdivisions
534 double xlk = xs1 - xs0;
535 double ylk = ys1 - ys0;
536 double xnm = xt1 - xt0;
537 double ynm = yt1 - yt0;
538 double xmk = xt0 - xs0;
539 double ymk = yt0 - ys0;
540 double det = xnm * ylk - ynm * xlk;
541 if (det != 0) {
542 double detinv = 1 / det;
543 double s = (xnm * ymk - ynm * xmk) * detinv;
544 double t = (xlk * ymk - ylk * xmk) * detinv;
545 if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
546 s = s0 + s * (s1 - s0);
547 t = t0 + t * (t1 - t0);
548 if (s < 0 || s > 1 || t < 0 || t > 1) {
549 System.out.println("Uh oh!");
550 }
551 double y = (this.YforT(s) + that.YforT(t)) / 2;
552 if (y <= yrange[1] && y > yrange[0]) {
553 yrange[1] = y;
554 return true;
555 }
556 }
557 }
558 //System.out.println("Testing lines!");
559 }
560 return false;
561 }
562
563 public double refineTforY(double t0, double y0) {
564 double t1 = 1;
565 while (true) {
566 double th = (t0 + t1) / 2;
567 if (th == t0 || th == t1) {
568 return t1;
569 }
570 double y = YforT(th);
571 if (y < y0) {
572 t0 = th;
573 } else if (y > y0) {
574 t1 = th;
575 } else {
576 return t1;
577 }
578 }
579 }
580
581 public boolean fairlyClose(double v1, double v2) {
582 return (Math.abs(v1 - v2) <
583 Math.max(Math.abs(v1), Math.abs(v2)) * 1E-10);
584 }
585
586 public abstract int getSegment(float coords[]);
587 }