1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
2 /* cairo - a vector graphics library with display and print output
3 *
4 * Copyright © 2002 University of Southern California
5 * Copyright © 2005 Red Hat, Inc.
6 * Copyright © 2006 Red Hat, Inc.
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it either under the terms of the GNU Lesser General Public
10 * License version 2.1 as published by the Free Software Foundation
11 * (the "LGPL") or, at your option, under the terms of the Mozilla
12 * Public License Version 1.1 (the "MPL"). If you do not alter this
13 * notice, a recipient may use your version of this file under either
14 * the MPL or the LGPL.
15 *
16 * You should have received a copy of the LGPL along with this library
17 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
19 * You should have received a copy of the MPL along with this library
20 * in the file COPYING-MPL-1.1
21 *
22 * The contents of this file are subject to the Mozilla Public License
23 * Version 1.1 (the "License"); you may not use this file except in
24 * compliance with the License. You may obtain a copy of the License at
25 * http://www.mozilla.org/MPL/
26 *
27 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
28 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
29 * the specific language governing rights and limitations.
30 *
31 * The Original Code is the cairo graphics library.
32 *
33 * The Initial Developer of the Original Code is University of Southern
34 * California.
35 *
36 * Contributor(s):
37 * Carl D. Worth <cworth@cworth.org>
38 */
39
40 #include "cairoint.h"
41
42 cairo_private void
_cairo_box_from_doubles(cairo_box_t * box,double * x1,double * y1,double * x2,double * y2)43 _cairo_box_from_doubles (cairo_box_t *box,
44 double *x1, double *y1,
45 double *x2, double *y2)
46 {
47 box->p1.x = _cairo_fixed_from_double (*x1);
48 box->p1.y = _cairo_fixed_from_double (*y1);
49 box->p2.x = _cairo_fixed_from_double (*x2);
50 box->p2.y = _cairo_fixed_from_double (*y2);
51 }
52
53 cairo_private void
_cairo_box_to_doubles(const cairo_box_t * box,double * x1,double * y1,double * x2,double * y2)54 _cairo_box_to_doubles (const cairo_box_t *box,
55 double *x1, double *y1,
56 double *x2, double *y2)
57 {
58 *x1 = _cairo_fixed_to_double (box->p1.x);
59 *y1 = _cairo_fixed_to_double (box->p1.y);
60 *x2 = _cairo_fixed_to_double (box->p2.x);
61 *y2 = _cairo_fixed_to_double (box->p2.y);
62 }
63
64 void
_cairo_box_from_rectangle(cairo_box_t * box,const cairo_rectangle_int_t * rect)65 _cairo_box_from_rectangle (cairo_box_t *box,
66 const cairo_rectangle_int_t *rect)
67 {
68 box->p1.x = _cairo_fixed_from_int (rect->x);
69 box->p1.y = _cairo_fixed_from_int (rect->y);
70 box->p2.x = _cairo_fixed_from_int (rect->x + rect->width);
71 box->p2.y = _cairo_fixed_from_int (rect->y + rect->height);
72 }
73
74 void
_cairo_boxes_get_extents(const cairo_box_t * boxes,int num_boxes,cairo_box_t * extents)75 _cairo_boxes_get_extents (const cairo_box_t *boxes,
76 int num_boxes,
77 cairo_box_t *extents)
78 {
79 int n;
80
81 assert (num_boxes > 0);
82 *extents = *boxes;
83
84 for (n = 1; n < num_boxes; n++) {
85 if (boxes[n].p1.x < extents->p1.x)
86 extents->p1.x = boxes[n].p1.x;
87 if (boxes[n].p2.x > extents->p2.x)
88 extents->p2.x = boxes[n].p2.x;
89
90 if (boxes[n].p1.y < extents->p1.y)
91 extents->p1.y = boxes[n].p1.y;
92 if (boxes[n].p2.y > extents->p2.y)
93 extents->p2.y = boxes[n].p2.y;
94 }
95 }
96
97 /* This function will return 'true' if the containing_rectangle contains the
98 * contained_rectangle, and false otherwise.
99 */
100 cairo_bool_t
_cairo_rectangle_contains(const cairo_rectangle_int_t * containing_rectangle,const cairo_rectangle_int_t * contained_rectangle)101 _cairo_rectangle_contains (const cairo_rectangle_int_t *containing_rectangle,
102 const cairo_rectangle_int_t *contained_rectangle)
103 {
104 if (containing_rectangle->x > contained_rectangle->x ||
105 containing_rectangle->y > contained_rectangle->y)
106 return FALSE;
107
108 if (containing_rectangle->x + containing_rectangle->width <
109 contained_rectangle->x + contained_rectangle->width ||
110 containing_rectangle->y + containing_rectangle->height <
111 contained_rectangle->y + contained_rectangle->height)
112 return FALSE;
113
114 return TRUE;
115 }
116
117 /* XXX We currently have a confusing mix of boxes and rectangles as
118 * exemplified by this function. A #cairo_box_t is a rectangular area
119 * represented by the coordinates of the upper left and lower right
120 * corners, expressed in fixed point numbers. A #cairo_rectangle_int_t is
121 * also a rectangular area, but represented by the upper left corner
122 * and the width and the height, as integer numbers.
123 *
124 * This function converts a #cairo_box_t to a #cairo_rectangle_int_t by
125 * increasing the area to the nearest integer coordinates. We should
126 * standardize on #cairo_rectangle_fixed_t and #cairo_rectangle_int_t, and
127 * this function could be renamed to the more reasonable
128 * _cairo_rectangle_fixed_round.
129 */
130
131 void
_cairo_box_round_to_rectangle(const cairo_box_t * box,cairo_rectangle_int_t * rectangle)132 _cairo_box_round_to_rectangle (const cairo_box_t *box,
133 cairo_rectangle_int_t *rectangle)
134 {
135 rectangle->x = _cairo_fixed_integer_floor (box->p1.x);
136 rectangle->y = _cairo_fixed_integer_floor (box->p1.y);
137 rectangle->width = _cairo_fixed_integer_ceil (box->p2.x) - rectangle->x;
138 rectangle->height = _cairo_fixed_integer_ceil (box->p2.y) - rectangle->y;
139 }
140
141 cairo_bool_t
_cairo_rectangle_intersect(cairo_rectangle_int_t * dst,const cairo_rectangle_int_t * src)142 _cairo_rectangle_intersect (cairo_rectangle_int_t *dst,
143 const cairo_rectangle_int_t *src)
144 {
145 int x1, y1, x2, y2;
146
147 x1 = MAX (dst->x, src->x);
148 y1 = MAX (dst->y, src->y);
149 /* Beware the unsigned promotion, fortunately we have bits to spare
150 * as (CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN) < UINT_MAX
151 */
152 x2 = MIN (dst->x + (int) dst->width, src->x + (int) src->width);
153 y2 = MIN (dst->y + (int) dst->height, src->y + (int) src->height);
154
155 if (x1 >= x2 || y1 >= y2) {
156 dst->x = 0;
157 dst->y = 0;
158 dst->width = 0;
159 dst->height = 0;
160
161 return FALSE;
162 } else {
163 dst->x = x1;
164 dst->y = y1;
165 dst->width = x2 - x1;
166 dst->height = y2 - y1;
167
168 return TRUE;
169 }
170 }
171
172 #define P1x (line->p1.x)
173 #define P1y (line->p1.y)
174 #define P2x (line->p2.x)
175 #define P2y (line->p2.y)
176 #define B1x (box->p1.x)
177 #define B1y (box->p1.y)
178 #define B2x (box->p2.x)
179 #define B2y (box->p2.y)
180
181 /*
182 * Check whether any part of line intersects box. This function essentially
183 * computes whether the ray starting at line->p1 in the direction of line->p2
184 * intersects the box before it reaches p2. Normally, this is done
185 * by dividing by the lengths of the line projected onto each axis. Because
186 * we're in fixed point, this function does a bit more work to avoid having to
187 * do the division -- we don't care about the actual intersection point, so
188 * it's of no interest to us.
189 */
190
191 cairo_bool_t
_cairo_box_intersects_line_segment(cairo_box_t * box,cairo_line_t * line)192 _cairo_box_intersects_line_segment (cairo_box_t *box, cairo_line_t *line)
193 {
194 cairo_fixed_t t1=0, t2=0, t3=0, t4=0;
195 cairo_int64_t t1y, t2y, t3x, t4x;
196
197 cairo_fixed_t xlen, ylen;
198
199 if (_cairo_box_contains_point (box, &line->p1) ||
200 _cairo_box_contains_point (box, &line->p2))
201 return TRUE;
202
203 xlen = P2x - P1x;
204 ylen = P2y - P1y;
205
206 if (xlen) {
207 if (xlen > 0) {
208 t1 = B1x - P1x;
209 t2 = B2x - P1x;
210 } else {
211 t1 = P1x - B2x;
212 t2 = P1x - B1x;
213 xlen = - xlen;
214 }
215
216 if (t1 > xlen || t2 < 0)
217 return FALSE;
218 } else {
219 /* Fully vertical line -- check that X is in bounds */
220 if (P1x < B1x || P1x > B2x)
221 return FALSE;
222 }
223
224 if (ylen) {
225 if (ylen > 0) {
226 t3 = B1y - P1y;
227 t4 = B2y - P1y;
228 } else {
229 t3 = P1y - B2y;
230 t4 = P1y - B1y;
231 ylen = - ylen;
232 }
233
234 if (t3 > ylen || t4 < 0)
235 return FALSE;
236 } else {
237 /* Fully horizontal line -- check Y */
238 if (P1y < B1y || P1y > B2y)
239 return FALSE;
240 }
241
242 /* If we had a horizontal or vertical line, then it's already been checked */
243 if (P1x == P2x || P1y == P2y)
244 return TRUE;
245
246 /* Check overlap. Note that t1 < t2 and t3 < t4 here. */
247 t1y = _cairo_int32x32_64_mul (t1, ylen);
248 t2y = _cairo_int32x32_64_mul (t2, ylen);
249 t3x = _cairo_int32x32_64_mul (t3, xlen);
250 t4x = _cairo_int32x32_64_mul (t4, xlen);
251
252 if (_cairo_int64_lt(t1y, t4x) &&
253 _cairo_int64_lt(t3x, t2y))
254 return TRUE;
255
256 return FALSE;
257 }
258
259 cairo_bool_t
_cairo_box_contains_point(cairo_box_t * box,const cairo_point_t * point)260 _cairo_box_contains_point (cairo_box_t *box, const cairo_point_t *point)
261 {
262 if (point->x < box->p1.x || point->x > box->p2.x ||
263 point->y < box->p1.y || point->y > box->p2.y)
264 return FALSE;
265 return TRUE;
266 }
267