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