Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/source/fitz/geometry.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 // Copyright (C) 2004-2025 Artifex Software, Inc.
2 //
3 // This file is part of MuPDF.
4 //
5 // MuPDF is free software: you can redistribute it and/or modify it under the
6 // terms of the GNU Affero General Public License as published by the Free
7 // Software Foundation, either version 3 of the License, or (at your option)
8 // any later version.
9 //
10 // MuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 // FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
13 // details.
14 //
15 // You should have received a copy of the GNU Affero General Public License
16 // along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>
17 //
18 // Alternative licensing terms are available from the licensor.
19 // For commercial licensing, see <https://www.artifex.com/> or contact
20 // Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
21 // CA 94129, USA, for further information.
22
23 #include "mupdf/fitz.h"
24
25 #include <math.h>
26 #include <float.h>
27 #include <limits.h>
28
29 #define MAX4(a,b,c,d) fz_max(fz_max(a,b), fz_max(c,d))
30 #define MIN4(a,b,c,d) fz_min(fz_min(a,b), fz_min(c,d))
31
32 /* A useful macro to add with overflow detection and clamping.
33
34 We want to do "b = a + x", but to allow for overflow. Consider the
35 top bits, and the cases in which overflow occurs:
36
37 overflow a x b ~a^x a^b (~a^x)&(a^b)
38 no 0 0 0 1 0 0
39 yes 0 0 1 1 1 1
40 no 0 1 0 0 0 0
41 no 0 1 1 0 1 0
42 no 1 0 0 0 1 0
43 no 1 0 1 0 0 0
44 yes 1 1 0 1 1 1
45 no 1 1 1 1 0 0
46 */
47 #define ADD_WITH_SAT(b,a,x) \
48 ((b) = (a) + (x), (b) = (((~(a)^(x))&((a)^(b))) < 0 ? ((x) < 0 ? INT_MIN : INT_MAX) : (b)))
49
50 /* Matrices, points and affine transformations */
51
52 const fz_matrix fz_identity = { 1, 0, 0, 1, 0, 0 };
53
54 fz_matrix
55 fz_concat(fz_matrix one, fz_matrix two)
56 {
57 fz_matrix dst;
58 dst.a = one.a * two.a + one.b * two.c;
59 dst.b = one.a * two.b + one.b * two.d;
60 dst.c = one.c * two.a + one.d * two.c;
61 dst.d = one.c * two.b + one.d * two.d;
62 dst.e = one.e * two.a + one.f * two.c + two.e;
63 dst.f = one.e * two.b + one.f * two.d + two.f;
64 return dst;
65 }
66
67 fz_matrix
68 fz_scale(float sx, float sy)
69 {
70 fz_matrix m;
71 m.a = sx; m.b = 0;
72 m.c = 0; m.d = sy;
73 m.e = 0; m.f = 0;
74 return m;
75 }
76
77 fz_matrix
78 fz_pre_scale(fz_matrix m, float sx, float sy)
79 {
80 m.a *= sx;
81 m.b *= sx;
82 m.c *= sy;
83 m.d *= sy;
84 return m;
85 }
86
87 fz_matrix
88 fz_post_scale(fz_matrix m, float sx, float sy)
89 {
90 m.a *= sx;
91 m.b *= sy;
92 m.c *= sx;
93 m.d *= sy;
94 m.e *= sx;
95 m.f *= sy;
96 return m;
97 }
98
99 fz_matrix
100 fz_shear(float h, float v)
101 {
102 fz_matrix m;
103 m.a = 1; m.b = v;
104 m.c = h; m.d = 1;
105 m.e = 0; m.f = 0;
106 return m;
107 }
108
109 fz_matrix
110 fz_pre_shear(fz_matrix m, float h, float v)
111 {
112 float a = m.a;
113 float b = m.b;
114 m.a += v * m.c;
115 m.b += v * m.d;
116 m.c += h * a;
117 m.d += h * b;
118 return m;
119 }
120
121 fz_matrix
122 fz_rotate(float theta)
123 {
124 fz_matrix m;
125 float s;
126 float c;
127
128 while (theta < 0)
129 theta += 360;
130 while (theta >= 360)
131 theta -= 360;
132
133 if (fabsf(0 - theta) < FLT_EPSILON)
134 {
135 s = 0;
136 c = 1;
137 }
138 else if (fabsf(90.0f - theta) < FLT_EPSILON)
139 {
140 s = 1;
141 c = 0;
142 }
143 else if (fabsf(180.0f - theta) < FLT_EPSILON)
144 {
145 s = 0;
146 c = -1;
147 }
148 else if (fabsf(270.0f - theta) < FLT_EPSILON)
149 {
150 s = -1;
151 c = 0;
152 }
153 else
154 {
155 s = sinf(theta * FZ_PI / 180);
156 c = cosf(theta * FZ_PI / 180);
157 }
158
159 m.a = c; m.b = s;
160 m.c = -s; m.d = c;
161 m.e = 0; m.f = 0;
162 return m;
163 }
164
165 fz_matrix
166 fz_pre_rotate(fz_matrix m, float theta)
167 {
168 while (theta < 0)
169 theta += 360;
170 while (theta >= 360)
171 theta -= 360;
172
173 if (fabsf(0 - theta) < FLT_EPSILON)
174 {
175 /* Nothing to do */
176 }
177 else if (fabsf(90.0f - theta) < FLT_EPSILON)
178 {
179 float a = m.a;
180 float b = m.b;
181 m.a = m.c;
182 m.b = m.d;
183 m.c = -a;
184 m.d = -b;
185 }
186 else if (fabsf(180.0f - theta) < FLT_EPSILON)
187 {
188 m.a = -m.a;
189 m.b = -m.b;
190 m.c = -m.c;
191 m.d = -m.d;
192 }
193 else if (fabsf(270.0f - theta) < FLT_EPSILON)
194 {
195 float a = m.a;
196 float b = m.b;
197 m.a = -m.c;
198 m.b = -m.d;
199 m.c = a;
200 m.d = b;
201 }
202 else
203 {
204 float s = sinf(theta * FZ_PI / 180);
205 float c = cosf(theta * FZ_PI / 180);
206 float a = m.a;
207 float b = m.b;
208 m.a = c * a + s * m.c;
209 m.b = c * b + s * m.d;
210 m.c =-s * a + c * m.c;
211 m.d =-s * b + c * m.d;
212 }
213
214 return m;
215 }
216
217 fz_matrix
218 fz_translate(float tx, float ty)
219 {
220 fz_matrix m;
221 m.a = 1; m.b = 0;
222 m.c = 0; m.d = 1;
223 m.e = tx; m.f = ty;
224 return m;
225 }
226
227 fz_matrix
228 fz_pre_translate(fz_matrix m, float tx, float ty)
229 {
230 m.e += tx * m.a + ty * m.c;
231 m.f += tx * m.b + ty * m.d;
232 return m;
233 }
234
235 fz_matrix
236 fz_transform_page(fz_rect mediabox, float resolution, float rotate)
237 {
238 float user_w, user_h, pixel_w, pixel_h;
239 fz_rect pixel_box;
240 fz_matrix matrix;
241
242 /* Adjust scaling factors to cover whole pixels */
243 user_w = mediabox.x1 - mediabox.x0;
244 user_h = mediabox.y1 - mediabox.y0;
245 pixel_w = floorf(user_w * resolution / 72 + 0.5f);
246 pixel_h = floorf(user_h * resolution / 72 + 0.5f);
247
248 matrix = fz_pre_rotate(fz_scale(pixel_w / user_w, pixel_h / user_h), rotate);
249
250 /* Adjust the page origin to sit at 0,0 after rotation */
251 pixel_box = fz_transform_rect(mediabox, matrix);
252 matrix.e -= pixel_box.x0;
253 matrix.f -= pixel_box.y0;
254
255 return matrix;
256 }
257
258 fz_matrix
259 fz_invert_matrix(fz_matrix src)
260 {
261 float a = src.a;
262 float det = a * src.d - src.b * src.c;
263 if (det < -FLT_EPSILON || det > FLT_EPSILON)
264 {
265 fz_matrix dst;
266 float rdet = 1 / det;
267 dst.a = src.d * rdet;
268 dst.b = -src.b * rdet;
269 dst.c = -src.c * rdet;
270 dst.d = a * rdet;
271 a = -src.e * dst.a - src.f * dst.c;
272 dst.f = -src.e * dst.b - src.f * dst.d;
273 dst.e = a;
274 return dst;
275 }
276 return src;
277 }
278
279 int
280 fz_try_invert_matrix(fz_matrix *dst, fz_matrix src)
281 {
282 double sa = (double)src.a;
283 double sb = (double)src.b;
284 double sc = (double)src.c;
285 double sd = (double)src.d;
286 double da, db, dc, dd;
287 double det = sa * sd - sb * sc;
288 if (det >= -DBL_EPSILON && det <= DBL_EPSILON)
289 return 1;
290 det = 1 / det;
291 da = sd * det;
292 dst->a = (float)da;
293 db = -sb * det;
294 dst->b = (float)db;
295 dc = -sc * det;
296 dst->c = (float)dc;
297 dd = sa * det;
298 dst->d = (float)dd;
299 da = -src.e * da - src.f * dc;
300 dst->f = (float)(-src.e * db - src.f * dd);
301 dst->e = (float)da;
302 return 0;
303 }
304
305 int
306 fz_is_rectilinear(fz_matrix m)
307 {
308 return (fabsf(m.b) < FLT_EPSILON && fabsf(m.c) < FLT_EPSILON) ||
309 (fabsf(m.a) < FLT_EPSILON && fabsf(m.d) < FLT_EPSILON);
310 }
311
312 float
313 fz_matrix_expansion(fz_matrix m)
314 {
315 return sqrtf(fabsf(m.a * m.d - m.b * m.c));
316 }
317
318 float
319 fz_matrix_max_expansion(fz_matrix m)
320 {
321 float max = fabsf(m.a);
322 float x = fabsf(m.b);
323 if (max < x)
324 max = x;
325 x = fabsf(m.c);
326 if (max < x)
327 max = x;
328 x = fabsf(m.d);
329 if (max < x)
330 max = x;
331 return max;
332 }
333
334 fz_point
335 fz_transform_point(fz_point p, fz_matrix m)
336 {
337 float x = p.x;
338 p.x = x * m.a + p.y * m.c + m.e;
339 p.y = x * m.b + p.y * m.d + m.f;
340 return p;
341 }
342
343 fz_point
344 fz_transform_point_xy(float x, float y, fz_matrix m)
345 {
346 fz_point p;
347 p.x = x * m.a + y * m.c + m.e;
348 p.y = x * m.b + y * m.d + m.f;
349 return p;
350 }
351
352 fz_point
353 fz_transform_vector(fz_point p, fz_matrix m)
354 {
355 float x = p.x;
356 p.x = x * m.a + p.y * m.c;
357 p.y = x * m.b + p.y * m.d;
358 return p;
359 }
360
361 fz_point
362 fz_normalize_vector(fz_point p)
363 {
364 float len = p.x * p.x + p.y * p.y;
365 if (len != 0)
366 {
367 len = sqrtf(len);
368 p.x /= len;
369 p.y /= len;
370 }
371 return p;
372 }
373
374 /* Rectangles and bounding boxes */
375
376 /* biggest and smallest integers that a float can represent perfectly (i.e. 24 bits) */
377 #define MAX_SAFE_INT 16777216
378 #define MIN_SAFE_INT -16777216
379
380 const fz_rect fz_infinite_rect = { FZ_MIN_INF_RECT, FZ_MIN_INF_RECT, FZ_MAX_INF_RECT, FZ_MAX_INF_RECT };
381 const fz_rect fz_empty_rect = { FZ_MAX_INF_RECT, FZ_MAX_INF_RECT, FZ_MIN_INF_RECT, FZ_MIN_INF_RECT };
382 const fz_rect fz_invalid_rect = { 0, 0, -1, -1 };
383 const fz_rect fz_unit_rect = { 0, 0, 1, 1 };
384
385 const fz_irect fz_infinite_irect = { FZ_MIN_INF_RECT, FZ_MIN_INF_RECT, FZ_MAX_INF_RECT, FZ_MAX_INF_RECT };
386 const fz_irect fz_empty_irect = { FZ_MAX_INF_RECT, FZ_MAX_INF_RECT, FZ_MIN_INF_RECT, FZ_MIN_INF_RECT };
387 const fz_irect fz_invalid_irect = { 0, 0, -1, -1 };
388 const fz_irect fz_unit_bbox = { 0, 0, 1, 1 };
389
390 const fz_quad fz_infinite_quad = { { -INFINITY, INFINITY}, {INFINITY, INFINITY}, {-INFINITY, -INFINITY}, {INFINITY, -INFINITY} };
391 const fz_quad fz_invalid_quad = { {NAN, NAN}, {NAN, NAN}, {NAN, NAN}, {NAN, NAN} };
392
393 fz_irect
394 fz_irect_from_rect(fz_rect r)
395 {
396 fz_irect b;
397 if (fz_is_infinite_rect(r))
398 return fz_infinite_irect;
399 if (!fz_is_valid_rect(r))
400 return fz_invalid_irect;
401
402 b.x0 = fz_clamp(floorf(r.x0), MIN_SAFE_INT, MAX_SAFE_INT);
403 b.y0 = fz_clamp(floorf(r.y0), MIN_SAFE_INT, MAX_SAFE_INT);
404 b.x1 = fz_clamp(ceilf(r.x1), MIN_SAFE_INT, MAX_SAFE_INT);
405 b.y1 = fz_clamp(ceilf(r.y1), MIN_SAFE_INT, MAX_SAFE_INT);
406
407 return b;
408 }
409
410 fz_rect
411 fz_rect_from_irect(fz_irect a)
412 {
413 fz_rect r;
414
415 if (fz_is_infinite_irect(a))
416 return fz_infinite_rect;
417
418 r.x0 = a.x0;
419 r.y0 = a.y0;
420 r.x1 = a.x1;
421 r.y1 = a.y1;
422 return r;
423 }
424
425 fz_irect
426 fz_round_rect(fz_rect r)
427 {
428 fz_irect b;
429 float f;
430
431 f = floorf(r.x0 + 0.001f);
432 b.x0 = fz_clamp(f, MIN_SAFE_INT, MAX_SAFE_INT);
433 f = floorf(r.y0 + 0.001f);
434 b.y0 = fz_clamp(f, MIN_SAFE_INT, MAX_SAFE_INT);
435 f = ceilf(r.x1 - 0.001f);
436 b.x1 = fz_clamp(f, MIN_SAFE_INT, MAX_SAFE_INT);
437 f = ceilf(r.y1 - 0.001f);
438 b.y1 = fz_clamp(f, MIN_SAFE_INT, MAX_SAFE_INT);
439
440 return b;
441 }
442
443 fz_rect
444 fz_intersect_rect(fz_rect a, fz_rect b)
445 {
446 if (fz_is_infinite_rect(b)) return a;
447 if (fz_is_infinite_rect(a)) return b;
448 if (a.x0 < b.x0)
449 a.x0 = b.x0;
450 if (a.y0 < b.y0)
451 a.y0 = b.y0;
452 if (a.x1 > b.x1)
453 a.x1 = b.x1;
454 if (a.y1 > b.y1)
455 a.y1 = b.y1;
456 return a;
457 }
458
459 fz_irect
460 fz_intersect_irect(fz_irect a, fz_irect b)
461 {
462 if (fz_is_infinite_irect(b)) return a;
463 if (fz_is_infinite_irect(a)) return b;
464 if (a.x0 < b.x0)
465 a.x0 = b.x0;
466 if (a.y0 < b.y0)
467 a.y0 = b.y0;
468 if (a.x1 > b.x1)
469 a.x1 = b.x1;
470 if (a.y1 > b.y1)
471 a.y1 = b.y1;
472 return a;
473 }
474
475 fz_rect
476 fz_union_rect(fz_rect a, fz_rect b)
477 {
478 /* Check for empty box before infinite box */
479 if (!fz_is_valid_rect(b)) return a;
480 if (!fz_is_valid_rect(a)) return b;
481 if (fz_is_infinite_rect(a)) return a;
482 if (fz_is_infinite_rect(b)) return b;
483 if (a.x0 > b.x0)
484 a.x0 = b.x0;
485 if (a.y0 > b.y0)
486 a.y0 = b.y0;
487 if (a.x1 < b.x1)
488 a.x1 = b.x1;
489 if (a.y1 < b.y1)
490 a.y1 = b.y1;
491 return a;
492 }
493
494 fz_rect
495 fz_translate_rect(fz_rect a, float xoff, float yoff)
496 {
497 if (fz_is_infinite_rect(a)) return a;
498 a.x0 += xoff;
499 a.y0 += yoff;
500 a.x1 += xoff;
501 a.y1 += yoff;
502 return a;
503 }
504
505 fz_irect
506 fz_translate_irect(fz_irect a, int xoff, int yoff)
507 {
508 int t;
509
510 if (fz_is_empty_irect(a)) return a;
511 if (fz_is_infinite_irect(a)) return a;
512 a.x0 = ADD_WITH_SAT(t, a.x0, xoff);
513 a.y0 = ADD_WITH_SAT(t, a.y0, yoff);
514 a.x1 = ADD_WITH_SAT(t, a.x1, xoff);
515 a.y1 = ADD_WITH_SAT(t, a.y1, yoff);
516 return a;
517 }
518
519 fz_rect
520 fz_transform_rect(fz_rect r, fz_matrix m)
521 {
522 fz_point s, t, u, v;
523 int invalid;
524
525 if (fz_is_infinite_rect(r))
526 return r;
527
528 if (fabsf(m.b) < FLT_EPSILON && fabsf(m.c) < FLT_EPSILON)
529 {
530 if (m.a < 0)
531 {
532 float f = r.x0;
533 r.x0 = r.x1;
534 r.x1 = f;
535 }
536 if (m.d < 0)
537 {
538 float f = r.y0;
539 r.y0 = r.y1;
540 r.y1 = f;
541 }
542 s = fz_transform_point_xy(r.x0, r.y0, m);
543 t = fz_transform_point_xy(r.x1, r.y1, m);
544 r.x0 = s.x; r.y0 = s.y;
545 r.x1 = t.x; r.y1 = t.y;
546 /* If r was invalid coming in, it'll still be invalid now. */
547 return r;
548 }
549 else if (fabsf(m.a) < FLT_EPSILON && fabsf(m.d) < FLT_EPSILON)
550 {
551 if (m.b < 0)
552 {
553 float f = r.x0;
554 r.x0 = r.x1;
555 r.x1 = f;
556 }
557 if (m.c < 0)
558 {
559 float f = r.y0;
560 r.y0 = r.y1;
561 r.y1 = f;
562 }
563 s = fz_transform_point_xy(r.x0, r.y0, m);
564 t = fz_transform_point_xy(r.x1, r.y1, m);
565 r.x0 = s.x; r.y0 = s.y;
566 r.x1 = t.x; r.y1 = t.y;
567 /* If r was invalid coming in, it'll still be invalid now. */
568 return r;
569 }
570
571 invalid = (r.x0 > r.x1) || (r.y0 > r.y1);
572 s.x = r.x0; s.y = r.y0;
573 t.x = r.x0; t.y = r.y1;
574 u.x = r.x1; u.y = r.y1;
575 v.x = r.x1; v.y = r.y0;
576 s = fz_transform_point(s, m);
577 t = fz_transform_point(t, m);
578 u = fz_transform_point(u, m);
579 v = fz_transform_point(v, m);
580 r.x0 = MIN4(s.x, t.x, u.x, v.x);
581 r.y0 = MIN4(s.y, t.y, u.y, v.y);
582 r.x1 = MAX4(s.x, t.x, u.x, v.x);
583 r.y1 = MAX4(s.y, t.y, u.y, v.y);
584
585 /* If we were called with an invalid rectangle, return an
586 * invalid rectangle after transformation. */
587 if (invalid)
588 {
589 float f;
590 f = r.x0; r.x0 = r.x1; r.x1 = f;
591 f = r.y0; r.y0 = r.y1; r.y1 = f;
592 }
593 return r;
594 }
595
596 fz_irect
597 fz_expand_irect(fz_irect a, int expand)
598 {
599 if (fz_is_infinite_irect(a)) return a;
600 if (!fz_is_valid_irect(a)) return a;
601 a.x0 -= expand;
602 a.y0 -= expand;
603 a.x1 += expand;
604 a.y1 += expand;
605 return a;
606 }
607
608 fz_rect
609 fz_expand_rect(fz_rect a, float expand)
610 {
611 if (fz_is_infinite_rect(a)) return a;
612 if (!fz_is_valid_rect(a)) return a;
613 a.x0 -= expand;
614 a.y0 -= expand;
615 a.x1 += expand;
616 a.y1 += expand;
617 return a;
618 }
619
620 /* Adding a point to an invalid rectangle makes the zero area rectangle
621 * that contains just that point. */
622 fz_rect fz_include_point_in_rect(fz_rect r, fz_point p)
623 {
624 if (fz_is_infinite_rect(r)) return r;
625 if (p.x < r.x0) r.x0 = p.x;
626 if (p.x > r.x1) r.x1 = p.x;
627 if (p.y < r.y0) r.y0 = p.y;
628 if (p.y > r.y1) r.y1 = p.y;
629 return r;
630 }
631
632 int fz_contains_rect(fz_rect a, fz_rect b)
633 {
634 /* An invalid rect can't contain anything */
635 if (!fz_is_valid_rect(a))
636 return 0;
637 /* Any valid rect contains all invalid rects */
638 if (!fz_is_valid_rect(b))
639 return 1;
640 return ((a.x0 <= b.x0) &&
641 (a.y0 <= b.y0) &&
642 (a.x1 >= b.x1) &&
643 (a.y1 >= b.y1));
644 }
645
646 int
647 fz_is_valid_quad(fz_quad q)
648 {
649 return (!isnan(q.ll.x) &&
650 !isnan(q.ll.y) &&
651 !isnan(q.ul.x) &&
652 !isnan(q.ul.y) &&
653 !isnan(q.lr.x) &&
654 !isnan(q.lr.y) &&
655 !isnan(q.ur.x) &&
656 !isnan(q.ur.y));
657 }
658
659 int
660 fz_is_infinite_quad(fz_quad q)
661 {
662 /* For a quad to be infinite, all the ordinates need to be infinite. */
663 if (!isinf(q.ll.x) ||
664 !isinf(q.ll.y) ||
665 !isinf(q.ul.x) ||
666 !isinf(q.ul.y) ||
667 !isinf(q.lr.x) ||
668 !isinf(q.lr.y) ||
669 !isinf(q.ur.x) ||
670 !isinf(q.ur.y))
671 return 0;
672
673 /* Just because all the ordinates are infinite, we don't necessarily have an infinite quad. */
674 /* The quad points in order are: ll, ul, ur, lr OR reversed: ll, lr, ur, ul */
675 /* The required points are: (-inf, -inf) (-inf, inf) (inf, inf) (inf, -inf) */
676
677 /* Not the fastest way to code it, but easy to understand! */
678 #define INF_QUAD_TEST(A,B,C,D) \
679 if (q.A.x < 0 && q.A.y < 0 && q.B.x < 0 && q.B.y > 0 && q.C.x > 0 && q.C.y > 0 && q.D.x > 0 && q.D.y < 0) return 1
680
681 INF_QUAD_TEST(ll, ul, ur, lr);
682 INF_QUAD_TEST(ul, ur, lr, ll);
683 INF_QUAD_TEST(ur, lr, ll, ul);
684 INF_QUAD_TEST(lr, ll, ul, ur);
685 INF_QUAD_TEST(ll, lr, ur, ul);
686 INF_QUAD_TEST(lr, ur, ul, ll);
687 INF_QUAD_TEST(ur, ul, ll, lr);
688 INF_QUAD_TEST(ul, ll, lr, ur);
689 #undef INF_QUAD_TEST
690
691 return 0;
692 }
693
694 int fz_is_empty_quad(fz_quad q)
695 {
696 /* Using "Shoelace" formula */
697 float area;
698
699 if (fz_is_infinite_quad(q))
700 return 0;
701 if (!fz_is_valid_quad(q))
702 return 1; /* All invalid quads are empty */
703
704 area = q.ll.x * q.lr.y +
705 q.lr.x * q.ur.y +
706 q.ur.x * q.ul.y +
707 q.ul.x * q.ll.y -
708 q.lr.x * q.ll.y -
709 q.ur.x * q.lr.y -
710 q.ul.x * q.ur.y -
711 q.ll.x * q.ul.y;
712
713 return area == 0;
714 }
715
716 fz_rect
717 fz_rect_from_quad(fz_quad q)
718 {
719 fz_rect r;
720
721 if (!fz_is_valid_quad(q))
722 return fz_invalid_rect;
723 if (fz_is_infinite_quad(q))
724 return fz_infinite_rect;
725
726 r.x0 = MIN4(q.ll.x, q.lr.x, q.ul.x, q.ur.x);
727 r.y0 = MIN4(q.ll.y, q.lr.y, q.ul.y, q.ur.y);
728 r.x1 = MAX4(q.ll.x, q.lr.x, q.ul.x, q.ur.x);
729 r.y1 = MAX4(q.ll.y, q.lr.y, q.ul.y, q.ur.y);
730 return r;
731 }
732
733 fz_quad
734 fz_transform_quad(fz_quad q, fz_matrix m)
735 {
736 if (!fz_is_valid_quad(q))
737 return q;
738 if (fz_is_infinite_quad(q))
739 return q;
740
741 q.ul = fz_transform_point(q.ul, m);
742 q.ur = fz_transform_point(q.ur, m);
743 q.ll = fz_transform_point(q.ll, m);
744 q.lr = fz_transform_point(q.lr, m);
745 return q;
746 }
747
748 fz_quad
749 fz_quad_from_rect(fz_rect r)
750 {
751 fz_quad q;
752
753 if (!fz_is_valid_rect(r))
754 return fz_invalid_quad;
755 if (fz_is_infinite_rect(r))
756 return fz_infinite_quad;
757
758 q.ul = fz_make_point(r.x0, r.y0);
759 q.ur = fz_make_point(r.x1, r.y0);
760 q.ll = fz_make_point(r.x0, r.y1);
761 q.lr = fz_make_point(r.x1, r.y1);
762 return q;
763 }
764
765
766 int fz_is_point_inside_rect(fz_point p, fz_rect r)
767 {
768 return (p.x >= r.x0 && p.x < r.x1 && p.y >= r.y0 && p.y < r.y1);
769 }
770
771 int fz_is_point_inside_irect(int x, int y, fz_irect r)
772 {
773 return (x >= r.x0 && x < r.x1 && y >= r.y0 && y < r.y1);
774 }
775
776 int fz_is_rect_inside_rect(fz_rect inner, fz_rect outer)
777 {
778 if (!fz_is_valid_rect(outer))
779 return 0;
780 if (!fz_is_valid_rect(inner))
781 return 0;
782 if (inner.x0 >= outer.x0 && inner.x1 <= outer.x1 && inner.y0 >= outer.y0 && inner.y1 <= outer.y1)
783 return 1;
784 return 0;
785 }
786
787 int fz_is_irect_inside_irect(fz_irect inner, fz_irect outer)
788 {
789 if (!fz_is_valid_irect(outer))
790 return 0;
791 if (!fz_is_valid_irect(inner))
792 return 0;
793 if (inner.x0 >= outer.x0 && inner.x1 <= outer.x1 && inner.y0 >= outer.y0 && inner.y1 <= outer.y1)
794 return 1;
795 return 0;
796 }
797
798 /* cross (b-a) with (p-a) */
799 static float
800 cross(fz_point a, fz_point b, fz_point p)
801 {
802 b.x -= a.x;
803 b.y -= a.y;
804 p.x -= a.x;
805 p.y -= a.y;
806 return b.x * p.y - b.y * p.x;
807 }
808
809 static int fz_is_point_inside_triangle(fz_point p, fz_point a, fz_point b, fz_point c)
810 {
811 /* Consider the following:
812 *
813 * P
814 * /|
815 * / |
816 * / |
817 * A +---+-------+ B
818 * M
819 *
820 * The cross product of vector AB and vector AP is the distance PM.
821 * The sign of this distance depends on what side of the line AB, P lies on.
822 *
823 * So, for a triangle ABC, if we take cross products of:
824 *
825 * AB and AP
826 * BC and BP
827 * CA and CP
828 *
829 * P can only be inside the triangle if the signs are all identical.
830 *
831 * One of the cross products being 0 indicates that the point is on a line.
832 * Two of the cross products being 0 indicates that the point is on a vertex.
833 *
834 * If 2 of the vertices are the same, the algorithm still works.
835 * Iff all 3 of the vertices are the same, the cross products are all zero. The
836 * value of p is irrelevant.
837 */
838 float crossa = cross(a, b, p);
839 float crossb = cross(b, c, p);
840 float crossc = cross(c, a, p);
841
842 /* Check for degenerate case. All vertices the same. */
843 if (crossa == 0 && crossb == 0 && crossc == 0)
844 return a.x == p.x && a.y == p.y;
845
846 if (crossa >= 0 && crossb >= 0 && crossc >= 0)
847 return 1;
848 if (crossa <= 0 && crossb <= 0 && crossc <= 0)
849 return 1;
850
851 return 0;
852 }
853
854 int fz_is_point_inside_quad(fz_point p, fz_quad q)
855 {
856 if (!fz_is_valid_quad(q))
857 return 0;
858 if (fz_is_infinite_quad(q))
859 return 1;
860
861 return
862 fz_is_point_inside_triangle(p, q.ul, q.ur, q.lr) ||
863 fz_is_point_inside_triangle(p, q.ul, q.lr, q.ll);
864 }
865
866 int fz_is_quad_inside_quad(fz_quad needle, fz_quad haystack)
867 {
868 if (!fz_is_valid_quad(needle) || !fz_is_valid_quad(haystack))
869 return 0;
870 if (fz_is_infinite_quad(haystack))
871 return 1;
872
873 return
874 fz_is_point_inside_quad(needle.ul, haystack) &&
875 fz_is_point_inside_quad(needle.ur, haystack) &&
876 fz_is_point_inside_quad(needle.ll, haystack) &&
877 fz_is_point_inside_quad(needle.lr, haystack);
878 }
879
880 int fz_is_quad_intersecting_quad(fz_quad a, fz_quad b)
881 {
882 fz_rect ar = fz_rect_from_quad(a);
883 fz_rect br = fz_rect_from_quad(b);
884 return !fz_is_empty_rect(fz_intersect_rect(ar, br));
885 }