20package com.jogamp.math.geom.plane;
22import com.jogamp.math.FloatUtil;
29 static final float DELTA = (float) 1E-5;
34 static final float ROOT_DELTA = (float) 1E-10;
39 public static final int CROSSING = 255;
44 static final int UNKNOWN = 254;
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];
63 float d = b * b - 4.0f * a * c;
68 d = FloatUtil.sqrt(d);
69 res[rc++] = (- b + d) / (a * 2.0f);
72 res[rc++] = (- b - d) / (a * 2.0f);
75 return fixRoots(res, rc);
84 public static int solveCubic(
final float eqn[],
final float res[]) {
85 final float d = eqn[3];
87 return solveQuad(eqn, res);
89 final float a = eqn[2] / d;
90 final float b = eqn[1] / d;
91 final float c = eqn[0] / d;
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;
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;
109 float A = FloatUtil.pow(Math.abs(R) + FloatUtil.sqrt(R2 - Q3), 1.0f / 3.0f);
114 if (-ROOT_DELTA < A && A < ROOT_DELTA) {
117 final float B = Q / A;
118 res[rc++] = A + B + n;
120 final float delta = R2 - Q3;
121 if (-ROOT_DELTA < delta && delta < ROOT_DELTA) {
122 res[rc++] = - (A + B) / 2.0f + n;
127 return fixRoots(res, rc);
136 static int fixRoots(
final float res[],
final int rc) {
138 for(
int i = 0; i < rc; i++) {
140 for(
int j = i + 1; j < rc; j++) {
141 if (isZero(res[i] - res[j])) {
156 float ax, ay, bx, by;
157 float Ax, Ay, Bx, By;
159 public QuadCurve(
final float x1,
final float y1,
final float cx,
final float cy,
final float x2,
final float y2) {
172 int cross(
final float res[],
final int rc,
final float py1,
final float py2) {
175 for (
int i = 0; i < rc; i++) {
176 final float t = res[i];
179 if (t < -DELTA || t > 1 + DELTA) {
184 if (py1 < 0.0 && (bx != 0.0 ? bx : ax - bx) < 0.0) {
192 if (py1 < ay && (ax != bx ? ax - bx : bx) > 0.0) {
198 final float ry = t * (t * Ay + By);
201 final float rxt = t * Ax + bx;
203 if (rxt > -DELTA && rxt < DELTA) {
206 cross += rxt > 0.0 ? 1 : -1;
213 int solvePoint(
final float res[],
final float px) {
214 final float eqn[] = {-px, Bx, Ax};
215 return solveQuad(eqn, res);
218 int solveExtrem(
final float res[]) {
221 res[rc++] = - Bx / (Ax + Ax);
224 res[rc++] = - By / (Ay + Ay);
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) {
237 bound[bc++] = t * (t * Ay + By);
255 float ax, ay, bx, by, cx, cy;
256 float Ax, Ay, Bx, By, Cx, Cy;
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) {
268 Bx = cx + cx + cx - Cx - Cx;
272 By = cy + cy + cy - Cy - Cy;
279 int cross(
final float res[],
final int rc,
final float py1,
final float py2) {
281 for (
int i = 0; i < rc; i++) {
282 final float t = res[i];
285 if (t < -DELTA || t > 1 + DELTA) {
291 if (py1 < 0.0 && (bx != 0.0 ? bx : (cx != bx ? cx - bx : ax - cx)) < 0.0) {
298 if (py1 < ay && (ax != cx ? ax - cx : (cx != bx ? cx - bx : bx)) > 0.0) {
304 final float ry = t * (t * (t * Ay + By) + Cy);
307 float rxt = t * (t * Ax3 + Bx2) + Cx;
309 if (rxt > -DELTA && rxt < DELTA) {
310 rxt = t * (Ax3 + Ax3) + Bx2;
312 if (rxt < -DELTA || rxt > DELTA) {
318 cross += rxt > 0.0 ? 1 : -1;
325 int solvePoint(
final float res[],
final float px) {
326 final float eqn[] = {-px, Cx, Bx, Ax};
327 return solveCubic(eqn, res);
330 int solveExtremX(
final float res[]) {
331 final float eqn[] = {Cx, Bx2, Ax3};
332 return solveQuad(eqn, res);
335 int solveExtremY(
final float res[]) {
336 final float eqn[] = {Cy, By + By, Ay + Ay + Ay};
337 return solveQuad(eqn, res);
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) {
348 bound[bc++] = t * (t * (t * Ay + By) + Cy);
364 public static int crossLine(
final float x1,
final float y1,
final float x2,
final float y2,
final float x,
final float y) {
367 if ((x < x1 && x < x2) ||
368 (x > x1 && x > x2) ||
369 (y > y1 && y > y2) ||
376 if (y < y1 && y < y2) {
379 if ((y2 - y1) * (x - x1) / (x2 - x1) <= y - y1) {
387 return x1 < x2 ? 0 : -1;
392 return x1 < x2 ? 1 : 0;
396 return x1 < x2 ? 1 : -1;
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) {
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))
414 if (y < y1 && y < cy && y < y2 && x != x1 && x != x2) {
416 return x1 < x && x < x2 ? 1 : 0;
418 return x2 < x && x < x1 ? -1 : 0;
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);
428 return c.cross(res, rc, py, py);
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) {
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))
446 if (y < y1 && y < cy1 && y < cy2 && y < y2 && x != x1 && x != x2) {
448 return x1 < x && x < x2 ? 1 : 0;
450 return x2 < x && x < x1 ? -1 : 0;
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);
465 public static int crossPath(
final Path2F.Iterator p,
final float x,
final float y) {
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) {
475 if (cx != mx || cy != my) {
476 cross += crossLine(cx, cy, mx, my, x, y);
478 mx = cx = points[idx+0];
479 my = cy = points[idx+1];
482 cross += crossLine(cx, cy, cx = points[idx+0], cy = points[idx+1], x, y);
485 cross += crossQuad(cx, cy, points[idx+0], points[idx+1], cx = points[idx+2], cy = points[idx+3], x, y);
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);
491 if (cy != my || cx != mx) {
492 cross += crossLine(cx, cy, cx = mx, cy = my, x, y);
498 if (x == cx && y == cy) {
505 cross += crossLine(cx, cy, mx, my, x, y);
513 public static int crossShape(
final Path2F s,
final float x,
final float y) {
514 if (!s.getBounds2D().contains(x, y)) {
517 return crossPath(s.iterator(
null), x, y);
523 public static boolean isZero(
final float val) {
524 return -DELTA < val && val < DELTA;
530 static void sortBound(
final float bound[],
final int bc) {
531 for(
int i = 0; i < bc - 4; i += 4) {
533 for(
int j = i + 4; j < bc; j += 4) {
534 if (bound[k] > bound[j]) {
539 float tmp = bound[i];
543 bound[i + 1] = bound[k + 1];
546 bound[i + 2] = bound[k + 2];
549 bound[i + 3] = bound[k + 3];
558 static int crossBound(
final float bound[],
final int bc,
final float py1,
final float py2) {
568 for(
int i = 2; i < bc; i += 4) {
569 if (bound[i] < py1) {
573 if (bound[i] > py2) {
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]) {
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) {
606 if ((rx2 < x1 && rx2 < x2) ||
607 (rx1 > x1 && rx1 > x2) ||
608 (ry1 > y1 && ry1 > y2))
614 if (ry2 < y1 && ry2 < y2) {
625 bx1 = x1 < rx1 ? rx1 : x1;
626 bx2 = x2 < rx2 ? x2 : rx2;
628 bx1 = x2 < rx1 ? rx1 : x2;
629 bx2 = x1 < rx2 ? x1 : rx2;
631 final float k = (y2 - y1) / (x2 - x1);
632 final float by1 = k * (bx1 - x1) + y1;
633 final float by2 = k * (bx2 - x1) + y1;
636 if (by1 < ry1 && by2 < ry1) {
641 if (by1 > ry2 && by2 > ry2) {
654 return x1 < x2 ? 0 : -1;
659 return x1 < x2 ? 1 : 0;
663 return x1 < rx1 && rx1 < x2 ? 1 : 0;
665 return x2 < rx1 && rx1 < x1 ? -1 : 0;
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) {
675 if ((rx2 < x1 && rx2 < cx && rx2 < x2) ||
676 (rx1 > x1 && rx1 > cx && rx1 > x2) ||
677 (ry1 > y1 && ry1 > cy && ry1 > y2))
683 if (ry2 < y1 && ry2 < cy && ry2 < y2 && rx1 != x1 && rx1 != x2) {
685 return x1 < rx1 && rx1 < x2 ? 1 : 0;
687 return x2 < rx1 && rx1 < x1 ? -1 : 0;
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;
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);
703 if (rc1 == 0 && rc2 == 0) {
708 final float minX = px1 - DELTA;
709 final float maxX = px2 + DELTA;
710 final float bound[] =
new float[28];
713 bc = c.addBound(bound, bc, res1, rc1, minX, maxX,
false, 0);
714 bc = c.addBound(bound, bc, res2, rc2, minX, maxX,
false, 1);
716 rc2 = c.solveExtrem(res2);
717 bc = c.addBound(bound, bc, res2, rc2, minX, maxX,
true, 2);
719 if (rx1 < x1 && x1 < rx2) {
725 if (rx1 < x2 && x2 < rx2) {
733 final int cross = crossBound(bound, bc, py1, py2);
734 if (cross != UNKNOWN) {
737 return c.cross(res1, rc1, py1, py2);
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) {
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))
754 if (ry2 < y1 && ry2 < cy1 && ry2 < cy2 && ry2 < y2 && rx1 != x1 && rx1 != x2) {
756 return x1 < rx1 && rx1 < x2 ? 1 : 0;
758 return x2 < rx1 && rx1 < x1 ? -1 : 0;
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;
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);
774 if (rc1 == 0 && rc2 == 0) {
778 final float minX = px1 - DELTA;
779 final float maxX = px2 + DELTA;
782 final float bound[] =
new float[40];
785 bc = c.addBound(bound, bc, res1, rc1, minX, maxX,
false, 0);
786 bc = c.addBound(bound, bc, res2, rc2, minX, maxX,
false, 1);
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);
793 if (rx1 < x1 && x1 < rx2) {
799 if (rx1 < x2 && x2 < rx2) {
807 final int cross = crossBound(bound, bc, py1, py2);
808 if (cross != UNKNOWN) {
811 return c.cross(res1, rc1, py1, py2);
817 public static int intersectPath(
final Path2F.Iterator p,
final float x,
final float y,
final float w,
final float h) {
821 float mx, my, cx, cy;
822 mx = my = cx = cy = 0.0f;
826 final float rx2 = x + w;
827 final float ry2 = y + h;
829 final float[] points = p.points();
831 while ( p.hasNext() ) {
832 final int idx = p.index();
833 final Path2F.SegmentType segmentType = p.next();
835 switch (segmentType) {
837 if (cx != mx || cy != my) {
838 count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
840 mx = cx = points[idx+0];
841 my = cy = points[idx+1];
844 count = intersectLine(cx, cy, cx = points[idx+0], cy = points[idx+1], rx1, ry1, rx2, ry2);
847 count = intersectQuad(cx, cy, points[idx+0], points[idx+1], cx = points[idx+2], cy = points[idx+3], rx1, ry1, rx2, ry2);
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);
853 if (cy != my || cx != mx) {
854 count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
860 if (count == CROSSING) {
866 count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
867 if (count == CROSSING) {
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)) {
882 return intersectPath(s.iterator(
null), x, y, w, h);
888 public static boolean isInsideNonZero(
final int cross) {
895 public static boolean isInsideEvenOdd(
final int cross) {
896 return (cross & 1) != 0;
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)