![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tktrig.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Micropolis - Activity] / micropolis / src / tk|
Return to tktrig.c CVS log | Up to [Micropolis - Activity] / micropolis / src / tk |
1.1 root 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
20: static 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:
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:
52: double
53: TkLineToPoint(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:
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:
156: int
157: TkLineToArea(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:
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:
294: double
295: TkPolygonToPoint(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:
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:
452: int
453: TkPolygonToArea(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:
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 */
525: double
526: TkOvalToPoint(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:
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:
604: int
605: TkOvalToArea(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:
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 */
724: void
725: TkIncludePoint(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:
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:
771: void
772: TkBezierScreenPoints(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:
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:
820: void
821: TkBezierPoints(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:
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:
868: int
869: TkMakeBezierCurve(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:
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:
1040: int
1041: TkGetMiterPoints(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:
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:
1149: void
1150: TkGetButtPoints(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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.