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 }