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 G_BEGIN_DECLS
  68
  69 /*
  70   Coordinate system used:
  71    +---> x
  72    |
  73    |
  74    V  y
  75  */
  76
  77 typedef double real;
  78 typedef real coord;
  79
  80 /*! \brief A two dimensional position */
  81 struct _Point {
  82   coord x; /*!< horizontal */
  83   coord y; /*!< vertical */
  84 };
  85
  86 /*! \brief A rectangle given by upper left and lower right corner */
  87 struct _Rectangle {
  88   coord top; /*!< y1 */
  89   coord left; /*!< x1 */
  90   coord bottom; /*!< y2 */
  91   coord right; /*!< x2 */
  92 };
  93
  94 /*! \brief A rectangle for fixed point e.g. pixel coordinates */
  95 struct _IntRectangle {
  96   int top; /*!< y1 */
  97   int left; /*!< x1 */
  98   int bottom; /*!< y2 */
  99   int right; /*!< x2 */
 100 };
 101
 102 /*!
 103  * \brief BezPoint is a bezier point forming _Bezierline or _Beziergon
 104  */
 105 struct _BezPoint {
 106   enum {
 107     BEZ_MOVE_TO, /*!< move to point p1 */
 108     BEZ_LINE_TO, /*!< line to point p1 */
 109     BEZ_CURVE_TO /*!< curve to point p3 using p1 and p2 as control points */
 110   } type;
 111   Point p1; /*!< main point in case of move or line-to, otherwise first control point */
 112   Point p2; /*!< second control point  */
 113   Point p3; /*!< main point for 'true' bezier point */
 114 };
 115
 116
 117 #define ROUND(x) ((int) floor((x)+0.5))
 118
 119 /* inline these functions if the platform supports it */
 120
 121 G_INLINE_FUNC void point_add(Point *p1, const Point *p2);
 122 #ifdef G_CAN_INLINE
 123 G_INLINE_FUNC void
 124 point_add(Point *p1, const Point *p2)
 125 {
 126   p1->x += p2->x;
 127   p1->y += p2->y;
 128 }
 129 #endif
 130
 131 G_INLINE_FUNC void point_sub(Point *p1, const Point *p2);
 132 #ifdef G_CAN_INLINE
 133 G_INLINE_FUNC void
 134 point_sub(Point *p1, const Point *p2)
 135 {
 136   p1->x -= p2->x;
 137   p1->y -= p2->y;
 138 }
 139 #endif
 140
 141 G_INLINE_FUNC real point_dot(const Point *p1, const Point *p2);
 142 #ifdef G_CAN_INLINE
 143 G_INLINE_FUNC real
 144 point_dot(const Point *p1, const Point *p2)
 145 {
 146   return p1->x*p2->x + p1->y*p2->y;
 147 }
 148 #endif
 149
 150 G_INLINE_FUNC real point_len(const Point *p);
 151 #ifdef G_CAN_INLINE
 152 G_INLINE_FUNC real
 153 point_len(const Point *p)
 154 {
 155   return sqrt(p->x*p->x + p->y*p->y);
 156 }
 157 #endif
 158
 159 G_INLINE_FUNC void point_scale(Point *p, real alpha);
 160 #ifdef G_CAN_INLINE
 161 G_INLINE_FUNC void
 162 point_scale(Point *p, real alpha)
 163 {
 164   p->x *= alpha;
 165   p->y *= alpha;
 166 }
 167 #endif
 168
 169 G_INLINE_FUNC void point_normalize(Point *p);
 170 #ifdef G_CAN_INLINE
 171 G_INLINE_FUNC void
 172 point_normalize(Point *p)
 173 {
 174   real len;
 175
 176   len = sqrt(p->x*p->x + p->y*p->y);
 177
 178   /* One could call it a bug to try normalizing a vector with
 179    * len 0 and the result at least requires definition. But
 180    * this is what makes the beziergon bounding box calculation
 181    * work. What's the mathematical correct result of 0.0/0.0 ?
 182    */
 183   if (len > 0.0) {
 184     p->x /= len;
 185     p->y /= len;
 186   } else {
 187     p->x = 0.0;
 188     p->y = 0.0;
 189   }
 190
 191 }
 192 #endif
 193
 194 G_INLINE_FUNC void point_rotate(Point *p1, const Point *p2);
 195 #ifdef G_CAN_INLINE
 196 G_INLINE_FUNC void
 197 point_rotate(Point *p1, const Point *p2)
 198 {
 199   p1->x = p1->x*p2->x - p1->y*p2->y;
 200   p1->y = p1->x*p2->y + p1->y*p2->x;
 201 }
 202 #endif
 203
 204 G_INLINE_FUNC void point_get_normed(Point *dst, const Point *src);
 205 #ifdef G_CAN_INLINE
 206 G_INLINE_FUNC void
 207 point_get_normed(Point *dst, const Point *src)
 208 {
 209   real len;
 210
 211   len = sqrt(src->x*src->x + src->y*src->y);
 212
 213   dst->x = src->x / len;
 214   dst->y = src->y / len;
 215 }
 216 #endif
 217
 218 G_INLINE_FUNC void point_get_perp(Point *dst, const Point *src);
 219 #ifdef G_CAN_INLINE
 220 G_INLINE_FUNC void
 221 point_get_perp(Point *dst, const Point *src)
 222 {
 223   /* dst = the src vector, rotated 90deg counter clowkwise. src *must* be
 224      normalized before. */
 225   dst->y = src->x;
 226   dst->x = -src->y;
 227 }
 228 #endif
 229
 230 G_INLINE_FUNC void point_copy(Point *dst, const Point *src);
 231 #ifdef G_CAN_INLINE
 232 G_INLINE_FUNC void
 233 point_copy(Point *dst, const Point *src)
 234 {
 235   /* Unfortunately, the compiler is not clever enough. And copying using
 236      ints is faster if we don't computer based on the copied values, but
 237      is slower if we have to make a FP reload afterwards.
 238      point_copy() is meant for the latter case : then, the compiler is
 239      able to shuffle and merge the FP loads. */
 240   dst->x = src->x;
 241   dst->y = src->y;
 242 }
 243 #endif
 244
 245 G_INLINE_FUNC void point_add_scaled(Point *dst, const Point *src, real alpha);
 246 #ifdef G_CAN_INLINE
 247 G_INLINE_FUNC void
 248 point_add_scaled(Point *dst, const Point *src, real alpha)
 249 {
 250   /* especially useful if src is a normed vector... */
 251   dst->x += alpha * src->x;
 252   dst->y += alpha * src->y;
 253 }
 254 #endif
 255
 256 G_INLINE_FUNC void point_copy_add_scaled(Point *dst, const Point *src,
 257                                          const Point *vct,
 258                                          real alpha);
 259 #ifdef G_CAN_INLINE
 260 G_INLINE_FUNC void
 261 point_copy_add_scaled(Point *dst, const Point *src,
 262                       const Point *vct, real alpha)
 263 {
 264   /* especially useful if vct is a normed vector... */
 265   dst->x = src->x + (alpha * vct->x);
 266   dst->y = src->y + (alpha * vct->y);
 267 }
 268 #endif
 269
 270 void point_convex(Point *dst, const Point *src1, const Point *src2, real alpha);
 271
 272 void rectangle_union(Rectangle *r1, const Rectangle *r2);
 273 void int_rectangle_union(IntRectangle *r1, const IntRectangle *r2);
 274 void rectangle_intersection(Rectangle *r1, const Rectangle *r2);
 275 int rectangle_intersects(const Rectangle *r1, const Rectangle *r2);
 276 int point_in_rectangle(const Rectangle* r, const Point *p);
 277 int rectangle_in_rectangle(const Rectangle* outer, const Rectangle *inner);
 278 void rectangle_add_point(Rectangle *r, const Point *p);
 279
 280 G_INLINE_FUNC gboolean rectangle_equals(const Rectangle *old_extents,
 281                                          const Rectangle *new_extents);
 282 #ifdef G_CAN_INLINE
 283 G_INLINE_FUNC gboolean
 284 rectangle_equals(const Rectangle *r1, const Rectangle *r2)
 285 {
 286   return ( (r2->left == r1->left) &&
 287            (r2->right == r1->right) &&
 288            (r2->top == r1->top) &&
 289            (r2->bottom == r1->bottom) );
 290 }
 291 #endif
 292
 293 G_INLINE_FUNC real distance_point_point(const Point *p1, const Point *p2);
 294 #ifdef G_CAN_INLINE
 295 G_INLINE_FUNC real
 296 distance_point_point(const Point *p1, const Point *p2)
 297 {
 298   real dx = p1->x - p2->x;
 299   real dy = p1->y - p2->y;
 300   return sqrt(dx*dx + dy*dy);
 301 }
 302 #endif
 303
 304 G_INLINE_FUNC const Point *closest_to(const Point *to, const Point *p1, const Point *p2);
 305 #ifdef G_CAN_INLINE
 306 G_INLINE_FUNC const Point *
 307 closest_to(const Point *to, const Point *p1, const Point *p2)
 308 {
 309   if (distance_point_point(to,p1) < distance_point_point(to,p2))
 310           return p1;
 311   return p2;
 312 }
 313 #endif
 314
 315 G_INLINE_FUNC real distance_point_point_manhattan(const Point *p1,
 316                                                   const Point *p2);
 317 #ifdef G_CAN_INLINE
 318 G_INLINE_FUNC real
 319 distance_point_point_manhattan(const Point *p1, const Point *p2)
 320 {
 321   real dx = p1->x - p2->x;
 322   real dy = p1->y - p2->y;
 323   return ABS(dx) + ABS(dy);
 324 }
 325 #endif
 326
 327 real distance_rectangle_point(const Rectangle *rect, const Point *point);
 328 real distance_line_point(const Point *line_start, const Point *line_end,
 329                          real line_width, const Point *point);
 330
 331 real distance_polygon_point(const Point *poly, guint npoints,
 332                             real line_width, const Point *point);
 333
 334 /* bezier distance calculations */
 335 real distance_bez_seg_point(const Point *b1, const Point *b2,
 336                             const Point *b3, const Point *b4,
 337                             real line_width, const Point *point);
 338 real distance_bez_line_point(const BezPoint *b, guint npoints,
 339                              real line_width, const Point *point);
 340 real distance_bez_shape_point(const BezPoint *b, guint npoints,
 341                               real line_width, const Point *point);
 342
 343 real distance_ellipse_point(const Point *centre, real width, real height,
 344                             real line_width, const Point *point);
 345
 346 typedef real  Vector[3];
 347 typedef Vector  Matrix[3];
 348
 349 void          transform_point             (Matrix, Point *, Point *);
 350 void          mult_matrix                 (Matrix, Matrix);
 351 void          identity_matrix             (Matrix);
 352 void          translate_matrix            (Matrix, real, real);
 353 void          scale_matrix                (Matrix, real, real);
 354 void          rotate_matrix               (Matrix, real);
 355 void          xshear_matrix               (Matrix, real);
 356 void          yshear_matrix               (Matrix, real);
 357
 358 real dot2(Point *p1, Point *p2);
 359 void line_coef(real *a, real *b, real *c, Point *p1, Point *p2);
 360 real line_to_point(real a, real b , real c, Point *p);
 361 void point_perp(Point *p, real a, real b, real c, Point *perp);
 362 void fillet(Point *p1, Point *p2, Point *p3, Point *p4,
 363             real r, Point *c, real *pa, real *aa);
 364 real point_cross(Point *p1, Point *p2);
 365 Point calculate_object_edge(Point *objmid, Point *end, DiaObject *obj);
 366
 367 G_END_DECLS
 368
 369 #endif /* GEOMETRY_H */