001: /*
002: * Copyright 1998-2003 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package sun.awt.geom;
027:
028: import java.util.Vector;
029: import java.util.Enumeration;
030: import java.util.Comparator;
031: import java.util.Arrays;
032:
033: public abstract class AreaOp {
034: public static abstract class CAGOp extends AreaOp {
035: boolean inLeft;
036: boolean inRight;
037: boolean inResult;
038:
039: public void newRow() {
040: inLeft = false;
041: inRight = false;
042: inResult = false;
043: }
044:
045: public int classify(Edge e) {
046: if (e.getCurveTag() == CTAG_LEFT) {
047: inLeft = !inLeft;
048: } else {
049: inRight = !inRight;
050: }
051: boolean newClass = newClassification(inLeft, inRight);
052: if (inResult == newClass) {
053: return ETAG_IGNORE;
054: }
055: inResult = newClass;
056: return (newClass ? ETAG_ENTER : ETAG_EXIT);
057: }
058:
059: public int getState() {
060: return (inResult ? RSTAG_INSIDE : RSTAG_OUTSIDE);
061: }
062:
063: public abstract boolean newClassification(boolean inLeft,
064: boolean inRight);
065: }
066:
067: public static class AddOp extends CAGOp {
068: public boolean newClassification(boolean inLeft, boolean inRight) {
069: return (inLeft || inRight);
070: }
071: }
072:
073: public static class SubOp extends CAGOp {
074: public boolean newClassification(boolean inLeft, boolean inRight) {
075: return (inLeft && !inRight);
076: }
077: }
078:
079: public static class IntOp extends CAGOp {
080: public boolean newClassification(boolean inLeft, boolean inRight) {
081: return (inLeft && inRight);
082: }
083: }
084:
085: public static class XorOp extends CAGOp {
086: public boolean newClassification(boolean inLeft, boolean inRight) {
087: return (inLeft != inRight);
088: }
089: }
090:
091: public static class NZWindOp extends AreaOp {
092: private int count;
093:
094: public void newRow() {
095: count = 0;
096: }
097:
098: public int classify(Edge e) {
099: // 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
164: .toArray(new Curve[numcurves]);
165: for (int i = 0; i < numcurves; i++) {
166: System.out.println("curvelist[" + i + "] = "
167: + curvelist[i]);
168: }
169: }
170: return edges;
171: }
172:
173: private static void addEdges(Vector edges, Vector curves,
174: int curvetag) {
175: Enumeration enum_ = curves.elements();
176: while (enum_.hasMoreElements()) {
177: Curve c = (Curve) enum_.nextElement();
178: if (c.getOrder() > 0) {
179: edges.add(new Edge(c, curvetag));
180: }
181: }
182: }
183:
184: private static Comparator YXTopComparator = new Comparator() {
185: public int compare(Object o1, Object o2) {
186: Curve c1 = ((Edge) o1).getCurve();
187: Curve c2 = ((Edge) o2).getCurve();
188: double v1, v2;
189: if ((v1 = c1.getYTop()) == (v2 = c2.getYTop())) {
190: if ((v1 = c1.getXTop()) == (v2 = c2.getXTop())) {
191: return 0;
192: }
193: }
194: if (v1 < v2) {
195: return -1;
196: }
197: return 1;
198: }
199: };
200:
201: private Vector pruneEdges(Vector edges) {
202: int numedges = edges.size();
203: if (numedges < 2) {
204: return edges;
205: }
206: Edge[] edgelist = (Edge[]) edges.toArray(new Edge[numedges]);
207: Arrays.sort(edgelist, YXTopComparator);
208: if (false) {
209: System.out.println("pruning: ");
210: for (int i = 0; i < numedges; i++) {
211: System.out.println("edgelist[" + i + "] = "
212: + edgelist[i]);
213: }
214: }
215: Edge e;
216: int left = 0;
217: int right = 0;
218: int cur = 0;
219: int next = 0;
220: double yrange[] = new double[2];
221: Vector subcurves = new Vector();
222: Vector chains = new Vector();
223: Vector links = new Vector();
224: // Active edges are between left (inclusive) and right (exclusive)
225: while (left < numedges) {
226: double y = yrange[0];
227: // Prune active edges that fall off the top of the active y range
228: for (cur = next = right - 1; cur >= left; cur--) {
229: e = edgelist[cur];
230: if (e.getCurve().getYBot() > y) {
231: if (next > cur) {
232: edgelist[next] = e;
233: }
234: next--;
235: }
236: }
237: left = next + 1;
238: // Grab a new "top of Y range" if the active edges are empty
239: if (left >= right) {
240: if (right >= numedges) {
241: break;
242: }
243: y = edgelist[right].getCurve().getYTop();
244: if (y > yrange[0]) {
245: finalizeSubCurves(subcurves, chains);
246: }
247: yrange[0] = y;
248: }
249: // Incorporate new active edges that enter the active y range
250: while (right < numedges) {
251: e = edgelist[right];
252: if (e.getCurve().getYTop() > y) {
253: break;
254: }
255: right++;
256: }
257: // Sort the current active edges by their X values and
258: // determine the maximum valid Y range where the X ordering
259: // is correct
260: yrange[1] = edgelist[left].getCurve().getYBot();
261: if (right < numedges) {
262: y = edgelist[right].getCurve().getYTop();
263: if (yrange[1] > y) {
264: yrange[1] = y;
265: }
266: }
267: if (false) {
268: System.out.println("current line: y = [" + yrange[0]
269: + ", " + yrange[1] + "]");
270: for (cur = left; cur < right; cur++) {
271: System.out.println(" " + edgelist[cur]);
272: }
273: }
274: // Note: We could start at left+1, but we need to make
275: // sure that edgelist[left] has its equivalence set to 0.
276: int nexteq = 1;
277: for (cur = left; cur < right; cur++) {
278: e = edgelist[cur];
279: e.setEquivalence(0);
280: for (next = cur; next > left; next--) {
281: Edge prevedge = edgelist[next - 1];
282: int ordering = e.compareTo(prevedge, yrange);
283: if (yrange[1] <= yrange[0]) {
284: throw new InternalError("backstepping to "
285: + yrange[1] + " from " + yrange[0]);
286: }
287: if (ordering >= 0) {
288: if (ordering == 0) {
289: // If the curves are equal, mark them to be
290: // deleted later if they cancel each other
291: // out so that we avoid having extraneous
292: // curve segments.
293: int eq = prevedge.getEquivalence();
294: if (eq == 0) {
295: eq = nexteq++;
296: prevedge.setEquivalence(eq);
297: }
298: e.setEquivalence(eq);
299: }
300: break;
301: }
302: edgelist[next] = prevedge;
303: }
304: edgelist[next] = e;
305: }
306: if (false) {
307: System.out.println("current sorted line: y = ["
308: + yrange[0] + ", " + yrange[1] + "]");
309: for (cur = left; cur < right; cur++) {
310: System.out.println(" " + edgelist[cur]);
311: }
312: }
313: // Now prune the active edge list.
314: // For each edge in the list, determine its classification
315: // (entering shape, exiting shape, ignore - no change) and
316: // record the current Y range and its classification in the
317: // Edge object for use later in constructing the new outline.
318: newRow();
319: double ystart = yrange[0];
320: double yend = yrange[1];
321: for (cur = left; cur < right; cur++) {
322: e = edgelist[cur];
323: int etag;
324: int eq = e.getEquivalence();
325: if (eq != 0) {
326: // Find one of the segments in the "equal" range
327: // with the right transition state and prefer an
328: // edge that was either active up until ystart
329: // or the edge that extends the furthest downward
330: // (i.e. has the most potential for continuation)
331: int origstate = getState();
332: etag = (origstate == AreaOp.RSTAG_INSIDE ? AreaOp.ETAG_EXIT
333: : AreaOp.ETAG_ENTER);
334: Edge activematch = null;
335: Edge longestmatch = e;
336: double furthesty = yend;
337: do {
338: // Note: classify() must be called
339: // on every edge we consume here.
340: classify(e);
341: if (activematch == null
342: && e.isActiveFor(ystart, etag)) {
343: activematch = e;
344: }
345: y = e.getCurve().getYBot();
346: if (y > furthesty) {
347: longestmatch = e;
348: furthesty = y;
349: }
350: } while (++cur < right
351: && (e = edgelist[cur]).getEquivalence() == eq);
352: --cur;
353: if (getState() == origstate) {
354: etag = AreaOp.ETAG_IGNORE;
355: } else {
356: e = (activematch != null ? activematch
357: : longestmatch);
358: }
359: } else {
360: etag = classify(e);
361: }
362: if (etag != AreaOp.ETAG_IGNORE) {
363: e.record(yend, etag);
364: links.add(new CurveLink(e.getCurve(), ystart, yend,
365: etag));
366: }
367: }
368: // assert(getState() == AreaOp.RSTAG_OUTSIDE);
369: if (getState() != AreaOp.RSTAG_OUTSIDE) {
370: System.out
371: .println("Still inside at end of active edge list!");
372: System.out.println("num curves = " + (right - left));
373: System.out.println("num links = " + links.size());
374: System.out.println("y top = " + yrange[0]);
375: if (right < numedges) {
376: System.out.println("y top of next curve = "
377: + edgelist[right].getCurve().getYTop());
378: } else {
379: System.out.println("no more curves");
380: }
381: for (cur = left; cur < right; cur++) {
382: e = edgelist[cur];
383: System.out.println(e);
384: int eq = e.getEquivalence();
385: if (eq != 0) {
386: System.out.println(" was equal to " + eq
387: + "...");
388: }
389: }
390: }
391: if (false) {
392: System.out.println("new links:");
393: for (int i = 0; i < links.size(); i++) {
394: CurveLink link = (CurveLink) links.elementAt(i);
395: System.out.println(" " + link.getSubCurve());
396: }
397: }
398: resolveLinks(subcurves, chains, links);
399: links.clear();
400: // Finally capture the bottom of the valid Y range as the top
401: // of the next Y range.
402: yrange[0] = yend;
403: }
404: finalizeSubCurves(subcurves, chains);
405: Vector ret = new Vector();
406: Enumeration enum_ = subcurves.elements();
407: while (enum_.hasMoreElements()) {
408: CurveLink link = (CurveLink) enum_.nextElement();
409: ret.add(link.getMoveto());
410: CurveLink nextlink = link;
411: while ((nextlink = nextlink.getNext()) != null) {
412: if (!link.absorb(nextlink)) {
413: ret.add(link.getSubCurve());
414: link = nextlink;
415: }
416: }
417: ret.add(link.getSubCurve());
418: }
419: return ret;
420: }
421:
422: public static void finalizeSubCurves(Vector subcurves, Vector chains) {
423: int numchains = chains.size();
424: if (numchains == 0) {
425: return;
426: }
427: if ((numchains & 1) != 0) {
428: throw new InternalError("Odd number of chains!");
429: }
430: ChainEnd[] endlist = new ChainEnd[numchains];
431: chains.toArray(endlist);
432: for (int i = 1; i < numchains; i += 2) {
433: ChainEnd open = endlist[i - 1];
434: ChainEnd close = endlist[i];
435: CurveLink subcurve = open.linkTo(close);
436: if (subcurve != null) {
437: subcurves.add(subcurve);
438: }
439: }
440: chains.clear();
441: }
442:
443: private static CurveLink[] EmptyLinkList = new CurveLink[2];
444: private static ChainEnd[] EmptyChainList = new ChainEnd[2];
445:
446: public static void resolveLinks(Vector subcurves, Vector chains,
447: Vector links) {
448: int numlinks = links.size();
449: CurveLink[] linklist;
450: if (numlinks == 0) {
451: linklist = EmptyLinkList;
452: } else {
453: if ((numlinks & 1) != 0) {
454: throw new InternalError("Odd number of new curves!");
455: }
456: linklist = new CurveLink[numlinks + 2];
457: links.toArray(linklist);
458: }
459: int numchains = chains.size();
460: ChainEnd[] endlist;
461: if (numchains == 0) {
462: endlist = EmptyChainList;
463: } else {
464: if ((numchains & 1) != 0) {
465: throw new InternalError("Odd number of chains!");
466: }
467: endlist = new ChainEnd[numchains + 2];
468: chains.toArray(endlist);
469: }
470: int curchain = 0;
471: int curlink = 0;
472: chains.clear();
473: ChainEnd chain = endlist[0];
474: ChainEnd nextchain = endlist[1];
475: CurveLink link = linklist[0];
476: CurveLink nextlink = linklist[1];
477: while (chain != null || link != null) {
478: /*
479: * Strategy 1:
480: * Connect chains or links if they are the only things left...
481: */
482: boolean connectchains = (link == null);
483: boolean connectlinks = (chain == null);
484:
485: if (!connectchains && !connectlinks) {
486: // assert(link != null && chain != null);
487: /*
488: * Strategy 2:
489: * Connect chains or links if they close off an open area...
490: */
491: connectchains = ((curchain & 1) == 0 && chain.getX() == nextchain
492: .getX());
493: connectlinks = ((curlink & 1) == 0 && link.getX() == nextlink
494: .getX());
495:
496: if (!connectchains && !connectlinks) {
497: /*
498: * Strategy 3:
499: * Connect chains or links if their successor is
500: * between them and their potential connectee...
501: */
502: double cx = chain.getX();
503: double lx = link.getX();
504: connectchains = (nextchain != null && cx < lx && obstructs(
505: nextchain.getX(), lx, curchain));
506: connectlinks = (nextlink != null && lx < cx && obstructs(
507: nextlink.getX(), cx, curlink));
508: }
509: }
510: if (connectchains) {
511: CurveLink subcurve = chain.linkTo(nextchain);
512: if (subcurve != null) {
513: subcurves.add(subcurve);
514: }
515: curchain += 2;
516: chain = endlist[curchain];
517: nextchain = endlist[curchain + 1];
518: }
519: if (connectlinks) {
520: ChainEnd openend = new ChainEnd(link, null);
521: ChainEnd closeend = new ChainEnd(nextlink, openend);
522: openend.setOtherEnd(closeend);
523: chains.add(openend);
524: chains.add(closeend);
525: curlink += 2;
526: link = linklist[curlink];
527: nextlink = linklist[curlink + 1];
528: }
529: if (!connectchains && !connectlinks) {
530: // assert(link != null);
531: // assert(chain != null);
532: // assert(chain.getEtag() == link.getEtag());
533: chain.addLink(link);
534: chains.add(chain);
535: curchain++;
536: chain = nextchain;
537: nextchain = endlist[curchain + 1];
538: curlink++;
539: link = nextlink;
540: nextlink = linklist[curlink + 1];
541: }
542: }
543: if ((chains.size() & 1) != 0) {
544: System.out.println("Odd number of chains!");
545: }
546: }
547:
548: /*
549: * Does the position of the next edge at v1 "obstruct" the
550: * connectivity between current edge and the potential
551: * partner edge which is positioned at v2?
552: *
553: * Phase tells us whether we are testing for a transition
554: * into or out of the interior part of the resulting area.
555: *
556: * Require 4-connected continuity if this edge and the partner
557: * edge are both "entering into" type edges
558: * Allow 8-connected continuity for "exiting from" type edges
559: */
560: public static boolean obstructs(double v1, double v2, int phase) {
561: return (((phase & 1) == 0) ? (v1 <= v2) : (v1 < v2));
562: }
563: }
|