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