Source Code Cross Referenced for Crossing.java in  » Apache-Harmony-Java-SE » org-package » org » apache » harmony » awt » gl » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Apache Harmony Java SE » org package » org.apache.harmony.awt.gl 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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