1 /* Dia -- an diagram creation/manipulation program
2 * Copyright (C) 1998 Alexander Larsson
4 * Matrix code from GIMP:app/transform_tool.c
5 * Copyright (C) 1995 Spencer Kimball and Peter Mattis
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program 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
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 /* include glib.h first, so we don't pick up its inline functions as well */
26 /* include normal versions of the inlined functions here ... */
28 #define G_INLINE_FUNC extern
29 #define G_CAN_INLINE 1
33 rectangle_union(Rectangle
*r1
, const Rectangle
*r2
)
35 r1
->top
= MIN( r1
->top
, r2
->top
);
36 r1
->bottom
= MAX( r1
->bottom
, r2
->bottom
);
37 r1
->left
= MIN( r1
->left
, r2
->left
);
38 r1
->right
= MAX( r1
->right
, r2
->right
);
42 int_rectangle_union(IntRectangle
*r1
, const IntRectangle
*r2
)
44 r1
->top
= MIN( r1
->top
, r2
->top
);
45 r1
->bottom
= MAX( r1
->bottom
, r2
->bottom
);
46 r1
->left
= MIN( r1
->left
, r2
->left
);
47 r1
->right
= MAX( r1
->right
, r2
->right
);
51 rectangle_intersection(Rectangle
*r1
, const Rectangle
*r2
)
53 r1
->top
= MAX( r1
->top
, r2
->top
);
54 r1
->bottom
= MIN( r1
->bottom
, r2
->bottom
);
55 r1
->left
= MAX( r1
->left
, r2
->left
);
56 r1
->right
= MIN( r1
->right
, r2
->right
);
58 /* Is rectangle empty? */
59 if ( (r1
->top
>= r1
->bottom
) ||
60 (r1
->left
>= r1
->right
) ) {
61 r1
->top
= r1
->bottom
= r1
->left
= r1
->right
= 0.0;
66 rectangle_intersects(const Rectangle
*r1
, const Rectangle
*r2
)
68 if ( (r1
->right
< r2
->left
) ||
69 (r1
->left
> r2
->right
) ||
70 (r1
->top
> r2
->bottom
) ||
71 (r1
->bottom
< r2
->top
) )
78 point_in_rectangle(const Rectangle
* r
, const Point
*p
)
80 if ( (p
->x
< r
->left
) ||
90 rectangle_in_rectangle(const Rectangle
* outer
, const Rectangle
*inner
)
92 if ( (inner
->left
< outer
->left
) ||
93 (inner
->right
> outer
->right
) ||
94 (inner
->top
< outer
->top
) ||
95 (inner
->bottom
> outer
->bottom
))
102 rectangle_add_point(Rectangle
*r
, const Point
*p
)
106 else if (p
->x
> r
->right
)
111 else if (p
->y
> r
->bottom
)
117 * This function estimates the distance from a point to a rectangle.
118 * If the point is in the rectangle, 0.0 is returned. Otherwise the
119 * distance in a manhattan metric from the point to the nearest point
120 * on the rectangle is returned.
123 distance_rectangle_point(const Rectangle
*rect
, const Point
*point
)
128 if (point
->x
< rect
->left
) {
129 dx
= rect
->left
- point
->x
;
130 } else if (point
->x
> rect
->right
) {
131 dx
= point
->x
- rect
->right
;
134 if (point
->y
< rect
->top
) {
135 dy
= rect
->top
- point
->y
;
136 } else if (point
->y
> rect
->bottom
) {
137 dy
= point
->y
- rect
->bottom
;
144 * This function estimates the distance from a point to a line segment
145 * specified by two endpoints.
146 * If the point is on the line segment, 0.0 is returned. Otherwise the
147 * distance in the R^2 metric from the point to the nearest point
148 * on the line segment is returned. Does one sqrt per call.
149 * Philosophical bug: line_width is ignored iff point is beyond
150 * end of line segment.
153 distance_line_point(const Point
*line_start
, const Point
*line_end
,
154 real line_width
, const Point
*point
)
162 point_sub(&v1
,line_start
);
165 point_sub(&v2
, line_start
);
167 v1_lensq
= point_dot(&v1
,&v1
);
169 if (v1_lensq
<0.000001) {
170 return sqrt(point_dot(&v2
,&v2
));
173 projlen
= point_dot(&v1
,&v2
) / v1_lensq
;
176 return sqrt(point_dot(&v2
,&v2
));
181 point_sub(&v3
,line_end
);
182 return sqrt(point_dot(&v3
,&v3
));
185 point_scale(&v1
, projlen
);
188 perp_dist
= sqrt(point_dot(&v1
,&v1
));
190 perp_dist
-= line_width
/ 2.0;
191 if (perp_dist
< 0.0) {
198 /* returns 1 iff the line crosses the ray from (-Inf, rayend.y) to rayend */
200 line_crosses_ray(const Point
*line_start
,
201 const Point
*line_end
, const Point
*rayend
)
205 /* swap end points if necessary */
206 if (line_start
->y
> line_end
->y
) {
210 line_start
= line_end
;
213 /* if y coords of line do not include rayend.y */
214 if (line_start
->y
> rayend
->y
|| line_end
->y
< rayend
->y
)
216 /* Avoid division by zero */
217 if (line_end
->y
- line_start
->y
< 0.00000000001) {
218 return line_end
->y
- rayend
->y
< 0.00000000001;
220 xpos
= line_start
->x
+ (rayend
->y
- line_start
->y
) *
221 (line_end
->x
- line_start
->x
) / (line_end
->y
- line_start
->y
);
222 return xpos
<= rayend
->x
;
226 distance_polygon_point(const Point
*poly
, guint npoints
, real line_width
,
229 guint i
, last
= npoints
- 1;
230 real line_dist
= G_MAXFLOAT
;
233 /* calculate ray crossings and line distances */
234 for (i
= 0; i
< npoints
; i
++) {
237 crossings
+= line_crosses_ray(&poly
[last
], &poly
[i
], point
);
238 dist
= distance_line_point(&poly
[last
], &poly
[i
], line_width
, point
);
239 line_dist
= MIN(line_dist
, dist
);
242 /* If there is an odd number of ray crossings, we are inside the polygon.
243 * Otherwise, return the minium distance from a line segment */
244 if (crossings
% 2 == 1)
250 /* number of segments to use in bezier curve approximation */
253 /* if cross is not NULL, it will be incremented for each ray crossing */
255 bez_point_distance_and_ray_crosses(const Point
*b1
,
256 const Point
*b2
, const Point
*b3
,
258 real line_width
, const Point
*point
,
261 static gboolean calculated_coeff
= FALSE
;
262 static real coeff
[NBEZ_SEGS
+1][4];
264 real line_dist
= G_MAXFLOAT
;
267 if (!calculated_coeff
) {
268 for (i
= 0; i
<= NBEZ_SEGS
; i
++) {
269 real t1
= ((real
)i
)/NBEZ_SEGS
, t2
= t1
*t1
, t3
= t1
*t2
;
270 real it1
= 1-t1
, it2
= it1
*it1
, it3
= it1
*it2
;
273 coeff
[i
][1] = 3 * t1
* it2
;
274 coeff
[i
][2] = 3 * t2
* it1
;
278 calculated_coeff
= TRUE
;
280 prev
.x
= coeff
[0][0] * b1
->x
+ coeff
[0][1] * b2
->x
+
281 coeff
[0][2] * b3
->x
+ coeff
[0][3] * b4
->x
;
282 prev
.y
= coeff
[0][0] * b1
->y
+ coeff
[0][1] * b2
->y
+
283 coeff
[0][2] * b3
->y
+ coeff
[0][3] * b4
->y
;
284 for (i
= 1; i
<= NBEZ_SEGS
; i
++) {
287 pt
.x
= coeff
[i
][0] * b1
->x
+ coeff
[i
][1] * b2
->x
+
288 coeff
[i
][2] * b3
->x
+ coeff
[i
][3] * b4
->x
;
289 pt
.y
= coeff
[i
][0] * b1
->y
+ coeff
[i
][1] * b2
->y
+
290 coeff
[i
][2] * b3
->y
+ coeff
[i
][3] * b4
->y
;
292 dist
= distance_line_point(&prev
, &pt
, line_width
, point
);
293 line_dist
= MIN(line_dist
, dist
);
295 *cross
+= line_crosses_ray(&prev
, &pt
, point
);
303 distance_bez_seg_point(const Point
*b1
, const Point
*b2
,
304 const Point
*b3
, const Point
*b4
,
305 real line_width
, const Point
*point
)
307 return bez_point_distance_and_ray_crosses(b1
, b2
, b3
, b4
,
308 line_width
, point
, NULL
);
312 distance_bez_line_point(const BezPoint
*b
, guint npoints
,
313 real line_width
, const Point
*point
)
317 real line_dist
= G_MAXFLOAT
;
319 g_return_val_if_fail(b
[0].type
== BEZ_MOVE_TO
, -1);
323 for (i
= 1; i
< npoints
; i
++) {
328 /*g_assert_not_reached();*/
329 g_warning("BEZ_MOVE_TO found half way through a bezier line");
332 dist
= distance_line_point(&last
, &b
[i
].p1
, line_width
, point
);
333 line_dist
= MIN(line_dist
, dist
);
337 dist
= bez_point_distance_and_ray_crosses(&last
, &b
[i
].p1
, &b
[i
].p2
,
338 &b
[i
].p3
, line_width
, point
,
340 line_dist
= MIN(line_dist
, dist
);
349 distance_bez_shape_point(const BezPoint
*b
, guint npoints
,
350 real line_width
, const Point
*point
)
354 real line_dist
= G_MAXFLOAT
;
357 g_return_val_if_fail(b
[0].type
== BEZ_MOVE_TO
, -1);
361 for (i
= 1; i
< npoints
; i
++) {
366 /*g_assert_not_reached();*/
367 g_warning("BEZ_MOVE_TO found half way through a bezier shape");
370 dist
= distance_line_point(&last
, &b
[i
].p1
, line_width
, point
);
371 crossings
+= line_crosses_ray(&last
, &b
[i
].p1
, point
);
372 line_dist
= MIN(line_dist
, dist
);
376 dist
= bez_point_distance_and_ray_crosses(&last
, &b
[i
].p1
, &b
[i
].p2
,
377 &b
[i
].p3
, line_width
, point
,
379 line_dist
= MIN(line_dist
, dist
);
384 /* If there is an odd number of ray crossings, we are inside the polygon.
385 * Otherwise, return the minium distance from a line segment */
386 if (crossings
% 2 == 1)
393 distance_ellipse_point(const Point
*centre
, real width
, real height
,
394 real line_width
, const Point
*point
)
396 real w2
= width
*width
, h2
= height
*height
;
397 real scale
, rad
, dist
;
400 /* find the radius of the ellipse in the appropriate direction */
402 /* find the point of intersection between line (x=cx+(px-cx)t; y=cy+(py-cy)t)
403 * and ellipse ((x-cx)^2)/(w/2)^2 + ((y-cy)^2)/(h/2)^2 = 1 */
404 /* radius along ray is sqrt((px-cx)^2 * t^2 + (py-cy)^2 * t^2) */
407 point_sub(&pt
, centre
);
409 pt
.y
*= pt
.y
; /* pt = (point - centre).^2 */
411 scale
= w2
* h2
/ (4*h2
*pt
.x
+ 4*w2
*pt
.y
);
412 rad
= sqrt((pt
.x
+ pt
.y
)*scale
) + line_width
/2;
414 dist
= sqrt(pt
.x
+ pt
.y
);
424 transform_point (Matrix m
, Point
*src
, Point
*dest
)
428 xx
= m
[0][0] * src
->x
+ m
[0][1] * src
->y
+ m
[0][2];
429 yy
= m
[1][0] * src
->x
+ m
[1][1] * src
->y
+ m
[1][2];
430 ww
= m
[2][0] * src
->x
+ m
[2][1] * src
->y
+ m
[2][2];
440 mult_matrix (Matrix m1
, Matrix m2
)
445 for (i
= 0; i
< 3; i
++)
446 for (j
= 0; j
< 3; j
++)
449 for (k
= 0; k
< 3; k
++)
450 result
[i
][j
] += m1
[i
][k
] * m2
[k
][j
];
453 /* copy the result into matrix 2 */
454 for (i
= 0; i
< 3; i
++)
455 for (j
= 0; j
< 3; j
++)
456 m2
[i
][j
] = result
[i
][j
];
460 identity_matrix (Matrix m
)
464 for (i
= 0; i
< 3; i
++)
465 for (j
= 0; j
< 3; j
++)
466 m
[i
][j
] = (i
== j
) ? 1 : 0;
471 translate_matrix (Matrix m
, real x
, real y
)
475 identity_matrix (trans
);
478 mult_matrix (trans
, m
);
482 scale_matrix (Matrix m
, real x
, real y
)
486 identity_matrix (scale
);
489 mult_matrix (scale
, m
);
493 rotate_matrix (Matrix m
, real theta
)
496 real cos_theta
, sin_theta
;
498 cos_theta
= cos (theta
);
499 sin_theta
= sin (theta
);
501 identity_matrix (rotate
);
502 rotate
[0][0] = cos_theta
;
503 rotate
[0][1] = -sin_theta
;
504 rotate
[1][0] = sin_theta
;
505 rotate
[1][1] = cos_theta
;
506 mult_matrix (rotate
, m
);
510 xshear_matrix (Matrix m
, real shear
)
514 identity_matrix (shear_m
);
515 shear_m
[0][1] = shear
;
516 mult_matrix (shear_m
, m
);
520 yshear_matrix (Matrix m
, real shear
)
524 identity_matrix (shear_m
);
525 shear_m
[1][0] = shear
;
526 mult_matrix (shear_m
, m
);
529 /* find the determinate for a 3x3 matrix */
531 determinate (Matrix m
)
536 for (i
= 0; i
< 3; i
++)
538 det
+= m
[0][i
] * m
[1][(i
+1)%3] * m
[2][(i
+2)%3];
539 det
-= m
[2][i
] * m
[1][(i
+1)%3] * m
[0][(i
+2)%3];