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