1#include "mupdf/fitz.h"
2
3#include <math.h>
4#include <float.h>
5#include <limits.h>
6
7#define MAX4(a,b,c,d) fz_max(fz_max(a,b), fz_max(c,d))
8#define MIN4(a,b,c,d) fz_min(fz_min(a,b), fz_min(c,d))
9
10/* A useful macro to add with overflow detection and clamping.
11
12 We want to do "b = a + x", but to allow for overflow. Consider the
13 top bits, and the cases in which overflow occurs:
14
15 overflow a x b ~a^x a^b (~a^x)&(a^b)
16 no 0 0 0 1 0 0
17 yes 0 0 1 1 1 1
18 no 0 1 0 0 0 0
19 no 0 1 1 0 1 0
20 no 1 0 0 0 1 0
21 no 1 0 1 0 0 0
22 yes 1 1 0 1 1 1
23 no 1 1 1 1 0 0
24*/
25#define ADD_WITH_SAT(b,a,x) \
26 ((b) = (a) + (x), (b) = (((~(a)^(x))&((a)^(b))) < 0 ? ((x) < 0 ? INT_MIN : INT_MAX) : (b)))
27
28/* Matrices, points and affine transformations */
29
30const fz_matrix fz_identity = { 1, 0, 0, 1, 0, 0 };
31
32/*
33 Multiply two matrices.
34
35 The order of the two matrices are important since matrix
36 multiplication is not commutative.
37
38 Returns result.
39*/
40fz_matrix
41fz_concat(fz_matrix one, fz_matrix two)
42{
43 fz_matrix dst;
44 dst.a = one.a * two.a + one.b * two.c;
45 dst.b = one.a * two.b + one.b * two.d;
46 dst.c = one.c * two.a + one.d * two.c;
47 dst.d = one.c * two.b + one.d * two.d;
48 dst.e = one.e * two.a + one.f * two.c + two.e;
49 dst.f = one.e * two.b + one.f * two.d + two.f;
50 return dst;
51}
52
53/*
54 Create a scaling matrix.
55
56 The returned matrix is of the form [ sx 0 0 sy 0 0 ].
57
58 m: Pointer to the matrix to populate
59
60 sx, sy: Scaling factors along the X- and Y-axes. A scaling
61 factor of 1.0 will not cause any scaling along the relevant
62 axis.
63
64 Returns m.
65*/
66fz_matrix
67fz_scale(float sx, float sy)
68{
69 fz_matrix m;
70 m.a = sx; m.b = 0;
71 m.c = 0; m.d = sy;
72 m.e = 0; m.f = 0;
73 return m;
74}
75
76/*
77 Scale a matrix by premultiplication.
78
79 m: Pointer to the matrix to scale
80
81 sx, sy: Scaling factors along the X- and Y-axes. A scaling
82 factor of 1.0 will not cause any scaling along the relevant
83 axis.
84
85 Returns m (updated).
86*/
87fz_matrix
88fz_pre_scale(fz_matrix m, float sx, float sy)
89{
90 m.a *= sx;
91 m.b *= sx;
92 m.c *= sy;
93 m.d *= sy;
94 return m;
95}
96
97/*
98 Scale a matrix by postmultiplication.
99
100 m: Pointer to the matrix to scale
101
102 sx, sy: Scaling factors along the X- and Y-axes. A scaling
103 factor of 1.0 will not cause any scaling along the relevant
104 axis.
105
106 Returns m (updated).
107*/
108fz_matrix
109fz_post_scale(fz_matrix m, float sx, float sy)
110{
111 m.a *= sx;
112 m.b *= sy;
113 m.c *= sx;
114 m.d *= sy;
115 m.e *= sx;
116 m.f *= sy;
117 return m;
118}
119
120/*
121 Create a shearing matrix.
122
123 The returned matrix is of the form [ 1 sy sx 1 0 0 ].
124
125 m: pointer to place to store returned matrix
126
127 sx, sy: Shearing factors. A shearing factor of 0.0 will not
128 cause any shearing along the relevant axis.
129
130 Returns m.
131*/
132fz_matrix
133fz_shear(float h, float v)
134{
135 fz_matrix m;
136 m.a = 1; m.b = v;
137 m.c = h; m.d = 1;
138 m.e = 0; m.f = 0;
139 return m;
140}
141
142/*
143 Premultiply a matrix with a shearing matrix.
144
145 The shearing matrix is of the form [ 1 sy sx 1 0 0 ].
146
147 m: pointer to matrix to premultiply
148
149 sx, sy: Shearing factors. A shearing factor of 0.0 will not
150 cause any shearing along the relevant axis.
151
152 Returns m (updated).
153*/
154fz_matrix
155fz_pre_shear(fz_matrix m, float h, float v)
156{
157 float a = m.a;
158 float b = m.b;
159 m.a += v * m.c;
160 m.b += v * m.d;
161 m.c += h * a;
162 m.d += h * b;
163 return m;
164}
165
166/*
167 Create a rotation matrix.
168
169 The returned matrix is of the form
170 [ cos(deg) sin(deg) -sin(deg) cos(deg) 0 0 ].
171
172 m: Pointer to place to store matrix
173
174 degrees: Degrees of counter clockwise rotation. Values less
175 than zero and greater than 360 are handled as expected.
176
177 Returns m.
178*/
179fz_matrix
180fz_rotate(float theta)
181{
182 fz_matrix m;
183 float s;
184 float c;
185
186 while (theta < 0)
187 theta += 360;
188 while (theta >= 360)
189 theta -= 360;
190
191 if (fabsf(0 - theta) < FLT_EPSILON)
192 {
193 s = 0;
194 c = 1;
195 }
196 else if (fabsf(90.0f - theta) < FLT_EPSILON)
197 {
198 s = 1;
199 c = 0;
200 }
201 else if (fabsf(180.0f - theta) < FLT_EPSILON)
202 {
203 s = 0;
204 c = -1;
205 }
206 else if (fabsf(270.0f - theta) < FLT_EPSILON)
207 {
208 s = -1;
209 c = 0;
210 }
211 else
212 {
213 s = sinf(theta * FZ_PI / 180);
214 c = cosf(theta * FZ_PI / 180);
215 }
216
217 m.a = c; m.b = s;
218 m.c = -s; m.d = c;
219 m.e = 0; m.f = 0;
220 return m;
221}
222
223/*
224 Rotate a transformation by premultiplying.
225
226 The premultiplied matrix is of the form
227 [ cos(deg) sin(deg) -sin(deg) cos(deg) 0 0 ].
228
229 m: Pointer to matrix to premultiply.
230
231 degrees: Degrees of counter clockwise rotation. Values less
232 than zero and greater than 360 are handled as expected.
233
234 Returns m (updated).
235*/
236fz_matrix
237fz_pre_rotate(fz_matrix m, float theta)
238{
239 while (theta < 0)
240 theta += 360;
241 while (theta >= 360)
242 theta -= 360;
243
244 if (fabsf(0 - theta) < FLT_EPSILON)
245 {
246 /* Nothing to do */
247 }
248 else if (fabsf(90.0f - theta) < FLT_EPSILON)
249 {
250 float a = m.a;
251 float b = m.b;
252 m.a = m.c;
253 m.b = m.d;
254 m.c = -a;
255 m.d = -b;
256 }
257 else if (fabsf(180.0f - theta) < FLT_EPSILON)
258 {
259 m.a = -m.a;
260 m.b = -m.b;
261 m.c = -m.c;
262 m.d = -m.d;
263 }
264 else if (fabsf(270.0f - theta) < FLT_EPSILON)
265 {
266 float a = m.a;
267 float b = m.b;
268 m.a = -m.c;
269 m.b = -m.d;
270 m.c = a;
271 m.d = b;
272 }
273 else
274 {
275 float s = sinf(theta * FZ_PI / 180);
276 float c = cosf(theta * FZ_PI / 180);
277 float a = m.a;
278 float b = m.b;
279 m.a = c * a + s * m.c;
280 m.b = c * b + s * m.d;
281 m.c =-s * a + c * m.c;
282 m.d =-s * b + c * m.d;
283 }
284
285 return m;
286}
287
288/*
289 Create a translation matrix.
290
291 The returned matrix is of the form [ 1 0 0 1 tx ty ].
292
293 m: A place to store the created matrix.
294
295 tx, ty: Translation distances along the X- and Y-axes. A
296 translation of 0 will not cause any translation along the
297 relevant axis.
298
299 Returns m.
300*/
301fz_matrix
302fz_translate(float tx, float ty)
303{
304 fz_matrix m;
305 m.a = 1; m.b = 0;
306 m.c = 0; m.d = 1;
307 m.e = tx; m.f = ty;
308 return m;
309}
310
311/*
312 Translate a matrix by premultiplication.
313
314 m: The matrix to translate
315
316 tx, ty: Translation distances along the X- and Y-axes. A
317 translation of 0 will not cause any translation along the
318 relevant axis.
319
320 Returns m.
321*/
322fz_matrix
323fz_pre_translate(fz_matrix m, float tx, float ty)
324{
325 m.e += tx * m.a + ty * m.c;
326 m.f += tx * m.b + ty * m.d;
327 return m;
328}
329
330/*
331 Create transform matrix to draw page
332 at a given resolution and rotation. Adjusts the scaling
333 factors so that the page covers whole number of
334 pixels and adjust the page origin to be at 0,0.
335*/
336fz_matrix
337fz_transform_page(fz_rect mediabox, float resolution, float rotate)
338{
339 float user_w, user_h, pixel_w, pixel_h;
340 fz_rect pixel_box;
341 fz_matrix matrix;
342
343 /* Adjust scaling factors to cover whole pixels */
344 user_w = mediabox.x1 - mediabox.x0;
345 user_h = mediabox.y1 - mediabox.y0;
346 pixel_w = floorf(user_w * resolution / 72 + 0.5f);
347 pixel_h = floorf(user_h * resolution / 72 + 0.5f);
348
349 matrix = fz_pre_rotate(fz_scale(pixel_w / user_w, pixel_h / user_h), rotate);
350
351 /* Adjust the page origin to sit at 0,0 after rotation */
352 pixel_box = fz_transform_rect(mediabox, matrix);
353 matrix.e -= pixel_box.x0;
354 matrix.f -= pixel_box.y0;
355
356 return matrix;
357}
358
359/*
360 Create an inverse matrix.
361
362 inverse: Place to store inverse matrix.
363
364 matrix: Matrix to invert. A degenerate matrix, where the
365 determinant is equal to zero, can not be inverted and the
366 original matrix is returned instead.
367
368 Returns inverse.
369*/
370fz_matrix
371fz_invert_matrix(fz_matrix src)
372{
373 float a = src.a;
374 float det = a * src.d - src.b * src.c;
375 if (det < -FLT_EPSILON || det > FLT_EPSILON)
376 {
377 fz_matrix dst;
378 float rdet = 1 / det;
379 dst.a = src.d * rdet;
380 dst.b = -src.b * rdet;
381 dst.c = -src.c * rdet;
382 dst.d = a * rdet;
383 a = -src.e * dst.a - src.f * dst.c;
384 dst.f = -src.e * dst.b - src.f * dst.d;
385 dst.e = a;
386 return dst;
387 }
388 return src;
389}
390
391/*
392 Attempt to create an inverse matrix.
393
394 inverse: Place to store inverse matrix.
395
396 matrix: Matrix to invert. A degenerate matrix, where the
397 determinant is equal to zero, can not be inverted.
398
399 Returns 1 if matrix is degenerate (singular), or 0 otherwise.
400*/
401int
402fz_try_invert_matrix(fz_matrix *dst, fz_matrix src)
403{
404 double sa = (double)src.a;
405 double sb = (double)src.b;
406 double sc = (double)src.c;
407 double sd = (double)src.d;
408 double da, db, dc, dd;
409 double det = sa * sd - sb * sc;
410 if (det >= -DBL_EPSILON && det <= DBL_EPSILON)
411 return 1;
412 det = 1 / det;
413 da = sd * det;
414 dst->a = (float)da;
415 db = -sb * det;
416 dst->b = (float)db;
417 dc = -sc * det;
418 dst->c = (float)dc;
419 dd = sa * det;
420 dst->d = (float)dd;
421 da = -src.e * da - src.f * dc;
422 dst->f = (float)(-src.e * db - src.f * dd);
423 dst->e = (float)da;
424 return 0;
425}
426
427/*
428 Check if a transformation is rectilinear.
429
430 Rectilinear means that no shearing is present and that any
431 rotations present are a multiple of 90 degrees. Usually this
432 is used to make sure that axis-aligned rectangles before the
433 transformation are still axis-aligned rectangles afterwards.
434*/
435int
436fz_is_rectilinear(fz_matrix m)
437{
438 return (fabsf(m.b) < FLT_EPSILON && fabsf(m.c) < FLT_EPSILON) ||
439 (fabsf(m.a) < FLT_EPSILON && fabsf(m.d) < FLT_EPSILON);
440}
441
442/*
443 Calculate average scaling factor of matrix.
444*/
445float
446fz_matrix_expansion(fz_matrix m)
447{
448 return sqrtf(fabsf(m.a * m.d - m.b * m.c));
449}
450
451float
452fz_matrix_max_expansion(fz_matrix m)
453{
454 float max = fabsf(m.a);
455 float x = fabsf(m.b);
456 if (max < x)
457 max = x;
458 x = fabsf(m.c);
459 if (max < x)
460 max = x;
461 x = fabsf(m.d);
462 if (max < x)
463 max = x;
464 return max;
465}
466
467/*
468 Apply a transformation to a point.
469
470 transform: Transformation matrix to apply. See fz_concat,
471 fz_scale, fz_rotate and fz_translate for how to create a
472 matrix.
473
474 point: Pointer to point to update.
475
476 Returns transform (unchanged).
477*/
478fz_point
479fz_transform_point(fz_point p, fz_matrix m)
480{
481 float x = p.x;
482 p.x = x * m.a + p.y * m.c + m.e;
483 p.y = x * m.b + p.y * m.d + m.f;
484 return p;
485}
486
487fz_point
488fz_transform_point_xy(float x, float y, fz_matrix m)
489{
490 fz_point p;
491 p.x = x * m.a + y * m.c + m.e;
492 p.y = x * m.b + y * m.d + m.f;
493 return p;
494}
495
496/*
497 Apply a transformation to a vector.
498
499 transform: Transformation matrix to apply. See fz_concat,
500 fz_scale and fz_rotate for how to create a matrix. Any
501 translation will be ignored.
502
503 vector: Pointer to vector to update.
504*/
505fz_point
506fz_transform_vector(fz_point p, fz_matrix m)
507{
508 float x = p.x;
509 p.x = x * m.a + p.y * m.c;
510 p.y = x * m.b + p.y * m.d;
511 return p;
512}
513
514/*
515 Normalize a vector to length one.
516*/
517fz_point
518fz_normalize_vector(fz_point p)
519{
520 float len = p.x * p.x + p.y * p.y;
521 if (len != 0)
522 {
523 len = sqrtf(len);
524 p.x /= len;
525 p.y /= len;
526 }
527 return p;
528}
529
530/* Rectangles and bounding boxes */
531
532/* biggest and smallest integers that a float can represent perfectly (i.e. 24 bits) */
533#define MAX_SAFE_INT 16777216
534#define MIN_SAFE_INT -16777216
535
536const fz_rect fz_infinite_rect = { 1, 1, -1, -1 };
537const fz_rect fz_empty_rect = { 0, 0, 0, 0 };
538const fz_rect fz_unit_rect = { 0, 0, 1, 1 };
539
540const fz_irect fz_infinite_irect = { 1, 1, -1, -1 };
541const fz_irect fz_empty_irect = { 0, 0, 0, 0 };
542const fz_irect fz_unit_bbox = { 0, 0, 1, 1 };
543
544/*
545 Convert a rect into the minimal bounding box
546 that covers the rectangle.
547
548 Coordinates in a bounding box are integers, so rounding of the
549 rects coordinates takes place. The top left corner is rounded
550 upwards and left while the bottom right corner is rounded
551 downwards and to the right.
552*/
553fz_irect
554fz_irect_from_rect(fz_rect r)
555{
556 fz_irect b;
557 if (fz_is_empty_rect(r))
558 {
559 b.x0 = 0;
560 b.y0 = 0;
561 b.x1 = 0;
562 b.y1 = 0;
563 }
564 else
565 {
566 b.x0 = fz_clamp(floorf(r.x0), MIN_SAFE_INT, MAX_SAFE_INT);
567 b.y0 = fz_clamp(floorf(r.y0), MIN_SAFE_INT, MAX_SAFE_INT);
568 b.x1 = fz_clamp(ceilf(r.x1), MIN_SAFE_INT, MAX_SAFE_INT);
569 b.y1 = fz_clamp(ceilf(r.y1), MIN_SAFE_INT, MAX_SAFE_INT);
570 }
571 return b;
572}
573
574/*
575 Convert a bbox into a rect.
576
577 For our purposes, a rect can represent all the values we meet in
578 a bbox, so nothing can go wrong.
579
580 rect: A place to store the generated rectangle.
581
582 bbox: The bbox to convert.
583
584 Returns rect (updated).
585*/
586fz_rect
587fz_rect_from_irect(fz_irect a)
588{
589 fz_rect r;
590 r.x0 = a.x0;
591 r.y0 = a.y0;
592 r.x1 = a.x1;
593 r.y1 = a.y1;
594 return r;
595}
596
597/*
598 Round rectangle coordinates.
599
600 Coordinates in a bounding box are integers, so rounding of the
601 rects coordinates takes place. The top left corner is rounded
602 upwards and left while the bottom right corner is rounded
603 downwards and to the right.
604
605 This differs from fz_irect_from_rect, in that fz_irect_from_rect
606 slavishly follows the numbers (i.e any slight over/under calculations
607 can cause whole extra pixels to be added). fz_round_rect
608 allows for a small amount of rounding error when calculating
609 the bbox.
610*/
611fz_irect
612fz_round_rect(fz_rect r)
613{
614 fz_irect b;
615 int i;
616
617 i = floorf(r.x0 + 0.001f);
618 b.x0 = fz_clamp(i, MIN_SAFE_INT, MAX_SAFE_INT);
619 i = floorf(r.y0 + 0.001f);
620 b.y0 = fz_clamp(i, MIN_SAFE_INT, MAX_SAFE_INT);
621 i = ceilf(r.x1 - 0.001f);
622 b.x1 = fz_clamp(i, MIN_SAFE_INT, MAX_SAFE_INT);
623 i = ceilf(r.y1 - 0.001f);
624 b.y1 = fz_clamp(i, MIN_SAFE_INT, MAX_SAFE_INT);
625
626 return b;
627}
628
629/*
630 Compute intersection of two rectangles.
631
632 Given two rectangles, update the first to be the smallest
633 axis-aligned rectangle that covers the area covered by both
634 given rectangles. If either rectangle is empty then the
635 intersection is also empty. If either rectangle is infinite
636 then the intersection is simply the non-infinite rectangle.
637 Should both rectangles be infinite, then the intersection is
638 also infinite.
639*/
640fz_rect
641fz_intersect_rect(fz_rect a, fz_rect b)
642{
643 /* Check for empty box before infinite box */
644 if (fz_is_empty_rect(a)) return fz_empty_rect;
645 if (fz_is_empty_rect(b)) return fz_empty_rect;
646 if (fz_is_infinite_rect(b)) return a;
647 if (fz_is_infinite_rect(a)) return b;
648 if (a.x0 < b.x0)
649 a.x0 = b.x0;
650 if (a.y0 < b.y0)
651 a.y0 = b.y0;
652 if (a.x1 > b.x1)
653 a.x1 = b.x1;
654 if (a.y1 > b.y1)
655 a.y1 = b.y1;
656 if (a.x1 < a.x0 || a.y1 < a.y0)
657 return fz_empty_rect;
658 return a;
659}
660
661/*
662 Compute intersection of two bounding boxes.
663
664 Similar to fz_intersect_rect but operates on two bounding
665 boxes instead of two rectangles.
666*/
667fz_irect
668fz_intersect_irect(fz_irect a, fz_irect b)
669{
670 /* Check for empty box before infinite box */
671 if (fz_is_empty_irect(a)) return fz_empty_irect;
672 if (fz_is_empty_irect(b)) return fz_empty_irect;
673 if (fz_is_infinite_irect(b)) return a;
674 if (fz_is_infinite_irect(a)) return b;
675 if (a.x0 < b.x0)
676 a.x0 = b.x0;
677 if (a.y0 < b.y0)
678 a.y0 = b.y0;
679 if (a.x1 > b.x1)
680 a.x1 = b.x1;
681 if (a.y1 > b.y1)
682 a.y1 = b.y1;
683 if (a.x1 < a.x0 || a.y1 < a.y0)
684 return fz_empty_irect;
685 return a;
686}
687
688/*
689 Compute union of two rectangles.
690
691 Given two rectangles, update the first to be the smallest
692 axis-aligned rectangle that encompasses both given rectangles.
693 If either rectangle is infinite then the union is also infinite.
694 If either rectangle is empty then the union is simply the
695 non-empty rectangle. Should both rectangles be empty, then the
696 union is also empty.
697*/
698fz_rect
699fz_union_rect(fz_rect a, fz_rect b)
700{
701 /* Check for empty box before infinite box */
702 if (fz_is_empty_rect(b)) return a;
703 if (fz_is_empty_rect(a)) return b;
704 if (fz_is_infinite_rect(a)) return a;
705 if (fz_is_infinite_rect(b)) return b;
706 if (a.x0 > b.x0)
707 a.x0 = b.x0;
708 if (a.y0 > b.y0)
709 a.y0 = b.y0;
710 if (a.x1 < b.x1)
711 a.x1 = b.x1;
712 if (a.y1 < b.y1)
713 a.y1 = b.y1;
714 return a;
715}
716
717/*
718 Translate bounding box.
719
720 Translate a bbox by a given x and y offset. Allows for overflow.
721*/
722fz_rect
723fz_translate_rect(fz_rect a, float xoff, float yoff)
724{
725 if (fz_is_empty_rect(a)) return a;
726 if (fz_is_infinite_rect(a)) return a;
727 a.x0 += xoff;
728 a.y0 += yoff;
729 a.x1 += xoff;
730 a.y1 += yoff;
731 return a;
732}
733
734fz_irect
735fz_translate_irect(fz_irect a, int xoff, int yoff)
736{
737 int t;
738
739 if (fz_is_empty_irect(a)) return a;
740 if (fz_is_infinite_irect(a)) return a;
741 a.x0 = ADD_WITH_SAT(t, a.x0, xoff);
742 a.y0 = ADD_WITH_SAT(t, a.y0, yoff);
743 a.x1 = ADD_WITH_SAT(t, a.x1, xoff);
744 a.y1 = ADD_WITH_SAT(t, a.y1, yoff);
745 return a;
746}
747
748/*
749 Apply a transform to a rectangle.
750
751 After the four corner points of the axis-aligned rectangle
752 have been transformed it may not longer be axis-aligned. So a
753 new axis-aligned rectangle is created covering at least the
754 area of the transformed rectangle.
755
756 transform: Transformation matrix to apply. See fz_concat,
757 fz_scale and fz_rotate for how to create a matrix.
758
759 rect: Rectangle to be transformed. The two special cases
760 fz_empty_rect and fz_infinite_rect, may be used but are
761 returned unchanged as expected.
762*/
763fz_rect
764fz_transform_rect(fz_rect r, fz_matrix m)
765{
766 fz_point s, t, u, v;
767
768 if (fz_is_infinite_rect(r))
769 return r;
770
771 if (fabsf(m.b) < FLT_EPSILON && fabsf(m.c) < FLT_EPSILON)
772 {
773 if (m.a < 0)
774 {
775 float f = r.x0;
776 r.x0 = r.x1;
777 r.x1 = f;
778 }
779 if (m.d < 0)
780 {
781 float f = r.y0;
782 r.y0 = r.y1;
783 r.y1 = f;
784 }
785 s = fz_transform_point_xy(r.x0, r.y0, m);
786 t = fz_transform_point_xy(r.x1, r.y1, m);
787 r.x0 = s.x; r.y0 = s.y;
788 r.x1 = t.x; r.y1 = t.y;
789 return r;
790 }
791
792 s.x = r.x0; s.y = r.y0;
793 t.x = r.x0; t.y = r.y1;
794 u.x = r.x1; u.y = r.y1;
795 v.x = r.x1; v.y = r.y0;
796 s = fz_transform_point(s, m);
797 t = fz_transform_point(t, m);
798 u = fz_transform_point(u, m);
799 v = fz_transform_point(v, m);
800 r.x0 = MIN4(s.x, t.x, u.x, v.x);
801 r.y0 = MIN4(s.y, t.y, u.y, v.y);
802 r.x1 = MAX4(s.x, t.x, u.x, v.x);
803 r.y1 = MAX4(s.y, t.y, u.y, v.y);
804 return r;
805}
806
807fz_irect
808fz_expand_irect(fz_irect a, int expand)
809{
810 if (fz_is_infinite_irect(a)) return a;
811 a.x0 -= expand;
812 a.y0 -= expand;
813 a.x1 += expand;
814 a.y1 += expand;
815 return a;
816}
817
818/*
819 Expand a bbox by a given amount in all directions.
820*/
821fz_rect
822fz_expand_rect(fz_rect a, float expand)
823{
824 if (fz_is_infinite_rect(a)) return a;
825 a.x0 -= expand;
826 a.y0 -= expand;
827 a.x1 += expand;
828 a.y1 += expand;
829 return a;
830}
831
832/*
833 Expand a bbox to include a given point.
834 To create a rectangle that encompasses a sequence of points, the
835 rectangle must first be set to be the empty rectangle at one of
836 the points before including the others.
837*/
838fz_rect fz_include_point_in_rect(fz_rect r, fz_point p)
839{
840 if (fz_is_infinite_rect(r)) return r;
841 if (p.x < r.x0) r.x0 = p.x;
842 if (p.x > r.x1) r.x1 = p.x;
843 if (p.y < r.y0) r.y0 = p.y;
844 if (p.y > r.y1) r.y1 = p.y;
845 return r;
846}
847
848/*
849 Test rectangle inclusion.
850
851 Return true if a entirely contains b.
852*/
853int fz_contains_rect(fz_rect a, fz_rect b)
854{
855 if (fz_is_empty_rect(b))
856 return 1;
857 if (fz_is_empty_rect(a))
858 return 0;
859 return ((a.x0 <= b.x0) &&
860 (a.y0 <= b.y0) &&
861 (a.x1 >= b.x1) &&
862 (a.y1 >= b.y1));
863}
864
865fz_rect
866fz_rect_from_quad(fz_quad q)
867{
868 fz_rect r;
869 r.x0 = MIN4(q.ll.x, q.lr.x, q.ul.x, q.ur.x);
870 r.y0 = MIN4(q.ll.y, q.lr.y, q.ul.y, q.ur.y);
871 r.x1 = MAX4(q.ll.x, q.lr.x, q.ul.x, q.ur.x);
872 r.y1 = MAX4(q.ll.y, q.lr.y, q.ul.y, q.ur.y);
873 return r;
874}
875
876fz_quad
877fz_transform_quad(fz_quad q, fz_matrix m)
878{
879 q.ul = fz_transform_point(q.ul, m);
880 q.ur = fz_transform_point(q.ur, m);
881 q.ll = fz_transform_point(q.ll, m);
882 q.lr = fz_transform_point(q.lr, m);
883 return q;
884}
885
886int fz_is_point_inside_rect(fz_point p, fz_rect r)
887{
888 return (p.x >= r.x0 && p.x < r.x1 && p.y >= r.y0 && p.y < r.y1);
889}
890
891int fz_is_point_inside_irect(int x, int y, fz_irect r)
892{
893 return (x >= r.x0 && x < r.x1 && y >= r.y0 && y < r.y1);
894}
895
896int fz_is_point_inside_quad(fz_point p, fz_quad q)
897{
898 // TODO: non-rectilinear quads
899 return fz_is_point_inside_rect(p, fz_rect_from_quad(q));
900}
901