libfoocanvas/foo-canvas-util.c

   1 /*
   2  * Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation
   3  * All rights reserved.
   4  *
   5  * This file is part of the Gnome Library.
   6  *
   7  * The Gnome Library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public License as
   9  * published by the Free Software Foundation; either version 2 of the
  10  * License, or (at your option) any later version.
  11  *
  12  * The Gnome Library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public
  18  * License along with the Gnome Library; see the file COPYING.LIB.  If not,
  19  * write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20  * Boston, MA 02111-1307, USA.
  21  */
  22 /*
  23   @NOTATION@
  24  */
  25 /* Miscellaneous utility functions for the FooCanvas widget
  26  *
  27  * FooCanvas is basically a port of the Tk toolkit's most excellent canvas widget.  Tk is
  28  * copyrighted by the Regents of the University of California, Sun Microsystems, and other parties.
  29  *
  30  *
  31  * Author: Federico Mena <federico@nuclecu.unam.mx>
  32  */
  33
  34 #include <config.h>
  35
  36 #include <sys/types.h>
  37 #include <glib.h>
  38 #include <math.h>
  39 #include "foo-canvas.h"
  40 #include "foo-canvas-util.h"
  41
  42 /*
  43  * Ok, so some systems require magic incantations for M_PI to be defined.
  44  * It's not important enough to worry about.
  45  */
  46 #ifndef M_PI
  47 #define M_PI 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117
  48 #endif
  49
  50 /**
  51  * foo_canvas_points_new:
  52  * @num_points: The number of points to allocate space for in the array.
  53  *
  54  * Creates a structure that should be used to pass an array of points to
  55  * items.
  56  *
  57  * Return value: A newly-created array of points.  It should be filled in
  58  * by the user.
  59  **/
  60 FooCanvasPoints *
  61 foo_canvas_points_new (int num_points)
  62 {
  63         FooCanvasPoints *points;
  64
  65         g_return_val_if_fail (num_points > 1, NULL);
  66
  67         points = g_new (FooCanvasPoints, 1);
  68         points->num_points = num_points;
  69         points->coords = g_new (double, 2 * num_points);
  70         points->ref_count = 1;
  71
  72         return points;
  73 }
  74
  75 /**
  76  * foo_canvas_points_ref:
  77  * @points: A canvas points structure.
  78  *
  79  * Increases the reference count of the specified points structure.
  80  *
  81  * Return value: The canvas points structure itself.
  82  **/
  83 FooCanvasPoints *
  84 foo_canvas_points_ref (FooCanvasPoints *points)
  85 {
  86         g_return_val_if_fail (points != NULL, NULL);
  87
  88         points->ref_count += 1;
  89         return points;
  90 }
  91
  92 /**
  93  * foo_canvas_points_free:
  94  * @points: A canvas points structure.
  95  *
  96  * Decreases the reference count of the specified points structure.  If it
  97  * reaches zero, then the structure is freed.
  98  **/
  99 void
 100 foo_canvas_points_free (FooCanvasPoints *points)
 101 {
 102         g_return_if_fail (points != NULL);
 103
 104         points->ref_count -= 1;
 105         if (points->ref_count == 0) {
 106                 g_free (points->coords);
 107                 g_free (points);
 108         }
 109 }
 110
 111 /**
 112  * foo_canvas_get_miter_points:
 113  * @x1: X coordinate of the first point
 114  * @y1: Y coordinate of the first point
 115  * @x2: X coordinate of the second (angle) point
 116  * @y2: Y coordinate of the second (angle) point
 117  * @x3: X coordinate of the third point
 118  * @y3: Y coordinate of the third point
 119  * @width: Width of the line
 120  * @mx1: The X coordinate of the first miter point is returned here.
 121  * @my1: The Y coordinate of the first miter point is returned here.
 122  * @mx2: The X coordinate of the second miter point is returned here.
 123  * @my2: The Y coordinate of the second miter point is returned here.
 124  *
 125  * Given three points forming an angle, computes the coordinates of the inside
 126  * and outside points of the mitered corner formed by a line of a given width at
 127  * that angle.
 128  *
 129  * Return value: FALSE if the angle is less than 11 degrees (this is the same
 130  * threshold as X uses.  If this occurs, the return points are not modified.
 131  * Otherwise, returns TRUE.
 132  **/
 133 int
 134 foo_canvas_get_miter_points (double x1, double y1, double x2, double y2, double x3, double y3,
 135                              double width,
 136                              double *mx1, double *my1, double *mx2, double *my2)
 137 {
 138         double theta1;          /* angle of segment p2-p1 */
 139         double theta2;          /* angle of segment p2-p3 */
 140         double theta;           /* angle between line segments */
 141         double theta3;          /* angle that bisects theta1 and theta2 and points to p1 */
 142         double dist;            /* distance of miter points from p2 */
 143         double dx, dy;          /* x and y offsets corresponding to dist */
 144
 145         double ELEVEN_DEGREES = 11.0 * M_PI / 180.0;
 146
 147         /* Degenerate cases.  */
 148         if ((x1 == x2 && y1 == y2) || (x2 == x3 && y2 == y3))
 149                 return FALSE;
 150
 151         theta1 = atan2 (y1 - y2, x1 - x2);
 152         theta2 = atan2 (y3 - y2, x3 - x2);
 153         theta = theta1 - theta2;
 154
 155         /* Normalize to (-pi; pi].  */
 156         if (theta > M_PI)
 157                 theta -= 2.0 * M_PI;
 158         else if (theta <= -M_PI)
 159                 theta += 2.0 * M_PI;
 160
 161         if (fabs (theta) < ELEVEN_DEGREES)
 162                 return FALSE;
 163
 164         dist = fabs (0.5 * width / sin (0.5 * theta));
 165
 166         theta3 = (theta1 + theta2) / 2.0;
 167         if (sin (theta3 - theta1) > 0.0)
 168                 theta3 += M_PI;
 169
 170         dx = dist * cos (theta3);
 171         dy = dist * sin (theta3);
 172
 173         *mx1 = x2 + dx;
 174         *mx2 = x2 - dx;
 175         *my1 = y2 + dy;
 176         *my2 = y2 - dy;
 177
 178         return TRUE;
 179 }
 180
 181 /**
 182  * foo_canvas_get_butt_points:
 183  * @x1: X coordinate of first point in the line
 184  * @y1: Y cooordinate of first point in the line
 185  * @x2: X coordinate of second point (endpoint) of the line
 186  * @y2: Y coordinate of second point (endpoint) of the line
 187  * @width: Width of the line
 188  * @project: Whether the butt points should project out by width/2 distance
 189  * @bx1: X coordinate of first butt point is returned here
 190  * @by1: Y coordinate of first butt point is returned here
 191  * @bx2: X coordinate of second butt point is returned here
 192  * @by2: Y coordinate of second butt point is returned here
 193  *
 194  * Computes the butt points of a line segment.
 195  **/
 196 void
 197 foo_canvas_get_butt_points (double x1, double y1, double x2, double y2,
 198                               double width, int project,
 199                               double *bx1, double *by1, double *bx2, double *by2)
 200 {
 201         double length;
 202         double dx, dy;
 203
 204         width *= 0.5;
 205         dx = x2 - x1;
 206         dy = y2 - y1;
 207         length = sqrt (dx * dx + dy * dy);
 208
 209         if (length < FOO_CANVAS_EPSILON) {
 210                 *bx1 = *bx2 = x2;
 211                 *by1 = *by2 = y2;
 212         } else {
 213                 dx = -width * (y2 - y1) / length;
 214                 dy = width * (x2 - x1) / length;
 215
 216                 *bx1 = x2 + dx;
 217                 *bx2 = x2 - dx;
 218                 *by1 = y2 + dy;
 219                 *by2 = y2 - dy;
 220
 221                 if (project) {
 222                         *bx1 += dy;
 223                         *bx2 += dy;
 224                         *by1 -= dx;
 225                         *by2 -= dx;
 226                 }
 227         }
 228 }
 229
 230 /**
 231  * foo_canvas_polygon_to_point:
 232  * @poly: Vertices of the polygon.  X coordinates are in the even indices, and Y
 233  * coordinates are in the odd indices
 234  * @num_points: Number of points in the polygon
 235  * @x: X coordinate of the point
 236  * @y: Y coordinate of the point
 237  *
 238  * Computes the distance between a point and a polygon.
 239  *
 240  * Return value: The distance from the point to the polygon, or zero if the
 241  * point is inside the polygon.
 242  **/
 243 double
 244 foo_canvas_polygon_to_point (double *poly, int num_points, double x, double y)
 245 {
 246         double best;
 247         int intersections;
 248         int i;
 249         double *p;
 250         double dx, dy;
 251
 252         /* Iterate through all the edges in the polygon, updating best and intersections.
 253          *
 254          * When computing intersections, include left X coordinate of line within its range, but not
 255          * Y coordinate.  Otherwise if the point lies exactly below a vertex we'll count it as two
 256          * intersections.
 257          */
 258
 259         best = 1.0e36;
 260         if (poly == NULL)
 261                 return best;
 262
 263         intersections = 0;
 264
 265         for (i = num_points, p = poly; i > 1; i--, p += 2) {
 266                 double px, py, dist;
 267
 268                 /* Compute the point on the current edge closest to the point and update the
 269                  * intersection count.  This must be done separately for vertical edges, horizontal
 270                  * edges, and others.
 271                  */
 272
 273                 if (p[2] == p[0]) {
 274                         /* Vertical edge */
 275
 276                         px = p[0];
 277
 278                         if (p[1] >= p[3]) {
 279                                 py = MIN (p[1], y);
 280                                 py = MAX (py, p[3]);
 281                         } else {
 282                                 py = MIN (p[3], y);
 283                                 py = MAX (py, p[1]);
 284                         }
 285                 } else if (p[3] == p[1]) {
 286                         /* Horizontal edge */
 287
 288                         py = p[1];
 289
 290                         if (p[0] >= p[2]) {
 291                                 px = MIN (p[0], x);
 292                                 px = MAX (px, p[2]);
 293
 294                                 if ((y < py) && (x < p[0]) && (x >= p[2]))
 295                                         intersections++;
 296                         } else {
 297                                 px = MIN (p[2], x);
 298                                 px = MAX (px, p[0]);
 299
 300                                 if ((y < py) && (x < p[2]) && (x >= p[0]))
 301                                         intersections++;
 302                         }
 303                 } else {
 304                         double m1, b1, m2, b2;
 305                         int lower;
 306
 307                         /* Diagonal edge.  Convert the edge to a line equation (y = m1*x + b1), then
 308                          * compute a line perpendicular to this edge but passing through the point,
 309                          * (y = m2*x + b2).
 310                          */
 311
 312                         m1 = (p[3] - p[1]) / (p[2] - p[0]);
 313                         b1 = p[1] - m1 * p[0];
 314
 315                         m2 = -1.0 / m1;
 316                         b2 = y - m2 * x;
 317
 318                         px = (b2 - b1) / (m1 - m2);
 319                         py = m1 * px + b1;
 320
 321                         if (p[0] > p[2]) {
 322                                 if (px > p[0]) {
 323                                         px = p[0];
 324                                         py = p[1];
 325                                 } else if (px < p[2]) {
 326                                         px = p[2];
 327                                         py = p[3];
 328                                 }
 329                         } else {
 330                                 if (px > p[2]) {
 331                                         px = p[2];
 332                                         py = p[3];
 333                                 } else if (px < p[0]) {
 334                                         px = p[0];
 335                                         py = p[1];
 336                                 }
 337                         }
 338
 339                         lower = (m1 * x + b1) > y;
 340
 341                         if (lower && (x >= MIN (p[0], p[2])) && (x < MAX (p[0], p[2])))
 342                                 intersections++;
 343                 }
 344
 345                 /* Compute the distance to the closest point, and see if that is the best so far */
 346
 347                 dx = x - px;
 348                 dy = y - py;
 349                 dist = sqrt (dx * dx + dy * dy);
 350                 if (dist < best)
 351                         best = dist;
 352         }
 353
 354         /* We've processed all the points.  If the number of intersections is odd, the point is
 355          * inside the polygon.
 356          */
 357
 358         if (intersections & 0x1)
 359                 return 0.0;
 360         else
 361                 return best;
 362 }
 363
 364 /**
 365  * foo_canvas_item_reset_bounds:
 366  * @item: A canvas item
 367  *
 368  * Resets the bounding box of a canvas item to an empty rectangle.
 369  **/
 370 void
 371 foo_canvas_item_reset_bounds (FooCanvasItem *item)
 372 {
 373         item->x1 = 0.0;
 374         item->y1 = 0.0;
 375         item->x2 = 0.0;
 376         item->y2 = 0.0;
 377 }
 378
 379 /**
 380  * foo_canvas_update_bbox:
 381  * @canvas: the canvas needing update
 382  * @x1: Left coordinate of the new bounding box
 383  * @y1: Top coordinate of the new bounding box
 384  * @x2: Right coordinate of the new bounding box
 385  * @y2: Bottom coordinate of the new bounding box
 386  *
 387  * Sets the bbox to the new value, requesting full repaint.
 388  **/
 389 void
 390 foo_canvas_update_bbox (FooCanvasItem *item, int x1, int y1, int x2, int y2)
 391 {
 392         foo_canvas_item_request_redraw (item);
 393         item->x1 = x1;
 394         item->y1 = y1;
 395         item->x2 = x2;
 396         item->y2 = y2;
 397         foo_canvas_item_request_redraw (item);
 398 }
 399