root / org.gvsig.jdk / trunk / org.gvsig.jdk / org.gvsig.jdk.v1_6 / src / main / java / org / gvsig / jdk / sun / awt / geom / Curve.java
History | View | Annotate | Download (47.7 KB)
1 |
/*
|
---|---|
2 |
* Copyright 1998-2006 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.jdk.sun.awt.geom; |
27 |
|
28 |
import java.awt.geom.IllegalPathStateException; |
29 |
import java.awt.geom.PathIterator; |
30 |
import java.awt.geom.Rectangle2D; |
31 |
import java.util.Vector; |
32 |
|
33 |
public abstract class Curve { |
34 |
public static final int INCREASING = 1; |
35 |
public static final int DECREASING = -1; |
36 |
|
37 |
protected int direction; |
38 |
|
39 |
public static void insertMove(Vector curves, double x, double y) { |
40 |
curves.add(new Order0(x, y));
|
41 |
} |
42 |
|
43 |
public static void insertLine(Vector curves, |
44 |
double x0, double y0, |
45 |
double x1, double y1) |
46 |
{ |
47 |
if (y0 < y1) {
|
48 |
curves.add(new Order1(x0, y0,
|
49 |
x1, y1, |
50 |
INCREASING)); |
51 |
} else if (y0 > y1) { |
52 |
curves.add(new Order1(x1, y1,
|
53 |
x0, y0, |
54 |
DECREASING)); |
55 |
} else {
|
56 |
// Do not add horizontal lines
|
57 |
} |
58 |
} |
59 |
|
60 |
public static void insertQuad(Vector curves, |
61 |
double x0, double y0, |
62 |
double coords[]) |
63 |
{ |
64 |
double y1 = coords[3]; |
65 |
if (y0 > y1) {
|
66 |
Order2.insert(curves, coords, |
67 |
coords[2], y1,
|
68 |
coords[0], coords[1], |
69 |
x0, y0, |
70 |
DECREASING); |
71 |
} else if (y0 == y1 && y0 == coords[1]) { |
72 |
// Do not add horizontal lines
|
73 |
return;
|
74 |
} else {
|
75 |
Order2.insert(curves, coords, |
76 |
x0, y0, |
77 |
coords[0], coords[1], |
78 |
coords[2], y1,
|
79 |
INCREASING); |
80 |
} |
81 |
} |
82 |
|
83 |
public static void insertCubic(Vector curves, |
84 |
double x0, double y0, |
85 |
double coords[]) |
86 |
{ |
87 |
double y1 = coords[5]; |
88 |
if (y0 > y1) {
|
89 |
Order3.insert(curves, coords, |
90 |
coords[4], y1,
|
91 |
coords[2], coords[3], |
92 |
coords[0], coords[1], |
93 |
x0, y0, |
94 |
DECREASING); |
95 |
} else if (y0 == y1 && y0 == coords[1] && y0 == coords[3]) { |
96 |
// Do not add horizontal lines
|
97 |
return;
|
98 |
} else {
|
99 |
Order3.insert(curves, coords, |
100 |
x0, y0, |
101 |
coords[0], coords[1], |
102 |
coords[2], coords[3], |
103 |
coords[4], y1,
|
104 |
INCREASING); |
105 |
} |
106 |
} |
107 |
|
108 |
/**
|
109 |
* Calculates the number of times the given path
|
110 |
* crosses the ray extending to the right from (px,py).
|
111 |
* If the point lies on a part of the path,
|
112 |
* then no crossings are counted for that intersection.
|
113 |
* +1 is added for each crossing where the Y coordinate is increasing
|
114 |
* -1 is added for each crossing where the Y coordinate is decreasing
|
115 |
* The return value is the sum of all crossings for every segment in
|
116 |
* the path.
|
117 |
* The path must start with a SEG_MOVETO, otherwise an exception is
|
118 |
* thrown.
|
119 |
* The caller must check p[xy] for NaN values.
|
120 |
* The caller may also reject infinite p[xy] values as well.
|
121 |
*/
|
122 |
public static int pointCrossingsForPath(PathIterator pi, |
123 |
double px, double py) |
124 |
{ |
125 |
if (pi.isDone()) {
|
126 |
return 0; |
127 |
} |
128 |
double coords[] = new double[6]; |
129 |
if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) { |
130 |
throw new IllegalPathStateException("missing initial moveto "+ |
131 |
"in path definition");
|
132 |
} |
133 |
pi.next(); |
134 |
double movx = coords[0]; |
135 |
double movy = coords[1]; |
136 |
double curx = movx;
|
137 |
double cury = movy;
|
138 |
double endx, endy;
|
139 |
int crossings = 0; |
140 |
while (!pi.isDone()) {
|
141 |
switch (pi.currentSegment(coords)) {
|
142 |
case PathIterator.SEG_MOVETO: |
143 |
if (cury != movy) {
|
144 |
crossings += pointCrossingsForLine(px, py, |
145 |
curx, cury, |
146 |
movx, movy); |
147 |
} |
148 |
movx = curx = coords[0];
|
149 |
movy = cury = coords[1];
|
150 |
break;
|
151 |
case PathIterator.SEG_LINETO: |
152 |
endx = coords[0];
|
153 |
endy = coords[1];
|
154 |
crossings += pointCrossingsForLine(px, py, |
155 |
curx, cury, |
156 |
endx, endy); |
157 |
curx = endx; |
158 |
cury = endy; |
159 |
break;
|
160 |
case PathIterator.SEG_QUADTO: |
161 |
endx = coords[2];
|
162 |
endy = coords[3];
|
163 |
crossings += pointCrossingsForQuad(px, py, |
164 |
curx, cury, |
165 |
coords[0], coords[1], |
166 |
endx, endy, 0);
|
167 |
curx = endx; |
168 |
cury = endy; |
169 |
break;
|
170 |
case PathIterator.SEG_CUBICTO: |
171 |
endx = coords[4];
|
172 |
endy = coords[5];
|
173 |
crossings += pointCrossingsForCubic(px, py, |
174 |
curx, cury, |
175 |
coords[0], coords[1], |
176 |
coords[2], coords[3], |
177 |
endx, endy, 0);
|
178 |
curx = endx; |
179 |
cury = endy; |
180 |
break;
|
181 |
case PathIterator.SEG_CLOSE: |
182 |
if (cury != movy) {
|
183 |
crossings += pointCrossingsForLine(px, py, |
184 |
curx, cury, |
185 |
movx, movy); |
186 |
} |
187 |
curx = movx; |
188 |
cury = movy; |
189 |
break;
|
190 |
} |
191 |
pi.next(); |
192 |
} |
193 |
if (cury != movy) {
|
194 |
crossings += pointCrossingsForLine(px, py, |
195 |
curx, cury, |
196 |
movx, movy); |
197 |
} |
198 |
return crossings;
|
199 |
} |
200 |
|
201 |
/**
|
202 |
* Calculates the number of times the line from (x0,y0) to (x1,y1)
|
203 |
* crosses the ray extending to the right from (px,py).
|
204 |
* If the point lies on the line, then no crossings are recorded.
|
205 |
* +1 is returned for a crossing where the Y coordinate is increasing
|
206 |
* -1 is returned for a crossing where the Y coordinate is decreasing
|
207 |
*/
|
208 |
public static int pointCrossingsForLine(double px, double py, |
209 |
double x0, double y0, |
210 |
double x1, double y1) |
211 |
{ |
212 |
if (py < y0 && py < y1) return 0; |
213 |
if (py >= y0 && py >= y1) return 0; |
214 |
// assert(y0 != y1);
|
215 |
if (px >= x0 && px >= x1) return 0; |
216 |
if (px < x0 && px < x1) return (y0 < y1) ? 1 : -1; |
217 |
double xintercept = x0 + (py - y0) * (x1 - x0) / (y1 - y0);
|
218 |
if (px >= xintercept) return 0; |
219 |
return (y0 < y1) ? 1 : -1; |
220 |
} |
221 |
|
222 |
/**
|
223 |
* Calculates the number of times the quad from (x0,y0) to (x1,y1)
|
224 |
* crosses the ray extending to the right from (px,py).
|
225 |
* If the point lies on a part of the curve,
|
226 |
* then no crossings are counted for that intersection.
|
227 |
* the level parameter should be 0 at the top-level call and will count
|
228 |
* up for each recursion level to prevent infinite recursion
|
229 |
* +1 is added for each crossing where the Y coordinate is increasing
|
230 |
* -1 is added for each crossing where the Y coordinate is decreasing
|
231 |
*/
|
232 |
public static int pointCrossingsForQuad(double px, double py, |
233 |
double x0, double y0, |
234 |
double xc, double yc, |
235 |
double x1, double y1, int level) |
236 |
{ |
237 |
if (py < y0 && py < yc && py < y1) return 0; |
238 |
if (py >= y0 && py >= yc && py >= y1) return 0; |
239 |
// Note y0 could equal y1...
|
240 |
if (px >= x0 && px >= xc && px >= x1) return 0; |
241 |
if (px < x0 && px < xc && px < x1) {
|
242 |
if (py >= y0) {
|
243 |
if (py < y1) return 1; |
244 |
} else {
|
245 |
// py < y0
|
246 |
if (py >= y1) return -1; |
247 |
} |
248 |
// py outside of y01 range, and/or y0==y1
|
249 |
return 0; |
250 |
} |
251 |
// double precision only has 52 bits of mantissa
|
252 |
if (level > 52) return pointCrossingsForLine(px, py, x0, y0, x1, y1); |
253 |
double x0c = (x0 + xc) / 2; |
254 |
double y0c = (y0 + yc) / 2; |
255 |
double xc1 = (xc + x1) / 2; |
256 |
double yc1 = (yc + y1) / 2; |
257 |
xc = (x0c + xc1) / 2;
|
258 |
yc = (y0c + yc1) / 2;
|
259 |
if (Double.isNaN(xc) || Double.isNaN(yc)) { |
260 |
// [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN
|
261 |
// [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN
|
262 |
// These values are also NaN if opposing infinities are added
|
263 |
return 0; |
264 |
} |
265 |
return (pointCrossingsForQuad(px, py,
|
266 |
x0, y0, x0c, y0c, xc, yc, |
267 |
level+1) +
|
268 |
pointCrossingsForQuad(px, py, |
269 |
xc, yc, xc1, yc1, x1, y1, |
270 |
level+1));
|
271 |
} |
272 |
|
273 |
/**
|
274 |
* Calculates the number of times the cubic from (x0,y0) to (x1,y1)
|
275 |
* crosses the ray extending to the right from (px,py).
|
276 |
* If the point lies on a part of the curve,
|
277 |
* then no crossings are counted for that intersection.
|
278 |
* the level parameter should be 0 at the top-level call and will count
|
279 |
* up for each recursion level to prevent infinite recursion
|
280 |
* +1 is added for each crossing where the Y coordinate is increasing
|
281 |
* -1 is added for each crossing where the Y coordinate is decreasing
|
282 |
*/
|
283 |
public static int pointCrossingsForCubic(double px, double py, |
284 |
double x0, double y0, |
285 |
double xc0, double yc0, |
286 |
double xc1, double yc1, |
287 |
double x1, double y1, int level) |
288 |
{ |
289 |
if (py < y0 && py < yc0 && py < yc1 && py < y1) return 0; |
290 |
if (py >= y0 && py >= yc0 && py >= yc1 && py >= y1) return 0; |
291 |
// Note y0 could equal yc0...
|
292 |
if (px >= x0 && px >= xc0 && px >= xc1 && px >= x1) return 0; |
293 |
if (px < x0 && px < xc0 && px < xc1 && px < x1) {
|
294 |
if (py >= y0) {
|
295 |
if (py < y1) return 1; |
296 |
} else {
|
297 |
// py < y0
|
298 |
if (py >= y1) return -1; |
299 |
} |
300 |
// py outside of y01 range, and/or y0==yc0
|
301 |
return 0; |
302 |
} |
303 |
// double precision only has 52 bits of mantissa
|
304 |
if (level > 52) return pointCrossingsForLine(px, py, x0, y0, x1, y1); |
305 |
double xmid = (xc0 + xc1) / 2; |
306 |
double ymid = (yc0 + yc1) / 2; |
307 |
xc0 = (x0 + xc0) / 2;
|
308 |
yc0 = (y0 + yc0) / 2;
|
309 |
xc1 = (xc1 + x1) / 2;
|
310 |
yc1 = (yc1 + y1) / 2;
|
311 |
double xc0m = (xc0 + xmid) / 2; |
312 |
double yc0m = (yc0 + ymid) / 2; |
313 |
double xmc1 = (xmid + xc1) / 2; |
314 |
double ymc1 = (ymid + yc1) / 2; |
315 |
xmid = (xc0m + xmc1) / 2;
|
316 |
ymid = (yc0m + ymc1) / 2;
|
317 |
if (Double.isNaN(xmid) || Double.isNaN(ymid)) { |
318 |
// [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN
|
319 |
// [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN
|
320 |
// These values are also NaN if opposing infinities are added
|
321 |
return 0; |
322 |
} |
323 |
return (pointCrossingsForCubic(px, py,
|
324 |
x0, y0, xc0, yc0, |
325 |
xc0m, yc0m, xmid, ymid, level+1) +
|
326 |
pointCrossingsForCubic(px, py, |
327 |
xmid, ymid, xmc1, ymc1, |
328 |
xc1, yc1, x1, y1, level+1));
|
329 |
} |
330 |
|
331 |
/**
|
332 |
* The rectangle intersection test counts the number of times
|
333 |
* that the path crosses through the shadow that the rectangle
|
334 |
* projects to the right towards (x => +INFINITY).
|
335 |
*
|
336 |
* During processing of the path it actually counts every time
|
337 |
* the path crosses either or both of the top and bottom edges
|
338 |
* of that shadow. If the path enters from the top, the count
|
339 |
* is incremented. If it then exits back through the top, the
|
340 |
* same way it came in, the count is decremented and there is
|
341 |
* no impact on the winding count. If, instead, the path exits
|
342 |
* out the bottom, then the count is incremented again and a
|
343 |
* full pass through the shadow is indicated by the winding count
|
344 |
* having been incremented by 2.
|
345 |
*
|
346 |
* Thus, the winding count that it accumulates is actually double
|
347 |
* the real winding count. Since the path is continuous, the
|
348 |
* final answer should be a multiple of 2, otherwise there is a
|
349 |
* logic error somewhere.
|
350 |
*
|
351 |
* If the path ever has a direct hit on the rectangle, then a
|
352 |
* special value is returned. This special value terminates
|
353 |
* all ongoing accumulation on up through the call chain and
|
354 |
* ends up getting returned to the calling function which can
|
355 |
* then produce an answer directly. For intersection tests,
|
356 |
* the answer is always "true" if the path intersects the
|
357 |
* rectangle. For containment tests, the answer is always
|
358 |
* "false" if the path intersects the rectangle. Thus, no
|
359 |
* further processing is ever needed if an intersection occurs.
|
360 |
*/
|
361 |
public static final int RECT_INTERSECTS = 0x80000000; |
362 |
|
363 |
/**
|
364 |
* Accumulate the number of times the path crosses the shadow
|
365 |
* extending to the right of the rectangle. See the comment
|
366 |
* for the RECT_INTERSECTS constant for more complete details.
|
367 |
* The return value is the sum of all crossings for both the
|
368 |
* top and bottom of the shadow for every segment in the path,
|
369 |
* or the special value RECT_INTERSECTS if the path ever enters
|
370 |
* the interior of the rectangle.
|
371 |
* The path must start with a SEG_MOVETO, otherwise an exception is
|
372 |
* thrown.
|
373 |
* The caller must check r[xy]{min,max} for NaN values.
|
374 |
*/
|
375 |
public static int rectCrossingsForPath(PathIterator pi, |
376 |
double rxmin, double rymin, |
377 |
double rxmax, double rymax) |
378 |
{ |
379 |
if (rxmax <= rxmin || rymax <= rymin) {
|
380 |
return 0; |
381 |
} |
382 |
if (pi.isDone()) {
|
383 |
return 0; |
384 |
} |
385 |
double coords[] = new double[6]; |
386 |
if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) { |
387 |
throw new IllegalPathStateException("missing initial moveto "+ |
388 |
"in path definition");
|
389 |
} |
390 |
pi.next(); |
391 |
double curx, cury, movx, movy, endx, endy;
|
392 |
curx = movx = coords[0];
|
393 |
cury = movy = coords[1];
|
394 |
int crossings = 0; |
395 |
while (crossings != RECT_INTERSECTS && !pi.isDone()) {
|
396 |
switch (pi.currentSegment(coords)) {
|
397 |
case PathIterator.SEG_MOVETO: |
398 |
if (curx != movx || cury != movy) {
|
399 |
crossings = rectCrossingsForLine(crossings, |
400 |
rxmin, rymin, |
401 |
rxmax, rymax, |
402 |
curx, cury, |
403 |
movx, movy); |
404 |
} |
405 |
// Count should always be a multiple of 2 here.
|
406 |
// assert((crossings & 1) != 0);
|
407 |
movx = curx = coords[0];
|
408 |
movy = cury = coords[1];
|
409 |
break;
|
410 |
case PathIterator.SEG_LINETO: |
411 |
endx = coords[0];
|
412 |
endy = coords[1];
|
413 |
crossings = rectCrossingsForLine(crossings, |
414 |
rxmin, rymin, |
415 |
rxmax, rymax, |
416 |
curx, cury, |
417 |
endx, endy); |
418 |
curx = endx; |
419 |
cury = endy; |
420 |
break;
|
421 |
case PathIterator.SEG_QUADTO: |
422 |
endx = coords[2];
|
423 |
endy = coords[3];
|
424 |
crossings = rectCrossingsForQuad(crossings, |
425 |
rxmin, rymin, |
426 |
rxmax, rymax, |
427 |
curx, cury, |
428 |
coords[0], coords[1], |
429 |
endx, endy, 0);
|
430 |
curx = endx; |
431 |
cury = endy; |
432 |
break;
|
433 |
case PathIterator.SEG_CUBICTO: |
434 |
endx = coords[4];
|
435 |
endy = coords[5];
|
436 |
crossings = rectCrossingsForCubic(crossings, |
437 |
rxmin, rymin, |
438 |
rxmax, rymax, |
439 |
curx, cury, |
440 |
coords[0], coords[1], |
441 |
coords[2], coords[3], |
442 |
endx, endy, 0);
|
443 |
curx = endx; |
444 |
cury = endy; |
445 |
break;
|
446 |
case PathIterator.SEG_CLOSE: |
447 |
if (curx != movx || cury != movy) {
|
448 |
crossings = rectCrossingsForLine(crossings, |
449 |
rxmin, rymin, |
450 |
rxmax, rymax, |
451 |
curx, cury, |
452 |
movx, movy); |
453 |
} |
454 |
curx = movx; |
455 |
cury = movy; |
456 |
// Count should always be a multiple of 2 here.
|
457 |
// assert((crossings & 1) != 0);
|
458 |
break;
|
459 |
} |
460 |
pi.next(); |
461 |
} |
462 |
if (crossings != RECT_INTERSECTS && (curx != movx || cury != movy)) {
|
463 |
crossings = rectCrossingsForLine(crossings, |
464 |
rxmin, rymin, |
465 |
rxmax, rymax, |
466 |
curx, cury, |
467 |
movx, movy); |
468 |
} |
469 |
// Count should always be a multiple of 2 here.
|
470 |
// assert((crossings & 1) != 0);
|
471 |
return crossings;
|
472 |
} |
473 |
|
474 |
/**
|
475 |
* Accumulate the number of times the line crosses the shadow
|
476 |
* extending to the right of the rectangle. See the comment
|
477 |
* for the RECT_INTERSECTS constant for more complete details.
|
478 |
*/
|
479 |
public static int rectCrossingsForLine(int crossings, |
480 |
double rxmin, double rymin, |
481 |
double rxmax, double rymax, |
482 |
double x0, double y0, |
483 |
double x1, double y1) |
484 |
{ |
485 |
if (y0 >= rymax && y1 >= rymax) return crossings; |
486 |
if (y0 <= rymin && y1 <= rymin) return crossings; |
487 |
if (x0 <= rxmin && x1 <= rxmin) return crossings; |
488 |
if (x0 >= rxmax && x1 >= rxmax) {
|
489 |
// Line is entirely to the right of the rect
|
490 |
// and the vertical ranges of the two overlap by a non-empty amount
|
491 |
// Thus, this line segment is partially in the "right-shadow"
|
492 |
// Path may have done a complete crossing
|
493 |
// Or path may have entered or exited the right-shadow
|
494 |
if (y0 < y1) {
|
495 |
// y-increasing line segment...
|
496 |
// We know that y0 < rymax and y1 > rymin
|
497 |
if (y0 <= rymin) crossings++;
|
498 |
if (y1 >= rymax) crossings++;
|
499 |
} else if (y1 < y0) { |
500 |
// y-decreasing line segment...
|
501 |
// We know that y1 < rymax and y0 > rymin
|
502 |
if (y1 <= rymin) crossings--;
|
503 |
if (y0 >= rymax) crossings--;
|
504 |
} |
505 |
return crossings;
|
506 |
} |
507 |
// Remaining case:
|
508 |
// Both x and y ranges overlap by a non-empty amount
|
509 |
// First do trivial INTERSECTS rejection of the cases
|
510 |
// where one of the endpoints is inside the rectangle.
|
511 |
if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) ||
|
512 |
(x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) |
513 |
{ |
514 |
return RECT_INTERSECTS;
|
515 |
} |
516 |
// Otherwise calculate the y intercepts and see where
|
517 |
// they fall with respect to the rectangle
|
518 |
double xi0 = x0;
|
519 |
if (y0 < rymin) {
|
520 |
xi0 += ((rymin - y0) * (x1 - x0) / (y1 - y0)); |
521 |
} else if (y0 > rymax) { |
522 |
xi0 += ((rymax - y0) * (x1 - x0) / (y1 - y0)); |
523 |
} |
524 |
double xi1 = x1;
|
525 |
if (y1 < rymin) {
|
526 |
xi1 += ((rymin - y1) * (x0 - x1) / (y0 - y1)); |
527 |
} else if (y1 > rymax) { |
528 |
xi1 += ((rymax - y1) * (x0 - x1) / (y0 - y1)); |
529 |
} |
530 |
if (xi0 <= rxmin && xi1 <= rxmin) return crossings; |
531 |
if (xi0 >= rxmax && xi1 >= rxmax) {
|
532 |
if (y0 < y1) {
|
533 |
// y-increasing line segment...
|
534 |
// We know that y0 < rymax and y1 > rymin
|
535 |
if (y0 <= rymin) crossings++;
|
536 |
if (y1 >= rymax) crossings++;
|
537 |
} else if (y1 < y0) { |
538 |
// y-decreasing line segment...
|
539 |
// We know that y1 < rymax and y0 > rymin
|
540 |
if (y1 <= rymin) crossings--;
|
541 |
if (y0 >= rymax) crossings--;
|
542 |
} |
543 |
return crossings;
|
544 |
} |
545 |
return RECT_INTERSECTS;
|
546 |
} |
547 |
|
548 |
/**
|
549 |
* Accumulate the number of times the quad crosses the shadow
|
550 |
* extending to the right of the rectangle. See the comment
|
551 |
* for the RECT_INTERSECTS constant for more complete details.
|
552 |
*/
|
553 |
public static int rectCrossingsForQuad(int crossings, |
554 |
double rxmin, double rymin, |
555 |
double rxmax, double rymax, |
556 |
double x0, double y0, |
557 |
double xc, double yc, |
558 |
double x1, double y1, |
559 |
int level)
|
560 |
{ |
561 |
if (y0 >= rymax && yc >= rymax && y1 >= rymax) return crossings; |
562 |
if (y0 <= rymin && yc <= rymin && y1 <= rymin) return crossings; |
563 |
if (x0 <= rxmin && xc <= rxmin && x1 <= rxmin) return crossings; |
564 |
if (x0 >= rxmax && xc >= rxmax && x1 >= rxmax) {
|
565 |
// Quad is entirely to the right of the rect
|
566 |
// and the vertical range of the 3 Y coordinates of the quad
|
567 |
// overlaps the vertical range of the rect by a non-empty amount
|
568 |
// We now judge the crossings solely based on the line segment
|
569 |
// connecting the endpoints of the quad.
|
570 |
// Note that we may have 0, 1, or 2 crossings as the control
|
571 |
// point may be causing the Y range intersection while the
|
572 |
// two endpoints are entirely above or below.
|
573 |
if (y0 < y1) {
|
574 |
// y-increasing line segment...
|
575 |
if (y0 <= rymin && y1 > rymin) crossings++;
|
576 |
if (y0 < rymax && y1 >= rymax) crossings++;
|
577 |
} else if (y1 < y0) { |
578 |
// y-decreasing line segment...
|
579 |
if (y1 <= rymin && y0 > rymin) crossings--;
|
580 |
if (y1 < rymax && y0 >= rymax) crossings--;
|
581 |
} |
582 |
return crossings;
|
583 |
} |
584 |
// The intersection of ranges is more complicated
|
585 |
// First do trivial INTERSECTS rejection of the cases
|
586 |
// where one of the endpoints is inside the rectangle.
|
587 |
if ((x0 < rxmax && x0 > rxmin && y0 < rymax && y0 > rymin) ||
|
588 |
(x1 < rxmax && x1 > rxmin && y1 < rymax && y1 > rymin)) |
589 |
{ |
590 |
return RECT_INTERSECTS;
|
591 |
} |
592 |
// Otherwise, subdivide and look for one of the cases above.
|
593 |
// double precision only has 52 bits of mantissa
|
594 |
if (level > 52) { |
595 |
return rectCrossingsForLine(crossings,
|
596 |
rxmin, rymin, rxmax, rymax, |
597 |
x0, y0, x1, y1); |
598 |
} |
599 |
double x0c = (x0 + xc) / 2; |
600 |
double y0c = (y0 + yc) / 2; |
601 |
double xc1 = (xc + x1) / 2; |
602 |
double yc1 = (yc + y1) / 2; |
603 |
xc = (x0c + xc1) / 2;
|
604 |
yc = (y0c + yc1) / 2;
|
605 |
if (Double.isNaN(xc) || Double.isNaN(yc)) { |
606 |
// [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN
|
607 |
// [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN
|
608 |
// These values are also NaN if opposing infinities are added
|
609 |
return 0; |
610 |
} |
611 |
crossings = rectCrossingsForQuad(crossings, |
612 |
rxmin, rymin, rxmax, rymax, |
613 |
x0, y0, x0c, y0c, xc, yc, |
614 |
level+1);
|
615 |
if (crossings != RECT_INTERSECTS) {
|
616 |
crossings = rectCrossingsForQuad(crossings, |
617 |
rxmin, rymin, rxmax, rymax, |
618 |
xc, yc, xc1, yc1, x1, y1, |
619 |
level+1);
|
620 |
} |
621 |
return crossings;
|
622 |
} |
623 |
|
624 |
/**
|
625 |
* Accumulate the number of times the cubic crosses the shadow
|
626 |
* extending to the right of the rectangle. See the comment
|
627 |
* for the RECT_INTERSECTS constant for more complete details.
|
628 |
*/
|
629 |
public static int rectCrossingsForCubic(int crossings, |
630 |
double rxmin, double rymin, |
631 |
double rxmax, double rymax, |
632 |
double x0, double y0, |
633 |
double xc0, double yc0, |
634 |
double xc1, double yc1, |
635 |
double x1, double y1, |
636 |
int level)
|
637 |
{ |
638 |
if (y0 >= rymax && yc0 >= rymax && yc1 >= rymax && y1 >= rymax) {
|
639 |
return crossings;
|
640 |
} |
641 |
if (y0 <= rymin && yc0 <= rymin && yc1 <= rymin && y1 <= rymin) {
|
642 |
return crossings;
|
643 |
} |
644 |
if (x0 <= rxmin && xc0 <= rxmin && xc1 <= rxmin && x1 <= rxmin) {
|
645 |
return crossings;
|
646 |
} |
647 |
if (x0 >= rxmax && xc0 >= rxmax && xc1 >= rxmax && x1 >= rxmax) {
|
648 |
// Cubic is entirely to the right of the rect
|
649 |
// and the vertical range of the 4 Y coordinates of the cubic
|
650 |
// overlaps the vertical range of the rect by a non-empty amount
|
651 |
// We now judge the crossings solely based on the line segment
|
652 |
// connecting the endpoints of the cubic.
|
653 |
// Note that we may have 0, 1, or 2 crossings as the control
|
654 |
// points may be causing the Y range intersection while the
|
655 |
// two endpoints are entirely above or below.
|
656 |
if (y0 < y1) {
|
657 |
// y-increasing line segment...
|
658 |
if (y0 <= rymin && y1 > rymin) crossings++;
|
659 |
if (y0 < rymax && y1 >= rymax) crossings++;
|
660 |
} else if (y1 < y0) { |
661 |
// y-decreasing line segment...
|
662 |
if (y1 <= rymin && y0 > rymin) crossings--;
|
663 |
if (y1 < rymax && y0 >= rymax) crossings--;
|
664 |
} |
665 |
return crossings;
|
666 |
} |
667 |
// The intersection of ranges is more complicated
|
668 |
// First do trivial INTERSECTS rejection of the cases
|
669 |
// where one of the endpoints is inside the rectangle.
|
670 |
if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) ||
|
671 |
(x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) |
672 |
{ |
673 |
return RECT_INTERSECTS;
|
674 |
} |
675 |
// Otherwise, subdivide and look for one of the cases above.
|
676 |
// double precision only has 52 bits of mantissa
|
677 |
if (level > 52) { |
678 |
return rectCrossingsForLine(crossings,
|
679 |
rxmin, rymin, rxmax, rymax, |
680 |
x0, y0, x1, y1); |
681 |
} |
682 |
double xmid = (xc0 + xc1) / 2; |
683 |
double ymid = (yc0 + yc1) / 2; |
684 |
xc0 = (x0 + xc0) / 2;
|
685 |
yc0 = (y0 + yc0) / 2;
|
686 |
xc1 = (xc1 + x1) / 2;
|
687 |
yc1 = (yc1 + y1) / 2;
|
688 |
double xc0m = (xc0 + xmid) / 2; |
689 |
double yc0m = (yc0 + ymid) / 2; |
690 |
double xmc1 = (xmid + xc1) / 2; |
691 |
double ymc1 = (ymid + yc1) / 2; |
692 |
xmid = (xc0m + xmc1) / 2;
|
693 |
ymid = (yc0m + ymc1) / 2;
|
694 |
if (Double.isNaN(xmid) || Double.isNaN(ymid)) { |
695 |
// [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN
|
696 |
// [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN
|
697 |
// These values are also NaN if opposing infinities are added
|
698 |
return 0; |
699 |
} |
700 |
crossings = rectCrossingsForCubic(crossings, |
701 |
rxmin, rymin, rxmax, rymax, |
702 |
x0, y0, xc0, yc0, |
703 |
xc0m, yc0m, xmid, ymid, level+1);
|
704 |
if (crossings != RECT_INTERSECTS) {
|
705 |
crossings = rectCrossingsForCubic(crossings, |
706 |
rxmin, rymin, rxmax, rymax, |
707 |
xmid, ymid, xmc1, ymc1, |
708 |
xc1, yc1, x1, y1, level+1);
|
709 |
} |
710 |
return crossings;
|
711 |
} |
712 |
|
713 |
Curve(int direction) {
|
714 |
this.direction = direction;
|
715 |
} |
716 |
|
717 |
public final int getDirection() { |
718 |
return direction;
|
719 |
} |
720 |
|
721 |
public final Curve getWithDirection(int direction) { |
722 |
return (this.direction == direction ? this : getReversedCurve()); |
723 |
} |
724 |
|
725 |
public static double round(double v) { |
726 |
//return Math.rint(v*10)/10;
|
727 |
return v;
|
728 |
} |
729 |
|
730 |
public static int orderof(double x1, double x2) { |
731 |
if (x1 < x2) {
|
732 |
return -1; |
733 |
} |
734 |
if (x1 > x2) {
|
735 |
return 1; |
736 |
} |
737 |
return 0; |
738 |
} |
739 |
|
740 |
public static long signeddiffbits(double y1, double y2) { |
741 |
return (Double.doubleToLongBits(y1) - Double.doubleToLongBits(y2)); |
742 |
} |
743 |
public static long diffbits(double y1, double y2) { |
744 |
return Math.abs(Double.doubleToLongBits(y1) - |
745 |
Double.doubleToLongBits(y2));
|
746 |
} |
747 |
public static double prev(double v) { |
748 |
return Double.longBitsToDouble(Double.doubleToLongBits(v)-1); |
749 |
} |
750 |
public static double next(double v) { |
751 |
return Double.longBitsToDouble(Double.doubleToLongBits(v)+1); |
752 |
} |
753 |
|
754 |
public String toString() { |
755 |
return ("Curve["+ |
756 |
getOrder()+", "+
|
757 |
("("+round(getX0())+", "+round(getY0())+"), ")+ |
758 |
controlPointString()+ |
759 |
("("+round(getX1())+", "+round(getY1())+"), ")+ |
760 |
(direction == INCREASING ? "D" : "U")+ |
761 |
"]");
|
762 |
} |
763 |
|
764 |
public String controlPointString() { |
765 |
return ""; |
766 |
} |
767 |
|
768 |
public abstract int getOrder(); |
769 |
|
770 |
public abstract double getXTop(); |
771 |
public abstract double getYTop(); |
772 |
public abstract double getXBot(); |
773 |
public abstract double getYBot(); |
774 |
|
775 |
public abstract double getXMin(); |
776 |
public abstract double getXMax(); |
777 |
|
778 |
public abstract double getX0(); |
779 |
public abstract double getY0(); |
780 |
public abstract double getX1(); |
781 |
public abstract double getY1(); |
782 |
|
783 |
public abstract double XforY(double y); |
784 |
public abstract double TforY(double y); |
785 |
public abstract double XforT(double t); |
786 |
public abstract double YforT(double t); |
787 |
public abstract double dXforT(double t, int deriv); |
788 |
public abstract double dYforT(double t, int deriv); |
789 |
|
790 |
public abstract double nextVertical(double t0, double t1); |
791 |
|
792 |
public int crossingsFor(double x, double y) { |
793 |
if (y >= getYTop() && y < getYBot()) {
|
794 |
if (x < getXMax() && (x < getXMin() || x < XforY(y))) {
|
795 |
return 1; |
796 |
} |
797 |
} |
798 |
return 0; |
799 |
} |
800 |
|
801 |
public boolean accumulateCrossings(Crossings c) { |
802 |
double xhi = c.getXHi();
|
803 |
if (getXMin() >= xhi) {
|
804 |
return false; |
805 |
} |
806 |
double xlo = c.getXLo();
|
807 |
double ylo = c.getYLo();
|
808 |
double yhi = c.getYHi();
|
809 |
double y0 = getYTop();
|
810 |
double y1 = getYBot();
|
811 |
double tstart, ystart, tend, yend;
|
812 |
if (y0 < ylo) {
|
813 |
if (y1 <= ylo) {
|
814 |
return false; |
815 |
} |
816 |
ystart = ylo; |
817 |
tstart = TforY(ylo); |
818 |
} else {
|
819 |
if (y0 >= yhi) {
|
820 |
return false; |
821 |
} |
822 |
ystart = y0; |
823 |
tstart = 0;
|
824 |
} |
825 |
if (y1 > yhi) {
|
826 |
yend = yhi; |
827 |
tend = TforY(yhi); |
828 |
} else {
|
829 |
yend = y1; |
830 |
tend = 1;
|
831 |
} |
832 |
boolean hitLo = false; |
833 |
boolean hitHi = false; |
834 |
while (true) { |
835 |
double x = XforT(tstart);
|
836 |
if (x < xhi) {
|
837 |
if (hitHi || x > xlo) {
|
838 |
return true; |
839 |
} |
840 |
hitLo = true;
|
841 |
} else {
|
842 |
if (hitLo) {
|
843 |
return true; |
844 |
} |
845 |
hitHi = true;
|
846 |
} |
847 |
if (tstart >= tend) {
|
848 |
break;
|
849 |
} |
850 |
tstart = nextVertical(tstart, tend); |
851 |
} |
852 |
if (hitLo) {
|
853 |
c.record(ystart, yend, direction); |
854 |
} |
855 |
return false; |
856 |
} |
857 |
|
858 |
public abstract void enlarge(Rectangle2D r); |
859 |
|
860 |
public Curve getSubCurve(double ystart, double yend) { |
861 |
return getSubCurve(ystart, yend, direction);
|
862 |
} |
863 |
|
864 |
public abstract Curve getReversedCurve(); |
865 |
public abstract Curve getSubCurve(double ystart, double yend, int dir); |
866 |
|
867 |
public int compareTo(Curve that, double yrange[]) { |
868 |
/*
|
869 |
System.out.println(this+".compareTo("+that+")");
|
870 |
System.out.println("target range = "+yrange[0]+"=>"+yrange[1]);
|
871 |
*/
|
872 |
double y0 = yrange[0]; |
873 |
double y1 = yrange[1]; |
874 |
y1 = Math.min(Math.min(y1, this.getYBot()), that.getYBot()); |
875 |
if (y1 <= yrange[0]) { |
876 |
System.err.println("this == "+this); |
877 |
System.err.println("that == "+that); |
878 |
System.out.println("target range = "+yrange[0]+"=>"+yrange[1]); |
879 |
throw new InternalError("backstepping from "+yrange[0]+" to "+y1); |
880 |
} |
881 |
yrange[1] = y1;
|
882 |
if (this.getXMax() <= that.getXMin()) { |
883 |
if (this.getXMin() == that.getXMax()) { |
884 |
return 0; |
885 |
} |
886 |
return -1; |
887 |
} |
888 |
if (this.getXMin() >= that.getXMax()) { |
889 |
return 1; |
890 |
} |
891 |
// Parameter s for thi(s) curve and t for tha(t) curve
|
892 |
// [st]0 = parameters for top of current section of interest
|
893 |
// [st]1 = parameters for bottom of valid range
|
894 |
// [st]h = parameters for hypothesis point
|
895 |
// [d][xy]s = valuations of thi(s) curve at sh
|
896 |
// [d][xy]t = valuations of tha(t) curve at th
|
897 |
double s0 = this.TforY(y0); |
898 |
double ys0 = this.YforT(s0); |
899 |
if (ys0 < y0) {
|
900 |
s0 = refineTforY(s0, ys0, y0); |
901 |
ys0 = this.YforT(s0);
|
902 |
} |
903 |
double s1 = this.TforY(y1); |
904 |
if (this.YforT(s1) < y0) { |
905 |
s1 = refineTforY(s1, this.YforT(s1), y0);
|
906 |
//System.out.println("s1 problem!");
|
907 |
} |
908 |
double t0 = that.TforY(y0);
|
909 |
double yt0 = that.YforT(t0);
|
910 |
if (yt0 < y0) {
|
911 |
t0 = that.refineTforY(t0, yt0, y0); |
912 |
yt0 = that.YforT(t0); |
913 |
} |
914 |
double t1 = that.TforY(y1);
|
915 |
if (that.YforT(t1) < y0) {
|
916 |
t1 = that.refineTforY(t1, that.YforT(t1), y0); |
917 |
//System.out.println("t1 problem!");
|
918 |
} |
919 |
double xs0 = this.XforT(s0); |
920 |
double xt0 = that.XforT(t0);
|
921 |
double scale = Math.max(Math.abs(y0), Math.abs(y1)); |
922 |
double ymin = Math.max(scale * 1E-14, 1E-300); |
923 |
if (fairlyClose(xs0, xt0)) {
|
924 |
double bump = ymin;
|
925 |
double maxbump = Math.min(ymin * 1E13, (y1 - y0) * .1); |
926 |
double y = y0 + bump;
|
927 |
while (y <= y1) {
|
928 |
if (fairlyClose(this.XforY(y), that.XforY(y))) { |
929 |
if ((bump *= 2) > maxbump) { |
930 |
bump = maxbump; |
931 |
} |
932 |
} else {
|
933 |
y -= bump; |
934 |
while (true) { |
935 |
bump /= 2;
|
936 |
double newy = y + bump;
|
937 |
if (newy <= y) {
|
938 |
break;
|
939 |
} |
940 |
if (fairlyClose(this.XforY(newy), that.XforY(newy))) { |
941 |
y = newy; |
942 |
} |
943 |
} |
944 |
break;
|
945 |
} |
946 |
y += bump; |
947 |
} |
948 |
if (y > y0) {
|
949 |
if (y < y1) {
|
950 |
yrange[1] = y;
|
951 |
} |
952 |
return 0; |
953 |
} |
954 |
} |
955 |
//double ymin = y1 * 1E-14;
|
956 |
if (ymin <= 0) { |
957 |
System.out.println("ymin = "+ymin); |
958 |
} |
959 |
/*
|
960 |
System.out.println("s range = "+s0+" to "+s1);
|
961 |
System.out.println("t range = "+t0+" to "+t1);
|
962 |
*/
|
963 |
while (s0 < s1 && t0 < t1) {
|
964 |
double sh = this.nextVertical(s0, s1); |
965 |
double xsh = this.XforT(sh); |
966 |
double ysh = this.YforT(sh); |
967 |
double th = that.nextVertical(t0, t1);
|
968 |
double xth = that.XforT(th);
|
969 |
double yth = that.YforT(th);
|
970 |
/*
|
971 |
System.out.println("sh = "+sh);
|
972 |
System.out.println("th = "+th);
|
973 |
*/
|
974 |
try {
|
975 |
if (findIntersect(that, yrange, ymin, 0, 0, |
976 |
s0, xs0, ys0, sh, xsh, ysh, |
977 |
t0, xt0, yt0, th, xth, yth)) { |
978 |
break;
|
979 |
} |
980 |
} catch (Throwable t) { |
981 |
System.err.println("Error: "+t); |
982 |
System.err.println("y range was "+yrange[0]+"=>"+yrange[1]); |
983 |
System.err.println("s y range is "+ys0+"=>"+ysh); |
984 |
System.err.println("t y range is "+yt0+"=>"+yth); |
985 |
System.err.println("ymin is "+ymin); |
986 |
return 0; |
987 |
} |
988 |
if (ysh < yth) {
|
989 |
if (ysh > yrange[0]) { |
990 |
if (ysh < yrange[1]) { |
991 |
yrange[1] = ysh;
|
992 |
} |
993 |
break;
|
994 |
} |
995 |
s0 = sh; |
996 |
xs0 = xsh; |
997 |
ys0 = ysh; |
998 |
} else {
|
999 |
if (yth > yrange[0]) { |
1000 |
if (yth < yrange[1]) { |
1001 |
yrange[1] = yth;
|
1002 |
} |
1003 |
break;
|
1004 |
} |
1005 |
t0 = th; |
1006 |
xt0 = xth; |
1007 |
yt0 = yth; |
1008 |
} |
1009 |
} |
1010 |
double ymid = (yrange[0] + yrange[1]) / 2; |
1011 |
/*
|
1012 |
System.out.println("final this["+s0+", "+sh+", "+s1+"]");
|
1013 |
System.out.println("final y["+ys0+", "+ysh+"]");
|
1014 |
System.out.println("final that["+t0+", "+th+", "+t1+"]");
|
1015 |
System.out.println("final y["+yt0+", "+yth+"]");
|
1016 |
System.out.println("final order = "+orderof(this.XforY(ymid),
|
1017 |
that.XforY(ymid)));
|
1018 |
System.out.println("final range = "+yrange[0]+"=>"+yrange[1]);
|
1019 |
*/
|
1020 |
/*
|
1021 |
System.out.println("final sx = "+this.XforY(ymid));
|
1022 |
System.out.println("final tx = "+that.XforY(ymid));
|
1023 |
System.out.println("final order = "+orderof(this.XforY(ymid),
|
1024 |
that.XforY(ymid)));
|
1025 |
*/
|
1026 |
return orderof(this.XforY(ymid), that.XforY(ymid)); |
1027 |
} |
1028 |
|
1029 |
public static final double TMIN = 1E-3; |
1030 |
|
1031 |
public boolean findIntersect(Curve that, double yrange[], double ymin, |
1032 |
int slevel, int tlevel, |
1033 |
double s0, double xs0, double ys0, |
1034 |
double s1, double xs1, double ys1, |
1035 |
double t0, double xt0, double yt0, |
1036 |
double t1, double xt1, double yt1) |
1037 |
{ |
1038 |
/*
|
1039 |
String pad = " ";
|
1040 |
pad = pad+pad+pad+pad+pad;
|
1041 |
pad = pad+pad;
|
1042 |
System.out.println("----------------------------------------------");
|
1043 |
System.out.println(pad.substring(0, slevel)+ys0);
|
1044 |
System.out.println(pad.substring(0, slevel)+ys1);
|
1045 |
System.out.println(pad.substring(0, slevel)+(s1-s0));
|
1046 |
System.out.println("-------");
|
1047 |
System.out.println(pad.substring(0, tlevel)+yt0);
|
1048 |
System.out.println(pad.substring(0, tlevel)+yt1);
|
1049 |
System.out.println(pad.substring(0, tlevel)+(t1-t0));
|
1050 |
*/
|
1051 |
if (ys0 > yt1 || yt0 > ys1) {
|
1052 |
return false; |
1053 |
} |
1054 |
if (Math.min(xs0, xs1) > Math.max(xt0, xt1) || |
1055 |
Math.max(xs0, xs1) < Math.min(xt0, xt1)) |
1056 |
{ |
1057 |
return false; |
1058 |
} |
1059 |
// Bounding boxes intersect - back off the larger of
|
1060 |
// the two subcurves by half until they stop intersecting
|
1061 |
// (or until they get small enough to switch to a more
|
1062 |
// intensive algorithm).
|
1063 |
if (s1 - s0 > TMIN) {
|
1064 |
double s = (s0 + s1) / 2; |
1065 |
double xs = this.XforT(s); |
1066 |
double ys = this.YforT(s); |
1067 |
if (s == s0 || s == s1) {
|
1068 |
System.out.println("s0 = "+s0); |
1069 |
System.out.println("s1 = "+s1); |
1070 |
throw new InternalError("no s progress!"); |
1071 |
} |
1072 |
if (t1 - t0 > TMIN) {
|
1073 |
double t = (t0 + t1) / 2; |
1074 |
double xt = that.XforT(t);
|
1075 |
double yt = that.YforT(t);
|
1076 |
if (t == t0 || t == t1) {
|
1077 |
System.out.println("t0 = "+t0); |
1078 |
System.out.println("t1 = "+t1); |
1079 |
throw new InternalError("no t progress!"); |
1080 |
} |
1081 |
if (ys >= yt0 && yt >= ys0) {
|
1082 |
if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, |
1083 |
s0, xs0, ys0, s, xs, ys, |
1084 |
t0, xt0, yt0, t, xt, yt)) { |
1085 |
return true; |
1086 |
} |
1087 |
} |
1088 |
if (ys >= yt) {
|
1089 |
if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, |
1090 |
s0, xs0, ys0, s, xs, ys, |
1091 |
t, xt, yt, t1, xt1, yt1)) { |
1092 |
return true; |
1093 |
} |
1094 |
} |
1095 |
if (yt >= ys) {
|
1096 |
if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, |
1097 |
s, xs, ys, s1, xs1, ys1, |
1098 |
t0, xt0, yt0, t, xt, yt)) { |
1099 |
return true; |
1100 |
} |
1101 |
} |
1102 |
if (ys1 >= yt && yt1 >= ys) {
|
1103 |
if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, |
1104 |
s, xs, ys, s1, xs1, ys1, |
1105 |
t, xt, yt, t1, xt1, yt1)) { |
1106 |
return true; |
1107 |
} |
1108 |
} |
1109 |
} else {
|
1110 |
if (ys >= yt0) {
|
1111 |
if (findIntersect(that, yrange, ymin, slevel+1, tlevel, |
1112 |
s0, xs0, ys0, s, xs, ys, |
1113 |
t0, xt0, yt0, t1, xt1, yt1)) { |
1114 |
return true; |
1115 |
} |
1116 |
} |
1117 |
if (yt1 >= ys) {
|
1118 |
if (findIntersect(that, yrange, ymin, slevel+1, tlevel, |
1119 |
s, xs, ys, s1, xs1, ys1, |
1120 |
t0, xt0, yt0, t1, xt1, yt1)) { |
1121 |
return true; |
1122 |
} |
1123 |
} |
1124 |
} |
1125 |
} else if (t1 - t0 > TMIN) { |
1126 |
double t = (t0 + t1) / 2; |
1127 |
double xt = that.XforT(t);
|
1128 |
double yt = that.YforT(t);
|
1129 |
if (t == t0 || t == t1) {
|
1130 |
System.out.println("t0 = "+t0); |
1131 |
System.out.println("t1 = "+t1); |
1132 |
throw new InternalError("no t progress!"); |
1133 |
} |
1134 |
if (yt >= ys0) {
|
1135 |
if (findIntersect(that, yrange, ymin, slevel, tlevel+1, |
1136 |
s0, xs0, ys0, s1, xs1, ys1, |
1137 |
t0, xt0, yt0, t, xt, yt)) { |
1138 |
return true; |
1139 |
} |
1140 |
} |
1141 |
if (ys1 >= yt) {
|
1142 |
if (findIntersect(that, yrange, ymin, slevel, tlevel+1, |
1143 |
s0, xs0, ys0, s1, xs1, ys1, |
1144 |
t, xt, yt, t1, xt1, yt1)) { |
1145 |
return true; |
1146 |
} |
1147 |
} |
1148 |
} else {
|
1149 |
// No more subdivisions
|
1150 |
double xlk = xs1 - xs0;
|
1151 |
double ylk = ys1 - ys0;
|
1152 |
double xnm = xt1 - xt0;
|
1153 |
double ynm = yt1 - yt0;
|
1154 |
double xmk = xt0 - xs0;
|
1155 |
double ymk = yt0 - ys0;
|
1156 |
double det = xnm * ylk - ynm * xlk;
|
1157 |
if (det != 0) { |
1158 |
double detinv = 1 / det; |
1159 |
double s = (xnm * ymk - ynm * xmk) * detinv;
|
1160 |
double t = (xlk * ymk - ylk * xmk) * detinv;
|
1161 |
if (s >= 0 && s <= 1 && t >= 0 && t <= 1) { |
1162 |
s = s0 + s * (s1 - s0); |
1163 |
t = t0 + t * (t1 - t0); |
1164 |
if (s < 0 || s > 1 || t < 0 || t > 1) { |
1165 |
System.out.println("Uh oh!"); |
1166 |
} |
1167 |
double y = (this.YforT(s) + that.YforT(t)) / 2; |
1168 |
if (y <= yrange[1] && y > yrange[0]) { |
1169 |
yrange[1] = y;
|
1170 |
return true; |
1171 |
} |
1172 |
} |
1173 |
} |
1174 |
//System.out.println("Testing lines!");
|
1175 |
} |
1176 |
return false; |
1177 |
} |
1178 |
|
1179 |
public double refineTforY(double t0, double yt0, double y0) { |
1180 |
double t1 = 1; |
1181 |
while (true) { |
1182 |
double th = (t0 + t1) / 2; |
1183 |
if (th == t0 || th == t1) {
|
1184 |
return t1;
|
1185 |
} |
1186 |
double y = YforT(th);
|
1187 |
if (y < y0) {
|
1188 |
t0 = th; |
1189 |
yt0 = y; |
1190 |
} else if (y > y0) { |
1191 |
t1 = th; |
1192 |
} else {
|
1193 |
return t1;
|
1194 |
} |
1195 |
} |
1196 |
} |
1197 |
|
1198 |
public boolean fairlyClose(double v1, double v2) { |
1199 |
return (Math.abs(v1 - v2) < |
1200 |
Math.max(Math.abs(v1), Math.abs(v2)) * 1E-10); |
1201 |
} |
1202 |
|
1203 |
public abstract int getSegment(double coords[]); |
1204 |
} |