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 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 Vector<Curve> rt = new Vector<>();
202 for (Edge edge: edges) {
203 rt.add(edge.getCurve());
204 }
205 return rt;
206 }
207 Edge[] edgelist = edges.toArray(new Edge[numedges]);
208 Arrays.sort(edgelist, YXTopComparator);
209 if (false) {
210 System.out.println("pruning: ");
211 for (int i = 0; i < numedges; i++) {
212 System.out.println("edgelist["+i+"] = "+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<CurveLink> subcurves = new Vector<>();
222 Vector<ChainEnd> chains = new Vector<>();
223 Vector<CurveLink> 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 = ["+
269 yrange[0]+", "+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 "+yrange[1]+
285 " 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
333 ? AreaOp.ETAG_EXIT
334 : AreaOp.ETAG_ENTER);
335 Edge activematch = null;
336 Edge longestmatch = e;
337 double furthesty = yend;
338 do {
339 // Note: classify() must be called
340 // on every edge we consume here.
341 classify(e);
342 if (activematch == null &&
343 e.isActiveFor(ystart, etag))
344 {
345 activematch = e;
346 }
347 y = e.getCurve().getYBot();
348 if (y > furthesty) {
349 longestmatch = e;
350 furthesty = y;
351 }
352 } while (++cur < right &&
353 (e = edgelist[cur]).getEquivalence() == eq);
354 --cur;
355 if (getState() == origstate) {
356 etag = AreaOp.ETAG_IGNORE;
357 } else {
358 e = (activematch != null ? activematch : longestmatch);
359 }
360 } else {
361 etag = classify(e);
362 }
363 if (etag != AreaOp.ETAG_IGNORE) {
364 e.record(yend, etag);
365 links.add(new CurveLink(e.getCurve(), ystart, yend, etag));
366 }
367 }
368 // assert(getState() == AreaOp.RSTAG_OUTSIDE);
369 if (getState() != AreaOp.RSTAG_OUTSIDE) {
370 System.out.println("Still inside at end of active edge list!");
371 System.out.println("num curves = "+(right-left));
372 System.out.println("num links = "+links.size());
373 System.out.println("y top = "+yrange[0]);
374 if (right < numedges) {
375 System.out.println("y top of next curve = "+
376 edgelist[right].getCurve().getYTop());
377 } else {
378 System.out.println("no more curves");
379 }
380 for (cur = left; cur < right; cur++) {
381 e = edgelist[cur];
382 System.out.println(e);
383 int eq = e.getEquivalence();
384 if (eq != 0) {
385 System.out.println(" was equal to "+eq+"...");
386 }
387 }
388 }
389 if (false) {
390 System.out.println("new links:");
391 for (int i = 0; i < links.size(); i++) {
392 CurveLink link = links.elementAt(i);
393 System.out.println(" "+link.getSubCurve());
394 }
395 }
396 resolveLinks(subcurves, chains, links);
397 links.clear();
398 // Finally capture the bottom of the valid Y range as the top
399 // of the next Y range.
400 yrange[0] = yend;
401 }
402 finalizeSubCurves(subcurves, chains);
403 Vector<Curve> ret = new Vector<>();
404 Enumeration<CurveLink> enum_ = subcurves.elements();
405 while (enum_.hasMoreElements()) {
406 CurveLink link = enum_.nextElement();
407 ret.add(link.getMoveto());
408 CurveLink nextlink = link;
409 while ((nextlink = nextlink.getNext()) != null) {
410 if (!link.absorb(nextlink)) {
411 ret.add(link.getSubCurve());
412 link = nextlink;
413 }
414 }
415 ret.add(link.getSubCurve());
416 }
417 return ret;
418 }
419
420 public static void finalizeSubCurves(Vector<CurveLink> subcurves,
421 Vector<ChainEnd> chains) {
422 int numchains = chains.size();
423 if (numchains == 0) {
424 return;
425 }
426 if ((numchains & 1) != 0) {
427 throw new InternalError("Odd number of chains!");
428 }
429 ChainEnd[] endlist = new ChainEnd[numchains];
430 chains.toArray(endlist);
431 for (int i = 1; i < numchains; i += 2) {
432 ChainEnd open = endlist[i - 1];
433 ChainEnd close = endlist[i];
434 CurveLink subcurve = open.linkTo(close);
435 if (subcurve != null) {
436 subcurves.add(subcurve);
437 }
438 }
439 chains.clear();
440 }
441
442 private static CurveLink[] EmptyLinkList = new CurveLink[2];
443 private static ChainEnd[] EmptyChainList = new ChainEnd[2];
444
445 public static void resolveLinks(Vector<CurveLink> subcurves,
446 Vector<ChainEnd> chains,
447 Vector<CurveLink> links)
448 {
449 int numlinks = links.size();
450 CurveLink[] linklist;
451 if (numlinks == 0) {
452 linklist = EmptyLinkList;
453 } else {
454 if ((numlinks & 1) != 0) {
455 throw new InternalError("Odd number of new curves!");
456 }
457 linklist = new CurveLink[numlinks+2];
458 links.toArray(linklist);
459 }
460 int numchains = chains.size();
461 ChainEnd[] endlist;
462 if (numchains == 0) {
463 endlist = EmptyChainList;
464 } else {
465 if ((numchains & 1) != 0) {
466 throw new InternalError("Odd number of chains!");
467 }
468 endlist = new ChainEnd[numchains+2];
469 chains.toArray(endlist);
470 }
471 int curchain = 0;
472 int curlink = 0;
473 chains.clear();
474 ChainEnd chain = endlist[0];
475 ChainEnd nextchain = endlist[1];
476 CurveLink link = linklist[0];
477 CurveLink nextlink = linklist[1];
478 while (chain != null || link != null) {
479 /*
480 * Strategy 1:
481 * Connect chains or links if they are the only things left...
482 */
483 boolean connectchains = (link == null);
484 boolean connectlinks = (chain == null);
485
486 if (!connectchains && !connectlinks) {
487 // assert(link != null && chain != null);
488 /*
489 * Strategy 2:
490 * Connect chains or links if they close off an open area...
491 */
492 connectchains = ((curchain & 1) == 0 &&
493 chain.getX() == nextchain.getX());
494 connectlinks = ((curlink & 1) == 0 &&
495 link.getX() == nextlink.getX());
496
497 if (!connectchains && !connectlinks) {
498 /*
499 * Strategy 3:
500 * Connect chains or links if their successor is
501 * between them and their potential connectee...
502 */
503 double cx = chain.getX();
504 double lx = link.getX();
505 connectchains =
506 (nextchain != null && cx < lx &&
507 obstructs(nextchain.getX(), lx, curchain));
508 connectlinks =
509 (nextlink != null && lx < cx &&
510 obstructs(nextlink.getX(), cx, curlink));
511 }
512 }
513 if (connectchains) {
514 CurveLink subcurve = chain.linkTo(nextchain);
515 if (subcurve != null) {
516 subcurves.add(subcurve);
517 }
518 curchain += 2;
519 chain = endlist[curchain];
520 nextchain = endlist[curchain+1];
521 }
522 if (connectlinks) {
523 ChainEnd openend = new ChainEnd(link, null);
524 ChainEnd closeend = new ChainEnd(nextlink, openend);
525 openend.setOtherEnd(closeend);
526 chains.add(openend);
527 chains.add(closeend);
528 curlink += 2;
529 link = linklist[curlink];
530 nextlink = linklist[curlink+1];
531 }
532 if (!connectchains && !connectlinks) {
533 // assert(link != null);
534 // assert(chain != null);
535 // assert(chain.getEtag() == link.getEtag());
536 chain.addLink(link);
537 chains.add(chain);
538 curchain++;
539 chain = nextchain;
540 nextchain = endlist[curchain+1];
541 curlink++;
542 link = nextlink;
543 nextlink = linklist[curlink+1];
544 }
545 }
546 if ((chains.size() & 1) != 0) {
547 System.out.println("Odd number of chains!");
548 }
549 }
550
551 /*
552 * Does the position of the next edge at v1 "obstruct" the
553 * connectivity between current edge and the potential
554 * partner edge which is positioned at v2?
555 *
556 * Phase tells us whether we are testing for a transition
557 * into or out of the interior part of the resulting area.
558 *
559 * Require 4-connected continuity if this edge and the partner
560 * edge are both "entering into" type edges
561 * Allow 8-connected continuity for "exiting from" type edges
562 */
563 public static boolean obstructs(double v1, double v2, int phase) {
564 return (((phase & 1) == 0) ? (v1 <= v2) : (v1 < v2));
565 }
566 }