19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * contributor license agreements. See the NOTICE file distributed with 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * this work for additional information regarding copyright ownership. 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * (the "License"); you may not use this file except in compliance with 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the License. You may obtain a copy of the License at 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * See the License for the specific language governing permissions and 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * limitations under the License. 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/** 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @author Denis M. Kishenko 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @version $Revision$ 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpackage org.apache.harmony.awt.gl; 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport java.awt.Shape; 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport java.awt.geom.PathIterator; 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpublic class Crossing { 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Allowable tolerance for bounds comparison 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static final double DELTA = 1E-5; 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * If roots have distance less then <code>ROOT_DELTA</code> they are double 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static final double ROOT_DELTA = 1E-10; 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Rectangle cross segment 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static final int CROSSING = 255; 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unknown crossing result 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static final int UNKNOWN = 254; 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Solves quadratic equation 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param eqn - the coefficients of the equation 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param res - the roots of the equation 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return a number of roots 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int solveQuad(double eqn[], double res[]) { 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double a = eqn[2]; 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double b = eqn[1]; 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double c = eqn[0]; 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc = 0; 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (a == 0.0) { 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (b == 0.0) { 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return -1; 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = -c / b; 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double d = b * b - 4.0 * a * c; 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // d < 0.0 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (d < 0.0) { 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project d = Math.sqrt(d); 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = (- b + d) / (a * 2.0); 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // d != 0.0 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (d != 0.0) { 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = (- b - d) / (a * 2.0); 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return fixRoots(res, rc); 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Solves cubic equation 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param eqn - the coefficients of the equation 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param res - the roots of the equation 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return a number of roots 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int solveCubic(double eqn[], double res[]) { 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double d = eqn[3]; 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (d == 0) { 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return solveQuad(eqn, res); 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double a = eqn[2] / d; 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double b = eqn[1] / d; 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double c = eqn[0] / d; 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc = 0; 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double Q = (a * a - 3.0 * b) / 9.0; 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double R = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0; 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double Q3 = Q * Q * Q; 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double R2 = R * R; 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double n = - a / 3.0; 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (R2 < Q3) { 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double t = Math.acos(R / Math.sqrt(Q3)) / 3.0; 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double p = 2.0 * Math.PI / 3.0; 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double m = -2.0 * Math.sqrt(Q); 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = m * Math.cos(t) + n; 1079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = m * Math.cos(t + p) + n; 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = m * Math.cos(t - p) + n; 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// Debug.println("R2 >= Q3 (" + R2 + "/" + Q3 + ")"); 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double A = Math.pow(Math.abs(R) + Math.sqrt(R2 - Q3), 1.0 / 3.0); 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (R > 0.0) { 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project A = -A; 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// if (A == 0.0) { 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (-ROOT_DELTA < A && A < ROOT_DELTA) { 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = n; 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double B = Q / A; 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = A + B + n; 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// if (R2 == Q3) { 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double delta = R2 - Q3; 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (-ROOT_DELTA < delta && delta < ROOT_DELTA) { 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = - (A + B) / 2.0 + n; 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return fixRoots(res, rc); 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Excludes double roots. Roots are double if they lies enough close with each other. 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param res - the roots 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param rc - the roots count 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return new roots count 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static int fixRoots(double res[], int rc) { 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int tc = 0; 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int i = 0; i < rc; i++) { 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project out: { 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int j = i + 1; j < rc; j++) { 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (isZero(res[i] - res[j])) { 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break out; 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[tc++] = res[i]; 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return tc; 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * QuadCurve class provides basic functionality to find curve crossing and calculating bounds 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static class QuadCurve { 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double ax, ay, bx, by; 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double Ax, Ay, Bx, By; 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public QuadCurve(double x1, double y1, double cx, double cy, double x2, double y2) { 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ax = x2 - x1; 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ay = y2 - y1; 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bx = cx - x1; 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project by = cy - y1; 1669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Bx = bx + bx; // Bx = 2.0 * bx 1689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Ax = ax - Bx; // Ax = ax - 2.0 * bx 1699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project By = by + by; // By = 2.0 * by 1719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Ay = ay - By; // Ay = ay - 2.0 * by 1729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int cross(double res[], int rc, double py1, double py2) { 1759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int cross = 0; 1769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < rc; i++) { 1789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double t = res[i]; 1799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-OUTSIDE 1819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (t < -DELTA || t > 1 + DELTA) { 1829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 1839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-START 1859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (t < DELTA) { 1869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (py1 < 0.0 && (bx != 0.0 ? bx : ax - bx) < 0.0) { 1879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross--; 1889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 1909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-END 1929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (t > 1 - DELTA) { 1939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (py1 < ay && (ax != bx ? ax - bx : bx) > 0.0) { 1949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross++; 1959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 1979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-INSIDE 1999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double ry = t * (t * Ay + By); 2009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // ry = t * t * Ay + t * By 2019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ry > py2) { 2029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double rxt = t * Ax + bx; 2039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // rxt = 2.0 * t * Ax + Bx = 2.0 * t * Ax + 2.0 * bx 2049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rxt > -DELTA && rxt < DELTA) { 2059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 2069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += rxt > 0.0 ? 1 : -1; 2089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } // for 2109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return cross; 2129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int solvePoint(double res[], double px) { 2159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double eqn[] = {-px, Bx, Ax}; 2169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return solveQuad(eqn, res); 2179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int solveExtrem(double res[]) { 2209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc = 0; 2219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (Ax != 0.0) { 2229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = - Bx / (Ax + Ax); 2239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (Ay != 0.0) { 2259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project res[rc++] = - By / (Ay + Ay); 2269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return rc; 2289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int addBound(double bound[], int bc, double res[], int rc, double minX, double maxX, boolean changeId, int id) { 2319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int i = 0; i < rc; i++) { 2329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double t = res[i]; 2339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (t > -DELTA && t < 1 + DELTA) { 2349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double rx = t * (t * Ax + Bx); 2359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (minX <= rx && rx <= maxX) { 2369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = t; 2379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = rx; 2389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = t * (t * Ay + By); 2399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = id; 2409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (changeId) { 2419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project id++; 2429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return bc; 2479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 2529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * CubicCurve class provides basic functionality to find curve crossing and calculating bounds 2539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 2549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static class CubicCurve { 2559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double ax, ay, bx, by, cx, cy; 2579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double Ax, Ay, Bx, By, Cx, Cy; 2589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double Ax3, Bx2; 2599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public CubicCurve(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2) { 2619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ax = x2 - x1; 2629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ay = y2 - y1; 2639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bx = cx1 - x1; 2649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project by = cy1 - y1; 2659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cx = cx2 - x1; 2669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cy = cy2 - y1; 2679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Cx = bx + bx + bx; // Cx = 3.0 * bx 2699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Bx = cx + cx + cx - Cx - Cx; // Bx = 3.0 * cx - 6.0 * bx 2709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Ax = ax - Bx - Cx; // Ax = ax - 3.0 * cx + 3.0 * bx 2719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Cy = by + by + by; // Cy = 3.0 * by 2739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project By = cy + cy + cy - Cy - Cy; // By = 3.0 * cy - 6.0 * by 2749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Ay = ay - By - Cy; // Ay = ay - 3.0 * cy + 3.0 * by 2759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Ax3 = Ax + Ax + Ax; 2779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Bx2 = Bx + Bx; 2789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int cross(double res[], int rc, double py1, double py2) { 2819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int cross = 0; 2829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < rc; i++) { 2839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double t = res[i]; 2849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-OUTSIDE 2869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (t < -DELTA || t > 1 + DELTA) { 2879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 2889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-START 2909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (t < DELTA) { 2919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (py1 < 0.0 && (bx != 0.0 ? bx : (cx != bx ? cx - bx : ax - cx)) < 0.0) { 2929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross--; 2939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 2959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-END 2979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (t > 1 - DELTA) { 2989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (py1 < ay && (ax != cx ? ax - cx : (cx != bx ? cx - bx : bx)) > 0.0) { 2999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross++; 3009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 3029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-INSIDE 3049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double ry = t * (t * (t * Ay + By) + Cy); 3059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // ry = t * t * t * Ay + t * t * By + t * Cy 3069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ry > py2) { 3079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double rxt = t * (t * Ax3 + Bx2) + Cx; 3089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // rxt = 3.0 * t * t * Ax + 2.0 * t * Bx + Cx 3099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rxt > -DELTA && rxt < DELTA) { 3109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project rxt = t * (Ax3 + Ax3) + Bx2; 3119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // rxt = 6.0 * t * Ax + 2.0 * Bx 3129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rxt < -DELTA || rxt > DELTA) { 3139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Inflection point 3149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 3159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project rxt = ax; 3179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += rxt > 0.0 ? 1 : -1; 3199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } //for 3219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return cross; 3239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int solvePoint(double res[], double px) { 3269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double eqn[] = {-px, Cx, Bx, Ax}; 3279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return solveCubic(eqn, res); 3289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int solveExtremX(double res[]) { 3319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double eqn[] = {Cx, Bx2, Ax3}; 3329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return solveQuad(eqn, res); 3339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int solveExtremY(double res[]) { 3369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double eqn[] = {Cy, By + By, Ay + Ay + Ay}; 3379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return solveQuad(eqn, res); 3389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int addBound(double bound[], int bc, double res[], int rc, double minX, double maxX, boolean changeId, int id) { 3419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int i = 0; i < rc; i++) { 3429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double t = res[i]; 3439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (t > -DELTA && t < 1 + DELTA) { 3449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double rx = t * (t * (t * Ax + Bx) + Cx); 3459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (minX <= rx && rx <= maxX) { 3469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = t; 3479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = rx; 3489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = t * (t * (t * Ay + By) + Cy); 3499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = id; 3509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (changeId) { 3519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project id++; 3529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return bc; 3579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 3629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times ray from point (x,y) cross line. 3639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 3649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int crossLine(double x1, double y1, double x2, double y2, double x, double y) { 3659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // LEFT/RIGHT/UP/EMPTY 3679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((x < x1 && x < x2) || 3689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (x > x1 && x > x2) || 3699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (y > y1 && y > y2) || 3709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (x1 == x2)) 3719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project { 3729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 3739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // DOWN 3769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (y < y1 && y < y2) { 3779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 3789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE 3799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((y2 - y1) * (x - x1) / (x2 - x1) <= y - y1) { 3809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE-UP 3819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 3829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // START 3869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x == x1) { 3879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < x2 ? 0 : -1; 3889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // END 3919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x == x2) { 3929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < x2 ? 1 : 0; 3939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE-DOWN 3969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < x2 ? 1 : -1; 3979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 4009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times ray from point (x,y) cross quard curve 4019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 4029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int crossQuad(double x1, double y1, double cx, double cy, double x2, double y2, double x, double y) { 4039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // LEFT/RIGHT/UP/EMPTY 4059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((x < x1 && x < cx && x < x2) || 4069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (x > x1 && x > cx && x > x2) || 4079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (y > y1 && y > cy && y > y2) || 4089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (x1 == cx && cx == x2)) 4099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project { 4109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 4119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // DOWN 4149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (y < y1 && y < cy && y < y2 && x != x1 && x != x2) { 4159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1 < x2) { 4169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < x && x < x2 ? 1 : 0; 4179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x2 < x && x < x1 ? -1 : 0; 4199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE 4229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2); 4239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double px = x - x1; 4249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double py = y - y1; 4259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double res[] = new double[3]; 4269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc = c.solvePoint(res, px); 4279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return c.cross(res, rc, py, py); 4299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 4329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times ray from point (x,y) cross cubic curve 4339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 4349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int crossCubic(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2, double x, double y) { 4359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // LEFT/RIGHT/UP/EMPTY 4379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((x < x1 && x < cx1 && x < cx2 && x < x2) || 4389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (x > x1 && x > cx1 && x > cx2 && x > x2) || 4399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (y > y1 && y > cy1 && y > cy2 && y > y2) || 4409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (x1 == cx1 && cx1 == cx2 && cx2 == x2)) 4419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project { 4429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 4439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // DOWN 4469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (y < y1 && y < cy1 && y < cy2 && y < y2 && x != x1 && x != x2) { 4479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1 < x2) { 4489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < x && x < x2 ? 1 : 0; 4499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x2 < x && x < x1 ? -1 : 0; 4519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE 4549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project CubicCurve c = new CubicCurve(x1, y1, cx1, cy1, cx2, cy2, x2, y2); 4559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double px = x - x1; 4569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double py = y - y1; 4579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double res[] = new double[3]; 4589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc = c.solvePoint(res, px); 4599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return c.cross(res, rc, py, py); 4609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 4639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times ray from point (x,y) cross path 4649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 4659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int crossPath(PathIterator p, double x, double y) { 4669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int cross = 0; 4679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double mx, my, cx, cy; 4689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mx = my = cx = cy = 0.0; 4699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double coords[] = new double[6]; 4709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (!p.isDone()) { 4729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (p.currentSegment(coords)) { 4739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_MOVETO: 4749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cx != mx || cy != my) { 4759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += crossLine(cx, cy, mx, my, x, y); 4769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mx = cx = coords[0]; 4789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project my = cy = coords[1]; 4799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 4809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_LINETO: 4819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += crossLine(cx, cy, cx = coords[0], cy = coords[1], x, y); 4829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 4839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_QUADTO: 4849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += crossQuad(cx, cy, coords[0], coords[1], cx = coords[2], cy = coords[3], x, y); 4859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 4869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_CUBICTO: 4879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += crossCubic(cx, cy, coords[0], coords[1], coords[2], coords[3], cx = coords[4], cy = coords[5], x, y); 4889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 4899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_CLOSE: 4909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cy != my || cx != mx) { 4919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += crossLine(cx, cy, cx = mx, cy = my, x, y); 4929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 4949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project p.next(); 4969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cy != my) { 4989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += crossLine(cx, cy, mx, my, x, y); 4999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return cross; 5019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times ray from point (x,y) cross shape 5059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int crossShape(Shape s, double x, double y) { 5079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!s.getBounds2D().contains(x, y)) { 5089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 5099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return crossPath(s.getPathIterator(null), x, y); 5119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns true if value enough small 5159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static boolean isZero(double val) { 5179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return -DELTA < val && val < DELTA; 5189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Sort bound array 5229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static void sortBound(double bound[], int bc) { 5249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int i = 0; i < bc - 4; i += 4) { 5259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int k = i; 5269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int j = i + 4; j < bc; j += 4) { 5279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (bound[k] > bound[j]) { 5289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project k = j; 5299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (k != i) { 5329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double tmp = bound[i]; 5339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[i] = bound[k]; 5349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[k] = tmp; 5359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project tmp = bound[i + 1]; 5369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[i + 1] = bound[k + 1]; 5379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[k + 1] = tmp; 5389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project tmp = bound[i + 2]; 5399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[i + 2] = bound[k + 2]; 5409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[k + 2] = tmp; 5419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project tmp = bound[i + 3]; 5429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[i + 3] = bound[k + 3]; 5439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[k + 3] = tmp; 5449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns are bounds intersect or not intersect rectangle 5509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static int crossBound(double bound[], int bc, double py1, double py2) { 5529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // LEFT/RIGHT 5549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (bc == 0) { 5559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 5569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Check Y coordinate 5599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int up = 0; 5609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int down = 0; 5619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int i = 2; i < bc; i += 4) { 5629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (bound[i] < py1) { 5639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project up++; 5649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 5659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (bound[i] > py2) { 5679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project down++; 5689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 5699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return CROSSING; 5719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // UP 5749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (down == 0) { 5759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 5769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (up != 0) { 5799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // bc >= 2 5809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project sortBound(bound, bc); 5819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean sign = bound[2] > py2; 5829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int i = 6; i < bc; i += 4) { 5839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean sign2 = bound[i] > py2; 5849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (sign != sign2 && bound[i + 1] != bound[i - 3]) { 5859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return CROSSING; 5869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project sign = sign2; 5889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return UNKNOWN; 5919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times rectangle stripe cross line or the are intersect 5959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int intersectLine(double x1, double y1, double x2, double y2, double rx1, double ry1, double rx2, double ry2) { 5979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // LEFT/RIGHT/UP 5999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((rx2 < x1 && rx2 < x2) || 6009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (rx1 > x1 && rx1 > x2) || 6019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (ry1 > y1 && ry1 > y2)) 6029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project { 6039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 6049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // DOWN 6079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ry2 < y1 && ry2 < y2) { 6089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 6099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE 6119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1 == x2) { 6129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return CROSSING; 6139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Build bound 6169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double bx1, bx2; 6179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1 < x2) { 6189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bx1 = x1 < rx1 ? rx1 : x1; 6199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bx2 = x2 < rx2 ? x2 : rx2; 6209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 6219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bx1 = x2 < rx1 ? rx1 : x2; 6229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bx2 = x1 < rx2 ? x1 : rx2; 6239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double k = (y2 - y1) / (x2 - x1); 6259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double by1 = k * (bx1 - x1) + y1; 6269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double by2 = k * (bx2 - x1) + y1; 6279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // BOUND-UP 6299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (by1 < ry1 && by2 < ry1) { 6309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 6319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // BOUND-DOWN 6349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (by1 > ry2 && by2 > ry2) { 6359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 6369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return CROSSING; 6379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // EMPTY 6419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1 == x2) { 6429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 6439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-START 6469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rx1 == x1) { 6479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < x2 ? 0 : -1; 6489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // CURVE-END 6519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rx1 == x2) { 6529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < x2 ? 1 : 0; 6539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1 < x2) { 6569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < rx1 && rx1 < x2 ? 1 : 0; 6579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x2 < rx1 && rx1 < x1 ? -1 : 0; 6599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 6639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times rectangle stripe cross quad curve or the are intersect 6649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 6659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int intersectQuad(double x1, double y1, double cx, double cy, double x2, double y2, double rx1, double ry1, double rx2, double ry2) { 6669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // LEFT/RIGHT/UP ------------------------------------------------------ 6689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((rx2 < x1 && rx2 < cx && rx2 < x2) || 6699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (rx1 > x1 && rx1 > cx && rx1 > x2) || 6709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (ry1 > y1 && ry1 > cy && ry1 > y2)) 6719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project { 6729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 6739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // DOWN --------------------------------------------------------------- 6769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ry2 < y1 && ry2 < cy && ry2 < y2 && rx1 != x1 && rx1 != x2) { 6779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1 < x2) { 6789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < rx1 && rx1 < x2 ? 1 : 0; 6799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x2 < rx1 && rx1 < x1 ? -1 : 0; 6819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE ------------------------------------------------------------- 6849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2); 6859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double px1 = rx1 - x1; 6869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double py1 = ry1 - y1; 6879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double px2 = rx2 - x1; 6889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double py2 = ry2 - y1; 6899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double res1[] = new double[3]; 6919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double res2[] = new double[3]; 6929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc1 = c.solvePoint(res1, px1); 6939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc2 = c.solvePoint(res2, px2); 6949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE-LEFT/RIGHT 6969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rc1 == 0 && rc2 == 0) { 6979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 6989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Build bound -------------------------------------------------------- 7019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double minX = px1 - DELTA; 7029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double maxX = px2 + DELTA; 7039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double bound[] = new double[28]; 7049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int bc = 0; 7059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Add roots 7069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0); 7079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1); 7089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Add extremal points` 7099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project rc2 = c.solveExtrem(res2); 7109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2); 7119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Add start and end 7129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rx1 < x1 && x1 < rx2) { 7139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 0.0; 7149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 0.0; 7159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 0.0; 7169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 4; 7179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rx1 < x2 && x2 < rx2) { 7199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 1.0; 7209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = c.ax; 7219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = c.ay; 7229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 5; 7239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // End build bound ---------------------------------------------------- 7259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int cross = crossBound(bound, bc, py1, py2); 7279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cross != UNKNOWN) { 7289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return cross; 7299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return c.cross(res1, rc1, py1, py2); 7319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 7349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times rectangle stripe cross cubic curve or the are intersect 7359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 7369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int intersectCubic(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2, double rx1, double ry1, double rx2, double ry2) { 7379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // LEFT/RIGHT/UP 7399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((rx2 < x1 && rx2 < cx1 && rx2 < cx2 && rx2 < x2) || 7409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (rx1 > x1 && rx1 > cx1 && rx1 > cx2 && rx1 > x2) || 7419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (ry1 > y1 && ry1 > cy1 && ry1 > cy2 && ry1 > y2)) 7429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project { 7439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 7449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // DOWN 7479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ry2 < y1 && ry2 < cy1 && ry2 < cy2 && ry2 < y2 && rx1 != x1 && rx1 != x2) { 7489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1 < x2) { 7499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x1 < rx1 && rx1 < x2 ? 1 : 0; 7509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return x2 < rx1 && rx1 < x1 ? -1 : 0; 7529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // INSIDE 7559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project CubicCurve c = new CubicCurve(x1, y1, cx1, cy1, cx2, cy2, x2, y2); 7569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double px1 = rx1 - x1; 7579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double py1 = ry1 - y1; 7589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double px2 = rx2 - x1; 7599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double py2 = ry2 - y1; 7609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double res1[] = new double[3]; 7629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double res2[] = new double[3]; 7639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc1 = c.solvePoint(res1, px1); 7649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int rc2 = c.solvePoint(res2, px2); 7659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // LEFT/RIGHT 7679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rc1 == 0 && rc2 == 0) { 7689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 7699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double minX = px1 - DELTA; 7729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double maxX = px2 + DELTA; 7739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Build bound -------------------------------------------------------- 7759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double bound[] = new double[40]; 7769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int bc = 0; 7779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Add roots 7789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0); 7799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1); 7809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Add extrimal points 7819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project rc2 = c.solveExtremX(res2); 7829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2); 7839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project rc2 = c.solveExtremY(res2); 7849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 4); 7859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Add start and end 7869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rx1 < x1 && x1 < rx2) { 7879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 0.0; 7889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 0.0; 7899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 0.0; 7909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 6; 7919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rx1 < x2 && x2 < rx2) { 7939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 1.0; 7949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = c.ax; 7959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = c.ay; 7969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bound[bc++] = 7; 7979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // End build bound ---------------------------------------------------- 7999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int cross = crossBound(bound, bc, py1, py2); 8019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cross != UNKNOWN) { 8029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return cross; 8039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return c.cross(res1, rc1, py1, py2); 8059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 8089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times rectangle stripe cross path or the are intersect 8099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 8109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int intersectPath(PathIterator p, double x, double y, double w, double h) { 8119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int cross = 0; 8139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int count; 8149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double mx, my, cx, cy; 8159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mx = my = cx = cy = 0.0; 8169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double coords[] = new double[6]; 8179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double rx1 = x; 8199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double ry1 = y; 8209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double rx2 = x + w; 8219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project double ry2 = y + h; 8229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (!p.isDone()) { 8249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project count = 0; 8259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (p.currentSegment(coords)) { 8269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_MOVETO: 8279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cx != mx || cy != my) { 8289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2); 8299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mx = cx = coords[0]; 8319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project my = cy = coords[1]; 8329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 8339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_LINETO: 8349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project count = intersectLine(cx, cy, cx = coords[0], cy = coords[1], rx1, ry1, rx2, ry2); 8359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 8369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_QUADTO: 8379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project count = intersectQuad(cx, cy, coords[0], coords[1], cx = coords[2], cy = coords[3], rx1, ry1, rx2, ry2); 8389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 8399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_CUBICTO: 8409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project count = intersectCubic(cx, cy, coords[0], coords[1], coords[2], coords[3], cx = coords[4], cy = coords[5], rx1, ry1, rx2, ry2); 8419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 8429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PathIterator.SEG_CLOSE: 8439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cy != my || cx != mx) { 8449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2); 8459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cx = mx; 8479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cy = my; 8489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 8499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (count == CROSSING) { 8519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return CROSSING; 8529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += count; 8549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project p.next(); 8559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cy != my) { 8579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2); 8589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (count == CROSSING) { 8599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return CROSSING; 8609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cross += count; 8629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return cross; 8649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 8679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns how many times rectangle stripe cross shape or the are intersect 8689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 8699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static int intersectShape(Shape s, double x, double y, double w, double h) { 8709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!s.getBounds2D().intersects(x, y, w, h)) { 8719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 8729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return intersectPath(s.getPathIterator(null), x, y, w, h); 8749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 8779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns true if cross count correspond inside location for non zero path rule 8789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 8799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static boolean isInsideNonZero(int cross) { 8809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return cross != 0; 8819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 8849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns true if cross count correspond inside location for even-odd path rule 8859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 8869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static boolean isInsideEvenOdd(int cross) { 8879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (cross & 1) != 0; 8889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 8899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project}