root / branches / v2_0_0_prep / libraries / org.gvsig.openjdk.v1_6 / src / main / java / org / gvsig / openjdk / v1_6 / sun / awt / geom / Crossings.java @ 31668
History | View | Annotate | Download (17.1 KB)
1 |
/*
|
---|---|
2 |
* Copyright 1998-2003 Sun Microsystems, Inc. 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. Sun designates this
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
9 |
* by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
22 |
* CA 95054 USA or visit www.sun.com if you need additional information or
|
23 |
* have any questions.
|
24 |
*/
|
25 |
|
26 |
package org.gvsig.openjdk.v1_6.sun.awt.geom; |
27 |
|
28 |
import java.awt.geom.PathIterator; |
29 |
import java.util.Enumeration; |
30 |
import java.util.Vector; |
31 |
|
32 |
abstract class Crossings { |
33 |
public static final boolean debug = false; |
34 |
|
35 |
int limit = 0; |
36 |
double yranges[] = new double[10]; |
37 |
|
38 |
double xlo, ylo, xhi, yhi;
|
39 |
|
40 |
Crossings(double xlo, double ylo, double xhi, double yhi) { |
41 |
this.xlo = xlo;
|
42 |
this.ylo = ylo;
|
43 |
this.xhi = xhi;
|
44 |
this.yhi = yhi;
|
45 |
} |
46 |
|
47 |
public final double getXLo() { |
48 |
return xlo;
|
49 |
} |
50 |
|
51 |
public final double getYLo() { |
52 |
return ylo;
|
53 |
} |
54 |
|
55 |
public final double getXHi() { |
56 |
return xhi;
|
57 |
} |
58 |
|
59 |
public final double getYHi() { |
60 |
return yhi;
|
61 |
} |
62 |
|
63 |
public abstract void record(double ystart, double yend, int direction); |
64 |
|
65 |
public void print() { |
66 |
System.out.println("Crossings ["); |
67 |
System.out.println(" bounds = ["+ylo+", "+yhi+"]"); |
68 |
for (int i = 0; i < limit; i += 2) { |
69 |
System.out.println(" ["+yranges[i]+", "+yranges[i+1]+"]"); |
70 |
} |
71 |
System.out.println("]"); |
72 |
} |
73 |
|
74 |
public final boolean isEmpty() { |
75 |
return (limit == 0); |
76 |
} |
77 |
|
78 |
public abstract boolean covers(double ystart, double yend); |
79 |
|
80 |
public static Crossings findCrossings(Vector curves, |
81 |
double xlo, double ylo, |
82 |
double xhi, double yhi) |
83 |
{ |
84 |
Crossings cross = new EvenOdd(xlo, ylo, xhi, yhi);
|
85 |
Enumeration enum_ = curves.elements();
|
86 |
while (enum_.hasMoreElements()) {
|
87 |
Curve c = (Curve) enum_.nextElement(); |
88 |
if (c.accumulateCrossings(cross)) {
|
89 |
return null; |
90 |
} |
91 |
} |
92 |
if (debug) {
|
93 |
cross.print(); |
94 |
} |
95 |
return cross;
|
96 |
} |
97 |
|
98 |
public static Crossings findCrossings(PathIterator pi, |
99 |
double xlo, double ylo, |
100 |
double xhi, double yhi) |
101 |
{ |
102 |
Crossings cross; |
103 |
if (pi.getWindingRule() == pi.WIND_EVEN_ODD) {
|
104 |
cross = new EvenOdd(xlo, ylo, xhi, yhi);
|
105 |
} else {
|
106 |
cross = new NonZero(xlo, ylo, xhi, yhi);
|
107 |
} |
108 |
// coords array is big enough for holding:
|
109 |
// coordinates returned from currentSegment (6)
|
110 |
// OR
|
111 |
// two subdivided quadratic curves (2+4+4=10)
|
112 |
// AND
|
113 |
// 0-1 horizontal splitting parameters
|
114 |
// OR
|
115 |
// 2 parametric equation derivative coefficients
|
116 |
// OR
|
117 |
// three subdivided cubic curves (2+6+6+6=20)
|
118 |
// AND
|
119 |
// 0-2 horizontal splitting parameters
|
120 |
// OR
|
121 |
// 3 parametric equation derivative coefficients
|
122 |
double coords[] = new double[23]; |
123 |
double movx = 0; |
124 |
double movy = 0; |
125 |
double curx = 0; |
126 |
double cury = 0; |
127 |
double newx, newy;
|
128 |
while (!pi.isDone()) {
|
129 |
int type = pi.currentSegment(coords);
|
130 |
switch (type) {
|
131 |
case PathIterator.SEG_MOVETO: |
132 |
if (movy != cury &&
|
133 |
cross.accumulateLine(curx, cury, movx, movy)) |
134 |
{ |
135 |
return null; |
136 |
} |
137 |
movx = curx = coords[0];
|
138 |
movy = cury = coords[1];
|
139 |
break;
|
140 |
case PathIterator.SEG_LINETO: |
141 |
newx = coords[0];
|
142 |
newy = coords[1];
|
143 |
if (cross.accumulateLine(curx, cury, newx, newy)) {
|
144 |
return null; |
145 |
} |
146 |
curx = newx; |
147 |
cury = newy; |
148 |
break;
|
149 |
case PathIterator.SEG_QUADTO: |
150 |
newx = coords[2];
|
151 |
newy = coords[3];
|
152 |
if (cross.accumulateQuad(curx, cury, coords)) {
|
153 |
return null; |
154 |
} |
155 |
curx = newx; |
156 |
cury = newy; |
157 |
break;
|
158 |
case PathIterator.SEG_CUBICTO: |
159 |
newx = coords[4];
|
160 |
newy = coords[5];
|
161 |
if (cross.accumulateCubic(curx, cury, coords)) {
|
162 |
return null; |
163 |
} |
164 |
curx = newx; |
165 |
cury = newy; |
166 |
break;
|
167 |
case PathIterator.SEG_CLOSE: |
168 |
if (movy != cury &&
|
169 |
cross.accumulateLine(curx, cury, movx, movy)) |
170 |
{ |
171 |
return null; |
172 |
} |
173 |
curx = movx; |
174 |
cury = movy; |
175 |
break;
|
176 |
} |
177 |
pi.next(); |
178 |
} |
179 |
if (movy != cury) {
|
180 |
if (cross.accumulateLine(curx, cury, movx, movy)) {
|
181 |
return null; |
182 |
} |
183 |
} |
184 |
if (debug) {
|
185 |
cross.print(); |
186 |
} |
187 |
return cross;
|
188 |
} |
189 |
|
190 |
public boolean accumulateLine(double x0, double y0, |
191 |
double x1, double y1) |
192 |
{ |
193 |
if (y0 <= y1) {
|
194 |
return accumulateLine(x0, y0, x1, y1, 1); |
195 |
} else {
|
196 |
return accumulateLine(x1, y1, x0, y0, -1); |
197 |
} |
198 |
} |
199 |
|
200 |
public boolean accumulateLine(double x0, double y0, |
201 |
double x1, double y1, |
202 |
int direction)
|
203 |
{ |
204 |
if (yhi <= y0 || ylo >= y1) {
|
205 |
return false; |
206 |
} |
207 |
if (x0 >= xhi && x1 >= xhi) {
|
208 |
return false; |
209 |
} |
210 |
if (y0 == y1) {
|
211 |
return (x0 >= xlo || x1 >= xlo);
|
212 |
} |
213 |
double xstart, ystart, xend, yend;
|
214 |
double dx = (x1 - x0);
|
215 |
double dy = (y1 - y0);
|
216 |
if (y0 < ylo) {
|
217 |
xstart = x0 + (ylo - y0) * dx / dy; |
218 |
ystart = ylo; |
219 |
} else {
|
220 |
xstart = x0; |
221 |
ystart = y0; |
222 |
} |
223 |
if (yhi < y1) {
|
224 |
xend = x0 + (yhi - y0) * dx / dy; |
225 |
yend = yhi; |
226 |
} else {
|
227 |
xend = x1; |
228 |
yend = y1; |
229 |
} |
230 |
if (xstart >= xhi && xend >= xhi) {
|
231 |
return false; |
232 |
} |
233 |
if (xstart > xlo || xend > xlo) {
|
234 |
return true; |
235 |
} |
236 |
record(ystart, yend, direction); |
237 |
return false; |
238 |
} |
239 |
|
240 |
private Vector tmp = new Vector(); |
241 |
|
242 |
public boolean accumulateQuad(double x0, double y0, double coords[]) { |
243 |
if (y0 < ylo && coords[1] < ylo && coords[3] < ylo) { |
244 |
return false; |
245 |
} |
246 |
if (y0 > yhi && coords[1] > yhi && coords[3] > yhi) { |
247 |
return false; |
248 |
} |
249 |
if (x0 > xhi && coords[0] > xhi && coords[2] > xhi) { |
250 |
return false; |
251 |
} |
252 |
if (x0 < xlo && coords[0] < xlo && coords[2] < xlo) { |
253 |
if (y0 < coords[3]) { |
254 |
record(Math.max(y0, ylo), Math.min(coords[3], yhi), 1); |
255 |
} else if (y0 > coords[3]) { |
256 |
record(Math.max(coords[3], ylo), Math.min(y0, yhi), -1); |
257 |
} |
258 |
return false; |
259 |
} |
260 |
Curve.insertQuad(tmp, x0, y0, coords); |
261 |
Enumeration enum_ = tmp.elements();
|
262 |
while (enum_.hasMoreElements()) {
|
263 |
Curve c = (Curve) enum_.nextElement(); |
264 |
if (c.accumulateCrossings(this)) { |
265 |
return true; |
266 |
} |
267 |
} |
268 |
tmp.clear(); |
269 |
return false; |
270 |
} |
271 |
|
272 |
public boolean accumulateCubic(double x0, double y0, double coords[]) { |
273 |
if (y0 < ylo && coords[1] < ylo && |
274 |
coords[3] < ylo && coords[5] < ylo) |
275 |
{ |
276 |
return false; |
277 |
} |
278 |
if (y0 > yhi && coords[1] > yhi && |
279 |
coords[3] > yhi && coords[5] > yhi) |
280 |
{ |
281 |
return false; |
282 |
} |
283 |
if (x0 > xhi && coords[0] > xhi && |
284 |
coords[2] > xhi && coords[4] > xhi) |
285 |
{ |
286 |
return false; |
287 |
} |
288 |
if (x0 < xlo && coords[0] < xlo && |
289 |
coords[2] < xlo && coords[4] < xlo) |
290 |
{ |
291 |
if (y0 <= coords[5]) { |
292 |
record(Math.max(y0, ylo), Math.min(coords[5], yhi), 1); |
293 |
} else {
|
294 |
record(Math.max(coords[5], ylo), Math.min(y0, yhi), -1); |
295 |
} |
296 |
return false; |
297 |
} |
298 |
Curve.insertCubic(tmp, x0, y0, coords); |
299 |
Enumeration enum_ = tmp.elements();
|
300 |
while (enum_.hasMoreElements()) {
|
301 |
Curve c = (Curve) enum_.nextElement(); |
302 |
if (c.accumulateCrossings(this)) { |
303 |
return true; |
304 |
} |
305 |
} |
306 |
tmp.clear(); |
307 |
return false; |
308 |
} |
309 |
|
310 |
final static class EvenOdd extends Crossings { |
311 |
public EvenOdd(double xlo, double ylo, double xhi, double yhi) { |
312 |
super(xlo, ylo, xhi, yhi);
|
313 |
} |
314 |
|
315 |
public final boolean covers(double ystart, double yend) { |
316 |
return (limit == 2 && yranges[0] <= ystart && yranges[1] >= yend); |
317 |
} |
318 |
|
319 |
public void record(double ystart, double yend, int direction) { |
320 |
if (ystart >= yend) {
|
321 |
return;
|
322 |
} |
323 |
int from = 0; |
324 |
// Quickly jump over all pairs that are completely "above"
|
325 |
while (from < limit && ystart > yranges[from+1]) { |
326 |
from += 2;
|
327 |
} |
328 |
int to = from;
|
329 |
while (from < limit) {
|
330 |
double yrlo = yranges[from++];
|
331 |
double yrhi = yranges[from++];
|
332 |
if (yend < yrlo) {
|
333 |
// Quickly handle insertion of the new range
|
334 |
yranges[to++] = ystart; |
335 |
yranges[to++] = yend; |
336 |
ystart = yrlo; |
337 |
yend = yrhi; |
338 |
continue;
|
339 |
} |
340 |
// The ranges overlap - sort, collapse, insert, iterate
|
341 |
double yll, ylh, yhl, yhh;
|
342 |
if (ystart < yrlo) {
|
343 |
yll = ystart; |
344 |
ylh = yrlo; |
345 |
} else {
|
346 |
yll = yrlo; |
347 |
ylh = ystart; |
348 |
} |
349 |
if (yend < yrhi) {
|
350 |
yhl = yend; |
351 |
yhh = yrhi; |
352 |
} else {
|
353 |
yhl = yrhi; |
354 |
yhh = yend; |
355 |
} |
356 |
if (ylh == yhl) {
|
357 |
ystart = yll; |
358 |
yend = yhh; |
359 |
} else {
|
360 |
if (ylh > yhl) {
|
361 |
ystart = yhl; |
362 |
yhl = ylh; |
363 |
ylh = ystart; |
364 |
} |
365 |
if (yll != ylh) {
|
366 |
yranges[to++] = yll; |
367 |
yranges[to++] = ylh; |
368 |
} |
369 |
ystart = yhl; |
370 |
yend = yhh; |
371 |
} |
372 |
if (ystart >= yend) {
|
373 |
break;
|
374 |
} |
375 |
} |
376 |
if (to < from && from < limit) {
|
377 |
System.arraycopy(yranges, from, yranges, to, limit-from);
|
378 |
} |
379 |
to += (limit-from); |
380 |
if (ystart < yend) {
|
381 |
if (to >= yranges.length) {
|
382 |
double newranges[] = new double[to+10]; |
383 |
System.arraycopy(yranges, 0, newranges, 0, to); |
384 |
yranges = newranges; |
385 |
} |
386 |
yranges[to++] = ystart; |
387 |
yranges[to++] = yend; |
388 |
} |
389 |
limit = to; |
390 |
} |
391 |
} |
392 |
|
393 |
final static class NonZero extends Crossings { |
394 |
private int crosscounts[]; |
395 |
|
396 |
public NonZero(double xlo, double ylo, double xhi, double yhi) { |
397 |
super(xlo, ylo, xhi, yhi);
|
398 |
crosscounts = new int[yranges.length / 2]; |
399 |
} |
400 |
|
401 |
public final boolean covers(double ystart, double yend) { |
402 |
int i = 0; |
403 |
while (i < limit) {
|
404 |
double ylo = yranges[i++];
|
405 |
double yhi = yranges[i++];
|
406 |
if (ystart >= yhi) {
|
407 |
continue;
|
408 |
} |
409 |
if (ystart < ylo) {
|
410 |
return false; |
411 |
} |
412 |
if (yend <= yhi) {
|
413 |
return true; |
414 |
} |
415 |
ystart = yhi; |
416 |
} |
417 |
return (ystart >= yend);
|
418 |
} |
419 |
|
420 |
public void remove(int cur) { |
421 |
limit -= 2;
|
422 |
int rem = limit - cur;
|
423 |
if (rem > 0) { |
424 |
System.arraycopy(yranges, cur+2, yranges, cur, rem); |
425 |
System.arraycopy(crosscounts, cur/2+1, |
426 |
crosscounts, cur/2,
|
427 |
rem/2);
|
428 |
} |
429 |
} |
430 |
|
431 |
public void insert(int cur, double lo, double hi, int dir) { |
432 |
int rem = limit - cur;
|
433 |
double oldranges[] = yranges; |
434 |
int oldcounts[] = crosscounts; |
435 |
if (limit >= yranges.length) {
|
436 |
yranges = new double[limit+10]; |
437 |
System.arraycopy(oldranges, 0, yranges, 0, cur); |
438 |
crosscounts = new int[(limit+10)/2]; |
439 |
System.arraycopy(oldcounts, 0, crosscounts, 0, cur/2); |
440 |
} |
441 |
if (rem > 0) { |
442 |
System.arraycopy(oldranges, cur, yranges, cur+2, rem); |
443 |
System.arraycopy(oldcounts, cur/2, |
444 |
crosscounts, cur/2+1, |
445 |
rem/2);
|
446 |
} |
447 |
yranges[cur+0] = lo;
|
448 |
yranges[cur+1] = hi;
|
449 |
crosscounts[cur/2] = dir;
|
450 |
limit += 2;
|
451 |
} |
452 |
|
453 |
public void record(double ystart, double yend, int direction) { |
454 |
if (ystart >= yend) {
|
455 |
return;
|
456 |
} |
457 |
int cur = 0; |
458 |
// Quickly jump over all pairs that are completely "above"
|
459 |
while (cur < limit && ystart > yranges[cur+1]) { |
460 |
cur += 2;
|
461 |
} |
462 |
if (cur < limit) {
|
463 |
int rdir = crosscounts[cur/2]; |
464 |
double yrlo = yranges[cur+0]; |
465 |
double yrhi = yranges[cur+1]; |
466 |
if (yrhi == ystart && rdir == direction) {
|
467 |
// Remove the range from the list and collapse it
|
468 |
// into the range being inserted. Note that the
|
469 |
// new combined range may overlap the following range
|
470 |
// so we must not simply combine the ranges in place
|
471 |
// unless we are at the last range.
|
472 |
if (cur+2 == limit) { |
473 |
yranges[cur+1] = yend;
|
474 |
return;
|
475 |
} |
476 |
remove(cur); |
477 |
ystart = yrlo; |
478 |
rdir = crosscounts[cur/2];
|
479 |
yrlo = yranges[cur+0];
|
480 |
yrhi = yranges[cur+1];
|
481 |
} |
482 |
if (yend < yrlo) {
|
483 |
// Just insert the new range at the current location
|
484 |
insert(cur, ystart, yend, direction); |
485 |
return;
|
486 |
} |
487 |
if (yend == yrlo && rdir == direction) {
|
488 |
// Just prepend the new range to the current one
|
489 |
yranges[cur] = ystart; |
490 |
return;
|
491 |
} |
492 |
// The ranges must overlap - (yend > yrlo && yrhi > ystart)
|
493 |
if (ystart < yrlo) {
|
494 |
insert(cur, ystart, yrlo, direction); |
495 |
cur += 2;
|
496 |
ystart = yrlo; |
497 |
} else if (yrlo < ystart) { |
498 |
insert(cur, yrlo, ystart, rdir); |
499 |
cur += 2;
|
500 |
yrlo = ystart; |
501 |
} |
502 |
// assert(yrlo == ystart);
|
503 |
int newdir = rdir + direction;
|
504 |
double newend = Math.min(yend, yrhi); |
505 |
if (newdir == 0) { |
506 |
remove(cur); |
507 |
} else {
|
508 |
crosscounts[cur/2] = newdir;
|
509 |
yranges[cur++] = ystart; |
510 |
yranges[cur++] = newend; |
511 |
} |
512 |
ystart = yrlo = newend; |
513 |
if (yrlo < yrhi) {
|
514 |
insert(cur, yrlo, yrhi, rdir); |
515 |
} |
516 |
} |
517 |
if (ystart < yend) {
|
518 |
insert(cur, ystart, yend, direction); |
519 |
} |
520 |
} |
521 |
} |
522 |
} |