Source code: com/port80/graph/dot/impl/DotSpline.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.awt.*;
8 import com.port80.util.msg;
9
10 /** Spline class represent a spline of n-Bezier segments with 3n+1
11 * points.
12 *
13 * //TODO: Should use int[] x,y instead IntPoint.
14 */
15 public class DotSpline {
16
17 ////////////////////////////////////////////////////////////////////////
18
19 private static final String NAME = "DotSpline";
20 private static final boolean VERBOSE = true;
21 private static final boolean DEBUG = false;
22
23 ////////////////////////////////////////////////////////////////////////
24
25 DotPoint[] pts;
26 int size;
27 DotPoint sp; /** Tail end point (ie. tail arrow head).*/
28 DotPoint ep; /** Head end point (ie. head arrow head).*/
29 boolean isReversed; /** false=sp is tail arrow head, else sp is head arrow head.*/
30
31 /** Temp. variables for splitAt(). */
32 private double[][] xs = new double[4][4];
33 private double[][] ys = new double[4][4];
34
35 ////////////////////////////////////////////////////////////////////////
36
37 public DotSpline() {
38 this(0);
39 }
40 public DotSpline(int n) {
41 this(n, 0);
42 }
43 public DotSpline(int n, int size) {
44 this.size = size;
45 pts = new DotPoint[n];
46 for (int i = 0; i < n; ++i)
47 pts[i] = new DotPoint();
48 }
49 public DotSpline(DotSpline s) {
50 this(s, 0, s.size);
51 }
52 /** Create a new spline from the given segment.
53 * @param start Start index.
54 * @param end End index. If start>end, new spline is reverse of
55 * the given segment from [start-1..end].
56 */
57 public DotSpline(DotSpline s, int start, int end) {
58 if (s.sp != null)
59 sp = new DotPoint(s.sp);
60 if (s.ep != null)
61 ep = new DotPoint(s.ep);
62 size = end - start;
63 if (size >= 0) {
64 pts = new DotPoint[size];
65 for (int i = 0; i < size; ++i)
66 pts[i] = new DotPoint(s.pts[start + i]);
67 } else {
68 size = -size;
69 pts = new DotPoint[size];
70 for (int i = 0; i < size; ++i)
71 pts[i] = new DotPoint(s.pts[start - i - 1]);
72 }
73 }
74 /** Splice point array and keep only points from offset to offset+newsize.*/
75 public void resize(int newsize, int offset) {
76 if (offset != 0)
77 for (int i = 0; i < newsize; ++i)
78 pts[i] = pts[offset++];
79 size = newsize;
80 }
81 public void reset() {
82 size = 0;
83 sp = null;
84 ep = null;
85 }
86 /** Determine the bounding rectange for the curve from Control
87 * 'c' to this control. The bounding polygon is given by the
88 * 7 control points when dividing the curve into half
89 * (t=0.5): P0(R0)->R1->R2->R3(S0)->S1->S2->S3(P3).
90 *
91 * The bounding rectangle is the bounds of the bounding
92 * polygon.
93 *
94 * @return the bounding rectangle.
95 * @see <a href="www.cee.hw.ac.uk/~ian/hyper00/curvesurf/morebez.html#drawing">tutorial</a>
96 */
97 public Rectangle getBounds() {
98 DotPoint p0, p1, p2, p3;
99 double r1x, r1y, r2x, r2y, r3x, r3y, s1x, s1y, s2x, s2y;
100 double minx = Double.MAX_VALUE;
101 double miny = Double.MAX_VALUE;
102 double maxx = Double.MIN_VALUE;
103 double maxy = Double.MIN_VALUE;
104 if (sp != null) {
105 if (sp.x < minx)
106 minx = sp.x;
107 if (sp.y < miny)
108 miny = sp.y;
109 if (sp.x > maxx)
110 maxx = sp.x;
111 if (sp.y > maxy)
112 maxy = sp.y;
113 }
114 if (ep != null) {
115 if (ep.x < minx)
116 minx = ep.x;
117 if (ep.y < miny)
118 miny = ep.y;
119 if (ep.x > maxx)
120 maxx = ep.x;
121 if (ep.y > maxy)
122 maxy = ep.y;
123 }
124 for (int i = 0; i < size - 3; i += 3) {
125 p0 = pts[i];
126 p1 = pts[i + 1];
127 p2 = pts[i + 2];
128 p3 = pts[i + 3];
129 r1x = (p0.x + p1.x) / 2.0;
130 r1y = (p0.y + p1.y) / 2.0;
131 r2x = r1x / 2.0 + (p1.x + p2.x) / 4.0;
132 r2y = r1y / 2.0 + (p1.y + p2.y) / 4.0;
133 s2x = (p2.x + p3.x) / 2.0;
134 s2y = (p2.y + p3.y) / 2.0;
135 s1x = (p1.x + p2.x) / 4.0 + s2x / 2.0;
136 s1y = (p1.y + p2.y) / 4.0 + s2y / 2.0;
137 r3x = (r2x + s1x) / 2.0;
138 r3y = (r2y + s1y) / 2.0;
139 //
140 if (r3x < minx)
141 minx = r3x;
142 if (r3y < miny)
143 miny = r3y;
144 if (r3x > maxx)
145 maxx = r3x;
146 if (r3y > maxy)
147 maxy = r3y;
148 //
149 if (p0.x < minx)
150 minx = p0.x;
151 if (p0.y < miny)
152 miny = p0.y;
153 if (p0.x > maxx)
154 maxx = p0.x;
155 if (p0.y > maxy)
156 maxy = p0.y;
157 //
158 if (p3.x < minx)
159 minx = p3.x;
160 if (p3.y < miny)
161 miny = p3.y;
162 if (p3.x > maxx)
163 maxx = p3.x;
164 if (p3.y > maxy)
165 maxy = p3.y;
166 //
167 if (r1x < minx)
168 minx = r1x;
169 if (r1y < miny)
170 miny = r1y;
171 if (r1x > maxx)
172 maxx = r1x;
173 if (r1y > maxy)
174 maxy = r1y;
175 //
176 if (r2x < minx)
177 minx = r2x;
178 if (r2y < miny)
179 miny = r2y;
180 if (r2x > maxx)
181 maxx = r2x;
182 if (r2y > maxy)
183 maxy = r2y;
184 //
185 if (s1x < minx)
186 minx = s1x;
187 if (s1y < miny)
188 miny = s1y;
189 if (s1x > maxx)
190 maxx = s1x;
191 if (s1y > maxy)
192 maxy = s1y;
193 //
194 if (s2x < minx)
195 minx = s2x;
196 if (s2y < miny)
197 miny = s2y;
198 if (s2x > maxx)
199 maxx = s2x;
200 if (s2y > maxy)
201 maxy = s2y;
202 //
203 }
204 return new Rectangle((int) minx, (int) miny, (int) (maxx - minx + 0.5), (int) (maxy - miny + 0.5));
205 }
206
207 public String toString() {
208 StringBuffer ret = new StringBuffer();
209 if (sp != null)
210 ret.append((isReversed ? "S " : "s ") + sp.toString() + " ");
211 if (ep != null)
212 ret.append((isReversed ? "E " : "e ") + ep.toString() + " ");
213 for (int i = 0; i < size; ++i) {
214 ret.append(pts[i].toString() + " ");
215 }
216 return ret.toString();
217 }
218 public String toGeneralPath() {
219 StringBuffer ret = new StringBuffer("<path>\n<curve>\n");
220 ret.append(" " + pts[0] + "\n");
221 for (int i = 1; i <= size - 3; i += 3) {
222 ret.append(" " + pts[i] + " " + pts[i + 1] + " " + pts[i + 2] + "\n");
223 }
224 ret.append("</curve>\n</path>\n");
225 return ret.toString();
226 }
227
228 ////////////////////////////////////////////////////////////////////////
229
230 /** Add a new Spline segment of n points to the spline. The first
231 * point of the segment should be same as the last point of the
232 * current spline.
233 */
234 public void add(DotPolyline segment) {
235 DotPoint p;
236 int si = 0;
237 if (segment.size % 3 != 1) {
238 msg.err(NAME + ".add(): incorrect segment size: " + segment.size);
239 }
240 if (size > 0) {
241 ++si;
242 p = pts[size - 1];
243 double x = segment.pts[0].x;
244 double y = segment.pts[0].y;
245 if (Math.abs(x - p.x) > 2 || Math.abs(y - p.y) > 2)
246 msg.err(
247 NAME
248 + ".add(): new start!=old end"
249 + ": start="
250 + x
251 + ","
252 + y
253 + ", end="
254 + p.toString());
255 }
256 int n = size + segment.size - si - pts.length;
257 if (n > 0)
258 grow(n + pts.length / 4 + 3);
259 for (; si < segment.size; ++si) {
260 pts[size].x = segment.pts[si].x;
261 pts[size].y = segment.pts[si].y;
262 ++size;
263 }
264 if (size % 3 != 1) {
265 msg.err(NAME + ".add(): incorrect spline size: " + size);
266 }
267 }
268 public void add(DotPoint p) {
269 if (size >= pts.length)
270 grow(pts.length / 4 + 3);
271 pts[size].x = p.x;
272 pts[size].y = p.y;
273 ++size;
274 }
275 public void add(double x, double y) {
276 if (size >= pts.length)
277 grow(pts.length / 4 + 3);
278 pts[size].x = x;
279 pts[size].y = y;
280 ++size;
281 }
282 public void grow(int n) {
283 int max = pts.length + n;
284 DotPoint[] a = new DotPoint[max];
285 System.arraycopy(pts, 0, a, 0, pts.length);
286 for (int i = pts.length; i < max; ++i)
287 a[i] = new DotPoint();
288 pts = a;
289 }
290 public int size() {
291 return size;
292 }
293 public DotPoint get(int n) {
294 return pts[n];
295 }
296 public boolean isReversed() {
297 return isReversed;
298 }
299
300 ////////////////////////////////////////////////////////////////////////
301
302 /**
303 * @return intersection point of spline and horizontal line at y.
304 * @enter assumed spline is monotonic along y ie. y is
305 * continuously increasing or decreasing.
306 */
307 public IntPoint bezierAtY(int y) {
308 IntPoint ret = new IntPoint();
309
310 if (y < pts[0].y) {
311 ret.x = (int) pts[0].x;
312 msg.warn(NAME + ".bezierAtY(): y above start: y=" + y + ", starty=" + pts[0].y);
313 } else if (y > pts[size - 1].y) {
314 ret.x = (int) pts[size - 1].x;
315 msg.warn(NAME + ".bezierAtY(): y below end: y=" + y + ", end=" + pts[size - 1].y);
316 } else {
317 int index, j;
318 for (index = 0; index < size; index += 3) {
319 for (j = 0; j < 3; j++) {
320 // y in between [i+j].y and [i+j+1].y regardless
321 // of which of them is larger.
322 if ((pts[index + j].y <= y) && (y <= pts[index + j + 1].y))
323 break;
324 if ((pts[index + j].y >= y) && (y >= pts[index + j + 1].y))
325 break;
326 }
327 if (j < 3)
328 break;
329 }
330 if (index >= size)
331 msg.err(NAME + ".bezierAtY(): index>=size");
332 /*
333 DotPoint[] c=new DotPoint[4];
334 for(i=0; i<4; ++i) c[i]=new DotPoint();
335 for(j=0; j<4; j++) {
336 c[j].x=pts[index+j].x;
337 c[j].y=pts[index+j].y;
338 // Make the spline be monotonic in Y, awful but it works for now.
339 if((j>0) && (c[j].y<c[j-1].y)) c[j].y=c[j-1].y;
340 }
341 */
342
343 // Binary search for the intersection.
344 double low = 0.0;
345 double high = 1.0;
346 double t;
347 DotPoint p = new DotPoint();
348 double d;
349 do {
350 t = (low + high) / 2.0;
351 splitAt(t, index, null, null, p);
352 d = p.y - y;
353 if (Math.abs(d) <= 1)
354 break;
355 if (d > 0)
356 high = t;
357 else
358 low = t;
359 } while (high - low > 1e-3);
360 ret.x = (int) p.x;
361 }
362 ret.y = y;
363 return ret;
364 }
365
366 /** Evaluate Bezier point on segment start at 'index' at parameter value 't'.*/
367 public void bezierAt(int index, double t, DotPoint ret) {
368 double x0 = pts[index].x;
369 double y0 = pts[index].y;
370 double x1 = pts[index + 1].x;
371 double y1 = pts[index + 1].y;
372 double x2 = pts[index + 2].x;
373 double y2 = pts[index + 2].y;
374 double x3 = pts[index + 3].x;
375 double y3 = pts[index + 3].y;
376 double u = (1.0 - t);
377 double w0, w1, w2, w3;
378 w0 = u * u;
379 w3 = t * t;
380 w1 = 3.0 * w0 * t;
381 w2 = 3.0 * w3 * u;
382 w0 *= u;
383 w3 *= t;
384 ret.x = w0 * x0 + w1 * x1 + w2 * x2 + w3 * x3;
385 ret.y = w0 * y0 + w1 * y1 + w2 * y2 + w3 * y3;
386 }
387
388 /** Binary search in 't' domain for intersection of the spline
389 * segment starting from 'index' with shape.
390 */
391 public boolean intersection(DotPoint ret, Shape shape, int index) {
392 //
393 double t, u, w0, w1, w2, w3, lastx, lasty;
394 double x0 = pts[index].x;
395 double y0 = pts[index].y;
396 double x1 = pts[index + 1].x;
397 double y1 = pts[index + 1].y;
398 double x2 = pts[index + 2].x;
399 double y2 = pts[index + 2].y;
400 double x3 = pts[index + 3].x;
401 double y3 = pts[index + 3].y;
402 double high = 1.0;
403 double low = 0.0;
404 boolean crossed = !shape.contains(x0, y0);
405 if (shape.contains(x3, y3) != crossed)
406 return false;
407 double x = x0;
408 double y = y0;
409 do {
410 lastx = x;
411 lasty = y;
412 t = (high + low) / 2.0;
413 // BezierAt(t)
414 u = (1.0 - t);
415 w0 = u * u;
416 w3 = t * t;
417 w1 = 3.0 * w0 * t;
418 w2 = 3.0 * w3 * u;
419 w0 *= u;
420 w3 *= t;
421 x = w0 * x0 + w1 * x1 + w2 * x2 + w3 * x3;
422 y = w0 * y0 + w1 * y1 + w2 * y2 + w3 * y3;
423 if (shape.contains(x, y) == crossed)
424 high = t;
425 else
426 low = t;
427 } while (Math.abs(x - lastx) > 0.25 || Math.abs(y - lasty) > 0.25);
428 ret.x = x;
429 ret.y = y;
430 return true;
431 }
432
433 /**
434 * Split the Bezier curve, started at given index, at a particular parameter value. Fill
435 * in control points for resulting sub-curves if 'left' and/or
436 * 'right' are not null.
437 *
438 * (From Glassner's Graphics Gems).
439 */
440 public void splitAt(double t, int index, DotSpline left, DotSpline right, DotPoint ret) {
441 // Copy control points.
442 for (int i = 0; i < 4; i++) {
443 xs[0][i] = pts[index + i].x;
444 ys[0][i] = pts[index + i].y;
445 }
446
447 // Triangle computation.
448 for (int i = 1; i <= 3; i++) {
449 for (int j = 0; j <= 3 - i; j++) {
450 xs[i][j] = (1.0 - t) * xs[i - 1][j] + t * xs[i - 1][j + 1];
451 ys[i][j] = (1.0 - t) * ys[i - 1][j] + t * ys[i - 1][j + 1];
452 }
453 }
454 if (ret != null) {
455 ret.x = xs[3][0];
456 ret.y = ys[3][0];
457 if (DEBUG)
458 msg.println(
459 NAME
460 + ".splitAt(): index="
461 + index
462 + ", t="
463 + t
464 + ", ret.x="
465 + ret.x
466 + ", ret.y="
467 + ret.y);
468 }
469 if (left != null) {
470 for (int i = 0; i <= 3; i++) {
471 left.pts[i].x = xs[i][0];
472 left.pts[i].y = ys[i][0];
473 }
474 if (DEBUG)
475 msg.println(
476 NAME
477 + ".splitAt(): t="
478 + t
479 + ", ret="
480 + ret.toString()
481 + ": left:"
482 + left.toString());
483 }
484 if (right != null) {
485 for (int i = 0; i <= 3; i++) {
486 right.pts[i].x = xs[3 - i][i];
487 right.pts[i].y = ys[3 - i][i];
488 }
489 if (DEBUG)
490 msg.println(
491 NAME
492 + ".splitAt(): t="
493 + t
494 + ", ret="
495 + ret.toString()
496 + ": right:"
497 + right.toString());
498 }
499 }
500
501 }