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 | 11 | jldominguez | /*
|
---|---|---|---|
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 | } |