Line data Source code
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
43 0 : _cairo_box_from_doubles (cairo_box_t *box,
44 : double *x1, double *y1,
45 : double *x2, double *y2)
46 : {
47 0 : box->p1.x = _cairo_fixed_from_double (*x1);
48 0 : box->p1.y = _cairo_fixed_from_double (*y1);
49 0 : box->p2.x = _cairo_fixed_from_double (*x2);
50 0 : box->p2.y = _cairo_fixed_from_double (*y2);
51 0 : }
52 :
53 : cairo_private void
54 0 : _cairo_box_to_doubles (const cairo_box_t *box,
55 : double *x1, double *y1,
56 : double *x2, double *y2)
57 : {
58 0 : *x1 = _cairo_fixed_to_double (box->p1.x);
59 0 : *y1 = _cairo_fixed_to_double (box->p1.y);
60 0 : *x2 = _cairo_fixed_to_double (box->p2.x);
61 0 : *y2 = _cairo_fixed_to_double (box->p2.y);
62 0 : }
63 :
64 : void
65 0 : _cairo_box_from_rectangle (cairo_box_t *box,
66 : const cairo_rectangle_int_t *rect)
67 : {
68 0 : box->p1.x = _cairo_fixed_from_int (rect->x);
69 0 : box->p1.y = _cairo_fixed_from_int (rect->y);
70 0 : box->p2.x = _cairo_fixed_from_int (rect->x + rect->width);
71 0 : box->p2.y = _cairo_fixed_from_int (rect->y + rect->height);
72 0 : }
73 :
74 : void
75 0 : _cairo_boxes_get_extents (const cairo_box_t *boxes,
76 : int num_boxes,
77 : cairo_box_t *extents)
78 : {
79 : int n;
80 :
81 0 : assert (num_boxes > 0);
82 0 : *extents = *boxes;
83 :
84 0 : for (n = 1; n < num_boxes; n++) {
85 0 : if (boxes[n].p1.x < extents->p1.x)
86 0 : extents->p1.x = boxes[n].p1.x;
87 0 : if (boxes[n].p2.x > extents->p2.x)
88 0 : extents->p2.x = boxes[n].p2.x;
89 :
90 0 : if (boxes[n].p1.y < extents->p1.y)
91 0 : extents->p1.y = boxes[n].p1.y;
92 0 : if (boxes[n].p2.y > extents->p2.y)
93 0 : extents->p2.y = boxes[n].p2.y;
94 : }
95 0 : }
96 :
97 : /* This function will return 'true' if the containing_rectangle contains the
98 : * contained_rectangle, and false otherwise.
99 : */
100 : cairo_bool_t
101 0 : _cairo_rectangle_contains (const cairo_rectangle_int_t *containing_rectangle,
102 : const cairo_rectangle_int_t *contained_rectangle)
103 : {
104 0 : if (containing_rectangle->x > contained_rectangle->x ||
105 0 : containing_rectangle->y > contained_rectangle->y)
106 0 : return FALSE;
107 :
108 0 : if (containing_rectangle->x + containing_rectangle->width <
109 0 : contained_rectangle->x + contained_rectangle->width ||
110 0 : containing_rectangle->y + containing_rectangle->height <
111 0 : contained_rectangle->y + contained_rectangle->height)
112 0 : return FALSE;
113 :
114 0 : 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
132 0 : _cairo_box_round_to_rectangle (const cairo_box_t *box,
133 : cairo_rectangle_int_t *rectangle)
134 : {
135 0 : rectangle->x = _cairo_fixed_integer_floor (box->p1.x);
136 0 : rectangle->y = _cairo_fixed_integer_floor (box->p1.y);
137 0 : rectangle->width = _cairo_fixed_integer_ceil (box->p2.x) - rectangle->x;
138 0 : rectangle->height = _cairo_fixed_integer_ceil (box->p2.y) - rectangle->y;
139 0 : }
140 :
141 : cairo_bool_t
142 0 : _cairo_rectangle_intersect (cairo_rectangle_int_t *dst,
143 : const cairo_rectangle_int_t *src)
144 : {
145 : int x1, y1, x2, y2;
146 :
147 0 : x1 = MAX (dst->x, src->x);
148 0 : 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 0 : x2 = MIN (dst->x + (int) dst->width, src->x + (int) src->width);
153 0 : y2 = MIN (dst->y + (int) dst->height, src->y + (int) src->height);
154 :
155 0 : if (x1 >= x2 || y1 >= y2) {
156 0 : dst->x = 0;
157 0 : dst->y = 0;
158 0 : dst->width = 0;
159 0 : dst->height = 0;
160 :
161 0 : return FALSE;
162 : } else {
163 0 : dst->x = x1;
164 0 : dst->y = y1;
165 0 : dst->width = x2 - x1;
166 0 : dst->height = y2 - y1;
167 :
168 0 : 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
192 0 : _cairo_box_intersects_line_segment (cairo_box_t *box, cairo_line_t *line)
193 : {
194 0 : 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 0 : if (_cairo_box_contains_point (box, &line->p1) ||
200 0 : _cairo_box_contains_point (box, &line->p2))
201 0 : return TRUE;
202 :
203 0 : xlen = P2x - P1x;
204 0 : ylen = P2y - P1y;
205 :
206 0 : if (xlen) {
207 0 : if (xlen > 0) {
208 0 : t1 = B1x - P1x;
209 0 : t2 = B2x - P1x;
210 : } else {
211 0 : t1 = P1x - B2x;
212 0 : t2 = P1x - B1x;
213 0 : xlen = - xlen;
214 : }
215 :
216 0 : if (t1 > xlen || t2 < 0)
217 0 : return FALSE;
218 : } else {
219 : /* Fully vertical line -- check that X is in bounds */
220 0 : if (P1x < B1x || P1x > B2x)
221 0 : return FALSE;
222 : }
223 :
224 0 : if (ylen) {
225 0 : if (ylen > 0) {
226 0 : t3 = B1y - P1y;
227 0 : t4 = B2y - P1y;
228 : } else {
229 0 : t3 = P1y - B2y;
230 0 : t4 = P1y - B1y;
231 0 : ylen = - ylen;
232 : }
233 :
234 0 : if (t3 > ylen || t4 < 0)
235 0 : return FALSE;
236 : } else {
237 : /* Fully horizontal line -- check Y */
238 0 : if (P1y < B1y || P1y > B2y)
239 0 : return FALSE;
240 : }
241 :
242 : /* If we had a horizontal or vertical line, then it's already been checked */
243 0 : if (P1x == P2x || P1y == P2y)
244 0 : return TRUE;
245 :
246 : /* Check overlap. Note that t1 < t2 and t3 < t4 here. */
247 0 : t1y = _cairo_int32x32_64_mul (t1, ylen);
248 0 : t2y = _cairo_int32x32_64_mul (t2, ylen);
249 0 : t3x = _cairo_int32x32_64_mul (t3, xlen);
250 0 : t4x = _cairo_int32x32_64_mul (t4, xlen);
251 :
252 0 : if (_cairo_int64_lt(t1y, t4x) &&
253 : _cairo_int64_lt(t3x, t2y))
254 0 : return TRUE;
255 :
256 0 : return FALSE;
257 : }
258 :
259 : cairo_bool_t
260 0 : _cairo_box_contains_point (cairo_box_t *box, const cairo_point_t *point)
261 : {
262 0 : if (point->x < box->p1.x || point->x > box->p2.x ||
263 0 : point->y < box->p1.y || point->y > box->p2.y)
264 0 : return FALSE;
265 0 : return TRUE;
266 : }
|
