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