cpml/cpml-pair.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2008, 2009  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 /**
  64  * cpml_pair_copy:
  65  * @pair: the destination #CpmlPair
  66  * @src: the source #CpmlPair
  67  *
  68  * Copies @src in @pair.
  69  *
  70  * Return value: @pair
  71  **/
  72 CpmlPair *
  73 cpml_pair_copy(CpmlPair *pair, const CpmlPair *src)
  74 {
  75     return memcpy(pair, src, sizeof(CpmlPair));
  76 }
  77
  78 /**
  79  * cpml_pair_from_cairo:
  80  * @pair: the destination #CpmlPair
  81  * @path_data: the original path data point
  82  *
  83  * Gets @pair from a #cairo_path_data_t struct. @path_data should contains
  84  * a point data: it is up to the caller to be sure @path_data is valid.
  85  *
  86  * Return value: @pair
  87  **/
  88 CpmlPair *
  89 cpml_pair_from_cairo(CpmlPair *pair, const cairo_path_data_t *path_data)
  90 {
  91     pair->x = path_data->point.x;
  92     pair->y = path_data->point.y;
  93     return pair;
  94 }
  95
  96 /**
  97  * cpml_pair_intersection_pv_pv:
  98  * @pair: the destination #CpmlPair
  99  * @p1: the start point of the first line
 100  * @v1: the director of the first line
 101  * @p2: the start point of the second line
 102  * @v2: the director of the second line
 103  *
 104  * Given two lines (by specifying start point and director), gets
 105  * their intersection point and store it in @pair.
 106  *
 107  * Return value: @pair or %NULL on no intersection
 108  **/
 109 CpmlPair *
 110 cpml_pair_intersection_pv_pv(CpmlPair *pair,
 111                              const CpmlPair *p1, const CpmlVector *v1,
 112                              const CpmlPair *p2, const CpmlVector *v2)
 113 {
 114     double divisor, factor;
 115
 116     divisor = v1->x*v2->y - v1->y*v2->x;
 117     if (divisor == 0)
 118         return NULL;
 119
 120     factor = ((p1->y - p2->y)*v2->x - (p1->x - p2->x)*v2->y) / divisor;
 121
 122     pair->x = p1->x + v1->x * factor;
 123     pair->y = p1->y + v1->y * factor;
 124
 125     return pair;
 126 }
 127
 128 /**
 129  * cpml_pair_at_line:
 130  * @pair: the destination #CpmlPair
 131  * @p1: first point of the line
 132  * @p2: second point of the line
 133  * @t: the mediation value
 134  *
 135  * Given the mediation value @t, where 0 means the start point and
 136  * 1 the end point (0.5 the midpoint and so on), calculates the coordinates
 137  * of the point at @t of the way from @p1 and @p2.
 138  *
 139  * Return value: @pair
 140  **/
 141 CpmlPair *
 142 cpml_pair_at_line(CpmlPair *pair, const CpmlPair *p1, const CpmlPair *p2,
 143                   double t)
 144 {
 145     CpmlPair delta;
 146
 147     delta.x = (p2->x - p1->x) * t;
 148     delta.y = (p2->y - p1->y) * t;
 149
 150     cpml_pair_add(cpml_pair_copy(pair, p1), &delta);
 151
 152     return pair;
 153 }
 154
 155 /**
 156  * cpml_pair_at_curve:
 157  * @pair: the destination #CpmlPair
 158  * @p1: start point
 159  * @p2: first control point
 160  * @p3: second control point
 161  * @p4: end point
 162  * @t: the mediation value
 163  *
 164  * Given the time value @t, returns the point on the specified Bézier curve
 165  * at time @t. Time values on Bézier curves are not evenly distributed, so
 166  * 0.5 is not necessarily the midpoint.
 167  *
 168  * Return value: @pair
 169  **/
 170 CpmlPair *
 171 cpml_pair_at_curve(CpmlPair *pair, const CpmlPair *p1, const CpmlPair *p2,
 172                    const CpmlPair *p3, const CpmlPair *p4, double t)
 173 {
 174     double t1, t1_2, t1_3;
 175     double t_2, t_3;
 176
 177     t1 = 1-t;
 178     t1_2 = t1*t1;
 179     t1_3 = t1_2*t1;
 180     t_2 = t*t;
 181     t_3 = t_2*t;
 182
 183     pair->x = t1_3*p1->x + 3*t1_2*t*p2->x + 3*t1*t_2*p3->x + t_3*p4->x;
 184     pair->y = t1_3*p1->y + 3*t1_2*t*p2->y + 3*t1*t_2*p3->y + t_3*p4->y;
 185
 186     return pair;
 187 }
 188
 189
 190 void
 191 cpml_pair_negate(CpmlPair *pair)
 192 {
 193     pair->x = - pair->x;
 194     pair->y = - pair->y;
 195 }
 196
 197 cairo_bool_t
 198 cpml_pair_invert(CpmlPair *pair)
 199 {
 200     if (pair->x == 0 || pair->y == 0)
 201         return 0;
 202
 203     pair->x = 1. / pair->x;
 204     pair->y = 1. / pair->y;
 205     return 1;
 206 }
 207
 208 void
 209 cpml_pair_add(CpmlPair *pair, const CpmlPair *src)
 210 {
 211     pair->x += src->x;
 212     pair->y += src->y;
 213 }
 214
 215 void
 216 cpml_pair_sub(CpmlPair *pair, const CpmlPair *src)
 217 {
 218     pair->x -= src->x;
 219     pair->y -= src->y;
 220 }
 221
 222 void
 223 cpml_pair_mul(CpmlPair *pair, const CpmlPair *src)
 224 {
 225     pair->x *= src->x;
 226     pair->y *= src->y;
 227 }
 228
 229 cairo_bool_t
 230 cpml_pair_div(CpmlPair *pair, const CpmlPair *src)
 231 {
 232     if (src->x == 0 || src->y == 0)
 233         return 0;
 234
 235     pair->x /= src->x;
 236     pair->y /= src->y;
 237     return 1;
 238 }
 239
 240 /**
 241  * cpml_pair_transform:
 242  * @pair: the destination #CpmlPair struct
 243  * @matrix: the transformation matrix
 244  *
 245  * Shortcut to apply a specific transformation matrix to @pair.
 246  **/
 247 void
 248 cpml_pair_transform(CpmlPair *pair, const cairo_matrix_t *matrix)
 249 {
 250     cairo_matrix_transform_point(matrix, &pair->x, &pair->y);
 251 }
 252
 253
 254 /**
 255  * cpml_pair_squared_distance:
 256  * @from: the first #CpmlPair struct
 257  * @to: the second #CpmlPair struct
 258  *
 259  * Gets the squared distance between @from and @to. This value is useful
 260  * for comparation purpose: if you need to get the real distance, use
 261  * cpml_pair_distance().
 262  *
 263  * @from or @to could be %NULL, in which case the fallback (0, 0) pair
 264  * will be used.
 265  *
 266  * Return value: the squared distance
 267  **/
 268 double
 269 cpml_pair_squared_distance(const CpmlPair *from, const CpmlPair *to)
 270 {
 271     double x, y;
 272
 273     if (from == NULL)
 274         from = &fallback_pair;
 275     if (to == NULL)
 276         to = &fallback_pair;
 277
 278     x = to->x - from->x;
 279     y = to->y - from->y;
 280
 281     return x * x + y * y;
 282 }
 283
 284 /**
 285  * cpml_pair_distance:
 286  * @from: the first #CpmlPair struct
 287  * @to: the second #CpmlPair struct
 288  * @distance: where to store the result
 289  *
 290  * Gets the distance between @from and @to, storing the result in @distance.
 291  * If you need this value only for comparation purpose, you could use
 292  * cpm_pair_squared_distance() instead.
 293  *
 294  * @from or @to could be %NULL, in which case the fallback (0, 0) pair
 295  * will be used.
 296  *
 297  * The algorithm used is adapted from:
 298  * "Replacing Square Roots by Pythagorean Sums"
 299  * by Clave Moler and Donald Morrison (1983)
 300  * IBM Journal of Research and Development 27 (6): 577–581
 301  * http://www.research.ibm.com/journal/rd/276/ibmrd2706P.pdf
 302  *
 303  * Return value: the distance
 304  **/
 305 double
 306 cpml_pair_distance(const CpmlPair *from, const CpmlPair *to)
 307 {
 308     double x, y;
 309     double p, q, r, s;
 310
 311     if (from == NULL)
 312         from = &fallback_pair;
 313     if (to == NULL)
 314         to = &fallback_pair;
 315
 316     x = to->x - from->x;
 317     y = to->y - from->y;
 318
 319     if (x < 0)
 320         x = -x;
 321     if (y < 0)
 322         y = -y;
 323
 324     if (x > y) {
 325         p = x;
 326         q = y;
 327     } else {
 328         p = y;
 329         q = x;
 330     }
 331
 332     if (p > 0) {
 333         for (;;) {
 334             r = q/p;
 335             r *= r;
 336             if (r == 0)
 337                 break;
 338
 339             s = r / (4+r);
 340             p += 2*s*p;
 341             q *= s;
 342         }
 343     }
 344
 345     return p;
 346 }
 347
 348 /**
 349  * cpml_vector_from_pair:
 350  * @vector: the destination vector
 351  * @pair: the source pair
 352  * @length: the length of the vector
 353  *
 354  * Given the line L passing throught the origin and @pair, gets the
 355  * coordinate of the point on this line far @length from the origin
 356  * and store the result in @vector. If @pair itsself is the origin,
 357  * NULL is returned.
 358  *
 359  * @pair and @vector can be the same struct.
 360  *
 361  * Return value: @vector
 362  **/
 363 CpmlVector *
 364 cpml_vector_from_pair(CpmlVector *vector, const CpmlPair *pair, double length)
 365 {
 366     double divisor = cpml_pair_distance(NULL, pair);
 367
 368     if (divisor <= 0)
 369         return NULL;
 370
 371     divisor /= length;
 372     vector->x = pair->x / divisor;
 373     vector->y = pair->y / divisor;
 374
 375     return vector;
 376 }
 377
 378 /**
 379  * cpml_vector_from_angle:
 380  * @vector: the destination #CpmlVector
 381  * @angle: angle of direction, in radians
 382  * @length: the length of the vector
 383  *
 384  * Calculates the coordinates of the point far @length from the origin
 385  * in the @angle direction. The result is stored in @vector.
 386  *
 387  * Return value: @vector
 388  **/
 389 CpmlVector *
 390 cpml_vector_from_angle(CpmlVector *vector, double angle, double length)
 391 {
 392     static double cached_angle = 0;
 393     static CpmlPair cached_vector = { 1, 0 };
 394
 395     /* Check for cached result */
 396     if (angle == cached_angle)
 397         return cpml_pair_copy(vector, &cached_vector);
 398
 399     /* Check for common conditions */
 400     if (angle == CPML_DIR_UP) {
 401         vector->x = 0;
 402         vector->y = -1;
 403         return vector;
 404     }
 405     if (angle == CPML_DIR_DOWN) {
 406         vector->x = 0;
 407         vector->y = +1;
 408         return vector;
 409     }
 410     if (angle == CPML_DIR_LEFT) {
 411         vector->x = -1;
 412         vector->y = 0;
 413         return vector;
 414     }
 415     if (angle == CPML_DIR_RIGHT) {
 416         vector->x = +1;
 417         vector->y = 0;
 418         return vector;
 419     }
 420
 421     /* Computation and cache registration */
 422     vector->x = cos(angle);
 423     vector->y = -sin(angle);
 424     cached_angle = angle;
 425     cpml_pair_copy(&cached_vector, vector);
 426
 427     return vector;
 428 }
 429
 430 /**
 431  * cpml_vector_at_curve:
 432  * @vector: the destination #CpmlVector
 433  * @p1: start point
 434  * @p2: first control point
 435  * @p3: second control point
 436  * @p4: end point
 437  * @t: the mediation value
 438  * @length: vector length
 439  *
 440  * Given the time value @t, returns the slope on the specified Bézier curve
 441  * at time @t. The slope is returned as a vector of arbitrary magnitude.
 442  *
 443  * Return value: @vector
 444  **/
 445 CpmlVector *
 446 cpml_vector_at_curve(CpmlVector *vector,
 447                      const CpmlPair *p1, const CpmlPair *p2,
 448                      const CpmlPair *p3, const CpmlPair *p4,
 449                      double t, double length)
 450 {
 451     CpmlPair p21, p32, p43;
 452     double t1, t1_2, t_2;
 453
 454     cpml_pair_sub(cpml_pair_copy(&p21, p2), p1);
 455     cpml_pair_sub(cpml_pair_copy(&p32, p3), p2);
 456     cpml_pair_sub(cpml_pair_copy(&p43, p4), p3);
 457     t1 = 1-t;
 458     t1_2 = t1*t1;
 459     t_2 = t*t;
 460
 461     vector->x = 3*t1_2*p21.x + 6*t1*t*p32.x + 3*t_2*p43.x;
 462     vector->y = 3*t1_2*p21.y + 6*t1*t*p32.y + 3*t_2*p43.y;
 463
 464     return cpml_vector_from_pair(vector, vector, length);
 465 }
 466
 467 /**
 468  * cpml_vector_angle:
 469  * @vector: the source #CpmlVector
 470  *
 471  * Gets the angle of @vector, in radians. If @vector is (0, 0),
 472  * %CPML_DIR_RIGHT is returned.
 473  *
 474  * Return value: the angle in radians
 475  **/
 476 double
 477 cpml_vector_angle(const CpmlVector *vector)
 478 {
 479     static CpmlPair cached_vector = { 1., 0. };
 480     static double cached_angle = 0.;
 481
 482     /* Check for cached result */
 483     if (vector->x == cached_vector.x && vector->y == cached_vector.y)
 484         return cached_angle;
 485
 486     /* Check for common conditions */
 487     if (vector->y == 0)
 488         return vector->x >= 0 ? CPML_DIR_RIGHT : CPML_DIR_LEFT;
 489     if (vector->x == 0)
 490         return vector->y > 0 ? CPML_DIR_DOWN : CPML_DIR_UP;
 491     if (vector->x == vector->y)
 492         return vector->x > 0 ? M_PI_4 * 7 : M_PI_4 * 3;
 493     if (vector->x == -vector->y)
 494         return vector->x > 0 ? M_PI_4 : M_PI_4 * 5;
 495
 496     /* Computation and cache registration */
 497     cached_angle = atan(-vector->y / vector->x);
 498     cpml_pair_copy(&cached_vector, vector);
 499
 500     return cached_angle;
 501 }
 502
 503 /**
 504  * cpml_vector_normal:
 505  * @vector: the subject #CpmlVector
 506  *
 507  * Stores in @vector a vector normal to the original @vector.
 508  * The length is retained.
 509  *
 510  * The algorithm is really quick because no trigonometry is involved.
 511  **/
 512 void
 513 cpml_vector_normal(CpmlVector *vector)
 514 {
 515     double tmp = vector->x;
 516
 517     vector->x = -vector->y;
 518     vector->y = tmp;
 519 }
 520
 521 /**
 522  * cpml_pair_to_cairo:
 523  * @pair: the destination #CpmlPair
 524  * @path_data: the original path data point
 525  *
 526  * Sets a #cairo_path_data_t struct to @pair. This is exactly the reverse
 527  * operation of cpml_pair_from_cairo().
 528  **/
 529 void
 530 cpml_pair_to_cairo(const CpmlPair *pair, cairo_path_data_t *path_data)
 531 {
 532     path_data->point.x = pair->x;
 533     path_data->point.y = pair->y;
 534 }