1/* 2 * tkTrig.c -- 3 * 4 * This file contains a collection of trigonometry utility routines that 5 * are used by Tk and in particular by the canvas code. It also has 6 * miscellaneous geometry functions used by canvases. 7 * 8 * Copyright (c) 1992-1994 The Regents of the University of California. 9 * Copyright (c) 1994-1997 Sun Microsystems, Inc. 10 * 11 * See the file "license.terms" for information on usage and redistribution of 12 * this file, and for a DISCLAIMER OF ALL WARRANTIES. 13 * 14 * RCS: @(#) $Id$ 15 */ 16 17#include <stdio.h> 18#include "tkInt.h" 19#include "tkCanvas.h" 20 21#undef MIN 22#define MIN(a,b) (((a) < (b)) ? (a) : (b)) 23#undef MAX 24#define MAX(a,b) (((a) > (b)) ? (a) : (b)) 25#ifndef PI 26# define PI 3.14159265358979323846 27#endif /* PI */ 28 29/* 30 *-------------------------------------------------------------- 31 * 32 * TkLineToPoint -- 33 * 34 * Compute the distance from a point to a finite line segment. 35 * 36 * Results: 37 * The return value is the distance from the line segment whose 38 * end-points are *end1Ptr and *end2Ptr to the point given by *pointPtr. 39 * 40 * Side effects: 41 * None. 42 * 43 *-------------------------------------------------------------- 44 */ 45 46double 47TkLineToPoint( 48 double end1Ptr[2], /* Coordinates of first end-point of line. */ 49 double end2Ptr[2], /* Coordinates of second end-point of line. */ 50 double pointPtr[2]) /* Points to coords for point. */ 51{ 52 double x, y; 53 54 /* 55 * Compute the point on the line that is closest to the point. This must 56 * be done separately for vertical edges, horizontal edges, and other 57 * edges. 58 */ 59 60 if (end1Ptr[0] == end2Ptr[0]) { 61 62 /* 63 * Vertical edge. 64 */ 65 66 x = end1Ptr[0]; 67 if (end1Ptr[1] >= end2Ptr[1]) { 68 y = MIN(end1Ptr[1], pointPtr[1]); 69 y = MAX(y, end2Ptr[1]); 70 } else { 71 y = MIN(end2Ptr[1], pointPtr[1]); 72 y = MAX(y, end1Ptr[1]); 73 } 74 } else if (end1Ptr[1] == end2Ptr[1]) { 75 76 /* 77 * Horizontal edge. 78 */ 79 80 y = end1Ptr[1]; 81 if (end1Ptr[0] >= end2Ptr[0]) { 82 x = MIN(end1Ptr[0], pointPtr[0]); 83 x = MAX(x, end2Ptr[0]); 84 } else { 85 x = MIN(end2Ptr[0], pointPtr[0]); 86 x = MAX(x, end1Ptr[0]); 87 } 88 } else { 89 double m1, b1, m2, b2; 90 91 /* 92 * The edge is neither horizontal nor vertical. Convert the edge to a 93 * line equation of the form y = m1*x + b1. Then compute a line 94 * perpendicular to this edge but passing through the point, also in 95 * the form y = m2*x + b2. 96 */ 97 98 m1 = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]); 99 b1 = end1Ptr[1] - m1*end1Ptr[0]; 100 m2 = -1.0/m1; 101 b2 = pointPtr[1] - m2*pointPtr[0]; 102 x = (b2 - b1)/(m1 - m2); 103 y = m1*x + b1; 104 if (end1Ptr[0] > end2Ptr[0]) { 105 if (x > end1Ptr[0]) { 106 x = end1Ptr[0]; 107 y = end1Ptr[1]; 108 } else if (x < end2Ptr[0]) { 109 x = end2Ptr[0]; 110 y = end2Ptr[1]; 111 } 112 } else { 113 if (x > end2Ptr[0]) { 114 x = end2Ptr[0]; 115 y = end2Ptr[1]; 116 } else if (x < end1Ptr[0]) { 117 x = end1Ptr[0]; 118 y = end1Ptr[1]; 119 } 120 } 121 } 122 123 /* 124 * Compute the distance to the closest point. 125 */ 126 127 return hypot(pointPtr[0] - x, pointPtr[1] - y); 128} 129 130/* 131 *-------------------------------------------------------------- 132 * 133 * TkLineToArea -- 134 * 135 * Determine whether a line lies entirely inside, entirely outside, or 136 * overlapping a given rectangular area. 137 * 138 * Results: 139 * -1 is returned if the line given by end1Ptr and end2Ptr is entirely 140 * outside the rectangle given by rectPtr. 0 is returned if the polygon 141 * overlaps the rectangle, and 1 is returned if the polygon is entirely 142 * inside the rectangle. 143 * 144 * Side effects: 145 * None. 146 * 147 *-------------------------------------------------------------- 148 */ 149 150int 151TkLineToArea( 152 double end1Ptr[2], /* X and y coordinates for one endpoint of 153 * line. */ 154 double end2Ptr[2], /* X and y coordinates for other endpoint of 155 * line. */ 156 double rectPtr[4]) /* Points to coords for rectangle, in the 157 * order x1, y1, x2, y2. X1 must be no larger 158 * than x2, and y1 no larger than y2. */ 159{ 160 int inside1, inside2; 161 162 /* 163 * First check the two points individually to see whether they are inside 164 * the rectangle or not. 165 */ 166 167 inside1 = (end1Ptr[0] >= rectPtr[0]) && (end1Ptr[0] <= rectPtr[2]) 168 && (end1Ptr[1] >= rectPtr[1]) && (end1Ptr[1] <= rectPtr[3]); 169 inside2 = (end2Ptr[0] >= rectPtr[0]) && (end2Ptr[0] <= rectPtr[2]) 170 && (end2Ptr[1] >= rectPtr[1]) && (end2Ptr[1] <= rectPtr[3]); 171 if (inside1 != inside2) { 172 return 0; 173 } 174 if (inside1 & inside2) { 175 return 1; 176 } 177 178 /* 179 * Both points are outside the rectangle, but still need to check for 180 * intersections between the line and the rectangle. Horizontal and 181 * vertical lines are particularly easy, so handle them separately. 182 */ 183 184 if (end1Ptr[0] == end2Ptr[0]) { 185 /* 186 * Vertical line. 187 */ 188 189 if (((end1Ptr[1] >= rectPtr[1]) ^ (end2Ptr[1] >= rectPtr[1])) 190 && (end1Ptr[0] >= rectPtr[0]) 191 && (end1Ptr[0] <= rectPtr[2])) { 192 return 0; 193 } 194 } else if (end1Ptr[1] == end2Ptr[1]) { 195 /* 196 * Horizontal line. 197 */ 198 199 if (((end1Ptr[0] >= rectPtr[0]) ^ (end2Ptr[0] >= rectPtr[0])) 200 && (end1Ptr[1] >= rectPtr[1]) 201 && (end1Ptr[1] <= rectPtr[3])) { 202 return 0; 203 } 204 } else { 205 double m, x, y, low, high; 206 207 /* 208 * Diagonal line. Compute slope of line and use for intersection 209 * checks against each of the sides of the rectangle: left, right, 210 * bottom, top. 211 */ 212 213 m = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]); 214 if (end1Ptr[0] < end2Ptr[0]) { 215 low = end1Ptr[0]; 216 high = end2Ptr[0]; 217 } else { 218 low = end2Ptr[0]; 219 high = end1Ptr[0]; 220 } 221 222 /* 223 * Left edge. 224 */ 225 226 y = end1Ptr[1] + (rectPtr[0] - end1Ptr[0])*m; 227 if ((rectPtr[0] >= low) && (rectPtr[0] <= high) 228 && (y >= rectPtr[1]) && (y <= rectPtr[3])) { 229 return 0; 230 } 231 232 /* 233 * Right edge. 234 */ 235 236 y += (rectPtr[2] - rectPtr[0])*m; 237 if ((y >= rectPtr[1]) && (y <= rectPtr[3]) 238 && (rectPtr[2] >= low) && (rectPtr[2] <= high)) { 239 return 0; 240 } 241 242 /* 243 * Bottom edge. 244 */ 245 246 if (end1Ptr[1] < end2Ptr[1]) { 247 low = end1Ptr[1]; 248 high = end2Ptr[1]; 249 } else { 250 low = end2Ptr[1]; 251 high = end1Ptr[1]; 252 } 253 x = end1Ptr[0] + (rectPtr[1] - end1Ptr[1])/m; 254 if ((x >= rectPtr[0]) && (x <= rectPtr[2]) 255 && (rectPtr[1] >= low) && (rectPtr[1] <= high)) { 256 return 0; 257 } 258 259 /* 260 * Top edge. 261 */ 262 263 x += (rectPtr[3] - rectPtr[1])/m; 264 if ((x >= rectPtr[0]) && (x <= rectPtr[2]) 265 && (rectPtr[3] >= low) && (rectPtr[3] <= high)) { 266 return 0; 267 } 268 } 269 return -1; 270} 271 272/* 273 *-------------------------------------------------------------- 274 * 275 * TkThickPolyLineToArea -- 276 * 277 * This function is called to determine whether a connected series of 278 * line segments lies entirely inside, entirely outside, or overlapping a 279 * given rectangular area. 280 * 281 * Results: 282 * -1 is returned if the lines are entirely outside the area, 0 if they 283 * overlap, and 1 if they are entirely inside the given area. 284 * 285 * Side effects: 286 * None. 287 * 288 *-------------------------------------------------------------- 289 */ 290 291 /* ARGSUSED */ 292int 293TkThickPolyLineToArea( 294 double *coordPtr, /* Points to an array of coordinates for the 295 * polyline: x0, y0, x1, y1, ... */ 296 int numPoints, /* Total number of points at *coordPtr. */ 297 double width, /* Width of each line segment. */ 298 int capStyle, /* How are end-points of polyline drawn? 299 * CapRound, CapButt, or CapProjecting. */ 300 int joinStyle, /* How are joints in polyline drawn? 301 * JoinMiter, JoinRound, or JoinBevel. */ 302 double *rectPtr) /* Rectangular area to check against. */ 303{ 304 double radius, poly[10]; 305 int count; 306 int changedMiterToBevel; /* Non-zero means that a mitered corner had to 307 * be treated as beveled after all because the 308 * angle was < 11 degrees. */ 309 int inside; /* Tentative guess about what to return, based 310 * on all points seen so far: one means 311 * everything seen so far was inside the area; 312 * -1 means everything was outside the area. 313 * 0 means overlap has been found. */ 314 315 radius = width/2.0; 316 inside = -1; 317 318 if ((coordPtr[0] >= rectPtr[0]) && (coordPtr[0] <= rectPtr[2]) 319 && (coordPtr[1] >= rectPtr[1]) && (coordPtr[1] <= rectPtr[3])) { 320 inside = 1; 321 } 322 323 /* 324 * Iterate through all of the edges of the line, computing a polygon for 325 * each edge and testing the area against that polygon. In addition, there 326 * are additional tests to deal with rounded joints and caps. 327 */ 328 329 changedMiterToBevel = 0; 330 for (count = numPoints; count >= 2; count--, coordPtr += 2) { 331 /* 332 * If rounding is done around the first point of the edge then test a 333 * circular region around the point with the area. 334 */ 335 336 if (((capStyle == CapRound) && (count == numPoints)) 337 || ((joinStyle == JoinRound) && (count != numPoints))) { 338 poly[0] = coordPtr[0] - radius; 339 poly[1] = coordPtr[1] - radius; 340 poly[2] = coordPtr[0] + radius; 341 poly[3] = coordPtr[1] + radius; 342 if (TkOvalToArea(poly, rectPtr) != inside) { 343 return 0; 344 } 345 } 346 347 /* 348 * Compute the polygonal shape corresponding to this edge, consisting 349 * of two points for the first point of the edge and two points for 350 * the last point of the edge. 351 */ 352 353 if (count == numPoints) { 354 TkGetButtPoints(coordPtr+2, coordPtr, width, 355 capStyle == CapProjecting, poly, poly+2); 356 } else if ((joinStyle == JoinMiter) && !changedMiterToBevel) { 357 poly[0] = poly[6]; 358 poly[1] = poly[7]; 359 poly[2] = poly[4]; 360 poly[3] = poly[5]; 361 } else { 362 TkGetButtPoints(coordPtr+2, coordPtr, width, 0, poly, poly+2); 363 364 /* 365 * If the last joint was beveled, then also check a polygon 366 * comprising the last two points of the previous polygon and the 367 * first two from this polygon; this checks the wedges that fill 368 * the beveled joint. 369 */ 370 371 if ((joinStyle == JoinBevel) || changedMiterToBevel) { 372 poly[8] = poly[0]; 373 poly[9] = poly[1]; 374 if (TkPolygonToArea(poly, 5, rectPtr) != inside) { 375 return 0; 376 } 377 changedMiterToBevel = 0; 378 } 379 } 380 if (count == 2) { 381 TkGetButtPoints(coordPtr, coordPtr+2, width, 382 capStyle == CapProjecting, poly+4, poly+6); 383 } else if (joinStyle == JoinMiter) { 384 if (TkGetMiterPoints(coordPtr, coordPtr+2, coordPtr+4, 385 (double) width, poly+4, poly+6) == 0) { 386 changedMiterToBevel = 1; 387 TkGetButtPoints(coordPtr, coordPtr+2, width, 0, poly+4, 388 poly+6); 389 } 390 } else { 391 TkGetButtPoints(coordPtr, coordPtr+2, width, 0, poly+4, poly+6); 392 } 393 poly[8] = poly[0]; 394 poly[9] = poly[1]; 395 if (TkPolygonToArea(poly, 5, rectPtr) != inside) { 396 return 0; 397 } 398 } 399 400 /* 401 * If caps are rounded, check the cap around the final point of the line. 402 */ 403 404 if (capStyle == CapRound) { 405 poly[0] = coordPtr[0] - radius; 406 poly[1] = coordPtr[1] - radius; 407 poly[2] = coordPtr[0] + radius; 408 poly[3] = coordPtr[1] + radius; 409 if (TkOvalToArea(poly, rectPtr) != inside) { 410 return 0; 411 } 412 } 413 414 return inside; 415} 416 417/* 418 *-------------------------------------------------------------- 419 * 420 * TkPolygonToPoint -- 421 * 422 * Compute the distance from a point to a polygon. 423 * 424 * Results: 425 * The return value is 0.0 if the point referred to by pointPtr is within 426 * the polygon referred to by polyPtr and numPoints. Otherwise the return 427 * value is the distance of the point from the polygon. 428 * 429 * Side effects: 430 * None. 431 * 432 *-------------------------------------------------------------- 433 */ 434 435double 436TkPolygonToPoint( 437 double *polyPtr, /* Points to an array coordinates for closed 438 * polygon: x0, y0, x1, y1, ... The polygon 439 * may be self-intersecting. */ 440 int numPoints, /* Total number of points at *polyPtr. */ 441 double *pointPtr) /* Points to coords for point. */ 442{ 443 double bestDist; /* Closest distance between point and any edge 444 * in polygon. */ 445 int intersections; /* Number of edges in the polygon that 446 * intersect a ray extending vertically 447 * upwards from the point to infinity. */ 448 int count; 449 register double *pPtr; 450 451 /* 452 * Iterate through all of the edges in the polygon, updating bestDist and 453 * intersections. 454 * 455 * TRICKY POINT: when computing intersections, include left x-coordinate 456 * of line within its range, but not y-coordinate. Otherwise if the point 457 * lies exactly below a vertex we'll count it as two intersections. 458 */ 459 460 bestDist = 1.0e36; 461 intersections = 0; 462 463 for (count = numPoints, pPtr = polyPtr; count > 1; count--, pPtr += 2) { 464 double x, y, dist; 465 466 /* 467 * Compute the point on the current edge closest to the point and 468 * update the intersection count. This must be done separately for 469 * vertical edges, horizontal edges, and other edges. 470 */ 471 472 if (pPtr[2] == pPtr[0]) { 473 474 /* 475 * Vertical edge. 476 */ 477 478 x = pPtr[0]; 479 if (pPtr[1] >= pPtr[3]) { 480 y = MIN(pPtr[1], pointPtr[1]); 481 y = MAX(y, pPtr[3]); 482 } else { 483 y = MIN(pPtr[3], pointPtr[1]); 484 y = MAX(y, pPtr[1]); 485 } 486 } else if (pPtr[3] == pPtr[1]) { 487 488 /* 489 * Horizontal edge. 490 */ 491 492 y = pPtr[1]; 493 if (pPtr[0] >= pPtr[2]) { 494 x = MIN(pPtr[0], pointPtr[0]); 495 x = MAX(x, pPtr[2]); 496 if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[0]) 497 && (pointPtr[0] >= pPtr[2])) { 498 intersections++; 499 } 500 } else { 501 x = MIN(pPtr[2], pointPtr[0]); 502 x = MAX(x, pPtr[0]); 503 if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[2]) 504 && (pointPtr[0] >= pPtr[0])) { 505 intersections++; 506 } 507 } 508 } else { 509 double m1, b1, m2, b2; 510 int lower; /* Non-zero means point below line. */ 511 512 /* 513 * The edge is neither horizontal nor vertical. Convert the edge 514 * to a line equation of the form y = m1*x + b1. Then compute a 515 * line perpendicular to this edge but passing through the point, 516 * also in the form y = m2*x + b2. 517 */ 518 519 m1 = (pPtr[3] - pPtr[1])/(pPtr[2] - pPtr[0]); 520 b1 = pPtr[1] - m1*pPtr[0]; 521 m2 = -1.0/m1; 522 b2 = pointPtr[1] - m2*pointPtr[0]; 523 x = (b2 - b1)/(m1 - m2); 524 y = m1*x + b1; 525 if (pPtr[0] > pPtr[2]) { 526 if (x > pPtr[0]) { 527 x = pPtr[0]; 528 y = pPtr[1]; 529 } else if (x < pPtr[2]) { 530 x = pPtr[2]; 531 y = pPtr[3]; 532 } 533 } else { 534 if (x > pPtr[2]) { 535 x = pPtr[2]; 536 y = pPtr[3]; 537 } else if (x < pPtr[0]) { 538 x = pPtr[0]; 539 y = pPtr[1]; 540 } 541 } 542 lower = (m1*pointPtr[0] + b1) > pointPtr[1]; 543 if (lower && (pointPtr[0] >= MIN(pPtr[0], pPtr[2])) 544 && (pointPtr[0] < MAX(pPtr[0], pPtr[2]))) { 545 intersections++; 546 } 547 } 548 549 /* 550 * Compute the distance to the closest point, and see if that is the 551 * best distance seen so far. 552 */ 553 554 dist = hypot(pointPtr[0] - x, pointPtr[1] - y); 555 if (dist < bestDist) { 556 bestDist = dist; 557 } 558 } 559 560 /* 561 * We've processed all of the points. If the number of intersections is 562 * odd, the point is inside the polygon. 563 */ 564 565 if (intersections & 0x1) { 566 return 0.0; 567 } 568 return bestDist; 569} 570 571/* 572 *-------------------------------------------------------------- 573 * 574 * TkPolygonToArea -- 575 * 576 * Determine whether a polygon lies entirely inside, entirely outside, or 577 * overlapping a given rectangular area. 578 * 579 * Results: 580 * -1 is returned if the polygon given by polyPtr and numPoints is 581 * entirely outside the rectangle given by rectPtr. 0 is returned if the 582 * polygon overlaps the rectangle, and 1 is returned if the polygon is 583 * entirely inside the rectangle. 584 * 585 * Side effects: 586 * None. 587 * 588 *-------------------------------------------------------------- 589 */ 590 591int 592TkPolygonToArea( 593 double *polyPtr, /* Points to an array coordinates for closed 594 * polygon: x0, y0, x1, y1, ... The polygon 595 * may be self-intersecting. */ 596 int numPoints, /* Total number of points at *polyPtr. */ 597 register double *rectPtr) /* Points to coords for rectangle, in the 598 * order x1, y1, x2, y2. X1 and y1 must be 599 * lower-left corner. */ 600{ 601 int state; /* State of all edges seen so far (-1 means 602 * outside, 1 means inside, won't ever be 603 * 0). */ 604 int count; 605 register double *pPtr; 606 607 /* 608 * Iterate over all of the edges of the polygon and test them against the 609 * rectangle. Can quit as soon as the state becomes "intersecting". 610 */ 611 612 state = TkLineToArea(polyPtr, polyPtr+2, rectPtr); 613 if (state == 0) { 614 return 0; 615 } 616 for (pPtr = polyPtr+2, count = numPoints-1; count >= 2; 617 pPtr += 2, count--) { 618 if (TkLineToArea(pPtr, pPtr+2, rectPtr) != state) { 619 return 0; 620 } 621 } 622 623 /* 624 * If all of the edges were inside the rectangle we're done. If all of the 625 * edges were outside, then the rectangle could still intersect the 626 * polygon (if it's entirely enclosed). Call TkPolygonToPoint to figure 627 * this out. 628 */ 629 630 if (state == 1) { 631 return 1; 632 } 633 if (TkPolygonToPoint(polyPtr, numPoints, rectPtr) == 0.0) { 634 return 0; 635 } 636 return -1; 637} 638 639/* 640 *-------------------------------------------------------------- 641 * 642 * TkOvalToPoint -- 643 * 644 * Computes the distance from a given point to a given oval, in canvas 645 * units. 646 * 647 * Results: 648 * The return value is 0 if the point given by *pointPtr is inside the 649 * oval. If the point isn't inside the oval then the return value is 650 * approximately the distance from the point to the oval. If the oval is 651 * filled, then anywhere in the interior is considered "inside"; if the 652 * oval isn't filled, then "inside" means only the area occupied by the 653 * outline. 654 * 655 * Side effects: 656 * None. 657 * 658 *-------------------------------------------------------------- 659 */ 660 661 /* ARGSUSED */ 662double 663TkOvalToPoint( 664 double ovalPtr[4], /* Pointer to array of four coordinates (x1, 665 * y1, x2, y2) defining oval's bounding 666 * box. */ 667 double width, /* Width of outline for oval. */ 668 int filled, /* Non-zero means oval should be treated as 669 * filled; zero means only consider 670 * outline. */ 671 double pointPtr[2]) /* Coordinates of point. */ 672{ 673 double xDelta, yDelta, scaledDistance, distToOutline, distToCenter; 674 double xDiam, yDiam; 675 676 /* 677 * Compute the distance between the center of the oval and the point in 678 * question, using a coordinate system where the oval has been transformed 679 * to a circle with unit radius. 680 */ 681 682 xDelta = (pointPtr[0] - (ovalPtr[0] + ovalPtr[2])/2.0); 683 yDelta = (pointPtr[1] - (ovalPtr[1] + ovalPtr[3])/2.0); 684 distToCenter = hypot(xDelta, yDelta); 685 scaledDistance = hypot(xDelta / ((ovalPtr[2] + width - ovalPtr[0])/2.0), 686 yDelta / ((ovalPtr[3] + width - ovalPtr[1])/2.0)); 687 688 /* 689 * If the scaled distance is greater than 1 then it means no hit. Compute 690 * the distance from the point to the edge of the circle, then scale this 691 * distance back to the original coordinate system. 692 * 693 * Note: this distance isn't completely accurate. It's only an 694 * approximation, and it can overestimate the correct distance when the 695 * oval is eccentric. 696 */ 697 698 if (scaledDistance > 1.0) { 699 return (distToCenter/scaledDistance) * (scaledDistance - 1.0); 700 } 701 702 /* 703 * Scaled distance less than 1 means the point is inside the outer edge of 704 * the oval. If this is a filled oval, then we have a hit. Otherwise, do 705 * the same computation as above (scale back to original coordinate 706 * system), but also check to see if the point is within the width of the 707 * outline. 708 */ 709 710 if (filled) { 711 return 0.0; 712 } 713 if (scaledDistance > 1E-10) { 714 distToOutline = (distToCenter/scaledDistance) * (1.0 - scaledDistance) 715 - width; 716 } else { 717 /* 718 * Avoid dividing by a very small number (it could cause an arithmetic 719 * overflow). This problem occurs if the point is very close to the 720 * center of the oval. 721 */ 722 723 xDiam = ovalPtr[2] - ovalPtr[0]; 724 yDiam = ovalPtr[3] - ovalPtr[1]; 725 if (xDiam < yDiam) { 726 distToOutline = (xDiam - width)/2; 727 } else { 728 distToOutline = (yDiam - width)/2; 729 } 730 } 731 732 if (distToOutline < 0.0) { 733 return 0.0; 734 } 735 return distToOutline; 736} 737 738/* 739 *-------------------------------------------------------------- 740 * 741 * TkOvalToArea -- 742 * 743 * Determine whether an oval lies entirely inside, entirely outside, or 744 * overlapping a given rectangular area. 745 * 746 * Results: 747 * -1 is returned if the oval described by ovalPtr is entirely outside 748 * the rectangle given by rectPtr. 0 is returned if the oval overlaps the 749 * rectangle, and 1 is returned if the oval is entirely inside the 750 * rectangle. 751 * 752 * Side effects: 753 * None. 754 * 755 *-------------------------------------------------------------- 756 */ 757 758int 759TkOvalToArea( 760 register double *ovalPtr, /* Points to coordinates definining the 761 * bounding rectangle for the oval: x1, y1, 762 * x2, y2. X1 must be less than x2 and y1 less 763 * than y2. */ 764 register double *rectPtr) /* Points to coords for rectangle, in the 765 * order x1, y1, x2, y2. X1 and y1 must be 766 * lower-left corner. */ 767{ 768 double centerX, centerY, radX, radY, deltaX, deltaY; 769 770 /* 771 * First, see if oval is entirely inside rectangle or entirely outside 772 * rectangle. 773 */ 774 775 if ((rectPtr[0] <= ovalPtr[0]) && (rectPtr[2] >= ovalPtr[2]) 776 && (rectPtr[1] <= ovalPtr[1]) && (rectPtr[3] >= ovalPtr[3])) { 777 return 1; 778 } 779 if ((rectPtr[2] < ovalPtr[0]) || (rectPtr[0] > ovalPtr[2]) 780 || (rectPtr[3] < ovalPtr[1]) || (rectPtr[1] > ovalPtr[3])) { 781 return -1; 782 } 783 784 /* 785 * Next, go through the rectangle side by side. For each side of the 786 * rectangle, find the point on the side that is closest to the oval's 787 * center, and see if that point is inside the oval. If at least one such 788 * point is inside the oval, then the rectangle intersects the oval. 789 */ 790 791 centerX = (ovalPtr[0] + ovalPtr[2])/2; 792 centerY = (ovalPtr[1] + ovalPtr[3])/2; 793 radX = (ovalPtr[2] - ovalPtr[0])/2; 794 radY = (ovalPtr[3] - ovalPtr[1])/2; 795 796 deltaY = rectPtr[1] - centerY; 797 if (deltaY < 0.0) { 798 deltaY = centerY - rectPtr[3]; 799 if (deltaY < 0.0) { 800 deltaY = 0; 801 } 802 } 803 deltaY /= radY; 804 deltaY *= deltaY; 805 806 /* 807 * Left side: 808 */ 809 810 deltaX = (rectPtr[0] - centerX)/radX; 811 deltaX *= deltaX; 812 if ((deltaX + deltaY) <= 1.0) { 813 return 0; 814 } 815 816 /* 817 * Right side: 818 */ 819 820 deltaX = (rectPtr[2] - centerX)/radX; 821 deltaX *= deltaX; 822 if ((deltaX + deltaY) <= 1.0) { 823 return 0; 824 } 825 826 deltaX = rectPtr[0] - centerX; 827 if (deltaX < 0.0) { 828 deltaX = centerX - rectPtr[2]; 829 if (deltaX < 0.0) { 830 deltaX = 0; 831 } 832 } 833 deltaX /= radX; 834 deltaX *= deltaX; 835 836 /* 837 * Bottom side: 838 */ 839 840 deltaY = (rectPtr[1] - centerY)/radY; 841 deltaY *= deltaY; 842 if ((deltaX + deltaY) < 1.0) { 843 return 0; 844 } 845 846 /* 847 * Top side: 848 */ 849 850 deltaY = (rectPtr[3] - centerY)/radY; 851 deltaY *= deltaY; 852 if ((deltaX + deltaY) < 1.0) { 853 return 0; 854 } 855 856 return -1; 857} 858 859/* 860 *-------------------------------------------------------------- 861 * 862 * TkIncludePoint -- 863 * 864 * Given a point and a generic canvas item header, expand the item's 865 * bounding box if needed to include the point. 866 * 867 * Results: 868 * None. 869 * 870 * Side effects: 871 * The boudn. 872 * 873 *-------------------------------------------------------------- 874 */ 875 876 /* ARGSUSED */ 877void 878TkIncludePoint( 879 register Tk_Item *itemPtr, /* Item whose bounding box is being 880 * calculated. */ 881 double *pointPtr) /* Address of two doubles giving x and y 882 * coordinates of point. */ 883{ 884 int tmp; 885 886 tmp = (int) (pointPtr[0] + 0.5); 887 if (tmp < itemPtr->x1) { 888 itemPtr->x1 = tmp; 889 } 890 if (tmp > itemPtr->x2) { 891 itemPtr->x2 = tmp; 892 } 893 tmp = (int) (pointPtr[1] + 0.5); 894 if (tmp < itemPtr->y1) { 895 itemPtr->y1 = tmp; 896 } 897 if (tmp > itemPtr->y2) { 898 itemPtr->y2 = tmp; 899 } 900} 901 902/* 903 *-------------------------------------------------------------- 904 * 905 * TkBezierScreenPoints -- 906 * 907 * Given four control points, create a larger set of XPoints for a Bezier 908 * curve based on the points. 909 * 910 * Results: 911 * The array at *xPointPtr gets filled in with numSteps XPoints 912 * corresponding to the Bezier spline defined by the four control points. 913 * Note: no output point is generated for the first input point, but an 914 * output point *is* generated for the last input point. 915 * 916 * Side effects: 917 * None. 918 * 919 *-------------------------------------------------------------- 920 */ 921 922void 923TkBezierScreenPoints( 924 Tk_Canvas canvas, /* Canvas in which curve is to be drawn. */ 925 double control[], /* Array of coordinates for four control 926 * points: x0, y0, x1, y1, ... x3 y3. */ 927 int numSteps, /* Number of curve points to generate. */ 928 register XPoint *xPointPtr) /* Where to put new points. */ 929{ 930 int i; 931 double u, u2, u3, t, t2, t3; 932 933 for (i = 1; i <= numSteps; i++, xPointPtr++) { 934 t = ((double) i)/((double) numSteps); 935 t2 = t*t; 936 t3 = t2*t; 937 u = 1.0 - t; 938 u2 = u*u; 939 u3 = u2*u; 940 Tk_CanvasDrawableCoords(canvas, 941 (control[0]*u3 + 3.0 * (control[2]*t*u2 + control[4]*t2*u) 942 + control[6]*t3), 943 (control[1]*u3 + 3.0 * (control[3]*t*u2 + control[5]*t2*u) 944 + control[7]*t3), 945 &xPointPtr->x, &xPointPtr->y); 946 } 947} 948 949/* 950 *-------------------------------------------------------------- 951 * 952 * TkBezierPoints -- 953 * 954 * Given four control points, create a larger set of points for a Bezier 955 * curve based on the points. 956 * 957 * Results: 958 * The array at *coordPtr gets filled in with 2*numSteps coordinates, 959 * which correspond to the Bezier spline defined by the four control 960 * points. Note: no output point is generated for the first input point, 961 * but an output point *is* generated for the last input point. 962 * 963 * Side effects: 964 * None. 965 * 966 *-------------------------------------------------------------- 967 */ 968 969void 970TkBezierPoints( 971 double control[], /* Array of coordinates for four control 972 * points: x0, y0, x1, y1, ... x3 y3. */ 973 int numSteps, /* Number of curve points to generate. */ 974 register double *coordPtr) /* Where to put new points. */ 975{ 976 int i; 977 double u, u2, u3, t, t2, t3; 978 979 for (i = 1; i <= numSteps; i++, coordPtr += 2) { 980 t = ((double) i)/((double) numSteps); 981 t2 = t*t; 982 t3 = t2*t; 983 u = 1.0 - t; 984 u2 = u*u; 985 u3 = u2*u; 986 coordPtr[0] = control[0]*u3 987 + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3; 988 coordPtr[1] = control[1]*u3 989 + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3; 990 } 991} 992 993/* 994 *-------------------------------------------------------------- 995 * 996 * TkMakeBezierCurve -- 997 * 998 * Given a set of points, create a new set of points that fit parabolic 999 * splines to the line segments connecting the original points. Produces 1000 * output points in either of two forms. 1001 * 1002 * Note: the name of this function should *not* be taken to mean that it 1003 * interprets the input points as directly defining Bezier curves. 1004 * Rather, it internally computes a Bezier curve representation of each 1005 * parabolic spline segment. (These Bezier curves are then flattened to 1006 * produce the points filled into the output arrays.) 1007 * 1008 * Results: 1009 * Either or both of the xPoints or dblPoints arrays are filled in. The 1010 * return value is the number of points placed in the arrays. Note: if 1011 * the first and last points are the same, then a closed curve is 1012 * generated. 1013 * 1014 * Side effects: 1015 * None. 1016 * 1017 *-------------------------------------------------------------- 1018 */ 1019 1020int 1021TkMakeBezierCurve( 1022 Tk_Canvas canvas, /* Canvas in which curve is to be drawn. */ 1023 double *pointPtr, /* Array of input coordinates: x0, y0, x1, y1, 1024 * etc.. */ 1025 int numPoints, /* Number of points at pointPtr. */ 1026 int numSteps, /* Number of steps to use for each spline 1027 * segments (determines smoothness of 1028 * curve). */ 1029 XPoint xPoints[], /* Array of XPoints to fill in (e.g. for 1030 * display). NULL means don't fill in any 1031 * XPoints. */ 1032 double dblPoints[]) /* Array of points to fill in as doubles, in 1033 * the form x0, y0, x1, y1, .... NULL means 1034 * don't fill in anything in this form. Caller 1035 * must make sure that this array has enough 1036 * space. */ 1037{ 1038 int closed, outputPoints, i; 1039 int numCoords = numPoints*2; 1040 double control[8]; 1041 1042 /* 1043 * If the curve is a closed one then generate a special spline that spans 1044 * the last points and the first ones. Otherwise just put the first point 1045 * into the output. 1046 */ 1047 1048 if (!pointPtr) { 1049 /* 1050 * Of pointPtr == NULL, this function returns an upper limit of the 1051 * array size to store the coordinates. This can be used to allocate 1052 * storage, before the actual coordinates are calculated. 1053 */ 1054 1055 return 1 + numPoints * numSteps; 1056 } 1057 1058 outputPoints = 0; 1059 if ((pointPtr[0] == pointPtr[numCoords-2]) 1060 && (pointPtr[1] == pointPtr[numCoords-1])) { 1061 closed = 1; 1062 control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0]; 1063 control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1]; 1064 control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0]; 1065 control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1]; 1066 control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2]; 1067 control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3]; 1068 control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; 1069 control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; 1070 if (xPoints != NULL) { 1071 Tk_CanvasDrawableCoords(canvas, control[0], control[1], 1072 &xPoints->x, &xPoints->y); 1073 TkBezierScreenPoints(canvas, control, numSteps, xPoints+1); 1074 xPoints += numSteps+1; 1075 } 1076 if (dblPoints != NULL) { 1077 dblPoints[0] = control[0]; 1078 dblPoints[1] = control[1]; 1079 TkBezierPoints(control, numSteps, dblPoints+2); 1080 dblPoints += 2*(numSteps+1); 1081 } 1082 outputPoints += numSteps+1; 1083 } else { 1084 closed = 0; 1085 if (xPoints != NULL) { 1086 Tk_CanvasDrawableCoords(canvas, pointPtr[0], pointPtr[1], 1087 &xPoints->x, &xPoints->y); 1088 xPoints += 1; 1089 } 1090 if (dblPoints != NULL) { 1091 dblPoints[0] = pointPtr[0]; 1092 dblPoints[1] = pointPtr[1]; 1093 dblPoints += 2; 1094 } 1095 outputPoints += 1; 1096 } 1097 1098 for (i = 2; i < numPoints; i++, pointPtr += 2) { 1099 /* 1100 * Set up the first two control points. This is done differently for 1101 * the first spline of an open curve than for other cases. 1102 */ 1103 1104 if ((i == 2) && !closed) { 1105 control[0] = pointPtr[0]; 1106 control[1] = pointPtr[1]; 1107 control[2] = 0.333*pointPtr[0] + 0.667*pointPtr[2]; 1108 control[3] = 0.333*pointPtr[1] + 0.667*pointPtr[3]; 1109 } else { 1110 control[0] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; 1111 control[1] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; 1112 control[2] = 0.167*pointPtr[0] + 0.833*pointPtr[2]; 1113 control[3] = 0.167*pointPtr[1] + 0.833*pointPtr[3]; 1114 } 1115 1116 /* 1117 * Set up the last two control points. This is done differently for 1118 * the last spline of an open curve than for other cases. 1119 */ 1120 1121 if ((i == (numPoints-1)) && !closed) { 1122 control[4] = .667*pointPtr[2] + .333*pointPtr[4]; 1123 control[5] = .667*pointPtr[3] + .333*pointPtr[5]; 1124 control[6] = pointPtr[4]; 1125 control[7] = pointPtr[5]; 1126 } else { 1127 control[4] = .833*pointPtr[2] + .167*pointPtr[4]; 1128 control[5] = .833*pointPtr[3] + .167*pointPtr[5]; 1129 control[6] = 0.5*pointPtr[2] + 0.5*pointPtr[4]; 1130 control[7] = 0.5*pointPtr[3] + 0.5*pointPtr[5]; 1131 } 1132 1133 /* 1134 * If the first two points coincide, or if the last two points 1135 * coincide, then generate a single straight-line segment by 1136 * outputting the last control point. 1137 */ 1138 1139 if (((pointPtr[0] == pointPtr[2]) && (pointPtr[1] == pointPtr[3])) 1140 || ((pointPtr[2] == pointPtr[4]) 1141 && (pointPtr[3] == pointPtr[5]))) { 1142 if (xPoints != NULL) { 1143 Tk_CanvasDrawableCoords(canvas, control[6], control[7], 1144 &xPoints[0].x, &xPoints[0].y); 1145 xPoints++; 1146 } 1147 if (dblPoints != NULL) { 1148 dblPoints[0] = control[6]; 1149 dblPoints[1] = control[7]; 1150 dblPoints += 2; 1151 } 1152 outputPoints += 1; 1153 continue; 1154 } 1155 1156 /* 1157 * Generate a Bezier spline using the control points. 1158 */ 1159 1160 1161 if (xPoints != NULL) { 1162 TkBezierScreenPoints(canvas, control, numSteps, xPoints); 1163 xPoints += numSteps; 1164 } 1165 if (dblPoints != NULL) { 1166 TkBezierPoints(control, numSteps, dblPoints); 1167 dblPoints += 2*numSteps; 1168 } 1169 outputPoints += numSteps; 1170 } 1171 return outputPoints; 1172} 1173 1174/* 1175 *-------------------------------------------------------------- 1176 * 1177 * TkMakeRawCurve -- 1178 * 1179 * Interpret the given set of points as the raw knots and control points 1180 * defining a sequence of cubic Bezier curves. Create a new set of points 1181 * that fit these Bezier curves. Output points are produced in either of 1182 * two forms. 1183 * 1184 * Results: 1185 * Either or both of the xPoints or dblPoints arrays are filled in. The 1186 * return value is the number of points placed in the arrays. 1187 * 1188 * Side effects: 1189 * None. 1190 * 1191 *-------------------------------------------------------------- 1192 */ 1193 1194int 1195TkMakeRawCurve( 1196 Tk_Canvas canvas, /* Canvas in which curve is to be drawn. */ 1197 double *pointPtr, /* Array of input coordinates: x0, y0, x1, y1, 1198 * etc.. */ 1199 int numPoints, /* Number of points at pointPtr. */ 1200 int numSteps, /* Number of steps to use for each curve 1201 * segment (determines smoothness of 1202 * curve). */ 1203 XPoint xPoints[], /* Array of XPoints to fill in (e.g. for 1204 * display). NULL means don't fill in any 1205 * XPoints. */ 1206 double dblPoints[]) /* Array of points to fill in as doubles, in 1207 * the form x0, y0, x1, y1, .... NULL means 1208 * don't fill in anything in this form. 1209 * Caller must make sure that this array has 1210 * enough space. */ 1211{ 1212 int outputPoints, i; 1213 int numSegments = (numPoints+1)/3; 1214 double *segPtr; 1215 1216 /* 1217 * The input describes a curve with s Bezier curve segments if there are 1218 * 3s+1, 3s, or 3s-1 input points. In the last two cases, 1 or 2 initial 1219 * points from the first curve segment are reused as defining points also 1220 * for the last curve segment. In the case of 3s input points, this will 1221 * automatically close the curve. 1222 */ 1223 1224 if (!pointPtr) { 1225 /* 1226 * If pointPtr == NULL, this function returns an upper limit of the 1227 * array size to store the coordinates. This can be used to allocate 1228 * storage, before the actual coordinates are calculated. 1229 */ 1230 1231 return 1 + numSegments * numSteps; 1232 } 1233 1234 outputPoints = 0; 1235 if (xPoints != NULL) { 1236 Tk_CanvasDrawableCoords(canvas, pointPtr[0], pointPtr[1], 1237 &xPoints->x, &xPoints->y); 1238 xPoints += 1; 1239 } 1240 if (dblPoints != NULL) { 1241 dblPoints[0] = pointPtr[0]; 1242 dblPoints[1] = pointPtr[1]; 1243 dblPoints += 2; 1244 } 1245 outputPoints += 1; 1246 1247 /* 1248 * The next loop handles all curve segments except one that overlaps the 1249 * end of the list of coordinates. 1250 */ 1251 1252 for (i=numPoints,segPtr=pointPtr ; i>=4 ; i-=3,segPtr+=6) { 1253 if (segPtr[0]==segPtr[2] && segPtr[1]==segPtr[3] && 1254 segPtr[4]==segPtr[6] && segPtr[5]==segPtr[7]) { 1255 /* 1256 * The control points on this segment are equal to their 1257 * neighbouring knots, so this segment is just a straight line. A 1258 * single point is sufficient. 1259 */ 1260 1261 if (xPoints != NULL) { 1262 Tk_CanvasDrawableCoords(canvas, segPtr[6], segPtr[7], 1263 &xPoints->x, &xPoints->y); 1264 xPoints += 1; 1265 } 1266 if (dblPoints != NULL) { 1267 dblPoints[0] = segPtr[6]; 1268 dblPoints[1] = segPtr[7]; 1269 dblPoints += 2; 1270 } 1271 outputPoints += 1; 1272 } else { 1273 /* 1274 * This is a generic Bezier curve segment. 1275 */ 1276 1277 if (xPoints != NULL) { 1278 TkBezierScreenPoints(canvas, segPtr, numSteps, xPoints); 1279 xPoints += numSteps; 1280 } 1281 if (dblPoints != NULL) { 1282 TkBezierPoints(segPtr, numSteps, dblPoints); 1283 dblPoints += 2*numSteps; 1284 } 1285 outputPoints += numSteps; 1286 } 1287 } 1288 1289 /* 1290 * If at this point i>1, then there is some point which has not yet been 1291 * used. Make another curve segment. 1292 */ 1293 1294 if (i > 1) { 1295 int j; 1296 double control[8]; 1297 1298 /* 1299 * Copy the relevant coordinates to control[], so that it can be 1300 * passed as a unit to e.g. TkBezierPoints. 1301 */ 1302 1303 for (j=0; j<2*i; j++) { 1304 control[j] = segPtr[j]; 1305 } 1306 for (; j<8; j++) { 1307 control[j] = pointPtr[j-2*i]; 1308 } 1309 1310 /* 1311 * Then we just do the same things as above. 1312 */ 1313 1314 if (control[0]==control[2] && control[1]==control[3] && 1315 control[4]==control[6] && control[5]==control[7]) { 1316 /* 1317 * The control points on this segment are equal to their 1318 * neighbouring knots, so this segment is just a straight line. A 1319 * single point is sufficient. 1320 */ 1321 1322 if (xPoints != NULL) { 1323 Tk_CanvasDrawableCoords(canvas, control[6], control[7], 1324 &xPoints->x, &xPoints->y); 1325 xPoints += 1; 1326 } 1327 if (dblPoints != NULL) { 1328 dblPoints[0] = control[6]; 1329 dblPoints[1] = control[7]; 1330 dblPoints += 2; 1331 } 1332 outputPoints += 1; 1333 } else { 1334 /* 1335 * This is a generic Bezier curve segment. 1336 */ 1337 1338 if (xPoints != NULL) { 1339 TkBezierScreenPoints(canvas, control, numSteps, xPoints); 1340 xPoints += numSteps; 1341 } 1342 if (dblPoints != NULL) { 1343 TkBezierPoints(control, numSteps, dblPoints); 1344 dblPoints += 2*numSteps; 1345 } 1346 outputPoints += numSteps; 1347 } 1348 } 1349 1350 return outputPoints; 1351} 1352 1353/* 1354 *-------------------------------------------------------------- 1355 * 1356 * TkMakeBezierPostscript -- 1357 * 1358 * This function generates Postscript commands that create a path 1359 * corresponding to a given Bezier curve. 1360 * 1361 * Results: 1362 * None. Postscript commands to generate the path are appended to the 1363 * interp's result. 1364 * 1365 * Side effects: 1366 * None. 1367 * 1368 *-------------------------------------------------------------- 1369 */ 1370 1371void 1372TkMakeBezierPostscript( 1373 Tcl_Interp *interp, /* Interpreter in whose result the Postscript 1374 * is to be stored. */ 1375 Tk_Canvas canvas, /* Canvas widget for which the Postscript is 1376 * being generated. */ 1377 double *pointPtr, /* Array of input coordinates: x0, y0, x1, y1, 1378 * etc.. */ 1379 int numPoints) /* Number of points at pointPtr. */ 1380{ 1381 int closed, i; 1382 int numCoords = numPoints*2; 1383 double control[8]; 1384 char buffer[200]; 1385 1386 /* 1387 * If the curve is a closed one then generate a special spline that spans 1388 * the last points and the first ones. Otherwise just put the first point 1389 * into the path. 1390 */ 1391 1392 if ((pointPtr[0] == pointPtr[numCoords-2]) 1393 && (pointPtr[1] == pointPtr[numCoords-1])) { 1394 closed = 1; 1395 control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0]; 1396 control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1]; 1397 control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0]; 1398 control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1]; 1399 control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2]; 1400 control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3]; 1401 control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; 1402 control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; 1403 sprintf(buffer, "%.15g %.15g moveto\n%.15g %.15g %.15g %.15g %.15g %.15g curveto\n", 1404 control[0], Tk_CanvasPsY(canvas, control[1]), 1405 control[2], Tk_CanvasPsY(canvas, control[3]), 1406 control[4], Tk_CanvasPsY(canvas, control[5]), 1407 control[6], Tk_CanvasPsY(canvas, control[7])); 1408 } else { 1409 closed = 0; 1410 control[6] = pointPtr[0]; 1411 control[7] = pointPtr[1]; 1412 sprintf(buffer, "%.15g %.15g moveto\n", 1413 control[6], Tk_CanvasPsY(canvas, control[7])); 1414 } 1415 Tcl_AppendResult(interp, buffer, NULL); 1416 1417 /* 1418 * Cycle through all the remaining points in the curve, generating a curve 1419 * section for each vertex in the linear path. 1420 */ 1421 1422 for (i = numPoints-2, pointPtr += 2; i > 0; i--, pointPtr += 2) { 1423 control[2] = 0.333*control[6] + 0.667*pointPtr[0]; 1424 control[3] = 0.333*control[7] + 0.667*pointPtr[1]; 1425 1426 /* 1427 * Set up the last two control points. This is done differently for 1428 * the last spline of an open curve than for other cases. 1429 */ 1430 1431 if ((i == 1) && !closed) { 1432 control[6] = pointPtr[2]; 1433 control[7] = pointPtr[3]; 1434 } else { 1435 control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; 1436 control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; 1437 } 1438 control[4] = 0.333*control[6] + 0.667*pointPtr[0]; 1439 control[5] = 0.333*control[7] + 0.667*pointPtr[1]; 1440 1441 sprintf(buffer, "%.15g %.15g %.15g %.15g %.15g %.15g curveto\n", 1442 control[2], Tk_CanvasPsY(canvas, control[3]), 1443 control[4], Tk_CanvasPsY(canvas, control[5]), 1444 control[6], Tk_CanvasPsY(canvas, control[7])); 1445 Tcl_AppendResult(interp, buffer, NULL); 1446 } 1447} 1448 1449/* 1450 *-------------------------------------------------------------- 1451 * 1452 * TkMakeRawCurvePostscript -- 1453 * 1454 * This function interprets the input points as the raw knot and control 1455 * points for a curve composed of Bezier curve segments, just like 1456 * TkMakeRawCurve. It generates Postscript commands that create a path 1457 * corresponding to this given curve. 1458 * 1459 * Results: 1460 * None. Postscript commands to generate the path are appended to the 1461 * interp's result. 1462 * 1463 * Side effects: 1464 * None. 1465 * 1466 *-------------------------------------------------------------- 1467 */ 1468 1469void 1470TkMakeRawCurvePostscript( 1471 Tcl_Interp *interp, /* Interpreter in whose result the Postscript 1472 * is to be stored. */ 1473 Tk_Canvas canvas, /* Canvas widget for which the Postscript is 1474 * being generated. */ 1475 double *pointPtr, /* Array of input coordinates: x0, y0, x1, y1, 1476 * etc.. */ 1477 int numPoints) /* Number of points at pointPtr. */ 1478{ 1479 int i; 1480 double *segPtr; 1481 char buffer[200]; 1482 1483 /* 1484 * Put the first point into the path. 1485 */ 1486 1487 sprintf(buffer, "%.15g %.15g moveto\n", 1488 pointPtr[0], Tk_CanvasPsY(canvas, pointPtr[1])); 1489 Tcl_AppendResult(interp, buffer, NULL); 1490 1491 /* 1492 * Loop through all the remaining points in the curve, generating a 1493 * straight line or curve section for every three of them. 1494 */ 1495 1496 for (i=numPoints-1,segPtr=pointPtr ; i>=3 ; i-=3,segPtr+=6) { 1497 if (segPtr[0]==segPtr[2] && segPtr[1]==segPtr[3] && 1498 segPtr[4]==segPtr[6] && segPtr[5]==segPtr[7]) { 1499 /* 1500 * The control points on this segment are equal to their 1501 * neighbouring knots, so this segment is just a straight line. 1502 */ 1503 1504 sprintf(buffer, "%.15g %.15g lineto\n", 1505 segPtr[6], Tk_CanvasPsY(canvas, segPtr[7])); 1506 } else { 1507 /* 1508 * This is a generic Bezier curve segment. 1509 */ 1510 1511 sprintf(buffer, "%.15g %.15g %.15g %.15g %.15g %.15g curveto\n", 1512 segPtr[2], Tk_CanvasPsY(canvas, segPtr[3]), 1513 segPtr[4], Tk_CanvasPsY(canvas, segPtr[5]), 1514 segPtr[6], Tk_CanvasPsY(canvas, segPtr[7])); 1515 } 1516 Tcl_AppendResult(interp, buffer, NULL); 1517 } 1518 1519 /* 1520 * If there are any points left that haven't been used, then build the 1521 * last segment and generate Postscript in the same way for that. 1522 */ 1523 1524 if (i > 0) { 1525 int j; 1526 double control[8]; 1527 1528 for (j=0; j<2*i+2; j++) { 1529 control[j] = segPtr[j]; 1530 } 1531 for (; j<8; j++) { 1532 control[j] = pointPtr[j-2*i-2]; 1533 } 1534 1535 if (control[0]==control[2] && control[1]==control[3] && 1536 control[4]==control[6] && control[5]==control[7]) { 1537 /* 1538 * Straight line. 1539 */ 1540 1541 sprintf(buffer, "%.15g %.15g lineto\n", 1542 control[6], Tk_CanvasPsY(canvas, control[7])); 1543 } else { 1544 /* 1545 * Bezier curve segment. 1546 */ 1547 1548 sprintf(buffer, "%.15g %.15g %.15g %.15g %.15g %.15g curveto\n", 1549 control[2], Tk_CanvasPsY(canvas, control[3]), 1550 control[4], Tk_CanvasPsY(canvas, control[5]), 1551 control[6], Tk_CanvasPsY(canvas, control[7])); 1552 } 1553 Tcl_AppendResult(interp, buffer, NULL); 1554 } 1555} 1556 1557/* 1558 *-------------------------------------------------------------- 1559 * 1560 * TkGetMiterPoints -- 1561 * 1562 * Given three points forming an angle, compute the coordinates of the 1563 * inside and outside points of the mitered corner formed by a line of a 1564 * given width at that angle. 1565 * 1566 * Results: 1567 * If the angle formed by the three points is less than 11 degrees then 0 1568 * is returned and m1 and m2 aren't modified. Otherwise 1 is returned and 1569 * the points at m1 and m2 are filled in with the positions of the points 1570 * of the mitered corner. 1571 * 1572 * Side effects: 1573 * None. 1574 * 1575 *-------------------------------------------------------------- 1576 */ 1577 1578int 1579TkGetMiterPoints( 1580 double p1[], /* Points to x- and y-coordinates of point 1581 * before vertex. */ 1582 double p2[], /* Points to x- and y-coordinates of vertex 1583 * for mitered joint. */ 1584 double p3[], /* Points to x- and y-coordinates of point 1585 * after vertex. */ 1586 double width, /* Width of line. */ 1587 double m1[], /* Points to place to put "left" vertex point 1588 * (see as you face from p1 to p2). */ 1589 double m2[]) /* Points to place to put "right" vertex 1590 * point. */ 1591{ 1592 double theta1; /* Angle of segment p2-p1. */ 1593 double theta2; /* Angle of segment p2-p3. */ 1594 double theta; /* Angle between line segments (angle of 1595 * joint). */ 1596 double theta3; /* Angle that bisects theta1 and theta2 and 1597 * points to m1. */ 1598 double dist; /* Distance of miter points from p2. */ 1599 double deltaX, deltaY; /* X and y offsets cooresponding to dist 1600 * (fudge factors for bounding box). */ 1601 double p1x, p1y, p2x, p2y, p3x, p3y; 1602#ifndef _MSC_VER 1603 static const double elevenDegrees = (11.0*2.0*PI)/360.0; 1604#else /* msvc8 with -fp:strict requires it this way */ 1605 static const double elevenDegrees = 0.19198621771937624; 1606#endif 1607 1608 /* 1609 * Round the coordinates to integers to mimic what happens when the line 1610 * segments are displayed; without this code, the bounding box of a 1611 * mitered line can be miscomputed greatly. 1612 */ 1613 1614 p1x = floor(p1[0]+0.5); 1615 p1y = floor(p1[1]+0.5); 1616 p2x = floor(p2[0]+0.5); 1617 p2y = floor(p2[1]+0.5); 1618 p3x = floor(p3[0]+0.5); 1619 p3y = floor(p3[1]+0.5); 1620 1621 if (p2y == p1y) { 1622 theta1 = (p2x < p1x) ? 0 : PI; 1623 } else if (p2x == p1x) { 1624 theta1 = (p2y < p1y) ? PI/2.0 : -PI/2.0; 1625 } else { 1626 theta1 = atan2(p1y - p2y, p1x - p2x); 1627 } 1628 1629 if (p3y == p2y) { 1630 theta2 = (p3x > p2x) ? 0 : PI; 1631 } else if (p3x == p2x) { 1632 theta2 = (p3y > p2y) ? PI/2.0 : -PI/2.0; 1633 } else { 1634 theta2 = atan2(p3y - p2y, p3x - p2x); 1635 } 1636 1637 theta = theta1 - theta2; 1638 if (theta > PI) { 1639 theta -= 2*PI; 1640 } else if (theta < -PI) { 1641 theta += 2*PI; 1642 } 1643 1644 if ((theta < elevenDegrees) && (theta > -elevenDegrees)) { 1645 return 0; 1646 } 1647 1648 dist = 0.5*width/sin(0.5*theta); 1649 if (dist < 0.0) { 1650 dist = -dist; 1651 } 1652 1653 /* 1654 * Compute theta3 (make sure that it points to the left when looking from 1655 * p1 to p2). 1656 */ 1657 1658 theta3 = (theta1 + theta2)/2.0; 1659 if (sin(theta3 - (theta1 + PI)) < 0.0) { 1660 theta3 += PI; 1661 } 1662 deltaX = dist*cos(theta3); 1663 m1[0] = p2x + deltaX; 1664 m2[0] = p2x - deltaX; 1665 deltaY = dist*sin(theta3); 1666 m1[1] = p2y + deltaY; 1667 m2[1] = p2y - deltaY; 1668 1669 return 1; 1670} 1671 1672/* 1673 *-------------------------------------------------------------- 1674 * 1675 * TkGetButtPoints -- 1676 * 1677 * Given two points forming a line segment, compute the coordinates of 1678 * two endpoints of a rectangle formed by bloating the line segment until 1679 * it is width units wide. 1680 * 1681 * Results: 1682 * There is no return value. M1 and m2 are filled in to correspond to m1 1683 * and m2 in the diagram below: 1684 * 1685 * ----------------* m1 1686 * | 1687 * p1 *---------------* p2 1688 * | 1689 * ----------------* m2 1690 * 1691 * M1 and m2 will be W units apart, with p2 centered between them and 1692 * m1-m2 perpendicular to p1-p2. However, if "project" is true then m1 1693 * and m2 will be as follows: 1694 * 1695 * -------------------* m1 1696 * p2 | 1697 * p1 *---------------* | 1698 * | 1699 * -------------------* m2 1700 * 1701 * In this case p2 will be width/2 units from the segment m1-m2. 1702 * 1703 * Side effects: 1704 * None. 1705 * 1706 *-------------------------------------------------------------- 1707 */ 1708 1709void 1710TkGetButtPoints( 1711 double p1[], /* Points to x- and y-coordinates of point 1712 * before vertex. */ 1713 double p2[], /* Points to x- and y-coordinates of vertex 1714 * for mitered joint. */ 1715 double width, /* Width of line. */ 1716 int project, /* Non-zero means project p2 by an additional 1717 * width/2 before computing m1 and m2. */ 1718 double m1[], /* Points to place to put "left" result point, 1719 * as you face from p1 to p2. */ 1720 double m2[]) /* Points to place to put "right" result 1721 * point. */ 1722{ 1723 double length; /* Length of p1-p2 segment. */ 1724 double deltaX, deltaY; /* Increments in coords. */ 1725 1726 width *= 0.5; 1727 length = hypot(p2[0] - p1[0], p2[1] - p1[1]); 1728 if (length == 0.0) { 1729 m1[0] = m2[0] = p2[0]; 1730 m1[1] = m2[1] = p2[1]; 1731 } else { 1732 deltaX = -width * (p2[1] - p1[1]) / length; 1733 deltaY = width * (p2[0] - p1[0]) / length; 1734 m1[0] = p2[0] + deltaX; 1735 m2[0] = p2[0] - deltaX; 1736 m1[1] = p2[1] + deltaY; 1737 m2[1] = p2[1] - deltaY; 1738 if (project) { 1739 m1[0] += deltaY; 1740 m2[0] += deltaY; 1741 m1[1] -= deltaX; 1742 m2[1] -= deltaX; 1743 } 1744 } 1745} 1746 1747/* 1748 * Local Variables: 1749 * mode: c 1750 * c-basic-offset: 4 1751 * fill-column: 78 1752 * End: 1753 */ 1754