lib/geometry.c

   1 /* Dia -- an diagram creation/manipulation program
   2  * Copyright (C) 1998 Alexander Larsson
   3  *
   4  * Matrix code from GIMP:app/transform_tool.c
   5  * Copyright (C) 1995 Spencer Kimball and Peter Mattis
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20  */
  21
  22 /* include glib.h first, so we don't pick up its inline functions as well */
  23 #include <config.h>
  24
  25 #include <glib.h>
  26 /* include normal versions of the inlined functions here ... */
  27 #undef G_INLINE_FUNC
  28 #define G_INLINE_FUNC extern
  29 #define G_CAN_INLINE 1
  30 #include "geometry.h"
  31 #include "object.h"
  32
  33 void
  34 rectangle_union(Rectangle *r1, const Rectangle *r2)
  35 {
  36   r1->top = MIN( r1->top, r2->top );
  37   r1->bottom = MAX( r1->bottom, r2->bottom );
  38   r1->left = MIN( r1->left, r2->left );
  39   r1->right = MAX( r1->right, r2->right );
  40 }
  41
  42 void
  43 int_rectangle_union(IntRectangle *r1, const IntRectangle *r2)
  44 {
  45   r1->top = MIN( r1->top, r2->top );
  46   r1->bottom = MAX( r1->bottom, r2->bottom );
  47   r1->left = MIN( r1->left, r2->left );
  48   r1->right = MAX( r1->right, r2->right );
  49 }
  50
  51 void
  52 rectangle_intersection(Rectangle *r1, const Rectangle *r2)
  53 {
  54   r1->top = MAX( r1->top, r2->top );
  55   r1->bottom = MIN( r1->bottom, r2->bottom );
  56   r1->left = MAX( r1->left, r2->left );
  57   r1->right = MIN( r1->right, r2->right );
  58
  59   /* Is rectangle empty? */
  60   if ( (r1->top >= r1->bottom) ||
  61        (r1->left >= r1->right) ) {
  62     r1->top = r1->bottom = r1->left = r1->right = 0.0;
  63   }
  64 }
  65
  66 int
  67 rectangle_intersects(const Rectangle *r1, const Rectangle *r2)
  68 {
  69   if ( (r1->right < r2->left) ||
  70        (r1->left > r2->right) ||
  71        (r1->top > r2->bottom) ||
  72        (r1->bottom < r2->top) )
  73     return FALSE;
  74
  75   return TRUE;
  76 }
  77
  78 int
  79 point_in_rectangle(const Rectangle* r, const Point *p)
  80 {
  81   if ( (p->x < r->left) ||
  82        (p->x > r->right) ||
  83        (p->y > r->bottom) ||
  84        (p->y < r->top) )
  85     return FALSE;
  86
  87   return TRUE;
  88 }
  89
  90 int
  91 rectangle_in_rectangle(const Rectangle* outer, const Rectangle *inner)
  92 {
  93   if ( (inner->left < outer->left) ||
  94        (inner->right > outer->right) ||
  95        (inner->top < outer->top) ||
  96        (inner->bottom > outer->bottom))
  97     return FALSE;
  98
  99   return TRUE;
 100 }
 101
 102 void
 103 rectangle_add_point(Rectangle *r, const Point *p)
 104 {
 105   if (p->x < r->left)
 106     r->left = p->x;
 107   else if (p->x > r->right)
 108     r->right = p->x;
 109
 110   if (p->y < r->top)
 111     r->top = p->y;
 112   else if (p->y > r->bottom)
 113     r->bottom = p->y;
 114 }
 115
 116
 117 /*
 118  * This function estimates the distance from a point to a rectangle.
 119  * If the point is in the rectangle, 0.0 is returned. Otherwise the
 120  * distance in a manhattan metric from the point to the nearest point
 121  * on the rectangle is returned.
 122  */
 123 real
 124 distance_rectangle_point(const Rectangle *rect, const Point *point)
 125 {
 126   real dx = 0.0;
 127   real dy = 0.0;
 128
 129   if (point->x < rect->left ) {
 130     dx = rect->left - point->x;
 131   } else if (point->x > rect->right ) {
 132     dx = point->x - rect->right;
 133   }
 134
 135   if (point->y < rect->top ) {
 136     dy = rect->top - point->y;
 137   } else if (point->y > rect->bottom ) {
 138     dy = point->y - rect->bottom;
 139   }
 140
 141   return dx + dy;
 142 }
 143
 144 /*
 145  * This function estimates the distance from a point to a line segment
 146  * specified by two endpoints.
 147  * If the point is on the line segment, 0.0 is returned. Otherwise the
 148  * distance in the R^2 metric from the point to the nearest point
 149  * on the line segment is returned. Does one sqrt per call.
 150  * Philosophical bug: line_width is ignored iff point is beyond
 151  * end of line segment.
 152  */
 153 real
 154 distance_line_point(const Point *line_start, const Point *line_end,
 155                     real line_width, const Point *point)
 156 {
 157   Point v1, v2;
 158   real v1_lensq;
 159   real projlen;
 160   real perp_dist;
 161
 162   v1 = *line_end;
 163   point_sub(&v1,line_start);
 164
 165   v2 = *point;
 166   point_sub(&v2, line_start);
 167
 168   v1_lensq = point_dot(&v1,&v1);
 169
 170   if (v1_lensq<0.000001) {
 171     return sqrt(point_dot(&v2,&v2));
 172   }
 173
 174   projlen = point_dot(&v1,&v2) / v1_lensq;
 175
 176   if (projlen<0.0) {
 177     return sqrt(point_dot(&v2,&v2));
 178   }
 179
 180   if (projlen>1.0) {
 181     Point v3 = *point;
 182     point_sub(&v3,line_end);
 183     return sqrt(point_dot(&v3,&v3));
 184   }
 185
 186   point_scale(&v1, projlen);
 187   point_sub(&v1, &v2);
 188
 189   perp_dist = sqrt(point_dot(&v1,&v1));
 190
 191   perp_dist -= line_width / 2.0;
 192   if (perp_dist < 0.0) {
 193     perp_dist = 0.0;
 194   }
 195
 196   return perp_dist;
 197 }
 198
 199 /* returns 1 iff the line crosses the ray from (-Inf, rayend.y) to rayend */
 200 static guint
 201 line_crosses_ray(const Point *line_start,
 202                  const Point *line_end, const Point *rayend)
 203 {
 204   coord xpos;
 205
 206   /* swap end points if necessary */
 207   if (line_start->y > line_end->y) {
 208     const Point *tmp;
 209
 210     tmp = line_start;
 211     line_start = line_end;
 212     line_end = tmp;
 213   }
 214   /* if y coords of line do not include rayend.y */
 215   if (line_start->y > rayend->y || line_end->y < rayend->y)
 216     return 0;
 217   /* Avoid division by zero for horizontal case */
 218   if (line_end->y - line_start->y < 0.00000000001) {
 219     return (line_end->y - rayend->y < 0.00000000001);
 220   }
 221   xpos = line_start->x + (rayend->y - line_start->y) *
 222     (line_end->x - line_start->x) / (line_end->y - line_start->y);
 223   return xpos <= rayend->x;
 224 }
 225
 226 real
 227 distance_polygon_point(const Point *poly, guint npoints, real line_width,
 228                        const Point *point)
 229 {
 230   guint i, last = npoints - 1;
 231   real line_dist = G_MAXFLOAT;
 232   guint crossings = 0;
 233
 234   /* calculate ray crossings and line distances */
 235   for (i = 0; i < npoints; i++) {
 236     real dist;
 237
 238     crossings += line_crosses_ray(&poly[last], &poly[i], point);
 239     dist = distance_line_point(&poly[last], &poly[i], line_width, point);
 240     line_dist = MIN(line_dist, dist);
 241     last = i;
 242   }
 243   /* If there is an odd number of ray crossings, we are inside the polygon.
 244    * Otherwise, return the minium distance from a line segment */
 245   if (crossings % 2 == 1)
 246     return 0.0;
 247   else
 248     return line_dist;
 249 }
 250
 251 /* number of segments to use in bezier curve approximation */
 252 #define NBEZ_SEGS 10
 253
 254 /* if cross is not NULL, it will be incremented for each ray crossing */
 255 static real
 256 bez_point_distance_and_ray_crosses(const Point *b1,
 257                                    const Point *b2, const Point *b3,
 258                                    const Point *b4,
 259                                    real line_width, const Point *point,
 260                                    guint *cross)
 261 {
 262   static gboolean calculated_coeff = FALSE;
 263   static real coeff[NBEZ_SEGS+1][4];
 264   int i;
 265   real line_dist = G_MAXFLOAT;
 266   Point prev, pt;
 267
 268   if (!calculated_coeff) {
 269     for (i = 0; i <= NBEZ_SEGS; i++) {
 270       real t1 = ((real)i)/NBEZ_SEGS, t2 = t1*t1, t3 = t1*t2;
 271       real it1 = 1-t1, it2 = it1*it1, it3 = it1*it2;
 272
 273       coeff[i][0] = it3;
 274       coeff[i][1] = 3 * t1 * it2;
 275       coeff[i][2] = 3 * t2 * it1;
 276       coeff[i][3] = t3;
 277     }
 278   }
 279   calculated_coeff = TRUE;
 280
 281   prev.x = coeff[0][0] * b1->x + coeff[0][1] * b2->x +
 282            coeff[0][2] * b3->x + coeff[0][3] * b4->x;
 283   prev.y = coeff[0][0] * b1->y + coeff[0][1] * b2->y +
 284            coeff[0][2] * b3->y + coeff[0][3] * b4->y;
 285   for (i = 1; i <= NBEZ_SEGS; i++) {
 286     real dist;
 287
 288     pt.x = coeff[i][0] * b1->x + coeff[i][1] * b2->x +
 289            coeff[i][2] * b3->x + coeff[i][3] * b4->x;
 290     pt.y = coeff[i][0] * b1->y + coeff[i][1] * b2->y +
 291            coeff[i][2] * b3->y + coeff[i][3] * b4->y;
 292
 293     dist = distance_line_point(&prev, &pt, line_width, point);
 294     line_dist = MIN(line_dist, dist);
 295     if (cross)
 296       *cross += line_crosses_ray(&prev, &pt, point);
 297
 298     prev = pt;
 299   }
 300   return line_dist;
 301 }
 302
 303 real
 304 distance_bez_seg_point(const Point *b1, const Point *b2,
 305                        const Point *b3, const Point *b4,
 306                        real line_width, const Point *point)
 307 {
 308   return bez_point_distance_and_ray_crosses(b1, b2, b3, b4,
 309                                             line_width, point, NULL);
 310 }
 311
 312 real
 313 distance_bez_line_point(const BezPoint *b, guint npoints,
 314                         real line_width, const Point *point)
 315 {
 316   Point last;
 317   guint i;
 318   real line_dist = G_MAXFLOAT;
 319
 320   g_return_val_if_fail(b[0].type == BEZ_MOVE_TO, -1);
 321
 322   last = b[0].p1;
 323
 324   for (i = 1; i < npoints; i++) {
 325     real dist;
 326
 327     switch (b[i].type) {
 328     case BEZ_MOVE_TO:
 329       /*g_assert_not_reached();*/
 330       g_warning("BEZ_MOVE_TO found half way through a bezier line");
 331       break;
 332     case BEZ_LINE_TO:
 333       dist = distance_line_point(&last, &b[i].p1, line_width, point);
 334       line_dist = MIN(line_dist, dist);
 335       last = b[i].p1;
 336       break;
 337     case BEZ_CURVE_TO:
 338       dist = bez_point_distance_and_ray_crosses(&last, &b[i].p1, &b[i].p2,
 339                                                 &b[i].p3, line_width, point,
 340                                                 NULL);
 341       line_dist = MIN(line_dist, dist);
 342       last = b[i].p3;
 343       break;
 344     }
 345   }
 346   return line_dist;
 347 }
 348
 349 real
 350 distance_bez_shape_point(const BezPoint *b, guint npoints,
 351                          real line_width, const Point *point)
 352 {
 353   Point last;
 354   guint i;
 355   real line_dist = G_MAXFLOAT;
 356   guint crossings = 0;
 357
 358   g_return_val_if_fail(b[0].type == BEZ_MOVE_TO, -1);
 359
 360   last = b[0].p1;
 361
 362   for (i = 1; i < npoints; i++) {
 363     real dist;
 364
 365     switch (b[i].type) {
 366     case BEZ_MOVE_TO:
 367       /*g_assert_not_reached();*/
 368       g_warning("BEZ_MOVE_TO found half way through a bezier shape");
 369       break;
 370     case BEZ_LINE_TO:
 371       dist = distance_line_point(&last, &b[i].p1, line_width, point);
 372       crossings += line_crosses_ray(&last, &b[i].p1, point);
 373       line_dist = MIN(line_dist, dist);
 374       last = b[i].p1;
 375       break;
 376     case BEZ_CURVE_TO:
 377       dist = bez_point_distance_and_ray_crosses(&last, &b[i].p1, &b[i].p2,
 378                                                 &b[i].p3, line_width, point,
 379                                                 &crossings);
 380       line_dist = MIN(line_dist, dist);
 381       last = b[i].p3;
 382       break;
 383     }
 384   }
 385   /* If there is an odd number of ray crossings, we are inside the polygon.
 386    * Otherwise, return the minium distance from a line segment */
 387   if (crossings % 2 == 1)
 388     return 0.0;
 389   else
 390     return line_dist;
 391 }
 392
 393 real
 394 distance_ellipse_point(const Point *centre, real width, real height,
 395                        real line_width, const Point *point)
 396 {
 397   /* A faster intersection method would be to scaled the ellipse and the
 398    * point to where the ellipse is a circle, intersect with the circle,
 399    * then scale back.
 400    */
 401   real w2 = width*width, h2 = height*height;
 402   real scale, rad, dist;
 403   Point pt;
 404
 405   /* find the radius of the ellipse in the appropriate direction */
 406
 407   /* find the point of intersection between line (x=cx+(px-cx)t; y=cy+(py-cy)t)
 408    * and ellipse ((x-cx)^2)/(w/2)^2 + ((y-cy)^2)/(h/2)^2 = 1 */
 409   /* radius along ray is sqrt((px-cx)^2 * t^2 + (py-cy)^2 * t^2) */
 410
 411   pt = *point;
 412   point_sub(&pt, centre);
 413   pt.x *= pt.x;
 414   pt.y *= pt.y;  /* pt = (point - centre).^2 */
 415
 416   scale = w2 * h2 / (4*h2*pt.x + 4*w2*pt.y);
 417   rad = sqrt((pt.x + pt.y)*scale) + line_width/2;
 418
 419   dist = sqrt(pt.x + pt.y);
 420
 421   if (dist <= rad)
 422     return 0.0;
 423   else
 424     return dist - rad;
 425 }
 426
 427
 428 void
 429 transform_point (Matrix m, Point *src, Point *dest)
 430 {
 431   real xx, yy, ww;
 432
 433   xx = m[0][0] * src->x + m[0][1] * src->y + m[0][2];
 434   yy = m[1][0] * src->x + m[1][1] * src->y + m[1][2];
 435   ww = m[2][0] * src->x + m[2][1] * src->y + m[2][2];
 436
 437   if (!ww)
 438     ww = 1.0;
 439
 440   dest->x = xx / ww;
 441   dest->y = yy / ww;
 442 }
 443
 444 void
 445 mult_matrix (Matrix m1, Matrix m2)
 446 {
 447   Matrix result;
 448   int i, j, k;
 449
 450   for (i = 0; i < 3; i++)
 451     for (j = 0; j < 3; j++)
 452       {
 453         result [i][j] = 0.0;
 454         for (k = 0; k < 3; k++)
 455           result [i][j] += m1 [i][k] * m2[k][j];
 456       }
 457
 458   /*  copy the result into matrix 2  */
 459   for (i = 0; i < 3; i++)
 460     for (j = 0; j < 3; j++)
 461       m2 [i][j] = result [i][j];
 462 }
 463
 464 void
 465 identity_matrix (Matrix m)
 466 {
 467   int i, j;
 468
 469   for (i = 0; i < 3; i++)
 470     for (j = 0; j < 3; j++)
 471       m[i][j] = (i == j) ? 1 : 0;
 472
 473 }
 474
 475 void
 476 translate_matrix (Matrix m, real x, real y)
 477 {
 478   Matrix trans;
 479
 480   identity_matrix (trans);
 481   trans[0][2] = x;
 482   trans[1][2] = y;
 483   mult_matrix (trans, m);
 484 }
 485
 486 void
 487 scale_matrix (Matrix m, real x, real y)
 488 {
 489   Matrix scale;
 490
 491   identity_matrix (scale);
 492   scale[0][0] = x;
 493   scale[1][1] = y;
 494   mult_matrix (scale, m);
 495 }
 496
 497 void
 498 rotate_matrix (Matrix m, real theta)
 499 {
 500   Matrix rotate;
 501   real cos_theta, sin_theta;
 502
 503   cos_theta = cos (theta);
 504   sin_theta = sin (theta);
 505
 506   identity_matrix (rotate);
 507   rotate[0][0] = cos_theta;
 508   rotate[0][1] = -sin_theta;
 509   rotate[1][0] = sin_theta;
 510   rotate[1][1] = cos_theta;
 511   mult_matrix (rotate, m);
 512 }
 513
 514 void
 515 xshear_matrix (Matrix m, real shear)
 516 {
 517   Matrix shear_m;
 518
 519   identity_matrix (shear_m);
 520   shear_m[0][1] = shear;
 521   mult_matrix (shear_m, m);
 522 }
 523
 524 void
 525 yshear_matrix (Matrix m, real shear)
 526 {
 527   Matrix shear_m;
 528
 529   identity_matrix (shear_m);
 530   shear_m[1][0] = shear;
 531   mult_matrix (shear_m, m);
 532 }
 533
 534 /*  find the determinate for a 3x3 matrix  */
 535 static real
 536 determinate (Matrix m)
 537 {
 538   int i;
 539   double det = 0;
 540
 541   for (i = 0; i < 3; i ++)
 542     {
 543       det += m[0][i] * m[1][(i+1)%3] * m[2][(i+2)%3];
 544       det -= m[2][i] * m[1][(i+1)%3] * m[0][(i+2)%3];
 545     }
 546
 547   return det;
 548 }
 549
 550
 551
 552 void
 553 point_convex(Point *dst, const Point *src1, const Point *src2, real alpha)
 554 {
 555   /* Make convex combination of src1 and src2:
 556      dst = alpha * src1 + (1-alpha) * src2;
 557   */
 558   point_copy(dst,src1);
 559   point_scale(dst,alpha);
 560   point_add_scaled(dst,src2,1.0 - alpha);
 561 }
 562
 563
 564
 565 /* The following functions were originally taken from Graphics Gems III,
 566    pg 193 and corresponding code pgs 496-499
 567
 568    They were modified to work within the dia coordinate system
 569  */
 570 /* return angle subtended by two vectors */
 571 real dot2(Point *p1, Point *p2)
 572 {
 573   real d, t;
 574   d = sqrt(((p1->x*p1->x)+(p1->y*p1->y)) *
 575            ((p2->x*p2->x)+(p2->y*p2->y)));
 576   if ( d != 0.0 )
 577   {
 578     t = (p1->x*p2->x+p1->y*p2->y)/d;
 579     return (acos(t));
 580   }
 581   else
 582   {
 583     return 0.0;
 584   }
 585 }
 586
 587 /* Find a,b,c in ax + by + c = 0 for line p1, p2 */
 588 void line_coef(real *a, real *b, real *c, Point *p1, Point *p2)
 589 {
 590   *c = ( p2->x * p1->y ) - ( p1->x * p2->y );
 591   *a = p2->y - p1->y;
 592   *b = p1->x - p2->x;
 593 }
 594
 595 /* Return signed distance from line
 596    ax + by + c = 0 to point p.              */
 597 real line_to_point(real a, real b , real c, Point *p) {
 598   real d, lp;
 599   d = sqrt((a*a)+(b*b));
 600   if ( d == 0.0 ) {
 601     lp = 0.0;
 602   } else {
 603     lp = (a*p->x+b*p->y+c)/d;
 604   }
 605   return (lp);
 606 }
 607
 608 /* Given line l = ax + by + c = 0 and point p,
 609    compute x,y so point perp is perpendicular to line l. */
 610 void point_perp(Point *p, real a, real b, real c, Point *perp) {
 611   real d, cp;
 612   perp->x = 0.0;
 613   perp->y = 0.0;
 614   d = a*a + b*b;
 615   cp = a*p->y-b*p->x;
 616   if ( d != 0.0 ) {
 617     perp->x = (-a*c-b*cp)/d;
 618     perp->y = (a*cp-b*c)/d;
 619   }
 620   return;
 621 }
 622
 623 /* Compute a circular arc fillet between lines L1 (p1 to p2)
 624    and L2 (p3 to p4) with radius r.
 625    The circle center is c.
 626    The start angle is pa
 627    The end angle is aa,
 628    The points p1-p4 will be modified as necessary */
 629 void fillet(Point *p1, Point *p2, Point *p3, Point *p4,
 630                    real r, Point *c, real *pa, real *aa) {
 631   real a1, b1, c1;  /* Coefficients for L1 */
 632   real a2, b2, c2;  /* Coefficients for L2 */
 633   real d, d1, d2;
 634   real c1p, c2p;
 635   real rr;
 636   real start_angle, stop_angle;
 637   Point mp,gv1,gv2;
 638   gboolean righthand = FALSE;
 639
 640   line_coef(&a1,&b1,&c1,p1,p2);
 641   line_coef(&a2,&b2,&c2,p3,p4);
 642
 643   if ( (a1*b2) == (a2*b1) ) /* Parallel or coincident lines */
 644   {
 645     return;
 646   }
 647
 648   mp.x = (p3->x + p4->x) / 2.0;          /* Find midpoint of p3 p4 */
 649   mp.y = (p3->y + p4->y) / 2.0;
 650   d1 = line_to_point(a1, b1, c1, &mp);    /* Find distance p1 p2 to
 651                                              midpoint p3 p4 */
 652   if ( d1 == 0.0 ) return;                /* p1p2 to p3 */
 653
 654   mp.x = (p1->x + p2->x) / 2.0;          /* Find midpoint of p1 p2 */
 655   mp.y = (p1->y + p2->y) / 2.0;
 656   d2 = line_to_point(a2, b2, c2, &mp);    /* Find distance p3 p4 to
 657                                              midpoint p1 p2 */
 658   if ( d2 == 0.0 ) return;
 659
 660   rr = r;
 661   if ( d1 <= 0.0 ) rr = -rr;
 662
 663   c1p = c1-rr*sqrt((a1*a1)+(b1*b1));     /* Line parallell l1 at d */
 664   rr = r;
 665
 666   if ( d2 <= 0.0 ) rr = -rr;
 667   c2p = c2-rr*sqrt((a2*a2)+(b2*b2));     /* Line parallell l2 at d */
 668   d = a1*b2-a2*b1;
 669
 670   c->x = ( c2p*b1-c1p*b2 ) / d;          /* Intersect constructed lines */
 671   c->y = ( c1p*a2-c2p*a1 ) / d;          /* to find center of arc */
 672
 673   point_perp(c,a1,b1,c1,p2);             /* Clip or extend lines as required */
 674   point_perp(c,a2,b2,c2,p3);
 675
 676   /* need to negate the y coords to calculate angles correctly */
 677   gv1.x = p2->x-c->x; gv1.y = -(p2->y-c->y);
 678   gv2.x = p3->x-c->x; gv2.y = -(p3->y-c->y);
 679
 680   start_angle = atan2(gv1.y,gv1.x);   /* Beginning angle for arc */
 681   stop_angle = dot2(&gv1,&gv2);
 682   if ( point_cross(&gv1,&gv2) < 0.0 ) {
 683     stop_angle = -stop_angle; /* Angle subtended by arc */
 684     /* also this means we need to swap our angles later on */
 685     righthand = TRUE;
 686   }
 687   /* now calculate the actual angles in a form that the draw arc function
 688      of the renderer can use */
 689   start_angle = start_angle*180.0/G_PI;
 690   stop_angle  = start_angle + stop_angle*180.0/G_PI;
 691   while (start_angle < 0.0) start_angle += 360.0;
 692   while (stop_angle < 0.0)  stop_angle += 360.0;
 693   /* swap the start and stop if we had to negate the cross product */
 694   if ( righthand ) {
 695     real tmp = start_angle;
 696     start_angle = stop_angle;
 697     stop_angle = tmp;
 698   }
 699   *pa = start_angle;
 700   *aa = stop_angle;
 701 }
 702
 703
 704
 705 /* moved this here since it is being reused by rounded polyline code*/
 706 real
 707 point_cross(Point *p1, Point *p2)
 708 {
 709   return p1->x * p2->y - p2->x * p1->y;
 710 }
 711
 712 /* moved this here since it is used by line and bezier */
 713 /* Computes one point between end and objmid which
 714  * touches the edge of the object */
 715 Point
 716 calculate_object_edge(Point *objmid, Point *end, DiaObject *obj)
 717 {
 718 #define MAXITER 25
 719 #ifdef TRACE_DIST
 720   Point trace[MAXITER];
 721   real disttrace[MAXITER];
 722 #endif
 723   Point mid1, mid2, mid3;
 724   real dist;
 725   int i = 0;
 726
 727   mid1 = *objmid;
 728   mid2.x = (objmid->x+end->x)/2;
 729   mid2.y = (objmid->y+end->y)/2;
 730   mid3 = *end;
 731
 732   /* If the other end is inside the object */
 733   dist = obj->ops->distance_from(obj, &mid3);
 734   if (dist < 0.001) return mid1;
 735
 736
 737   do {
 738     dist = obj->ops->distance_from(obj, &mid2);
 739     if (dist < 0.0000001) {
 740       mid1 = mid2;
 741     } else {
 742       mid3 = mid2;
 743     }
 744     mid2.x = (mid1.x + mid3.x)/2;
 745     mid2.y = (mid1.y + mid3.y)/2;
 746 #ifdef TRACE_DIST
 747     trace[i] = mid2;
 748     disttrace[i] = dist;
 749 #endif
 750     i++;
 751   } while (i < MAXITER && (dist < 0.0000001 || dist > 0.001));
 752
 753 #ifdef TRACE_DIST
 754   if (i == MAXITER) {
 755     for (i = 0; i < MAXITER; i++) {
 756       printf("%d: %f, %f: %f\n", i, trace[i].x, trace[i].y, disttrace[i]);
 757     }
 758     printf("i = %d, dist = %f\n", i, dist);
 759   }
 760 #endif
 761
 762   return mid2;
 763 }
 764