001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: /**
018: * @author Denis M. Kishenko
019: * @version $Revision$
020: */package org.apache.harmony.awt.gl;
021:
022: import java.awt.Shape;
023: import java.awt.geom.PathIterator;
024:
025: public class Crossing {
026:
027: /**
028: * Allowable tolerance for bounds comparison
029: */
030: static final double DELTA = 1E-5;
031:
032: /**
033: * If roots have distance less then <code>ROOT_DELTA</code> they are double
034: */
035: static final double ROOT_DELTA = 1E-10;
036:
037: /**
038: * Rectangle cross segment
039: */
040: public static final int CROSSING = 255;
041:
042: /**
043: * Unknown crossing result
044: */
045: static final int UNKNOWN = 254;
046:
047: /**
048: * Solves quadratic equation
049: * @param eqn - the coefficients of the equation
050: * @param res - the roots of the equation
051: * @return a number of roots
052: */
053: public static int solveQuad(double eqn[], double res[]) {
054: double a = eqn[2];
055: double b = eqn[1];
056: double c = eqn[0];
057: int rc = 0;
058: if (a == 0.0) {
059: if (b == 0.0) {
060: return -1;
061: }
062: res[rc++] = -c / b;
063: } else {
064: double d = b * b - 4.0 * a * c;
065: // d < 0.0
066: if (d < 0.0) {
067: return 0;
068: }
069: d = Math.sqrt(d);
070: res[rc++] = (-b + d) / (a * 2.0);
071: // d != 0.0
072: if (d != 0.0) {
073: res[rc++] = (-b - d) / (a * 2.0);
074: }
075: }
076: return fixRoots(res, rc);
077: }
078:
079: /**
080: * Solves cubic equation
081: * @param eqn - the coefficients of the equation
082: * @param res - the roots of the equation
083: * @return a number of roots
084: */
085: public static int solveCubic(double eqn[], double res[]) {
086: double d = eqn[3];
087: if (d == 0) {
088: return solveQuad(eqn, res);
089: }
090: double a = eqn[2] / d;
091: double b = eqn[1] / d;
092: double c = eqn[0] / d;
093: int rc = 0;
094:
095: double Q = (a * a - 3.0 * b) / 9.0;
096: double R = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0;
097: double Q3 = Q * Q * Q;
098: double R2 = R * R;
099: double n = -a / 3.0;
100:
101: if (R2 < Q3) {
102: double t = Math.acos(R / Math.sqrt(Q3)) / 3.0;
103: double p = 2.0 * Math.PI / 3.0;
104: double m = -2.0 * Math.sqrt(Q);
105: res[rc++] = m * Math.cos(t) + n;
106: res[rc++] = m * Math.cos(t + p) + n;
107: res[rc++] = m * Math.cos(t - p) + n;
108: } else {
109: // Debug.println("R2 >= Q3 (" + R2 + "/" + Q3 + ")");
110: double A = Math.pow(Math.abs(R) + Math.sqrt(R2 - Q3),
111: 1.0 / 3.0);
112: if (R > 0.0) {
113: A = -A;
114: }
115: // if (A == 0.0) {
116: if (-ROOT_DELTA < A && A < ROOT_DELTA) {
117: res[rc++] = n;
118: } else {
119: double B = Q / A;
120: res[rc++] = A + B + n;
121: // if (R2 == Q3) {
122: double delta = R2 - Q3;
123: if (-ROOT_DELTA < delta && delta < ROOT_DELTA) {
124: res[rc++] = -(A + B) / 2.0 + n;
125: }
126: }
127:
128: }
129: return fixRoots(res, rc);
130: }
131:
132: /**
133: * Excludes double roots. Roots are double if they lies enough close with each other.
134: * @param res - the roots
135: * @param rc - the roots count
136: * @return new roots count
137: */
138: static int fixRoots(double res[], int rc) {
139: int tc = 0;
140: for (int i = 0; i < rc; i++) {
141: out: {
142: for (int j = i + 1; j < rc; j++) {
143: if (isZero(res[i] - res[j])) {
144: break out;
145: }
146: }
147: res[tc++] = res[i];
148: }
149: }
150: return tc;
151: }
152:
153: /**
154: * QuadCurve class provides basic functionality to find curve crossing and calculating bounds
155: */
156: public static class QuadCurve {
157:
158: double ax, ay, bx, by;
159: double Ax, Ay, Bx, By;
160:
161: public QuadCurve(double x1, double y1, double cx, double cy,
162: double x2, double y2) {
163: ax = x2 - x1;
164: ay = y2 - y1;
165: bx = cx - x1;
166: by = cy - y1;
167:
168: Bx = bx + bx; // Bx = 2.0 * bx
169: Ax = ax - Bx; // Ax = ax - 2.0 * bx
170:
171: By = by + by; // By = 2.0 * by
172: Ay = ay - By; // Ay = ay - 2.0 * by
173: }
174:
175: int cross(double res[], int rc, double py1, double py2) {
176: int cross = 0;
177:
178: for (int i = 0; i < rc; i++) {
179: double t = res[i];
180:
181: // CURVE-OUTSIDE
182: if (t < -DELTA || t > 1 + DELTA) {
183: continue;
184: }
185: // CURVE-START
186: if (t < DELTA) {
187: if (py1 < 0.0 && (bx != 0.0 ? bx : ax - bx) < 0.0) {
188: cross--;
189: }
190: continue;
191: }
192: // CURVE-END
193: if (t > 1 - DELTA) {
194: if (py1 < ay && (ax != bx ? ax - bx : bx) > 0.0) {
195: cross++;
196: }
197: continue;
198: }
199: // CURVE-INSIDE
200: double ry = t * (t * Ay + By);
201: // ry = t * t * Ay + t * By
202: if (ry > py2) {
203: double rxt = t * Ax + bx;
204: // rxt = 2.0 * t * Ax + Bx = 2.0 * t * Ax + 2.0 * bx
205: if (rxt > -DELTA && rxt < DELTA) {
206: continue;
207: }
208: cross += rxt > 0.0 ? 1 : -1;
209: }
210: } // for
211:
212: return cross;
213: }
214:
215: int solvePoint(double res[], double px) {
216: double eqn[] = { -px, Bx, Ax };
217: return solveQuad(eqn, res);
218: }
219:
220: int solveExtrem(double res[]) {
221: int rc = 0;
222: if (Ax != 0.0) {
223: res[rc++] = -Bx / (Ax + Ax);
224: }
225: if (Ay != 0.0) {
226: res[rc++] = -By / (Ay + Ay);
227: }
228: return rc;
229: }
230:
231: int addBound(double bound[], int bc, double res[], int rc,
232: double minX, double maxX, boolean changeId, int id) {
233: for (int i = 0; i < rc; i++) {
234: double t = res[i];
235: if (t > -DELTA && t < 1 + DELTA) {
236: double rx = t * (t * Ax + Bx);
237: if (minX <= rx && rx <= maxX) {
238: bound[bc++] = t;
239: bound[bc++] = rx;
240: bound[bc++] = t * (t * Ay + By);
241: bound[bc++] = id;
242: if (changeId) {
243: id++;
244: }
245: }
246: }
247: }
248: return bc;
249: }
250:
251: }
252:
253: /**
254: * CubicCurve class provides basic functionality to find curve crossing and calculating bounds
255: */
256: public static class CubicCurve {
257:
258: double ax, ay, bx, by, cx, cy;
259: double Ax, Ay, Bx, By, Cx, Cy;
260: double Ax3, Bx2;
261:
262: public CubicCurve(double x1, double y1, double cx1, double cy1,
263: double cx2, double cy2, double x2, double y2) {
264: ax = x2 - x1;
265: ay = y2 - y1;
266: bx = cx1 - x1;
267: by = cy1 - y1;
268: cx = cx2 - x1;
269: cy = cy2 - y1;
270:
271: Cx = bx + bx + bx; // Cx = 3.0 * bx
272: Bx = cx + cx + cx - Cx - Cx; // Bx = 3.0 * cx - 6.0 * bx
273: Ax = ax - Bx - Cx; // Ax = ax - 3.0 * cx + 3.0 * bx
274:
275: Cy = by + by + by; // Cy = 3.0 * by
276: By = cy + cy + cy - Cy - Cy; // By = 3.0 * cy - 6.0 * by
277: Ay = ay - By - Cy; // Ay = ay - 3.0 * cy + 3.0 * by
278:
279: Ax3 = Ax + Ax + Ax;
280: Bx2 = Bx + Bx;
281: }
282:
283: int cross(double res[], int rc, double py1, double py2) {
284: int cross = 0;
285: for (int i = 0; i < rc; i++) {
286: double t = res[i];
287:
288: // CURVE-OUTSIDE
289: if (t < -DELTA || t > 1 + DELTA) {
290: continue;
291: }
292: // CURVE-START
293: if (t < DELTA) {
294: if (py1 < 0.0
295: && (bx != 0.0 ? bx : (cx != bx ? cx - bx
296: : ax - cx)) < 0.0) {
297: cross--;
298: }
299: continue;
300: }
301: // CURVE-END
302: if (t > 1 - DELTA) {
303: if (py1 < ay
304: && (ax != cx ? ax - cx : (cx != bx ? cx
305: - bx : bx)) > 0.0) {
306: cross++;
307: }
308: continue;
309: }
310: // CURVE-INSIDE
311: double ry = t * (t * (t * Ay + By) + Cy);
312: // ry = t * t * t * Ay + t * t * By + t * Cy
313: if (ry > py2) {
314: double rxt = t * (t * Ax3 + Bx2) + Cx;
315: // rxt = 3.0 * t * t * Ax + 2.0 * t * Bx + Cx
316: if (rxt > -DELTA && rxt < DELTA) {
317: rxt = t * (Ax3 + Ax3) + Bx2;
318: // rxt = 6.0 * t * Ax + 2.0 * Bx
319: if (rxt < -DELTA || rxt > DELTA) {
320: // Inflection point
321: continue;
322: }
323: rxt = ax;
324: }
325: cross += rxt > 0.0 ? 1 : -1;
326: }
327: } //for
328:
329: return cross;
330: }
331:
332: int solvePoint(double res[], double px) {
333: double eqn[] = { -px, Cx, Bx, Ax };
334: return solveCubic(eqn, res);
335: }
336:
337: int solveExtremX(double res[]) {
338: double eqn[] = { Cx, Bx2, Ax3 };
339: return solveQuad(eqn, res);
340: }
341:
342: int solveExtremY(double res[]) {
343: double eqn[] = { Cy, By + By, Ay + Ay + Ay };
344: return solveQuad(eqn, res);
345: }
346:
347: int addBound(double bound[], int bc, double res[], int rc,
348: double minX, double maxX, boolean changeId, int id) {
349: for (int i = 0; i < rc; i++) {
350: double t = res[i];
351: if (t > -DELTA && t < 1 + DELTA) {
352: double rx = t * (t * (t * Ax + Bx) + Cx);
353: if (minX <= rx && rx <= maxX) {
354: bound[bc++] = t;
355: bound[bc++] = rx;
356: bound[bc++] = t * (t * (t * Ay + By) + Cy);
357: bound[bc++] = id;
358: if (changeId) {
359: id++;
360: }
361: }
362: }
363: }
364: return bc;
365: }
366:
367: }
368:
369: /**
370: * Returns how many times ray from point (x,y) cross line.
371: */
372: public static int crossLine(double x1, double y1, double x2,
373: double y2, double x, double y) {
374:
375: // LEFT/RIGHT/UP/EMPTY
376: if ((x < x1 && x < x2) || (x > x1 && x > x2)
377: || (y > y1 && y > y2) || (x1 == x2)) {
378: return 0;
379: }
380:
381: // DOWN
382: if (y < y1 && y < y2) {
383: } else {
384: // INSIDE
385: if ((y2 - y1) * (x - x1) / (x2 - x1) <= y - y1) {
386: // INSIDE-UP
387: return 0;
388: }
389: }
390:
391: // START
392: if (x == x1) {
393: return x1 < x2 ? 0 : -1;
394: }
395:
396: // END
397: if (x == x2) {
398: return x1 < x2 ? 1 : 0;
399: }
400:
401: // INSIDE-DOWN
402: return x1 < x2 ? 1 : -1;
403: }
404:
405: /**
406: * Returns how many times ray from point (x,y) cross quard curve
407: */
408: public static int crossQuad(double x1, double y1, double cx,
409: double cy, double x2, double y2, double x, double y) {
410:
411: // LEFT/RIGHT/UP/EMPTY
412: if ((x < x1 && x < cx && x < x2)
413: || (x > x1 && x > cx && x > x2)
414: || (y > y1 && y > cy && y > y2)
415: || (x1 == cx && cx == x2)) {
416: return 0;
417: }
418:
419: // DOWN
420: if (y < y1 && y < cy && y < y2 && x != x1 && x != x2) {
421: if (x1 < x2) {
422: return x1 < x && x < x2 ? 1 : 0;
423: }
424: return x2 < x && x < x1 ? -1 : 0;
425: }
426:
427: // INSIDE
428: QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2);
429: double px = x - x1;
430: double py = y - y1;
431: double res[] = new double[3];
432: int rc = c.solvePoint(res, px);
433:
434: return c.cross(res, rc, py, py);
435: }
436:
437: /**
438: * Returns how many times ray from point (x,y) cross cubic curve
439: */
440: public static int crossCubic(double x1, double y1, double cx1,
441: double cy1, double cx2, double cy2, double x2, double y2,
442: double x, double y) {
443:
444: // LEFT/RIGHT/UP/EMPTY
445: if ((x < x1 && x < cx1 && x < cx2 && x < x2)
446: || (x > x1 && x > cx1 && x > cx2 && x > x2)
447: || (y > y1 && y > cy1 && y > cy2 && y > y2)
448: || (x1 == cx1 && cx1 == cx2 && cx2 == x2)) {
449: return 0;
450: }
451:
452: // DOWN
453: if (y < y1 && y < cy1 && y < cy2 && y < y2 && x != x1
454: && x != x2) {
455: if (x1 < x2) {
456: return x1 < x && x < x2 ? 1 : 0;
457: }
458: return x2 < x && x < x1 ? -1 : 0;
459: }
460:
461: // INSIDE
462: CubicCurve c = new CubicCurve(x1, y1, cx1, cy1, cx2, cy2, x2,
463: y2);
464: double px = x - x1;
465: double py = y - y1;
466: double res[] = new double[3];
467: int rc = c.solvePoint(res, px);
468: return c.cross(res, rc, py, py);
469: }
470:
471: /**
472: * Returns how many times ray from point (x,y) cross path
473: */
474: public static int crossPath(PathIterator p, double x, double y) {
475: int cross = 0;
476: double mx, my, cx, cy;
477: mx = my = cx = cy = 0.0;
478: double coords[] = new double[6];
479:
480: while (!p.isDone()) {
481: switch (p.currentSegment(coords)) {
482: case PathIterator.SEG_MOVETO:
483: if (cx != mx || cy != my) {
484: cross += crossLine(cx, cy, mx, my, x, y);
485: }
486: mx = cx = coords[0];
487: my = cy = coords[1];
488: break;
489: case PathIterator.SEG_LINETO:
490: cross += crossLine(cx, cy, cx = coords[0],
491: cy = coords[1], x, y);
492: break;
493: case PathIterator.SEG_QUADTO:
494: cross += crossQuad(cx, cy, coords[0], coords[1],
495: cx = coords[2], cy = coords[3], x, y);
496: break;
497: case PathIterator.SEG_CUBICTO:
498: cross += crossCubic(cx, cy, coords[0], coords[1],
499: coords[2], coords[3], cx = coords[4],
500: cy = coords[5], x, y);
501: break;
502: case PathIterator.SEG_CLOSE:
503: if (cy != my || cx != mx) {
504: cross += crossLine(cx, cy, cx = mx, cy = my, x, y);
505: }
506: break;
507: }
508:
509: // checks if the point (x,y) is the vertex of shape with PathIterator p
510: if (x == cx && y == cy) {
511: cross = 0;
512: cy = my;
513: break;
514: }
515: p.next();
516: }
517: if (cy != my) {
518: cross += crossLine(cx, cy, mx, my, x, y);
519: }
520: return cross;
521: }
522:
523: /**
524: * Returns how many times ray from point (x,y) cross shape
525: */
526: public static int crossShape(Shape s, double x, double y) {
527: if (!s.getBounds2D().contains(x, y)) {
528: return 0;
529: }
530: return crossPath(s.getPathIterator(null), x, y);
531: }
532:
533: /**
534: * Returns true if value enough small
535: */
536: public static boolean isZero(double val) {
537: return -DELTA < val && val < DELTA;
538: }
539:
540: /**
541: * Sort bound array
542: */
543: static void sortBound(double bound[], int bc) {
544: for (int i = 0; i < bc - 4; i += 4) {
545: int k = i;
546: for (int j = i + 4; j < bc; j += 4) {
547: if (bound[k] > bound[j]) {
548: k = j;
549: }
550: }
551: if (k != i) {
552: double tmp = bound[i];
553: bound[i] = bound[k];
554: bound[k] = tmp;
555: tmp = bound[i + 1];
556: bound[i + 1] = bound[k + 1];
557: bound[k + 1] = tmp;
558: tmp = bound[i + 2];
559: bound[i + 2] = bound[k + 2];
560: bound[k + 2] = tmp;
561: tmp = bound[i + 3];
562: bound[i + 3] = bound[k + 3];
563: bound[k + 3] = tmp;
564: }
565: }
566: }
567:
568: /**
569: * Returns are bounds intersect or not intersect rectangle
570: */
571: static int crossBound(double bound[], int bc, double py1, double py2) {
572:
573: // LEFT/RIGHT
574: if (bc == 0) {
575: return 0;
576: }
577:
578: // Check Y coordinate
579: int up = 0;
580: int down = 0;
581: for (int i = 2; i < bc; i += 4) {
582: if (bound[i] < py1) {
583: up++;
584: continue;
585: }
586: if (bound[i] > py2) {
587: down++;
588: continue;
589: }
590: return CROSSING;
591: }
592:
593: // UP
594: if (down == 0) {
595: return 0;
596: }
597:
598: if (up != 0) {
599: // bc >= 2
600: sortBound(bound, bc);
601: boolean sign = bound[2] > py2;
602: for (int i = 6; i < bc; i += 4) {
603: boolean sign2 = bound[i] > py2;
604: if (sign != sign2 && bound[i + 1] != bound[i - 3]) {
605: return CROSSING;
606: }
607: sign = sign2;
608: }
609: }
610: return UNKNOWN;
611: }
612:
613: /**
614: * Returns how many times rectangle stripe cross line or the are intersect
615: */
616: public static int intersectLine(double x1, double y1, double x2,
617: double y2, double rx1, double ry1, double rx2, double ry2) {
618:
619: // LEFT/RIGHT/UP
620: if ((rx2 < x1 && rx2 < x2) || (rx1 > x1 && rx1 > x2)
621: || (ry1 > y1 && ry1 > y2)) {
622: return 0;
623: }
624:
625: // DOWN
626: if (ry2 < y1 && ry2 < y2) {
627: } else {
628:
629: // INSIDE
630: if (x1 == x2) {
631: return CROSSING;
632: }
633:
634: // Build bound
635: double bx1, bx2;
636: if (x1 < x2) {
637: bx1 = x1 < rx1 ? rx1 : x1;
638: bx2 = x2 < rx2 ? x2 : rx2;
639: } else {
640: bx1 = x2 < rx1 ? rx1 : x2;
641: bx2 = x1 < rx2 ? x1 : rx2;
642: }
643: double k = (y2 - y1) / (x2 - x1);
644: double by1 = k * (bx1 - x1) + y1;
645: double by2 = k * (bx2 - x1) + y1;
646:
647: // BOUND-UP
648: if (by1 < ry1 && by2 < ry1) {
649: return 0;
650: }
651:
652: // BOUND-DOWN
653: if (by1 > ry2 && by2 > ry2) {
654: } else {
655: return CROSSING;
656: }
657: }
658:
659: // EMPTY
660: if (x1 == x2) {
661: return 0;
662: }
663:
664: // CURVE-START
665: if (rx1 == x1) {
666: return x1 < x2 ? 0 : -1;
667: }
668:
669: // CURVE-END
670: if (rx1 == x2) {
671: return x1 < x2 ? 1 : 0;
672: }
673:
674: if (x1 < x2) {
675: return x1 < rx1 && rx1 < x2 ? 1 : 0;
676: }
677: return x2 < rx1 && rx1 < x1 ? -1 : 0;
678:
679: }
680:
681: /**
682: * Returns how many times rectangle stripe cross quad curve or the are intersect
683: */
684: public static int intersectQuad(double x1, double y1, double cx,
685: double cy, double x2, double y2, double rx1, double ry1,
686: double rx2, double ry2) {
687:
688: // LEFT/RIGHT/UP ------------------------------------------------------
689: if ((rx2 < x1 && rx2 < cx && rx2 < x2)
690: || (rx1 > x1 && rx1 > cx && rx1 > x2)
691: || (ry1 > y1 && ry1 > cy && ry1 > y2)) {
692: return 0;
693: }
694:
695: // DOWN ---------------------------------------------------------------
696: if (ry2 < y1 && ry2 < cy && ry2 < y2 && rx1 != x1 && rx1 != x2) {
697: if (x1 < x2) {
698: return x1 < rx1 && rx1 < x2 ? 1 : 0;
699: }
700: return x2 < rx1 && rx1 < x1 ? -1 : 0;
701: }
702:
703: // INSIDE -------------------------------------------------------------
704: QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2);
705: double px1 = rx1 - x1;
706: double py1 = ry1 - y1;
707: double px2 = rx2 - x1;
708: double py2 = ry2 - y1;
709:
710: double res1[] = new double[3];
711: double res2[] = new double[3];
712: int rc1 = c.solvePoint(res1, px1);
713: int rc2 = c.solvePoint(res2, px2);
714:
715: // INSIDE-LEFT/RIGHT
716: if (rc1 == 0 && rc2 == 0) {
717: return 0;
718: }
719:
720: // Build bound --------------------------------------------------------
721: double minX = px1 - DELTA;
722: double maxX = px2 + DELTA;
723: double bound[] = new double[28];
724: int bc = 0;
725: // Add roots
726: bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0);
727: bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1);
728: // Add extremal points`
729: rc2 = c.solveExtrem(res2);
730: bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2);
731: // Add start and end
732: if (rx1 < x1 && x1 < rx2) {
733: bound[bc++] = 0.0;
734: bound[bc++] = 0.0;
735: bound[bc++] = 0.0;
736: bound[bc++] = 4;
737: }
738: if (rx1 < x2 && x2 < rx2) {
739: bound[bc++] = 1.0;
740: bound[bc++] = c.ax;
741: bound[bc++] = c.ay;
742: bound[bc++] = 5;
743: }
744: // End build bound ----------------------------------------------------
745:
746: int cross = crossBound(bound, bc, py1, py2);
747: if (cross != UNKNOWN) {
748: return cross;
749: }
750: return c.cross(res1, rc1, py1, py2);
751: }
752:
753: /**
754: * Returns how many times rectangle stripe cross cubic curve or the are intersect
755: */
756: public static int intersectCubic(double x1, double y1, double cx1,
757: double cy1, double cx2, double cy2, double x2, double y2,
758: double rx1, double ry1, double rx2, double ry2) {
759:
760: // LEFT/RIGHT/UP
761: if ((rx2 < x1 && rx2 < cx1 && rx2 < cx2 && rx2 < x2)
762: || (rx1 > x1 && rx1 > cx1 && rx1 > cx2 && rx1 > x2)
763: || (ry1 > y1 && ry1 > cy1 && ry1 > cy2 && ry1 > y2)) {
764: return 0;
765: }
766:
767: // DOWN
768: if (ry2 < y1 && ry2 < cy1 && ry2 < cy2 && ry2 < y2 && rx1 != x1
769: && rx1 != x2) {
770: if (x1 < x2) {
771: return x1 < rx1 && rx1 < x2 ? 1 : 0;
772: }
773: return x2 < rx1 && rx1 < x1 ? -1 : 0;
774: }
775:
776: // INSIDE
777: CubicCurve c = new CubicCurve(x1, y1, cx1, cy1, cx2, cy2, x2,
778: y2);
779: double px1 = rx1 - x1;
780: double py1 = ry1 - y1;
781: double px2 = rx2 - x1;
782: double py2 = ry2 - y1;
783:
784: double res1[] = new double[3];
785: double res2[] = new double[3];
786: int rc1 = c.solvePoint(res1, px1);
787: int rc2 = c.solvePoint(res2, px2);
788:
789: // LEFT/RIGHT
790: if (rc1 == 0 && rc2 == 0) {
791: return 0;
792: }
793:
794: double minX = px1 - DELTA;
795: double maxX = px2 + DELTA;
796:
797: // Build bound --------------------------------------------------------
798: double bound[] = new double[40];
799: int bc = 0;
800: // Add roots
801: bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0);
802: bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1);
803: // Add extrimal points
804: rc2 = c.solveExtremX(res2);
805: bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2);
806: rc2 = c.solveExtremY(res2);
807: bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 4);
808: // Add start and end
809: if (rx1 < x1 && x1 < rx2) {
810: bound[bc++] = 0.0;
811: bound[bc++] = 0.0;
812: bound[bc++] = 0.0;
813: bound[bc++] = 6;
814: }
815: if (rx1 < x2 && x2 < rx2) {
816: bound[bc++] = 1.0;
817: bound[bc++] = c.ax;
818: bound[bc++] = c.ay;
819: bound[bc++] = 7;
820: }
821: // End build bound ----------------------------------------------------
822:
823: int cross = crossBound(bound, bc, py1, py2);
824: if (cross != UNKNOWN) {
825: return cross;
826: }
827: return c.cross(res1, rc1, py1, py2);
828: }
829:
830: /**
831: * Returns how many times rectangle stripe cross path or the are intersect
832: */
833: public static int intersectPath(PathIterator p, double x, double y,
834: double w, double h) {
835:
836: int cross = 0;
837: int count;
838: double mx, my, cx, cy;
839: mx = my = cx = cy = 0.0;
840: double coords[] = new double[6];
841:
842: double rx1 = x;
843: double ry1 = y;
844: double rx2 = x + w;
845: double ry2 = y + h;
846:
847: while (!p.isDone()) {
848: count = 0;
849: switch (p.currentSegment(coords)) {
850: case PathIterator.SEG_MOVETO:
851: if (cx != mx || cy != my) {
852: count = intersectLine(cx, cy, mx, my, rx1, ry1,
853: rx2, ry2);
854: }
855: mx = cx = coords[0];
856: my = cy = coords[1];
857: break;
858: case PathIterator.SEG_LINETO:
859: count = intersectLine(cx, cy, cx = coords[0],
860: cy = coords[1], rx1, ry1, rx2, ry2);
861: break;
862: case PathIterator.SEG_QUADTO:
863: count = intersectQuad(cx, cy, coords[0], coords[1],
864: cx = coords[2], cy = coords[3], rx1, ry1, rx2,
865: ry2);
866: break;
867: case PathIterator.SEG_CUBICTO:
868: count = intersectCubic(cx, cy, coords[0], coords[1],
869: coords[2], coords[3], cx = coords[4],
870: cy = coords[5], rx1, ry1, rx2, ry2);
871: break;
872: case PathIterator.SEG_CLOSE:
873: if (cy != my || cx != mx) {
874: count = intersectLine(cx, cy, mx, my, rx1, ry1,
875: rx2, ry2);
876: }
877: cx = mx;
878: cy = my;
879: break;
880: }
881: if (count == CROSSING) {
882: return CROSSING;
883: }
884: cross += count;
885: p.next();
886: }
887: if (cy != my) {
888: count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
889: if (count == CROSSING) {
890: return CROSSING;
891: }
892: cross += count;
893: }
894: return cross;
895: }
896:
897: /**
898: * Returns how many times rectangle stripe cross shape or the are intersect
899: */
900: public static int intersectShape(Shape s, double x, double y,
901: double w, double h) {
902: if (!s.getBounds2D().intersects(x, y, w, h)) {
903: return 0;
904: }
905: return intersectPath(s.getPathIterator(null), x, y, w, h);
906: }
907:
908: /**
909: * Returns true if cross count correspond inside location for non zero path rule
910: */
911: public static boolean isInsideNonZero(int cross) {
912: return cross != 0;
913: }
914:
915: /**
916: * Returns true if cross count correspond inside location for even-odd path rule
917: */
918: public static boolean isInsideEvenOdd(int cross) {
919: return (cross & 1) != 0;
920: }
921: }
|