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.awt.geom.PathIterator;
029: import java.util.Vector;
030: import java.util.Enumeration;
031:
032: public abstract class Crossings {
033: public static final boolean debug = false;
034:
035: int limit = 0;
036: double yranges[] = new double[10];
037:
038: double xlo, ylo, xhi, yhi;
039:
040: public Crossings(double xlo, double ylo, double xhi, double yhi) {
041: this .xlo = xlo;
042: this .ylo = ylo;
043: this .xhi = xhi;
044: this .yhi = yhi;
045: }
046:
047: public final double getXLo() {
048: return xlo;
049: }
050:
051: public final double getYLo() {
052: return ylo;
053: }
054:
055: public final double getXHi() {
056: return xhi;
057: }
058:
059: public final double getYHi() {
060: return yhi;
061: }
062:
063: public abstract void record(double ystart, double yend,
064: int direction);
065:
066: public void print() {
067: System.out.println("Crossings [");
068: System.out.println(" bounds = [" + ylo + ", " + yhi + "]");
069: for (int i = 0; i < limit; i += 2) {
070: System.out.println(" [" + yranges[i] + ", "
071: + yranges[i + 1] + "]");
072: }
073: System.out.println("]");
074: }
075:
076: public final boolean isEmpty() {
077: return (limit == 0);
078: }
079:
080: public abstract boolean covers(double ystart, double yend);
081:
082: public static Crossings findCrossings(Vector curves, double xlo,
083: double ylo, double xhi, double yhi) {
084: Crossings cross = new EvenOdd(xlo, ylo, xhi, yhi);
085: Enumeration enum_ = curves.elements();
086: while (enum_.hasMoreElements()) {
087: Curve c = (Curve) enum_.nextElement();
088: if (c.accumulateCrossings(cross)) {
089: return null;
090: }
091: }
092: if (debug) {
093: cross.print();
094: }
095: return cross;
096: }
097:
098: public static Crossings findCrossings(PathIterator pi, double xlo,
099: double ylo, double xhi, double yhi) {
100: Crossings cross;
101: if (pi.getWindingRule() == pi.WIND_EVEN_ODD) {
102: cross = new EvenOdd(xlo, ylo, xhi, yhi);
103: } else {
104: cross = new NonZero(xlo, ylo, xhi, yhi);
105: }
106: // coords array is big enough for holding:
107: // coordinates returned from currentSegment (6)
108: // OR
109: // two subdivided quadratic curves (2+4+4=10)
110: // AND
111: // 0-1 horizontal splitting parameters
112: // OR
113: // 2 parametric equation derivative coefficients
114: // OR
115: // three subdivided cubic curves (2+6+6+6=20)
116: // AND
117: // 0-2 horizontal splitting parameters
118: // OR
119: // 3 parametric equation derivative coefficients
120: double coords[] = new double[23];
121: double movx = 0;
122: double movy = 0;
123: double curx = 0;
124: double cury = 0;
125: double newx, newy;
126: while (!pi.isDone()) {
127: int type = pi.currentSegment(coords);
128: switch (type) {
129: case PathIterator.SEG_MOVETO:
130: if (movy != cury
131: && cross.accumulateLine(curx, cury, movx, movy)) {
132: return null;
133: }
134: movx = curx = coords[0];
135: movy = cury = coords[1];
136: break;
137: case PathIterator.SEG_LINETO:
138: newx = coords[0];
139: newy = coords[1];
140: if (cross.accumulateLine(curx, cury, newx, newy)) {
141: return null;
142: }
143: curx = newx;
144: cury = newy;
145: break;
146: case PathIterator.SEG_QUADTO:
147: newx = coords[2];
148: newy = coords[3];
149: if (cross.accumulateQuad(curx, cury, coords)) {
150: return null;
151: }
152: curx = newx;
153: cury = newy;
154: break;
155: case PathIterator.SEG_CUBICTO:
156: newx = coords[4];
157: newy = coords[5];
158: if (cross.accumulateCubic(curx, cury, coords)) {
159: return null;
160: }
161: curx = newx;
162: cury = newy;
163: break;
164: case PathIterator.SEG_CLOSE:
165: if (movy != cury
166: && cross.accumulateLine(curx, cury, movx, movy)) {
167: return null;
168: }
169: curx = movx;
170: cury = movy;
171: break;
172: }
173: pi.next();
174: }
175: if (movy != cury) {
176: if (cross.accumulateLine(curx, cury, movx, movy)) {
177: return null;
178: }
179: }
180: if (debug) {
181: cross.print();
182: }
183: return cross;
184: }
185:
186: public boolean accumulateLine(double x0, double y0, double x1,
187: double y1) {
188: if (y0 <= y1) {
189: return accumulateLine(x0, y0, x1, y1, 1);
190: } else {
191: return accumulateLine(x1, y1, x0, y0, -1);
192: }
193: }
194:
195: public boolean accumulateLine(double x0, double y0, double x1,
196: double y1, int direction) {
197: if (yhi <= y0 || ylo >= y1) {
198: return false;
199: }
200: if (x0 >= xhi && x1 >= xhi) {
201: return false;
202: }
203: if (y0 == y1) {
204: return (x0 >= xlo || x1 >= xlo);
205: }
206: double xstart, ystart, xend, yend;
207: double dx = (x1 - x0);
208: double dy = (y1 - y0);
209: if (y0 < ylo) {
210: xstart = x0 + (ylo - y0) * dx / dy;
211: ystart = ylo;
212: } else {
213: xstart = x0;
214: ystart = y0;
215: }
216: if (yhi < y1) {
217: xend = x0 + (yhi - y0) * dx / dy;
218: yend = yhi;
219: } else {
220: xend = x1;
221: yend = y1;
222: }
223: if (xstart >= xhi && xend >= xhi) {
224: return false;
225: }
226: if (xstart > xlo || xend > xlo) {
227: return true;
228: }
229: record(ystart, yend, direction);
230: return false;
231: }
232:
233: private Vector tmp = new Vector();
234:
235: public boolean accumulateQuad(double x0, double y0, double coords[]) {
236: if (y0 < ylo && coords[1] < ylo && coords[3] < ylo) {
237: return false;
238: }
239: if (y0 > yhi && coords[1] > yhi && coords[3] > yhi) {
240: return false;
241: }
242: if (x0 > xhi && coords[0] > xhi && coords[2] > xhi) {
243: return false;
244: }
245: if (x0 < xlo && coords[0] < xlo && coords[2] < xlo) {
246: if (y0 < coords[3]) {
247: record(Math.max(y0, ylo), Math.min(coords[3], yhi), 1);
248: } else if (y0 > coords[3]) {
249: record(Math.max(coords[3], ylo), Math.min(y0, yhi), -1);
250: }
251: return false;
252: }
253: Curve.insertQuad(tmp, x0, y0, coords);
254: Enumeration enum_ = tmp.elements();
255: while (enum_.hasMoreElements()) {
256: Curve c = (Curve) enum_.nextElement();
257: if (c.accumulateCrossings(this )) {
258: return true;
259: }
260: }
261: tmp.clear();
262: return false;
263: }
264:
265: public boolean accumulateCubic(double x0, double y0,
266: double coords[]) {
267: if (y0 < ylo && coords[1] < ylo && coords[3] < ylo
268: && coords[5] < ylo) {
269: return false;
270: }
271: if (y0 > yhi && coords[1] > yhi && coords[3] > yhi
272: && coords[5] > yhi) {
273: return false;
274: }
275: if (x0 > xhi && coords[0] > xhi && coords[2] > xhi
276: && coords[4] > xhi) {
277: return false;
278: }
279: if (x0 < xlo && coords[0] < xlo && coords[2] < xlo
280: && coords[4] < xlo) {
281: if (y0 <= coords[5]) {
282: record(Math.max(y0, ylo), Math.min(coords[5], yhi), 1);
283: } else {
284: record(Math.max(coords[5], ylo), Math.min(y0, yhi), -1);
285: }
286: return false;
287: }
288: Curve.insertCubic(tmp, x0, y0, coords);
289: Enumeration enum_ = tmp.elements();
290: while (enum_.hasMoreElements()) {
291: Curve c = (Curve) enum_.nextElement();
292: if (c.accumulateCrossings(this )) {
293: return true;
294: }
295: }
296: tmp.clear();
297: return false;
298: }
299:
300: public final static class EvenOdd extends Crossings {
301: public EvenOdd(double xlo, double ylo, double xhi, double yhi) {
302: super (xlo, ylo, xhi, yhi);
303: }
304:
305: public final boolean covers(double ystart, double yend) {
306: return (limit == 2 && yranges[0] <= ystart && yranges[1] >= yend);
307: }
308:
309: public void record(double ystart, double yend, int direction) {
310: if (ystart >= yend) {
311: return;
312: }
313: int from = 0;
314: // Quickly jump over all pairs that are completely "above"
315: while (from < limit && ystart > yranges[from + 1]) {
316: from += 2;
317: }
318: int to = from;
319: while (from < limit) {
320: double yrlo = yranges[from++];
321: double yrhi = yranges[from++];
322: if (yend < yrlo) {
323: // Quickly handle insertion of the new range
324: yranges[to++] = ystart;
325: yranges[to++] = yend;
326: ystart = yrlo;
327: yend = yrhi;
328: continue;
329: }
330: // The ranges overlap - sort, collapse, insert, iterate
331: double yll, ylh, yhl, yhh;
332: if (ystart < yrlo) {
333: yll = ystart;
334: ylh = yrlo;
335: } else {
336: yll = yrlo;
337: ylh = ystart;
338: }
339: if (yend < yrhi) {
340: yhl = yend;
341: yhh = yrhi;
342: } else {
343: yhl = yrhi;
344: yhh = yend;
345: }
346: if (ylh == yhl) {
347: ystart = yll;
348: yend = yhh;
349: } else {
350: if (ylh > yhl) {
351: ystart = yhl;
352: yhl = ylh;
353: ylh = ystart;
354: }
355: if (yll != ylh) {
356: yranges[to++] = yll;
357: yranges[to++] = ylh;
358: }
359: ystart = yhl;
360: yend = yhh;
361: }
362: if (ystart >= yend) {
363: break;
364: }
365: }
366: if (to < from && from < limit) {
367: System.arraycopy(yranges, from, yranges, to, limit
368: - from);
369: }
370: to += (limit - from);
371: if (ystart < yend) {
372: if (to >= yranges.length) {
373: double newranges[] = new double[to + 10];
374: System.arraycopy(yranges, 0, newranges, 0, to);
375: yranges = newranges;
376: }
377: yranges[to++] = ystart;
378: yranges[to++] = yend;
379: }
380: limit = to;
381: }
382: }
383:
384: public final static class NonZero extends Crossings {
385: private int crosscounts[];
386:
387: public NonZero(double xlo, double ylo, double xhi, double yhi) {
388: super (xlo, ylo, xhi, yhi);
389: crosscounts = new int[yranges.length / 2];
390: }
391:
392: public final boolean covers(double ystart, double yend) {
393: int i = 0;
394: while (i < limit) {
395: double ylo = yranges[i++];
396: double yhi = yranges[i++];
397: if (ystart >= yhi) {
398: continue;
399: }
400: if (ystart < ylo) {
401: return false;
402: }
403: if (yend <= yhi) {
404: return true;
405: }
406: ystart = yhi;
407: }
408: return (ystart >= yend);
409: }
410:
411: public void remove(int cur) {
412: limit -= 2;
413: int rem = limit - cur;
414: if (rem > 0) {
415: System.arraycopy(yranges, cur + 2, yranges, cur, rem);
416: System.arraycopy(crosscounts, cur / 2 + 1, crosscounts,
417: cur / 2, rem / 2);
418: }
419: }
420:
421: public void insert(int cur, double lo, double hi, int dir) {
422: int rem = limit - cur;
423: double oldranges[] = yranges;
424: int oldcounts[] = crosscounts;
425: if (limit >= yranges.length) {
426: yranges = new double[limit + 10];
427: System.arraycopy(oldranges, 0, yranges, 0, cur);
428: crosscounts = new int[(limit + 10) / 2];
429: System.arraycopy(oldcounts, 0, crosscounts, 0, cur / 2);
430: }
431: if (rem > 0) {
432: System.arraycopy(oldranges, cur, yranges, cur + 2, rem);
433: System.arraycopy(oldcounts, cur / 2, crosscounts,
434: cur / 2 + 1, rem / 2);
435: }
436: yranges[cur + 0] = lo;
437: yranges[cur + 1] = hi;
438: crosscounts[cur / 2] = dir;
439: limit += 2;
440: }
441:
442: public void record(double ystart, double yend, int direction) {
443: if (ystart >= yend) {
444: return;
445: }
446: int cur = 0;
447: // Quickly jump over all pairs that are completely "above"
448: while (cur < limit && ystart > yranges[cur + 1]) {
449: cur += 2;
450: }
451: if (cur < limit) {
452: int rdir = crosscounts[cur / 2];
453: double yrlo = yranges[cur + 0];
454: double yrhi = yranges[cur + 1];
455: if (yrhi == ystart && rdir == direction) {
456: // Remove the range from the list and collapse it
457: // into the range being inserted. Note that the
458: // new combined range may overlap the following range
459: // so we must not simply combine the ranges in place
460: // unless we are at the last range.
461: if (cur + 2 == limit) {
462: yranges[cur + 1] = yend;
463: return;
464: }
465: remove(cur);
466: ystart = yrlo;
467: rdir = crosscounts[cur / 2];
468: yrlo = yranges[cur + 0];
469: yrhi = yranges[cur + 1];
470: }
471: if (yend < yrlo) {
472: // Just insert the new range at the current location
473: insert(cur, ystart, yend, direction);
474: return;
475: }
476: if (yend == yrlo && rdir == direction) {
477: // Just prepend the new range to the current one
478: yranges[cur] = ystart;
479: return;
480: }
481: // The ranges must overlap - (yend > yrlo && yrhi > ystart)
482: if (ystart < yrlo) {
483: insert(cur, ystart, yrlo, direction);
484: cur += 2;
485: ystart = yrlo;
486: } else if (yrlo < ystart) {
487: insert(cur, yrlo, ystart, rdir);
488: cur += 2;
489: yrlo = ystart;
490: }
491: // assert(yrlo == ystart);
492: int newdir = rdir + direction;
493: double newend = Math.min(yend, yrhi);
494: if (newdir == 0) {
495: remove(cur);
496: } else {
497: crosscounts[cur / 2] = newdir;
498: yranges[cur++] = ystart;
499: yranges[cur++] = newend;
500: }
501: ystart = yrlo = newend;
502: if (yrlo < yrhi) {
503: insert(cur, yrlo, yrhi, rdir);
504: }
505: }
506: if (ystart < yend) {
507: insert(cur, ystart, yend, direction);
508: }
509: }
510: }
511: }
|