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 
  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<? 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 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 }