contrib/groff/src/libs/libgroff/geometry.cc

   1 // -*- C++ -*-
   2 /* Copyright (C) 1989, 1990, 1991, 1992, 2000, 2001, 2002
   3    Free Software Foundation, Inc.
   4      Written by Gaius Mulley <gaius@glam.ac.uk>
   5      using adjust_arc_center() from printer.cc, written by James Clark.
   6
   7 This file is part of groff.
   8
   9 groff is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 2, or (at your option) any later
  12 version.
  13
  14 groff is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License along
  20 with groff; see the file COPYING.  If not, write to the Free Software
  21 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  22
  23
  24 #include <stdio.h>
  25 #include <math.h>
  26
  27 #undef  MAX
  28 #define MAX(a, b)  (((a) > (b)) ? (a) : (b))
  29
  30 #undef  MIN
  31 #define MIN(a, b)  (((a) < (b)) ? (a) : (b))
  32
  33
  34 // This utility function adjusts the specified center of the
  35 // arc so that it is equidistant between the specified start
  36 // and end points.  (p[0], p[1]) is a vector from the current
  37 // point to the center; (p[2], p[3]) is a vector from the
  38 // center to the end point.  If the center can be adjusted,
  39 // a vector from the current point to the adjusted center is
  40 // stored in c[0], c[1] and 1 is returned.  Otherwise 0 is
  41 // returned.
  42
  43 #if 1
  44 int adjust_arc_center(const int *p, double *c)
  45 {
  46   // We move the center along a line parallel to the line between
  47   // the specified start point and end point so that the center
  48   // is equidistant between the start and end point.
  49   // It can be proved (using Lagrange multipliers) that this will
  50   // give the point nearest to the specified center that is equidistant
  51   // between the start and end point.
  52
  53   double x = p[0] + p[2];       // (x, y) is the end point
  54   double y = p[1] + p[3];
  55   double n = x*x + y*y;
  56   if (n != 0) {
  57     c[0]= double(p[0]);
  58     c[1] = double(p[1]);
  59     double k = .5 - (c[0]*x + c[1]*y)/n;
  60     c[0] += k*x;
  61     c[1] += k*y;
  62     return 1;
  63   }
  64   else
  65     return 0;
  66 }
  67 #else
  68 int printer::adjust_arc_center(const int *p, double *c)
  69 {
  70   int x = p[0] + p[2];  // (x, y) is the end point
  71   int y = p[1] + p[3];
  72   // Start at the current point; go in the direction of the specified
  73   // center point until we reach a point that is equidistant between
  74   // the specified starting point and the specified end point.  Place
  75   // the center of the arc there.
  76   double n = p[0]*double(x) + p[1]*double(y);
  77   if (n > 0) {
  78     double k = (double(x)*x + double(y)*y)/(2.0*n);
  79     // (cx, cy) is our chosen center
  80     c[0] = k*p[0];
  81     c[1] = k*p[1];
  82     return 1;
  83   }
  84   else {
  85     // We would never reach such a point.  So instead start at the
  86     // specified end point of the arc.  Go towards the specified
  87     // center point until we reach a point that is equidistant between
  88     // the specified start point and specified end point.  Place
  89     // the center of the arc there.
  90     n = p[2]*double(x) + p[3]*double(y);
  91     if (n > 0) {
  92       double k = 1 - (double(x)*x + double(y)*y)/(2.0*n);
  93       // (c[0], c[1]) is our chosen center
  94       c[0] = p[0] + k*p[2];
  95       c[1] = p[1] + k*p[3];
  96       return 1;
  97     }
  98     else
  99       return 0;
 100   }
 101 }
 102 #endif
 103
 104
 105 /*
 106  *  check_output_arc_limits - works out the smallest box that will encompass
 107  *                            an arc defined by an origin (x, y) and two
 108  *                            vectors (p0, p1) and (p2, p3).
 109  *                            (x1, y1) -> start of arc
 110  *                            (x1, y1) + (xv1, yv1) -> center of circle
 111  *                            (x1, y1) + (xv1, yv1) + (xv2, yv2) -> end of arc
 112  *
 113  *                            Works out in which quadrant the arc starts and
 114  *                            stops, and from this it determines the x, y
 115  *                            max/min limits.  The arc is drawn clockwise.
 116  *
 117  *                            [I'm sure there is a better way to do this, but
 118  *                             I don't know how.  Please can someone let me
 119  *                             know or "improve" this function.]
 120  */
 121
 122 void check_output_arc_limits(int x1, int y1,
 123                              int xv1, int yv1,
 124                              int xv2, int yv2,
 125                              double c0, double c1,
 126                              int *minx, int *maxx,
 127                              int *miny, int *maxy)
 128 {
 129   int radius = (int)sqrt(c0*c0 + c1*c1);
 130   int x2 = x1 + xv1 + xv2;                      // end of arc is (x2, y2)
 131   int y2 = y1 + yv1 + yv2;
 132
 133   // firstly lets use the `circle' limitation
 134   *minx = x1 + xv1 - radius;
 135   *maxx = x1 + xv1 + radius;
 136   *miny = y1 + yv1 - radius;
 137   *maxy = y1 + yv1 + radius;
 138
 139   /*  now to see which min/max can be reduced and increased for the limits of
 140    *  the arc
 141    *
 142    *       Q2   |   Q1
 143    *       -----+-----
 144    *       Q3   |   Q4
 145    *
 146    *
 147    *  NB. (x1+xv1, y1+yv1) is at the origin
 148    *
 149    *  below we ask a nested question
 150    *  (i)  from which quadrant does the first vector start?
 151    *  (ii) into which quadrant does the second vector go?
 152    *  from the 16 possible answers we determine the limits of the arc
 153    */
 154   if (xv1 > 0 && yv1 > 0) {
 155     // first vector in Q3
 156     if (xv2 >= 0 && yv2 >= 0 ) {
 157       // second in Q1
 158       *maxx = x2;
 159       *miny = y1;
 160     }
 161     else if (xv2 < 0 && yv2 >= 0) {
 162       // second in Q2
 163       *maxx = x2;
 164       *miny = y1;
 165     }
 166     else if (xv2 >= 0 && yv2 < 0) {
 167       // second in Q4
 168       *miny = MIN(y1, y2);
 169     }
 170     else if (xv2 < 0 && yv2 < 0) {
 171       // second in Q3
 172       if (x1 >= x2) {
 173         *minx = x2;
 174         *maxx = x1;
 175         *miny = MIN(y1, y2);
 176         *maxy = MAX(y1, y2);
 177       }
 178       else {
 179         // xv2, yv2 could all be zero?
 180       }
 181     }
 182   }
 183   else if (xv1 > 0 && yv1 < 0) {
 184     // first vector in Q2
 185     if (xv2 >= 0 && yv2 >= 0) {
 186       // second in Q1
 187       *maxx = MAX(x1, x2);
 188       *minx = MIN(x1, x2);
 189       *miny = y1;
 190     }
 191     else if (xv2 < 0 && yv2 >= 0) {
 192       // second in Q2
 193       if (x1 < x2) {
 194         *maxx = x2;
 195         *minx = x1;
 196         *miny = MIN(y1, y2);
 197         *maxy = MAX(y1, y2);
 198       }
 199       else {
 200         // otherwise almost full circle anyway
 201       }
 202     }
 203     else if (xv2 >= 0 && yv2 < 0) {
 204       // second in Q4
 205       *miny = y2;
 206       *minx = x1;
 207     }
 208     else if (xv2 < 0 && yv2 < 0) {
 209       // second in Q3
 210       *minx = MIN(x1, x2);
 211     }
 212   }
 213   else if (xv1 <= 0 && yv1 <= 0) {
 214     // first vector in Q1
 215     if (xv2 >= 0 && yv2 >= 0) {
 216       // second in Q1
 217       if (x1 < x2) {
 218         *minx = x1;
 219         *maxx = x2;
 220         *miny = MIN(y1, y2);
 221         *maxy = MAX(y1, y2);
 222       }
 223       else {
 224         // nearly full circle
 225       }
 226     }
 227     else if (xv2 < 0 && yv2 >= 0) {
 228       // second in Q2
 229       *maxy = MAX(y1, y2);
 230     }
 231     else if (xv2 >= 0 && yv2 < 0) {
 232       // second in Q4
 233       *miny = MIN(y1, y2);
 234       *maxy = MAX(y1, y2);
 235       *minx = MIN(x1, x2);
 236     }
 237     else if (xv2 < 0 && yv2 < 0) {
 238       // second in Q3
 239       *minx = x2;
 240       *maxy = y1;
 241     }
 242   }
 243   else if (xv1 <= 0 && yv1 > 0) {
 244     // first vector in Q4
 245     if (xv2 >= 0 && yv2 >= 0) {
 246       // second in Q1
 247       *maxx = MAX(x1, x2);
 248     }
 249     else if (xv2 < 0 && yv2 >= 0) {
 250       // second in Q2
 251       *maxy = MAX(y1, y2);
 252       *maxx = MAX(x1, x2);
 253     }
 254     else if (xv2 >= 0 && yv2 < 0) {
 255       // second in Q4
 256       if (x1 >= x2) {
 257         *miny = MIN(y1, y2);
 258         *maxy = MAX(y1, y2);
 259         *minx = MIN(x1, x2);
 260         *maxx = MAX(x2, x2);
 261       }
 262       else {
 263         // nearly full circle
 264       }
 265     }
 266     else if (xv2 < 0 && yv2 < 0) {
 267       // second in Q3
 268       *maxy = MAX(y1, y2);
 269       *minx = MIN(x1, x2);
 270       *maxx = MAX(x1, x2);
 271     }
 272   }
 273
 274   // this should *never* happen but if it does it means a case above is wrong
 275   // this code is only present for safety sake
 276   if (*maxx < *minx) {
 277     fprintf(stderr, "assert failed *minx > *maxx\n");
 278     fflush(stderr);
 279     *maxx = *minx;
 280   }
 281   if (*maxy < *miny) {
 282     fprintf(stderr, "assert failed *miny > *maxy\n");
 283     fflush(stderr);
 284     *maxy = *miny;
 285   }
 286 }