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.util.Vector; 29 import java.util.Enumeration; 30 import java.util.Comparator; 31 import java.util.Arrays; 32 33 public abstract class AreaOp { 34 public static abstract class CAGOp extends AreaOp { 35 boolean inLeft; 36 boolean inRight; 37 boolean inResult; 38 39 public void newRow() { 40 inLeft = false; 41 inRight = false; 42 inResult = false; 43 } 44 45 public int classify(Edge e) { 46 if (e.getCurveTag() == CTAG_LEFT) { 47 inLeft = !inLeft; 48 } else { 49 inRight = !inRight; 50 } 51 boolean newClass = newClassification(inLeft, inRight); 52 if (inResult == newClass) { 53 return ETAG_IGNORE; 54 } 55 inResult = newClass; 56 return (newClass ? ETAG_ENTER : ETAG_EXIT); 57 } 58 59 public int getState() { 60 return (inResult ? RSTAG_INSIDE : RSTAG_OUTSIDE); 61 } 62 63 public abstract boolean newClassification(boolean inLeft, 64 boolean inRight); 65 } 66 67 public static class AddOp extends CAGOp { 68 public boolean newClassification(boolean inLeft, boolean inRight) { 69 return (inLeft || inRight); 70 } 71 } 72 73 public static class SubOp extends CAGOp { 74 public boolean newClassification(boolean inLeft, boolean inRight) { 75 return (inLeft && !inRight); 76 } 77 } 78 79 public static class IntOp extends CAGOp { 80 public boolean newClassification(boolean inLeft, boolean inRight) { 81 return (inLeft && inRight); 82 } 83 } 84 85 public static class XorOp extends CAGOp { 86 public boolean newClassification(boolean inLeft, boolean inRight) { 87 return (inLeft != inRight); 88 } 89 } 90 91 public static class NZWindOp extends AreaOp { 92 private int count; 93 94 public void newRow() { 95 count = 0; 96 } 97 98 public int classify(Edge e) { 99 // Note: the right curves should be an empty set with this op... 100 // assert(e.getCurveTag() == CTAG_LEFT); 101 int newCount = count; 102 int type = (newCount == 0 ? ETAG_ENTER : ETAG_IGNORE); 103 newCount += e.getCurve().getDirection(); 104 count = newCount; 105 return (newCount == 0 ? ETAG_EXIT : type); 106 } 107 108 public int getState() { 109 return ((count == 0) ? RSTAG_OUTSIDE : RSTAG_INSIDE); 110 } 111 } 112 113 public static class EOWindOp extends AreaOp { 114 private boolean inside; 115 116 public void newRow() { 117 inside = false; 118 } 119 120 public int classify(Edge e) { 121 // Note: the right curves should be an empty set with this op... 122 // assert(e.getCurveTag() == CTAG_LEFT); 123 boolean newInside = !inside; 124 inside = newInside; 125 return (newInside ? ETAG_ENTER : ETAG_EXIT); 126 } 127 128 public int getState() { 129 return (inside ? RSTAG_INSIDE : RSTAG_OUTSIDE); 130 } 131 } 132 133 private AreaOp() { 134 } 135 136 /* Constants to tag the left and right curves in the edge list */ 137 public static final int CTAG_LEFT = 0; 138 public static final int CTAG_RIGHT = 1; 139 140 /* Constants to classify edges */ 141 public static final int ETAG_IGNORE = 0; 142 public static final int ETAG_ENTER = 1; 143 public static final int ETAG_EXIT = -1; 144 145 /* Constants used to classify result state */ 146 public static final int RSTAG_INSIDE = 1; 147 public static final int RSTAG_OUTSIDE = -1; 148 149 public abstract void newRow(); 150 151 public abstract int classify(Edge e); 152 153 public abstract int getState(); 154 155 public Vector<Curve> calculate(Vector<Curve> left, Vector<Curve> right) { 156 Vector<Edge> edges = new Vector<>(); 157 addEdges(edges, left, AreaOp.CTAG_LEFT); 158 addEdges(edges, right, AreaOp.CTAG_RIGHT); 159 @SuppressWarnings("unchecked") 160 Vector<Edge> tmp1 = (Vector<Edge>)((Vector)pruneEdges(edges)); 161 edges = tmp1; 162 if (false) { 163 System.out.println("result: "); 164 int numcurves = edges.size(); 165 Curve[] curvelist = edges.toArray(new Curve[numcurves]); 166 for (int i = 0; i < numcurves; i++) { 167 System.out.println("curvelist["+i+"] = "+curvelist[i]); 168 } 169 } 170 @SuppressWarnings("unchecked") 171 Vector<Curve> tmp2 = (Vector<Curve>)((Vector)edges); 172 return tmp2; 173 } 174 175 private static void addEdges(Vector<Edge> edges, Vector<Curve> curves, int curvetag) { 176 Enumeration<Curve> enum_ = curves.elements(); 177 while (enum_.hasMoreElements()) { 178 Curve c = enum_.nextElement(); 179 if (c.getOrder() > 0) { 180 edges.add(new Edge(c, curvetag)); 181 } 182 } 183 } 184 185 private static Comparator<Edge> YXTopComparator = new Comparator<Edge>() { 186 public int compare(Edge o1, Edge o2) { 187 Curve c1 = o1.getCurve(); 188 Curve c2 = o2.getCurve(); 189 double v1, v2; 190 if ((v1 = c1.getYTop()) == (v2 = c2.getYTop())) { 191 if ((v1 = c1.getXTop()) == (v2 = c2.getXTop())) { 192 return 0; 193 } 194 } 195 if (v1 < v2) { 196 return -1; 197 } 198 return 1; 199 } 200 }; 201 202 private Vector<?> pruneEdges(Vector<Edge> edges) { 203 /* 204 * The implementation of this method consistently treats its 205 * return type either as a Vector<Edge> or a Vector<Curve>. 206 */ 207 int numedges = edges.size(); 208 if (numedges < 2) { 209 return edges; 210 } 211 Edge[] edgelist = edges.toArray(new Edge[numedges]); 212 Arrays.sort(edgelist, YXTopComparator); 213 if (false) { 214 System.out.println("pruning: "); 215 for (int i = 0; i < numedges; i++) { 216 System.out.println("edgelist["+i+"] = "+edgelist[i]); 217 } 218 } 219 Edge e; 220 int left = 0; 221 int right = 0; 222 int cur = 0; 223 int next = 0; 224 double yrange[] = new double[2]; 225 Vector<CurveLink> subcurves = new Vector<>(); 226 Vector<ChainEnd> chains = new Vector<>(); 227 Vector<CurveLink> links = new Vector<>(); 228 // Active edges are between left (inclusive) and right (exclusive) 229 while (left < numedges) { 230 double y = yrange[0]; 231 // Prune active edges that fall off the top of the active y range 232 for (cur = next = right - 1; cur >= left; cur--) { 233 e = edgelist[cur]; 234 if (e.getCurve().getYBot() > y) { 235 if (next > cur) { 236 edgelist[next] = e; 237 } 238 next--; 239 } 240 } 241 left = next + 1; 242 // Grab a new "top of Y range" if the active edges are empty 243 if (left >= right) { 244 if (right >= numedges) { 245 break; 246 } 247 y = edgelist[right].getCurve().getYTop(); 248 if (y > yrange[0]) { 249 finalizeSubCurves(subcurves, chains); 250 } 251 yrange[0] = y; 252 } 253 // Incorporate new active edges that enter the active y range 254 while (right < numedges) { 255 e = edgelist[right]; 256 if (e.getCurve().getYTop() > y) { 257 break; 258 } 259 right++; 260 } 261 // Sort the current active edges by their X values and 262 // determine the maximum valid Y range where the X ordering 263 // is correct 264 yrange[1] = edgelist[left].getCurve().getYBot(); 265 if (right < numedges) { 266 y = edgelist[right].getCurve().getYTop(); 267 if (yrange[1] > y) { 268 yrange[1] = y; 269 } 270 } 271 if (false) { 272 System.out.println("current line: y = ["+ 273 yrange[0]+", "+yrange[1]+"]"); 274 for (cur = left; cur < right; cur++) { 275 System.out.println(" "+edgelist[cur]); 276 } 277 } 278 // Note: We could start at left+1, but we need to make 279 // sure that edgelist[left] has its equivalence set to 0. 280 int nexteq = 1; 281 for (cur = left; cur < right; cur++) { 282 e = edgelist[cur]; 283 e.setEquivalence(0); 284 for (next = cur; next > left; next--) { 285 Edge prevedge = edgelist[next-1]; 286 int ordering = e.compareTo(prevedge, yrange); 287 if (yrange[1] <= yrange[0]) { 288 throw new InternalError("backstepping to "+yrange[1]+ 289 " from "+yrange[0]); 290 } 291 if (ordering >= 0) { 292 if (ordering == 0) { 293 // If the curves are equal, mark them to be 294 // deleted later if they cancel each other 295 // out so that we avoid having extraneous 296 // curve segments. 297 int eq = prevedge.getEquivalence(); 298 if (eq == 0) { 299 eq = nexteq++; 300 prevedge.setEquivalence(eq); 301 } 302 e.setEquivalence(eq); 303 } 304 break; 305 } 306 edgelist[next] = prevedge; 307 } 308 edgelist[next] = e; 309 } 310 if (false) { 311 System.out.println("current sorted line: y = ["+ 312 yrange[0]+", "+yrange[1]+"]"); 313 for (cur = left; cur < right; cur++) { 314 System.out.println(" "+edgelist[cur]); 315 } 316 } 317 // Now prune the active edge list. 318 // For each edge in the list, determine its classification 319 // (entering shape, exiting shape, ignore - no change) and 320 // record the current Y range and its classification in the 321 // Edge object for use later in constructing the new outline. 322 newRow(); 323 double ystart = yrange[0]; 324 double yend = yrange[1]; 325 for (cur = left; cur < right; cur++) { 326 e = edgelist[cur]; 327 int etag; 328 int eq = e.getEquivalence(); 329 if (eq != 0) { 330 // Find one of the segments in the "equal" range 331 // with the right transition state and prefer an 332 // edge that was either active up until ystart 333 // or the edge that extends the furthest downward 334 // (i.e. has the most potential for continuation) 335 int origstate = getState(); 336 etag = (origstate == AreaOp.RSTAG_INSIDE 337 ? AreaOp.ETAG_EXIT 338 : AreaOp.ETAG_ENTER); 339 Edge activematch = null; 340 Edge longestmatch = e; 341 double furthesty = yend; 342 do { 343 // Note: classify() must be called 344 // on every edge we consume here. 345 classify(e); 346 if (activematch == null && 347 e.isActiveFor(ystart, etag)) 348 { 349 activematch = e; 350 } 351 y = e.getCurve().getYBot(); 352 if (y > furthesty) { 353 longestmatch = e; 354 furthesty = y; 355 } 356 } while (++cur < right && 357 (e = edgelist[cur]).getEquivalence() == eq); 358 --cur; 359 if (getState() == origstate) { 360 etag = AreaOp.ETAG_IGNORE; 361 } else { 362 e = (activematch != null ? activematch : longestmatch); 363 } 364 } else { 365 etag = classify(e); 366 } 367 if (etag != AreaOp.ETAG_IGNORE) { 368 e.record(yend, etag); 369 links.add(new CurveLink(e.getCurve(), ystart, yend, etag)); 370 } 371 } 372 // assert(getState() == AreaOp.RSTAG_OUTSIDE); 373 if (getState() != AreaOp.RSTAG_OUTSIDE) { 374 System.out.println("Still inside at end of active edge list!"); 375 System.out.println("num curves = "+(right-left)); 376 System.out.println("num links = "+links.size()); 377 System.out.println("y top = "+yrange[0]); 378 if (right < numedges) { 379 System.out.println("y top of next curve = "+ 380 edgelist[right].getCurve().getYTop()); 381 } else { 382 System.out.println("no more curves"); 383 } 384 for (cur = left; cur < right; cur++) { 385 e = edgelist[cur]; 386 System.out.println(e); 387 int eq = e.getEquivalence(); 388 if (eq != 0) { 389 System.out.println(" was equal to "+eq+"..."); 390 } 391 } 392 } 393 if (false) { 394 System.out.println("new links:"); 395 for (int i = 0; i < links.size(); i++) { 396 CurveLink link = links.elementAt(i); 397 System.out.println(" "+link.getSubCurve()); 398 } 399 } 400 resolveLinks(subcurves, chains, links); 401 links.clear(); 402 // Finally capture the bottom of the valid Y range as the top 403 // of the next Y range. 404 yrange[0] = yend; 405 } 406 finalizeSubCurves(subcurves, chains); 407 Vector<Curve> ret = new Vector<>(); 408 Enumeration<CurveLink> enum_ = subcurves.elements(); 409 while (enum_.hasMoreElements()) { 410 CurveLink link = enum_.nextElement(); 411 ret.add(link.getMoveto()); 412 CurveLink nextlink = link; 413 while ((nextlink = nextlink.getNext()) != null) { 414 if (!link.absorb(nextlink)) { 415 ret.add(link.getSubCurve()); 416 link = nextlink; 417 } 418 } 419 ret.add(link.getSubCurve()); 420 } 421 return ret; 422 } 423 424 public static void finalizeSubCurves(Vector<CurveLink> subcurves, Vector<ChainEnd> chains) { 425 int numchains = chains.size(); 426 if (numchains == 0) { 427 return; 428 } 429 if ((numchains & 1) != 0) { 430 throw new InternalError("Odd number of chains!"); 431 } 432 ChainEnd[] endlist = new ChainEnd[numchains]; 433 chains.toArray(endlist); 434 for (int i = 1; i < numchains; i += 2) { 435 ChainEnd open = endlist[i - 1]; 436 ChainEnd close = endlist[i]; 437 CurveLink subcurve = open.linkTo(close); 438 if (subcurve != null) { 439 subcurves.add(subcurve); 440 } 441 } 442 chains.clear(); 443 } 444 445 private static CurveLink[] EmptyLinkList = new CurveLink[2]; 446 private static ChainEnd[] EmptyChainList = new ChainEnd[2]; 447 448 public static void resolveLinks(Vector<CurveLink> subcurves, 449 Vector<ChainEnd> chains, 450 Vector<CurveLink> links) 451 { 452 int numlinks = links.size(); 453 CurveLink[] linklist; 454 if (numlinks == 0) { 455 linklist = EmptyLinkList; 456 } else { 457 if ((numlinks & 1) != 0) { 458 throw new InternalError("Odd number of new curves!"); 459 } 460 linklist = new CurveLink[numlinks+2]; 461 links.toArray(linklist); 462 } 463 int numchains = chains.size(); 464 ChainEnd[] endlist; 465 if (numchains == 0) { 466 endlist = EmptyChainList; 467 } else { 468 if ((numchains & 1) != 0) { 469 throw new InternalError("Odd number of chains!"); 470 } 471 endlist = new ChainEnd[numchains+2]; 472 chains.toArray(endlist); 473 } 474 int curchain = 0; 475 int curlink = 0; 476 chains.clear(); 477 ChainEnd chain = endlist[0]; 478 ChainEnd nextchain = endlist[1]; 479 CurveLink link = linklist[0]; 480 CurveLink nextlink = linklist[1]; 481 while (chain != null || link != null) { 482 /* 483 * Strategy 1: 484 * Connect chains or links if they are the only things left... 485 */ 486 boolean connectchains = (link == null); 487 boolean connectlinks = (chain == null); 488 489 if (!connectchains && !connectlinks) { 490 // assert(link != null && chain != null); 491 /* 492 * Strategy 2: 493 * Connect chains or links if they close off an open area... 494 */ 495 connectchains = ((curchain & 1) == 0 && 496 chain.getX() == nextchain.getX()); 497 connectlinks = ((curlink & 1) == 0 && 498 link.getX() == nextlink.getX()); 499 500 if (!connectchains && !connectlinks) { 501 /* 502 * Strategy 3: 503 * Connect chains or links if their successor is 504 * between them and their potential connectee... 505 */ 506 double cx = chain.getX(); 507 double lx = link.getX(); 508 connectchains = 509 (nextchain != null && cx < lx && 510 obstructs(nextchain.getX(), lx, curchain)); 511 connectlinks = 512 (nextlink != null && lx < cx && 513 obstructs(nextlink.getX(), cx, curlink)); 514 } 515 } 516 if (connectchains) { 517 CurveLink subcurve = chain.linkTo(nextchain); 518 if (subcurve != null) { 519 subcurves.add(subcurve); 520 } 521 curchain += 2; 522 chain = endlist[curchain]; 523 nextchain = endlist[curchain+1]; 524 } 525 if (connectlinks) { 526 ChainEnd openend = new ChainEnd(link, null); 527 ChainEnd closeend = new ChainEnd(nextlink, openend); 528 openend.setOtherEnd(closeend); 529 chains.add(openend); 530 chains.add(closeend); 531 curlink += 2; 532 link = linklist[curlink]; 533 nextlink = linklist[curlink+1]; 534 } 535 if (!connectchains && !connectlinks) { 536 // assert(link != null); 537 // assert(chain != null); 538 // assert(chain.getEtag() == link.getEtag()); 539 chain.addLink(link); 540 chains.add(chain); 541 curchain++; 542 chain = nextchain; 543 nextchain = endlist[curchain+1]; 544 curlink++; 545 link = nextlink; 546 nextlink = linklist[curlink+1]; 547 } 548 } 549 if ((chains.size() & 1) != 0) { 550 System.out.println("Odd number of chains!"); 551 } 552 } 553 554 /* 555 * Does the position of the next edge at v1 "obstruct" the 556 * connectivity between current edge and the potential 557 * partner edge which is positioned at v2? 558 * 559 * Phase tells us whether we are testing for a transition 560 * into or out of the interior part of the resulting area. 561 * 562 * Require 4-connected continuity if this edge and the partner 563 * edge are both "entering into" type edges 564 * Allow 8-connected continuity for "exiting from" type edges 565 */ 566 public static boolean obstructs(double v1, double v2, int phase) { 567 return (((phase & 1) == 0) ? (v1 <= v2) : (v1 < v2)); 568 } 569 }