lib/geometry.h

   1 /* Dia -- an diagram creation/manipulation program
   2  * Copyright (C) 1998 Alexander Larsson
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program 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
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17  */
  18
  19 /** \file geometry.h -- basic geometry classes and functions operationg on them */
  20 #ifndef GEOMETRY_H
  21 #define GEOMETRY_H
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include <config.h>
  25 #endif
  26
  27 #include "diatypes.h"
  28
  29 #include <glib.h>
  30 #include <math.h>
  31
  32 /* Solaris 2.4, 2.6, probably 2.5.x, and possibly others prototype
  33    finite() in ieeefp.h instead of math.h.  finite() might not be
  34    available at all on some HP-UX configurations (in which case,
  35    you're on your own). */
  36 #ifdef HAVE_IEEEFP_H
  37 #include <ieeefp.h>
  38 #endif
  39 #ifndef HAVE_ISINF
  40 #define isinf(a) (!finite(a))
  41 #endif
  42
  43 #ifdef _MSC_VER
  44 /* #ifdef G_OS_WIN32  apparently _MSC_VER and mingw */
  45    /* there are some things more in the gcc headers */
  46 #  include <float.h>
  47 #  define finite(a) _finite(a)
  48 #  define isnan(a) _isnan(a)
  49 #endif
  50 #ifdef G_OS_WIN32
  51 #  define M_PI      3.14159265358979323846
  52 #  define M_SQRT2       1.41421356237309504880  /* sqrt(2) */
  53 #  define M_SQRT1_2 0.70710678118654752440      /* 1/sqrt(2) */
  54 #endif
  55
  56 /* gcc -std=c89 doesn't have it either */
  57 #ifndef M_PI
  58 #define M_PI G_PI
  59 #endif
  60 #ifndef M_SQRT2
  61 #define M_SQRT2 G_SQRT2
  62 #endif
  63 #ifndef M_SQRT1_2
  64 #define M_SQRT1_2 (1.0/G_SQRT2)
  65 #endif
  66
  67 /*
  68   Coordinate system used:
  69    +---> x
  70    |
  71    |
  72    V  y
  73  */
  74
  75 typedef double real;
  76 typedef real coord;
  77
  78 /*! \brief A two dimensional position */
  79 struct _Point {
  80   coord x; /*!< horizontal */
  81   coord y; /*!< vertical */
  82 };
  83
  84 /*! \brief A rectangle given by upper left and lower right corner */
  85 struct _Rectangle {
  86   coord top; /*!< y1 */
  87   coord left; /*!< x1 */
  88   coord bottom; /*!< y2 */
  89   coord right; /*!< x2 */
  90 };
  91
  92 /*! \brief A rectangle for fixed point e.g. pixel coordinates */
  93 struct _IntRectangle {
  94   int top; /*!< y1 */
  95   int left; /*!< x1 */
  96   int bottom; /*!< y2 */
  97   int right; /*!< x2 */
  98 };
  99
 100 /*!
 101  * \brief BezPoint is a bezier point forming _Bezierline or _Beziergon
 102  */
 103 struct _BezPoint {
 104   enum {
 105     BEZ_MOVE_TO, /*!< move to point p1 */
 106     BEZ_LINE_TO, /*!< line to point p1 */
 107     BEZ_CURVE_TO /*!< curve to point p3 using p1 and p2 as control points */
 108   } type;
 109   Point p1; /*!< main point in case of move or line-to, otherwise first control point */
 110   Point p2; /*!< second control point  */
 111   Point p3; /*!< main point for 'true' bezier point */
 112 };
 113
 114
 115 #define ROUND(x) ((int) floor((x)+0.5))
 116
 117 /* inline these functions if the platform supports it */
 118
 119 G_INLINE_FUNC void point_add(Point *p1, const Point *p2);
 120 #ifdef G_CAN_INLINE
 121 G_INLINE_FUNC void
 122 point_add(Point *p1, const Point *p2)
 123 {
 124   p1->x += p2->x;
 125   p1->y += p2->y;
 126 }
 127 #endif
 128
 129 G_INLINE_FUNC void point_sub(Point *p1, const Point *p2);
 130 #ifdef G_CAN_INLINE
 131 G_INLINE_FUNC void
 132 point_sub(Point *p1, const Point *p2)
 133 {
 134   p1->x -= p2->x;
 135   p1->y -= p2->y;
 136 }
 137 #endif
 138
 139 G_INLINE_FUNC real point_dot(const Point *p1, const Point *p2);
 140 #ifdef G_CAN_INLINE
 141 G_INLINE_FUNC real
 142 point_dot(const Point *p1, const Point *p2)
 143 {
 144   return p1->x*p2->x + p1->y*p2->y;
 145 }
 146 #endif
 147
 148 G_INLINE_FUNC real point_len(const Point *p);
 149 #ifdef G_CAN_INLINE
 150 G_INLINE_FUNC real
 151 point_len(const Point *p)
 152 {
 153   return sqrt(p->x*p->x + p->y*p->y);
 154 }
 155 #endif
 156
 157 G_INLINE_FUNC void point_scale(Point *p, real alpha);
 158 #ifdef G_CAN_INLINE
 159 G_INLINE_FUNC void
 160 point_scale(Point *p, real alpha)
 161 {
 162   p->x *= alpha;
 163   p->y *= alpha;
 164 }
 165 #endif
 166
 167 G_INLINE_FUNC void point_normalize(Point *p);
 168 #ifdef G_CAN_INLINE
 169 G_INLINE_FUNC void
 170 point_normalize(Point *p)
 171 {
 172   real len;
 173
 174   len = sqrt(p->x*p->x + p->y*p->y);
 175
 176   /* One could call it a bug to try normalizing a vector with
 177    * len 0 and the result at least requires definition. But
 178    * this is what makes the beziergon bounding box calculation
 179    * work. What's the mathematical correct result of 0.0/0.0 ?
 180    */
 181   if (len > 0.0) {
 182     p->x /= len;
 183     p->y /= len;
 184   } else {
 185     p->x = 0.0;
 186     p->y = 0.0;
 187   }
 188
 189 }
 190 #endif
 191
 192 G_INLINE_FUNC void point_rotate(Point *p1, const Point *p2);
 193 #ifdef G_CAN_INLINE
 194 G_INLINE_FUNC void
 195 point_rotate(Point *p1, const Point *p2)
 196 {
 197   p1->x = p1->x*p2->x - p1->y*p2->y;
 198   p1->y = p1->x*p2->y + p1->y*p2->x;
 199 }
 200 #endif
 201
 202 G_INLINE_FUNC void point_get_normed(Point *dst, const Point *src);
 203 #ifdef G_CAN_INLINE
 204 G_INLINE_FUNC void
 205 point_get_normed(Point *dst, const Point *src)
 206 {
 207   real len;
 208
 209   len = sqrt(src->x*src->x + src->y*src->y);
 210
 211   dst->x = src->x / len;
 212   dst->y = src->y / len;
 213 }
 214 #endif
 215
 216 G_INLINE_FUNC void point_get_perp(Point *dst, const Point *src);
 217 #ifdef G_CAN_INLINE
 218 G_INLINE_FUNC void
 219 point_get_perp(Point *dst, const Point *src)
 220 {
 221   /* dst = the src vector, rotated 90deg counter clowkwise. src *must* be
 222      normalized before. */
 223   dst->y = src->x;
 224   dst->x = -src->y;
 225 }
 226 #endif
 227
 228 G_INLINE_FUNC void point_copy(Point *dst, const Point *src);
 229 #ifdef G_CAN_INLINE
 230 G_INLINE_FUNC void
 231 point_copy(Point *dst, const Point *src)
 232 {
 233   /* Unfortunately, the compiler is not clever enough. And copying using
 234      ints is faster if we don't computer based on the copied values, but
 235      is slower if we have to make a FP reload afterwards.
 236      point_copy() is meant for the latter case : then, the compiler is
 237      able to shuffle and merge the FP loads. */
 238   dst->x = src->x;
 239   dst->y = src->y;
 240 }
 241 #endif
 242
 243 G_INLINE_FUNC void point_add_scaled(Point *dst, const Point *src, real alpha);
 244 #ifdef G_CAN_INLINE
 245 G_INLINE_FUNC void
 246 point_add_scaled(Point *dst, const Point *src, real alpha)
 247 {
 248   /* especially useful if src is a normed vector... */
 249   dst->x += alpha * src->x;
 250   dst->y += alpha * src->y;
 251 }
 252 #endif
 253
 254 G_INLINE_FUNC void point_copy_add_scaled(Point *dst, const Point *src,
 255                                          const Point *vct,
 256                                          real alpha);
 257 #ifdef G_CAN_INLINE
 258 G_INLINE_FUNC void
 259 point_copy_add_scaled(Point *dst, const Point *src,
 260                       const Point *vct, real alpha)
 261 {
 262   /* especially useful if vct is a normed vector... */
 263   dst->x = src->x + (alpha * vct->x);
 264   dst->y = src->y + (alpha * vct->y);
 265 }
 266 #endif
 267
 268 void point_convex(Point *dst, const Point *src1, const Point *src2, real alpha);
 269
 270 void rectangle_union(Rectangle *r1, const Rectangle *r2);
 271 void int_rectangle_union(IntRectangle *r1, const IntRectangle *r2);
 272 void rectangle_intersection(Rectangle *r1, const Rectangle *r2);
 273 int rectangle_intersects(const Rectangle *r1, const Rectangle *r2);
 274 int point_in_rectangle(const Rectangle* r, const Point *p);
 275 int rectangle_in_rectangle(const Rectangle* outer, const Rectangle *inner);
 276 void rectangle_add_point(Rectangle *r, const Point *p);
 277
 278 G_INLINE_FUNC gboolean rectangle_equals(const Rectangle *old_extents,
 279                                          const Rectangle *new_extents);
 280 #ifdef G_CAN_INLINE
 281 G_INLINE_FUNC gboolean
 282 rectangle_equals(const Rectangle *r1, const Rectangle *r2)
 283 {
 284   return ( (r2->left == r1->left) &&
 285            (r2->right == r1->right) &&
 286            (r2->top == r1->top) &&
 287            (r2->bottom == r1->bottom) );
 288 }
 289 #endif
 290
 291 G_INLINE_FUNC real distance_point_point(const Point *p1, const Point *p2);
 292 #ifdef G_CAN_INLINE
 293 G_INLINE_FUNC real
 294 distance_point_point(const Point *p1, const Point *p2)
 295 {
 296   real dx = p1->x - p2->x;
 297   real dy = p1->y - p2->y;
 298   return sqrt(dx*dx + dy*dy);
 299 }
 300 #endif
 301
 302 G_INLINE_FUNC const Point *closest_to(const Point *to, const Point *p1, const Point *p2);
 303 #ifdef G_CAN_INLINE
 304 G_INLINE_FUNC const Point *
 305 closest_to(const Point *to, const Point *p1, const Point *p2)
 306 {
 307   if (distance_point_point(to,p1) < distance_point_point(to,p2))
 308           return p1;
 309   return p2;
 310 }
 311 #endif
 312
 313 G_INLINE_FUNC real distance_point_point_manhattan(const Point *p1,
 314                                                   const Point *p2);
 315 #ifdef G_CAN_INLINE
 316 G_INLINE_FUNC real
 317 distance_point_point_manhattan(const Point *p1, const Point *p2)
 318 {
 319   real dx = p1->x - p2->x;
 320   real dy = p1->y - p2->y;
 321   return ABS(dx) + ABS(dy);
 322 }
 323 #endif
 324
 325 real distance_rectangle_point(const Rectangle *rect, const Point *point);
 326 real distance_line_point(const Point *line_start, const Point *line_end,
 327                          real line_width, const Point *point);
 328
 329 real distance_polygon_point(const Point *poly, guint npoints,
 330                             real line_width, const Point *point);
 331
 332 /* bezier distance calculations */
 333 real distance_bez_seg_point(const Point *b1, const Point *b2,
 334                             const Point *b3, const Point *b4,
 335                             real line_width, const Point *point);
 336 real distance_bez_line_point(const BezPoint *b, guint npoints,
 337                              real line_width, const Point *point);
 338 real distance_bez_shape_point(const BezPoint *b, guint npoints,
 339                               real line_width, const Point *point);
 340
 341 real distance_ellipse_point(const Point *centre, real width, real height,
 342                             real line_width, const Point *point);
 343
 344 typedef real  Vector[3];
 345 typedef Vector  Matrix[3];
 346
 347 void          transform_point             (Matrix, Point *, Point *);
 348 void          mult_matrix                 (Matrix, Matrix);
 349 void          identity_matrix             (Matrix);
 350 void          translate_matrix            (Matrix, real, real);
 351 void          scale_matrix                (Matrix, real, real);
 352 void          rotate_matrix               (Matrix, real);
 353 void          xshear_matrix               (Matrix, real);
 354 void          yshear_matrix               (Matrix, real);
 355
 356 real dot2(Point *p1, Point *p2);
 357 void line_coef(real *a, real *b, real *c, Point *p1, Point *p2);
 358 real line_to_point(real a, real b , real c, Point *p);
 359 void point_perp(Point *p, real a, real b, real c, Point *perp);
 360 void fillet(Point *p1, Point *p2, Point *p3, Point *p4,
 361             real r, Point *c, real *pa, real *aa);
 362 real point_cross(Point *p1, Point *p2);
 363 Point calculate_object_edge(Point *objmid, Point *end, DiaObject *obj);
 364
 365 #endif /* GEOMETRY_H */