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