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