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 }