1 /* GIMP - The GNU Image Manipulation Program
2 * Copyright (C) 1995-2001 Spencer Kimball, Peter Mattis, and others
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 3 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, see <https://www.gnu.org/licenses/>.
16 */
17
18 #include "config.h"
19
20 #include <string.h>
21
22 #include <gio/gio.h>
23 #include <gegl.h>
24
25 #include "libgimpmath/gimpmath.h"
26
27 #include "core-types.h"
28
29 #include "gimp-transform-resize.h"
30 #include "gimp-transform-utils.h"
31 #include "gimp-utils.h"
32
33
34 #if defined (HAVE_ISFINITE)
35 #define FINITE(x) isfinite(x)
36 #elif defined (HAVE_FINITE)
37 #define FINITE(x) finite(x)
38 #elif defined (G_OS_WIN32)
39 #define FINITE(x) _finite(x)
40 #else
41 #error "no FINITE() implementation available?!"
42 #endif
43
44 #define EPSILON 0.00000001
45
46
47 typedef struct
48 {
49 GimpVector2 a, b, c, d;
50 gdouble area;
51 gdouble aspect;
52 } Rectangle;
53
54
55 static void gimp_transform_resize_adjust (const GimpVector2 *points,
56 gint n_points,
57 gint *x1,
58 gint *y1,
59 gint *x2,
60 gint *y2);
61 static void gimp_transform_resize_crop (const GimpVector2 *points,
62 gint n_points,
63 gdouble aspect,
64 gint *x1,
65 gint *y1,
66 gint *x2,
67 gint *y2);
68
69 static void add_rectangle (const GimpVector2 *points,
70 gint n_points,
71 Rectangle *r,
72 GimpVector2 a,
73 GimpVector2 b,
74 GimpVector2 c,
75 GimpVector2 d);
76 static gboolean intersect (GimpVector2 a,
77 GimpVector2 b,
78 GimpVector2 c,
79 GimpVector2 d,
80 GimpVector2 *i);
81 static gboolean intersect_x (GimpVector2 a,
82 GimpVector2 b,
83 GimpVector2 c,
84 GimpVector2 *i);
85 static gboolean intersect_y (GimpVector2 a,
86 GimpVector2 b,
87 GimpVector2 c,
88 GimpVector2 *i);
89 static gboolean in_poly (const GimpVector2 *points,
90 gint n_points,
91 GimpVector2 p);
92 static gboolean point_on_border (const GimpVector2 *points,
93 gint n_points,
94 GimpVector2 p);
95
96 static void find_two_point_rectangle (Rectangle *r,
97 const GimpVector2 *points,
98 gint n_points,
99 gint p);
100 static void find_three_point_rectangle_corner (Rectangle *r,
101 const GimpVector2 *points,
102 gint n_points,
103 gint p);
104 static void find_three_point_rectangle (Rectangle *r,
105 const GimpVector2 *points,
106 gint n_points,
107 gint p);
108 static void find_three_point_rectangle_triangle (Rectangle *r,
109 const GimpVector2 *points,
110 gint n_points,
111 gint p);
112 static void find_maximum_aspect_rectangle (Rectangle *r,
113 const GimpVector2 *points,
114 gint n_points,
115 gint p);
116
117
118 /*
119 * This function wants to be passed the inverse transformation matrix!!
120 */
121 gboolean
gimp_transform_resize_boundary(const GimpMatrix3 * inv,GimpTransformResize resize,gdouble u1,gdouble v1,gdouble u2,gdouble v2,gint * x1,gint * y1,gint * x2,gint * y2)122 gimp_transform_resize_boundary (const GimpMatrix3 *inv,
123 GimpTransformResize resize,
124 gdouble u1,
125 gdouble v1,
126 gdouble u2,
127 gdouble v2,
128 gint *x1,
129 gint *y1,
130 gint *x2,
131 gint *y2)
132 {
133 GimpVector2 bounds[4];
134 GimpVector2 points[5];
135 gint n_points;
136 gboolean valid;
137 gint i;
138
139 g_return_val_if_fail (inv != NULL, FALSE);
140
141 /* initialize with the original boundary */
142 *x1 = floor (u1);
143 *y1 = floor (v1);
144 *x2 = ceil (u2);
145 *y2 = ceil (v2);
146
147 /* if clipping then just return the original rectangle */
148 if (resize == GIMP_TRANSFORM_RESIZE_CLIP)
149 return TRUE;
150
151 bounds[0] = (GimpVector2) { u1, v1 };
152 bounds[1] = (GimpVector2) { u2, v1 };
153 bounds[2] = (GimpVector2) { u2, v2 };
154 bounds[3] = (GimpVector2) { u1, v2 };
155
156 gimp_transform_polygon (inv, bounds, 4, TRUE,
157 points, &n_points);
158
159 valid = (n_points >= 2);
160
161 /* check if the transformation matrix is valid at all */
162 for (i = 0; i < n_points && valid; i++)
163 valid = (FINITE (points[i].x) && FINITE (points[i].y));
164
165 if (! valid)
166 {
167 /* since there is no sensible way to deal with this, just do the same as
168 * with GIMP_TRANSFORM_RESIZE_CLIP: return
169 */
170 return FALSE;
171 }
172
173 switch (resize)
174 {
175 case GIMP_TRANSFORM_RESIZE_ADJUST:
176 /* return smallest rectangle (with sides parallel to x- and y-axis)
177 * that surrounds the new points */
178 gimp_transform_resize_adjust (points, n_points,
179 x1, y1, x2, y2);
180 break;
181
182 case GIMP_TRANSFORM_RESIZE_CROP:
183 gimp_transform_resize_crop (points, n_points,
184 0.0,
185 x1, y1, x2, y2);
186 break;
187
188 case GIMP_TRANSFORM_RESIZE_CROP_WITH_ASPECT:
189 gimp_transform_resize_crop (points, n_points,
190 (u2 - u1) / (v2 - v1),
191 x1, y1, x2, y2);
192 break;
193
194 case GIMP_TRANSFORM_RESIZE_CLIP:
195 /* Remove warning about not handling all enum values. We handle
196 * this case in the beginning of the function
197 */
198 break;
199 }
200
201 /* ensure that resulting rectangle has at least area 1 */
202 if (*x1 == *x2)
203 (*x2)++;
204
205 if (*y1 == *y2)
206 (*y2)++;
207
208 return TRUE;
209 }
210
211 /* this calculates the smallest rectangle (with sides parallel to x- and
212 * y-axis) that contains the points d1 to d4
213 */
214 static void
gimp_transform_resize_adjust(const GimpVector2 * points,gint n_points,gint * x1,gint * y1,gint * x2,gint * y2)215 gimp_transform_resize_adjust (const GimpVector2 *points,
216 gint n_points,
217 gint *x1,
218 gint *y1,
219 gint *x2,
220 gint *y2)
221 {
222 GimpVector2 top_left;
223 GimpVector2 bottom_right;
224 gint i;
225
226 top_left = bottom_right = points[0];
227
228 for (i = 1; i < n_points; i++)
229 {
230 top_left.x = MIN (top_left.x, points[i].x);
231 top_left.y = MIN (top_left.y, points[i].y);
232
233 bottom_right.x = MAX (bottom_right.x, points[i].x);
234 bottom_right.y = MAX (bottom_right.y, points[i].y);
235 }
236
237 *x1 = (gint) floor (top_left.x + EPSILON);
238 *y1 = (gint) floor (top_left.y + EPSILON);
239
240 *x2 = (gint) ceil (bottom_right.x - EPSILON);
241 *y2 = (gint) ceil (bottom_right.y - EPSILON);
242 }
243
244 static void
gimp_transform_resize_crop(const GimpVector2 * orig_points,gint n_points,gdouble aspect,gint * x1,gint * y1,gint * x2,gint * y2)245 gimp_transform_resize_crop (const GimpVector2 *orig_points,
246 gint n_points,
247 gdouble aspect,
248 gint *x1,
249 gint *y1,
250 gint *x2,
251 gint *y2)
252 {
253 GimpVector2 points[5];
254 Rectangle r;
255 GimpVector2 t,a;
256 gint i, j;
257 gint min;
258
259 memcpy (points, orig_points, sizeof (GimpVector2) * n_points);
260
261 /* find lowest, rightmost corner of surrounding rectangle */
262 a.x = 0;
263 a.y = 0;
264 for (i = 0; i < 4; i++)
265 {
266 if (points[i].x < a.x)
267 a.x = points[i].x;
268
269 if (points[i].y < a.y)
270 a.y = points[i].y;
271 }
272
273 /* and translate all the points to the first quadrant */
274 for (i = 0; i < n_points; i++)
275 {
276 points[i].x += (-a.x) * 2;
277 points[i].y += (-a.y) * 2;
278 }
279
280 /* find the convex hull using Jarvis's March as the points are passed
281 * in different orders due to gimp_matrix3_transform_point()
282 */
283 min = 0;
284 for (i = 0; i < n_points; i++)
285 {
286 if (points[i].y < points[min].y)
287 min = i;
288 }
289
290 t = points[0];
291 points[0] = points[min];
292 points[min] = t;
293
294 for (i = 1; i < n_points - 1; i++)
295 {
296 gdouble min_theta;
297 gdouble min_mag;
298 int next;
299
300 next = n_points - 1;
301 min_theta = 2.0 * G_PI;
302 min_mag = DBL_MAX;
303
304 for (j = i; j < n_points; j++)
305 {
306 gdouble theta;
307 gdouble sy;
308 gdouble sx;
309 gdouble mag;
310
311 sy = points[j].y - points[i - 1].y;
312 sx = points[j].x - points[i - 1].x;
313
314 if ((sx == 0.0) && (sy == 0.0))
315 {
316 next = j;
317 break;
318 }
319
320 theta = atan2 (-sy, -sx);
321 mag = (sx * sx) + (sy * sy);
322
323 if ((theta < min_theta) ||
324 ((theta == min_theta) && (mag < min_mag)))
325 {
326 min_theta = theta;
327 min_mag = mag;
328 next = j;
329 }
330 }
331
332 t = points[i];
333 points[i] = points[next];
334 points[next] = t;
335 }
336
337 /* reverse the order of points */
338 for (i = 0; i < n_points / 2; i++)
339 {
340 t = points[i];
341 points[i] = points[n_points - i - 1];
342 points[n_points - i - 1] = t;
343 }
344
345 r.a.x = r.a.y = r.b.x = r.b.y = r.c.x = r.c.y = r.d.x = r.d.y = r.area = 0;
346 r.aspect = aspect;
347
348 if (aspect != 0)
349 {
350 for (i = 0; i < n_points; i++)
351 find_maximum_aspect_rectangle (&r, points, n_points, i);
352 }
353 else
354 {
355 for (i = 0; i < n_points; i++)
356 {
357 find_three_point_rectangle (&r, points, n_points, i);
358 find_three_point_rectangle_corner (&r, points, n_points, i);
359 find_two_point_rectangle (&r, points, n_points, i);
360 find_three_point_rectangle_triangle (&r, points, n_points, i);
361 }
362 }
363
364 if (r.area == 0)
365 {
366 /* saveguard if something went wrong, adjust and give warning */
367 gimp_transform_resize_adjust (orig_points, n_points,
368 x1, y1, x2, y2);
369 g_printerr ("no rectangle found by algorithm, no cropping done\n");
370 return;
371 }
372 else
373 {
374 /* round and translate the calculated points back */
375 *x1 = floor (r.a.x + 0.5);
376 *y1 = floor (r.a.y + 0.5);
377 *x2 = ceil (r.c.x - 0.5);
378 *y2 = ceil (r.c.y - 0.5);
379
380 *x1 = *x1 - ((-a.x) * 2);
381 *y1 = *y1 - ((-a.y) * 2);
382 *x2 = *x2 - ((-a.x) * 2);
383 *y2 = *y2 - ((-a.y) * 2);
384 return;
385 }
386 }
387
388 static void
find_three_point_rectangle(Rectangle * r,const GimpVector2 * points,gint n_points,gint p)389 find_three_point_rectangle (Rectangle *r,
390 const GimpVector2 *points,
391 gint n_points,
392 gint p)
393 {
394 GimpVector2 a = points[p % n_points]; /* 0 1 2 3 */
395 GimpVector2 b = points[(p + 1) % n_points]; /* 1 2 3 0 */
396 GimpVector2 c = points[(p + 2) % n_points]; /* 2 3 0 1 */
397 GimpVector2 d = points[(p + 3) % n_points]; /* 3 0 1 2 */
398 GimpVector2 i1; /* intersection point */
399 GimpVector2 i2; /* intersection point */
400 GimpVector2 i3; /* intersection point */
401
402 if (intersect_x (b, c, a, &i1) &&
403 intersect_y (c, d, i1, &i2) &&
404 intersect_x (d, a, i2, &i3))
405 add_rectangle (points, n_points, r, i3, i3, i1, i1);
406
407 if (intersect_y (b, c, a, &i1) &&
408 intersect_x (c, d, i1, &i2) &&
409 intersect_y (d, a, i2, &i3))
410 add_rectangle (points, n_points, r, i3, i3, i1, i1);
411
412 if (intersect_x (d, c, a, &i1) &&
413 intersect_y (c, b, i1, &i2) &&
414 intersect_x (b, a, i2, &i3))
415 add_rectangle (points, n_points, r, i3, i3, i1, i1);
416
417 if (intersect_y (d, c, a, &i1) &&
418 intersect_x (c, b, i1, &i2) &&
419 intersect_y (b, a, i2, &i3))
420 add_rectangle (points, n_points, r, i3, i3, i1, i1);
421 }
422
423 static void
find_three_point_rectangle_corner(Rectangle * r,const GimpVector2 * points,gint n_points,gint p)424 find_three_point_rectangle_corner (Rectangle *r,
425 const GimpVector2 *points,
426 gint n_points,
427 gint p)
428 {
429 GimpVector2 a = points[p % n_points]; /* 0 1 2 3 */
430 GimpVector2 b = points[(p + 1) % n_points]; /* 1 2 3 0 */
431 GimpVector2 c = points[(p + 2) % n_points]; /* 2 3 0 2 */
432 GimpVector2 d = points[(p + 3) % n_points]; /* 3 0 2 1 */
433 GimpVector2 i1; /* intersection point */
434 GimpVector2 i2; /* intersection point */
435
436 if (intersect_x (b, c, a , &i1) &&
437 intersect_y (c, d, i1, &i2))
438 add_rectangle (points, n_points, r, a, a, i1, i2);
439
440 if (intersect_y (b, c, a , &i1) &&
441 intersect_x (c, d, i1, &i2))
442 add_rectangle (points, n_points, r, a, a, i1, i2);
443
444 if (intersect_x (c, d, a , &i1) &&
445 intersect_y (b, c, i1, &i2))
446 add_rectangle (points, n_points, r, a, a, i1, i2);
447
448 if (intersect_y (c, d, a , &i1) &&
449 intersect_x (b, c, i1, &i2))
450 add_rectangle (points, n_points, r, a, a, i1, i2);
451 }
452
453 static void
find_two_point_rectangle(Rectangle * r,const GimpVector2 * points,gint n_points,gint p)454 find_two_point_rectangle (Rectangle *r,
455 const GimpVector2 *points,
456 gint n_points,
457 gint p)
458 {
459 GimpVector2 a = points[ p % n_points]; /* 0 1 2 3 */
460 GimpVector2 b = points[(p + 1) % n_points]; /* 1 2 3 0 */
461 GimpVector2 c = points[(p + 2) % n_points]; /* 2 3 0 1 */
462 GimpVector2 d = points[(p + 3) % n_points]; /* 3 0 1 2 */
463 GimpVector2 i1; /* intersection point */
464 GimpVector2 i2; /* intersection point */
465 GimpVector2 mid; /* Mid point */
466
467 add_rectangle (points, n_points, r, a, a, c, c);
468 add_rectangle (points, n_points, r, b, b, d, d);
469
470 if (intersect_x (c, b, a, &i1) &&
471 intersect_y (c, b, a, &i2))
472 {
473 mid.x = ( i1.x + i2.x ) / 2.0;
474 mid.y = ( i1.y + i2.y ) / 2.0;
475
476 add_rectangle (points, n_points, r, a, a, mid, mid);
477 }
478 }
479
480 static void
find_three_point_rectangle_triangle(Rectangle * r,const GimpVector2 * points,gint n_points,gint p)481 find_three_point_rectangle_triangle (Rectangle *r,
482 const GimpVector2 *points,
483 gint n_points,
484 gint p)
485 {
486 GimpVector2 a = points[p % n_points]; /* 0 1 2 3 */
487 GimpVector2 b = points[(p + 1) % n_points]; /* 1 2 3 0 */
488 GimpVector2 c = points[(p + 2) % n_points]; /* 2 3 0 1 */
489 GimpVector2 d = points[(p + 3) % n_points]; /* 3 0 1 2 */
490 GimpVector2 i1; /* intersection point */
491 GimpVector2 i2; /* intersection point */
492 GimpVector2 mid;
493
494 mid.x = (a.x + b.x) / 2.0;
495 mid.y = (a.y + b.y) / 2.0;
496
497 if (intersect_x (b, c, mid, &i1) &&
498 intersect_y (a, d, mid, &i2))
499 add_rectangle (points, n_points, r, mid, mid, i1, i2);
500
501 if (intersect_y (b, c, mid, &i1) &&
502 intersect_x (a, d, mid, &i2))
503 add_rectangle (points, n_points, r, mid, mid, i1, i2);
504
505 if (intersect_x (a, d, mid, &i1) &&
506 intersect_y (b, c, mid, &i2))
507 add_rectangle (points, n_points, r, mid, mid, i1, i2);
508
509 if (intersect_y (a, d, mid, &i1) &&
510 intersect_x (b, c, mid, &i2))
511 add_rectangle (points, n_points, r, mid, mid, i1, i2);
512 }
513
514 static void
find_maximum_aspect_rectangle(Rectangle * r,const GimpVector2 * points,gint n_points,gint p)515 find_maximum_aspect_rectangle (Rectangle *r,
516 const GimpVector2 *points,
517 gint n_points,
518 gint p)
519 {
520 GimpVector2 a = points[ p % n_points]; /* 0 1 2 3 */
521 GimpVector2 b = points[(p + 1) % n_points]; /* 1 2 3 0 */
522 GimpVector2 c = points[(p + 2) % n_points]; /* 2 3 0 1 */
523 GimpVector2 d = points[(p + 3) % n_points]; /* 3 0 1 2 */
524 GimpVector2 i1; /* intersection point */
525 GimpVector2 i2; /* intersection point */
526 GimpVector2 i3; /* intersection point */
527
528 if (intersect_x (b, c, a, &i1))
529 {
530 i2.x = i1.x + 1.0 * r->aspect;
531 i2.y = i1.y + 1.0;
532
533 if (intersect (d, a, i1, i2, &i3))
534 add_rectangle (points, n_points, r, i1, i3, i1, i3);
535
536 if (intersect (a, b, i1, i2, &i3))
537 add_rectangle (points, n_points, r, i1, i3, i1, i3);
538
539 if (intersect (c, d, i1, i2, &i3))
540 add_rectangle (points, n_points, r, i1, i3, i1, i3);
541
542 i2.x = i1.x - 1.0 * r->aspect;
543 i2.y = i1.y + 1.0;
544
545 if (intersect (d, a, i1, i2, &i3))
546 add_rectangle (points, n_points, r, i1, i3, i1, i3);
547
548 if (intersect (a, b, i1, i2, &i3))
549 add_rectangle (points, n_points, r, i1, i3, i1, i3);
550
551 if (intersect (c, d, i1, i2, &i3))
552 add_rectangle (points, n_points, r, i1, i3, i1, i3);
553 }
554
555 if (intersect_y (b, c, a, &i1))
556 {
557 i2.x = i1.x + 1.0 * r->aspect;
558 i2.y = i1.y + 1.0;
559
560 if (intersect (d, a, i1, i2, &i3))
561 add_rectangle (points, n_points, r, i1, i3, i1, i3);
562
563 if (intersect (a, b, i1, i2, &i3))
564 add_rectangle (points, n_points, r, i1, i3, i1, i3);
565
566 if (intersect (c, d, i1, i2, &i3))
567 add_rectangle (points, n_points, r, i1, i3, i1, i3);
568
569 i2.x = i1.x - 1.0 * r->aspect;
570 i2.y = i1.y + 1.0;
571
572 if (intersect (d, a, i1, i2, &i3))
573 add_rectangle (points, n_points, r, i1, i3, i1, i3);
574
575 if (intersect (a, b, i1, i2, &i3))
576 add_rectangle (points, n_points, r, i1, i3, i1, i3);
577
578 if (intersect (c, d, i1, i2, &i3))
579 add_rectangle (points, n_points, r, i1, i3, i1, i3);
580 }
581
582 if (intersect_x (c, d, a, &i1))
583 {
584 i2.x = i1.x + 1.0 * r->aspect;
585 i2.y = i1.y + 1.0;
586
587 if (intersect (d, a, i1, i2, &i3))
588 add_rectangle (points, n_points, r, i1, i3, i1, i3);
589
590 if (intersect (a, b, i1, i2, &i3))
591 add_rectangle (points, n_points, r, i1, i3, i1, i3);
592
593 if (intersect (b, c, i1, i2, &i3))
594 add_rectangle (points, n_points, r, i1, i3, i1, i3);
595
596 i2.x = i1.x - 1.0 * r->aspect;
597 i2.y = i1.y + 1.0;
598
599 if (intersect (d, a, i1, i2, &i3))
600 add_rectangle (points, n_points, r, i1, i3, i1, i3);
601
602 if (intersect (a, b, i1, i2, &i3))
603 add_rectangle (points, n_points, r, i1, i3, i1, i3);
604
605 if (intersect (b, c, i1, i2, &i3))
606 add_rectangle (points, n_points, r, i1, i3, i1, i3);
607 }
608
609 if (intersect_y (c, d, a, &i1))
610 {
611 i2.x = i1.x + 1.0 * r->aspect;
612 i2.y = i1.y + 1.0;
613
614 if (intersect (d, a, i1, i2, &i3))
615 add_rectangle (points, n_points, r, i1, i3, i1, i3);
616
617 if (intersect (a, b, i1, i2, &i3))
618 add_rectangle (points, n_points, r, i1, i3, i1, i3);
619
620 if (intersect (b, c, i1, i2, &i3))
621 add_rectangle (points, n_points, r, i1, i3, i1, i3);
622
623 i2.x = i1.x - 1.0 * r->aspect;
624 i2.y = i1.y + 1.0;
625
626 if (intersect (d, a, i1, i2, &i3))
627 add_rectangle (points, n_points, r, i1, i3, i1, i3);
628
629 if (intersect (a, b, i1, i2, &i3))
630 add_rectangle (points, n_points, r, i1, i3, i1, i3);
631
632 if (intersect (b, c, i1, i2, &i3))
633 add_rectangle (points, n_points, r, i1, i3, i1, i3);
634 }
635 }
636
637 /* check if point is inside the polygon "points", if point is on border
638 * its still inside.
639 */
640 static gboolean
in_poly(const GimpVector2 * points,gint n_points,GimpVector2 p)641 in_poly (const GimpVector2 *points,
642 gint n_points,
643 GimpVector2 p)
644 {
645 GimpVector2 p1, p2;
646 gint counter = 0;
647 gint i;
648
649 p1 = points[0];
650
651 for (i = 1; i <= n_points; i++)
652 {
653 p2 = points[i % n_points];
654
655 if (p.y > MIN (p1.y, p2.y))
656 {
657 if (p.y <= MAX (p1.y, p2.y))
658 {
659 if (p.x <= MAX (p1.x, p2.x))
660 {
661 if (p1.y != p2.y)
662 {
663 gdouble xinters = ((p.y - p1.y) * (p2.x - p1.x) /
664 (p2.y - p1.y) + p1.x);
665
666 if (p1.x == p2.x || p.x <= xinters)
667 counter++;
668 }
669 }
670 }
671 }
672
673 p1 = p2;
674 }
675
676 /* border check */
677 if (point_on_border (points, n_points, p))
678 return TRUE;
679
680 return (counter % 2 != 0);
681 }
682
683 /* check if the point p lies on the polygon "points"
684 */
685 static gboolean
point_on_border(const GimpVector2 * points,gint n_points,GimpVector2 p)686 point_on_border (const GimpVector2 *points,
687 gint n_points,
688 GimpVector2 p)
689 {
690 gint i;
691
692 for (i = 0; i <= n_points; i++)
693 {
694 GimpVector2 a = points[i % n_points];
695 GimpVector2 b = points[(i + 1) % n_points];
696 gdouble a1 = (b.y - a.y);
697 gdouble b1 = (a.x - b.x);
698 gdouble c1 = a1 * a.x + b1 * a.y;
699 gdouble c2 = a1 * p.x + b1 * p.y;
700
701 if (ABS (c1 - c2) < EPSILON &&
702 MIN (a.x, b.x) <= p.x &&
703 MAX (a.x, b.x) >= p.x &&
704 MIN (a.y, b.y) <= p.y &&
705 MAX (a.y, b.y) >= p.y)
706 return TRUE;
707 }
708
709 return FALSE;
710 }
711
712 /* calculate the intersection point of the line a-b with the line c-d
713 * and write it to i, if existing.
714 */
715 static gboolean
intersect(GimpVector2 a,GimpVector2 b,GimpVector2 c,GimpVector2 d,GimpVector2 * i)716 intersect (GimpVector2 a,
717 GimpVector2 b,
718 GimpVector2 c,
719 GimpVector2 d,
720 GimpVector2 *i)
721 {
722 gdouble a1 = (b.y - a.y);
723 gdouble b1 = (a.x - b.x);
724 gdouble c1 = a1 * a.x + b1 * a.y;
725
726 gdouble a2 = (d.y - c.y);
727 gdouble b2 = (c.x - d.x);
728 gdouble c2 = a2 * c.x + b2 * c.y;
729 gdouble det = a1 * b2 - a2 * b1;
730
731 if (det == 0)
732 return FALSE;
733
734 i->x = (b2 * c1 - b1 * c2) / det;
735 i->y = (a1 * c2 - a2 * c1) / det;
736
737 return TRUE;
738 }
739
740 /* calculate the intersection point of the line a-b with the vertical line
741 * through c and write it to i, if existing.
742 */
743 static gboolean
intersect_x(GimpVector2 a,GimpVector2 b,GimpVector2 c,GimpVector2 * i)744 intersect_x (GimpVector2 a,
745 GimpVector2 b,
746 GimpVector2 c,
747 GimpVector2 *i)
748 {
749 GimpVector2 d = c;
750 d.y += 1;
751
752 return intersect(a,b,c,d,i);
753 }
754
755 /* calculate the intersection point of the line a-b with the horizontal line
756 * through c and write it to i, if existing.
757 */
758 static gboolean
intersect_y(GimpVector2 a,GimpVector2 b,GimpVector2 c,GimpVector2 * i)759 intersect_y (GimpVector2 a,
760 GimpVector2 b,
761 GimpVector2 c,
762 GimpVector2 *i)
763 {
764 GimpVector2 d = c;
765 d.x += 1;
766
767 return intersect(a,b,c,d,i);
768 }
769
770 /* this takes the smallest ortho-aligned (the sides of the rectangle are
771 * parallel to the x- and y-axis) rectangle fitting around the points a to d,
772 * checks if the whole rectangle is inside the polygon described by points and
773 * writes it to r if the area is bigger than the rectangle already stored in r.
774 */
775 static void
add_rectangle(const GimpVector2 * points,gint n_points,Rectangle * r,GimpVector2 a,GimpVector2 b,GimpVector2 c,GimpVector2 d)776 add_rectangle (const GimpVector2 *points,
777 gint n_points,
778 Rectangle *r,
779 GimpVector2 a,
780 GimpVector2 b,
781 GimpVector2 c,
782 GimpVector2 d)
783 {
784 gdouble width;
785 gdouble height;
786 gdouble minx, maxx;
787 gdouble miny, maxy;
788
789 /* get the orthoaligned (the sides of the rectangle are parallel to the x-
790 * and y-axis) rectangle surrounding the points a to d.
791 */
792 minx = MIN4 (a.x, b.x, c.x, d.x);
793 maxx = MAX4 (a.x, b.x, c.x, d.x);
794 miny = MIN4 (a.y, b.y, c.y, d.y);
795 maxy = MAX4 (a.y, b.y, c.y, d.y);
796
797 a.x = minx;
798 a.y = miny;
799
800 b.x = maxx;
801 b.y = miny;
802
803 c.x = maxx;
804 c.y = maxy;
805
806 d.x = minx;
807 d.y = maxy;
808
809 width = maxx - minx;
810 height = maxy - miny;
811
812 /* check if this rectangle is inside the polygon "points" */
813 if (in_poly (points, n_points, a) &&
814 in_poly (points, n_points, b) &&
815 in_poly (points, n_points, c) &&
816 in_poly (points, n_points, d))
817 {
818 gdouble area = width * height;
819
820 /* check if the new rectangle is larger (in terms of area)
821 * than the currently stored rectangle in r, if yes store
822 * new rectangle to r
823 */
824 if (r->area <= area)
825 {
826 r->a.x = a.x;
827 r->a.y = a.y;
828
829 r->b.x = b.x;
830 r->b.y = b.y;
831
832 r->c.x = c.x;
833 r->c.y = c.y;
834
835 r->d.x = d.x;
836 r->d.y = d.y;
837
838 r->area = area;
839 }
840 }
841 }
842