cpml/cpml-pair.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2008, Nicola Fontana <ntd at entidi.it>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA  02110-1301, USA.
  18  */
  19
  20
  21 /**
  22  * SECTION:cpmlpair
  23  * @title: CpmlPair
  24  * @short_description: A structure holding a couple of values
  25  *
  26  * The CpmlPair is a generic 2D structure. It can be used to represent points,
  27  * sizes, offsets or whatever have two components.
  28  *
  29  * The name comes from MetaFont.
  30  */
  31
  32 /**
  33  * CpmlPair:
  34  * @x: the x component of the pair
  35  * @y: the y component of the pair
  36  *
  37  * A generic 2D structure.
  38  **/
  39
  40 /**
  41  * CpmlVector:
  42  * @x: the x component of the vector
  43  * @y: the y component of the vector
  44  *
  45  * Another name for #CpmlPair. It is used to clarify when a function expects
  46  * a pair or a vector.
  47  *
  48  * A vector represents a line starting from the origin (0,0) and ending
  49  * to the given coordinates pair. Vectors are useful to define directions
  50  * and length at once.
  51  **/
  52
  53 #include "cpml-pair.h"
  54 #include "cpml-macros.h"
  55
  56 #include <stdlib.h>
  57 #include <string.h>
  58
  59
  60 static CpmlPair fallback_pair = { 0, 0 };
  61
  62
  63 CpmlPair *
  64 cpml_pair_copy(CpmlPair *pair, const CpmlPair *src)
  65 {
  66     return memcpy(pair, src, sizeof(CpmlPair));
  67 }
  68
  69 CpmlPair *
  70 cpml_pair_from_value(CpmlPair *pair, double value)
  71 {
  72     pair->x = value;
  73     pair->y = value;
  74
  75     return pair;
  76 }
  77
  78 void
  79 cpml_pair_negate(CpmlPair *pair)
  80 {
  81     pair->x = - pair->x;
  82     pair->y = - pair->y;
  83 }
  84
  85 cairo_bool_t
  86 cpml_pair_invert(CpmlPair *pair)
  87 {
  88     if (pair->x == 0 || pair->y == 0)
  89         return 0;
  90
  91     pair->x = 1. / pair->x;
  92     pair->y = 1. / pair->y;
  93     return 1;
  94 }
  95
  96 void
  97 cpml_pair_add(CpmlPair *pair, const CpmlPair *src)
  98 {
  99     pair->x += src->x;
 100     pair->y += src->y;
 101 }
 102
 103 void
 104 cpml_pair_sub(CpmlPair *pair, const CpmlPair *src)
 105 {
 106     pair->x -= src->x;
 107     pair->y -= src->y;
 108 }
 109
 110 void
 111 cpml_pair_mul(CpmlPair *pair, const CpmlPair *src)
 112 {
 113     pair->x *= src->x;
 114     pair->y *= src->y;
 115 }
 116
 117 cairo_bool_t
 118 cpml_pair_div(CpmlPair *pair, const CpmlPair *src)
 119 {
 120     if (src->x == 0 || src->y == 0)
 121         return 0;
 122
 123     pair->x /= src->x;
 124     pair->y /= src->y;
 125     return 1;
 126 }
 127
 128 /**
 129  * cpml_pair_transform:
 130  * @pair: the destination #CpmlPair struct
 131  * @matrix: the transformation matrix
 132  *
 133  * Shortcut to apply a specific transformation matrix to @pair.
 134  **/
 135 void
 136 cpml_pair_transform(CpmlPair *pair, const cairo_matrix_t *matrix)
 137 {
 138     cairo_matrix_transform_point(matrix, &pair->x, &pair->y);
 139 }
 140
 141
 142 /**
 143  * cpml_pair_squared_distance:
 144  * @from: the first #CpmlPair struct
 145  * @to: the second #CpmlPair struct
 146  *
 147  * Gets the squared distance between @from and @to. This value is useful
 148  * for comparation purpose: if you need to get the real distance, use
 149  * cpml_pair_distance().
 150  *
 151  * @from or @to could be %NULL, in which case the fallback (0, 0) pair
 152  * will be used.
 153  *
 154  * Return value: the squared distance
 155  **/
 156 double
 157 cpml_pair_squared_distance(const CpmlPair *from, const CpmlPair *to)
 158 {
 159     double x, y;
 160
 161     if (from == NULL)
 162         from = &fallback_pair;
 163     if (to == NULL)
 164         to = &fallback_pair;
 165
 166     x = to->x - from->x;
 167     y = to->y - from->y;
 168
 169     return x * x + y * y;
 170 }
 171
 172 /**
 173  * cpml_pair_distance:
 174  * @from: the first #CpmlPair struct
 175  * @to: the second #CpmlPair struct
 176  * @distance: where to store the result
 177  *
 178  * Gets the distance between @from and @to, storing the result in @distance.
 179  * If you need this value only for comparation purpose, you could use
 180  * cpm_pair_squared_distance() instead.
 181  *
 182  * @from or @to could be %NULL, in which case the fallback (0, 0) pair
 183  * will be used.
 184  *
 185  * The algorithm used is adapted from:
 186  * "Replacing Square Roots by Pythagorean Sums"
 187  * by Clave Moler and Donald Morrison (1983)
 188  * IBM Journal of Research and Development 27 (6): 577–581
 189  * http://www.research.ibm.com/journal/rd/276/ibmrd2706P.pdf
 190  *
 191  * Return value: the distance
 192  **/
 193 double
 194 cpml_pair_distance(const CpmlPair *from, const CpmlPair *to)
 195 {
 196     double x, y;
 197     double p, q, r, s;
 198
 199     if (from == NULL)
 200         from = &fallback_pair;
 201     if (to == NULL)
 202         to = &fallback_pair;
 203
 204     x = to->x - from->x;
 205     y = to->y - from->y;
 206
 207     if (x < 0)
 208         x = -x;
 209     if (y < 0)
 210         y = -y;
 211
 212     if (x > y) {
 213         p = x;
 214         q = y;
 215     } else {
 216         p = y;
 217         q = x;
 218     }
 219
 220     if (p > 0) {
 221         for (;;) {
 222             r = q/p;
 223             r *= r;
 224             if (r == 0)
 225                 break;
 226
 227             s = r / (4+r);
 228             p += 2*s*p;
 229             q *= s;
 230         }
 231     }
 232
 233     return p;
 234 }
 235
 236 /**
 237  * cpml_vector_from_pair:
 238  * @vector: the destination vector
 239  * @pair: the source pair
 240  * @length: the length of the vector
 241  *
 242  * Given the line L passing throught the origin and @pair, gets the
 243  * coordinate of the point on this line far @length from the origin
 244  * and store the result in @vector. If @pair itsself is the origin,
 245  * (0, 0) is returned.
 246  *
 247  * @pair and @vector can be the same struct.
 248  *
 249  * Return value: @vector
 250  **/
 251 CpmlVector *
 252 cpml_vector_from_pair(CpmlVector *vector, const CpmlPair *pair, double length)
 253 {
 254     double distance = cpml_pair_distance(NULL, pair);
 255
 256     if (distance == 0) {
 257         vector->x = 0;
 258         vector->y = 0;
 259     } else {
 260         distance /= length;
 261         vector->x = pair->x / distance;
 262         vector->y = pair->y / distance;
 263     }
 264
 265     return vector;
 266 }
 267
 268 /**
 269  * cpml_vector_from_angle:
 270  * @vector: the destination #CpmlVector
 271  * @angle: angle of direction, in radians
 272  * @length: the length of the vector
 273  *
 274  * Calculates the coordinates of the point far @length from the origin
 275  * in the @angle direction. The result is stored in @vector.
 276  *
 277  * Return value: @vector
 278  **/
 279 CpmlVector *
 280 cpml_vector_from_angle(CpmlVector *vector, double angle, double length)
 281 {
 282     static double cached_angle = 0;
 283     static CpmlPair cached_vector = { 1, 0 };
 284
 285     /* Check for cached result */
 286     if (angle == cached_angle)
 287         return cpml_pair_copy(vector, &cached_vector);
 288
 289     /* Check for common conditions */
 290     if (angle == CPML_DIR_UP) {
 291         vector->x = 0;
 292         vector->y = -1;
 293         return vector;
 294     }
 295     if (angle == CPML_DIR_DOWN) {
 296         vector->x = 0;
 297         vector->y = +1;
 298         return vector;
 299     }
 300     if (angle == CPML_DIR_LEFT) {
 301         vector->x = -1;
 302         vector->y = 0;
 303         return vector;
 304     }
 305     if (angle == CPML_DIR_RIGHT) {
 306         vector->x = +1;
 307         vector->y = 0;
 308         return vector;
 309     }
 310
 311     /* Computation and cache registration */
 312     vector->x = cos(angle);
 313     vector->y = -sin(angle);
 314     cached_angle = angle;
 315     cpml_pair_copy(&cached_vector, vector);
 316
 317     return vector;
 318 }
 319
 320 /**
 321  * cpml_vector_angle:
 322  * @vector: the source #CpmlVector
 323  *
 324  * Gets the angle of @vector, in radians. If @vector is (0, 0),
 325  * %CPML_DIR_RIGHT is returned.
 326  *
 327  * Return value: the angle in radians
 328  **/
 329 double
 330 cpml_vector_angle(const CpmlVector *vector)
 331 {
 332     static CpmlPair cached_vector = { 1., 0. };
 333     static double cached_angle = 0.;
 334
 335     /* Check for cached result */
 336     if (vector->x == cached_vector.x && vector->y == cached_vector.y)
 337         return cached_angle;
 338
 339     /* Check for common conditions */
 340     if (vector->y == 0)
 341         return vector->x >= 0 ? CPML_DIR_RIGHT : CPML_DIR_LEFT;
 342     if (vector->x == 0)
 343         return vector->y > 0 ? CPML_DIR_DOWN : CPML_DIR_UP;
 344     if (vector->x == vector->y)
 345         return vector->x > 0 ? M_PI_4 * 7 : M_PI_4 * 3;
 346     if (vector->x == -vector->y)
 347         return vector->x > 0 ? M_PI_4 : M_PI_4 * 5;
 348
 349     /* Computation and cache registration */
 350     cached_angle = atan(-vector->y / vector->x);
 351     cpml_pair_copy(&cached_vector, vector);
 352
 353     return cached_angle;
 354 }
 355
 356 /**
 357  * cpml_vector_normal:
 358  * @vector: the subject #CpmlVector
 359  *
 360  * Stores in @vector a vector normal to the original @vector.
 361  * The length is retained.
 362  *
 363  * The algorithm is really quick because no trigonometry is involved.
 364  **/
 365 void
 366 cpml_vector_normal(CpmlVector *vector)
 367 {
 368     double tmp = vector->x;
 369
 370     vector->x = vector->y;
 371     vector->y = tmp;
 372 }