View Javadoc
1   /*
2    * Copyright (c) 1998, 2003, 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  
26  package sun.awt.geom;
27  
28  import java.awt.geom.PathIterator;
29  import java.util.Vector;
30  import java.util.Enumeration;
31  
32  public 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 curves,
81                                            double xlo, double ylo,
82                                            double xhi, double yhi)
83      {
84          Crossings cross = new EvenOdd(xlo, ylo, xhi, yhi);
85          Enumeration enum_ = curves.elements();
86          while (enum_.hasMoreElements()) {
87              Curve c = (Curve) 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() == pi.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 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 enum_ = tmp.elements();
262         while (enum_.hasMoreElements()) {
263             Curve c = (Curve) 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 enum_ = tmp.elements();
300         while (enum_.hasMoreElements()) {
301             Curve c = (Curve) enum_.nextElement();
302             if (c.accumulateCrossings(this)) {
303                 return true;
304             }
305         }
306         tmp.clear();
307         return false;
308     }
309 
310     public final static 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 final 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 final static 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 final 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 }