1/*
2 * Copyright (c) 1998, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.  Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26package sun.awt.geom;
27
28import java.awt.geom.PathIterator;
29import java.util.Vector;
30import java.util.Enumeration;
31
32public abstract class Crossings {
33    public static final boolean debug = false;
34
35    int limit = 0;
36    double yranges[] = new double[10];
37
38    double xlo, ylo, xhi, yhi;
39
40    public Crossings(double xlo, double ylo, double xhi, double yhi) {
41        this.xlo = xlo;
42        this.ylo = ylo;
43        this.xhi = xhi;
44        this.yhi = yhi;
45    }
46
47    public final double getXLo() {
48        return xlo;
49    }
50
51    public final double getYLo() {
52        return ylo;
53    }
54
55    public final double getXHi() {
56        return xhi;
57    }
58
59    public final double getYHi() {
60        return yhi;
61    }
62
63    public abstract void record(double ystart, double yend, int direction);
64
65    public void print() {
66        System.out.println("Crossings [");
67        System.out.println("  bounds = ["+ylo+", "+yhi+"]");
68        for (int i = 0; i < limit; i += 2) {
69            System.out.println("  ["+yranges[i]+", "+yranges[i+1]+"]");
70        }
71        System.out.println("]");
72    }
73
74    public final boolean isEmpty() {
75        return (limit == 0);
76    }
77
78    public abstract boolean covers(double ystart, double yend);
79
80    public static Crossings findCrossings(Vector<? extends Curve> curves,
81                                          double xlo, double ylo,
82                                          double xhi, double yhi)
83    {
84        Crossings cross = new EvenOdd(xlo, ylo, xhi, yhi);
85        Enumeration<? extends Curve> enum_ = curves.elements();
86        while (enum_.hasMoreElements()) {
87            Curve c = enum_.nextElement();
88            if (c.accumulateCrossings(cross)) {
89                return null;
90            }
91        }
92        if (debug) {
93            cross.print();
94        }
95        return cross;
96    }
97
98    public static Crossings findCrossings(PathIterator pi,
99                                          double xlo, double ylo,
100                                          double xhi, double yhi)
101    {
102        Crossings cross;
103        if (pi.getWindingRule() == PathIterator.WIND_EVEN_ODD) {
104            cross = new EvenOdd(xlo, ylo, xhi, yhi);
105        } else {
106            cross = new NonZero(xlo, ylo, xhi, yhi);
107        }
108        // coords array is big enough for holding:
109        //     coordinates returned from currentSegment (6)
110        //     OR
111        //         two subdivided quadratic curves (2+4+4=10)
112        //         AND
113        //             0-1 horizontal splitting parameters
114        //             OR
115        //             2 parametric equation derivative coefficients
116        //     OR
117        //         three subdivided cubic curves (2+6+6+6=20)
118        //         AND
119        //             0-2 horizontal splitting parameters
120        //             OR
121        //             3 parametric equation derivative coefficients
122        double coords[] = new double[23];
123        double movx = 0;
124        double movy = 0;
125        double curx = 0;
126        double cury = 0;
127        double newx, newy;
128        while (!pi.isDone()) {
129            int type = pi.currentSegment(coords);
130            switch (type) {
131            case PathIterator.SEG_MOVETO:
132                if (movy != cury &&
133                    cross.accumulateLine(curx, cury, movx, movy))
134                {
135                    return null;
136                }
137                movx = curx = coords[0];
138                movy = cury = coords[1];
139                break;
140            case PathIterator.SEG_LINETO:
141                newx = coords[0];
142                newy = coords[1];
143                if (cross.accumulateLine(curx, cury, newx, newy)) {
144                    return null;
145                }
146                curx = newx;
147                cury = newy;
148                break;
149            case PathIterator.SEG_QUADTO:
150                newx = coords[2];
151                newy = coords[3];
152                if (cross.accumulateQuad(curx, cury, coords)) {
153                    return null;
154                }
155                curx = newx;
156                cury = newy;
157                break;
158            case PathIterator.SEG_CUBICTO:
159                newx = coords[4];
160                newy = coords[5];
161                if (cross.accumulateCubic(curx, cury, coords)) {
162                    return null;
163                }
164                curx = newx;
165                cury = newy;
166                break;
167            case PathIterator.SEG_CLOSE:
168                if (movy != cury &&
169                    cross.accumulateLine(curx, cury, movx, movy))
170                {
171                    return null;
172                }
173                curx = movx;
174                cury = movy;
175                break;
176            }
177            pi.next();
178        }
179        if (movy != cury) {
180            if (cross.accumulateLine(curx, cury, movx, movy)) {
181                return null;
182            }
183        }
184        if (debug) {
185            cross.print();
186        }
187        return cross;
188    }
189
190    public boolean accumulateLine(double x0, double y0,
191                                  double x1, double y1)
192    {
193        if (y0 <= y1) {
194            return accumulateLine(x0, y0, x1, y1, 1);
195        } else {
196            return accumulateLine(x1, y1, x0, y0, -1);
197        }
198    }
199
200    public boolean accumulateLine(double x0, double y0,
201                                  double x1, double y1,
202                                  int direction)
203    {
204        if (yhi <= y0 || ylo >= y1) {
205            return false;
206        }
207        if (x0 >= xhi && x1 >= xhi) {
208            return false;
209        }
210        if (y0 == y1) {
211            return (x0 >= xlo || x1 >= xlo);
212        }
213        double xstart, ystart, xend, yend;
214        double dx = (x1 - x0);
215        double dy = (y1 - y0);
216        if (y0 < ylo) {
217            xstart = x0 + (ylo - y0) * dx / dy;
218            ystart = ylo;
219        } else {
220            xstart = x0;
221            ystart = y0;
222        }
223        if (yhi < y1) {
224            xend = x0 + (yhi - y0) * dx / dy;
225            yend = yhi;
226        } else {
227            xend = x1;
228            yend = y1;
229        }
230        if (xstart >= xhi && xend >= xhi) {
231            return false;
232        }
233        if (xstart > xlo || xend > xlo) {
234            return true;
235        }
236        record(ystart, yend, direction);
237        return false;
238    }
239
240    private Vector<Curve> tmp = new Vector<>();
241
242    public boolean accumulateQuad(double x0, double y0, double coords[]) {
243        if (y0 < ylo && coords[1] < ylo && coords[3] < ylo) {
244            return false;
245        }
246        if (y0 > yhi && coords[1] > yhi && coords[3] > yhi) {
247            return false;
248        }
249        if (x0 > xhi && coords[0] > xhi && coords[2] > xhi) {
250            return false;
251        }
252        if (x0 < xlo && coords[0] < xlo && coords[2] < xlo) {
253            if (y0 < coords[3]) {
254                record(Math.max(y0, ylo), Math.min(coords[3], yhi), 1);
255            } else if (y0 > coords[3]) {
256                record(Math.max(coords[3], ylo), Math.min(y0, yhi), -1);
257            }
258            return false;
259        }
260        Curve.insertQuad(tmp, x0, y0, coords);
261        Enumeration<Curve> enum_ = tmp.elements();
262        while (enum_.hasMoreElements()) {
263            Curve c = enum_.nextElement();
264            if (c.accumulateCrossings(this)) {
265                return true;
266            }
267        }
268        tmp.clear();
269        return false;
270    }
271
272    public boolean accumulateCubic(double x0, double y0, double coords[]) {
273        if (y0 < ylo && coords[1] < ylo &&
274            coords[3] < ylo && coords[5] < ylo)
275        {
276            return false;
277        }
278        if (y0 > yhi && coords[1] > yhi &&
279            coords[3] > yhi && coords[5] > yhi)
280        {
281            return false;
282        }
283        if (x0 > xhi && coords[0] > xhi &&
284            coords[2] > xhi && coords[4] > xhi)
285        {
286            return false;
287        }
288        if (x0 < xlo && coords[0] < xlo &&
289            coords[2] < xlo && coords[4] < xlo)
290        {
291            if (y0 <= coords[5]) {
292                record(Math.max(y0, ylo), Math.min(coords[5], yhi), 1);
293            } else {
294                record(Math.max(coords[5], ylo), Math.min(y0, yhi), -1);
295            }
296            return false;
297        }
298        Curve.insertCubic(tmp, x0, y0, coords);
299        Enumeration<Curve> enum_ = tmp.elements();
300        while (enum_.hasMoreElements()) {
301            Curve c = enum_.nextElement();
302            if (c.accumulateCrossings(this)) {
303                return true;
304            }
305        }
306        tmp.clear();
307        return false;
308    }
309
310    public static final class EvenOdd extends Crossings {
311        public EvenOdd(double xlo, double ylo, double xhi, double yhi) {
312            super(xlo, ylo, xhi, yhi);
313        }
314
315        public boolean covers(double ystart, double yend) {
316            return (limit == 2 && yranges[0] <= ystart && yranges[1] >= yend);
317        }
318
319        public void record(double ystart, double yend, int direction) {
320            if (ystart >= yend) {
321                return;
322            }
323            int from = 0;
324            // Quickly jump over all pairs that are completely "above"
325            while (from < limit && ystart > yranges[from+1]) {
326                from += 2;
327            }
328            int to = from;
329            while (from < limit) {
330                double yrlo = yranges[from++];
331                double yrhi = yranges[from++];
332                if (yend < yrlo) {
333                    // Quickly handle insertion of the new range
334                    yranges[to++] = ystart;
335                    yranges[to++] = yend;
336                    ystart = yrlo;
337                    yend = yrhi;
338                    continue;
339                }
340                // The ranges overlap - sort, collapse, insert, iterate
341                double yll, ylh, yhl, yhh;
342                if (ystart < yrlo) {
343                    yll = ystart;
344                    ylh = yrlo;
345                } else {
346                    yll = yrlo;
347                    ylh = ystart;
348                }
349                if (yend < yrhi) {
350                    yhl = yend;
351                    yhh = yrhi;
352                } else {
353                    yhl = yrhi;
354                    yhh = yend;
355                }
356                if (ylh == yhl) {
357                    ystart = yll;
358                    yend = yhh;
359                } else {
360                    if (ylh > yhl) {
361                        ystart = yhl;
362                        yhl = ylh;
363                        ylh = ystart;
364                    }
365                    if (yll != ylh) {
366                        yranges[to++] = yll;
367                        yranges[to++] = ylh;
368                    }
369                    ystart = yhl;
370                    yend = yhh;
371                }
372                if (ystart >= yend) {
373                    break;
374                }
375            }
376            if (to < from && from < limit) {
377                System.arraycopy(yranges, from, yranges, to, limit-from);
378            }
379            to += (limit-from);
380            if (ystart < yend) {
381                if (to >= yranges.length) {
382                    double newranges[] = new double[to+10];
383                    System.arraycopy(yranges, 0, newranges, 0, to);
384                    yranges = newranges;
385                }
386                yranges[to++] = ystart;
387                yranges[to++] = yend;
388            }
389            limit = to;
390        }
391    }
392
393    public static final class NonZero extends Crossings {
394        private int crosscounts[];
395
396        public NonZero(double xlo, double ylo, double xhi, double yhi) {
397            super(xlo, ylo, xhi, yhi);
398            crosscounts = new int[yranges.length / 2];
399        }
400
401        public boolean covers(double ystart, double yend) {
402            int i = 0;
403            while (i < limit) {
404                double ylo = yranges[i++];
405                double yhi = yranges[i++];
406                if (ystart >= yhi) {
407                    continue;
408                }
409                if (ystart < ylo) {
410                    return false;
411                }
412                if (yend <= yhi) {
413                    return true;
414                }
415                ystart = yhi;
416            }
417            return (ystart >= yend);
418        }
419
420        public void remove(int cur) {
421            limit -= 2;
422            int rem = limit - cur;
423            if (rem > 0) {
424                System.arraycopy(yranges, cur+2, yranges, cur, rem);
425                System.arraycopy(crosscounts, cur/2+1,
426                                 crosscounts, cur/2,
427                                 rem/2);
428            }
429        }
430
431        public void insert(int cur, double lo, double hi, int dir) {
432            int rem = limit - cur;
433            double oldranges[] = yranges;
434            int oldcounts[] = crosscounts;
435            if (limit >= yranges.length) {
436                yranges = new double[limit+10];
437                System.arraycopy(oldranges, 0, yranges, 0, cur);
438                crosscounts = new int[(limit+10)/2];
439                System.arraycopy(oldcounts, 0, crosscounts, 0, cur/2);
440            }
441            if (rem > 0) {
442                System.arraycopy(oldranges, cur, yranges, cur+2, rem);
443                System.arraycopy(oldcounts, cur/2,
444                                 crosscounts, cur/2+1,
445                                 rem/2);
446            }
447            yranges[cur+0] = lo;
448            yranges[cur+1] = hi;
449            crosscounts[cur/2] = dir;
450            limit += 2;
451        }
452
453        public void record(double ystart, double yend, int direction) {
454            if (ystart >= yend) {
455                return;
456            }
457            int cur = 0;
458            // Quickly jump over all pairs that are completely "above"
459            while (cur < limit && ystart > yranges[cur+1]) {
460                cur += 2;
461            }
462            if (cur < limit) {
463                int rdir = crosscounts[cur/2];
464                double yrlo = yranges[cur+0];
465                double yrhi = yranges[cur+1];
466                if (yrhi == ystart && rdir == direction) {
467                    // Remove the range from the list and collapse it
468                    // into the range being inserted.  Note that the
469                    // new combined range may overlap the following range
470                    // so we must not simply combine the ranges in place
471                    // unless we are at the last range.
472                    if (cur+2 == limit) {
473                        yranges[cur+1] = yend;
474                        return;
475                    }
476                    remove(cur);
477                    ystart = yrlo;
478                    rdir = crosscounts[cur/2];
479                    yrlo = yranges[cur+0];
480                    yrhi = yranges[cur+1];
481                }
482                if (yend < yrlo) {
483                    // Just insert the new range at the current location
484                    insert(cur, ystart, yend, direction);
485                    return;
486                }
487                if (yend == yrlo && rdir == direction) {
488                    // Just prepend the new range to the current one
489                    yranges[cur] = ystart;
490                    return;
491                }
492                // The ranges must overlap - (yend > yrlo && yrhi > ystart)
493                if (ystart < yrlo) {
494                    insert(cur, ystart, yrlo, direction);
495                    cur += 2;
496                    ystart = yrlo;
497                } else if (yrlo < ystart) {
498                    insert(cur, yrlo, ystart, rdir);
499                    cur += 2;
500                    yrlo = ystart;
501                }
502                // assert(yrlo == ystart);
503                int newdir = rdir + direction;
504                double newend = Math.min(yend, yrhi);
505                if (newdir == 0) {
506                    remove(cur);
507                } else {
508                    crosscounts[cur/2] = newdir;
509                    yranges[cur++] = ystart;
510                    yranges[cur++] = newend;
511                }
512                ystart = yrlo = newend;
513                if (yrlo < yrhi) {
514                    insert(cur, yrlo, yrhi, rdir);
515                }
516            }
517            if (ystart < yend) {
518                insert(cur, ystart, yend, direction);
519            }
520        }
521    }
522}
523