]> git.zerfleddert.de Git - micropolis/blame - src/tk/tktrig.c
Import Micropolis from http://www.donhopkins.com/home/micropolis/
[micropolis] / src / tk / tktrig.c
CommitLineData
6a5fa4e0
MG
1/*
2 * tkTrig.c --
3 *
4 * This file contains a collection of trigonometry utility
5 * routines that are used by Tk and in particular by the
6 * canvas code. It also has miscellaneous geometry functions
7 * used by canvases.
8 *
9 * Copyright 1992 Regents of the University of California.
10 * Permission to use, copy, modify, and distribute this
11 * software and its documentation for any purpose and without
12 * fee is hereby granted, provided that the above copyright
13 * notice appear in all copies. The University of California
14 * makes no representations about the suitability of this
15 * software for any purpose. It is provided "as is" without
16 * express or implied warranty.
17 */
18
19#ifndef lint
20static char rcsid[] = "$Header: /user6/ouster/wish/RCS/tkTrig.c,v 1.8 92/08/24 09:24:14 ouster Exp $ SPRITE (Berkeley)";
21#endif
22
23#include <stdio.h>
24#include <math.h>
25#include "tkconfig.h"
26#include "tkcanvas.h"
27
28#undef MIN
29#define MIN(a,b) (((a) < (b)) ? (a) : (b))
30#undef MAX
31#define MAX(a,b) (((a) > (b)) ? (a) : (b))
32#define PI 3.14159265358979323846
33\f
34/*
35 *--------------------------------------------------------------
36 *
37 * TkLineToPoint --
38 *
39 * Compute the distance from a point to a finite line segment.
40 *
41 * Results:
42 * The return value is the distance from the line segment
43 * whose end-points are *end1Ptr and *end2Ptr to the point
44 * given by *pointPtr.
45 *
46 * Side effects:
47 * None.
48 *
49 *--------------------------------------------------------------
50 */
51
52double
53TkLineToPoint(end1Ptr, end2Ptr, pointPtr)
54 double end1Ptr[2]; /* Coordinates of first end-point of line. */
55 double end2Ptr[2]; /* Coordinates of second end-point of line. */
56 double pointPtr[2]; /* Points to coords for point. */
57{
58 double x, y;
59
60 /*
61 * Compute the point on the line that is closest to the
62 * point. This must be done separately for vertical edges,
63 * horizontal edges, and other edges.
64 */
65
66 if (end1Ptr[0] == end2Ptr[0]) {
67
68 /*
69 * Vertical edge.
70 */
71
72 x = end1Ptr[0];
73 if (end1Ptr[1] >= end2Ptr[1]) {
74 y = MIN(end1Ptr[1], pointPtr[1]);
75 y = MAX(y, end2Ptr[1]);
76 } else {
77 y = MIN(end2Ptr[1], pointPtr[1]);
78 y = MAX(y, end1Ptr[1]);
79 }
80 } else if (end1Ptr[1] == end2Ptr[1]) {
81
82 /*
83 * Horizontal edge.
84 */
85
86 y = end1Ptr[1];
87 if (end1Ptr[0] >= end2Ptr[0]) {
88 x = MIN(end1Ptr[0], pointPtr[0]);
89 x = MAX(x, end2Ptr[0]);
90 } else {
91 x = MIN(end2Ptr[0], pointPtr[0]);
92 x = MAX(x, end1Ptr[0]);
93 }
94 } else {
95 double m1, b1, m2, b2;
96
97 /*
98 * The edge is neither horizontal nor vertical. Convert the
99 * edge to a line equation of the form y = m1*x + b1. Then
100 * compute a line perpendicular to this edge but passing
101 * through the point, also in the form y = m2*x + b2.
102 */
103
104 m1 = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]);
105 b1 = end1Ptr[1] - m1*end1Ptr[0];
106 m2 = -1.0/m1;
107 b2 = pointPtr[1] - m2*pointPtr[0];
108 x = (b2 - b1)/(m1 - m2);
109 y = m1*x + b1;
110 if (end1Ptr[0] > end2Ptr[0]) {
111 if (x > end1Ptr[0]) {
112 x = end1Ptr[0];
113 y = end1Ptr[1];
114 } else if (x < end2Ptr[0]) {
115 x = end2Ptr[0];
116 y = end2Ptr[1];
117 }
118 } else {
119 if (x > end2Ptr[0]) {
120 x = end2Ptr[0];
121 y = end2Ptr[1];
122 } else if (x < end1Ptr[0]) {
123 x = end1Ptr[0];
124 y = end1Ptr[1];
125 }
126 }
127 }
128
129 /*
130 * Compute the distance to the closest point.
131 */
132
133 return hypot(pointPtr[0] - x, pointPtr[1] - y);
134}
135\f
136/*
137 *--------------------------------------------------------------
138 *
139 * TkLineToArea --
140 *
141 * Determine whether a line lies entirely inside, entirely
142 * outside, or overlapping a given rectangular area.
143 *
144 * Results:
145 * -1 is returned if the line given by end1Ptr and end2Ptr
146 * is entirely outside the rectangle given by rectPtr. 0 is
147 * returned if the polygon overlaps the rectangle, and 1 is
148 * returned if the polygon is entirely inside the rectangle.
149 *
150 * Side effects:
151 * None.
152 *
153 *--------------------------------------------------------------
154 */
155
156int
157TkLineToArea(end1Ptr, end2Ptr, rectPtr)
158 double end1Ptr[2]; /* X and y coordinates for one endpoint
159 * of line. */
160 double end2Ptr[2]; /* X and y coordinates for other endpoint
161 * of line. */
162 double rectPtr[4]; /* Points to coords for rectangle, in the
163 * order x1, y1, x2, y2. X1 must be no
164 * larger than x2, and y1 no larger than y2. */
165{
166 int inside1, inside2;
167
168 /*
169 * First check the two points individually to see whether they
170 * are inside the rectangle or not.
171 */
172
173 inside1 = (end1Ptr[0] >= rectPtr[0]) && (end1Ptr[0] <= rectPtr[2])
174 && (end1Ptr[1] >= rectPtr[1]) && (end1Ptr[1] <= rectPtr[3]);
175 inside2 = (end2Ptr[0] >= rectPtr[0]) && (end2Ptr[0] <= rectPtr[2])
176 && (end2Ptr[1] >= rectPtr[1]) && (end2Ptr[1] <= rectPtr[3]);
177 if (inside1 != inside2) {
178 return 0;
179 }
180 if (inside1 & inside2) {
181 return 1;
182 }
183
184 /*
185 * Both points are outside the rectangle, but still need to check
186 * for intersections between the line and the rectangle. Horizontal
187 * and vertical lines are particularly easy, so handle them
188 * separately.
189 */
190
191 if (end1Ptr[0] == end2Ptr[0]) {
192 /*
193 * Vertical line.
194 */
195
196 if (((end1Ptr[1] >= rectPtr[1]) ^ (end2Ptr[1] >= rectPtr[1]))
197 && (end1Ptr[0] >= rectPtr[0])
198 && (end1Ptr[0] <= rectPtr[2])) {
199 return 0;
200 }
201 } else if (end1Ptr[1] == end2Ptr[1]) {
202 /*
203 * Horizontal line.
204 */
205
206 if (((end1Ptr[0] >= rectPtr[0]) ^ (end2Ptr[0] >= rectPtr[0]))
207 && (end1Ptr[1] >= rectPtr[1])
208 && (end1Ptr[1] <= rectPtr[3])) {
209 return 0;
210 }
211 } else {
212 double m, x, y, low, high;
213
214 /*
215 * Diagonal line. Compute slope of line and use
216 * for intersection checks against each of the
217 * sides of the rectangle: left, right, bottom, top.
218 */
219
220 m = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]);
221 if (end1Ptr[0] < end2Ptr[0]) {
222 low = end1Ptr[0]; high = end2Ptr[0];
223 } else {
224 low = end2Ptr[0]; high = end1Ptr[0];
225 }
226
227 /*
228 * Left edge.
229 */
230
231 y = end1Ptr[1] + (rectPtr[0] - end1Ptr[0])*m;
232 if ((rectPtr[0] >= low) && (rectPtr[0] <= high)
233 && (y >= rectPtr[1]) && (y <= rectPtr[3])) {
234 return 0;
235 }
236
237 /*
238 * Right edge.
239 */
240
241 y += (rectPtr[2] - rectPtr[0])*m;
242 if ((y >= rectPtr[1]) && (y <= rectPtr[3])
243 && (rectPtr[2] >= low) && (rectPtr[2] <= high)) {
244 return 0;
245 }
246
247 /*
248 * Bottom edge.
249 */
250
251 if (end1Ptr[1] < end2Ptr[1]) {
252 low = end1Ptr[1]; high = end2Ptr[1];
253 } else {
254 low = end2Ptr[1]; high = end1Ptr[1];
255 }
256 x = end1Ptr[0] + (rectPtr[1] - end1Ptr[1])/m;
257 if ((x >= rectPtr[0]) && (x <= rectPtr[2])
258 && (rectPtr[1] >= low) && (rectPtr[1] <= high)) {
259 return 0;
260 }
261
262 /*
263 * Top edge.
264 */
265
266 x += (rectPtr[3] - rectPtr[1])/m;
267 if ((x >= rectPtr[0]) && (x <= rectPtr[2])
268 && (rectPtr[3] >= low) && (rectPtr[3] <= high)) {
269 return 0;
270 }
271 }
272 return -1;
273}
274\f
275/*
276 *--------------------------------------------------------------
277 *
278 * TkPolygonToPoint --
279 *
280 * Compute the distance from a point to a polygon.
281 *
282 * Results:
283 * The return value is 0.0 if the point referred to by
284 * pointPtr is within the polygon referred to by polyPtr
285 * and numPoints. Otherwise the return value is the
286 * distance of the point from the polygon.
287 *
288 * Side effects:
289 * None.
290 *
291 *--------------------------------------------------------------
292 */
293
294double
295TkPolygonToPoint(polyPtr, numPoints, pointPtr)
296 double *polyPtr; /* Points to an array coordinates for
297 * closed polygon: x0, y0, x1, y1, ...
298 * The polygon may be self-intersecting. */
299 int numPoints; /* Total number of points at *polyPtr. */
300 double *pointPtr; /* Points to coords for point. */
301{
302 double bestDist; /* Closest distance between point and
303 * any edge in polygon. */
304 int intersections; /* Number of edges in the polygon that
305 * intersect a ray extending vertically
306 * upwards from the point to infinity. */
307 int count;
308 register double *pPtr;
309
310 /*
311 * Iterate through all of the edges in the polygon, updating
312 * bestDist and intersections.
313 *
314 * TRICKY POINT: when computing intersections, include left
315 * x-coordinate of line within its range, but not y-coordinate.
316 * Otherwise if the point lies exactly below a vertex we'll
317 * count it as two intersections.
318 */
319
320 bestDist = 1.0e40;
321 intersections = 0;
322
323 for (count = numPoints, pPtr = polyPtr; count > 1; count--, pPtr += 2) {
324 double x, y, dist;
325
326 /*
327 * Compute the point on the current edge closest to the point
328 * and update the intersection count. This must be done
329 * separately for vertical edges, horizontal edges, and
330 * other edges.
331 */
332
333 if (pPtr[2] == pPtr[0]) {
334
335 /*
336 * Vertical edge.
337 */
338
339 x = pPtr[0];
340 if (pPtr[1] >= pPtr[3]) {
341 y = MIN(pPtr[1], pointPtr[1]);
342 y = MAX(y, pPtr[3]);
343 } else {
344 y = MIN(pPtr[3], pointPtr[1]);
345 y = MAX(y, pPtr[1]);
346 }
347 } else if (pPtr[3] == pPtr[1]) {
348
349 /*
350 * Horizontal edge.
351 */
352
353 y = pPtr[1];
354 if (pPtr[0] >= pPtr[2]) {
355 x = MIN(pPtr[0], pointPtr[0]);
356 x = MAX(x, pPtr[2]);
357 if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[0])
358 && (pointPtr[0] >= pPtr[2])) {
359 intersections++;
360 }
361 } else {
362 x = MIN(pPtr[2], pointPtr[0]);
363 x = MAX(x, pPtr[0]);
364 if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[2])
365 && (pointPtr[0] >= pPtr[0])) {
366 intersections++;
367 }
368 }
369 } else {
370 double m1, b1, m2, b2;
371 int lower; /* Non-zero means point below line. */
372
373 /*
374 * The edge is neither horizontal nor vertical. Convert the
375 * edge to a line equation of the form y = m1*x + b1. Then
376 * compute a line perpendicular to this edge but passing
377 * through the point, also in the form y = m2*x + b2.
378 */
379
380 m1 = (pPtr[3] - pPtr[1])/(pPtr[2] - pPtr[0]);
381 b1 = pPtr[1] - m1*pPtr[0];
382 m2 = -1.0/m1;
383 b2 = pointPtr[1] - m2*pointPtr[0];
384 x = (b2 - b1)/(m1 - m2);
385 y = m1*x + b1;
386 if (pPtr[0] > pPtr[2]) {
387 if (x > pPtr[0]) {
388 x = pPtr[0];
389 y = pPtr[1];
390 } else if (x < pPtr[2]) {
391 x = pPtr[2];
392 y = pPtr[3];
393 }
394 } else {
395 if (x > pPtr[2]) {
396 x = pPtr[2];
397 y = pPtr[3];
398 } else if (x < pPtr[0]) {
399 x = pPtr[0];
400 y = pPtr[1];
401 }
402 }
403 lower = (m1*pointPtr[0] + b1) > pointPtr[1];
404 if (lower && (pointPtr[0] >= MIN(pPtr[0], pPtr[2]))
405 && (pointPtr[0] < MAX(pPtr[0], pPtr[2]))) {
406 intersections++;
407 }
408 }
409
410 /*
411 * Compute the distance to the closest point, and see if that
412 * is the best distance seen so far.
413 */
414
415 dist = hypot(pointPtr[0] - x, pointPtr[1] - y);
416 if (dist < bestDist) {
417 bestDist = dist;
418 }
419 }
420
421 /*
422 * We've processed all of the points. If the number of intersections
423 * is odd, the point is inside the polygon.
424 */
425
426 if (intersections & 0x1) {
427 return 0.0;
428 }
429 return bestDist;
430}
431\f
432/*
433 *--------------------------------------------------------------
434 *
435 * TkPolygonToArea --
436 *
437 * Determine whether a polygon lies entirely inside, entirely
438 * outside, or overlapping a given rectangular area.
439 *
440 * Results:
441 * -1 is returned if the polygon given by polyPtr and numPoints
442 * is entirely outside the rectangle given by rectPtr. 0 is
443 * returned if the polygon overlaps the rectangle, and 1 is
444 * returned if the polygon is entirely inside the rectangle.
445 *
446 * Side effects:
447 * None.
448 *
449 *--------------------------------------------------------------
450 */
451
452int
453TkPolygonToArea(polyPtr, numPoints, rectPtr)
454 double *polyPtr; /* Points to an array coordinates for
455 * closed polygon: x0, y0, x1, y1, ...
456 * The polygon may be self-intersecting. */
457 int numPoints; /* Total number of points at *polyPtr. */
458 register double *rectPtr; /* Points to coords for rectangle, in the
459 * order x1, y1, x2, y2. X1 and y1 must
460 * be lower-left corner. */
461{
462 int state; /* State of all edges seen so far (-1 means
463 * outside, 1 means inside, won't ever be
464 * 0). */
465 int count;
466 register double *pPtr;
467
468 /*
469 * Iterate over all of the edges of the polygon and test them
470 * against the rectangle. Can quit as soon as the state becomes
471 * "intersecting".
472 */
473
474 state = TkLineToArea(polyPtr, polyPtr+2, rectPtr);
475 if (state == 0) {
476 return 0;
477 }
478 for (pPtr = polyPtr+2, count = numPoints-1; count >= 2;
479 pPtr += 2, count--) {
480 if (TkLineToArea(pPtr, pPtr+2, rectPtr) != state) {
481 return 0;
482 }
483 }
484
485 /*
486 * If all of the edges were inside the rectangle we're done.
487 * If all of the edges were outside, then the rectangle could
488 * still intersect the polygon (if it's entirely enclosed).
489 * Call TkPolygonToPoint to figure this out.
490 */
491
492 if (state == 1) {
493 return 1;
494 }
495 if (TkPolygonToPoint(polyPtr, numPoints, rectPtr) == 0.0) {
496 return 0;
497 }
498 return -1;
499}
500\f
501/*
502 *--------------------------------------------------------------
503 *
504 * TkOvalToPoint --
505 *
506 * Computes the distance from a given point to a given
507 * oval, in canvas units.
508 *
509 * Results:
510 * The return value is 0 if the point given by *pointPtr is
511 * inside the oval. If the point isn't inside the
512 * oval then the return value is approximately the distance
513 * from the point to the oval. If the oval is filled, then
514 * anywhere in the interior is considered "inside"; if
515 * the oval isn't filled, then "inside" means only the area
516 * occupied by the outline.
517 *
518 * Side effects:
519 * None.
520 *
521 *--------------------------------------------------------------
522 */
523
524 /* ARGSUSED */
525double
526TkOvalToPoint(ovalPtr, width, filled, pointPtr)
527 double ovalPtr[4]; /* Pointer to array of four coordinates
528 * (x1, y1, x2, y2) defining oval's bounding
529 * box. */
530 double width; /* Width of outline for oval. */
531 int filled; /* Non-zero means oval should be treated as
532 * filled; zero means only consider outline. */
533 double pointPtr[2]; /* Coordinates of point. */
534{
535 double xDelta, yDelta, scaledDistance, distToOutline, distToCenter;
536
537 /*
538 * Compute the distance between the center of the oval and the
539 * point in question, using a coordinate system where the oval
540 * has been transformed to a circle with unit radius.
541 */
542
543 xDelta = (pointPtr[0] - (ovalPtr[0] + ovalPtr[2])/2.0);
544 yDelta = (pointPtr[1] - (ovalPtr[1] + ovalPtr[3])/2.0);
545 distToCenter = hypot(xDelta, yDelta);
546 scaledDistance = hypot(xDelta / ((ovalPtr[2] + width - ovalPtr[0])/2.0),
547 yDelta / ((ovalPtr[3] + width - ovalPtr[1])/2.0));
548
549
550 /*
551 * If the scaled distance is greater than 1 then it means no
552 * hit. Compute the distance from the point to the edge of
553 * the circle, then scale this distance back to the original
554 * coordinate system.
555 *
556 * Note: this distance isn't completely accurate. It's only
557 * an approximation, and it can overestimate the correct
558 * distance when the oval is eccentric.
559 */
560
561 if (scaledDistance > 1.0) {
562 return (distToCenter/scaledDistance) * (scaledDistance - 1.0);
563 }
564
565 /*
566 * Scaled distance less than 1 means the point is inside the
567 * outer edge of the oval. If this is a filled oval, then we
568 * have a hit. Otherwise, do the same computation as above
569 * (scale back to original coordinate system), but also check
570 * to see if the point is within the width of the outline.
571 */
572
573 if (filled) {
574 return 0.0;
575 }
576 distToOutline = (distToCenter/scaledDistance) * (1.0 - scaledDistance)
577 - width;
578 if (distToOutline < 0.0) {
579 return 0.0;
580 }
581 return distToOutline;
582}
583\f
584/*
585 *--------------------------------------------------------------
586 *
587 * TkOvalToArea --
588 *
589 * Determine whether an oval lies entirely inside, entirely
590 * outside, or overlapping a given rectangular area.
591 *
592 * Results:
593 * -1 is returned if the oval described by ovalPtr is entirely
594 * outside the rectangle given by rectPtr. 0 is returned if the
595 * oval overlaps the rectangle, and 1 is returned if the oval
596 * is entirely inside the rectangle.
597 *
598 * Side effects:
599 * None.
600 *
601 *--------------------------------------------------------------
602 */
603
604int
605TkOvalToArea(ovalPtr, rectPtr)
606 register double *ovalPtr; /* Points to coordinates definining the
607 * bounding rectangle for the oval: x1, y1,
608 * x2, y2. X1 must be less than x2 and y1
609 * less than y2. */
610 register double *rectPtr; /* Points to coords for rectangle, in the
611 * order x1, y1, x2, y2. X1 and y1 must
612 * be lower-left corner. */
613{
614 double centerX, centerY, radX, radY, deltaX, deltaY;
615
616 /*
617 * First, see if oval is entirely inside rectangle or entirely
618 * outside rectangle.
619 */
620
621 if ((rectPtr[0] <= ovalPtr[0]) && (rectPtr[2] >= ovalPtr[2])
622 && (rectPtr[1] <= ovalPtr[1]) && (rectPtr[3] >= ovalPtr[3])) {
623 return 1;
624 }
625 if ((rectPtr[2] < ovalPtr[0]) || (rectPtr[0] > ovalPtr[2])
626 || (rectPtr[3] < ovalPtr[1]) || (rectPtr[1] > ovalPtr[3])) {
627 return -1;
628 }
629
630 /*
631 * Next, go through the rectangle side by side. For each side
632 * of the rectangle, find the point on the side that is closest
633 * to the oval's center, and see if that point is inside the
634 * oval. If at least one such point is inside the oval, then
635 * the rectangle intersects the oval.
636 */
637
638 centerX = (ovalPtr[0] + ovalPtr[2])/2;
639 centerY = (ovalPtr[1] + ovalPtr[3])/2;
640 radX = (ovalPtr[2] - ovalPtr[0])/2;
641 radY = (ovalPtr[3] - ovalPtr[1])/2;
642
643 deltaY = rectPtr[1] - centerY;
644 if (deltaY < 0.0) {
645 deltaY = centerY - rectPtr[3];
646 if (deltaY < 0.0) {
647 deltaY = 0;
648 }
649 }
650 deltaY /= radY;
651 deltaY *= deltaY;
652
653 /*
654 * Left side:
655 */
656
657 deltaX = (rectPtr[0] - centerX)/radX;
658 deltaX *= deltaX;
659 if ((deltaX + deltaY) <= 1.0) {
660 return 0;
661 }
662
663 /*
664 * Right side:
665 */
666
667 deltaX = (rectPtr[2] - centerX)/radX;
668 deltaX *= deltaX;
669 if ((deltaX + deltaY) <= 1.0) {
670 return 0;
671 }
672
673 deltaX = rectPtr[0] - centerX;
674 if (deltaX < 0.0) {
675 deltaX = centerX - rectPtr[2];
676 if (deltaX < 0.0) {
677 deltaX = 0;
678 }
679 }
680 deltaX /= radX;
681 deltaX *= deltaX;
682
683 /*
684 * Bottom side:
685 */
686
687 deltaY = (rectPtr[1] - centerY)/radY;
688 deltaY *= deltaY;
689 if ((deltaX + deltaY) < 1.0) {
690 return 0;
691 }
692
693 /*
694 * Top side:
695 */
696
697 deltaY = (rectPtr[3] - centerY)/radY;
698 deltaY *= deltaY;
699 if ((deltaX + deltaY) < 1.0) {
700 return 0;
701 }
702
703 return -1;
704}
705\f
706/*
707 *--------------------------------------------------------------
708 *
709 * TkIncludePoint --
710 *
711 * Given a point and a generic canvas item header, expand
712 * the item's bounding box if needed to include the point.
713 *
714 * Results:
715 * None.
716 *
717 * Side effects:
718 * The boudn.
719 *
720 *--------------------------------------------------------------
721 */
722
723 /* ARGSUSED */
724void
725TkIncludePoint(canvasPtr, itemPtr, pointPtr)
726 Tk_Canvas *canvasPtr; /* Canvas containing item. */
727 register Tk_Item *itemPtr; /* Item whose bounding box is
728 * being calculated. */
729 double *pointPtr; /* Address of two doubles giving
730 * x and y coordinates of point. */
731{
732 int tmp;
733
734 tmp = pointPtr[0] + 0.5;
735 if (tmp < itemPtr->x1) {
736 itemPtr->x1 = tmp;
737 }
738 if (tmp > itemPtr->x2) {
739 itemPtr->x2 = tmp;
740 }
741 tmp = pointPtr[1] + 0.5;
742 if (tmp < itemPtr->y1) {
743 itemPtr->y1 = tmp;
744 }
745 if (tmp > itemPtr->y2) {
746 itemPtr->y2 = tmp;
747 }
748}
749\f
750/*
751 *--------------------------------------------------------------
752 *
753 * TkBezierScreenPoints --
754 *
755 * Given four control points, create a larger set of XPoints
756 * for a Bezier spline based on the points.
757 *
758 * Results:
759 * The array at *xPointPtr gets filled in with numSteps XPoints
760 * corresponding to the Bezier spline defined by the four
761 * control points. Note: no output point is generated for the
762 * first input point, but an output point *is* generated for
763 * the last input point.
764 *
765 * Side effects:
766 * None.
767 *
768 *--------------------------------------------------------------
769 */
770
771void
772TkBezierScreenPoints(canvasPtr, control, numSteps, xPointPtr)
773 Tk_Canvas *canvasPtr; /* Canvas in which curve is to be
774 * drawn. */
775 double control[]; /* Array of coordinates for four
776 * control points: x0, y0, x1, y1,
777 * ... x3 y3. */
778 int numSteps; /* Number of curve points to
779 * generate. */
780 register XPoint *xPointPtr; /* Where to put new points. */
781{
782 int i;
783 double u, u2, u3, t, t2, t3;
784
785 for (i = 1; i <= numSteps; i++, xPointPtr++) {
786 t = ((double) i)/((double) numSteps);
787 t2 = t*t;
788 t3 = t2*t;
789 u = 1.0 - t;
790 u2 = u*u;
791 u3 = u2*u;
792 xPointPtr->x = SCREEN_X(canvasPtr, (control[0]*u3
793 + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3));
794 xPointPtr->y = SCREEN_Y(canvasPtr, (control[1]*u3
795 + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3));
796 }
797}
798\f
799/*
800 *--------------------------------------------------------------
801 *
802 * TkBezierPoints --
803 *
804 * Given four control points, create a larger set of points
805 * for a Bezier spline based on the points.
806 *
807 * Results:
808 * The array at *coordPtr gets filled in with 2*numSteps
809 * coordinates, which correspond to the Bezier spline defined
810 * by the four control points. Note: no output point is
811 * generated for the first input point, but an output point
812 * *is* generated for the last input point.
813 *
814 * Side effects:
815 * None.
816 *
817 *--------------------------------------------------------------
818 */
819
820void
821TkBezierPoints(control, numSteps, coordPtr)
822 double control[]; /* Array of coordinates for four
823 * control points: x0, y0, x1, y1,
824 * ... x3 y3. */
825 int numSteps; /* Number of curve points to
826 * generate. */
827 register double *coordPtr; /* Where to put new points. */
828{
829 int i;
830 double u, u2, u3, t, t2, t3;
831
832 for (i = 1; i <= numSteps; i++, coordPtr += 2) {
833 t = ((double) i)/((double) numSteps);
834 t2 = t*t;
835 t3 = t2*t;
836 u = 1.0 - t;
837 u2 = u*u;
838 u3 = u2*u;
839 coordPtr[0] = control[0]*u3
840 + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3;
841 coordPtr[1] = control[1]*u3
842 + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3;
843 }
844}
845\f
846/*
847 *--------------------------------------------------------------
848 *
849 * TkMakeBezierCurve --
850 *
851 * Given a set of points, create a new set of points that
852 * fit Bezier splines to the line segments connecting the
853 * original points. Produces output points in either of two
854 * forms.
855 *
856 * Results:
857 * Either or both of the xPoints or dblPoints arrays are filled
858 * in. The return value is the number of points placed in the
859 * arrays. Note: if the first and last points are the same, then
860 * a closed curve is generated.
861 *
862 * Side effects:
863 * None.
864 *
865 *--------------------------------------------------------------
866 */
867
868int
869TkMakeBezierCurve(canvasPtr, pointPtr, numPoints, numSteps, xPoints, dblPoints)
870 Tk_Canvas *canvasPtr; /* Canvas in which curve is to be
871 * drawn. */
872 double *pointPtr; /* Array of input coordinates: x0,
873 * y0, x1, y1, etc.. */
874 int numPoints; /* Number of points at pointPtr. */
875 int numSteps; /* Number of steps to use for each
876 * spline segments (determines
877 * smoothness of curve). */
878 XPoint xPoints[]; /* Array of XPoints to fill in (e.g.
879 * for display. NULL means don't
880 * fill in any XPoints. */
881 double dblPoints[]; /* Array of points to fill in as
882 * doubles, in the form x0, y0,
883 * x1, y1, .... NULL means don't
884 * fill in anything in this form.
885 * Caller must make sure that this
886 * array has enough space. */
887{
888 int closed, outputPoints, i;
889 int numCoords = numPoints*2;
890 double control[8];
891
892 /*
893 * If the curve is a closed one then generate a special spline
894 * that spans the last points and the first ones. Otherwise
895 * just put the first point into the output.
896 */
897
898 outputPoints = 0;
899 if ((pointPtr[0] == pointPtr[numCoords-2])
900 && (pointPtr[1] == pointPtr[numCoords-1])) {
901 closed = 1;
902 control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0];
903 control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1];
904 control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0];
905 control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1];
906 control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2];
907 control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3];
908 control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
909 control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
910 if (xPoints != NULL) {
911 xPoints->x = SCREEN_X(canvasPtr, control[0]);
912 xPoints->y = SCREEN_Y(canvasPtr, control[1]);
913 TkBezierScreenPoints(canvasPtr, control, numSteps, xPoints+1);
914 xPoints += numSteps+1;
915 }
916 if (dblPoints != NULL) {
917 dblPoints[0] = control[0];
918 dblPoints[1] = control[1];
919 TkBezierPoints(control, numSteps, dblPoints+2);
920 dblPoints += 2*(numSteps+1);
921 }
922 outputPoints += numSteps+1;
923 } else {
924 closed = 0;
925 if (xPoints != NULL) {
926 xPoints->x = SCREEN_X(canvasPtr, pointPtr[0]);
927 xPoints->y = SCREEN_Y(canvasPtr, pointPtr[1]);
928 xPoints += 1;
929 }
930 if (dblPoints != NULL) {
931 dblPoints[0] = pointPtr[0];
932 dblPoints[1] = pointPtr[1];
933 dblPoints += 2;
934 }
935 outputPoints += 1;
936 }
937
938 for (i = 2; i < numPoints; i++, pointPtr += 2) {
939 /*
940 * Set up the first two control points. This is done
941 * differently for the first spline of an open curve
942 * than for other cases.
943 */
944
945 if ((i == 2) && !closed) {
946 control[0] = pointPtr[0];
947 control[1] = pointPtr[1];
948 control[2] = 0.333*pointPtr[0] + 0.667*pointPtr[2];
949 control[3] = 0.333*pointPtr[1] + 0.667*pointPtr[3];
950 } else {
951 control[0] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
952 control[1] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
953 control[2] = 0.167*pointPtr[0] + 0.833*pointPtr[2];
954 control[3] = 0.167*pointPtr[1] + 0.833*pointPtr[3];
955 }
956
957 /*
958 * Set up the last two control points. This is done
959 * differently for the last spline of an open curve
960 * than for other cases.
961 */
962
963 if ((i == (numPoints-1)) && !closed) {
964 control[4] = .667*pointPtr[2] + .333*pointPtr[4];
965 control[5] = .667*pointPtr[3] + .333*pointPtr[5];
966 control[6] = pointPtr[4];
967 control[7] = pointPtr[5];
968 } else {
969 control[4] = .833*pointPtr[2] + .167*pointPtr[4];
970 control[5] = .833*pointPtr[3] + .167*pointPtr[5];
971 control[6] = 0.5*pointPtr[2] + 0.5*pointPtr[4];
972 control[7] = 0.5*pointPtr[3] + 0.5*pointPtr[5];
973 }
974
975 /*
976 * If the first two points coincide, or if the last
977 * two points coincide, then generate a single
978 * straight-line segment by outputting the last control
979 * point.
980 */
981
982 if (((pointPtr[0] == pointPtr[2]) && (pointPtr[1] == pointPtr[3]))
983 || ((pointPtr[2] == pointPtr[4])
984 && (pointPtr[3] == pointPtr[5]))) {
985 if (xPoints != NULL) {
986 xPoints[0].x = SCREEN_X(canvasPtr, control[6]);
987 xPoints[0].y = SCREEN_Y(canvasPtr, control[7]);
988 xPoints++;
989 }
990 if (dblPoints != NULL) {
991 dblPoints[0] = control[6];
992 dblPoints[1] = control[7];
993 dblPoints += 2;
994 }
995 outputPoints += 1;
996 continue;
997 }
998
999 /*
1000 * Generate a Bezier spline using the control points.
1001 */
1002
1003
1004 if (xPoints != NULL) {
1005 TkBezierScreenPoints(canvasPtr, control, numSteps, xPoints);
1006 xPoints += numSteps;
1007 }
1008 if (dblPoints != NULL) {
1009 TkBezierPoints(control, numSteps, dblPoints);
1010 dblPoints += 2*numSteps;
1011 }
1012 outputPoints += numSteps;
1013 }
1014 return outputPoints;
1015}
1016\f
1017/*
1018 *--------------------------------------------------------------
1019 *
1020 * TkGetMiterPoints --
1021 *
1022 * Given three points forming an angle, compute the
1023 * coordinates of the inside and outside points of
1024 * the mitered corner formed by a line of a given
1025 * width at that angle.
1026 *
1027 * Results:
1028 * If the angle formed by the three points is less than
1029 * 11 degrees then 0 is returned and m1 and m2 aren't
1030 * modified. Otherwise 1 is returned and the points at
1031 * m1 and m2 are filled in with the positions of the points
1032 * of the mitered corner.
1033 *
1034 * Side effects:
1035 * None.
1036 *
1037 *--------------------------------------------------------------
1038 */
1039
1040int
1041TkGetMiterPoints(p1, p2, p3, width, m1, m2)
1042 double p1[]; /* Points to x- and y-coordinates of point
1043 * before vertex. */
1044 double p2[]; /* Points to x- and y-coordinates of vertex
1045 * for mitered joint. */
1046 double p3[]; /* Points to x- and y-coordinates of point
1047 * after vertex. */
1048 double width; /* Width of line. */
1049 double m1[]; /* Points to place to put "left" vertex
1050 * point (see as you face from p1 to p2). */
1051 double m2[]; /* Points to place to put "right" vertex
1052 * point. */
1053{
1054 double theta1; /* Angle of segment p2-p1. */
1055 double theta2; /* Angle of segment p2-p3. */
1056 double theta; /* Angle between line segments (angle
1057 * of joint). */
1058 double theta3; /* Angle that bisects theta1 and
1059 * theta2 and points to m1. */
1060 double dist; /* Distance of miter points from p2. */
1061 double deltaX, deltaY; /* X and y offsets cooresponding to
1062 * dist (fudge factors for bounding
1063 * box). */
1064 static float elevenDegrees = (11.0*2.0*PI)/360.0;
1065
1066 if (p2[1] == p1[1]) {
1067 theta1 = (p2[0] < p1[0]) ? 0 : PI;
1068 } else if (p2[0] == p1[0]) {
1069 theta1 = (p2[1] < p1[1]) ? PI/2.0 : -PI/2.0;
1070 } else {
1071 theta1 = atan2(p1[1] - p2[1], p1[0] - p2[0]);
1072 }
1073 if (p3[1] == p2[1]) {
1074 theta2 = (p3[0] > p2[0]) ? 0 : PI;
1075 } else if (p3[0] == p2[0]) {
1076 theta2 = (p3[1] > p2[1]) ? PI/2.0 : -PI/2.0;
1077 } else {
1078 theta2 = atan2(p3[1] - p2[1], p3[0] - p2[0]);
1079 }
1080 theta = theta1 - theta2;
1081 if (theta > PI) {
1082 theta -= 2*PI;
1083 } else if (theta < -PI) {
1084 theta += 2*PI;
1085 }
1086 if ((theta < elevenDegrees) && (theta > -elevenDegrees)) {
1087 return 0;
1088 }
1089 dist = 0.5*width/sin(0.5*theta);
1090 if (dist < 0.0) {
1091 dist = -dist;
1092 }
1093
1094 /*
1095 * Compute theta3 (make sure that it points to the left when
1096 * looking from p1 to p2).
1097 */
1098
1099 theta3 = (theta1 + theta2)/2.0;
1100 if (sin(theta3 - (theta1 + PI)) < 0.0) {
1101 theta3 += PI;
1102 }
1103 deltaX = dist*cos(theta3);
1104 m1[0] = p2[0] + deltaX;
1105 m2[0] = p2[0] - deltaX;
1106 deltaY = dist*sin(theta3);
1107 m1[1] = p2[1] + deltaY;
1108 m2[1] = p2[1] - deltaY;
1109 return 1;
1110}
1111\f
1112/*
1113 *--------------------------------------------------------------
1114 *
1115 * TkGetButtPoints --
1116 *
1117 * Given two points forming a line segment, compute the
1118 * coordinates of two endpoints of a rectangle formed by
1119 * bloating the line segment until it is width units wide.
1120 *
1121 * Results:
1122 * There is no return value. M1 and m2 are filled in to
1123 * correspond to m1 and m2 in the diagram below:
1124 *
1125 * ----------------* m1
1126 * |
1127 * p1 *---------------* p2
1128 * |
1129 * ----------------* m2
1130 *
1131 * M1 and m2 will be W units apart, with p2 centered between
1132 * them and m1-m2 perpendicular to p1-p2. However, if
1133 * "project" is true then m1 and m2 will be as follows:
1134 *
1135 * -------------------* m1
1136 * p2 |
1137 * p1 *---------------* |
1138 * |
1139 * -------------------* m2
1140 *
1141 * In this case p2 will be width/2 units from the segment m1-m2.
1142 *
1143 * Side effects:
1144 * None.
1145 *
1146 *--------------------------------------------------------------
1147 */
1148
1149void
1150TkGetButtPoints(p1, p2, width, project, m1, m2)
1151 double p1[]; /* Points to x- and y-coordinates of point
1152 * before vertex. */
1153 double p2[]; /* Points to x- and y-coordinates of vertex
1154 * for mitered joint. */
1155 double width; /* Width of line. */
1156 int project; /* Non-zero means project p2 by an additional
1157 * width/2 before computing m1 and m2. */
1158 double m1[]; /* Points to place to put "left" result
1159 * point, as you face from p1 to p2. */
1160 double m2[]; /* Points to place to put "right" result
1161 * point. */
1162{
1163 double length; /* Length of p1-p2 segment. */
1164 double deltaX, deltaY; /* Increments in coords. */
1165
1166 width *= 0.5;
1167 length = hypot(p2[0] - p1[0], p2[1] - p1[1]);
1168 if (length == 0.0) {
1169 m1[0] = m2[0] = p2[0];
1170 m1[1] = m2[1] = p2[1];
1171 } else {
1172 deltaX = -width * (p2[1] - p1[1]) / length;
1173 deltaY = width * (p2[0] - p1[0]) / length;
1174 m1[0] = p2[0] + deltaX;
1175 m2[0] = p2[0] - deltaX;
1176 m1[1] = p2[1] + deltaY;
1177 m2[1] = p2[1] - deltaY;
1178 if (project) {
1179 m1[0] += deltaY;
1180 m2[0] += deltaY;
1181 m1[1] -= deltaX;
1182 m2[1] -= deltaX;
1183 }
1184 }
1185}
Impressum, Datenschutz